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

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

1.下列算法的時(shí)間復(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的順序表中做刪除運(yùn)算，平均移動(dòng)元素的次數(shù)為(　　)

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

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

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

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

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

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

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

7.循環(huán)隊(duì)列存儲在數(shù)組A[m]中，則入隊(duì)列操作中隊(duì)列尾指針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é)點(diǎn)個(gè)數(shù)最多為(　　)

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

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

A.

B.

C.

D.

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

A.0個(gè)
B.10個(gè)
C.19個(gè)
D.20個(gè)

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

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

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

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

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

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

14.直接選擇排序算法的時(shí)間復(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é)點(diǎn)的后面插入一個(gè)新結(jié)點(diǎn) * t，需要修改四個(gè)指針，分別為：t->prior=P; t->next=P->next; p->next—>prior=t; _______;。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23.寫出題31圖所示有向圖頂點(diǎn)的所有拓?fù)渑判蛐蛄小?img style="width: 253px; height: 147px;" src="https://status.shangxueba.com/exam/2019-03-21/922016760766233.png" width="302" height="178"/>

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

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

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

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

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