濱州學(xué)院數(shù)據(jù)結(jié)構(gòu)期末考試復(fù)習(xí)題庫(kù)

2023年上學(xué)期數(shù)據(jù)結(jié)構(gòu)期末考試題庫(kù)

一、單項(xiàng)選擇題

1.對(duì)二叉排序樹(shù)進(jìn)行（），可以得到各結(jié)點(diǎn)鍵值的遞增序列。

A.先根遍歷

B.中根遍歷

C.層次遍歷

D.后根遍歷

答案：B

2.最好和最壞時(shí)間復(fù)雜度均為O（nlog<sub〉2</sub〉n）且穩(wěn)定的排序方法是（）。

A.快速排序

B.堆排序

C.歸并排序

D.基數(shù)排序

答案：C

3.

將數(shù)組稱為隨機(jī)存儲(chǔ)結(jié)構(gòu)是因?yàn)椋ǎ?/p>

A.數(shù)組元素是隨機(jī)的

B.隨時(shí)可以對(duì)數(shù)組元素進(jìn)行訪問(wèn)

C.對(duì)數(shù)組的任一元素的存取時(shí)間是相等的

D.數(shù)組的存儲(chǔ)結(jié)構(gòu)是不定的

答案：C

4.圖的廣度遍歷必須借助（）作為輔助空間。

A.棧

B.隊(duì)列

C.查找表

D.數(shù)組

答案：B

5.在AVL樹(shù)中，每個(gè)結(jié)點(diǎn)的平衡因子的取值范圍是（）。

A.-1-1

B.-2-2

C.1-2

D.0-1

答案：A

6.在有頭結(jié)點(diǎn)的單鏈表L中，向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行（）。

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

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

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

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

答案：D

第1/57頁(yè)

7.循環(huán)鏈表的主要優(yōu)點(diǎn)是（）。

A.不在需要頭指針了

B.已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到他的直接前趨

C.在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好的保證鏈表不斷開(kāi)

D.從表中的任意結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表

答案：D

8.若要從1000個(gè)元素中得到2個(gè)最小值元素，最好采用（）方法。

A.直接插入排序

B.直接選擇排序

C.堆排序

D.快速排序

答案：B

9對(duì)關(guān)鍵字序列（14,5,19,20,11,19）,第一趟排序的結(jié)果為（14,5,19,20,11,19）,則可能的排序

方法是（）。

A.簡(jiǎn)單選擇排序

B.快速排序

C.希爾排序

D.二路歸并排序

答案：C

10.某二叉樹(shù)的先根遍歷序列和后根遍歷序列相同，則該二叉樹(shù)的特征是（）o

A.高度等于其結(jié)點(diǎn)數(shù)

B.任一結(jié)點(diǎn)無(wú)左孩子

C.任一結(jié)點(diǎn)無(wú)右孩子

D.空或只有一個(gè)結(jié)點(diǎn)

答案：D

1L時(shí)間復(fù)雜性為O（nk）g₂n）且空間復(fù)雜性為0（1）的排序方法是（）。

A.歸并排序

B.堆排序

C.快速排序

D.錦標(biāo)賽排序

答案：B

12.除根結(jié)點(diǎn)外，樹(shù)上每個(gè)結(jié)點(diǎn)（）。

A.可有任意多個(gè)孩子、一個(gè)雙親

B.可有任意多個(gè)孩子、任意多個(gè)雙親

C.可有一個(gè)孩子、任意多個(gè)雙親

D.只有一個(gè)孩子、一個(gè)雙親

答案：A

13.設(shè)計(jì)一個(gè)判斷表達(dá)式中左右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最好。

A.順序表

B.鏈表

C.隊(duì)列

第2/57頁(yè)

D.棧

答案：D

14.

下列查找方法中，不屬于動(dòng)態(tài)的查找方法是（）。

A.二叉排序樹(shù)法

B.平衡樹(shù)法

C.散列法

D.二分查找法

答案：D

15.導(dǎo)致隊(duì)列下溢的操作是（）。

A.隊(duì)滿時(shí)執(zhí)行出隊(duì)

B.隊(duì)滿時(shí)執(zhí)行入隊(duì)

C.隊(duì)空時(shí)執(zhí)行出隊(duì)

D.隊(duì)空時(shí)執(zhí)行入隊(duì)

答案：C

16.若一個(gè)圖的邊集為{<1,2〉,<1,4>,<2,5>,<3,1〉,<3,5>,<4,3>},則從頂點(diǎn)1開(kāi)始對(duì)該圖進(jìn)行深

度優(yōu)先搜索，得到的頂點(diǎn)序列可能為Oo

A.1,2,5,4,3

B.1,2,3,4,5

C.1,2,5,3,4

D.1,4,3,2,5

答案：A

17.要將現(xiàn)實(shí)生活中的數(shù)據(jù)轉(zhuǎn)化為計(jì)算機(jī)所能表示的形式，其轉(zhuǎn)化過(guò)程依次為（）。

A.邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、機(jī)外表示

B.存儲(chǔ)結(jié)構(gòu)、邏輯結(jié)構(gòu)、機(jī)外表示

C.機(jī)外表示、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)

D.機(jī)外表示、存儲(chǔ)結(jié)構(gòu)、邏輯結(jié)構(gòu)

答案：C

18.圖的深度遍歷必須借助（）作為輔助空間。

A.棧

B.隊(duì)列

C.查找表

D.數(shù)組

答案：A

19.多維數(shù)組之所以有行優(yōu)先順序和列優(yōu)先順序兩種存儲(chǔ)方式是因?yàn)椋ǎ?/p>

A.數(shù)組的元素處在行和列兩個(gè)關(guān)系中

B.數(shù)組的元素必須從左到右順序排列

C.數(shù)組的元素之間存在次序關(guān)系

D.數(shù)組是多維結(jié)構(gòu)，內(nèi)存是一維結(jié)構(gòu)

答案：A

第3/57頁(yè)

20.

下列敘述錯(cuò)誤的是（）。

A.多維數(shù)組是向量的推廣。

B.多維數(shù)組是非線性結(jié)構(gòu)。

C.如果將二維數(shù)組看成由若干個(gè)行向量組成的一維數(shù)組，則為線性結(jié)構(gòu)。

D.對(duì)矩陣進(jìn)行壓縮存儲(chǔ)的目的是為了數(shù)據(jù)加密。

答案：D

21.如果某圖的鄰接矩陣是對(duì)角線元素均為零的上三角矩陣，則此圖是（）0

A.有向完全圖

B.連通圖

C.強(qiáng)連通圖

D.有向無(wú)環(huán)圖

答案：D

22.關(guān)于哈夫曼樹(shù)，下列敘述正確的是（）。

A.可能有度為1的結(jié)點(diǎn)

B.總是完全二叉樹(shù)

C.有可能是滿二叉樹(shù)

D.WPL是深度最大葉子的帶權(quán)路徑長(zhǎng)度

答案：C

23.對(duì)關(guān)鍵字序歹U{Q,H,C,Y,P,A,M,S,R,D,F,X},用下歹U（）方法進(jìn)行第一趟排序的結(jié)果為

{F,H,C,D,P,A,M,Q,R,S,Y,X}。

A.直接插入排序

B.二路歸并排序

C.以第一元素為基準(zhǔn)的快速排序

D.基數(shù)排序

答案：C

24.假定有k個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)法把這k個(gè)關(guān)鍵字存入散列表中，至少要進(jìn)

行（）次探側(cè)。

A.k-1

B.k

C.k+1

D.k（k+l）/2

答案：D

25.若一個(gè)圖的邊集為{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>},則從頂點(diǎn)1開(kāi)始對(duì)該圖進(jìn)行廣

度優(yōu)先搜索，得到的頂點(diǎn)序列可能為（）。

A.1,2,3,4,5

B.1,2,4,3,5

C.1,2,4,5,3

D.1,4,2,5,3

答案：C

第4/57頁(yè)

26.

若進(jìn)棧序列為a,b,c,則通過(guò)入出棧操作能得到的a,b,c的不同排列個(gè)數(shù)為（）。

A.4

B.5

C.6

D.7

答案：B

27.在待排關(guān)鍵字序列基本有序的前提下，效率最高的排序方法是（）o

A.直接插入排序

B.快速排序

C.直接選擇排序

D.歸并排序

答案：A

28.在不完全排序的情況下，就可以找出前幾個(gè)最大值的方法是（）。

A.快速排序

B.直接插入排序

C.堆排序

D.歸并排序

答案：C

29.

單鏈表中增加頭結(jié)點(diǎn)的目的是為了（）。

A.使單鏈表至少有一個(gè)結(jié)點(diǎn)

B.標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置

C.方便運(yùn)算的實(shí)現(xiàn)

D.說(shuō)明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)

答案：C

30.

