2019年10月自考02331數(shù)據(jù)結(jié)構(gòu)試題及答案含解析

數(shù)據(jù)結(jié)構(gòu)年月真題

02331201910

1、【單選題】下列選項(xiàng)中,不宜采用鏈?zhǔn)酱鎯?chǔ)的是

無(wú)向圖

單鏈表

A:

最優(yōu)二叉樹(shù)

B:

數(shù)組

C:

答D:案：D

2、【單選題】將10個(gè)數(shù)據(jù)元素保存在順序棧S中,若棧頂元素的存儲(chǔ)地址是100,棧中每個(gè)

元素占4個(gè)存儲(chǔ)單元,進(jìn)棧按Stop=S.top+1修改棧頂,則棧底元素的存儲(chǔ)地址是

60

64

A:

136

B:

140

C:

答D:案：B

3、【單選題】設(shè)指針變量head指向循環(huán)鏈表的頭結(jié)點(diǎn),next是結(jié)點(diǎn)的指針域,則判斷此鏈表

為空的條件是

head->next==NULL

head->next==head

A:

head->next!=NULL

B:

head->next!=head->next

C:

答D:案：B

4、【單選題】已知廣義表LS=(((a,b,c)),((d,(e)),(f,(g))),(h,g),i),LS的深度是

4

3

A:

2

B:

1

C:

答D:案：A

5、【單選題】已知一棵完全二叉樹(shù)T共有7個(gè)分支結(jié)點(diǎn),則T中葉子結(jié)點(diǎn)個(gè)數(shù)最少是

7

A:

8

9

B:

10

C:

答D:案：A

6、【單選題】在一棵非空二叉樹(shù)的后序遍歷序列中,所有列在根結(jié)點(diǎn)前面的是

左子樹(shù)中的部分結(jié)點(diǎn)

右子樹(shù)中的全部結(jié)點(diǎn)

A:

左右子樹(shù)中的全部結(jié)點(diǎn)

B:

左右子樹(shù)中的部分結(jié)點(diǎn)

C:

答D:案：C

解析：在一棵非空二叉樹(shù)的后序遍歷序列中，所有出現(xiàn)在根節(jié)點(diǎn)前面的元素都是左子樹(shù)和

右子樹(shù)中的全部節(jié)點(diǎn)。后序遍歷是一種遍歷二叉樹(shù)的方式，它的遍歷順序是先遍歷左子

樹(shù)，再遍歷右子樹(shù)，最后訪(fǎng)問(wèn)根節(jié)點(diǎn)。因此，在后序遍歷序列中，根節(jié)點(diǎn)的位置是在最后

的。假設(shè)后序遍歷序列為[L1,L2,...,Ln,R1,R2,...,Rm,Root]，其中L1,

L2,...,Ln是左子樹(shù)的節(jié)點(diǎn)，R1,R2,...,Rm是右子樹(shù)的節(jié)點(diǎn)，Root是根節(jié)點(diǎn)。由于

后序遍歷的特性，我們可以觀(guān)察到，在序列中，所有出現(xiàn)在根節(jié)點(diǎn)前面的元素都是左子樹(shù)

和右子樹(shù)中的全部節(jié)點(diǎn)。也就是說(shuō)，L1,L2,...,Ln,R1,R2,...,Rm都是左子樹(shù)和右

子樹(shù)中的節(jié)點(diǎn)，而Root是根節(jié)點(diǎn)。這個(gè)特性可以用來(lái)判斷一個(gè)序列是否是一個(gè)合法的后

序遍歷序列，以及還原二叉樹(shù)的結(jié)構(gòu)。

7、【單選題】用鄰接表保存有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖,鄰接表中指針個(gè)數(shù)是

e

n-e

A:

n+e

B:

n+2e

C:

答D:案：D

解析：在鄰接表中保存有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖時(shí)，每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)鏈表，鏈表中

存儲(chǔ)與該頂點(diǎn)相鄰的其他頂點(diǎn)。對(duì)于每個(gè)頂點(diǎn)，我們需要一個(gè)指針來(lái)指向與之相鄰的頂

