數(shù)據(jù)結(jié)構(gòu)(習(xí)題)

1.第15題多維數(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

2.第17題3個(gè)結(jié)點(diǎn)可構(gòu)成（）個(gè)不同形態(tài)的二叉樹。

A.2

B.3

C.4

D.5

答案:D

3.第18題二叉樹的葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對次序（）。

A.可能改變

B.一定會(huì)改變

C.一定不改變

D.可能變也可能不變

答案:C

4.第19題以下敘述錯(cuò)誤的是（）。

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

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

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

D.樹的先根序列與對應(yīng).：叉樹的先根序列相同。

答案:C

5.第20題在n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接表中，存放表頭結(jié)點(diǎn)的數(shù)組的

大小為（）。

A.n

B.n+e

C.n+2e

D.e

答案:A

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

A.1

B.n-1

C.n

D.n+1

答案:C

7.第22題給定整數(shù)集合{3,5,6,9,12},與之對應(yīng)的哈夫曼樹是（）。

A.A

B.B

C.C

D.D

答案:C

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

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

B.三元組和散列

C.三元組和十字鏈表

D.散列和十字鏈表

答案:C

9.第40題以下敘述錯(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)系表示出來。

答案:B

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

A.必須連續(xù)

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

C.一定不連續(xù)

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

答案:D

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

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

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

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

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

答案:C

13.第44題下面關(guān)于B樹和B+樹的敘述中，不正確的是

A.都是平衡的多叉樹

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

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

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

答案:D

14.第45題設(shè)計(jì)一個(gè)判斷表達(dá)式中左右括號是否配對出現(xiàn)的算法，采用（）數(shù)

據(jù)結(jié)構(gòu)最好。

A.順序表

B.鏈表

C.隊(duì)列

D.棧

答案:D

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

A.ABCD

B.DCBA

C.任意順序

D.以上都不是

答案:A

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

A.直接插入排序

B.直接選擇排序

C.堆排序

D.快速排序

答案:B

17.第48題對關(guān)鍵字序列（14,5,19,20,11,19）,第一趟排序的結(jié)果為

（14,5,19,20,11,19）,則可能的排序方法是（）。

A.簡單選擇排序

B.快速排序

C.希爾排序

D.二路歸并排序

答案:C

18.第49題某鏈表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除

最后一個(gè)元素，則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。

A.單鏈表

B.雙鏈表

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

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

答案:D

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

A.14

B.13

C.13或14

D.以上都不是

答案:C

20.第51題對有向圖，下面（）種說法是正確的。

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

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

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

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

答案:B

21.第52題在n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中，表示邊存在的元素個(gè)

數(shù)為（）。

A.n

B.n*e

C.e

D.2*e

答案:D

22.第68題線索二叉樹中某結(jié)點(diǎn)沒有左孩子的條件是（）。

A.p!=NULL

B.p->ltag==0

C.p->ltag==l

D.p->Ichild!=NULL

答案:C

24.第70題對n個(gè)結(jié)點(diǎn)的二叉樹，按（）遍歷順序?qū)Y(jié)點(diǎn)編號（號碼為l~n）時(shí),

任一結(jié)點(diǎn)的編號等于其左子樹中結(jié)點(diǎn)的最大編號加1,又等于其右子樹中結(jié)點(diǎn)的

最小編號減lo

A.前根

B.中根

C.后根

D.層次

答案:B

25.第71題要將現(xiàn)實(shí)生活中的數(shù)據(jù)轉(zhuǎn)化為計(jì)算機(jī)所能表示的形式，其轉(zhuǎn)化過程

依次為（）。

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

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

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

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

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

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

答案:C

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

A.不在需要頭指針了

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

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

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

答案:D

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

A.插入

B.刪除

C.串聯(lián)接

D.子串定位

答案:D

29.第75題對n個(gè)元素進(jìn)行快速排序，最壞情況下需要進(jìn)行（）趟。

A）n

B）n-1

C）n/2

D）log2n

A.A

B.B

C.C

D.D

答案:B

30.第76題若要在0（1）的時(shí)間內(nèi)將兩個(gè)循環(huán)鏈表頭尾相接，則應(yīng)對兩個(gè)循環(huán)

鏈表各設(shè)置一個(gè)指針，分別指向（）。

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

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

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

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

答案:B

31.第77題下面的二叉樹中，（）不是完全二叉樹。

A.A

B.B

C.C

D.D

答案:C

32.第78題對n個(gè)頂點(diǎn)的有向圖，若所有頂點(diǎn)的出度之和為s,則所有頂點(diǎn)的

入度之和為（）。

A.s

B.s-1

C.s+1

D.n

答案:A

34.第80題若一個(gè)圖中包含有k個(gè)連通分量，若要按照深度優(yōu)先搜索的方法訪

問所有頂點(diǎn)，則必須調(diào)用（）次深度優(yōu)先搜索遍歷的算法。

A.1

B.k

C.k-1

D.k+1

答案:B

36.第99題若某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和

刪除最后一個(gè)元素，則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。

A.單鏈表

B.雙鏈表

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

D.容量足夠大的順序表

答案:D

37.第100題由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹（）。

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

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

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

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

答案:A

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

A.-ri

B.-2~2

C.「2

D.0~1

答案:A

39.第102題算法分析的目的是（）。

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

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

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

D.分析算法的易讀性

答案:C