在索引查找中，若主表長(zhǎng)度為144,它被均分為12子表，每個(gè)子表的長(zhǎng)度均為12,則索引

查找的平均查找長(zhǎng)度為（）。

A.13

B.24

C.12

D.79

答案：A

31.稀疏矩陣常用的壓縮存儲(chǔ)方法有兩種，即（）。

A.二維數(shù)組和三維數(shù)組

B.三元組和散列

C.三元組和十字鏈表

第5/57頁(yè)

D.散列和十字鏈表

答案：C

32.在n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接表中，存放表頭結(jié)點(diǎn)的數(shù)組的大小為（）。

A.n

B.n+e

C.n+2e

D.e

答案：A

33.要解決散列引起的沖突問(wèn)題，常采用的方法有（）。

A.數(shù)字分析法、平方取中法

B.數(shù)字分析法、線性探測(cè)法

C.二次探測(cè)法、平方取中法

D.二次探測(cè)法、鏈地址法

答案：D

34.

若某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采

用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。

A.單鏈表

B.僅有頭指針的單循環(huán)鏈表

C.雙鏈表

D.僅有尾指針的單循環(huán)鏈表

答案：D

35.

棧和隊(duì)列通常采用的兩種存儲(chǔ)方式是（）。

A.散列存儲(chǔ)和索引存儲(chǔ)

B.索引存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)

C.順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)

D.散列存儲(chǔ)和順序存儲(chǔ)

答案：C

36.下面關(guān)于圖的存儲(chǔ)的敘述中，（）是正確的。

A.鄰接矩陣表示時(shí)，占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)

B.鄰接矩陣表示時(shí)，占用的存儲(chǔ)空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)

C.鄰接表表示時(shí)，占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)

D.鄰接表表示時(shí)，占用的存儲(chǔ)空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)

答案：A

37.下列關(guān)于串的敘述中，正確的是（）。

A.一個(gè)串的字符個(gè)數(shù)即該串的長(zhǎng)度

B.一個(gè)串的長(zhǎng)度至少是1

C.空串是由空格字符組成的串

第6/57頁(yè)

D.兩個(gè)串若長(zhǎng)度相同，則它們相等

答案：A

38.棧和隊(duì)列的共同特點(diǎn)是（）。

A.都是先進(jìn)后出

B.都是先進(jìn)先出

C.只允許在端點(diǎn)處插入和刪除元素

D.沒(méi)有共同點(diǎn)

答案：C

39.給定整數(shù)集合{3,5,6,9,12},與之對(duì)應(yīng)的哈夫曼樹(shù)是（）。<imgheight="102"width="717"

alt=""src="/UserFiles/Image/hsm/sd16.png"/>

A.A

B.B

C.C

D.D

答案：C

40.

算法分析的目的是（）。

A.找出數(shù)據(jù)結(jié)構(gòu)的合理性

B.研究算法中的輸入/輸出關(guān)系

C.分析算法的效率以求改進(jìn)

D.分析算法的易讀性

答案：C

41.假設(shè)某完全二叉樹(shù)順序存儲(chǔ)在數(shù)組.BT[m]中，其中根結(jié)點(diǎn)存放在BT⑼，若BT「i]中的結(jié)

點(diǎn)有左孩子，則左孩子存放在（）。

A.BT[i/2]

B.BT[2*i-l]

C.BT[2*i]

D.BT[2*i+l]

答案：D

42.連通圖是指圖中任意兩個(gè)頂點(diǎn)之間（）。

A.都連通的無(wú)向圖

B.都不連通的無(wú)向圖

C.都連通的有向圖

D.都不連通的有向圖

答案：A

43.若結(jié)點(diǎn)的存儲(chǔ)地址可以反映數(shù)據(jù)間的邏輯關(guān)系，則相應(yīng)的存儲(chǔ)結(jié)構(gòu)應(yīng)為（）o

A.順序存儲(chǔ)結(jié)構(gòu)

B.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

C.索引存儲(chǔ)結(jié)構(gòu)

D.散列存儲(chǔ)結(jié)構(gòu)

第7/57頁(yè)

答案：A

44.為便于判別有向圖中是否存在回路，可借助于（）。

A.廣度優(yōu)先搜索算法

B.最小生成樹(shù)算法

C.最短路徑算法

D.拓?fù)渑判蛩惴?/p>

答案：D

45.

對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（）。

A.以順序方式存儲(chǔ)

B.以鏈接方式存儲(chǔ)

C.順序存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序

D?鏈?zhǔn)酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序

答案：C

46.在AVL樹(shù)中，任一結(jié)點(diǎn)的（）。

A.左、右子樹(shù)的高度均相同

B.左、右子樹(shù)高度差的絕對(duì)值不超過(guò)1

C.左、右子樹(shù)的結(jié)點(diǎn)數(shù)均相同

D.左、右子樹(shù)結(jié)點(diǎn)數(shù)差的絕對(duì)值不超過(guò)1

答案：B

47.對(duì)于有向圖，其鄰接矩陣表示相比鄰接表表示更易于進(jìn)行的操作為（）。

A.求頂點(diǎn)的鄰接點(diǎn)

B.求頂點(diǎn)的度

C.深度優(yōu)先遍歷

D.廣度優(yōu)先遍歷

答案：B

48.

在順序表中，數(shù)據(jù)元素之間的邏輯關(guān)系用（）。

A.數(shù)據(jù)元素的相鄰地址表示

B.數(shù)據(jù)元素在表中的序號(hào)表示

C.指向后繼元素的指針表示

D.數(shù)據(jù)元素的值表示

答案：A

49.在二叉鏈表上交換所有分支結(jié)點(diǎn)左右子樹(shù)的位置，則利用（）遍歷方法最合適。

A.前序

B.中序

C后序

D.按層次

答案：C

第8/57頁(yè)

50.下面關(guān)于線性表的敘述錯(cuò)誤的是()。

A.線性表采用順序存儲(chǔ)，必須占用一片地址連續(xù)的單元；

B.線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作；

C.線性表采用鏈?zhǔn)酱鎯?chǔ)，不必占用一片地址連續(xù)的單元；

D.線性表采用鏈?zhǔn)酱鎯?chǔ)，便于進(jìn)行插入和刪除操作；

答案：B

51.

下列有關(guān)線性表的敘述中，正確的是()。

A.元素之間是線性關(guān)系

B.線性表中至少有一個(gè)元素

C.任一元素有且僅有一個(gè)直接前趨

D.任一元素有且僅有一個(gè)直接后繼

答案：A

52.以下敘述錯(cuò)誤的是()。

A.樹(shù)的先根遍歷需要借助棧來(lái)實(shí)現(xiàn)。

B.樹(shù)的層次遍歷需要借助隊(duì)列來(lái)實(shí)現(xiàn)。

C.樹(shù)的后根遍歷與對(duì)應(yīng)二叉樹(shù)的后根遍歷相同。

D.樹(shù)的先根序列與對(duì)應(yīng)二叉樹(shù)的先根序列相同。

答案：C

53.若下圖表示某廣義表,則它是一種()o<imgheight="178"width="155"alt=""

src=,7UserFiles/Image/hsm/zd8.pngH/>

A.線性表

B.純表

C.再入表

D.遞歸表

答案：D

54.

串是一種()線性表。

A.長(zhǎng)度受限

B.元素類型受限

C.操作受限

D.一般

答案：B

55.

在下列排序方法中，空間復(fù)雜性為OQogzn)的方法為()。

A.直接選擇排序

B.歸并排序

C.堆排序

第9/57頁(yè)

D.快速排序

答案：D

56.下列哪種情況需要遇到隊(duì)列（）o

A.迷宮求解

B.括號(hào)匹配

C.多級(jí)函數(shù)調(diào)用

D.多項(xiàng)打印任務(wù)的安排

答案：D

57.對(duì)有向圖，下面（）種說(shuō)法是正確的。

A.每個(gè)頂點(diǎn)的入度等于出度

B.每個(gè)頂點(diǎn)的度等于其入度與出度之和

C.每個(gè)頂點(diǎn)的入度為0

D.每個(gè)頂點(diǎn)的出度為0

答案：B

58.對(duì)n個(gè)頂點(diǎn)的有向圖，若所有頂點(diǎn)的出度之和為s,則所有頂點(diǎn)的入度之和為（）。

A.s

B.s-1

C.s+1

D.n

答案：A

59.為查找某一特定單詞在文本中出現(xiàn)的位置，可應(yīng)用的串運(yùn)算是（）。

A.插入

B.刪除

C.串聯(lián)接

D.子串定位

答案：D

60.從理論上講，將數(shù)據(jù)以（）結(jié)構(gòu)存放，查找一個(gè)數(shù)據(jù)的時(shí)間不依賴于數(shù)據(jù)的個(gè)數(shù)n。

A.二叉查找樹(shù)

B.鏈表

C.散列表

D.順序表

答案：C

61.對(duì)長(zhǎng)度為n的順序表，刪除第i個(gè)元素（IgiSn）時(shí)元素移動(dòng)的次數(shù)為（）o

A.n-i+1

B.n-i-1

C.i

D.n-i

答案：D

62.下列編碼中屬前綴碼的是（）o

A."{1,01,000,001}"

第10/57頁(yè)

B."{1,01,011,010}"

C."{0,10,110,11）"

D."{0,l,00,H}"

答案：A

63.

適用于靜態(tài)的查找方法為（）。

A.二分查找、二叉排序樹(shù)查找

B.二分查找、索引順序表查找

C.二叉排序樹(shù)查找、索引順序表查找

D.二叉排序樹(shù)查找、散列法查找

答案：B

64.靜態(tài)查找表與動(dòng)態(tài)查找表二者的根本差別在于（）。

A.它們的邏輯結(jié)構(gòu)不一樣

B.施加在其上的操作不同

C.所包含的數(shù)據(jù)元素的類型不一樣

D.存儲(chǔ)實(shí)現(xiàn)不一樣

答案：B

65.下圖是一棵（）。<imgheight="91"width="245"alt=""src="/UserFiles/Image/hsm/cdl5.png"

/>

A.4階B-樹(shù)

B.4階B+樹(shù)

C.3階B-樹(shù)

D.3階B+樹(shù)

答案：D

66.已知森林F={TLT2,T3},各棵樹(shù)Ti（i=L2,3）中所含結(jié)點(diǎn)的個(gè)數(shù)分別為7,3,5,則

與F對(duì)應(yīng)的二叉樹(shù)的右子樹(shù)中的結(jié)點(diǎn)個(gè)數(shù)為（）。

A.10

B.12

C.8

D.15

答案：C

67.

希爾排序的增量序列必須是（）。

A.遞增的

B.隨機(jī)的

C.遞減的

D.任意的

答案：C

68.在索引順序表中查找一個(gè)元素，可用的且最快的方法是（）。

第11/57頁(yè)

A.用順序查找法確定元素所在塊，再用順序查找法在相應(yīng)塊中查找

B.用順序查找法確定元素所在塊，再用二分查找法在相應(yīng)塊中查找

C.用二分查找法確定元素所在塊，再用順序查找法在相應(yīng)塊中查找

D.用二分查找法確定元素所在塊，再用二分查找法在相應(yīng)塊中查找

答案：C

69.串s="DataStructure"中長(zhǎng)度為3的子串的數(shù)目是()。

A.9

B.U

C.12

D.14

答案：C

7O.n個(gè)記錄直接選擇排序時(shí)所需的記錄最多交換次數(shù)是()。

A.n-1

B.n

C.n(n-l)/2

D.n(n+l)/2

答案：A

71.由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹(shù)()。

A.形態(tài)和平均查找長(zhǎng)度都不一定相同

B.形態(tài)不一定相同，但平均查找長(zhǎng)度相同

C.形態(tài)和平均查找長(zhǎng)度都相同

D.形態(tài)相同，但平均查找長(zhǎng)度不一定相同

答案：A

72.在循環(huán)雙鏈表的p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)的操作是()。

A.p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;

B.p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;

C.s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;

D.s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;

答案：D

73.若有向圖的鄰接矩陣中，主對(duì)角線以下的元素均為零，則該圖的拓?fù)溆行蛐蛄?)。

A.存在

B.不存在

C.不確定

答案：A

74.

在需要經(jīng)常查找結(jié)點(diǎn)的前趨與后繼的場(chǎng)合中，使用()比較合適。

A.單鏈表

B.雙鏈表

C.循環(huán)鏈表

D.順序表

第12/57頁(yè)

答案：D

75.

關(guān)于十字鏈表中的敘述，錯(cuò)誤的是（）。

A.便于查找每一行或列的非零元素

B.每行、每列的非零元素分別組成行鏈表、列鏈表

C.C.十字鏈表是一種多重鏈表

D.行鏈表、列鏈表的頭結(jié)點(diǎn)不能共用

答案：D

76.下圖所示二叉樹(shù)對(duì)應(yīng)的森林中有（）棵樹(shù)。<imgheight="140"width="186"alt=""

src="/UserFiles/Image/hsm/sdl4.png"/>

A.l

B.2

C.3

D.不確定

答案：C

77.某鏈表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除最后一個(gè)元素，則采

用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。

A.單鏈表

B.雙鏈表

C.單循環(huán)鏈表

D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表

答案：D

78.設(shè)S="abc";T="xyz”,則strcmp（S,T）的值為（）。

A.正數(shù)

B.負(fù)數(shù)

C.零

D.不確定

答案：B

79.對(duì)長(zhǎng)度為10的順序表進(jìn)行查找，若查找前面5個(gè)元素的概率相同，均為1/8,查找后面5

個(gè)元素的概率相同，均為3/40,則查找任一元素的平均查找長(zhǎng)度為（）。

A.5.5

B.5

C.39/8

D.19/4

答案：C

80.若下圖表示某廣義表，則它是一種（）o<imgheight="120"width="136"alt=""

src="/UserFiles/Image/hsm/20100326114057/zd7.png"/>

A.線性表

B.純表

C.再入表

第13/57頁(yè)

D.遞歸表

答案：C

81.棧和隊(duì)列都是（）。

A.限制存取位置的線性結(jié)構(gòu)

B.順序存儲(chǔ)的線性結(jié)構(gòu)

C.鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu)

D.限制存取位置的非線性結(jié)構(gòu)

答案：A

82.<spanstyle="font-size:10.5pt">下列各式中，按增長(zhǎng)率由小至大的順序正確排列的是

nnnM

</span><spanstyle=font-size:10.5pt>（）</span><spanstyle=font-size:10.5pt>o<span

lang=nEN-US"style="font-size:10.5pt;font-family:"times="“new=,n,>A</span><span

style=nfont-size:10.5pt;font-family:宋體;mso-font-kerning:l.Opt;mso-ansi-language:EN-US;

mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA;mso-bidi-fbnt-size:lO.Opt;

mso-ascii-font-family:'TimesNewRoman1;mso-hansi-font-family:TimesNewRoman,;

mso-bidi-font-family:TimesNewRomanM'>.</span>n^1/2,n!,2ⁿ,

n^3/2<spanlang="EN-US"style=nfont-size:10.5pt;font-family:"times=nn

new="u>B</span><spanstyle="font-size:10.5pt;font-family:宋體；mso-font?keming:1.Opt;

mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA;

mso-bidi-font-size:lO.Opt;mso-ascii-font-family:TimesNewRoman*;mso-hansi-font-family:

TimesNewRoman*;mso-bidi-font-family:TimesNewRoman'"〉.</span>n^3/2,

2ⁿ,n^logn,2¹⁰⁰<spanlang=nEN-USnstyle=nfont-size:

10.5pt;font-family:"times二"”new="n>C</span><spanstyle="font-size:10.5pt;font-family:宋

體;mso-font-kerning:1.Opt;mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;

mso-bidi-language:AR-SA;mso-bidi-font-size:10.Opt;mso-ascii-font-family:TimesNew

Roman*;mso-hansi-font-family:TimesNewRoman*;mso-bidi-font-family:TimesNew

Roman"',.</span>2ⁿ,logo,n^logn,n^3/2<span

lang=HEN-USustyle="font-size:10.5pt;font-family:"times二"“new=,n>>D</span><span

style=nfont-size:10.5pt;font-family:宋體；mso-font-keming:l.Opt;mso-ansi-language:EN-US;

mso-fareast-language:ZH-CN;mso-bidi-language:AR-SA;mso-bidi-font-size:lO.Opt;

mso-ascii-font-family:TimesNewRoman1;mso-hansi-font-family:'TimesNewRoman1;

mso-bidi-font-family:'TimesNewRomanH'>.</span>2¹⁰⁰,logn,2ⁿ,

nⁿ</span>

A.A

B.B

C.C

D.D

答案：D

83.連通網(wǎng)的最小生成樹(shù)是其所有生成樹(shù)中（）。

A.頂點(diǎn)集最小的生成樹(shù)

B.邊集最小的生成樹(shù)

C.頂點(diǎn)權(quán)值之和最小的生成樹(shù)

D.邊的權(quán)值之和最小的生成樹(shù)

答案：D

第14/57頁(yè)

84.若對(duì)n個(gè)元素進(jìn)行歸并排序，則進(jìn)行每一趟歸并的時(shí)間復(fù)雜性為()。

A.O(l)

B.O(log2n)

C.O(n)

D.O(n2)

答案：C

85.在n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接表中，邊結(jié)點(diǎn)的個(gè)數(shù)為()。

A.n

B.n*e

C.e

D.2*e

答案：D

86.

執(zhí)行下列程序段后，串X的值為()。S="abc";T="xyz";X=strcat(S,T);

