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

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

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

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

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

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

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

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

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

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

B.源程序的代碼長度

C.程序采用的語言

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

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

A.1

B. n/2

C. n

D. n+1

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

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.一個(gè)保存各種操作符的棧

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

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

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

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

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

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

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

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

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

A.前序遍歷序列

B. 中序遍歷序列

C. 后序遍歷序列

D. 按層遍歷序列.

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

A.哈夫曼算法

B.普里姆算法

C.克魯斯卡爾算法

D.迪杰斯特拉算法

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

A.圖G是一個(gè)有向圖

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

C.圖G是一個(gè)無向圖

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

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

A. CPU中

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

C.外存儲(chǔ)器中

D.計(jì)算機(jī)中

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

A.冒泡排序

B.希爾排序

C.直接插入排序

D.直接選擇排序

14.散列查找方法可以達(dá)到的最好時(shí)間復(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é)點(diǎn)在同一層

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

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

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

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

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

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

21.圖G的鄰接矩陣不是一個(gè)對(duì)稱矩陣，則圖G一定是           圖。

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

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

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

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

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

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

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

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

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

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

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

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

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