大學(xué)計(jì)算機(jī)《數(shù)據(jù)結(jié)構(gòu)》試卷及答案(三)

大學(xué)計(jì)算機(jī)《數(shù)據(jù)結(jié)構(gòu)》試卷及答案一、單選題（每小題2分，共8分）1nx（x()。A n B n/2 C (n+1)/2 D (n-1)/22,qp所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn),qps所指的結(jié)點(diǎn),則執(zhí)行()。As→link=p→link;p→link=s;Bp→link=s;s→link=q;Cp→link=s→link;s→link=p;Dq→link=s;s→link=p;3、棧的插入和刪除操作在（）進(jìn)行。A 棧頂 B 棧底 C 任意位置 D 指定位置4、由權(quán)值分別為徑長度為（）A 24 B 71 C 48 D 53二、 填空題（每空1分，共32分）1、數(shù)據(jù)的邏輯結(jié)構(gòu)被分為 、 、 和 四種。2、一種抽象數(shù)據(jù)類型包括 和 兩個(gè)部分。3在下面的數(shù)組a中鏈接存儲(chǔ)著一個(gè)線性表表頭指針為則該性表為 。a 0 1 2 3 4 5 6 7 860564260564238742543762014在以HL為表頭指針的帶表頭附加結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中判斷表為空的條件分別為 和 。5、用具有n個(gè)元素的一維數(shù)組存儲(chǔ)一個(gè)循環(huán)隊(duì)列，則其隊(duì)首指針總是指隊(duì)首元素的 ，該循環(huán)隊(duì)列的最大長度為 。6、當(dāng)堆棧采用順序存儲(chǔ)結(jié)構(gòu)時(shí)，棧頂元素的值可用———————表示當(dāng)堆棧采用鏈接存儲(chǔ)結(jié)構(gòu)時(shí)，棧頂元素的值可用 表示。7一棵高度為5的二叉樹中最少含有 個(gè)結(jié)點(diǎn)最多含有 個(gè)結(jié)點(diǎn)；一棵高度為5的理想平衡樹中最少含有 個(gè)結(jié)點(diǎn)最多含有 個(gè)結(jié)點(diǎn)8、在圖的鄰接表中，每個(gè)結(jié)點(diǎn)被稱為 ，通常它包含三個(gè)域一是 ；二是 ；三是 。9、在一個(gè)索引文件的索引表中，每個(gè)索引項(xiàng)包含對應(yīng)記錄的 和 兩項(xiàng)數(shù)據(jù)。10、 假定一棵樹的廣義表表示為（（C（（J），則樹中所含的結(jié)點(diǎn)數(shù)為 個(gè)，樹的深度為 ,樹的度為 ,結(jié)點(diǎn)H的雙親結(jié)點(diǎn)為 ,孩子結(jié)點(diǎn)為 。11、 在堆排序的過程中，對任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為 ,整個(gè)堆排序過程的時(shí)間復(fù)雜度為 。12、 在對m階的B_樹插入元素的過程中，每向一個(gè)結(jié)點(diǎn)插入一個(gè)索引項(xiàng)（葉子結(jié)點(diǎn)中的索引項(xiàng)為關(guān)鍵字和空指針）后，若該結(jié)點(diǎn)的索引項(xiàng)數(shù)等 個(gè)，則必須把它分裂為 個(gè)結(jié)點(diǎn)。三、 運(yùn)算題（每小題6分，共24分）1、已知一組記錄的排序碼為467956384080, 9524，寫出其進(jìn)行快速排序的每一次劃分結(jié)果。2、一個(gè)線性表為B=（12，23，45，57，20，03，78，31，15，36HT[0..12]，散列函數(shù)為H（key）=key%13突，請畫出散列表，并計(jì)算等概率情況下查找成功的平均查找長度。3ABECKFGHIJEBCDAFHIGJ，試寫出這棵二叉樹的后序遍歷結(jié)果。4VG如下：V0，1，2，3，4，5，6，7，8，9}；E=（0，1（0，41，21，7（，（3，4（3，（5，6，5，8（5，9（6，7（7，8（8，9）}當(dāng)它用鄰接矩陣表示和鄰接表表示時(shí)，分別寫出從頂點(diǎn)V0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列和按廣度優(yōu)先搜索遍歷等到的頂點(diǎn)序列。假定每個(gè)頂點(diǎn)鄰接表中的結(jié)點(diǎn)是按頂點(diǎn)序號從大到小的次序鏈接的。圖圖鄰接表表示時(shí)深度優(yōu)先序列廣度優(yōu)先序列四、 閱讀算法，回答問題（每小題8分，共16分）1、假定從鍵盤上輸入一批整數(shù)，依次為63 45 30 91 34 –1，寫出輸出結(jié)果。#include<iostream.h>#include<stdlib.h>consstintstackmaxsize=30;typedefintelemtype;structstack{elemtypestack[stackmaxsize];inttop;};#include“stack.h”main(){stacka;initstack(a);intx;cin>>x;while(x!=-1){push(a,x);cin>>x;}while(!stackempty(a))cout<<pop(a)<<”cout<<end1;}該算法的輸出結(jié)果為： .2、閱讀以下二叉樹操作算法，指出該算法的功能Template<calss type>void BinTree<Type>：unknown(BinTreeNode<Type>*t) {BinTreeNode<Type> *p=t,if(p!=NULL){temp=p→leftchild;p→leftchild=p→rightchild;p→rightchild=temp;unknown(p→leftchild);undnown(p→rightchild);}}該算法的功能是： 五、 算法填空，在畫有橫線的地方填寫合適的內(nèi)容（10分）對順序存儲(chǔ)的有序表進(jìn)行二分查找的遞歸算法。intBinsch(ElemTypeA[],intlow,inthigh,KeyTypeK){if(low<=high){intmid=1if(K==A[mid].key)returnmid;elseif(K<A[mid].key)return2else}

return3elsereturn 4六、 編寫算法（10分）Lnodea1，……an-1，an,an，an-1，……a1。contrary(Lnode*&HL)數(shù)據(jù)結(jié)構(gòu)試題（答案）題號答案1C2D題號答案1C2D3A4B二、填空題（132分1：集合、線性、樹、圖；2：數(shù)據(jù)描述、操作聲名；3：38562560474；4：HL→next；5：前一個(gè)位置；n-1；6：S.stack[S.top]; 7：5 318：邊結(jié)點(diǎn)、鄰接點(diǎn)域、權(quán)域、鏈域；9：索引值域、開始位置域；10：10、、、、I1：（lo2nO(nlo2n);12：m、m-1劃分次序劃分結(jié)果三、運(yùn)算題（624分1劃分次序劃分結(jié)果第一次[382440]46[56809579]第二次24[3840]46[56809579]第三次24384046[56809579]第四次2438404656[809579]第五次243840465679[8095]第六次24384046567980952、0 1 2 3 4 5 6 7 8 9 10 11 127878150357452031233612SUCC=14/10=34、圖鄰接矩陣表示時(shí)鄰接表表示時(shí)

深度優(yōu)先序列0，1，2，8，3，4，5，6，7，90，4，3，8，9，5，6，7，1，2

廣度優(yōu)先序列0，1，4，2，7，3，8，6，5，90，4，1，3，7，2，8，6，9，5四、閱讀算法，回答問題（每小題8分，共16分）1、1、該算法的輸入結(jié)果是91 30 45 63 782、2、該算法的功能是：交換二叉樹的左右子樹的遞歸算法。五、算法填空，在畫有橫線的地方填寫合適的內(nèi)容（10