A.^^abcxyz^^

B.''xyzabc”

C."abc”

D.^^xyz^^

答案：A

87.若一個(gè)圖的邊集為{(八上)小?,出0,9尸)心正)3萬(wàn))},則從頂點(diǎn)人開(kāi)始對(duì)該圖進(jìn)行深

度優(yōu)先搜索，得到的頂點(diǎn)序列可能為()o

A.A,B,C,F,D,E

B.A,C,F,D,E,B

C.A,B,D,C,F,E

D.A,B,D,F,E,C

答案：B

88

棧操作的原則是()。

A.先進(jìn)先出

B.后進(jìn)先出

C.棧底刪除

D.以上都不是

答案：B

89.線索二叉樹(shù)中某結(jié)點(diǎn)沒(méi)有左孩子的條件是()。

A.p!=NULL

B.p->ltag==O

C.p->ltag==l

D.p->lchild!=NULL

答案：c

第15/57頁(yè)

90.求單鏈表中當(dāng)前結(jié)點(diǎn)的后繼和前趨的時(shí)間復(fù)雜度分別是()。

A.O(n)和0(1)

B.0⑴和0(1)

C.O(l)和0(n)

D.O(n)和O(n)

答案：C

91.

關(guān)于矩陣的三元組表表示，以下敘述正確的是()。

A.轉(zhuǎn)置運(yùn)算時(shí)只需把每個(gè)三元組的行、列下標(biāo)互換即可。

B.存儲(chǔ)時(shí)只需要各非零元素的三元組信息，不需要其它信息。

C.適合于對(duì)稱矩陣的壓縮存儲(chǔ)。

D.訪問(wèn)元素時(shí)不能隨機(jī)存取。

答案：D

92.以下敘述錯(cuò)誤的是()。

A.數(shù)據(jù)可分為數(shù)值型和非數(shù)值型

B.數(shù)據(jù)類型可分為原子類型和結(jié)構(gòu)類型

C.運(yùn)算可分為加工型和引用型

D.數(shù)據(jù)結(jié)構(gòu)可分為邏輯結(jié)構(gòu)和非邏輯結(jié)構(gòu)

答案：D

93.線索二叉樹(shù)中某結(jié)點(diǎn)為葉子的條件是()。

A.p->lchild!=NULL||p->rchild!=NULL

B.p->ltag==O||p->rtag==O

C.p->lchild!=NULL&&p->rchild!=NULL

D.p->ltag==l&&p->rtag==l

答案：D

94.在下列排序方法中，空間復(fù)雜性為O(n)的方法為()。

A.快速排序

B.直接插入排序

C.堆排序

D.歸并排序

答案：D

95.在散列查找中，平均查找長(zhǎng)度主要與()有關(guān)。

A.散列表長(zhǎng)度

B.散列元素的個(gè)數(shù)

C.裝填因子

D.處理沖突方法

答案：C

96.若要在0(1)的時(shí)間內(nèi)將兩個(gè)循環(huán)鏈表頭尾相接，則應(yīng)對(duì)兩個(gè)循環(huán)鏈表各設(shè)置一個(gè)指針,

分別指向()。

A.各自的頭結(jié)點(diǎn)

第16/57頁(yè)

B.各自的尾結(jié)點(diǎn)

C.各自的第一個(gè)元素結(jié)點(diǎn)

D.一個(gè)表的頭結(jié)點(diǎn)，另一個(gè)表的尾結(jié)點(diǎn)

答案：B

97.以下關(guān)于算法敘述不正確的是()。

A.時(shí)間和空間性能往往是一對(duì)矛盾

B.常常可犧牲空間性能換取時(shí)間性能

C.常?？蔂奚鼤r(shí)間性能換取空間性能

D.時(shí)間和空間性能并不會(huì)矛盾

答案：D

98.對(duì)長(zhǎng)度為n的順序表，等概率情況下插入一個(gè)元素時(shí)平均要移動(dòng)元素的個(gè)數(shù)為()o

A.n/2

B.(n+l)/2

C.(n-l)/2

D.n

答案：A

99.與鄰接表表示相比，鄰接矩陣表示更適合()。

A.無(wú)向圖

B.有向圖

C.稠密圖

D.稀疏圖

答案：C

lOO.n個(gè)頂點(diǎn)的強(qiáng)連通圖若只有n條邊，則該有向圖的形狀是()。

A.無(wú)回路

B.有回路

C.環(huán)狀

D.樹(shù)狀

答案：C

lOl.n個(gè)記錄直接插入排序時(shí)所需的記錄最少比較次數(shù)是()。

A.n-1

B.n

C.n(n-l)/2

D.n(n+l)/2

答案：A

102.

算法的時(shí)間復(fù)雜度取決于()。

A.問(wèn)題的規(guī)模

B.數(shù)據(jù)的初始狀態(tài)

C.A和B

D.以上都不是

第17/57頁(yè)

答案：c

103.

下列排序方法中，穩(wěn)定的是（）。

A.直接選擇排序

B.冒泡排序

C.快速排序

D.希爾排序

答案：B

104.

若某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除最后一個(gè)元素，則

采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。

A.單鏈表

B.雙鏈表

C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表

D.容量足夠大的順序表

答案：D

105.若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前趨元素，則采用（）存儲(chǔ)方

式最節(jié)省運(yùn)算時(shí)間（）。

A.單鏈表

B.順序表

C.雙鏈表

D.單循環(huán)鏈表

答案：B

106.

若下圖表示某廣義表，則它是一種（）。

A.線性表

B.純表

C.再入表

D.遞歸表

答案：B

第18/57頁(yè)

107.對(duì)n個(gè)頂點(diǎn)和e條邊的有向圖，以鄰接矩陣存儲(chǔ)，則求圖中某頂點(diǎn)入度的時(shí)間復(fù)雜度為

()oA)O(n)B)O(e)C)O(n+e)D)O(n²)

A.A

B.B

C.C

D.D

答案：A

108.<spanstyle="font-size:12px"><spanstyle="font-family:宋體；mso-bidi-font-size:lO.Opt;

mso-ascii-font-family:'TimesNewRoman';mso-bidi-font-family:'TimesNewRoman';

mso-font-kerning:1.Opt;mso-ansi-language:EN-US;mso-fareast-language:ZH-CN;

mso-bidi-language:AR-SA">以下廣義表關(guān)系正確的是()。</span></span>

A.線性表<再入表〈純表〈遞歸表

B.線性表〈純表〈遞歸表〈再入表

C.純表〈線性表〈再入表〈遞歸表

D.線性表〈純表〈再入表〈遞歸表

答案：D

109.隊(duì)列操作的原則是()。

A.先進(jìn)先出

B.后進(jìn)先出

C.隊(duì)尾刪除

D.隊(duì)頭插入

答案：A

110.某完全二叉樹(shù)有7個(gè)葉子，則其結(jié)點(diǎn)總數(shù)為()。

A.14

B.13

C.13或14

D.以上都不是

答案：C

111.

下列排序方法中，不穩(wěn)定的是()。

A.冒泡排序

B.歸并排序

C.希爾排序

D.直接插入排序

答案：C

112.若結(jié)點(diǎn)的存儲(chǔ)地址與結(jié)點(diǎn)內(nèi)容有某種確定的關(guān)系，則相應(yīng)的存儲(chǔ)結(jié)構(gòu)應(yīng)為()。

A.順序存儲(chǔ)結(jié)構(gòu)

B.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

C.索引存儲(chǔ)結(jié)構(gòu)

D.散列存儲(chǔ)結(jié)構(gòu)

答案：D

第19/57頁(yè)

113.若只在線性表的首、尾兩端進(jìn)行插入操作，宜采用的存儲(chǔ)結(jié)構(gòu)為（）。

A.順序表

B.用頭指針表示的單循環(huán)鏈表

C.用尾指針表示的單循環(huán)鏈表

D.單鏈表

答案：C

114.設(shè)輸入序列為A,B,C,D,借助一個(gè)棧得到的輸出序列不可能是（）。

A.ABCD

B.ACDB

C.DABC

D.DCBA

答案：C

115.對(duì)n個(gè)元素進(jìn)行冒泡排序，最好情況下的只需進(jìn)行（）對(duì)相鄰元素之間的比較。

A.n

B.n-1

C.n+1

D.n/2

答案：B

116.下述序列中，哪個(gè)可能是在二叉排序樹(shù)上查找35時(shí)所比較過(guò)的關(guān)鍵字序列？

A.2,25,40,39,53,34,35

B.25,39,2,40,53,34,35

C.53,40,2,25,34,39,35

D.39,25,40,53,34,2,35

答案：C

117.串是（）。

A.一些符號(hào)構(gòu)成的序列

B.有限個(gè)字母構(gòu)成的序列

C.一個(gè)以上的字符構(gòu)成的序列