40.第103題算法的時(shí)間復(fù)雜度取決于（）。

A.問題的規(guī)模

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

C.A和B

D.以上都不是

答案:C

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

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

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

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

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

答案:C

42.第105題隊(duì)列操作的原則是（）。

A.先進(jìn)先出

B.后進(jìn)先出

C.隊(duì)尾刪除

D.隊(duì)頭插入

答案:A

43.第23題若二叉樹中沒有度為1的結(jié)點(diǎn)，則為滿二叉樹。

答案:錯(cuò)誤

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

答案:錯(cuò)誤

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

答案:錯(cuò)誤

46.第26題不管樹的深度和形態(tài)如何，也不可能構(gòu)造出一棵有100個(gè)結(jié)點(diǎn)的哈

夫曼樹。

答案:正確

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

答案：正確

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

答案:錯(cuò)誤

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

答案：正確

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

答案:正確

51.第31題二分查找所對應(yīng)的判定樹，是一棵理想平衡的二叉排序樹。

答案:正確

52.第32題一維數(shù)組是一種順序表。

答案:正確

53.第33題排序的目的是為了方便以后的查找。

答案:正確

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

答案:正確

55.第35題二叉樹中不可能有兩個(gè)結(jié)點(diǎn)在先根、中根和后根序列中的相對次序

都不變。

答案:錯(cuò)誤

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

答案:錯(cuò)誤

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

答案:錯(cuò)誤

58.第82題二叉樹中可能所有結(jié)點(diǎn)的度都小于20

答案：正確

59.第83題哈夫曼樹中不存在度為1的結(jié)點(diǎn)。

答案:正確

60.第84題開散列表和閉散列表的裝填因子都可大于、等于或小于1。

答案:錯(cuò)誤

61.第85題任何樹或林都可轉(zhuǎn)化為二叉樹，反之，二叉樹可轉(zhuǎn)化為任何樹或林。

答案:錯(cuò)誤

62.第86題在線索二叉樹上，求結(jié)點(diǎn)的（遍歷）前趨和后繼時(shí)可利用線索得到，

即不必進(jìn)行遍歷了。

答案:錯(cuò)誤

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

答案:錯(cuò)誤

64.第88題若算法的復(fù)雜性與數(shù)據(jù)集的狀態(tài)無關(guān)，則最好、最壞和平均復(fù)雜性

是相同的。

答案:正確

65.第89題如果根結(jié)點(diǎn)的左子樹和右子樹高度差不超過1,則該二叉樹是平衡

二叉樹。

答案:錯(cuò)誤

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

答案:正確

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

答案:錯(cuò)誤

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

答案:錯(cuò)誤

69.第93題樹和森林都可轉(zhuǎn)化為二叉樹，故對給定的二叉樹，不能區(qū)分是由樹

還是森林轉(zhuǎn)換來的。

答案:錯(cuò)誤

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

答案:正確

71.第95題每個(gè)節(jié)點(diǎn)一個(gè)鏈域的鏈表是單鏈表，每個(gè)節(jié)點(diǎn)兩個(gè)鏈域的鏈表是雙

鏈表。

答案:錯(cuò)誤

72.第96題設(shè)串的長度為n,則其子串個(gè)數(shù)為n(n+l)/2。

答案:錯(cuò)誤

73.第1題四種基本邏輯結(jié)構(gòu)是：__、____、樹、圖；可把它們分成兩類：

____和____O

答案：

集合、線性；線性、非線性

74.第2題在150個(gè)結(jié)點(diǎn)的有序表中二分法查找，不論成功與否，鍵值比較次

數(shù)最多為__。

答案：

8

75.第3題深度為k的二叉樹，結(jié)點(diǎn)數(shù)至多為一，結(jié)點(diǎn)數(shù)至少為一?

答案：

2-hk

2k-l>k76.第4題由權(quán)值為3,8,6,2,5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的

帶權(quán)路徑長度為__。

答案：

53

77.第5題下面程序段的時(shí)間復(fù)雜性為—o

y=l;

while(y<n)y=y*3;

答案:

0(log3n)

78.第6題對廣義表((x),(a,b)),長度是____,深度是

答案:

2、2

2、279.第7題順序棧在進(jìn)行—運(yùn)算時(shí)，可能發(fā)生棧的上溢，在進(jìn)行

運(yùn)算時(shí)，可能發(fā)生棧的下溢。

答案：

進(jìn)棧、退棧

80.第8題設(shè)循環(huán)隊(duì)列用C語言數(shù)組A[m]表示，front指針指向真正隊(duì)頭的前

一個(gè)位置，rear指針指向真正隊(duì)尾，隊(duì)列中當(dāng)前元素個(gè)數(shù)為n,則

(1)若已知front、rear,貝ljn=。

(2)若已知front、n,則rear=____。

(3)若已知rear、n,則front=。

答案：

n=(rear-front+m)%m

rear=(front+n)%m

front=(rear-n+m)%m

n=(rear-front+m)%m

rear=(front+n)%m

front=(rear-n+m)%m81.第9題n(Nl)個(gè)頂點(diǎn)的強(qiáng)連通圖至少____條邊,

最多——條邊。

答案:

n^n(n-l)

n、n(n-l)82.第10題可以將排序算法分為：插入排序、__、選擇排序、

—、分配排序。

答案：

交換排序、歸并排序

