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

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

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

1.下列算法的時間復(fù)雜度為(　　)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.根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常將數(shù)據(jù)結(jié)構(gòu)分為四類基本結(jié)構(gòu)，即(　　)

A.集合、順序結(jié)構(gòu)、樹形結(jié)構(gòu)、圖結(jié)構(gòu)
B.集合、線性結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)、圖結(jié)構(gòu)
C.集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖結(jié)構(gòu)
D.線性結(jié)構(gòu)、順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)、圖結(jié)構(gòu)

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

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

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

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

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

A.運算算法實現(xiàn)簡單
B.便于隨機存取數(shù)據(jù)
C.不需要預(yù)先分配存儲空間
D.結(jié)點個數(shù)受到限制

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

A.鏈棧不用預(yù)先考慮容量的大小
B.鏈棧出棧時不需要判斷?？?br/>C.鏈棧進棧時需要判斷棧滿
D.鏈棧出棧時需要判斷棧滿

7.循環(huán)隊列存儲在數(shù)組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的二叉樹，結(jié)點個數(shù)最多為(　　)

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

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

A.

B.

C.

D.

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

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

11.設(shè)圖的頂點數(shù)為n，則采用鄰接矩陣作為存儲結(jié)構(gòu)的圖的深度優(yōu)先搜索算法的時間復(fù)雜度為(　　)

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)，當(dāng)二分查找值為126的元素時，檢索成功需進行的比較次數(shù)為(　　)

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

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

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

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

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

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

11.在數(shù)據(jù)庫中，_____又稱為字段或域。

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

13.線性表中所含結(jié)點的個數(shù)稱為_______。

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

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

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

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

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

19.一個樹的最少結(jié)點個數(shù)為_______。

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

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

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

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

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

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

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

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

24.將題32圖所示的一棵樹轉(zhuǎn)換為二叉樹。

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

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

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

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