D.有限個(gè)字符構(gòu)成的序列

答案：D

118.

引起循環(huán)隊(duì)列隊(duì)頭位置發(fā)生變化的操作是（）。

A.入隊(duì)

B.出隊(duì)

C.取隊(duì)頭元素

D.取隊(duì)尾元素

答案：B

119.

用鏈表表示線性表的優(yōu)點(diǎn)是（）。

第20/57頁(yè)

A.便于隨機(jī)存取

B.花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少

C.便于插入和刪除

D.數(shù)據(jù)元素的物理順序與邏輯順序相同

答案：C

120.高度為n、結(jié)點(diǎn)數(shù)也為n的二叉樹(shù)，共有()棵。A)nB)2ⁿ-1C)n-lD)

2^n-l

A.A

B.B

C.C

D.D

答案：D

121.對(duì)長(zhǎng)度為n的順序表，訪問(wèn)第i個(gè)元素的時(shí)間是。。

A.O(n2)

B.O(n)

C.O(nlog2n)

D.O(l)

答案：D

122.二叉樹(shù)的葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對(duì)次序()。

A.可能改變

B.一定會(huì)改變

C.一定不改變

D.可能變也可能不變

答案：C

123.若一個(gè)圖的邊集為{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)},則從頂點(diǎn)A開(kāi)始對(duì)該圖進(jìn)行廣

度優(yōu)先搜索，得到的頂點(diǎn)序列可能為()o

A.A,B,C,D,E,F

B.A,B,C,F,D,E

C.A,B,D,C,E,F

D.A,C,B,F,D,E

答案：D

124.若一個(gè)圖中包含有k個(gè)連通分量，若要按照深度優(yōu)先搜索的方法訪問(wèn)所有頂點(diǎn)，則必須

調(diào)用()次深度優(yōu)先搜索遍歷的算法。

A.1

B.k

C.k-1

D.k+1

答案：B

125.在以單鏈表為存儲(chǔ)結(jié)構(gòu)的線性表中，數(shù)據(jù)元素之間的邏輯關(guān)系用()。

A.數(shù)據(jù)元素的相鄰地址表示

第21/57頁(yè)

B.數(shù)據(jù)元素在表中的序號(hào)表示

C.指向后繼元素的指針表示

D.數(shù)據(jù)元素的值表示

答案：C

126?設(shè)輸入序列為A,B,C,D,借助一個(gè)隊(duì)列得到的輸出序列可能是（）。

A.ABCD

B.DCBA

C.任意順序

D.以上都不是

答案：A

127.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址（）。

A.必須連續(xù)

B.部分地址必須連續(xù)

C.一定不連續(xù)

D.連續(xù)與否均可

答案：D

128.下面關(guān)于B樹(shù)和B+樹(shù)的敘述中，不正確的是

A.都是平衡的多叉樹(shù)

B.都是可用于文件的索引結(jié)構(gòu)

C.都能有效地支持順序檢索

D.都能有效地支持隨機(jī)檢索

答案：C

129.

以下敘述錯(cuò)誤的是（）。

A.數(shù)據(jù)的三個(gè)層次是數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)

B.數(shù)據(jù)類型是指相同性質(zhì)的計(jì)算機(jī)數(shù)據(jù)的集合

C.每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算的集合

D.儲(chǔ)存結(jié)構(gòu)中不僅要儲(chǔ)存數(shù)據(jù)的內(nèi)容，還要把數(shù)據(jù)間的關(guān)系表示出來(lái)。

答案：B

130.已知一個(gè)有向圖的邊集為{<a,b>,<a,c>,<a,d>,<b,d>,<b,e>,<d,e>},則由該圖產(chǎn)生的一種

可能的拓?fù)湫蛄袨椋ǎ﹐

A.a,b,c,d,e

B.a,c,d,e,b

C.a,c,b,e,d

D.a,c,d,b,e

答案：A

131.對(duì)11個(gè)元素進(jìn)行快速排序，最壞情況下需要進(jìn)行（）趟6）方）11-1011/2口）108<5此〉2</5此>11

A.A

B.B

C.C

第22/57頁(yè)

D.D

答案：B

132.

基數(shù)排序中的“基數(shù)”可以是()。

A.10

B.8

C.16

D.以上都可以

答案：D

133.對(duì)包含n個(gè)關(guān)鍵字的散列表進(jìn)行檢索，平均檢索長(zhǎng)度是()o

A)O(log₂n)B)O(n)C)不直接依賴于nD)O(nlog<sub〉2</sub>n)

A.A

B.B

C.C

D.D

答案：C

134.下列排序算法中，當(dāng)初始數(shù)據(jù)有序時(shí)，花費(fèi)時(shí)間反而最多的是()。

A.起泡排序

B.希爾排序

C.堆排序

D.快速排序

答案：D

135.排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是()排序法。

A.插入

B.選擇

C.希爾

D.快速

答案：D

136.算法分析是指()。

A.分析算法的正確性

B.分析算法的可讀性

C.分析算法的健壯性

D.分析算法的時(shí)空性能

答案：D

137.在n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接矩陣中，表示邊存在的元素個(gè)數(shù)為()。

A.n

B.n*e

C.e

D.2*e

答案：D

第23/57頁(yè)

138.有n個(gè)頂點(diǎn)的圖形成一個(gè)環(huán)，則其生成樹(shù)的個(gè)數(shù)為()。

A.1

B.n-1

C.n

D.n+1

答案：C

139.若要在單鏈表中的結(jié)點(diǎn)*p之后插入一個(gè)結(jié)點(diǎn)*s,則應(yīng)執(zhí)行的語(yǔ)句是()。

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

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

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

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

答案：A

140.3個(gè)結(jié)點(diǎn)可構(gòu)成()個(gè)不同形態(tài)的二叉樹(shù)。

A.2

B.3

C.4

D.5

答案：D

141.樹(shù)結(jié)構(gòu)最適合用來(lái)表示()。

A.有序數(shù)據(jù)

B.無(wú)序數(shù)據(jù)

C.元素間具有分支層次關(guān)系的數(shù)據(jù)

D.元素間無(wú)關(guān)聯(lián)的數(shù)據(jù)

答案：C

142.關(guān)鍵字比較次數(shù)與數(shù)據(jù)的初始狀態(tài)無(wú)關(guān)的排序算法是()。

A.直接選擇排序

B.冒泡排序

C.直接插入排序

D.希爾排序

答案：A

143.對(duì)n個(gè)結(jié)點(diǎn)的二叉樹(shù)，按()遍歷順序?qū)Y(jié)點(diǎn)編號(hào)(號(hào)碼為l~n)時(shí)，任一結(jié)點(diǎn)的編號(hào)等

于其左子樹(shù)中結(jié)點(diǎn)的最大編號(hào)加1,又等于其右子樹(shù)中結(jié)點(diǎn)的最小編號(hào)減1。

A.前根

B.中根

C后根

D層次

答案：B

144.設(shè)有向圖n個(gè)頂點(diǎn)和e條邊，進(jìn)行拓?fù)渑判驎r(shí)，總的計(jì)算時(shí)間為()。

A)O(nlog₂n)B)O(en)C)O(elog₂n)D)O(n+e)

A.A

第24/57頁(yè)

B.B

C.C

D.D

答案：D

145.（）存儲(chǔ)方式適用于折半查找。

A.鍵值有序的單鏈表

B.鍵值有序的順序表

C.鍵值有序的雙鏈表

D.鍵值無(wú)序的順序表

答案：B

146.設(shè)p指向單鏈表中的一個(gè)結(jié)點(diǎn)，s指向待插入的結(jié)點(diǎn)，則下述程序段的功能是（）。

s->next=p->next;p->next=s;t=p->data;p->data=s->data;s->data=t;

A.結(jié)點(diǎn)*p與結(jié)點(diǎn)*s的數(shù)據(jù)域互換

B.在p所指結(jié)點(diǎn)的元素之前插入元素

C.在p所指結(jié)點(diǎn)的元素之后插入元素

D.在結(jié)點(diǎn)*p之前插入結(jié)點(diǎn)*s

答案：D

147.二叉樹(shù)的結(jié)構(gòu)如下圖所示，其中序遍歷的序列為（）。<imgheight="221"width="257"

alt=""src='7UserFiles/Image/hsm/sd7.png"/>

A.a,b,d,g,c,e,f,h

B.d,g,b,a,e,c,h,f

C.g,d,b,e,h,f,c,a

D.a,b,c,d,e,f,g,h

答案：B

148.在C語(yǔ)言中，串的存儲(chǔ)方式是（）。

A.順序存儲(chǔ)

B.散列存儲(chǔ)

C.索引存儲(chǔ)

D?鏈?zhǔn)酱鎯?chǔ)

答案：A

149.下面的二叉樹(shù)中，（）不是完全二叉樹(shù)。<imgheight="175"width="691"alt=""

src="/UserFiles/Image/hsm/sd6.jpg"/>

A.A

B.B

C.C

D.D

答案：C

二、判斷題

150.數(shù)組的基本運(yùn)算有讀、寫、插入、刪除等。

答案：錯(cuò)誤

第25/57頁(yè)

151.如果根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)高度差不超過(guò)1,則該二叉樹(shù)是平衡二叉樹(shù)。

答案：錯(cuò)誤

152.每一種邏輯結(jié)構(gòu)只能對(duì)應(yīng)一種存儲(chǔ)結(jié)構(gòu)。

答案：錯(cuò)誤

153.

單鏈表中取第i個(gè)元素的時(shí)間與i成正比。

答案：正確

154.不是所有的有向圖都可以進(jìn)行拓?fù)渑判?，而能拓?fù)渑判驎r(shí)，結(jié)果不一定唯一。

答案：正確

155.計(jì)算機(jī)的速度越快，算法的時(shí)間復(fù)雜性就越低。

答案：錯(cuò)誤

156.排序的目的是為了方便以后的查找。

答案：正確

157.多維數(shù)組可以順序儲(chǔ)存，所以實(shí)際上是一種順序表。

答案：錯(cuò)誤

158.在順序表中按值查找運(yùn)算的復(fù)雜性為0(1)。

答案：錯(cuò)誤

159.算法的時(shí)間復(fù)雜性是指在計(jì)算機(jī)上的實(shí)際運(yùn)行時(shí)間。

答案：錯(cuò)誤

160.順序表插入和刪除時(shí)，移動(dòng)元素的個(gè)數(shù)與該元素的位置有關(guān)。

答案：正確

161.線性結(jié)構(gòu)可以順序存儲(chǔ)，也可以鏈接存儲(chǔ)。非線性結(jié)構(gòu)只能鏈接存儲(chǔ)。

答案：錯(cuò)誤

162.在棧的應(yīng)用中，棧頂指針總是指向真正的棧頂。

答案：錯(cuò)誤

163.

利用?？蓪⑦f歸程序轉(zhuǎn)化成非遞歸程序。

答案：正確

164.為了運(yùn)算方便，鏈隊(duì)列一般帶頭結(jié)點(diǎn)。

答案：正確

第26/57頁(yè)

165.一維數(shù)組是一種順序表。

答案：正確

166.堆排序是一種巧妙的樹(shù)型選擇排序。

答案：正確

167.稀疏矩陣壓縮存儲(chǔ)后會(huì)喪失隨機(jī)存取特性。

答案：正確

168.

顧名思義，快速排序法是在所有情況下，速度最快的排序方法。

答案：錯(cuò)誤

169?計(jì)算機(jī)的內(nèi)、外存越大，算法的空間復(fù)雜性就越低。

答案：錯(cuò)誤

170.任何樹(shù)或林都可轉(zhuǎn)化為二叉樹(shù)，反之，二叉樹(shù)可轉(zhuǎn)化為任何樹(shù)或林。

答案：錯(cuò)誤

171.在數(shù)據(jù)結(jié)構(gòu)中，算法的空間耗費(fèi)包括代碼和數(shù)據(jù)兩部分。

答案：錯(cuò)誤

172.有向圖中頂點(diǎn)i的出度等于鄰接矩陣中第i行中1的個(gè)數(shù)；入度等于第i列中1的個(gè)數(shù)。

答案：正確

173.如果n個(gè)頂點(diǎn)的無(wú)向圖有n條邊，則圖中肯定有回路。

答案：正確

174.矩陣按三元組形式存貯，就可節(jié)省存儲(chǔ)空間。

答案：錯(cuò)誤

175.若鏈隊(duì)列的頭指針為F,尾指針為R,則隊(duì)列中元素個(gè)數(shù)為R-F。

答案：錯(cuò)誤

176.

若有向圖中含有一個(gè)或多個(gè)環(huán)，則其頂點(diǎn)間不存在拓?fù)湫蛄小?/p>

答案：正確

177.

無(wú)向圖中邊數(shù)等于鄰接矩陣中1的個(gè)數(shù)的一半；也等于鄰接表中的邊表結(jié)點(diǎn)數(shù)的一半。

答案：正確

178.

哈夫曼樹(shù)是一種二叉樹(shù)，所以其節(jié)點(diǎn)的度可為0,1或2。

第27/57頁(yè)

答案：錯(cuò)誤

179.用線性探測(cè)法解決突出時(shí)，同義詞在散列表中是相鄰的。

答案：錯(cuò)誤

180.

在二叉排序樹(shù)中，即使刪除一個(gè)結(jié)點(diǎn)后馬上再插入該結(jié)點(diǎn)，該二叉排序樹(shù)的形態(tài)也可能不

同。

答案：正確

18L循環(huán)隊(duì)列中入隊(duì)和出隊(duì)的節(jié)點(diǎn)位置可出現(xiàn)在數(shù)組的任一端，已不滿足“一端進(jìn)另一端

出”的要求，故實(shí)際上已不是隊(duì)列了。

答案：錯(cuò)誤

182.關(guān)鍵路徑是指起點(diǎn)到終點(diǎn)的最短路徑，它決定了整個(gè)工期的長(zhǎng)短。

答案：錯(cuò)誤

183.稀疏矩陣就是矩陣的元素很少。

答案：錯(cuò)誤

184.

順序表不需存放指針，鏈表要存放指針，故鏈表的存儲(chǔ)空間要求總是比順序表大。

答案：錯(cuò)誤

185.圖的生成樹(shù)不唯一，但圖的最小生成樹(shù)是唯一的。

答案：錯(cuò)誤

186.不可能有二叉樹(shù)的任何遍歷次序是相同的。

答案：錯(cuò)誤

187.樹(shù)的度是指樹(shù)中結(jié)點(diǎn)的最大度數(shù)，所以二叉樹(shù)的度為2。

答案：錯(cuò)誤

188.不管樹(shù)的深度和形態(tài)如何，也不可能構(gòu)造出一棵剛好有100個(gè)結(jié)點(diǎn)的哈夫曼樹(shù)。

答案：正確

189.拓?fù)渑判蚩梢苑治瞿彻こ棠芊耥樌M(jìn)行。

答案：正確

190.消除遞歸不一定需要使用棧。

答案：正確

191.在線索二叉樹(shù)上，求結(jié)點(diǎn)的（遍歷）前趨和后繼時(shí)可利用線索得到，即不必進(jìn)行遍歷了。

答案：錯(cuò)誤

第28/57頁(yè)

192.二叉樹(shù)中可能所有結(jié)點(diǎn)的度都小于2。

答案：正確

193.線性表的邏輯順序與存儲(chǔ)順序總是一致的。

答案：錯(cuò)誤

194.連通圖的BFS生成樹(shù)一般比DFS生成樹(shù)的高度小。

答案：正確

195.數(shù)據(jù)的邏輯結(jié)構(gòu)與計(jì)算機(jī)無(wú)關(guān)，但存儲(chǔ)結(jié)構(gòu)依賴于計(jì)算機(jī)。

答案：正確

196.二叉排序樹(shù)上，以根到任一結(jié)點(diǎn)的路徑為界，則：路徑左邊結(jié)點(diǎn)〈路徑結(jié)點(diǎn)V路徑右

邊結(jié)點(diǎn)。

答案：錯(cuò)誤

197.隊(duì)列在使用中必須設(shè)置兩個(gè)指針，分別指向真正的隊(duì)頭和隊(duì)尾的位置。

答案：錯(cuò)誤

198.開(kāi)散列表和閉散列表的裝填因子都可大于、等于或小于1。

答案：錯(cuò)誤

199.單鏈表是順序存取結(jié)構(gòu)。

答案：正確

200.采用高速計(jì)算機(jī)，可以降低算法的時(shí)間復(fù)雜性。

答案：錯(cuò)誤

201.利用哈夫曼編碼，可以進(jìn)行文件壓縮。

答案：正確

202.圖G的生成樹(shù)T是G的子圖。

答案：正確

203.棧和隊(duì)列邏輯上都是線性表。

答案：正確

204.當(dāng)問(wèn)題具有先進(jìn)先出特點(diǎn)時(shí)，就需要用到棧。

答案：錯(cuò)誤

205.二叉樹(shù)中不可能有兩個(gè)結(jié)點(diǎn)在先根、中根和后根序列中的相對(duì)次序都不變。

答案：錯(cuò)誤

206.在AOE網(wǎng)中關(guān)鍵路徑最多只有一條。

答案：錯(cuò)誤

第29/57頁(yè)

207.數(shù)據(jù)的邏輯結(jié)構(gòu)和運(yùn)算集組成問(wèn)題的數(shù)學(xué)模型，與計(jì)算機(jī)無(wú)關(guān)。

答案：正確

208.如果某種排序算法是不穩(wěn)定的，則該方法沒(méi)有實(shí)際的應(yīng)用價(jià)值。

答案：錯(cuò)誤

2O9.Shell排序的時(shí)間性能與增量序列的選取有關(guān)，但關(guān)系不大。

答案：錯(cuò)誤

210.對(duì)任何圖，執(zhí)行一次深度優(yōu)先或廣度優(yōu)先遍歷后，就可訪問(wèn)到圖中所有節(jié)點(diǎn)。

答案：錯(cuò)誤

211.

以中序方式遍歷一個(gè)堆，則得到一個(gè)有序序列。

答案：錯(cuò)誤

212.二叉排序樹(shù)的中序遍歷序列是遞增的，它的前序或后序遍歷序列也可能是遞增的。

答案：正確

213.

含n個(gè)頂點(diǎn)的無(wú)向圖，其鄰接矩陣中非零元素的個(gè)數(shù)就是圖中的邊數(shù)。

答案：錯(cuò)誤

214.線索二叉鏈表就是用結(jié)點(diǎn)的空指針域來(lái)存放某種遍歷的前趨和后繼線索，所以線索二

叉鏈表中就沒(méi)有空指針了。

答案：錯(cuò)誤

215.

鏈棧一般不需要頭結(jié)點(diǎn)，因?yàn)闊o(wú)頭結(jié)點(diǎn)的鏈棧運(yùn)算也很方便。

答案：正確

216.數(shù)據(jù)結(jié)構(gòu)的概念包括數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算三個(gè)方面。

答案：正確

217.空串并不是由空白字符組成的串。

答案：正確

218.

如果網(wǎng)絡(luò)中有多條邊的權(quán)相同，則其最小生成樹(shù)就不會(huì)是唯一的。

答案：錯(cuò)誤

219.n個(gè)結(jié)點(diǎn)的有向圖，若它有n(n—l)條邊，則它一定是強(qiáng)連通的。

答案：正確

第30/57頁(yè)

220.由普通樹(shù)轉(zhuǎn)換來(lái)的二叉樹(shù)，其根結(jié)點(diǎn)一定沒(méi)有右子樹(shù)。

答案：正確

221.有向圖的鄰接表和逆鄰接表中的結(jié)點(diǎn)數(shù)肯定是相同的。

答案：正確

222.線性表、樹(shù)、圖等都可以用廣義表表示。

答案：正確

223.

每個(gè)節(jié)點(diǎn)一個(gè)鏈域的鏈表是單鏈表，每個(gè)節(jié)點(diǎn)兩個(gè)鏈域的鏈表是雙鏈表。

答案：錯(cuò)誤

224.哈夫曼樹(shù)中不存在度為1的結(jié)點(diǎn)。

答案：正確

225.空串是指長(zhǎng)度為0的字符串。

答案：錯(cuò)誤

226.樹(shù)和森林都可轉(zhuǎn)化為二叉樹(shù)，故對(duì)給定的二叉樹(shù)，不能區(qū)分是由樹(shù)還是森林轉(zhuǎn)換來(lái)的。

答案：錯(cuò)誤

227.有向圖中邊數(shù)等于鄰接矩陣中1的個(gè)數(shù)；也等于鄰接表中的邊表結(jié)點(diǎn)數(shù)。

答案：正確

228.單鏈表中的頭結(jié)點(diǎn)就是單鏈表的第一個(gè)結(jié)點(diǎn)。

答案：錯(cuò)誤

229.在拓?fù)湫蛄兄?，若兩點(diǎn)Vi和Vj相鄰，則從Vi到Vj有路徑。

答案：錯(cuò)誤

230.由二叉樹(shù)的先根和后根序列可以唯一確定該二叉樹(shù)。

答案：錯(cuò)誤

231.數(shù)組各元素在內(nèi)存中連續(xù)存放，故前后相鄰的兩元素物理地址相差為1或-1。

答案：錯(cuò)誤

232.若算法的復(fù)雜性與數(shù)據(jù)集的狀態(tài)無(wú)關(guān)，則最好、最壞和平均復(fù)雜性是相同的。

答案：正確

233.不論數(shù)據(jù)如何組織，分別在10000個(gè)結(jié)點(diǎn)和10個(gè)結(jié)點(diǎn)的查找表中進(jìn)行查找，前者的平均

查找長(zhǎng)度肯定比后者大。

答案：錯(cuò)誤

234.二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2。

第31/57頁(yè)

答案：錯(cuò)誤

235.廣義表不僅是線性表的推廣，也是樹(shù)的推廣。

答案：正確

236.

在順序表的某些位置插入和刪除結(jié)點(diǎn)時(shí)不需移動(dòng)其它結(jié)點(diǎn)。

答案：正確

237.二叉排序樹(shù)是用來(lái)進(jìn)行排序的。

答案：錯(cuò)誤

238.對(duì)稱矩陣壓縮存儲(chǔ)后仍然可以隨機(jī)存取。

答案：正確

239.鏈表中邏輯上相鄰的元素在物理位置上不一定相鄰。

答案：正確

240.縮短關(guān)鍵路徑上活動(dòng)的工期一定能夠縮短整個(gè)工程的工期。

答案：錯(cuò)誤

241.順序查找法不僅可用于順序表上的查找，也可用于鏈表上的查找。

答案：正確

242.有時(shí)冒泡排序的速度會(huì)快過(guò)快速排序。

答案：正確

243.將樹(shù)轉(zhuǎn)化為二叉樹(shù)后，原樹(shù)中的葉子結(jié)點(diǎn)在二叉樹(shù)中不一定也是葉子結(jié)點(diǎn)。

答案：正確

244.算法的正確性，一般不進(jìn)行形式化的證明，而是用測(cè)試來(lái)驗(yàn)證。

答案：正確

245.算法的時(shí)間復(fù)雜性越高，則計(jì)算機(jī)速度提高后，得到的收益就越大。

答案：錯(cuò)誤

246.二分查找所對(duì)應(yīng)的判定樹(shù)，是一棵理想平衡的二叉排序樹(shù)。

答案：正確

247.

基數(shù)排序不需進(jìn)行關(guān)鍵字間的比較，故執(zhí)行時(shí)間比基于比較的排序方法要快。

答案：錯(cuò)誤

248.二叉排序樹(shù)的形態(tài)與關(guān)鍵字的輸入序列有關(guān)，但平衡二叉排序樹(shù)是相同的。

答案：錯(cuò)誤

第32/57頁(yè)

249.順序表的存儲(chǔ)密度為1,鏈表的存儲(chǔ)密度肯定小于1。

答案：正確

250.在鏈棧上進(jìn)行進(jìn)棧操作時(shí)，不需判斷棧滿。

答案：正確

251.算法和程序沒(méi)有區(qū)別，在數(shù)據(jù)結(jié)構(gòu)中二者是通用的。

答案：錯(cuò)誤

252.

直接插入排序是穩(wěn)定的，而Shell排序就是調(diào)用若干趟直接插入排序，故也是穩(wěn)定的。

答案：錯(cuò)誤

253.在線性結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)都有一個(gè)直接前驅(qū)和一個(gè)直接后繼。

答案：錯(cuò)誤

254.與鏈表相比，順序表的主要優(yōu)點(diǎn)是不必用額外的空間來(lái)表示邏輯關(guān)系。

答案：錯(cuò)誤

255.

若二叉樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)，則為滿二叉樹(shù)。

答案：錯(cuò)誤

256.

順序表可以按序號(hào)隨機(jī)存取。

答案：正確

257.散列表可從關(guān)鍵字計(jì)算出存放地址，故查找中不需要進(jìn)行關(guān)鍵字的比較。

答案：錯(cuò)誤

258.

在開(kāi)散列表中不會(huì)出現(xiàn)堆積現(xiàn)象。

答案：正確

259.

滿二叉樹(shù)是一種特殊的完全二叉樹(shù)。

答案：正確

260.二路歸并排序的核心操作是把兩個(gè)有序序列合并為一個(gè)有序序列。

答案：正確

第33/57頁(yè)

261.設(shè)串的長(zhǎng)度為n,則其子串個(gè)數(shù)為n(n+l)/2。

答案：錯(cuò)誤

262.線性探查法在解決同義詞沖突的過(guò)程中，可能引起非同義詞的沖突。

答案：正確

263.若將當(dāng)前最長(zhǎng)的關(guān)鍵活動(dòng)的時(shí)間縮短2天，則整個(gè)工期可提前2天。

答案：錯(cuò)誤

三、填空題

264.n個(gè)頂點(diǎn)的連通圖至少條邊，最多條邊。

答案：<spanstyle='font-size:18px'>n-1>n(n-l)/2</span></p>

265.下面程序段的時(shí)間復(fù)雜性為。for(i=0;i<n;i++)for(j=0;j<

i；j++)A[i][j]=O；

