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

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

02142202210

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

O(log2n)

O(n)

A:

O(n2)

B:

O(2n)

C:

答D:案：A

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

頭指針head

第一個(gè)結(jié)點(diǎn)

A:

任意一個(gè)結(jié)點(diǎn)

B:

最后一個(gè)結(jié)點(diǎn)

C:

答D:案：D

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

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

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

A:

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

B:

對(duì)于插入、刪除運(yùn)算，在順序表和鏈表中，都需要進(jìn)行定位

C:

答D:案：A

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

必須是連續(xù)的

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

A:

一定是不連續(xù)的

B:

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

C:

答D:案：D

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

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、【單選題】一個(gè)數(shù)組的第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素占2存儲(chǔ)單元.則第5個(gè)

元素的存儲(chǔ)地址是

100

108

A:

110

B:

120

C:

答D:案：B

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

3種

4種

A:

5種

B:

6種

C:

答D:案：C

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

2n

n-1

A:

2n-1

B:

2n+1

C:

答D:案：C

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

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

樹中只有一個(gè)根結(jié)點(diǎn)

A:

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

B:

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

C:

答D:案：B

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

n(n-1)/2

n(n-1)

A:

n2/2

B:

C:

n2

答D:案：B

11、【單選題】設(shè)圖G中有n個(gè)頂點(diǎn)，e條弧，采用鄰接表存儲(chǔ)，則拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)

雜度為

O(n)

O(n+e)

A:

O(n2)

B:

O(n×e)

C:

答D:案：B

12、【單選題】在長(zhǎng)度為n的帶有崗哨的順序表中，進(jìn)行順序查找，查找不成功時(shí)，與關(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、【單選題】用線性探測(cè)法解決沖突，可能要探測(cè)多個(gè)散列地址，這些位置上的鍵值

一定是同義詞

一定都不是同義詞

A:

都相同

B:

不一定都是同義詞

C:

答D:案：D

15、【單選題】快速排序最壞時(shí)間復(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)二叉樹通常有哪兩類存儲(chǔ)結(jié)構(gòu)？

答案：(1)題29-1圖為滿二叉樹；題29-2圖為完全二叉樹。(2)順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱?/p>

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

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

答案：

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

序，已知第一趟排序后的鍵值為384566881025_45_90，請(qǐng)寫出后續(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}分別是一棵二叉樹的先序序列和中序序

列，請(qǐng)畫出該二叉樹。

答案：

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

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

沖突的散列表。

答案：

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

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

答案：

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

答案：

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

答案：一半

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

答案：p->next==NULL

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

答案：輔助變量

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

答案：二維數(shù)組

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

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

答案：1

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

答案：1

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

答案：分類

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

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

答案：M2+M3

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

______。

答案：2

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