全國2022年4月自考02331《數(shù)據(jù)結(jié)構(gòu)》真題

精品文檔-下載后可編輯全國2022年4月自考02331《數(shù)據(jù)結(jié)構(gòu)》真題全國2022年4月自考02331《數(shù)據(jù)結(jié)構(gòu)》真題

1.（單選題,2分）設(shè)散列表長m=14，散列函數(shù)H（key）=key%13。采用線性探測法處理沖突。表中己按散列地址保存了3個關(guān)鍵字16，30，18，此時存儲關(guān)鍵字29的探查次數(shù)是（）

A、1

B、2

C、3

D、4

2.（單選題,2分）在一棵二叉排序樹中，關(guān)鍵字n所在結(jié)點(diǎn)是關(guān)鍵字m所在結(jié)點(diǎn)的孩子結(jié)點(diǎn)，則（）

A、n一定大于m

B、n一定小于m

C、n一定等于m

D、n與m的大小關(guān)系不確定

3.（單選題,2分）關(guān)鍵碼序列為30，77，57，12，25，86，建立的初始大根堆是（）

A、77，30，57，12，25，86

B、86，77，57，12，25，30

C、86，77，57，30，25，12

D、86，57，77，25，30，12

4.（單選題,2分）下列選項中，穩(wěn)定的排序方法是（）

A、直接插入排序

B、直接選擇排序

C、希爾排序

D、堆排序

5.（單選題,2分）對數(shù)據(jù)序列（15，12，13，12，8，4，5）采用冒泡排序進(jìn)行升序排序，兩趟排序后得到的排序結(jié)果是（）

A、12，13，12，8，4，5，15

B、12，12，8，4，5，13，15

C、5，4，8，12，12，13，15

D、4，5，8，12，12，13，15

6.（單選題,2分）設(shè)有向圖G含有n個頂點(diǎn)、e條邊，使用鄰接矩陣存儲。對G求拓?fù)湫蛄兴惴ǖ臅r間復(fù)雜度是（）

A、

B、

C、

D、

7.（單選題,2分）無向圖中所有頂點(diǎn)的度數(shù)之和是10，則頂點(diǎn)的最大度數(shù)是（）

A、5

B、6

C、7

D、10

8.（單選題,2分）采用鄰接矩陣存儲含n個頂點(diǎn)和e條邊的有向圖G，鄰接矩陣中0的個數(shù)是（）

A、

B、

C、

D、

9.（單選題,2分）已知二叉樹T的前序遍歷序列為a，b，c，d，e，則前序遍歷序列與T相同的不同二叉樹個數(shù)（不包含T）是（）

A、11

B、12

C、13

D、14

10.（單選題,2分）已知一棵高度為4的完全二叉樹T的第4層上共有3個葉子結(jié)點(diǎn)，則T中葉子結(jié)點(diǎn)的個數(shù)是（）

A、4

B、5

C、6

D、7

11.（單選題,2分）（）

A、2

B、3

C、4

D、5

12.（單選題,2分）設(shè)指針變量p指向非空單鏈表中的結(jié)點(diǎn)，next是結(jié)點(diǎn)的指針域，現(xiàn)要刪除p所指結(jié)點(diǎn)的所有后繼結(jié)點(diǎn)，則下列語句中正確的是（）

A、

B、

C、

D、

13.（單選題,2分）設(shè)棧的初始狀態(tài)為空，元素1，3，5，2，4依次入棧，不能得到的出棧序列是（）

A、5，1，3，2，4

B、4，2，5，3，1

C、2，4，5，3，1

D、1，3，5，2，4

14.（單選題,2分）將20個數(shù)據(jù)元素的線性表存儲在數(shù)組中，若第9個元素的存儲地址是1000，第11個元素的存儲地址是1040，則最后一個元素的存儲地址是（）

A、1200

B、1210

C、1215

D、1220

15.（單選題,2分）下列數(shù)據(jù)結(jié)構(gòu)中，與存儲結(jié)構(gòu)相關(guān)的是（）

A、線性表

B、棧

C、鏈隊列

D、二叉樹

16.（填空題,2分）

假設(shè)順序存儲的有序表R含有13個關(guān)鍵字，進(jìn)行二分查找時，查找成功時平均查找長度為[]。

17.（填空題,2分）散列表的平均查找長度不是結(jié)點(diǎn)個數(shù)n的函數(shù)，而是[]的函數(shù)。

18.（填空題,2分）

（對含n個元素的數(shù)據(jù)序列采用二路歸并排序算法進(jìn)行排序，算法的時間復(fù)雜度是）（[]）（。）

（（）（答案：）（））

19.（填空題,2分）將森林T轉(zhuǎn)換為一棵二叉樹T1，則T中葉子結(jié)點(diǎn)在T1中滿足的條件為[]。

20.（填空題,2分）如果有向無環(huán)圖G中至少有兩個頂點(diǎn)的入度為0，則G中至少有[]個不同的拓?fù)湫蛄小?/p>

21.（填空題,2分）已知完全二叉樹的按層遍歷序列存儲在一維數(shù)組A[0..n-1]中，則A[i]（1≤i≤n-1）的父結(jié)點(diǎn)是[]。

22.（填空題,2分）廣義表（（a，b），（c，d），（（e，f），（g，h）））的表尾是[]。

23.（填空題,2分）

實(shí)現(xiàn)遞歸函數(shù)調(diào)用和返回的數(shù)據(jù)結(jié)構(gòu)是[]。

24.（填空題,2分）若指針p和q分別指向單鏈表L中的兩個相鄰結(jié)點(diǎn)，且q指向的是終端結(jié)點(diǎn)。則在p所指結(jié)點(diǎn)之后插入指針r所指結(jié)點(diǎn)的語句是r-next=q；[]；。

25.（填空題,2分）鏈棧、順序隊列的存儲結(jié)構(gòu)不同，數(shù)據(jù)的運(yùn)算也不同，它們的[]結(jié)構(gòu)相同。

26.（解答題,5分）

27.（解答題,5分）

有數(shù)據(jù)序列（15，16，04，12，21，23，43，31，16，13），使用希爾排序方法將其排成升序序列。

請回答下列問題：

（1）分別寫出增量序列的取值依次為4，1的希爾排序結(jié)果。

（2）計算增量為4時希爾排序中數(shù)據(jù)元素之間的總交換次數(shù)（兩個元素之間的交換記1次）。

28.（解答題,5分）