83.第11題設(shè)待排序數(shù)據(jù)中最大者為2010,則對基數(shù)為10的基數(shù)排序，需要

進(jìn)行一趟排序。

答案：

4

84.第12題Kruskal算法求最小生成樹的時(shí)間為____,對____圖比較有利。

答案：

0(elog2e)>稀疏

O(elog,e)>稀疏85.第13題對400個(gè)結(jié)點(diǎn)的完全二叉樹，度為1的結(jié)點(diǎn)數(shù)

為____。

答案：

0

86.第14題數(shù)組中，每個(gè)元素占3個(gè)單元，從首地址SA開始

存放，若該數(shù)組按列存放，則元素A[8][5]的地址是一

答案：

SA+117

SA+11787.第16題下面程序段的時(shí)間復(fù)雜度為__。

y=n；

while(y>1)y=y/2;

答案：

0(log2n)

88.第53題算法評價(jià)一般考慮的四個(gè)方面是：—、可讀性、—、—;其

中在數(shù)據(jù)結(jié)構(gòu)里主要考慮—o

答案：

正確性、健壯性、時(shí)空性能；時(shí)空性能。

89.第54題對廣義表((x),(a,b)),表頭是—，表尾是__。

答案：

(x)、((a,b))

(x)、((a,b))90.第55題若I和0分別表示入棧和出棧，對元素a、b、c、

d、e依次執(zhí)行HOIOHOOO,則棧的容量至少為o

答案：

3

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

答案：

0(log2n)

92.第57題200個(gè)結(jié)點(diǎn)的二叉樹，深度至多為___,深度至少為___o

答案：

200、8

93.第58題頭指針為F、尾指針為R、帶頭結(jié)點(diǎn)的鏈隊(duì)列為空的條件是一一o

答案：

R==F

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

答案：

100

95.第60題n個(gè)頂點(diǎn)的無向圖，最少有__條邊，最多有____條邊。

答案：

0、n(n-l)/2

0、n(n-l)/296.第61題某樹所有結(jié)點(diǎn)的度數(shù)之和為100,則樹中邊數(shù)為

答案:

100

97.第62題在有向無環(huán)圖中，若存在一條從頂點(diǎn)i到頂點(diǎn)j的弧，則在頂點(diǎn)的

拓?fù)湫蛄兄?，頂點(diǎn)i與頂點(diǎn)j的先后次序是____。

答案：

i在j之前

98.第63題所有基于比較的排序方法，平均時(shí)間復(fù)雜性最好時(shí)為__o

答案：

O(nlog2n)

99.第64題樹的三種主要的遍歷方法是：__、__和層次遍歷。

答案：

先根、后根

100.第65題稀疏矩陣的三元組表示中，三元組是指非零元素的__、__和

__三項(xiàng)。

答案：

行號、列號、值

101.第66題算法滿足的五個(gè)重要特性是：__、—、―、輸入、輸出；

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

答案：

有窮性、確定性、可行性；有窮性。

102.第67題下面程序段的時(shí)間復(fù)雜性為

for(i=0;i<n;i++)

for(j=0;j<i;j++)

A[i][j]=O；

答案：

0(n2)

103.第38題設(shè)計(jì)遞歸算法，判斷二叉樹t中是否所有結(jié)點(diǎn)都為正數(shù)。

二叉鏈表的類型定義如下：

typedefintdatatype;//結(jié)點(diǎn)的數(shù)據(jù)類型，假設(shè)為int

typedefstructNODE*pointer;//結(jié)點(diǎn)指針類型

structNODE{

datatypedata;

pointerIchild,rchild;

}；

typedefpointerbitree;//根指針類型

答案：

