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

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

一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的。請將其選出并將“答題卡”的相應代碼涂黑。未涂、錯涂或多涂均無分。

1.下列算法的時間復雜度為(　　)for( i=1; i<=n; i++){  m++;   for(j=1; i<=n; j++)        k*=m;}

A.O(n)
B.O(n²)
C.O(n³)
D.O(log₂n)

2.根據數據元素之間關系的不同特性，通常將數據結構分為四類基本結構，即(　　)

A.集合、順序結構、樹形結構、圖結構
B.集合、線性結構、鏈式結構、圖結構
C.集合、線性結構、樹形結構、圖結構
D.線性結構、順序結構、鏈式結構、圖結構

3.在表長為101的順序表中做刪除運算，平均移動元素的次數為(　　)

A.25
B.50
C.51
D.100

4.在表長為n的順序表中做插入運算的時間復雜度為(　　)

A.O(n)
B.O(log₂n)
C.O(1)
D.O(n²)

5.單鏈表與順序表相比，其特點是(　　)

A.運算算法實現簡單
B.便于隨機存取數據
C.不需要預先分配存儲空間
D.結點個數受到限制

6.關于鏈棧的說法，正確的是(　　)

A.鏈棧不用預先考慮容量的大小
B.鏈棧出棧時不需要判斷棧空
C.鏈棧進棧時需要判斷棧滿
D.鏈棧出棧時需要判斷棧滿

7.循環隊列存儲在數組A[m]中，則入隊列操作中隊列尾指針rear的變化為(　　)

A.rear=rear+1
B.rear=(rear+1)%(m-1)
C.rear=(rear+1)%m
D.rear=(rear+1)%(m+1)

8.深度為k的二叉樹，結點個數最多為(　　)

A.2^k
B.2^k-1
C.2^k-1
D.2k-1

9.已知一棵度為k的樹中有n1個度為1的結點，n2個度為2的結點，……，nk個度為k的結點，則該樹中的葉結點個數為(　　)

A.

B.

C.

D.

10.具有10個葉結點的哈夫曼樹中度為1的結點數為(　　)

A.0個
B.10個
C.19個
D.20個

11.設圖的頂點數為n，則采用鄰接矩陣作為存儲結構的圖的深度優先搜索算法的時間復雜度為(　　)

A.O(1)
B.O(n)
C.O(n²)
D.O(log₂n)

12.n個頂點的無向圖若采用鄰接矩陣存儲，則該矩陣的大小是(　　)

A.n×(n-1)
B.(n-1)×(n-1)
C.(n+1)×(n+1)
D.n×n

13.已知一個有序表為(15，19，30，33，49，50，65，88，93，126，164)，當二分查找值為126的元素時，檢索成功需進行的比較次數為(　　)

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

14.直接選擇排序算法的時間復雜度為(　　)

A.O(1)
B.O(log²n)
C.O(n)
D.O(n²)

15.下述四種排序算法中，所需輔助存儲量最多的是(　　)

A.堆排序
B.快速排序
C.歸并排序
D.直接選擇排序

二、填空題(本大題共13小題，每小題2分。共26分)

11.在數據庫中，_____又稱為字段或域。

12.雙向循環鏈表中，在P所指結點的后面插入一個新結點 * t，需要修改四個指針，分別為：t->prior=P; t->next=P->next; p->next—>prior=t; _______;。

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

14.在帶有頭結點的循環鏈表中，頭指針為head，判斷P所指結點為尾結點的條件是_________

15.鏈棧LS中，Ls->next指向棧頂結點，則新結點 * P入棧的操作為：P->next=LS->next;和_______;。

16.為了節省存儲空間，將矩陣中多個值相同的元素只分配一個存儲空間，零元素不存儲，這種存儲方式通常稱為矩陣的________。

17.100個結點的二叉樹采用二叉鏈表存儲時，空指針域NULL有______個。

18.已知完全二叉樹的第5層有5個結點，則整個完全二叉樹有________個葉結點。

19.一個樹的最少結點個數為_______。

110.索引順序表由兩部分組成：一個是順序表，另一個是_______。

111.二叉排序樹上的平均查找長度介于________和O(n)之間。

112.二分查找算法的時間復雜度是________。

113.最好情況下，冒泡排序算法的時間復雜度為_______，它是一種穩定的排序方法。

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

21.如題29圖所示，在棧的輸入端元素的輸入順序為A，5，8，試寫出在棧的輸出端可以得到的以數字開頭的所有輸出序列，并寫出進棧、出棧的操作過程(用push(X)表示X進棧，pop(x)表示x出棧)。

22.分別寫出題30圖所示二叉樹的先序遍歷、中序遍歷和后序遍歷的結點序列。

23.寫出題31圖所示有向圖頂點的所有拓撲排序序列。

24.將題32圖所示的一棵樹轉換為二叉樹。

25.判斷序列(28，75，33，68，25，56，47，99，86，36)是否為堆?如果不是，則把它調整為堆(最小堆)。

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

31.單鏈表的結構定義如下：typedef struct node{  int data;    struct node *next;}Node, *LinkList;試編寫算法int CountLinklist(LinkList head,int x)實現在帶頭結點的單鏈表head中計算值為x的結點數。

32.假設線性表中結點是按鍵值遞增的順序排列，試編寫一個順序查找算法，將崗哨設在高下標端。并說明等概率情況下查找成功和不成功時的平均查找長度。