?2022年10月自考02331數據結構真題試卷

下文是希賽自考頻道整理的2022年10月自考02331數據結構真題試卷，想要查看更多自考真題，可以查閱【自考歷年真題】【2022年自考真題匯總】【自考題庫app下載】。

2022年10月高等教育自學考試數據結構試題

課程代碼:02331

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

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

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

1.下列選項中，采用了鏈式方式存儲的是

A.順序棧

B.三元組

C.二叉鏈表

D.鄰接矩陣

2.線性表采用順序存儲時的優點是

A.插入運算方便

B.刪除運算方便

C.存儲空間不必連續

D.可隨機訪問各元素

3.帶頭結點的單鏈表L的頭指針是head,結點結構為: ， 若要求當L不為空時判定條件為“真”，則正確的表達式是

A. head->next != NULL

B. head->next = NULL

C. head != head

D. head = NULL

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

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個結點的二叉樹T采用順序存儲方式保存在數組B中。若B[7]中保存了τ中的結點v，則保存v的父結點的是

A. B[0]

B. B[2]

C. B[3]

D. B[4]

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

A.左子樹中的部分結點

B.右子樹中的部分結點

C.左子樹中的全部結點

D.右子樹中的全部結點

8.下列關于二叉樹與森林相互轉換的敘述中，正確的是

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

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

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

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

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

A.5

B.4

C.3

D.2

10.對下圖進行拓撲排序，得到的拓撲序列可能是

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.若初始關鍵字序列為15, 10, 12, 5, 48, 30,按升序進行直接插入排序，則三趟排序后,得到的排序結果為

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.基數排序

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

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

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

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

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

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

A.0

B. 1

C.2

D.3

15.對數據序列進行順序查找時，必須滿足的條件是

A.數據必須保存在數組中

B.數據必須保存在鏈表中

C.數據必須是按升序排列的

D.數據必須能進行比較操作

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

16.數據的運算是定義在數據的________結構上的。

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

18.使用數組保存的棧是_________。

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

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

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

22.若有向圖G存在拓撲序列，則序列中第一個頂點的入度值為_________。

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

24.利用堆排序對數據序列進行升序排序，首先要將初始序列建立為_________。

25.在散列方法中，實現關鍵字到存儲地址映射的是_________。

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

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

27.求題27圖所示連通網的最小生成樹，并計算最小生成樹的權。

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

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

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

30.鏈表類型定義如下: