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

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

0214220224

1、【單選題】算法時間復(fù)雜度指的是

一個算法需要的存儲量

一個程序的確切執(zhí)行時間

A:

算法在給定輸入下的計(jì)算量

B:

算法在給定時間下的計(jì)算量

C:

答D:案：C

2、【單選題】雙向循環(huán)鏈表結(jié)點(diǎn)結(jié)構(gòu)為

data、next、node

prior、data、next

A:

rear、data、next

B:

prior、data、rear

C:

答D:案：B

3、【單選題】設(shè)順序表有9個元素.則在第3個元素前插入一個元素所需移動元素的個數(shù)為

5

6

A:

7

B:

9

C:

答D:案：C

4、【單選題】隊(duì)列可以實(shí)現(xiàn)

函數(shù)的嵌套調(diào)用和操作系統(tǒng)中進(jìn)程調(diào)度

函數(shù)的嵌套調(diào)用和程序遞歸的處理

A:

程序遞歸的處理和操作系統(tǒng)中進(jìn)程調(diào)度

B:

操作系統(tǒng)中進(jìn)程調(diào)度和網(wǎng)絡(luò)管理中的打印服務(wù)

C:

答D:案：D

解析：函數(shù)的嵌套調(diào)用和程序遞歸的處理都是使用棧來實(shí)現(xiàn)的,操作系統(tǒng)中進(jìn)程調(diào)度、網(wǎng)

絡(luò)管理中的打印服務(wù)等都是用隊(duì)列來實(shí)現(xiàn)的。

5、【單選題】在單鏈表中，釋放已移出結(jié)點(diǎn)p的空間使用語句

malloc(p)

sizeof(p)

A:

free(p)

B:

p=NULL

C:

答D:案：C

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

CQ.rear==CQ.front

CQ.rear=CQ.front

A:

CQ.rear+1==CQ.front-1

B:

CQ.Rear+1=CQ.front

C:

答D:案：A

7、【單選題】元素的進(jìn)棧次序?yàn)锳.B.C,D.E.則出棧中不可能的序列是

A，B，C，D，E

B，C，D，E，A

A:

E，A，B，C，D

B:

E，D，C，B，A

C:

答D:案：C

8、【單選題】滿二叉樹需滿足條件

深度為k(k≥0)

有2K+1個結(jié)點(diǎn)

A:

深度為k(k≥0)且有2K個結(jié)點(diǎn)

B:

深度為k(k≥1)且有2K-1個結(jié)點(diǎn)

C:

答D:案：D

9、【單選題】若二叉樹采用二叉鏈表作為存儲結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左右子樹的位

置，最合適的遍歷方法是

先序遍歷

中序遍歷

A:

后序遍歷

B:

層次遍歷

C:

答D:案：C

10、【單選題】把特殊矩陣A[10][10]的下三角矩陣壓縮存儲到一個一維數(shù)組M中，則A中

元素a[4][3]在M中所對應(yīng)的下標(biāo)位置是

8

12

A:

13

B:

55

C:

答D:案：C

11、【單選題】任何一個帶權(quán)的無向連通圖的最小生成樹

只有一棵

一定有多棵

A:

有一棵或多棵

B:

可能不存在

C:

答D:案：C

12、【單選題】有關(guān)解決沖突的方法中，描述正確的是

多重散列法不易產(chǎn)生“堆積”

線性探測法生成后繼散列地址計(jì)算復(fù)雜

A:

二次探測法生成的后繼散列地址是連續(xù)的

B:

二次探測法容易探測到整個散列表的所有空間

C:

答D:案：A

13、【單選題】依次輸入鍵值序列50,72,43,85,75,20,35,45,65,30，建立對應(yīng)的二叉排序

樹以后，查找元素35要進(jìn)行元素間的比較次數(shù)為

4

5

A:

7

B:

10

C:

答D:案：A

14、【單選題】在散列函數(shù)H(k)=kMODm中，一般來講,m應(yīng)取

奇數(shù)

偶數(shù)

A:

素?cái)?shù)

B:

合數(shù)

C:

答D:案：C

15、【單選題】下列序列中，符合堆定義的是

(100,80,55,60,50,40,58,35,20)

(100,80,55,60,50,40,35,58,20)

A:

(100,80,55,58,50,40,60,35,20)

B:

(100,70,55,60,50,40,58,35,20)

C:

答D:案：B

16、【問答題】二叉樹的五種基本形態(tài)如題29圖所示。(1)子樹用什么形狀表示?(2)分別

寫出題29-1圖、題29-2圖和題29-5圖的形態(tài)。

答案：(1)方塊。(2)空二叉樹；左右子樹均為空的二叉樹；左、右子樹都非空的二叉

樹。

17、【問答題】給定無向圖如題30圖所示。(1)計(jì)算D(v1)和D(v2)(2)寫出以頂點(diǎn)

v0為起點(diǎn)到v3的所有簡單路徑。

答案：(1)D(v1)=2,D(v2)=3。(2)v0→v1→v2→v3,v0→v2→v3。

18、【問答題】給定一組鍵值{45,38,66,90,88,10,25,_45_}，假設(shè)在排序過程中，前4個

記錄已按鍵值遞增順序重新排列，構(gòu)成了一個有序序列為(38,45,66,90}。(1)請寫出應(yīng)用

直接插入排序方法對剩余鍵值排序的排序過程。(2)直接插入排序方法是否穩(wěn)定？

答案：(1)[3845668890]1025_45_[103845668890]25_45_[10253845

668890]_45_[10253845_45_668890](2)穩(wěn)定

19、【問答題】設(shè)有m個頂點(diǎn)的無向圖G,采用鄰接矩陣作存儲結(jié)構(gòu)，在鄰接矩陣上判斷下列

有關(guān)問題，給出簡單的算法描述。(1)圖中有多少條邊？(2)任意兩個頂點(diǎn)i和j是否有

邊相連？(3)任意一個頂點(diǎn)的度是多少？

答案：(1)圖中邊數(shù)等于矩陣中值為1的元素個數(shù)除以2。(2)矩陣中第i行和第j列的

元素是否為1。(3)任意一個頂點(diǎn)的度是該頂點(diǎn)所在行（或列）的元素值之和。

20、【問答題】已知散列函數(shù)為H(key)=keymod7，構(gòu)造散列表如題33表，并用線性探測

法解決沖突。若要用該散列表查找元素25,32,68，請分別給出所需的比較次數(shù)。

答案：H(25)=25%7=4,比較1次；H(32)=32%7=4與25沖突，探測5，成功。比較2次；

H(68)=68%7=5與32沖突，探測地址6，與48沖突，探測地址0，成功。比較次數(shù)3次。

21、【問答題】寫出實(shí)現(xiàn)對一個n×n階矩陣進(jìn)行轉(zhuǎn)置的算法。

答案：

22、【問答題】已知二叉鏈表的類型定義如下：

假定visit(bt)是一個已定

義的過程，其功能是訪問指針bt所指結(jié)點(diǎn)。設(shè)計(jì)在二叉鏈表上的先序遍歷算法和中序遍

歷算法。

答案：

23、【填空題】數(shù)據(jù)及數(shù)據(jù)的組織方式稱為數(shù)據(jù)的______。

答案：邏輯結(jié)構(gòu)

24、【填空題】設(shè)r指向單鏈表的最后一個結(jié)點(diǎn)，要在最后一個結(jié)點(diǎn)之后插人s所指的結(jié)

點(diǎn)，需執(zhí)行的語句序列是______；r=s;r->next=NULL。

答案：r->next=s

25、【填空題】棧初始化時，生成一個結(jié)點(diǎn)，將該結(jié)點(diǎn)的next域設(shè)置為______。

答案：NULL

26、【填空題】鏈隊(duì)列中，單鏈表的頭結(jié)點(diǎn)的next域指向隊(duì)列______結(jié)點(diǎn)。

答案：首

27、【填空題】數(shù)組采用______存儲結(jié)構(gòu)來存儲數(shù)據(jù)元素。

答案：順序

28、【填空題】一棵樹中所有結(jié)點(diǎn)的度的______稱為該樹的度。

答案：最大值

29、【填空題】由先序序列的第一個結(jié)點(diǎn)可以確定這棵樹的______結(jié)點(diǎn)。

答案：根

30、【填空題】一棵樹的最少結(jié)點(diǎn)個數(shù)為______。

答案：0

31、【填空題】任何兩點(diǎn)之間都有邊的無向圖稱為無向______圖。

答案：完全

32、【填空題】已知完全二叉樹的第7層有