intdetect(bitreet){

intLzR;

if(t==NULL)return1;

if(t->data<=0)return0;

returndetect(t->lchild)&&detect(t->rchild);

104.第97題設(shè)計(jì)算法將順序表L中所有的負(fù)數(shù)都移動(dòng)到表的前端，要求移動(dòng)

次數(shù)盡量少。

順序表類型定義如下：

typedefintdatatype;//結(jié)點(diǎn)的數(shù)據(jù)類型，假設(shè)為int

constintmaxsize=100;//最大表長，假設(shè)為100

typedefstruct{

datatypedata[maxsize];//線性表的存儲(chǔ)向量，第一個(gè)結(jié)點(diǎn)是

data[0]

intn;//線性表的當(dāng)前長度

}sqlist;//順序表類型

答案：

voidmoves(sqlist*L){

inti,j;datatypex;

i=l;j=L->n;

while(i<j){

while(L->data[i]<0&&i<j)i++;

while(L->data[j]>=0&&i<j)j--;

if(i<j){

x=L->data[i];L->data[i]=L一〉data[j];L->data[j]=x;

i++；j一；

}

}

)

105.第98題設(shè)計(jì)遞歸算法，判斷二叉樹t是否滿足小根堆的特點(diǎn)。二叉鏈表

的類型定義如下：

typedefintdatatype;//結(jié)點(diǎn)的數(shù)據(jù)類型，假設(shè)為int

typedefstructNODE*pointer;//結(jié)點(diǎn)指針類型

structNODE{

datatypedata;

pointerIchild,rchild;

)；

typedefpointerbitree;//根指針類型

答案：

intdetect(bitreet){

if(t==NULL)return1;//空樹看成真

if((t->lchild!=NULL&&t->1child->data>t-data),,

(t->rchild!=NULL&&t->rchild->data>t-data))

return0;//左孩子＞根，或右孩子〉根，為假

else

returndetect(t->rchild)&&detect(t->rchild);

)

1.第12題在下列排序方法中，空間復(fù)雜性為O（logzn）的方法為（）。

A.直接選擇排序

B.歸并排序

C.堆排序

D.快速排序

答案:D

2.第13題二叉樹的結(jié)構(gòu)如下圖所示，其中序遍歷的序列為（）。

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

3.第14題算法的時(shí)間復(fù)雜度取決于（）。

A.問題的規(guī)模

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

C.A和B

D.以上都不是

答案:C

4.第15題若某線性表中最常用的操作是在最后■■個(gè)元素之后插入一個(gè)元素和

刪除最后一個(gè)元素，則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。

A.單鏈表

B.雙鏈表

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

D.容量足夠大的順序表

答案:D

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

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

B.三元組和散列

C.三元組和十字鏈表

D.散列和十字鏈表

答案:C

7.第18題下圖是一棵（）。

1102228」

|0510H151922H2628I

A,4階B-樹

B.4階B+樹

C.3階B-樹

D.3階B+樹

答案:D

8.第19題串是一種（）線性表。

A.長度受限

B.元素類型受限

C.操作受限

D.一般

答案:B

9.第20題在散列查找中，平均查找長度主要與（）有關(guān)。

A.散列表長度

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

C.裝填因子

D.處理沖突方法

答案:C

10.第21題（）存儲(chǔ)方式適用于折半查找。

A.鍵值有序的單鏈表

B.鍵值有序的順序表

C.鍵值有序的雙鏈表

D.鍵值無序的順序表

答案:B

11.第22題若要在0（1）的時(shí)間內(nèi)將兩個(gè)循環(huán)鏈表頭尾相接，則應(yīng)對兩個(gè)循環(huán)

鏈表各設(shè)置一個(gè)指針，分別指向（）。

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

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

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

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

答案:B

12.第23題下圖所示二叉樹對應(yīng)的森林中有（）棵樹。

A.1

B.2

C.3

D.不確定

答案:C

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

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

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

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

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

答案:A

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

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

B.最小生成樹算法

C.最短路徑算法

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

答案:D

15.第47題時(shí)間復(fù)雜性為O（nlogzn）且空間復(fù)雜性為0（1）的排序方法是（）。

A.歸并排序

B.堆排序

C.快速排序

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

答案:B

17.第49題以下敘述錯(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)系表示出來。

答案:B

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

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

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

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

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

答案:A

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

A.入隊(duì)

B.出隊(duì)

C.取隊(duì)頭元素

D.取隊(duì)尾元素

答案:B

21.第53題設(shè)S="abc"；T="xyz”,則strcmp⑸T）的值為（）。

A.正數(shù)

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

C.零

D.不確定

答案:B

22.第54題若要從1000個(gè)元素中得到2個(gè)最小值元素,最好采用（）方法。

A.直接插入排序

B.直接選擇排序

C.堆排序

D.快速排序

答案:B

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

A.14

B.13

C.13或14

D.以上都不是

答案:C

25.第66題圖的深度遍歷必須借助（）作為輔助空間。

棧

列

A.隊(duì)

找

查

RC.表

組

數(shù)

D.案

答:A

26.第67題要解決散列引起的沖突問題，常米用的方法有（）。

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

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

C.二次探測法、平方取中法

D.二次探測法、鏈地址法

答案:D

27.第68題對n個(gè)元素進(jìn)行冒泡排序，最好情況下的只需進(jìn)行（）對相鄰元素

之間的比較。

A.n

B.n-1

C.n+1

D.n/2

答案:B

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

入

插

擇

A.選

B.希

C爾

快

D.速

答

案

:D

30.第82題樹結(jié)構(gòu)最適合用來表示（）。

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

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

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

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

答案:C

31.第83題下列敘述錯(cuò)誤的是()。

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

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

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

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

答案:D

32.第84題基數(shù)排序中的“基數(shù)”可以是()。

A.10

B.8

C.16

D.以上都可以

答案:D

33.第85題

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

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

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

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

答案:D

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

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

B.常?？蔂奚臻g性能換取時(shí)間性能

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

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

答案:D

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

A0(n)和0(1)

B.0⑴和0(1)

C.0⑴和0(n)

D.0(n)和0(n)

答案:C

36.第88題在AVL樹中，任一結(jié)點(diǎn)的（）。

A.左、右子樹的高度均相同

B.左、右子樹高度差的絕對值不超過1

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

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

答案:B

37.第89題下列哪種情況需要遇到隊(duì)列（）。

A.迷宮求解

B.括號匹配

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

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

答案:D

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

于數(shù)據(jù)的個(gè)數(shù)n。

A.二叉查找樹

B.鏈表

C.散列表

D.順序表

答案:C

39.第91題假設(shè)某完全二叉樹順序存儲(chǔ)在數(shù)組BT[m]中，其中根結(jié)點(diǎn)存放在

BT[0],若BT[i]中的結(jié)點(diǎn)有左孩子，則左孩子存放在（）。

A.BT[i/2]

B.BT[2*i-l]

C.BT[2*i]

D.BT[2*i+l]

答案:B

40.第92題在n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接表中，邊結(jié)點(diǎn)的個(gè)數(shù)為（）。

A.n

B.n*e

C.e

D.2*e

答案:D

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

A.1

B.n-1

C.n

D.n+1

答案:C

42.第98題用鏈表表示線性表的優(yōu)點(diǎn)是()。

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

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

C.便于插入和刪除

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

答案:C

43.第26題由二叉樹的先根和后根序列可以唯一確定該二叉樹。

答案:錯(cuò)誤

44.第27題在開散列表中不會(huì)出現(xiàn)堆積現(xiàn)象。

答案:正確

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

答案:錯(cuò)誤

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

答案:正確

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

答案:正確

50.第33題連通圖的BFS生成樹一般比DFS生成樹的高度小。

答案：正確

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

答案:錯(cuò)誤

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

答案:正確

53.第70題哈夫曼樹中不存在度為1的結(jié)點(diǎn)。

答案:正確

54.第71題開散列表和閉散列表的裝填因子都可大于、等于或小于1。

答案:錯(cuò)誤

55.第72題算法的正確性，一般不進(jìn)行形式化的證明，而是用測試來驗(yàn)證。

答案:正確

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

答案:正確

57.第74題對稱矩陣壓縮存儲(chǔ)后仍然可以隨機(jī)存取。

答案：正確

59.第76題基數(shù)排序不需進(jìn)行關(guān)鍵字間的比較，故執(zhí)行時(shí)間比基于比較的排序

方法要快。

答案:錯(cuò)誤

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

答案:錯(cuò)誤

61.第78題滿二叉樹是一種特殊的完全二叉樹。

答案:正確

62.第79題線性表、樹、圖等都可以用廣義表表示。

答案:正確

63.第94題若二叉樹中沒有度為1的結(jié)點(diǎn)，則為滿二叉樹。

答案:錯(cuò)誤

64.第95題消除遞歸不一定需要使用棧。

答案:正確

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

答案:錯(cuò)誤

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

答案:錯(cuò)誤

68.第100題稀疏矩陣就是矩陣的元素很少。

答案:錯(cuò)誤

69.第101題圖G的生成樹T是G的子圖。

答案:正確

70.第102題不是所有的有向圖都可以進(jìn)行拓?fù)渑判?，而能拓?fù)渑判驎r(shí)、結(jié)果

不一定唯一。

答案:正確

71.第103題堆排序是一種巧妙的樹型選擇排序。

答案：正確

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

___________O

答案：

0(log2n)

74.第2題設(shè)循環(huán)鏈隊(duì)列的長度為n,若只設(shè)尾指針，則出隊(duì)和入隊(duì)的時(shí)間復(fù)

雜度分別是—和—。

答案：

0(1)、0(1)

。(1)、0(1)75.第3題200個(gè)結(jié)點(diǎn)的二叉樹，深度至多為，深度至少為

答案:

200、8

76.第4題線索二叉樹中，線索的含義是___0

答案：

某種遍歷的前趨或后繼信息

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

、__O

答案：

行指針、列指針

78.第6題用尾指針表示單循環(huán)鏈表的好處是—o

答案：

找頭、找尾都方便

79.第7題n(21)個(gè)頂點(diǎn)的強(qiáng)連通圖至少一—條邊，最多___條邊。

答案：

n、n(n-l)

n、n(n1)80.第8題在鄰接矩陣和鄰接表上對圖進(jìn)行BFS或DFS遍歷時(shí)，時(shí)

間復(fù)雜性分別為__、——o

答案:

0(r?)、O(n+e)

0(n?)、O(n+e)81.第9題將長度為2n和n的有序表歸并成一個(gè)有序表，至

少進(jìn)行一次鍵值比較。

答案：

n

82.第10題對n個(gè)頂點(diǎn)和e條邊的圖，采用鄰接矩陣和鄰接表表示時(shí)，空間復(fù)

雜性分別為—和—。

答案：

0(r?)、0(n+e)

O(rT)、O(n+e)83.第11題對n個(gè)結(jié)點(diǎn)的線索二叉樹，線索有一個(gè)。

答案：

n+1

n+184.第37題散列表既是一種——方式又是一種___方法。

答案：

儲(chǔ)存、查找

85.第38題串“The”含有的子串個(gè)數(shù)為

答案:

7

86.第39題運(yùn)算定義在邏輯結(jié)構(gòu)上，算法定義在—結(jié)構(gòu)上；運(yùn)算指出“做什

么”，算法指出__。

答案：

儲(chǔ)存；怎么做

87.第40題對廣義表L=((a,b),c,d)進(jìn)行操作head(tailQ))的結(jié)果是：__。

答案：

C88.第41題在鏈表的結(jié)點(diǎn)中，數(shù)據(jù)元素所占的存儲(chǔ)量和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)

量之比稱作____o

答案：

儲(chǔ)存密度

89.第42題Prim算法求最小生成樹的時(shí)間為—，對__圖比較有利。

答案：

0(/)、稠密

0(/)、稠密90.第43題在順序表中做插入操作時(shí)首先檢查

答案：

上溢或表滿

91.第44題排序算法的穩(wěn)定性是指__。

答案：

對相同關(guān)鍵字排序前后相對位置不變

92.第45題圖的DFS遍歷類似樹的—_遍歷，是其推廣。

答案：

先根

93.第46題程序設(shè)計(jì)的實(shí)質(zhì)是：數(shù)據(jù)的表示和__,或者說，程序=數(shù)據(jù)結(jié)構(gòu)

