2020年10月自考02331數(shù)據(jù)結(jié)構(gòu)試題及答案含解析

數(shù)據(jù)結(jié)構(gòu)年月真題

02331202010

1、【單選題】數(shù)據(jù)結(jié)構(gòu)研究的基本內(nèi)容是

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

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

A:

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

B:

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

C:

答D:案：A

解析：數(shù)據(jù)結(jié)構(gòu)研究的基本內(nèi)容包括數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和對(duì)數(shù)據(jù)元素施加的操

作。1.數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)描述了數(shù)據(jù)元素之間的關(guān)系，包括線性結(jié)構(gòu)、

樹(shù)形結(jié)構(gòu)、圖形結(jié)構(gòu)等。線性結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系，如數(shù)組、鏈表

等；樹(shù)形結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系，如二叉樹(shù)、堆等；圖形結(jié)構(gòu)中的數(shù)據(jù)

元素之間存在多對(duì)多的關(guān)系，如圖、網(wǎng)絡(luò)等。2.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)描述了

數(shù)據(jù)在計(jì)算機(jī)內(nèi)存中的存儲(chǔ)方式，包括順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)等。順序存儲(chǔ)將數(shù)據(jù)元素連續(xù)

地存儲(chǔ)在一塊連續(xù)的內(nèi)存空間中，如數(shù)組；鏈?zhǔn)酱鎯?chǔ)通過(guò)指針將數(shù)據(jù)元素存儲(chǔ)在不連續(xù)的

內(nèi)存空間中，如鏈表。3.對(duì)數(shù)據(jù)元素施加的操作：對(duì)數(shù)據(jù)元素施加的操作包括插入、刪

除、查找、修改等。這些操作可以通過(guò)不同的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)，不同的數(shù)據(jù)結(jié)構(gòu)對(duì)這些操

作的效率有所差異。通過(guò)研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和對(duì)數(shù)據(jù)元素施加的操作，可以

選擇合適的數(shù)據(jù)結(jié)構(gòu)來(lái)解決實(shí)際問(wèn)題，提高數(shù)據(jù)的存儲(chǔ)和操作效率。

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

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

源程序的代碼長(zhǎng)度

A:

程序采用的語(yǔ)言

B:

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

C:

答D:案：D

解析：算法的時(shí)間復(fù)雜度是評(píng)價(jià)算法好壞的重要指標(biāo)之一。時(shí)間復(fù)雜度描述了算法執(zhí)行所

需的時(shí)間與輸入規(guī)模之間的關(guān)系。它衡量了算法的執(zhí)行效率，即算法在處理不同規(guī)模的輸

入時(shí)所需的時(shí)間量級(jí)。通常情況下，我們希望算法的時(shí)間復(fù)雜度盡可能低，即算法的執(zhí)行

時(shí)間隨著輸入規(guī)模的增加而增長(zhǎng)得較慢。常見(jiàn)的時(shí)間復(fù)雜度有常數(shù)時(shí)間O(1)、對(duì)數(shù)時(shí)間

O(logn)、線性時(shí)間O(n)、線性對(duì)數(shù)時(shí)間O(nlogn)、平方時(shí)間O(n^2)等。其中，常數(shù)

時(shí)間和對(duì)數(shù)時(shí)間的算法效率較高，而平方時(shí)間的算法效率較低。通過(guò)分析算法的時(shí)間復(fù)雜

度，我們可以對(duì)算法的執(zhí)行效率有一個(gè)大致的估計(jì)，從而選擇合適的算法來(lái)解決問(wèn)題。然

而，時(shí)間復(fù)雜度并不是唯一的評(píng)價(jià)指標(biāo)，還需要考慮算法的空間復(fù)雜度、可讀性、可維護(hù)

性等因素來(lái)綜合評(píng)價(jià)算法的好壞。

3、【單選題】等概率情況下,在長(zhǎng)度為n的順序表中插入1個(gè)元素需要移動(dòng)元素的平均次數(shù)

是

1

n/2

A:

n

B:

n+1

