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

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

0233120214

1、【單選題】下列選項(xiàng)中，不屬于線性結(jié)構(gòu)的是

線性表

雙向鏈表

A:

循環(huán)隊(duì)列

B:

二叉樹

C:

答D:案：D

解析：二叉樹不屬于線性結(jié)構(gòu)。線性結(jié)構(gòu)是指數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系，即每個(gè)元

素只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。而二叉樹是一種非線性結(jié)構(gòu)，它的每個(gè)節(jié)點(diǎn)最多有

兩個(gè)子節(jié)點(diǎn)，分別稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。這種分支結(jié)構(gòu)使得二叉樹的數(shù)據(jù)元素之間存

在多對(duì)一的關(guān)系，因此二叉樹不屬于線性結(jié)構(gòu)。

2、【單選題】某線性表L含有n個(gè)元素，采用單循環(huán)鏈表保存，僅有尾指針指向鏈表的終端

結(jié)點(diǎn)。在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)及刪除第一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度分別是

O(1)和O(1)

O(1)和O(n)

A:

O(n)和O(1)

B:

O(n)和O(n)

C:

答D:案：A

3、【單選題】下列應(yīng)用中會(huì)用到棧的是

計(jì)算后綴表達(dá)式的值

圖的廣度優(yōu)先遍歷

A:

對(duì)數(shù)組進(jìn)行希爾排序

B:

對(duì)散列表進(jìn)行查找

C:

答D:案：A

4、【單選題】設(shè)棧初始為空，入棧序列為1，2，3，4，5，下列選項(xiàng)中，不可能得到的出棧

序列是

1，2，3，4，5

3，1，4，2，5

A:

4，3，2，5，1

B:

5，4，3，2，1

C:

D:

答案：B

5、【單選題】已知廣義表LS=(((c，(d))，(e，(f)))，(g，h)，(m，n)))，head(LS)是

c

(c)

A:

(c，(d))

B:

((c，(d))，(e，(f)))

C:

答D:案：D

6、【單選題】設(shè)線性表采用順序存儲(chǔ)方式保存，每個(gè)元素占8個(gè)存儲(chǔ)單元。第1個(gè)元素的存

儲(chǔ)地址為200，則第5個(gè)元素占用的最后一個(gè)存儲(chǔ)單元的地址是

239

240

A:

247

B:

248

C:

答D:案：A

7、【單選題】一棵完全二叉樹T的全部k個(gè)葉結(jié)點(diǎn)都在同一層中，每個(gè)分支結(jié)點(diǎn)都有兩個(gè)孩

子結(jié)點(diǎn)。T中包含的結(jié)點(diǎn)數(shù)是

k

2k-1

A:

k2

B:

2k-1

C:

答D:案：B

8、【單選題】設(shè)字符集中有n個(gè)字符，對(duì)其進(jìn)行哈夫曼編碼，得到的哈夫曼樹的結(jié)點(diǎn)總數(shù)是

2n-1

2n

A:

2n+1

B:

不確定

C:

答D:案：A

9、【單選題】設(shè)圖G的鄰接矩陣A如下所示。G的各頂點(diǎn)的度依次是

1，2，1，2

2，2，1，1

A:

3，4，2，3

B:

4，4，2，2

C:

答D:案：C

10、【單選題】對(duì)題10-11圖進(jìn)行深度優(yōu)先遍歷，下列選項(xiàng)中，正確的遍歷序列是

1，2，3，4，5

A:

2，3，5，4，1

3，5，1，2，4

B:

4，3，5，1，2

C:

答D:案：A

11、【單選題】對(duì)題10-11圖進(jìn)行拓?fù)渑判?，下列選項(xiàng)中，正確的拓?fù)湫蛄惺?/p>

1，2，3，4，5

2，3，1，4，5

A:

3，5，1，2，4

B:

5，3，1，2，4

C:

答D:案：D

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

直接插入排序

冒泡排序

A:

歸并排序

B:

快速排序

C:

答D:案：D

解析：快速排序不是穩(wěn)定的排序方法。穩(wěn)定排序是指如果兩個(gè)元素的值相等，排序后它們

的相對(duì)順序保持不變。而快速排序在每一次分割過(guò)程中，會(huì)選擇一個(gè)基準(zhǔn)元素，將小于基

準(zhǔn)元素的放在左邊，大于基準(zhǔn)元素的放在右邊，這個(gè)過(guò)程會(huì)改變相等元素的相對(duì)順序，因

此快速排序不是穩(wěn)定的排序方法。

13、【單選題】已知數(shù)據(jù)序列(18，19，20，4，51，6，30，1，2)是某種排序算法第二趟排

序后得到的結(jié)果，則該算法可能是

