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

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

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

課程代碼:02331

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

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

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

1.下列選項(xiàng)中，采用了鏈?zhǔn)椒绞酱鎯?chǔ)的是

A.順序棧

B.三元組

C.二叉鏈表

D.鄰接矩陣

2.線性表采用順序存儲(chǔ)時(shí)的優(yōu)點(diǎn)是

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

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

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

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

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

A. head->next != NULL

B. head->next = NULL

C. head != head

D. head = NULL

4. n階方陣A是對(duì)稱矩陣，現(xiàn)要使用一維數(shù)組B按行優(yōu)先存儲(chǔ)A的上三角部分，B 的元素個(gè)數(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個(gè)結(jié)點(diǎn)的二叉樹(shù)T采用順序存儲(chǔ)方式保存在數(shù)組B中。若B[7]中保存了τ中的結(jié)點(diǎn)v，則保存v的父結(jié)點(diǎn)的是

A. B[0]

B. B[2]

C. B[3]

D. B[4]

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

A.左子樹(shù)中的部分結(jié)點(diǎn)

B.右子樹(shù)中的部分結(jié)點(diǎn)

C.左子樹(shù)中的全部結(jié)點(diǎn)

D.右子樹(shù)中的全部結(jié)點(diǎn)

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

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

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

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

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

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

A.5

B.4

C.3

D.2

10.對(duì)下圖進(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.下列排序方法中，排序過(guò)程中使用的輔助空間不是0(1)的是

A.直接插入排序

B.冒泡排序

C.希爾排序

D.基數(shù)排序

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

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

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

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

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

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

A.0

B. 1

C.2

D.3

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

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.在非空的線性表中，沒(méi)有前趨的元素稱為_(kāi)________。

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

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

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

21.圖G的遍歷過(guò)程實(shí)際上是對(duì)每個(gè)頂點(diǎn)搜索其_________的過(guò)程。

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

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

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

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

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

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

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

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

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

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

30.鏈表類型定義如下: