數(shù)據(jù)結(jié)構(gòu)試卷（一）.一、單選題（每題只允許在端點(diǎn)處插入和刪除元素.B.都是先進(jìn)后出C.都是先進(jìn)先出.D.沒有共同點(diǎn)僅修改尾指針D.頭、尾指針可能都要修改.(10)存放在什么位置？腳注(10)表示用10進(jìn)制表示。.A．688B．678C．692D．696.A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素.C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù).二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為(-1B.2K+1C.2K-1若有18個(gè)元素的有序表存放在一維數(shù)組A[19]中，第一個(gè)元素放A[1]中，現(xiàn)進(jìn)行二分查找，則查找A［3］的比較序列的下標(biāo)依次為(作為散列函數(shù)，則散列地址為1的元素有（A．1B．2C．3D．4.10.設(shè)有6個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有(A.5B.6C.7D.8.二、填空題（每空1分，共26假定一棵樹的廣義表表示為A（C，D（E，F(xiàn)，G），H（I，J）），則樹中所含的結(jié)點(diǎn)數(shù)為__________的值為__________。中綴算式（3+4X）-2Y/3對(duì)應(yīng)的后綴算式為______若用鏈表存儲(chǔ)一棵二叉樹時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指針。在這種存儲(chǔ)結(jié)構(gòu)中，n個(gè)結(jié)點(diǎn)的二叉樹共有________個(gè)指針域，其中有________個(gè)指針域是存放了地址，有________________個(gè)指針是空指針。.對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無向圖，在其對(duì)應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別有______在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中，包含有________條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有________條邊。.假定一個(gè)線性表為(12,23,74,55,63,40)，若按Key條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個(gè)子表，則得到的四個(gè)子表分別為____________________________、___________________、______10.向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點(diǎn)的分裂，則新樹比原樹的高度___________。.11.在堆排序的過程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為________，整個(gè)堆排序過程的時(shí)間復(fù)雜度為________。.12.在快速排序、堆排序、歸并排序中，_________排序是穩(wěn)定的。.三、計(jì)算題（每題next，試寫出該線性表。.data605078903440next已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為：V={1,2,3,4,5,6,7};.E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,.(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};.用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。.實(shí)用文檔四、閱讀算法（每題7分，共14S1：whinext=q；qnext=NULL；.請(qǐng)回答下列問題：.（1）說明語句S1的功能；.（2）說明語句組S2的功能；.（3）設(shè)鏈表表示的線性表為（a1,voidABC(BTNodeABC(BT-lefABC(BT-right該算法的功能是：.五、算法填空（共8二叉搜索樹的查找——遞歸算法:.boolFind(BTreeNode*BST,ElemType&item).(BST==NULL).returnfalse;//查找失敗.else(item==BST-data){.item=BST-data;//查找成功.return實(shí)用文檔elseif(itemBST-data).returnFind(______________,item);.elsereturnFind(_______________,item);.CountX(LNode*HL,ElemType實(shí)用文檔數(shù)據(jù)結(jié)構(gòu)試卷（二）.線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn).2．設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m，若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹中總共有（4m.3．設(shè)順序循環(huán)隊(duì)列Q[0：M-1]的頭指針和尾指針分別為F和R，頭指針F總是指向隊(duì)頭元素的前一位置，尾指針R總是指向隊(duì)尾元素的當(dāng)前位置(曹縣很富嗎？曹縣是山東省管轄的一個(gè)縣。從該縣2020年完成的宏觀經(jīng)濟(jì)指標(biāo)來看，GDP已經(jīng)超過460億元，屬于全市為數(shù)不多GDP突破460億的縣，綜合經(jīng)濟(jì)實(shí)力相對(duì)較強(qiáng)。)，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為（CBDA.5．設(shè)某完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中有（6．設(shè)某棵二叉樹中有2000個(gè)結(jié)點(diǎn)，則該二叉樹的最小高度為（12.7．設(shè)某有向圖中有n個(gè)頂點(diǎn)，則該有向圖對(duì)應(yīng)的鄰接表中有（）個(gè)表頭結(jié)點(diǎn)。.2n-1.8．設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確的語句。.op;}sqsvoidpush(sqsack&stack,op==m-1)print設(shè)某棵二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為N1，則該二叉樹中度數(shù)為2的結(jié)點(diǎn)數(shù)為_________；若采用二叉鏈表作為該二叉樹的存儲(chǔ)結(jié)構(gòu)，則該二叉樹中共有_______個(gè)空指針域。.