選擇排序

冒泡排序

A:

直接插入排序

B:

快速排序

C:

答D:案：C

14、【單選題】對(duì)有序表(1，3，9，12，32，41，45，62，75，77)進(jìn)行二分查找，查找關(guān)

鍵字9時(shí)，進(jìn)行比較的關(guān)鍵字依次是

1，3，9

32，3，9

A:

32，12，9

B:

C:

41，12，9

答D:案：B

15、【單選題】分別使用下列數(shù)據(jù)序列建立二叉排序樹，能得到高度最高的二叉樹的是

10，8，9，6，12，11，13

10，6，8，9，12，11，13

A:

10，12，11，13，8，6，9

B:

10，8，6，9，12，13，11

C:

答D:案：B

16、【問(wèn)答題】請(qǐng)畫出題26圖所示的二叉樹對(duì)應(yīng)的樹或森林。

答案：

17、【問(wèn)答題】求題27圖從頂點(diǎn)A到其余各頂點(diǎn)的最短路徑，給出各條路徑包含的頂點(diǎn)

序列及路徑長(zhǎng)度。

答案：

18、【問(wèn)答題】有以下數(shù)據(jù)序列(20，84，19，14，23，01，68，27，55，11，10，79，

12)，使用二路歸并排序算法將其排成升序序列。給出各趟排序結(jié)果。

答案：初始：20，84，19，14，23，01，68，27，55，11，10，79，12一趟歸并：

20，84，14，19，01，23，27，68，11，55，10，79，12二趟歸并：14，19，20，84，

01，23，27，68，10，11，55，79，12三趟歸并：01，14，19，20，23，27，68，84，

10，11，12，55，79四趟歸并：01，10，11，12，14，19，20，23，27，55，68，79，

84

19、【問(wèn)答題】設(shè)有以下關(guān)鍵字：15，72，52，65，23，68，散列函數(shù)H(key)=key%7，散列

表空間為0~6，采用線性探查法解決沖突。請(qǐng)回答下列問(wèn)題。(1)構(gòu)造散列表。(2)計(jì)算等

概率情況下查找成功時(shí)的平均查找長(zhǎng)度。

答案：

20、【問(wèn)答題】順序表類型定義如下。

答案：(1)30，2，10，9，5，3，(2)根據(jù)所給的數(shù)據(jù)建立順序表，將偶數(shù)從表頭插入，

奇數(shù)從表尾插入。

21、【問(wèn)答題】閱讀函數(shù)f31，并回答問(wèn)題。

答案：(1)-38，-256，256，9，25，47，128，4，64(2)找到數(shù)組中第一個(gè)非負(fù)數(shù)的位

置。

22、【問(wèn)答題】二叉排序樹的存儲(chǔ)結(jié)構(gòu)類型定義如下。

答案：(1)1618253650(2)查找二叉排序樹T中所有滿足大于等于K1且小于等于K2

的元素，并按升序輸出。

23、【問(wèn)答題】待排序記錄的數(shù)據(jù)類型定義如下。

答案：(1)j<=n(2)R[j].key＜R[k].key(3)k!=i

24、【問(wèn)答題】已知單鏈表的存儲(chǔ)結(jié)構(gòu)類型定義如下。

答案：

25、【填空題】數(shù)據(jù)的運(yùn)算，即對(duì)數(shù)據(jù)元素施加的操作，是定義在數(shù)據(jù)的_______結(jié)構(gòu)上

的。

答案：邏輯

26、【填空題】在順序表中，因?yàn)樵L問(wèn)任一結(jié)點(diǎn)的方式是_______，所以訪問(wèn)每個(gè)結(jié)點(diǎn)的時(shí)

間復(fù)雜度均為O(1)。

答案：隨機(jī)訪問(wèn)

27、【填空題】帶頭結(jié)點(diǎn)的鏈隊(duì)列可以由一個(gè)頭指針和一個(gè)尾指針唯一確定。當(dāng)頭指針和尾

指針相等時(shí)，表示隊(duì)列_______。

答案：為空

28、【填空題】稀疏矩陣采用壓縮存儲(chǔ)，只保存非零元素，得到的順序存儲(chǔ)結(jié)構(gòu)稱為

_______。

答案：三元組表

29、【填空題】廣義表((a)，(b，c)，(d，e，(f，g，h)))的表尾是_______。

答案：((b，c)，(d，e，(f，g，h)))

30、【填空題】中序線索化二叉樹的過(guò)程，是在中序遍歷過(guò)程中用線索取代_______。

答案：空指針

31、【填空題】在有n個(gè)頂點(diǎn)、e條邊的無(wú)向連通圖中，e的取值范圍是_______。

答案：n-1