?2022年10月自考02331數(shù)據(jù)結(jié)構(gòu)真題試卷

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

2022年10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題

課程代碼:02331

1.請考生按規(guī)定用筆將所有試題的答案涂、寫在答題紙上。

2.答題前,考生務(wù)必將自己的考試課程名稱、姓名、準(zhǔn)考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規(guī)定的位置上。

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

1.下列選項中，采用了鏈?zhǔn)椒绞酱鎯Φ氖?/p>

A.順序棧

B.三元組

C.二叉鏈表

D.鄰接矩陣

2.線性表采用順序存儲時的優(yōu)點是

A.插入運(yùn)算方便

B.刪除運(yùn)算方便

C.存儲空間不必連續(xù)

D.可隨機(jī)訪問各元素

3.帶頭結(jié)點的單鏈表L的頭指針是head,結(jié)點結(jié)構(gòu)為: ， 若要求當(dāng)L不為空時判定條件為“真”，則正確的表達(dá)式是

A. head->next != NULL

B. head->next = NULL

C. head != head

D. head = NULL

4. n階方陣A是對稱矩陣，現(xiàn)要使用一維數(shù)組B按行優(yōu)先存儲A的上三角部分，B 的元素個數(shù)至少是

A. nx(n+1)/2

B. nx(n-1)/2

C. nxn/2

D. n

5.已知廣義表, LS 的深度是

A.5

B.4

C.3

D.2

6.具有20個結(jié)點的二叉樹T采用順序存儲方式保存在數(shù)組B中。若B[7]中保存了τ中的結(jié)點v，則保存v的父結(jié)點的是

A. B[0]

B. B[2]

C. B[3]

D. B[4]

7.在一棵非空二叉樹的中序遍歷序列中，位于根結(jié)點后面的是

A.左子樹中的部分結(jié)點

B.右子樹中的部分結(jié)點

C.左子樹中的全部結(jié)點

D.右子樹中的全部結(jié)點

8.下列關(guān)于二叉樹與森林相互轉(zhuǎn)換的敘述中，正確的是

A.將二叉樹轉(zhuǎn)換為森林時，得到的森林不是唯一的

B.將二叉樹轉(zhuǎn)換為森林時，得到的森林一定是唯一的

C.將森林轉(zhuǎn)換為二叉樹時，得到的二叉樹不是唯一的

D.將森林轉(zhuǎn)換為二叉樹時，得到的二叉樹可能不是唯一的

9.有向圖G中，頂點v的出度和入度均為2，則G中的弧數(shù)最少是

A.5

B.4

C.3

D.2

10.對下圖進(jìn)行拓?fù)渑判颍玫降耐負(fù)湫蛄锌赡苁?/p>

A.3,1,2,4,5,6

B.3, 1,2,4,6,5

C.3, 1,4,2,5, 6

D. 3, 1,4,2, 6, 5

11.若初始關(guān)鍵字序列為15, 10, 12, 5, 48, 30,按升序進(jìn)行直接插入排序，則三趟排序后,得到的排序結(jié)果為

A.5, 10,12, 15, 48, 30

B.5, 10, 12, 15, 30, 48

C.10, 15, 12, 5, 48, 30

D.10, 12, 15, 5, 48, 30

12.下列排序方法中，排序過程中使用的輔助空間不是0(1)的是

A.直接插入排序

B.冒泡排序

C.希爾排序

D.基數(shù)排序

13.下列關(guān)于二叉排序樹 T的操作的敘述中，正確的是

A.在T中刪除一個關(guān)鍵字時，樹的高度一定減1

B.在T中刪除一個關(guān)鍵字時，樹的高度不變化

C.在T中插入新關(guān)鍵字時，樹的高度一定加1

D.在T中查找某關(guān)鍵字時，樹的高度不變化

14.設(shè)散列表長m=7,散列函數(shù)H(key)= key %7,采用線性探查法處理沖突。表中已保存3個關(guān)鍵字: H(21)=0, H(8)= 1, H(25)=4,其余地址均為開放地址。現(xiàn)要插入關(guān)鍵字14，其在散列表中的下標(biāo)地址是

A.0

B. 1

C.2

D.3

15.對數(shù)據(jù)序列進(jìn)行順序查找時，必須滿足的條件是

A.數(shù)據(jù)必須保存在數(shù)組中

B.數(shù)據(jù)必須保存在鏈表中

C.數(shù)據(jù)必須是按升序排列的

D.數(shù)據(jù)必須能進(jìn)行比較操作

二、填空題:本大題共10小題，每小題2分，共20分。

16.數(shù)據(jù)的運(yùn)算是定義在數(shù)據(jù)的________結(jié)構(gòu)上的。

17.在非空的線性表中，沒有前趨的元素稱為_________。

18.使用數(shù)組保存的棧是_________。

19. 設(shè)廣義表L((a, b),(c,d, e)), ((f),g),h)， 則head( head(L)) 的結(jié)果是_________。

20.非空二叉樹T的前(先)序遍歷序列中，第一個元素是__________。

21.圖G的遍歷過程實際上是對每個頂點搜索其_________的過程。

22.若有向圖G存在拓?fù)湫蛄?，則序列中第一個頂點的入度值為_________。

23.快速排序中要將數(shù)據(jù)序列進(jìn)行劃分，為此，要選擇一個元素作為________。

24.利用堆排序?qū)?shù)據(jù)序列進(jìn)行升序排序，首先要將初始序列建立為_________。

25.在散列方法中，實現(xiàn)關(guān)鍵字到存儲地址映射的是_________。

三、解答題:本大題共4小題，每小題5分，共20分。

26.設(shè)二叉樹T的前序遍歷序列是ABDEHCFGI,中序遍歷序列是DBHEAFCIG,請畫出樹T。

27.求題27圖所示連通網(wǎng)的最小生成樹，并計算最小生成樹的權(quán)。

28.有以下關(guān)鍵字序列(25, 30, 14, 2, 21, 36, 51,3),使用二路歸并排序進(jìn)行升序排序，給出歸并過程。

29.設(shè)有一組關(guān)鍵字(2, 13, 18, 25, 30, 33, 36, 55),請畫出描述二分查找過程的二叉樹。

四、算法閱讀題:本大題共4小題，每小題5分，共20分。

30.鏈表類型定義如下: