您的本次作業(yè)分?jǐn)?shù)為：99分

1.【第1章第2節(jié)】數(shù)據(jù)結(jié)構(gòu)課程重要研究以下三方面的內(nèi)容，它們是。

「A數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型

"B數(shù)據(jù)元素、數(shù)據(jù)類型、算法實(shí)現(xiàn)

「C數(shù)據(jù)元素、數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

④D數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算

對的答案：D

2.【第1章第2節(jié)】在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的結(jié)構(gòu)。

「A存儲(chǔ)

「B物理

‘C邏輯

「D物理與存儲(chǔ)

對的答案：C

3.【第1章第2節(jié)】邏輯結(jié)構(gòu)相同時(shí)物理結(jié)構(gòu)也應(yīng)當(dāng)相同。

「對的?錯(cuò)誤

4.【第1章第3節(jié)】計(jì)算機(jī)算法是指o

「A計(jì)算方法

B排序方法

rC調(diào)度方法

,*D解決問題的有限運(yùn)算序列

對的答案：D

5.【第1章第3節(jié)】設(shè)某二維數(shù)組AEl..n,l.m],則在該數(shù)組中用順序查找法查找一個(gè)元

素的時(shí)間復(fù)雜性的量級(jí)為.

A0(log2n)

'BO(n)

「C0(nlog2n)

⑤DO(M2)

對的答案:D

6.【第1章第3節(jié)】所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界

行對的「錯(cuò)誤

對的答案：對

7.【第3章第2節(jié)】向一個(gè)有115個(gè)元素的順序表中插入一個(gè)新元素并保持本來順序不變,

平均要移動(dòng)個(gè)元素。

「A115

CB114

口C58

「D57

對的答案:C

8.【第3章第2節(jié)】在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中，插入一個(gè)新的結(jié)點(diǎn)并使之仍然有

序的時(shí)間復(fù)雜度是.

行AO(n)

BO(log2n)

「C0(1)

'DO(nA2)

對的答案:A

9.【第3章第2節(jié)】若規(guī)定能快速地實(shí)現(xiàn)在鏈表的末尾插入和刪除結(jié)點(diǎn)的運(yùn)算，則選擇—

最合適。

A單鏈表

"B帶尾指針的單循環(huán)鏈表

「C雙鏈表

,D雙循環(huán)鏈表

對的答案:B

10.【第3章第2節(jié)】在長度為n的雙鏈表中某結(jié)點(diǎn)(已知其地址)之前，插入一個(gè)新結(jié)點(diǎn)的

時(shí)間復(fù)雜度是。

1AO(n)

「BO(log2n)

RCO(1)

CDO(n八2)

對的答案:C

11.【第3章第2節(jié)】在一個(gè)長度為n的順序表中，在第i個(gè)元素(l<=i<=n)之前插入一

個(gè)新元素時(shí)需向后移動(dòng)個(gè)元素。

「A1

「Bn-i

CCn-i-1

仃Dn-i+1

對的答案：D

12.【第3章第2節(jié)】對順序存儲(chǔ)的線性表，設(shè)其長度為n，且在任何位置上插入或刪除操作

都是等概率的。則插入一個(gè)元素時(shí)平均要移動(dòng)表中的個(gè)元素。

6An/2

CB(n+1)/2

C(n-1)/2

,Dn

對的答案：A

13.【第3章第2節(jié)】順序表的特點(diǎn)是o

1A邏輯上相鄰的結(jié)點(diǎn)其物理位置不相鄰

GB邏輯上相鄰的結(jié)點(diǎn)其物理位置亦相鄰

「C順序表不是隨機(jī)存儲(chǔ)結(jié)構(gòu)

CD在順序表中插入和刪除操作比在鏈表上方便

14.【第3章第2節(jié)】帶頭結(jié)點(diǎn)的單鏈表Head為空表的鑒定條件是

AHead—>next==Head

5*BHead->next==NULL

rCHead!=NULL

「DHead==NULL

對的答案:B

15.【第3章第2節(jié)】線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址。

「A必須是連續(xù)的

'-B必須是不連續(xù)的

尸C連續(xù)與否均可

「D部分地址必須是連續(xù)的

對的答案:C

16.【第3章第2節(jié)】鏈表不具有的特點(diǎn)是o

CA可隨機(jī)訪問任一元素

CB插入和刪除不需要移動(dòng)元素

C不必事先估計(jì)存儲(chǔ)空間

'D所需空間和線性表長度成正比

對的答案:A

17.【第3章第2節(jié)】線性表按鏈?zhǔn)椒绞酱鎯?chǔ)時(shí),每個(gè)結(jié)點(diǎn)的存儲(chǔ)涉及兩部分。

「A數(shù)據(jù)值與符號(hào)

3B數(shù)據(jù)與指針

「C數(shù)據(jù)與表名

「D數(shù)據(jù)項(xiàng)與符號(hào)

對的答案:B

18.【第3章第2節(jié)】在n個(gè)元素的順序表中刪除第i個(gè)元素，需要移動(dòng)n-i個(gè)元素。

份對的「錯(cuò)誤

對的答案：對

19.【第3章第3節(jié)】一個(gè)棧的進(jìn)棧序列是a,b,c,d,e,則棧的不也許的出棧序列是

Aedcba

'?Bdceab

'Cdecba

Dabcde

對的答案:B

20.【第3章第3節(jié)】棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是o

「A線性存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu)

「B散列方式和索引方式

「C鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組

；D線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)

對的答案:D

21.【第3章第3節(jié)】當(dāng)字符序列x5y作為字符堆棧的輸入時(shí)，輸出長度為3的且可以

作為C語言標(biāo)記符的個(gè)數(shù)是一。

6A3個(gè)

「B4個(gè)

「C5個(gè)

“D6個(gè)

對的答案：A

22.【第3章第3節(jié)】一個(gè)棧的入棧序列是a,b,c,d,則下列序列中不也許的輸出序列是

_______O

「Aacbd

Bdcba

「Cacdb

：*Ddbac

對的答案:D

23.【第3章第3節(jié)】作進(jìn)棧操作時(shí)，應(yīng)先判斷棧是否為。

「A空

B滿

「C上溢

一D下溢

對的答案:B

24.【第3章第3節(jié)】若某堆棧的輸入序列為1,2,3,…,n—l,n,輸出序列的第1個(gè)元素為

n,則第i個(gè)輸出元素為。

⑥An-i+1

Bn-i

Ci

'D哪個(gè)元素?zé)o所謂

對的答案:A

25.【第3章第3節(jié)】采用不帶尾指針的單鏈表方式表達(dá)一個(gè)棧，便于結(jié)點(diǎn)的插入與刪除。

棧頂結(jié)點(diǎn)的插入與刪除通常在鏈表的進(jìn)行。

「A任意位置

「B鏈表頭尾兩端

C鏈表頭一端

「D鏈表尾一端

對的答案:C

26.【第3章第3節(jié)】判斷順序儲(chǔ)存下堆棧s是空的條件是s.top==0。

⑤對的「錯(cuò)誤

對的答案：對

27.【第3章第4節(jié)】判斷一個(gè)循環(huán)隊(duì)列是空隊(duì)列的條件是.

CAQ.rear==Q.front

'BQ.front==0

「CQ.rear==0

D(Q.rear+l)%maxsize==Q.front

對的答案：A

28.［第3章第4節(jié)】隊(duì)列的操作原則是o

區(qū)A先進(jìn)先出

「B先進(jìn)后出

C只能進(jìn)行插入

'D只能進(jìn)行刪除

對的答案:A

29.【第3章第4節(jié)】判斷順序儲(chǔ)存下隊(duì)列q是空的條件是q.front==q.rear。

⑤對的「錯(cuò)誤

對的答案：對

30.【第4章第1節(jié)】對線性表進(jìn)行二分查找時(shí)，規(guī)定線性表必須0

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

"B以順序方式存儲(chǔ)且元素有序

「C以鏈?zhǔn)椒绞酱鎯?chǔ)

