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

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

02142202210

1、【單選題】下面幾種算法時間復(fù)雜度中，階數(shù)最小的是

O(log2n)

O(n)

A:

O(n2)

B:

O(2n)

C:

答D:案：A

2、【單選題】雙向循環(huán)鏈表（非空表）中，頭結(jié)點的prior指向

頭指針head

第一個結(jié)點

A:

任意一個結(jié)點

B:

最后一個結(jié)點

C:

答D:案：D

3、【單選題】下列關(guān)于線性表的順序?qū)崿F(xiàn)和鏈接實現(xiàn)特點的描述，_錯誤_的是

順序表不需要預(yù)先分配存儲空間

單鏈表的指針域需要占用額外空間

A:

對于定位運算，順序表和單鏈表上的實現(xiàn)算法的時間復(fù)雜度相同

B:

對于插入、刪除運算，在順序表和鏈表中，都需要進行定位

C:

答D:案：A

4、【單選題】線性表采用鏈表存儲結(jié)構(gòu)時，內(nèi)存中可用存儲單元的地址

必須是連續(xù)的

部分必須是連續(xù)的

A:

一定是不連續(xù)的

B:

連續(xù)不連續(xù)都可以

C:

答D:案：D

5、【單選題】循環(huán)隊列滿條件為

CQ.rear==CQ.front

CQ.rear=CQ.front

A:

(CQ.rear+1)%maxsize==CQ.front

B:

C:

(CQ.rear-1)%maxsize=CQ.front

答D:案：C

6、【單選題】一個數(shù)組的第一個元素的存儲地址是100，每個元素占2存儲單元.則第5個

元素的存儲地址是

100

108

A:

110

B:

120

C:

答D:案：B

7、【單選題】二叉樹的基本形態(tài)有

3種

4種

A:

5種

B:

6種

C:

答D:案：C

8、【單選題】在有n個葉子結(jié)點的哈夫曼樹中，其結(jié)點總數(shù)為

2n

n-1

A:

2n-1

B:

2n+1

C:

答D:案：C

9、【單選題】若一棵非空二叉樹的先序序列與后序序列相同，則該二叉樹可能的形狀是

樹中沒有度為2的結(jié)點

樹中只有一個根結(jié)點

A:

樹中非葉結(jié)點均只有左子樹

B:

樹中非葉結(jié)點均只有右子樹

C:

答D:案：B

10、【單選題】一個具有n個頂點的有向完全圖的弧數(shù)為

n(n-1)/2

n(n-1)

A:

n2/2

B:

C:

n2

答D:案：B

11、【單選題】設(shè)圖G中有n個頂點，e條弧，采用鄰接表存儲，則拓撲排序算法的時間復(fù)

雜度為

O(n)

O(n+e)

A:

O(n2)

B:

O(n×e)

C:

答D:案：B

12、【單選題】在長度為n的帶有崗哨的順序表中，進行順序查找，查找不成功時，與關(guān)鍵

字的比較次數(shù)為

1

n-1

A:

n

B:

n+1

C:

答D:案：D

13、【單選題】查找表的邏輯結(jié)構(gòu)是

集合

鏈表

A:

樹形結(jié)構(gòu)

B:

圖狀結(jié)構(gòu)

C:

答D:案：A

14、【單選題】用線性探測法解決沖突，可能要探測多個散列地址，這些位置上的鍵值

一定是同義詞

一定都不是同義詞

A:

都相同

B:

不一定都是同義詞

C:

答D:案：D

15、【單選題】快速排序最壞時間復(fù)雜度為

O(n2)

O(nlog2n)

A:

B:

O(log2n)

O(n)

C:

答D:案：A

16、【問答題】題29-1圖和題29-2圖為兩種形態(tài)的二叉樹。(1)題29-1圖、題29-2

圖各屬于何種類型的二叉樹？(2)二叉樹通常有哪兩類存儲結(jié)構(gòu)？

答案：(1)題29-1圖為滿二叉樹；題29-2圖為完全二叉樹。(2)順序存儲結(jié)構(gòu)和鏈式存

儲結(jié)構(gòu)。

17、【問答題】無向圖如題30圖所示。(1)列出所有簡單回路。(2)寫出鄰接矩陣。

答案：

18、【問答題】設(shè)待排序的鍵值為45386690881025_45_。利用冒泡排序算法進行排

序，已知第一趟排序后的鍵值為384566881025_45_90，請寫出后續(xù)每趟排序的結(jié)果。

答案：第二趟排序后3845661025_45_8890第三趟排序后38451025_45_66

8890第四趟排序后38102545_45_668890第五趟排序后10253845_45_66

8890第六趟排序后10253845_45_668890第七趟排序后10253845_45_66

8890

19、【問答題】設(shè)序列{dcbaheifg}和{abchdiefg}分別是一棵二叉樹的先序序列和中序序

列，請畫出該二叉樹。

答案：

20、【問答題】給定表(Jan,Feb,Mar,Apr,May,Jul)。散列表的地址空間為0~10.設(shè)散列函數(shù)

H(x)=[i/2],其中i為鍵值中第一個字母在英語字母表中的序號，要求畫出以線性探測法解決

沖突的散列表。

答案：

21、【問答題】設(shè)計算法在整型數(shù)組A[n]中查找值為k的元素，若找到，則輸出其位置

i(0≤i≤n-1),否則輸出一1作為標志。

答案：

22、【問答題】設(shè)計算法按先序次序打印二叉樹T中葉子結(jié)點的值。

答案：

23、【填空題】在順序表上做插入運算平均要移動表中______的結(jié)點。

答案：一半

24、【填空題】在單鏈表中，指針p所指的結(jié)點為最后一個結(jié)點的條件是______。

答案：p->next==NULL

25、【填空題】在估算算法空間復(fù)雜度時，一般只需要分析______所占用的空間。

答案：輔助變量

26、【填空題】若一維數(shù)組中的數(shù)據(jù)元素又是一維數(shù)組結(jié)構(gòu)，則該數(shù)組稱為______。

答案：二維數(shù)組

27、【填空題】線性表中如果結(jié)點數(shù)不為零，則除起始結(jié)點沒有直接前驅(qū)外，其他每個結(jié)點

有且僅有______個直接前驅(qū)。

答案：1

28、【填空題】在樹中，從根開始算起，根的層次為______。

答案：1

29、【填空題】一棵判定樹描述了一種______方法。

答案：分類

30、【填空題】設(shè)森林F中有三棵樹，第一、第二、第三棵樹的結(jié)點個數(shù)分別為M1、M2和

M3。與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是______。

答案：M2+M3

31、【填空題】設(shè)棧的輸入序列為12.3，若輸出的第一個元素為3，則第二個輸出的元素為

______。

答案：2

32、【填空題】無向圖的鄰接