數(shù)據(jù)結(jié)構(gòu)期末試卷及參考答案B

《數(shù)據(jù)結(jié)構(gòu)》試卷（B）學(xué)號(hào)：姓名：日期：題號(hào)一二三四五總分得分一.選擇題（每小題2分，共30分，請(qǐng)寫在答卷紙上）：1.下面程序的時(shí)間復(fù)雜為（）。for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}A.O(n) B.O(n2) C.O(n3) D.O(n4)2.設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，則數(shù)據(jù)結(jié)構(gòu)A是（）。A.線性結(jié)構(gòu) B.樹型結(jié)構(gòu) C.物理結(jié)構(gòu) D.圖狀結(jié)構(gòu)3.設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A，若刪除單鏈表中結(jié)點(diǎn)A，則需要修改指針的操作序列為（）。A.q=p->next；p->data=q->data；p->next=q->next；free(q)；B.q=p->next；q->data=p->data；p->next=q->next；free(q)；C.q=p->next；p->next=q->next；free(q)；D.q=p->next；p->data=q->data；free(q)；4.棧和隊(duì)列的共同特點(diǎn)是()。A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出C.都是先進(jìn)先出D.沒有共同點(diǎn)5.設(shè)某棵二叉樹的中序遍歷序列為ABCD，先序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（）。A.BADC B.BCDA C.CDAB D.CBDA6.設(shè)有一個(gè)二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每個(gè)元素占一個(gè)空間，問A[3][3](10)存放在什么位置？腳注(10)表示用10進(jìn)制表示。A．688B．678C．692D7.設(shè)一組權(quán)值集合W={2，3，4，5，6}，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長(zhǎng)度之和為（）。A.20 B.30 C.40 D.458.執(zhí)行一趟快速排序能夠得到的序列是（）。A.[41，12，34，45，27]55[72，63]B.[45，34，12，41]55[72，63，27]C.[63，12，34，45，27]55[41，72]D.[12，27，45，41]55[34，63，72]9．設(shè)一條單鏈表的頭指針變量為head且該鏈表沒有頭結(jié)點(diǎn)，則其判空條件是（）。A.head==0 B.head->next==0C.head->next==head10.設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（）。A.任一結(jié)點(diǎn)無左孩子 B.高度等于其結(jié)點(diǎn)數(shù)C.空或只有一個(gè)結(jié)點(diǎn) D.任一結(jié)點(diǎn)無右孩子11.第一趟排序結(jié)束后不一定能夠選出一個(gè)最大元素放在其最后位置上的是（）。A.堆排序 B.冒泡排序 C.快速排序 D.選擇排序12．設(shè)某棵三叉樹中有40個(gè)結(jié)點(diǎn)，則該三叉樹的最小高度為（）。A.3B.6 C.5D.13.深度為k的完全二叉樹中最少有（）個(gè)結(jié)點(diǎn)。A.2k-1-1 B.2k-1 C.2k-1+1 D.2k14.設(shè)某哈夫曼樹中有199個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有（）個(gè)葉子結(jié)點(diǎn)。A.99B.100C.101 D.15.設(shè)用鄰接矩陣A表示有向圖G的存儲(chǔ)結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為（）。A.第i行非0元素的個(gè)數(shù)之和 B.第i列非0元素的個(gè)數(shù)之和C.第i行0元素的個(gè)數(shù)之和 D.第i列0元素的個(gè)數(shù)之和二．填空（每題2分，共20分，請(qǐng)寫在答卷紙上）1.

