?全國2020年10月自考數據結構02331真題

自考真題是考生復習備考的一大法寶，需要好好利用，而且年份離的越近，參考價值越高。以下是希賽網自考頻道整理的全國2020年10月自考數據結構02331真題，考生可參考試卷題型、分值、重點考試內容及答題規范，參考答案現在暫未公布，希賽網將持續更新。

全國2020年10月自考數據結構02331真題

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

1.數據結構研究的基本內容是

A.數據的邏輯結構、存儲結構和對數據元素施加的操作

B.數據的類型、數據的定義、算法描述和各種操作實現

C.數據的線性結構、樹型結構、圖型結構及相關的算法

D.數據元素之間的邏輯關系、物理存儲和相關程序實現

2.數據結構中，評價算法好壞的重要指標之一是

A.程序的執行時間

B.源程序的代碼長度

C.程序采用的語言

D.算法的時間復雜度

3.等概率情況下，在長度為n的順序表中插入1個元素需要移動元素的平均次數是

A.1

B. n/2

C. n

D. n+1

4.已知head 為指向帶頭結點的單鏈表的頭指針，指針變量p指向一個新結點，next是結點的指針域，若要將p所指結點插入到單鏈表的表頭，則正確的語句序列是

A. head->next= p; p->next= head;

B. p->next = head->next; head = p;

C. head = p; p->next = head->head;

D. p->next = head->next; head->next p;

5.后綴表達式求值的過程中要用到的數據結構是

A.一個保存各種操作符的棧

B.一個保存操作數及運算結果的棧

C.兩個分別保存操作符和操作數的棧

D.兩個分別保存操作數和運算結果的棧

8.用n (n≥2)個帶權值的結點作為葉結點構造一 棵哈夫曼樹， 下列選項中正確的是

A.哈夫曼樹是葉結點權值之和最小的二叉樹

B.哈夫曼樹是帶權路徑長度WPL最小的二叉樹

C. n個帶有權值的結點可以構造出唯一棵哈夫曼樹

D.哈夫曼樹是有n個葉結點的二叉樹中高度最低的二叉樹

9.將一棵樹T轉換為等價的二叉樹T1，與T的后序遍歷序列相同的是T1的

A.前序遍歷序列

B. 中序遍歷序列

C. 后序遍歷序列

D. 按層遍歷序列.

10. 要在帶權圖(權值>0)中求從某一頂點到其余各頂點的最短路徑，應采用的算法是

A.哈夫曼算法

B.普里姆算法

C.克魯斯卡爾算法

D.迪杰斯特拉算法

11.設圖G存在拓撲序列，則下列結論中正確的是

A.圖G是一個有向圖

B.圖G的拓撲序列唯一

C.圖G是一個無向圖

D.圖G是一個有向無環圖.

12.內排序過程中，待排序數據保存在

A. CPU中

B.內存儲器中

C.外存儲器中

D.計算機中

13.下列排序方法中，關鍵字總的比較次數與記錄的初始排列次序無關的是

A.冒泡排序

B.希爾排序

C.直接插入排序

D.直接選擇排序

14.散列查找方法可以達到的最好時間復雜度是

A.0(1)

B. O(n)

C. O(log n)

D.0(n'2)

15.下列關于二分查找判定樹T的敘述中，正確的是

A. T是一棵二叉樹

B. T是一棵滿二叉樹

C. T是一棵完全二叉樹

D. T的葉結點在同一層

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

16.算法必須滿足的五個準則是:輸入、輸出、有窮性、確定性和           

17.將100個數據元素保存在順序表中，若第一個元素的存儲地址是1000,第二個元素的存儲地址是1004，則該順序表最后一個元素的存儲地址是           

18.循環隊列保存在長度為M的數組中，隊頭為front, 隊尾為rear,若要求隊滿時條件為真，則條件表達式應是           

19.廣義表(())的長度是           

20.具有n個結點的完全二叉樹的深度為           

21.圖G的鄰接矩陣不是一個對稱矩陣，則圖G一定是           圖。

22.頂點表示活動、邊表示活動間先后關系的有向無環圖稱為           網。

23.在排序過程中，如果具有相同關鍵字的記錄之間的相對次序保持不變，則稱該排序方法是           的。

24.對二叉排序樹BT進行           遍歷可以得到BT中所有結點的有序序列。

25.在一棵25階的B樹中，非根結點內所包含的關鍵字個數至少是           個。

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

26.將中綴表達式“a*(b+c)”轉換為后綴表達式，請回答下列問題。

(1)畫出轉換過程中棧的變化過程。

(2)寫出轉換后得到的后綴表達式。

27.已知二叉樹T的前序遍歷序列為: adbce, 中序遍歷序列為: daceb.請回答下列問題。

(1)畫出對應的二叉樹T。

(2)建立并畫出二叉樹T的后序線索。

28.求題28圖的最小生成樹。要求:按照克魯斯卡爾算法的思想，依次寫出進入最小生成樹的邊。

29.已知數據序列(19, 14, 23, 01, 68, 79, 84, 27,55, 11, 10)，請畫出建立大根堆的過程。