「D以鏈?zhǔn)椒绞酱鎯?chǔ)且元素有序

對的答案:B

31.【第4章第1節(jié)】若用二分查找法取得的中間位置元素鍵值大于被查找值，說明被查找

值位于中間值的前面，下次的查找區(qū)間為從原開始位置至o

「A該中間位置

谷B該中間位置一1

「C該中間位置+1

廠D該中間位置/2

對的答案:B

32.【第4章第1節(jié)】在順序表｛2、5、7、10、14、15、18、23、35、41、52｝中,用二分

法查找關(guān)鍵碼12需做次關(guān)鍵碼比較。

rA2

B3

0c4

D5

對的答案:c

33.【第4章第2節(jié)】樹最適合用來表達(dá)o

CA有序數(shù)據(jù)元素

1B無序數(shù)據(jù)元素

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

「D元素之間無聯(lián)系的數(shù)據(jù)

對的答案:C

34.【第4章第2節(jié)】若由森林轉(zhuǎn)化得到的二叉樹是非空的二叉樹，則二叉樹形狀是。

CA根結(jié)點(diǎn)無右子樹的二叉樹

「B根結(jié)點(diǎn)無左子樹的二叉樹

%C根節(jié)點(diǎn)也許有左子樹和右子樹的二叉樹

廣D各結(jié)點(diǎn)只有一個(gè)兒子的二叉樹

對的答案:C

35.【第4章第2節(jié)】任何一個(gè)森林都可以唯一地與一棵二叉樹相應(yīng)。

:對的「錯(cuò)誤

對的答案：對

36.【第4章第2節(jié)】n(n>0)個(gè)結(jié)點(diǎn)的樹有n-1條邊。

6對的「錯(cuò)誤

對的答案：對

37.【第4章第3節(jié)】設(shè)深度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹

中所包含的結(jié)點(diǎn)數(shù)至多為(注意C和D中h是指數(shù))。

「A2h-1

'B2(h-1)

C2*h-1

D2*h

對的答案:A

我感覺對的答案應(yīng)當(dāng)是C,但是系統(tǒng)給的答案是A

38.【第4章第3節(jié)】在某棵二叉樹的一種序列中，假如發(fā)現(xiàn)其中每一結(jié)點(diǎn)的左孩子均是其

前趨,則可判斷定這種序列為中序序列。

“A對的

「B不對的

對的答案:A

39.【第4章第3節(jié)】已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,

它的前序遍歷序列是o

Aacbed

JBdecab

「Cdeabc

'?Dcedba

對的答案:D

40.【第4章第3節(jié)】假如某二叉樹的先序遍歷序列是abdcef,中序遍歷序列是dbaefc,

則其后序遍歷序列是o

「Adbafec

Bfecdba

CCefcdba

54Ddbfeca

對的答案:D

41.【第4章第3節(jié)】任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷的序列中的相對順

序。

⑤A不發(fā)生變化

CB發(fā)生變化

「C不能擬定

「D以上都不對

對的答案:A

42.【第4章第3節(jié)】某非空二叉樹的前序序列和后序序列正好相反，則二叉樹一定是

_的二叉樹。

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

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

「C.任一結(jié)點(diǎn)無左孩子

°、D任一結(jié)點(diǎn)無右孩子

對的答案：A

43.【第4章第3節(jié)】樹的基本遍歷策略可分為先根遍歷和后根遍歷;二叉樹的基本遍歷策略

可分為先序遍歷、中序遍歷和后序遍歷。這里我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹相應(yīng)

的二叉樹。那么以下結(jié)論中是對的的。

"A樹的先根遍歷序列與其相應(yīng)的二叉樹的先序遍歷序列相同

'B樹的后根遍歷序列與其相應(yīng)的二叉樹的后序遍歷序列相同

「C樹的先根遍歷序列與其相應(yīng)的二叉樹的中序遍歷序列相同

「D以上都不對

對的答案：A

44.【第4章第3節(jié)】設(shè)深度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中