答案：0(n²)</p>

266.圖的BFS遍歷類似樹(shù)的遍歷，是其推廣。

答案：層次</p>

267.圖的DFS遍歷類似樹(shù)的遍歷，是其推廣。

答案：先根</p>

268.下面程序段的時(shí)間復(fù)雜度為。y=n;while(y>1)y=y/2;

答案：O(log₂n)</p>

269.內(nèi)排序是指o

答案：數(shù)據(jù)全部在內(nèi)存中進(jìn)行排序</p>

270.希爾排序的增量序列中，最后一個(gè)增量為o

答案：l</p>

271.對(duì)廣義表L=((a,b),c,d)進(jìn)行操作head(tail(L))的結(jié)果是：。

答案：<spanstyle='font-size:18px'>c</span></p>

272.數(shù)組中，每個(gè)元素占3個(gè)單元，從首地址SA開(kāi)始存放，若該數(shù)組按列存放,

則元素A[8]⑸的地址是

答案：<spanstyle='font-size:18px'>SA+l17</span></p>

273.散列表的沖突處理方法有和兩種，對(duì)應(yīng)的散列表分別稱為開(kāi)散列

表和閉散列表。

答案：開(kāi)放地址法、鏈地址法(或拉鏈法)〈/p〉

274.某有向圖有28條邊，則其頂點(diǎn)數(shù)最少為o

答案：7</p>

第34/57頁(yè)

275.下圖所示帶權(quán)無(wú)向圖的最小生成樹(shù)的權(quán)為o<imgalt=""

src="/UserFiles/Image/hsm/tt14.png"/>

答案：17</p>

276.

設(shè)待排序數(shù)據(jù)中最大者為2010,則對(duì)基數(shù)為10的基數(shù)排序，需要進(jìn)行趟排序。

答案：4</p>

277.評(píng)價(jià)查找效率的主要標(biāo)準(zhǔn)是。

答案：鍵值比較次數(shù)（或平均查找長(zhǎng)度）</p>

278

排序算法的穩(wěn)定性是指O

答案：對(duì)相同關(guān)鍵字排序前后相對(duì)位置不變</p>

279.

評(píng)價(jià)排序效率的主要標(biāo)準(zhǔn)是O

答案：關(guān)鍵字比較次數(shù)、移動(dòng)次數(shù)</p>

280.用尾指針表示單循環(huán)鏈表的好處是。

答案：找頭、找尾都方便</p>

281.20個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按層序順序存于數(shù)組bt[1..2O]中，則該樹(shù)最底層左邊第一個(gè)結(jié)點(diǎn)

存儲(chǔ)在數(shù)組元素（）中。

答案：bt[16]

282.串“The"含有的子串個(gè)數(shù)為。

答案：7</p>

283.圖的邊集為{<0,1>3,<0,2>5,<0,3>5,<0,4>10,<1,2>4,<2,4>2,<3,4>6>},則從頂點(diǎn)V0到頂

點(diǎn)V4的最短路徑長(zhǎng)度為（）o

答案：7

284.某有向圖的頂點(diǎn)集為{a,b,c,d,e,f},邊集為{<a,c>,<a,e>,<c,f>,<d,c>,<e,b>,<e,d>},則

出度為0的頂點(diǎn)個(gè)數(shù)為（），入度為1的頂點(diǎn)個(gè)數(shù)為（）o

答案:2,4

285.稀疏矩陣的三元組表示中，三元組是指非零元素的、和

三項(xiàng)。

答案：行號(hào)、列號(hào)、值</p〉

286.

兩個(gè)串相等的充分必要條件是兩個(gè)串的長(zhǎng)度相等且O

答案：對(duì)應(yīng)字符相同</p>

287.某二叉樹(shù)中雙分支結(jié)點(diǎn)數(shù)為5個(gè)，單分支結(jié)點(diǎn)數(shù)為4個(gè)，則葉子結(jié)點(diǎn)數(shù)為個(gè)。

答案：6</p>

第35/57頁(yè)

288.可以將排序算法分為：插入排序、、選擇排序、、分配排序。

答案：交換排序、歸并排序</p>

289.n(>l)個(gè)頂點(diǎn)的強(qiáng)連通圖至少條邊，最多條邊。

答案：(spanstyle='font-size:18px'>n、n(n-1)</span></p>

290.順序棧在進(jìn)行運(yùn)算時(shí)，可能發(fā)生棧的上溢，在進(jìn)行運(yùn)算時(shí)，可能

發(fā)生棧的下溢。

答案：進(jìn)棧、退棧</p>

291.算法滿足的五個(gè)重要特性是：、、、輸入、輸出；其中

區(qū)別于程序的地方是o

答案：有窮性、確定性、可行性；有窮性。</p>

292.如果從無(wú)向圖的某個(gè)頂點(diǎn)出發(fā)，進(jìn)行一次廣度優(yōu)先搜索，可訪問(wèn)到圖的每個(gè)頂點(diǎn)，則

該圖一定是圖。

答案：連通</p>

293.快速排序的平均時(shí)間復(fù)雜性為()，最壞時(shí)間復(fù)雜性為()o

答案：O(nlog2n)、O(n2)

294.n個(gè)頂點(diǎn)的無(wú)向圖，最少有條邊，最多有條邊。

答案：(spanstyle='font-size:18px'>0、n(n-1)/2</span></p>

295.若S『"linkedst",S2="ring",則strcat(Sl,S2)的結(jié)果為()。

答案：linkedstring

296.在有向無(wú)環(huán)圖中，若存在一條從頂點(diǎn)i到頂點(diǎn)j的弧，則在頂點(diǎn)的拓?fù)湫蛄兄校旤c(diǎn)i與

頂點(diǎn)j的先后次序是。

答案：i在j之前</p>

297.十字鏈表中的結(jié)點(diǎn)需存儲(chǔ)非零元素的五個(gè)信息：行號(hào)、列號(hào)、值、、o

答案：行指針、列指針</p>

298.對(duì)n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，采用鄰接矩陣和鄰接表表示時(shí)，求任一頂點(diǎn)度數(shù)的時(shí)間

復(fù)雜性分別為和0

答案：〈spanstyle='font-size:18px'>O(n)、O(e/n)</span></p>

299.深度為k的二叉樹(shù)，葉子數(shù)至多為,葉子數(shù)至少為o

答案：<spanstyle-font-size:18px'>2^k-l>l</span></p><br/></p>

300.某哈夫曼樹(shù)有109個(gè)結(jié)點(diǎn)，則其葉子數(shù)是,度為2的結(jié)點(diǎn)數(shù)是

答案：55、54</p>

301.對(duì)400個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，葉子數(shù)為

答案：200</p〉

第36/57頁(yè)

302.散列表既是一種方式又是一種方法。

答案：儲(chǔ)存、查找</p>

303.“就地排序”是指排序算法輔助空間的復(fù)雜度為。

答案：O(l)</p>

304.

設(shè)元素al,a2,a3,a4,a5和a6依次入棧，出棧順序?yàn)閍3,a5,a4,a6,a2,al,則棧的容

量至少為o

答案：4</p>

305.

帶頭結(jié)點(diǎn)的單鏈表L為空的判定條件是o

答案：〈spanstyle='font-size:18px'>L->next==NULL</span></p>

306.

索引順序表上的查找分兩個(gè)階段：、O

答案：索引表查找、塊內(nèi)查找</p>

307.若圖的頂點(diǎn)集為{a,b,c,d,e,f},邊集為{(a,b),(a,c),(b,c),(d,e)},則該圖有()個(gè)連通分量。

答案：3

308.從n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)中查找一個(gè)元素，平均時(shí)間復(fù)雜性大致為o

答案：O(log₂n)</p>

309.某圖所有頂點(diǎn)的度數(shù)之和為200,則邊數(shù)為條。

答案：100</p>

31O.Kruska噂法求最小生成樹(shù)的時(shí)間為，對(duì)圖比較有利。

答案:<spanstyle="font-size:18px'>O(elog₂e)s稀疏</span></p>

311.用head。和tail。函數(shù)表示在廣義表人=9,(*,丫,2),1))中取出原子*的運(yùn)算是：。

答案：<spanstyle='font-size:18px'>head(head(tail(A)))</span></p>

312.

某完全二叉樹(shù)的第5層只有6個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)數(shù)是o

答案：ll</p>

313.將復(fù)雜性O(shè)(n2)、O(nlog2n)>O(2n)從低到高排序，依次為()。

答案:O(nlog2n)>O(n2)>O(2n)

314.非空單循環(huán)鏈表L中結(jié)點(diǎn)*p是尾結(jié)點(diǎn)的條件是o

答案：<spanstyle='font-size:18px'>p->next==L</span></p>

315.在順序表中做插入操作時(shí)首先檢查_(kāi)_____o

答案：上溢或表滿</p>