C:

答D:案：B

4、【單選題】已知head為指向帶頭結(jié)點(diǎn)的單鏈表的頭指針,指針變量p指向一個(gè)新結(jié)

點(diǎn),next是結(jié)點(diǎn)的指針域,若要將p所指結(jié)點(diǎn)插入到單鏈表的表頭,則正確的語(yǔ)句序列是

head->next=p;p->next=head;

p->next=head->next;head=p;

A:

head=p;p->next=head->head;

B:

p->next=head->next;head->next=p;

C:

答D:案：D

5、【單選題】后綴表達(dá)式求值的過(guò)程中要用到的數(shù)據(jù)結(jié)構(gòu)是

一個(gè)保存各種操作符的棧

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

A:

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

B:

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

C:

答D:案：B

6、【單選題】廣義表LS=(((a),(b)),((c,(d)),(e,(f))),(g,h))的表尾是

(g,h)

((c,(d)),(e,(f))),(g,h)

A:

((g,h))

B:

(((c,(d)),(e,(f))),(g,h))

C:

答D:案：D

7、【單選題】

A

B

A:

C

B:

D

C:

答D:案：A

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

是

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

哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹(shù)

A:

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

B:

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

C:

答D:案：B

9、【單選題】將一棵樹(shù)T轉(zhuǎn)換為等價(jià)的二叉樹(shù)T1,與T的后序遍歷序列相同的是T1的

前序遍歷序列

中序遍歷序列

A:

后序遍歷序列

B:

按層遍歷序列

C:

答D:案：B

解析：將一棵樹(shù)T轉(zhuǎn)換為等價(jià)的二叉樹(shù)T1，且T1的后序遍歷序列與T的后序遍歷序列相

同的話，T1的中序遍歷序列也與T的中序遍歷序列相同。后序遍歷的順序是先遍歷左子

樹(shù)，再遍歷右子樹(shù)，最后訪問(wèn)根節(jié)點(diǎn)。如果T1的后序遍歷序列與T的后序遍歷序列相

同，說(shuō)明T1的根節(jié)點(diǎn)與T的根節(jié)點(diǎn)相同，且T1的左子樹(shù)和右子樹(shù)的后序遍歷序列也與T

的左子樹(shù)和右子樹(shù)的后序遍歷序列相同。中序遍歷的順序是先遍歷左子樹(shù)，再訪問(wèn)根節(jié)

點(diǎn)，最后遍歷右子樹(shù)。由于T1的后序遍歷序列與T的后序遍歷序列相同，說(shuō)明T1的根節(jié)

點(diǎn)與T的根節(jié)點(diǎn)相同，且T1的左子樹(shù)和右子樹(shù)的后序遍歷序列也與T的左子樹(shù)和右子樹(shù)

的后序遍歷序列相同。因此，T1的中序遍歷序列與T的中序遍歷序列相同。

10、【單選題】要在帶權(quán)圖(權(quán)值>0)中求從某一頂點(diǎn)到其余各頂點(diǎn)的最短路徑,應(yīng)采用的算

法是

哈夫曼算法

普里姆算法

A:

克魯斯卡爾算法

B:

迪杰斯特拉算法

C:

答D:案：D

解析：迪杰斯特拉算法是典型最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑。

它的主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展(廣度優(yōu)先搜索思想)，直到擴(kuò)展到終點(diǎn)為

止。

11、【單選題】設(shè)圖G存在拓?fù)湫蛄?則下列結(jié)論中正確的是

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

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

A:

圖G是一個(gè)無(wú)向圖

B:

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

C:

答D:案：D

12、【單選題】?jī)?nèi)排序過(guò)程中,待排序數(shù)據(jù)保存在

CPU中

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

A:

外存儲(chǔ)器中

B:

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

C:

答D:案：B

解析：內(nèi)部排序:待排序記錄存放在計(jì)算機(jī)隨機(jī)存儲(chǔ)器中(說(shuō)簡(jiǎn)單點(diǎn),就是內(nèi)存)進(jìn)行的排序

