下文是希賽自考頻道整理的2022年4月自考02142數(shù)據(jù)結(jié)構(gòu)導(dǎo)論真題試卷，想要查看更多自考真題，可以查閱【自考?xì)v年真題】【2022年自考真題匯總】【自考題庫app下載】。

2022年4月高等教育自學(xué)考試全國統(tǒng)一命題考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題

(課程代碼：02142)

注意事項(xiàng):

1.本試卷分為兩部分,第一部分為選擇題,第二部分為非選擇題。

2.應(yīng)考者必須按試題順序在答題卡(紙)指定位置上作答，答在試卷上無效。

3.涂寫部分、畫圖部分必須使用2B鉛筆,書寫部分必須使用黑色字跡簽字筆。

一、 單項(xiàng)選擇題:本大題共15小題，每小題2分,共30分。在每小題列出的備選項(xiàng)中只有一項(xiàng)是最符合題目要求的，請將其選出。

1.算法時間復(fù)雜度指的是

A.一個算法需要的存儲量

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

C.算法在給定輸人下的計(jì)算量

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

2.雙向循環(huán)鏈表結(jié)點(diǎn)結(jié)構(gòu)為

A. data .next、node.

B. prior idata ,next

C. rear、data、next.

D. prior、data、rear

3.設(shè)順序表有9個元素,則在第3個元素前插人一個元索所需移動元素的個數(shù)為

A.5

B.6

C.7

D.9

4.隊(duì)列可以實(shí)現(xiàn)

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

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

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

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

5.在單鏈表中,釋放已移出結(jié)點(diǎn)p的空間使用語句

A. malloc(p)

B. sizeof(p)

C. free(p)

D. p= NULL

6.循環(huán)隊(duì)列空條件為

A. CQ. tear= = CQ. front

B. CQ. rear= CQ. front

C. CQ. rear+1== CQ. front+1

D. CQ. rear+1=CQ. front

7.元索的進(jìn)棧次序?yàn)锳,B,C.D,E,則出棧中不可能的序列是

A. A,B,C,D,E

B. B,C,D,E,A

C. E,A,B,C,D

D. E,D,C,B,A

8.滿二叉樹需滿足條件

A.深度為k(k≥0)

B.有+1個結(jié)點(diǎn)

C.深度為k(k≥0)且有個結(jié)點(diǎn)，

D.深度為k(k≥1)且有一1個結(jié)點(diǎn)

9.若二叉樹采用二叉鏈表作為存儲結(jié)構(gòu),要交換其所有分支結(jié)點(diǎn)左右子樹的位置，最合適的

遍歷方法是

A.先序遍歷

B.中序遍歷

C.后序遍歷

D.層次遍歷

10.把特殊矩陣A[10][10]的下三角矩陣壓縮存儲到一個一維數(shù)組M中,則A中元素a[4][3]在M中所對應(yīng)的下標(biāo)位置是

A.8

B.12

C.13

D.55

11.任何一個帶權(quán)的無向連通圖的最小生成樹

A.只有一棵

B.一定有多棵

C.有一棵或多棵

D.可能不存在

12.有關(guān)解決沖突的方法中，描述正確的是.

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

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

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

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

13,依次輸人鍵值序列50,72,43, 85.75.20,35,45,65,30,建立對應(yīng)的二叉排序樹以后查找元素35要進(jìn)行元素間的比較次數(shù)為

A.4

B.5

C.7

D.10

14.在散列函數(shù)H(k)=k MOD m中，一般來講,m應(yīng)取

A.奇數(shù)

B.偶數(shù)

C.素?cái)?shù)

D.合數(shù)

15. 下列序列中,符合堆定義的是

A. (100.80.55.60.50.40.58.35.20)

B. (100.80.55.60.50.40.35.58.20)

C. (100.80.55.58.50.40.60.35.20)

D. (100.70.55.60.50.40.58.35.20)

二、填空題:本大題共13空,每空2分,共26分。

16.數(shù)據(jù)及數(shù)據(jù)的組織方式稱為數(shù)據(jù)的_________。

17.設(shè)r指向單鏈表的最后一個結(jié)點(diǎn),要在最后一個結(jié)點(diǎn)之后插人s所指的結(jié)點(diǎn)，需執(zhí)行的語句序列是_________；r=s;r->next= NULL。

18.棧初始化時,生成一個結(jié)點(diǎn),將該結(jié)點(diǎn)的next域設(shè)置為_________。

19.鏈隊(duì)列中，單鏈表的頭結(jié)點(diǎn)的next域指向隊(duì)列_________結(jié)點(diǎn)。

20.數(shù)組采用_________存儲結(jié)構(gòu)來存儲數(shù)據(jù)元素。

21.-棵樹中所有結(jié)點(diǎn)的度的_________稱為該樹的度。

22.由先序序列的第一一個結(jié) 點(diǎn)可以確定這棵樹的_________結(jié)點(diǎn)。

23.一棵樹的最少結(jié)點(diǎn)個數(shù)為_________。

24.任何兩點(diǎn)之間都有邊的無向圖稱為無向_________圖。

25.已知完全二叉樹的第7層有20個結(jié)點(diǎn),則整個完全二叉樹的葉子結(jié)點(diǎn)數(shù)是_________。

26.任何一個無環(huán)有向圖,其全部頂點(diǎn)可以排成一個_________序列。

27.稀疏矩陣可以采用_________表示法進(jìn)行壓縮存儲。

28.相同鍵值的兩個記錄在排序前后相對位置的變化情況是排序算法研究中經(jīng)常關(guān)注的一個問題,這個問題稱為排序算法的_________。

三、應(yīng)用題:本大題共5小題,每小題6分,共30分。

29.二叉樹的五種基本形態(tài)如題29圖所示。(1)子樹用什么形狀表示? (2)分別寫出題29-1圖、題29-2圖和題29-5圖的形態(tài)。

30.給定無向圖如題30圖所示。

(1)計(jì)算D(V1 )和D(V2)。

(2)寫出以頂點(diǎn)Vo為起點(diǎn)到V3的所有簡單路徑。

31.給定一組鍵值{45,38,66 ,90 ,88,10,25.45}，假設(shè)在排序過程中,前4個記錄已按鍵值遞增

順序重新排列,構(gòu)成了一個有序序列為{38,45,66,90}.

(1)請寫出應(yīng)用直接插人排序方法對剩余鍵值排序的排序過程。

(2)直接插人排序方法是否穩(wěn)定?

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

給出簡單的算法描述。

(1)圖中有多少條邊?

(2)任意兩個頂點(diǎn)i和j是否有邊相連?

(3)任意一個頂點(diǎn)的度是多少?

33.已知散列西數(shù)為H(key)=keymod7,構(gòu)造散列表如題33表,并用線性探測法解決沖突。

若要用該散列表查找元索25,32,68,請分別給出所需的比較次數(shù)。

題33表

四、算法設(shè)計(jì)題:本大題共2小題,每小題7分,共14分。

34,寫出實(shí)現(xiàn)對一個nX n階矩陣進(jìn)行轉(zhuǎn)置的算法。

35.已知二叉鏈表的類型定義如下:

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