數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2009年10月真題及答案解析（02142）

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2009年10月真題及答案（02142），該試卷為數(shù)據(jù)結(jié)構(gòu)導(dǎo)論自考?xì)v年真題試卷，包含答案及詳細(xì)解析。

一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。

1.在表長(zhǎng)為n的順序表上做插入運(yùn)算，平均要移動(dòng)的結(jié)點(diǎn)數(shù)為(　　)

A.n/4
B.n/3
C.n/2
D.n

2.順序表中有19個(gè)元素，第一個(gè)元素的地址為200，且每個(gè)元素占一個(gè)字節(jié)，則第14個(gè)元素的存儲(chǔ)地址為(　　)

A.212
B.213
C.214
D.215

3.由頂點(diǎn)V1，V2，V3構(gòu)成的圖的鄰接矩陣為，則該圖中頂點(diǎn)V1的出度為(　　)

A.0
B.1
C.2
D.3

4.元素的進(jìn)棧次序?yàn)锳，B，C，D，E，則退棧中不可能的序列是(　　)

A.A，B，C，D，E
B.B，C，D，E，A
C.E，A，B，C，D
D.E，D，C，B，A

5.由帶權(quán)為9，2，5，7的四個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長(zhǎng)度為(　　)

A.23
B.37
C.44
D.46

6.在已知尾指針的單循環(huán)鏈表中，插入一個(gè)新結(jié)點(diǎn)使之成為首結(jié)點(diǎn)，其算法的時(shí)間復(fù)雜度為(　　)

A.O(1)

B.

D.

7.已知一個(gè)有序表為(13，18，24，35，47，50，62，83，90，115，134)，當(dāng)二分查找值為90的元素時(shí)，查找成功時(shí)需比較的次數(shù)為(　　)

A.1
B.2
C.3
D.4

8.在查找順序表各結(jié)點(diǎn)概率相等的情況下，順序按值查找某個(gè)元素的算法時(shí)間復(fù)雜度為(　　)

A.O(1)
B.O(n)

C.O()

D.

9.下列各項(xiàng)鍵值序列中不是堆的為(　　)

A.{5，23，16，68，94，72，71，73}
B.{5，16，23，68，94，72，71，73}
C.{5，23，16，73，94，72，71，68}
D.{5，23，16，68，73，71，72，94}

10.在線性表的下列存儲(chǔ)結(jié)構(gòu)中進(jìn)行插入、刪除運(yùn)算，花費(fèi)時(shí)間最多的是(　　)

A.單鏈表
B.雙鏈表
C.順序表
D.單循環(huán)鏈表

11.在棧中進(jìn)行插入和刪除操作的一端稱為(　　)

A.棧頂
B.棧底
C.任意位置
D.指定位置

12.用n個(gè)值構(gòu)造一棵二叉排序樹，它的最大高度為(　　)

A.n/2
B.n

C.

D.

13.冒泡排序的時(shí)間復(fù)雜度是(　　)

A.

B.

D.

14.設(shè)無向圖的鄰接表如題14圖所示，則該圖的邊數(shù)為(　　)                                        題14圖

A.4
B.5
C.10
D.20

15.帶表頭結(jié)點(diǎn)鏈隊(duì)列的隊(duì)頭和隊(duì)尾指針分別為front和rear，則判斷隊(duì)空的條件為(　　)

A.front==rear
B.front!=NULL
C.rear!=NULL
D.front==NULL

二、填空題(本大題共13小題，每小題2分，共26分)請(qǐng)?jiān)诿啃☆}的空格中填上正確答案。錯(cuò)填、不填均無分。

11.下列程序段的時(shí)間復(fù)雜度為________。i=0; s=0;while(i<n){   i++;    s=s+i;}

12.數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合結(jié)構(gòu)、________、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)4種。

13.線性表中所含結(jié)點(diǎn)的個(gè)數(shù)稱為________。

14.向一個(gè)棧頂指針為top的鏈棧中插入一個(gè)新結(jié)點(diǎn)*p時(shí)，應(yīng)執(zhí)行________和top=p操作。

15.設(shè)一個(gè)順序棧S，元素s1，s2，s3，s4，s5，s6依次進(jìn)棧，如果6個(gè)元素的退棧順序?yàn)閟2，s3，s4，s6，s5，s1，則順序棧的容量至少為________。

16.若滿二叉樹的結(jié)點(diǎn)數(shù)為n，則其高度為________。

17.在一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹中，從樹根起，自上而下、從左到右地給所有結(jié)點(diǎn)編號(hào)。若編號(hào)為i的結(jié)點(diǎn)有父結(jié)點(diǎn)，那么其父結(jié)點(diǎn)的編號(hào)為________。

18.深度為k的二叉樹，結(jié)點(diǎn)數(shù)最多有________個(gè)。

19.某二叉樹的后根遍歷為ABKCBPM，則該二叉樹的根為________。

110.在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，頂點(diǎn)的度最大可達(dá)________。

111.有向圖G的鄰接矩陣為A，如果圖中存在弧，則A[i][j]的值為________。

112.順序查找算法的平均查找長(zhǎng)度為________。

113.二路歸并排序的平均時(shí)間復(fù)雜度為________。

三、應(yīng)用題(本大題共5小題，每小題6分，共30分)

21.某通訊電文由A，B，C，D，E，F(xiàn)六個(gè)字符編碼組成，每個(gè)字符編碼在電文中出現(xiàn)的次數(shù)分別是6，5，9，10，20，1，試畫出這六個(gè)字符編碼所用的哈夫曼樹。

22.已知一棵二叉樹的順序存儲(chǔ)結(jié)構(gòu)如題30圖所示，其中∧表示虛結(jié)點(diǎn)，試構(gòu)造該二叉樹。

23.題31圖中二叉排序樹的各結(jié)點(diǎn)的值為1～9，標(biāo)出各結(jié)點(diǎn)的值。題31圖

24.寫出題32圖所示的有向圖的鄰接矩陣及該圖的所有拓?fù)渑判蛐蛄小?img style="width: 375px; height: 270px;" src="https://status.shangxueba.com/exam/2019-03-20/921941860769462.png" width="1783" height="1280"/>                                     題32圖

25.寫出鍵值(83，40，63，13，84，35，96，57，39，79，61，15)應(yīng)用二路歸并排序算法從小到大排序后各趟的結(jié)果。

四、算法設(shè)計(jì)題(本大題共2小題，每小題7分，共14分)

31.若兩棵二叉樹B1和B2皆為空，或者皆不空且B1的左、右子樹和B2的左、右子樹分別相似，則稱二叉樹B1和B2相似。試編寫算法，判別給定兩棵二叉樹是否相似。

32.設(shè)順序表va中的數(shù)據(jù)元素遞增有序。試編寫算法實(shí)現(xiàn)將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。