+。

答案：

數(shù)據(jù)的處理；算法

94.第55題散列表的沖突處理方法有___和兩種，對應(yīng)的散列表分別稱為

開散列表和閉散列表。

答案：

開放地址法、鏈地址法（或拉鏈法）

95.第56題對400個(gè)結(jié)點(diǎn)的完全二叉樹，葉子數(shù)為o

答案：

200

96.第57題算法評價(jià)一般考慮的四個(gè)方面是：__、可讀性、__、—；其

中在數(shù)據(jù)結(jié)構(gòu)里主要考慮—。

答案：

正確性、健壯性、時(shí)空性能；時(shí)空性能。

97.第58題設(shè)循環(huán)隊(duì)列用C語言數(shù)組A[m]表示，front指針指向真正隊(duì)頭的前

一個(gè)位置，rear指針指向真正隊(duì)尾，隊(duì)列中當(dāng)前元素個(gè)數(shù)為n,則

(1)若已知front、rear,貝n=。

(2)若已知front、n,則rear=。

(3)若已知rear、n,則front=。

答案：

n=(rear-front+m)%m

rear=(front+n)%m

front=(rear-n+m)%m

n=(rear-front+m)%m

rear=(front+n)%m

front=(rear-n+m)%m98.第59題某無向圖有28條邊，則其頂點(diǎn)數(shù)最少

為____。

答案:

8

99.第60題圖的BFS遍歷類似樹的__遍歷，是其推廣。

答案：

層次

100.第61題所仃基于比較的排序方法，平均時(shí)間復(fù)雜性最好時(shí)為

答案：

0(nlog2n)

101.第62題n個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí)，該矩陣至少有____個(gè)非零

元素。

答案：

2(n-l)

102.第63題若有向圖有2個(gè)有向回路，則其拓?fù)湫蛄杏衉_個(gè)。

答案：

0

103.第36題設(shè)計(jì)算法將順序表L中所有的小寫字符都移動(dòng)到表的前端，要求

元素的移動(dòng)次數(shù)盡量少。

順序表類型定義如下：

typedefchardatatype;//結(jié)點(diǎn)的數(shù)據(jù)類型，假設(shè)為char

constintmaxsize=100;//最大表長，假設(shè)為100

typedefstruct{

datatypedata[maxsize];//線性表的存儲(chǔ)向量，第一個(gè)結(jié)點(diǎn)是

data[0]

intn;//線性表的當(dāng)前長度

}sqlist;//順序表類型

答案：