所包含的結(jié)點(diǎn)數(shù)至少為（注意C和D中h為指數(shù)）。

A2h-1

B2(h-1)

CC2*h-1

CD2*h

對的答案:A

45.【第4章第3節(jié)】關(guān)于二叉樹的三種遍歷，下列說法對的的是一。

「A任意兩種遍歷序列都不可以唯一決定該二叉樹

「B任意兩種遍歷序列都可以唯一決定該二叉樹

「C先序遍歷序列和后序遍歷序列可以唯一決定該二叉樹

④D先序遍歷序列和中序遍歷序列可以唯一決定該二叉樹

對的答案:D

46.【第4章第3節(jié)】設(shè)a,b為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，a在b前的條件

是O

「Aa是b祖先

「Ba是b子孫

仿Ca在b左方

Da在b右方

對的答案:C

47.【第4章第3節(jié)】設(shè)二叉樹根結(jié)點(diǎn)的層次為1,所有具有15個(gè)結(jié)點(diǎn)的二叉樹中，最小高度

是O

「A6

rB5

CC4

D3

對的答案:c

48.【第4章第3節(jié)】由二叉樹的前序和中序遍歷序列可惟一構(gòu)造這棵二叉樹。

⑵對的「錯(cuò)誤

對的答案：對

49.【第4章第3節(jié)】滿二叉樹一定是完全二叉樹，反之不然。

1'*對的「錯(cuò)誤

對的答案：對

50.【第4章第3節(jié)】任何二叉樹的葉子數(shù)都要比度為2的結(jié)點(diǎn)數(shù)多。

1'*對的「錯(cuò)誤

對的答案：對

51.【第4章第4節(jié)】若構(gòu)造一棵具有n個(gè)結(jié)點(diǎn)的二叉排序樹，最壞的情況下其深度不會(huì)超

過。

「An/2

⑵Bn

「C(n+l)/2

Dn+1

對的答案:B

52.【第4章第4節(jié)】假如某二叉樹的左右子樹的高度差的絕對值不大于1,則一定是平衡

二叉樹。

r對的“錯(cuò)誤

對的答案：錯(cuò)

53.【第4章第4節(jié)】二叉排序樹一般用于查找某個(gè)元素。

6對的「錯(cuò)誤

對的答案：對

54.［第4章第6節(jié)】有m個(gè)葉子結(jié)點(diǎn)的Huffman樹所具有的結(jié)點(diǎn)總數(shù)為。

CAm+1

⑵B2m-1

「C2m

rD2m+l

對的答案:B

55.【第4章第6節(jié)】哈夫曼編碼使一串文字的編碼長度最短。

對的「錯(cuò)誤

對的答案：對

56.【第4章第6節(jié)】序列｛12,23,15,24,22,18,16,30,27｝是一個(gè)堆。

「對的與錯(cuò)誤

對的答案：錯(cuò)

57.【第5章第1節(jié)】哈希表是用于查找的技術(shù)之一。

④對的「錯(cuò)誤

對的答案：對

58.【第5章第2節(jié)】將10個(gè)元素散列到100000個(gè)單元的散列表中，則產(chǎn)生

沖突。

「A一定會(huì)

「B一定不會(huì)

④C仍也許會(huì)

對的答案:C

59.【第5章第2節(jié)】若散列表的裝載因子a<l,則可避免沖突的產(chǎn)生。

「對的”錯(cuò)誤

對的答案：錯(cuò)

60.【第5章第3節(jié)】設(shè)散列表長為14,散列函數(shù)是H(key)=key%l1,表中已有數(shù)據(jù)的關(guān)

鍵字為15,38,61,84共四個(gè)，現(xiàn)要將關(guān)鍵字為49的結(jié)點(diǎn)加到表中，用二次探測法解決沖突,

則放入的位置是。

「A8

「B3

「C5

“D9

對的答案:D

61.【第6章第2節(jié)】在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的一倍。

「A1/2

「B1

④C2

「D4

對的答案：C

62.［第6章第2節(jié)】具有5個(gè)頂點(diǎn)的有向完全圖有一條弧。

