?全國2020年10月自考數(shù)據(jù)結(jié)構(gòu)02331真題

自考真題是考生復(fù)習(xí)備考的一大法寶，需要好好利用，而且年份離的越近，參考價值越高。以下是希賽網(wǎng)自考頻道整理的全國2020年10月自考數(shù)據(jù)結(jié)構(gòu)02331真題，考生可參考試卷題型、分值、重點考試內(nèi)容及答題規(guī)范，參考答案現(xiàn)在暫未公布，希賽網(wǎng)將持續(xù)更新。

全國2020年10月自考數(shù)據(jù)結(jié)構(gòu)02331真題

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

1.數(shù)據(jù)結(jié)構(gòu)研究的基本內(nèi)容是

A.數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和對數(shù)據(jù)元素施加的操作

B.數(shù)據(jù)的類型、數(shù)據(jù)的定義、算法描述和各種操作實現(xiàn)

C.數(shù)據(jù)的線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖型結(jié)構(gòu)及相關(guān)的算法

D.數(shù)據(jù)元素之間的邏輯關(guān)系、物理存儲和相關(guān)程序?qū)崿F(xiàn)

2.數(shù)據(jù)結(jié)構(gòu)中，評價算法好壞的重要指標(biāo)之一是

A.程序的執(zhí)行時間

B.源程序的代碼長度

C.程序采用的語言

D.算法的時間復(fù)雜度

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

A.1

B. n/2

C. n

D. n+1

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

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.后綴表達(dá)式求值的過程中要用到的數(shù)據(jù)結(jié)構(gòu)是

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

B.一個保存操作數(shù)及運算結(jié)果的棧

C.兩個分別保存操作符和操作數(shù)的棧

D.兩個分別保存操作數(shù)和運算結(jié)果的棧

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

A.哈夫曼樹是葉結(jié)點權(quán)值之和最小的二叉樹

B.哈夫曼樹是帶權(quán)路徑長度WPL最小的二叉樹

C. n個帶有權(quán)值的結(jié)點可以構(gòu)造出唯一棵哈夫曼樹

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

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

A.前序遍歷序列

B. 中序遍歷序列

C. 后序遍歷序列

D. 按層遍歷序列.

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

A.哈夫曼算法

B.普里姆算法

C.克魯斯卡爾算法

D.迪杰斯特拉算法

11.設(shè)圖G存在拓?fù)湫蛄校瑒t下列結(jié)論中正確的是

A.圖G是一個有向圖

B.圖G的拓?fù)湫蛄形ㄒ?/p>

C.圖G是一個無向圖

D.圖G是一個有向無環(huán)圖.

12.內(nèi)排序過程中，待排序數(shù)據(jù)保存在

A. CPU中

B.內(nèi)存儲器中

C.外存儲器中

D.計算機中

13.下列排序方法中，關(guān)鍵字總的比較次數(shù)與記錄的初始排列次序無關(guān)的是

A.冒泡排序

B.希爾排序

C.直接插入排序

D.直接選擇排序

14.散列查找方法可以達(dá)到的最好時間復(fù)雜度是

A.0(1)

B. O(n)

C. O(log n)

D.0(n'2)

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

A. T是一棵二叉樹

B. T是一棵滿二叉樹

C. T是一棵完全二叉樹

D. T的葉結(jié)點在同一層

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

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

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

18.循環(huán)隊列保存在長度為M的數(shù)組中，隊頭為front, 隊尾為rear,若要求隊滿時條件為真，則條件表達(dá)式應(yīng)是           

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

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

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

22.頂點表示活動、邊表示活動間先后關(guān)系的有向無環(huán)圖稱為           網(wǎng)。

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

24.對二叉排序樹BT進(jìn)行           遍歷可以得到BT中所有結(jié)點的有序序列。

25.在一棵25階的B樹中，非根結(jié)點內(nèi)所包含的關(guān)鍵字個數(shù)至少是           個。

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

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

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

(2)寫出轉(zhuǎn)換后得到的后綴表達(dá)式。

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

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

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

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

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