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

《數(shù)據(jù)結(jié)構(gòu)》試卷（B）

學(xué)號：姓名：日期：

題號—?二三四五總分

得分

一.選擇題（每小題2分，共30分，請寫在答卷紙上）：

1.下面程序的時間復(fù)雜為（）。

for(i=l,s=0；i<=n；i++){t=l；for(j=l；j<=i；j++)t=t*j；s=s+t；}

A.0(n)B.0(n2)C.0(n3)D.0(n)

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é)點A,若刪除單鏈表中結(jié)點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.棧和隊列的共同特點是（）o

A.只允許在端點處插入和刪除元素

B.都是先進(jìn)后出

C.都是先進(jìn)先出

D.沒有共同點

5.設(shè)某棵二叉樹的中序遍歷序列為ABCD,先序遍歷序列為CABD,則后序遍歷該二叉樹得到

序列為（）o

A.BADCB.BCDAC.CDABD.CBDA

6.設(shè)有一個二維數(shù)組萩加,假設(shè)加0][0]存放位置在644（10）,m2][2]存放位置在676（10）,

每個元素占一個空間，問加3][3]（助存放在什么位置？腳注的表示用10進(jìn)制表示。

A.688B.678C.692D.696

7.設(shè)一組權(quán)值集合W={2,3,4,5,6},則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之

和為（）。

A.20B.30C.40D.45

8.執(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é)點，則其判空條件是（）。

A.head==0B.head->next==0C.head->next==headD.head!=0

10.設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（）。

A.任一結(jié)點無左孩子B.高度等于其結(jié)點數(shù)

C.空或只有一個結(jié)點D.任一結(jié)點無右孩子

11.第一趟排序結(jié)束后不一定能夠選出一個最大元素放在其最后位置上的是（）。

A.堆排序B.冒泡排序C.快速排序D.選擇排序

12.設(shè)某棵三叉樹中有40個結(jié)點，則該三叉樹的最小高度為（）。

A.3B.6C.5D.4

13.深度為k的完全二叉樹中最少有（）個結(jié)點。

A.2卜二1B.2k-1C.2k-1+lD.2-1

14.設(shè)某哈夫曼樹中有199個結(jié)點，則該哈夫曼樹中有（）個葉子結(jié)點。

A.99B.100C.101D.102

15.設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點i的入度為（）。

A.第i行非0元素的個數(shù)之和B.第i列非0元素的個數(shù)之和

C.第i行0元素的個數(shù)之和D.第i列。元素的個數(shù)之和

二.填空（每題2分，共20分，請寫在答卷紙上）

1.數(shù)據(jù)結(jié)構(gòu)是相互之間的存在一種或多種L1的數(shù)據(jù)元素的集合。當(dāng)結(jié)點之間存在M對

N（M：N）的聯(lián)系時，稱這種結(jié)構(gòu)為_LL。

2.根據(jù)初始關(guān)鍵字序列（19,22,01,38,10）建立的二叉排序樹的高度為_LJ_。

3.設(shè)順序線性表中有n個數(shù)據(jù)元素，則第i個位置上插入一個數(shù)據(jù)元素需要移動表中_LJ_

個數(shù)據(jù)元素；刪除第i個位置上的數(shù)據(jù)元素需要移動表中U個元素。

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ù)渑判蛐蛄衉LJ_。

6.設(shè)二叉樹中度數(shù)為0的結(jié)點數(shù)為50,度數(shù)為1的結(jié)點數(shù)為30,則該二叉樹中總共有_LJ

個結(jié)點數(shù)。

7.設(shè)二叉樹中結(jié)點的兩個指針域分別為Ichild和rchild,則判斷指針變量p所指向的結(jié)點

為葉子結(jié)點的條件是【】。

8.已知一有向圖的鄰接表存儲結(jié)構(gòu)如下：從頂點1出發(fā)，深度優(yōu)先遍歷的輸出序列是

【】,廣度優(yōu)先遍歷的輸出序列是LL。

圖的鄰接表存儲結(jié)構(gòu)

9.設(shè)散列表的長度為8,散列函數(shù)H（k）=k%7,用線性探測法解決沖突，則根據(jù)一組初始

關(guān)鍵字序列（8,15,16,22,30,32）構(gòu)造出的散列表的平均查找長度是LJ。

10.已知廣義表A=(a,((b,c),d)),函數(shù)Gethead(Gettail(A))的運算結(jié)果是1］。

11.設(shè)一棵完全二叉樹中有50個結(jié)點，則該二叉樹的深度為【】；若用二叉鏈表作為該完

全二叉樹的存儲結(jié)構(gòu)，則共有【1個空指針域。

三.判斷題（每小題1分，共10分，請寫在答卷紙上）

1.有向圖的鄰接表和逆鄰接表中表結(jié)點的個數(shù)不一定相等。（）

2.對鏈表進(jìn)行插入和刪除操作時不必移動鏈表中結(jié)點。（）

3.分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。（）

4.若一個葉子結(jié)點是某二叉樹的中序遍歷序列的最后一個結(jié)點，則它必是該二叉樹的先序

遍歷序列中的最后一個結(jié)點。（）

5.設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT,則二叉樹BT中一定沒有右子樹。（）

6.用鄰接矩陣作為圖的存儲結(jié)構(gòu)時，則其所占用的存儲空間與圖中頂點數(shù)無關(guān)而與圖中邊

數(shù)有關(guān)。（）

7.中序遍歷一棵二叉排序樹可以得到一個有序的序列。（）

8.入棧操作和入隊列操作在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實現(xiàn)時不需要考慮棧溢出的情況。（）

9.順序表查找指的是在順序存儲結(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）計算出每一個元素的散列地址并在下圖中填寫出散列表：

（2）求出在查找每一個元素概率相等情況下的平均查找長度。

3.設(shè)一組有序的記錄關(guān)鍵字序列為（13,18,24,35,47,50,62,83,90）,查找方法用

二分查找，要求畫出折半查找過程的判定樹并計算出查找成功時的平均查找長度。

4.設(shè)一棵樹T中邊的集合為｛（A,B）,（A,C）,（A,D）,（B,E）,（C,F）,（C,G）｝,要求

用孩子兄弟表示法（二叉鏈表）表示出該樹的存儲結(jié)構(gòu)并將該樹轉(zhuǎn)化成對應(yīng)的二叉樹。

5.設(shè)有無向圖G,要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。

五算法設(shè)計（8分）

1.統(tǒng)計出單鏈表HL中結(jié)點的值等于給定值X的結(jié)點數(shù)。

intCountX（LNode*HL,ElemTypex）

參考答案

一、選擇題（每小題2分，共30分）

題號123456789101112131415

答案BBAAAADAACCDBBB

二、填空題（每小題2分，共22分）

1關(guān)系圖狀結(jié)構(gòu)

23

3n-in-i

4(16,18,19,20,30,22)

5l->3->2->4->5

6129

7p->lchild==NULL&&p->rchild==NULL

81,3,