點(diǎn)。由于無(wú)向圖中的每條邊都會(huì)連接兩個(gè)頂點(diǎn)，所以每個(gè)頂點(diǎn)的鏈表中需要存儲(chǔ)與之相鄰

的頂點(diǎn)的信息?？紤]到每條邊都會(huì)在兩個(gè)頂點(diǎn)之間建立連接，所以總共有2e個(gè)指針。而

每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)鏈表，所以需要n個(gè)指針來(lái)指向這些鏈表。因此，鄰接表中指針的個(gè)

數(shù)是n+2e。其中n表示頂點(diǎn)的個(gè)數(shù)，2e表示邊的個(gè)數(shù)乘以2，是因?yàn)槊織l邊都會(huì)在兩個(gè)

頂點(diǎn)之間建立連接。

8、【單選題】有向圖G中某個(gè)頂點(diǎn)的出度和入度均為2,則G中的頂點(diǎn)個(gè)數(shù)最少是

2

3

A:

4

B:

5

C:

答D:案：B

9、【單選題】在帶權(quán)圖的最短路徑問(wèn)題中,路徑長(zhǎng)度是指

路徑上邊的數(shù)目

路徑上結(jié)點(diǎn)的數(shù)目

A:

路徑上邊的權(quán)值之和

B:

到達(dá)終點(diǎn)的最短路徑數(shù)目

C:

答D:案：C

解析：在交通網(wǎng)絡(luò)中，常常會(huì)提出許多這樣的問(wèn)題：兩地之間是否有路相通，在有多條通

路的情況下，哪--條最近，哪一條花費(fèi)最少，等等。交通網(wǎng)絡(luò)可以用帶權(quán)圖表示，圖中頂

點(diǎn)表示城鎮(zhèn)，邊表示兩城鎮(zhèn)之間的道路，邊上的權(quán)值可表示兩城鎮(zhèn)間的距離、交通費(fèi)用或

途中所需的時(shí)間等。上述這些問(wèn)題就是在帶權(quán)圖中求最短路徑的問(wèn)題。此時(shí)的路徑長(zhǎng)度的

度量不再是路徑上邊的數(shù)目，而是路徑上邊的權(quán)值之和。P158

10、【單選題】對(duì)數(shù)據(jù)序列(15,10,8,12,15,8,10)按升序進(jìn)行希爾排序,增量序列為5,3,兩

趟排序后,得到的排序結(jié)果為

8,8,10,10,15,15,12

8,8,10,10,12,15,15

A:

8,10,8,10,15,15,12

B:

8,10,8,10,12,15,15

C:

答D:案：C

11、【單選題】下列排序方法中,不穩(wěn)定的排序方法是

直接選擇排序

歸并排序

A:

直接插入排序

B:

基數(shù)排序

C:

答D:案：A

解析：直接選擇排序是一種不穩(wěn)定的排序方法。在直接選擇排序中，每次從未排序的元素

中選擇最小（或最大）的元素，然后將其放置在已排序序列的末尾。這個(gè)過(guò)程會(huì)破壞相同

元素之間的相對(duì)順序，導(dǎo)致排序結(jié)果不穩(wěn)定。

12、【單選題】一組記錄的關(guān)鍵字為(35,58,24,13,44,19,10),利用堆排序算法進(jìn)行降序排

序,要求空間復(fù)雜度為O(1),建立的初始堆為

10,13,19,58,44,35,24

10,13,35,58,44,19,24

A:

58,44,24,13,35,19,10

B:

58,35,24,13,44,19,10

C:

答D:案：A

13、【單選題】一棵二叉排序樹(shù)中,關(guān)鍵字n所在結(jié)點(diǎn)的層數(shù)大于關(guān)鍵字m所在結(jié)點(diǎn)的層數(shù),

則

n一定大于m

n一定小于m

A:

n一定等于m

B:

n與m的大小關(guān)系不確定

C:

答D:案：D