CA10

CB16

6c20

CD25

對的答案:C

63.【第6章第2節(jié)】無向圖各頂點(diǎn)度之和就等于邊的數(shù)量。

r對的仃錯(cuò)誤

對的答案：錯(cuò)

64.【第6章第2節(jié)】有向圖各頂點(diǎn)入度之和就等于邊的數(shù)量。

對的錯(cuò)誤

對的答案：對

65.【第6章第2節(jié)】5個(gè)頂點(diǎn)的無向圖，若不連通，則最多也許有6條邊。

6對的「錯(cuò)誤

對的答案：對

66.【第6章第2節(jié)】樹可以當(dāng)作是連通的圖。

谷'對的「錯(cuò)誤

對的答案：對

67.［第6章第3節(jié)】設(shè)n個(gè)頂點(diǎn)e條邊的圖G用鄰接表存儲(chǔ)，則求每個(gè)頂點(diǎn)入度的時(shí)間復(fù)

雜度為。

「AO(n)

“BO(n+e)

rCO(n*n)

「DO(n*e)

對的答案:B

68.【第6章第3節(jié)】對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，若采用鄰接表表達(dá)，鄰接表

中所有結(jié)點(diǎn)總數(shù)是。

「Ae/2

B2e

CCe

「Dn+e

對的答案:B

69.【第6章第3節(jié)】下面關(guān)于圖的存儲(chǔ)的敘述中，哪一個(gè)是對的的？

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

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

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

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

對的答案:A

70.【第6章第3節(jié)】鄰接表是圖的一種—o

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

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

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

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

對的答案:B

71.【第6章第3節(jié)】用鄰接矩陣表達(dá)圖所用的存儲(chǔ)空間大小與圖的邊數(shù)成正比。

「對的、錯(cuò)誤

對的答案：錯(cuò)

72.【第6章第4節(jié)】假如無向圖G必須進(jìn)行二次廣度優(yōu)先搜索才干訪問其所有頂點(diǎn)，則

下列說法中不對的的是o

「AG肯定不是完全圖

「BG一定不是連通圖

仿,CG中一定有回路

「DG有2個(gè)連通分量

對的答案:C

73.【第6章第4節(jié)】連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來暫存剛訪問過的頂點(diǎn)。

仃對的「錯(cuò)誤

對的答案：對

74.【第6章第4節(jié)】圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷都包含了圖的所有頂點(diǎn)。

對的r錯(cuò)誤

對的答案：對

75.【第6章第5節(jié)】關(guān)于無向連通圖的最小生成樹的個(gè)數(shù)。

rA一定有多棵

6B一定只有一棵

rC有一棵或多棵

「D也許不存在

對的答案:B

76.【第6章第5節(jié)】下列關(guān)于圖的生成樹的唯一性，對的的是。

「A生成樹是唯一的

B生成樹是不唯一的

“C生成樹是唯一性不擬定

「D圖的生成樹有兩棵

對的答案:C

77.【第7章第2節(jié)】一組記錄的排序碼為(20,29,11,74,35,3,8,56)，則運(yùn)用堆排序方法建

立的初始(小頂)堆為。

「A20,29,11,74,35,3,8,56

仿B3,29,8,56,35,20,11,74

「C3,8,11,20,29,35,56,74

「D20,29,3,8,11,35,74,56

對的答案:B

78.【第7章第3節(jié)】用某種排序方法對線性表(25,84,21,47,15,27,68,35,20)進(jìn)行

排序時(shí)，元素序列的變化情況如下(1)20,15,21,25,47,27,68,35,84(2)15,20,2

1,25,35,27,47,68,84(3)15,20,21,25,27,35,47,68,84則所采用的排序方法是。

'A選擇排序

「B希爾排序

「C歸并排序

'D快速排序

對的答案:D

79.【第7章第3節(jié)】在某個(gè)實(shí)例的排序結(jié)果看出，值相同的兩個(gè)關(guān)鍵字排序前后領(lǐng)先關(guān)系

不變，由此可知該