過(guò)程。

13、【單選題】下列排序方法中,關(guān)鍵字總的比較次數(shù)與記錄的初始排列次序無(wú)關(guān)的是

冒泡排序

希爾排序

A:

直接插入排序

B:

直接選擇排序

C:

答D:案：D

14、【單選題】散列查找方法可以達(dá)到的最好時(shí)間復(fù)雜度是

O(1)

A:

O(n)

O(logn)

B:

O(n1/2)

C:

答D:案：A

解析：散列查找方法可以達(dá)到的最好時(shí)間復(fù)雜度是O(1)。散列查找，也稱為哈希查找，是

一種通過(guò)散列函數(shù)將關(guān)鍵字映射到存儲(chǔ)位置的查找方法。在理想情況下，如果散列函數(shù)能

夠?qū)⒚總€(gè)關(guān)鍵字均勻地映射到不同的存儲(chǔ)位置，那么查找一個(gè)元素的時(shí)間復(fù)雜度就是常數(shù)

級(jí)別的，即O(1)。

15、【單選題】下列關(guān)于二分查找判定樹(shù)T的敘述中,正確的是

T是一棵二叉樹(shù)

T是一棵滿二叉樹(shù)

A:

T是一棵完全二叉樹(shù)

B:

T的葉結(jié)點(diǎn)在同一層

C:

答D:案：A

16、【問(wèn)答題】將中綴表達(dá)式“a*(b+c)”轉(zhuǎn)換為后綴表達(dá)式,請(qǐng)回答下列問(wèn)題。(1)畫(huà)出

轉(zhuǎn)換過(guò)程中棧的變化過(guò)程。(2)寫(xiě)出轉(zhuǎn)換后得到的后綴表達(dá)式。

答案：

17、【問(wèn)答題】已知二叉樹(shù)T的前序遍歷序列為:adbce,中序遍歷序列為:daceb請(qǐng)回答下列

問(wèn)題。(1)畫(huà)出對(duì)應(yīng)的二叉樹(shù)T。(2)建立并畫(huà)出二叉樹(shù)T的后序線索。

答案：

18、【問(wèn)答題】

答案：

19、【問(wèn)答題】已知數(shù)據(jù)序列(19,14,23,01,68,79,84,27,55,11,10),請(qǐng)畫(huà)出建立大根堆的

過(guò)程。

答案：

20、【問(wèn)答題】

答案：

21、【問(wèn)答題】

答案：(1)-1(2)L.length(3)pmax-pmin

22、【問(wèn)答題】

答案：(1)null(2)head->next(3)head->next

23、【問(wèn)答題】

答案：(1)2,10.12.24,3343,50,66,88(2)增量序列(3)函數(shù)f33()的功能是對(duì)數(shù)組a進(jìn)

行希爾排序。

24、【問(wèn)答題】

答案：

25、【填空題】算法必須滿足的五個(gè)準(zhǔn)則是:輸入、輸出、有窮性、確定性和____

答案：可行性

26、【填空題】將100個(gè)數(shù)據(jù)元素保存在順序表中,若第一個(gè)元素的存儲(chǔ)地址是1000,第二個(gè)

元素的存儲(chǔ)地址是1004,則該順序表最后一個(gè)元素的存儲(chǔ)地址是____

答案：1396

27、【填空題】循環(huán)隊(duì)列保存在長(zhǎng)度為M的數(shù)組中,隊(duì)頭為front,隊(duì)尾為rear,若要求隊(duì)滿

時(shí)條件為真,則條件表達(dá)式應(yīng)是____

答案：(rear+1)%M==front

28、【填空題】廣義表(())的長(zhǎng)度是____

答案：1

29、【填空題】具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為_(kāi)___

答案：[logn]+1(或]log(n+1)]

30、【填空題】圖G的鄰接矩陣不是一個(gè)對(duì)稱矩陣,則圖G一定是____圖。

答案：有向

31、【填空題】頂點(diǎn)表示活動(dòng)、邊表示活動(dòng)間先