14、【單選題】設(shè)散列表長(zhǎng)m=10,散列函數(shù)H(key)=key%9.表中已保存3個(gè)關(guān)鍵

字:H(13)=4,H(32)=5,H(15)=6,其余地址均為空。保存關(guān)鍵字23時(shí)存在沖突,采用線(xiàn)性探查法

來(lái)處理。則查找關(guān)鍵字23時(shí)的探查次數(shù)是

1

2

A:

3

B:

4

C:

答D:案：C

15、【單選題】下面關(guān)于m階(m≥3)B樹(shù)的敘述中,正確的是

終端結(jié)點(diǎn)可位于不同層

非終端結(jié)點(diǎn)至多有m+1棵子樹(shù)

A:

若樹(shù)非空,則根結(jié)點(diǎn)至少有2個(gè)關(guān)鍵字

B:

每個(gè)非根結(jié)點(diǎn)包含n個(gè)關(guān)鍵字,[m/2]-1≤n≤m-1

C:

答D:案：D

16、【問(wèn)答題】設(shè)電文字符集是{e1,e2,e3,e4,e5,e6},它們出現(xiàn)的次數(shù)分別

為:38,12,17,26,14,20。現(xiàn)要為該字符集設(shè)計(jì)一種哈夫曼編碼。請(qǐng)回答下列問(wèn)題。(1)畫(huà)出得

到的哈夫曼樹(shù)。(2)給出各符號(hào)的哈夫曼編碼。

答案：

17、【問(wèn)答題】

答案：(1)ABDEFGCABDEGFC(2)ABCDEFGABCDEGFACBDEFG

18、【問(wèn)答題】有以下關(guān)鍵字序列(15,20,24,32,15,7,14,23),使用快速排序方法將其按升

序排列。請(qǐng)回答下列問(wèn)題。(1)若取第一個(gè)關(guān)鍵字為基準(zhǔn),寫(xiě)出第一趟快速排序的結(jié)果。(2)若

取最后一個(gè)關(guān)鍵字為基準(zhǔn),寫(xiě)出第一趟快速排序的結(jié)果

答案：(1)14,7,15,32,15,24,20,23(2)15,20,14,7,15,23,32,24

19、【問(wèn)答題】

答案：

20、【問(wèn)答題】

答案：(1)3,5,9,10,2,30,(2)用給定的整數(shù)建立順序表,奇數(shù)從頭插入,偶數(shù)從表尾插

入。

21、【問(wèn)答題】

答案：

22、【問(wèn)答題】。

答案：(1)R[mid].key==k(2)mid-1(3)mid+1

23、【問(wèn)答題】

答案：(1)Q[front]!=NULL(2)rear%2(3)front++

24、【問(wèn)答題】

答案：

25、【填空題】數(shù)據(jù)的四種基本存儲(chǔ)方法是順序存儲(chǔ)、鏈接存儲(chǔ)、____和散列存儲(chǔ)。

答案：索引存儲(chǔ)

26、【填空題】指針p和指針q分別指向單鏈表L中的兩個(gè)結(jié)點(diǎn),next為指針域,則判斷這兩

個(gè)結(jié)點(diǎn)是否相鄰的條件是____

答案：p->next==q||q->next==p

27、【填空題】遞歸求解過(guò)程中的最小子問(wèn)題稱(chēng)為_(kāi)___

答案：遞歸的終止條件(或遞歸出口)

28、【填空題】廣義表(((a,b),(c,d,e)),(f,g),h)的表頭是____

答案：((a,b),(c,d,e))

29、【填空題】3個(gè)結(jié)點(diǎn)的不同形狀的二叉樹(shù)有____棵。

答案：5

30、【填空題】若有向無(wú)環(huán)圖G存在2個(gè)入度為0的結(jié)點(diǎn),則G至少存在____個(gè)不同的拓?fù)?/p>

序列。

答案：2

31、【填空題】將一棵樹(shù)T轉(zhuǎn)換為一棵二叉樹(shù),則這棵二