voidmoves(sqlist*L){

inti,j;datatypex;

i=l;j=L->n;

while(i<j){

while((L->data[i]>='a'&&L->data[i]<='z')&&i<j)i++;

while((L->data[j]<fa!,,L->data[i]>*z*)&&i<j)j--;

if(i<j){

x=L->data[i];L->data[i]=L->data[j];L->data[j]=x;

i++；j——；

104.第80題設(shè)計(jì)遞歸算法，求二叉排序樹t的葉子數(shù)。二叉鏈表的類型定義

如下：

typedefintdatatype;//結(jié)點(diǎn)的數(shù)據(jù)類型，假設(shè)為int

typedefstructNODE*pointer;//結(jié)點(diǎn)指針類型

structNODE{

datatypedata;

pointerIchild,rchild;

}；

typedefpointerbitree;//根指針類型

答案：

intleaf(bitreet){

intL,R;

if(t==NULL)return0;

if(t->child==NULL&&t->rchild==NULL)return1;

L=leaf(t->lchild);

R=leaf(t->rchild);

returnL+R;

105.第105題設(shè)計(jì)一個(gè)遞歸算法，求二叉樹t中度為1的結(jié)點(diǎn)數(shù)。設(shè)二叉鏈表

類型定義如下。

typedefintdatatype;//結(jié)點(diǎn)的數(shù)據(jù)類型，假設(shè)為int

typedefstructNODE*pointer;//結(jié)點(diǎn)指針類型

structNODE{

datatypedata;

pointerIchild,rchild;

};

typedefpointerbitree;//根指針類型

答案：

intsuml(bitreet){

intL,R;

if(t==NULL)return0;

L=suml(t->lchild);

R=suml(t->rchild);

if((t->lchild==NULL&&t->rchild!=NULL),,

(t->lchild!=NULL&&t->rchild==NULL))

returnL+R+l;

else

returnL+R;

)

2.第13題設(shè)輸入序列為A,B,C,D,借助一個(gè)隊(duì)列得到的輸出序列可能是()。

A.ABCD

B.DCBA

C.任意順序

D.以上都不是

答案:A

3.第14題串是一種（）線性表。

A.長度受限

B.元素類型受限

C.操作受限

D.一般

答案：B

4.第15題若下圖表示某廣義表，則它是一種（）。

A.線性表

B.純表

C.再入表

D.遞歸表

答案:B

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

A.直接插入排序

B.直接選擇排序

C.堆排序

D.快速排序

答案:B

7.第18題關(guān)鍵字比較次數(shù)與數(shù)據(jù)的初始狀態(tài)無關(guān)的排序算法是（）。

A.直接選擇排序

B.冒泡排序

C.直接插入排序

D.希爾排序

答案:A

8.第19題對關(guān)鍵字序列（14,5,19,20,11,19）,第一趟排序的結(jié)果為

（14,5,19,20,11,19）,則可能的排序方法是（）。

A.簡單選擇排序

B.快速排序

C.希爾排序

D.二路歸并排序

答案:C

9.第20題對n個(gè)元素進(jìn)行冒泡排序，最好情況下的只需進(jìn)行（）對相鄰元素之

間的比較。

A.n

B.n-1

C.n+1

D.n/2

答案:B

10.第21題若某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和

刪除第一個(gè)元素，則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。

A.單鏈表

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

C.雙鏈表

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

答案:D

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

A.都連通的無向圖

B.都不連通的無向圖

C.都連通的有向圖

D.都不連通的有向圖

答案:A

13.第38題如果某圖的鄰接矩陣是對角線元素均為零的上三角矩陣，則此圖是

（）o

A.有向完全圖

B.連通圖

C.強(qiáng)連通圖

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

答案:D

14.第39題圖的深度遍歷必須借助（）作為輔助空間。

A棧

.

隊(duì)

列

民

查

表

C找

D數(shù)

.組

案

生

口:A

16.第47題樹結(jié)構(gòu)最適合用來表示（）。

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

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

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

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

答案:C

17.第48題對n個(gè)結(jié)點(diǎn)的二叉樹，按（）遍歷順序?qū)Y(jié)點(diǎn)編號（號碼為廣n）

時(shí)，任一結(jié)點(diǎn)的編號等于其左子樹中結(jié)點(diǎn)的最大編號加1,又等于其右子樹中結(jié)

點(diǎn)的最小編號減1。

前

A根

?

中

B根

?

后

c根

?

D層

?次

凄

筆xh"

rl:B

18.第49題算法分析是指（）。

A.分析算法的正確性

B.分析算法的可讀性

C.分析算法的健壯性

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

答案:D

19.第50題下列有關(guān)線性表的敘述中，正確的是（）。

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

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

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

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

答案:A

22.第68題多維數(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

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

A.起泡排序

B.希爾排序

C.堆排序

D.快速排序

答案:D

24.第70題已知森林F={T1,T2,T3},各棵樹Ti（i=l,2,3）中所含結(jié)點(diǎn)的個(gè)

數(shù)分別為7,3,5,則與F對應(yīng)的二叉樹的右子樹中的結(jié)點(diǎn)個(gè)數(shù)為（）。

A.10

B.12

C.8

D.15

答案:C

25.第71題以下關(guān)于算法敘述不正確的是（）。

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

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

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

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

答案:D

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

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

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

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

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

答案:A

27.第73題若某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和

刪除最后一個(gè)元素，則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。

A.單鏈表

B.雙鏈表

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

D.容量足夠大的順序表

答案:D

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

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

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

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

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

答案:C

29.第75題隊(duì)列操作的原則是（）。

A.先進(jìn)先出

B.后進(jìn)先出

C.隊(duì)尾刪除

D.隊(duì)頭插入

答案:A

30.第76題下列哪種情況需要遇到隊(duì)列（）。

A.迷宮求解

B.括號匹配

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

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

答案:D

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

A.插入

B.刪除

C.串聯(lián)接

D.子串定位

答案:D

32.第78題二叉樹的葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對次序（）。

A.可能改變

B.一定會(huì)改變

C.一定不改變

D.可能變也可能不變

答案:C

33.第79題

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

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

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

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

答案:D

34.第80題希爾排序的增量序列必須是（）。

A.遞增的

B.隨機(jī)的

C.遞減的

D.任意的

答案:C

35.第81題假定有k個(gè)關(guān)鍵字互為同義詞，若用線性探測法把這k個(gè)關(guān)鍵字存

入散列表中，至少要進(jìn)行（）次探側(cè)。

A.k-1

B.k

C.k+1

D.k（k+l）/2

答案:D

36.第82題在下列排序方法中，空間復(fù)雜性為0（n）的方法為（）。

A.快速排序

B.直接插入排序

C.堆排序

D.歸并排序

答案:D

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

A.快速排序

B.直接插入排序

C.堆排序

D.歸并排序

答案:C

38.第84題下面關(guān)于線性表的敘述錯(cuò)誤的是（）。

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

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

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

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

答案:B

39.第85題在有頭結(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

40.第86題對n個(gè)頂點(diǎn)的有向圖，若所有頂點(diǎn)的出度之和為s,則所有頂點(diǎn)的

入度之和為（）。

A.s

B.s-1

C.s+1

D.n

答案:A

41.第87題在n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接表中，存放表頭結(jié)點(diǎn)的數(shù)組的

大小為（）。

A.n

B.n+e

C.n+2e

D.e

答案:A

42.第88題若有向圖的鄰接矩陣中，主對角線以下的元素均為零，則該圖的拓

撲有序序列()。

A.存在

B.不存在

C.不確定

答案:B

43.第24題哈夫曼樹中不存在度為1的結(jié)點(diǎn)。

答案:正確

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

答案:正確

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

答案:錯(cuò)誤

48.第29題順序查找法不僅可用于順序表上的查找，也可用于鏈表上的查找。

答案:正確

49.第30題廣義表不僅是線性表的推廣，也是樹的推廣。

答案:正確

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

答案:正確

51.第32題有時(shí)冒泡排序的速度會(huì)快過快速排序。

答案:正確

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

答案:正確

54.第35題二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2。

答案:錯(cuò)誤

55.第36題二叉樹中不可能有兩個(gè)結(jié)點(diǎn)在先根、中根和后根序列中的相對次序

都不變。

答案:錯(cuò)誤

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

答案:錯(cuò)誤

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

答案:錯(cuò)誤

59.第90題在二叉排序樹中，即使刪除一個(gè)結(jié)點(diǎn)后馬上再插入該結(jié)點(diǎn)，該二叉

排序樹的形態(tài)也可能不同。

答案:正確

60.第91題循環(huán)隊(duì)列中入隊(duì)和出隊(duì)的節(jié)點(diǎn)位置可出現(xiàn)在數(shù)組的任一端，已不滿

足”一端進(jìn)另一端出”的要求，故實(shí)際上已不是隊(duì)列了。

答案:錯(cuò)誤

61.第92題不可能有二叉樹的任何遍歷次序是相同的。

答案:錯(cuò)誤

62.第93題將樹轉(zhuǎn)化為二叉樹后，原樹中的葉子結(jié)點(diǎn)在二叉樹中不一定也是葉

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

答案:正確

63.第94題順序表可以按序號隨機(jī)存取。

答案:正確

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

答案:正確

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

答案:錯(cuò)誤

67.第98題在A0E網(wǎng)中關(guān)鍵路徑最多只有一條。

答案:錯(cuò)誤

68.第99題滿二叉樹是一種特殊的完全二叉樹。

答案：正確

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

答案:正確

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

于第i列中1的個(gè)數(shù)。

答案:錯(cuò)誤

73.第1題在鏈表的結(jié)點(diǎn)中，數(shù)據(jù)元素所占的存儲(chǔ)量和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)量

之比稱作____o

答案：

儲(chǔ)存密度

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

答案：

p->next==L

p->next==L75.第3題散列表既是一種—方式又是一種__方法。

答案：

儲(chǔ)存、查找

76.第4題頭指針為F、尾指針為R、帶頭結(jié)點(diǎn)的鏈隊(duì)列為空的條件是__。

答案：

R==F

77.第5題在一個(gè)雙鏈表中刪除指針p所指結(jié)點(diǎn)，可執(zhí)行以下操作：

p->next->prior=____；p->prior->next=____；____；

答案：

p、p、deletep

p>p、deletep78.第6題內(nèi)排序是指。

答案：

數(shù)據(jù)全部在內(nèi)存中進(jìn)行排序

79.第7題所有基于比較的排序方法，平均時(shí)間復(fù)雜性最好時(shí)為—o

答案：

0(nlog2n)

80.第8題n(21)個(gè)頂點(diǎn)的強(qiáng)連通圖至少條邊，最多___條邊。

答案：

n、n(n-l)

n、n(n-l)81.第9題n個(gè)頂點(diǎn)的無向圖，最少有__條邊，最多有____條邊。

答案：

0、n(n-l)/2

0、n(n-l)/282.第10題在有向無環(huán)圖中，若存在一條從頂點(diǎn)i到頂點(diǎn)j的

弧，則在頂點(diǎn)的拓?fù)湫蛄兄?，頂點(diǎn)i與頂點(diǎn)j的先后次序是—o

答案：

i在j之前

83.第11題圖的DFS遍歷類似樹的一遍歷，是其推廣。

答案：

先根

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

點(diǎn)數(shù)為____個(gè)。

答案：

6

85.第43題數(shù)組A[L.8][L.1O]中,每個(gè)元素占3個(gè)單元，從首地址SA開始

存放，若該數(shù)組按列存放，則元素A[8][5]的地址是__

答案：

SA+117

SA+11786.第44題四種基本邏輯結(jié)構(gòu)是：___、—一、樹、圖；可把它們分

成兩類：____和____o

答案：

集合、線性；線性、非線性

87.第45題n個(gè)結(jié)點(diǎn)的二叉鏈表中，指針總數(shù)為個(gè)，其中個(gè)指針為空。

答案：

2n、n+1

2n、n+188.第53題從n個(gè)結(jié)點(diǎn)的二叉排序樹中查找一個(gè)元素，平均時(shí)間復(fù)

雜性大致為—o

答案：

O(log2n)

89.第54題對廣義表((x),(a,b)),長度是,深度是___。

答案：

2、2

2、290.第55題用尾指針表示單循環(huán)鏈表的好處是__。

答案：

找頭、找尾都方便

91.第56題帶頭結(jié)點(diǎn)的循環(huán)單鏈表L為空的條件分別是_一。

答案：

L->next==L或L->prior==L

L->next==L或L->prior==L92.第57題在帶頭結(jié)點(diǎn)的單鏈表L中，若

要?jiǎng)h除第一個(gè)結(jié)點(diǎn)，則需執(zhí)行下列三條語句：

____；L->next=p->next；deletep；

答案：

p=L->next

p=L->next93.第58題某圖所有頂點(diǎn)的度數(shù)之和為200,則邊數(shù)為__條。

答案：

100

94.第59題對n個(gè)頂點(diǎn)和e條邊的無向圖，采用鄰接矩陣和鄰接表表示時(shí)，求

任一頂點(diǎn)度數(shù)的時(shí)間復(fù)雜性分別為—和—o

答案：

O(n)>0(e/n)

0(n)、0(e/n)95.第60題在順序表中做插入操作時(shí)首先檢查__。

答案：

上溢或表滿

96.第61題在堆排序的過程中，對n個(gè)記錄