?數據結構導論2009年10月真題（02142）

數據結構導論2009年10月真題及答案解析（02142）

數據結構導論2009年10月真題及答案（02142），該試卷為數據結構導論自考歷年真題試卷，包含答案及詳細解析。

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

1.在表長為n的順序表上做插入運算，平均要移動的結點數為(　　)

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

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

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

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

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

4.元素的進棧次序為A，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.由帶權為9，2，5，7的四個葉子結點構造一棵哈夫曼樹，該樹的帶權路徑長度為(　　)

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

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

A.O(1)

B.

C.O(n)

D.

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

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

8.在查找順序表各結點概率相等的情況下，順序按值查找某個元素的算法時間復雜度為(　　)

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

C.O()

D.

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

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.在線性表的下列存儲結構中進行插入、刪除運算，花費時間最多的是(　　)

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

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

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

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

A.n/2
B.n

C.

D.

13.冒泡排序的時間復雜度是(　　)

A.

B.

C.O(n)

D.

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

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

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

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

二、填空題(本大題共13小題，每小題2分，共26分)請在每小題的空格中填上正確答案。錯填、不填均無分。

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

12.數據的邏輯結構被分為集合結構、________、樹形結構和圖狀結構4種。

13.線性表中所含結點的個數稱為________。

14.向一個棧頂指針為top的鏈棧中插入一個新結點*p時，應執(zhí)行________和top=p操作。

15.設一個順序棧S，元素s1，s2，s3，s4，s5，s6依次進棧，如果6個元素的退棧順序為s2，s3，s4，s6，s5，s1，則順序棧的容量至少為________。

16.若滿二叉樹的結點數為n，則其高度為________。

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

18.深度為k的二叉樹，結點數最多有________個。

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

110.在一個具有n個頂點的無向圖中，頂點的度最大可達________。

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

112.順序查找算法的平均查找長度為________。

113.二路歸并排序的平均時間復雜度為________。

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

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

22.已知一棵二叉樹的順序存儲結構如題30圖所示，其中∧表示虛結點，試構造該二叉樹。

23.題31圖中二叉排序樹的各結點的值為1～9，標出各結點的值。題31圖

24.寫出題32圖所示的有向圖的鄰接矩陣及該圖的所有拓撲排序序列。                                     題32圖

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

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

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

32.設順序表va中的數據元素遞增有序。試編寫算法實現將x插入到順序表的適當位置上，以保持該表的有序性。