數(shù)據(jù)結(jié)構(gòu)是相互之間的存在一種或多種【】的數(shù)據(jù)元素的集合。當(dāng)結(jié)點(diǎn)之間存在M對(duì)N（M：N）的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為【】。2.根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為【】。3.設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則第i個(gè)位置上插入一個(gè)數(shù)據(jù)元素需要移動(dòng)表中【】個(gè)數(shù)據(jù)元素；刪除第i個(gè)位置上的數(shù)據(jù)元素需要移動(dòng)表中【】個(gè)元素。4.設(shè)一組初始記錄關(guān)鍵字序列為(20，18，22，16，30，19)，則根據(jù)這些初始關(guān)鍵字序列建成的初始小頂堆為【】。5.設(shè)有向圖G的二元組形式表示為G=（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，則給出該圖的一種拓?fù)渑判蛐蛄小尽俊?．設(shè)二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為50，度數(shù)為1的結(jié)點(diǎn)數(shù)為30，則該二叉樹中總共有【】個(gè)結(jié)點(diǎn)數(shù)。7.設(shè)二叉樹中結(jié)點(diǎn)的兩個(gè)指針域分別為lchild和rchild，則判斷指針變量p所指向的結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是【】。8.已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下：從頂點(diǎn)1出發(fā)，深度優(yōu)先遍歷的輸出序列是【】，廣度優(yōu)先遍歷的輸出序列是【】。9.設(shè)散列表的長(zhǎng)度為8，散列函數(shù)H(k)=k%7，用線性探測(cè)法解決沖突，則根據(jù)一組初始關(guān)鍵字序列(8，15，16，22，30,32)構(gòu)造出的散列表的平均查找長(zhǎng)度是【】。10.已知廣義表A=(a，((b，c)，d))，函數(shù)Gethead(Gettail(A))的運(yùn)算結(jié)果是【】。11.設(shè)一棵完全二叉樹中有50個(gè)結(jié)點(diǎn)，則該二叉樹的深度為【】；若用二叉鏈表作為該完全二叉樹的存儲(chǔ)結(jié)構(gòu)，則共有【】個(gè)空指針域。三.判斷題（每小題1分，共10分，請(qǐng)寫在答卷紙上）1.有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)的個(gè)數(shù)不一定相等。()2.對(duì)鏈表進(jìn)行插入和刪除操作時(shí)不必移動(dòng)鏈表中結(jié)點(diǎn)。()3.分塊查找的平均查找長(zhǎng)度不僅與索引表的長(zhǎng)度有關(guān)，而且與塊的長(zhǎng)度有關(guān)。()4.若一個(gè)葉子結(jié)點(diǎn)是某二叉樹的中序遍歷序列的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的先序遍歷序列中的最后一個(gè)結(jié)點(diǎn)。()5.設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT，則二叉樹BT中一定沒有右子樹。()6.用鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)，則其所占用的存儲(chǔ)空間與圖中頂點(diǎn)數(shù)無關(guān)而與圖中邊數(shù)有關(guān)。()7.中序遍歷一棵二叉排序樹可以得到一個(gè)有序的序列。()8.入棧操作和入隊(duì)列操作在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)時(shí)不需要考慮棧溢出的情況。()9.順序表查找指的是在順序存儲(chǔ)結(jié)構(gòu)上進(jìn)行查找。（）10.堆是完全二叉樹，完全二叉樹不一定是堆。（）四.應(yīng)用題（每題6分，共30分）1.已知二叉樹的前序遍歷序列是AEFBGCDHIKJ，中序遍歷序列是EFAGBCHKIJD，畫出此二叉樹，并畫出它的后序線索二叉樹。2．已知待散列的線性表為（36，15，40，63，22），散列用的一維地址空間為[0..6]，假定選用的散列函數(shù)是H（K）=Kmod7，若發(fā)生沖突采用線性探查法處理，試：（1）計(jì)算出每一個(gè)元素的散列地址并在下圖中填寫出散列表：`0123456（2）求出在查找每一個(gè)元素概率相等情況下的平均查找長(zhǎng)度。3.設(shè)一組有序的記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求畫出折半查找過程的判定樹并計(jì)算出查找成功時(shí)的平均查找長(zhǎng)度。4.設(shè)一棵樹T中邊的集合為{(A，B)，(A，C)，(A，D)，(B，E)，(C，F(xiàn))，(C，G)}，要求用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲(chǔ)結(jié)構(gòu)并將該樹轉(zhuǎn)化成對(duì)應(yīng)的二叉樹。5.設(shè)有無向圖G，要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。五算法設(shè)計(jì)（8分）1.統(tǒng)計(jì)出單鏈表HL中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù)。intCountX(LNode*HL,ElemTypex)參考答案一、選擇題（每小題2分，共30分）題號(hào)123456789101112131415答案BBAAAADAACCDBBB二、填空題（每小題2分，共22分）1關(guān)系圖狀結(jié)構(gòu)233n-in-i4(16,18,19,20,30,22)51->3->2->4->561297p->lchild==NULL&&p->rchild==NULL81,3,4,5,21,3,2,4,598/310((b,c),d)11651三、判斷題（每小題1分，共10分）題號(hào)12345678910答案NYYNYNYNNY四.應(yīng)用題1.解:(1)二叉樹如下:(2)后序線索二叉樹如下:ABGDHIABGDHIcKJEFABGDHIcKJEF2.解:(1)01234566336152240(2)平均查找長(zhǎng)度=(1+2+1+1+3)/5=8/53.解:(1)折半查找過程的判定樹構(gòu)造如下：4718471862132450833590