濱州學院數(shù)據(jù)結構期末考試復習題庫

2023年上學期數(shù)據(jù)結構期末考試題庫

一、單項選擇題

1.對二叉排序樹進行（），可以得到各結點鍵值的遞增序列。

A.先根遍歷

B.中根遍歷

C.層次遍歷

D.后根遍歷

答案：B

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

A.快速排序

B.堆排序

C.歸并排序

D.基數(shù)排序

答案：C

3.

將數(shù)組稱為隨機存儲結構是因為（）。

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

B.隨時可以對數(shù)組元素進行訪問

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

D.數(shù)組的存儲結構是不定的

答案：C

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

A.棧

B.隊列

C.查找表

D.數(shù)組

答案：B

5.在AVL樹中，每個結點的平衡因子的取值范圍是（）。

A.-1-1

B.-2-2

C.1-2

D.0-1

答案：A

6.在有頭結點的單鏈表L中，向表頭插入一個由指針p指向的結點，則執(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頁

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

A.不在需要頭指針了

B.已知某個結點的位置后，能夠容易找到他的直接前趨

C.在進行插入、刪除運算時，能更好的保證鏈表不斷開

D.從表中的任意結點出發(fā)都能掃描到整個鏈表

答案：D

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

A.直接插入排序

B.直接選擇排序

C.堆排序

D.快速排序

答案：B

9對關鍵字序列（14,5,19,20,11,19）,第一趟排序的結果為（14,5,19,20,11,19）,則可能的排序

方法是（）。

A.簡單選擇排序

B.快速排序

C.希爾排序

D.二路歸并排序

答案：C

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

A.高度等于其結點數(shù)

B.任一結點無左孩子

C.任一結點無右孩子

D.空或只有一個結點

答案：D

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

A.歸并排序

B.堆排序

C.快速排序

D.錦標賽排序

答案：B

12.除根結點外，樹上每個結點（）。

A.可有任意多個孩子、一個雙親

B.可有任意多個孩子、任意多個雙親

C.可有一個孩子、任意多個雙親

D.只有一個孩子、一個雙親

答案：A

13.設計一個判斷表達式中左右括號是否配對出現(xiàn)的算法，采用（）數(shù)據(jù)結構最好。

A.順序表

B.鏈表

C.隊列

第2/57頁

D.棧

答案：D

14.

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

A.二叉排序樹法

B.平衡樹法

C.散列法

D.二分查找法

答案：D

15.導致隊列下溢的操作是（）。

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

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

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

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

答案：C

16.若一個圖的邊集為{<1,2〉,<1,4>,<2,5>,<3,1〉,<3,5>,<4,3>},則從頂點1開始對該圖進行深

度優(yōu)先搜索，得到的頂點序列可能為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ù)據(jù)轉化為計算機所能表示的形式，其轉化過程依次為（）。

A.邏輯結構、存儲結構、機外表示

B.存儲結構、邏輯結構、機外表示

C.機外表示、邏輯結構、存儲結構

D.機外表示、存儲結構、邏輯結構

答案：C

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

A.棧

B.隊列

C.查找表

D.數(shù)組

答案：A

19.多維數(shù)組之所以有行優(yōu)先順序和列優(yōu)先順序兩種存儲方式是因為（）。

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

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

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

D.數(shù)組是多維結構，內存是一維結構

答案：A

第3/57頁

20.

下列敘述錯誤的是（）。

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

B.多維數(shù)組是非線性結構。

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

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

答案：D

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

A.有向完全圖

B.連通圖

C.強連通圖

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

答案：D

22.關于哈夫曼樹，下列敘述正確的是（）。

A.可能有度為1的結點

B.總是完全二叉樹

C.有可能是滿二叉樹

D.WPL是深度最大葉子的帶權路徑長度

答案：C

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

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

A.直接插入排序

B.二路歸并排序

C.以第一元素為基準的快速排序

D.基數(shù)排序

答案：C

24.假定有k個關鍵字互為同義詞，若用線性探測法把這k個關鍵字存入散列表中，至少要進

行（）次探側。

A.k-1

B.k

C.k+1

D.k（k+l）/2

答案：D

25.若一個圖的邊集為{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>},則從頂點1開始對該圖進行廣

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

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頁

26.

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

A.4

B.5

C.6

D.7

答案：B

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

A.直接插入排序

B.快速排序

C.直接選擇排序

D.歸并排序

答案：A

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

A.快速排序

B.直接插入排序

C.堆排序

D.歸并排序

答案：C

29.

單鏈表中增加頭結點的目的是為了（）。

A.使單鏈表至少有一個結點

B.標識表結點中首結點的位置

C.方便運算的實現(xiàn)

D.說明單鏈表是線性表的鏈式存儲

答案：C

30.

在索引查找中，若主表長度為144,它被均分為12子表，每個子表的長度均為12,則索引

查找的平均查找長度為（）。

A.13

B.24

C.12

D.79

答案：A

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

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

B.三元組和散列

C.三元組和十字鏈表

第5/57頁

D.散列和十字鏈表

答案：C

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

A.n

B.n+e

C.n+2e

D.e

答案：A

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

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

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

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

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

答案：D

34.

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

用（）存儲方式最節(jié)省運算時間。

A.單鏈表

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

C.雙鏈表

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

答案：D

35.

棧和隊列通常采用的兩種存儲方式是（）。

A.散列存儲和索引存儲

B.索引存儲和鏈式存儲

C.順序存儲和鏈式存儲

D.散列存儲和順序存儲

答案：C

36.下面關于圖的存儲的敘述中，（）是正確的。

A.鄰接矩陣表示時，占用的存儲空間數(shù)只與圖中結點個數(shù)有關，而與邊數(shù)無關

B.鄰接矩陣表示時，占用的存儲空間數(shù)只與圖中邊數(shù)有關，而與結點個數(shù)無關

C.鄰接表表示時，占用的存儲空間數(shù)只與圖中結點個數(shù)有關，而與邊數(shù)無關

D.鄰接表表示時，占用的存儲空間數(shù)只與圖中邊數(shù)有關，而與結點個數(shù)無關

答案：A

37.下列關于串的敘述中，正確的是（）。

A.一個串的字符個數(shù)即該串的長度

B.一個串的長度至少是1

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

第6/57頁

D.兩個串若長度相同，則它們相等

答案：A

38.棧和隊列的共同特點是（）。

A.都是先進后出

B.都是先進先出

C.只允許在端點處插入和刪除元素

D.沒有共同點

答案：C

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

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

A.A

B.B

C.C

D.D

答案：C

40.

算法分析的目的是（）。

A.找出數(shù)據(jù)結構的合理性

B.研究算法中的輸入/輸出關系

C.分析算法的效率以求改進

D.分析算法的易讀性

答案：C

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

點有左孩子，則左孩子存放在（）。

A.BT[i/2]

B.BT[2*i-l]

C.BT[2*i]

D.BT[2*i+l]

答案：D

42.連通圖是指圖中任意兩個頂點之間（）。

A.都連通的無向圖

B.都不連通的無向圖

C.都連通的有向圖

D.都不連通的有向圖

答案：A

43.若結點的存儲地址可以反映數(shù)據(jù)間的邏輯關系，則相應的存儲結構應為（）o

A.順序存儲結構

B.鏈式存儲結構

C.索引存儲結構

D.散列存儲結構

第7/57頁

答案：A

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

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

B.最小生成樹算法

C.最短路徑算法

D.拓撲排序算法

答案：D

45.

對線性表進行二分查找時，要求線性表必須（）。

A.以順序方式存儲

B.以鏈接方式存儲

C.順序存儲，且結點按關鍵字有序排序

D?鏈式存儲，且結點按關鍵字有序排序

答案：C

46.在AVL樹中，任一結點的（）。

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

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

C.左、右子樹的結點數(shù)均相同

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

答案：B

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

A.求頂點的鄰接點

B.求頂點的度

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

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

答案：B

48.

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

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

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

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

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

答案：A

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

A.前序

B.中序

C后序

D.按層次

答案：C

第8/57頁

50.下面關于線性表的敘述錯誤的是()。

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

B.線性表采用順序存儲，便于進行插入和刪除操作；

C.線性表采用鏈式存儲，不必占用一片地址連續(xù)的單元；

D.線性表采用鏈式存儲，便于進行插入和刪除操作；

答案：B

51.

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

A.元素之間是線性關系

B.線性表中至少有一個元素

C.任一元素有且僅有一個直接前趨

D.任一元素有且僅有一個直接后繼

答案：A

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

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

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

C.樹的后根遍歷與對應二叉樹的后根遍歷相同。

D.樹的先根序列與對應二叉樹的先根序列相同。

答案：C

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

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

A.線性表

B.純表

C.再入表

D.遞歸表

答案：D

54.

串是一種()線性表。

A.長度受限

B.元素類型受限

C.操作受限

D.一般

答案：B

55.

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

A.直接選擇排序

B.歸并排序

C.堆排序

第9/57頁

D.快速排序

答案：D

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

A.迷宮求解

B.括號匹配

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

D.多項打印任務的安排

答案：D

57.對有向圖，下面（）種說法是正確的。

A.每個頂點的入度等于出度

B.每個頂點的度等于其入度與出度之和

C.每個頂點的入度為0

D.每個頂點的出度為0

答案：B

58.對n個頂點的有向圖，若所有頂點的出度之和為s,則所有頂點的入度之和為（）。

A.s

B.s-1

C.s+1

D.n

答案：A

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

A.插入

B.刪除

C.串聯(lián)接

D.子串定位

答案：D

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

A.二叉查找樹

B.鏈表

C.散列表

D.順序表

答案：C

61.對長度為n的順序表，刪除第i個元素（IgiSn）時元素移動的次數(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頁

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

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

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

答案：A

63.

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

A.二分查找、二叉排序樹查找

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

C.二叉排序樹查找、索引順序表查找

D.二叉排序樹查找、散列法查找

答案：B

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

A.它們的邏輯結構不一樣

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

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

D.存儲實現(xiàn)不一樣

答案：B

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

/>

A.4階B-樹

B.4階B+樹

C.3階B-樹

D.3階B+樹

答案：D

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

與F對應的二叉樹的右子樹中的結點個數(shù)為（）。

A.10

B.12

C.8

D.15

答案：C

67.

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

A.遞增的

B.隨機的

C.遞減的

D.任意的

答案：C

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

第11/57頁

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

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

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

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

答案：C

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

A.9

B.U

C.12

D.14

答案：C

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

A.n-1

B.n

C.n(n-l)/2

D.n(n+l)/2

答案：A

71.由同一關鍵字集合構造的各棵二叉排序樹()。

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

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

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

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

答案：A

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

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.若有向圖的鄰接矩陣中，主對角線以下的元素均為零，則該圖的拓撲有序序列()。

A.存在

B.不存在

C.不確定

答案：A

74.

在需要經常查找結點的前趨與后繼的場合中，使用()比較合適。

A.單鏈表

B.雙鏈表

C.循環(huán)鏈表

D.順序表

第12/57頁

答案：D

75.

關于十字鏈表中的敘述，錯誤的是（）。

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

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

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

D.行鏈表、列鏈表的頭結點不能共用

答案：D

76.下圖所示二叉樹對應的森林中有（）棵樹。<imgheight="140"width="186"alt=""

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

A.l

B.2

C.3

D.不確定

答案：C

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

用（）存儲方式最節(jié)省運算時間。

A.單鏈表

B.雙鏈表

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

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

答案：D

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

A.正數(shù)

B.負數(shù)

C.零

D.不確定

答案：B

79.對長度為10的順序表進行查找，若查找前面5個元素的概率相同，均為1/8,查找后面5

個元素的概率相同，均為3/40,則查找任一元素的平均查找長度為（）。

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頁

D.遞歸表

答案：C

81.棧和隊列都是（）。

A.限制存取位置的線性結構

B.順序存儲的線性結構

C.鏈式存儲的線性結構

D.限制存取位置的非線性結構

答案：A

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

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.連通網的最小生成樹是其所有生成樹中（）。

A.頂點集最小的生成樹

B.邊集最小的生成樹

C.頂點權值之和最小的生成樹

D.邊的權值之和最小的生成樹

答案：D

第14/57頁

84.若對n個元素進行歸并排序，則進行每一趟歸并的時間復雜性為()。

A.O(l)

B.O(log2n)

C.O(n)

D.O(n2)

答案：C

85.在n個頂點和e條邊的無向圖的鄰接表中，邊結點的個數(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.若一個圖的邊集為{(八上)小?,出0,9尸)心正)3萬)},則從頂點人開始對該圖進行深

度優(yōu)先搜索，得到的頂點序列可能為()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.先進先出

B.后進先出

C.棧底刪除

D.以上都不是

答案：B

89.線索二叉樹中某結點沒有左孩子的條件是()。

A.p!=NULL

B.p->ltag==O

C.p->ltag==l

D.p->lchild!=NULL

答案：c

第15/57頁

90.求單鏈表中當前結點的后繼和前趨的時間復雜度分別是()。

A.O(n)和0(1)

B.0⑴和0(1)

C.O(l)和0(n)

D.O(n)和O(n)

答案：C

91.

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

A.轉置運算時只需把每個三元組的行、列下標互換即可。

B.存儲時只需要各非零元素的三元組信息，不需要其它信息。

C.適合于對稱矩陣的壓縮存儲。

D.訪問元素時不能隨機存取。

答案：D

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

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

B.數(shù)據(jù)類型可分為原子類型和結構類型

C.運算可分為加工型和引用型

D.數(shù)據(jù)結構可分為邏輯結構和非邏輯結構

答案：D

93.線索二叉樹中某結點為葉子的條件是()。

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.在下列排序方法中，空間復雜性為O(n)的方法為()。

A.快速排序

B.直接插入排序

C.堆排序

D.歸并排序

答案：D

95.在散列查找中，平均查找長度主要與()有關。

A.散列表長度

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

C.裝填因子

D.處理沖突方法

答案：C

96.若要在0(1)的時間內將兩個循環(huán)鏈表頭尾相接，則應對兩個循環(huán)鏈表各設置一個指針,

分別指向()。

A.各自的頭結點

第16/57頁

B.各自的尾結點

C.各自的第一個元素結點

D.一個表的頭結點，另一個表的尾結點

答案：B

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

A.時間和空間性能往往是一對矛盾

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

C.常常可犧牲時間性能換取空間性能

D.時間和空間性能并不會矛盾

答案：D

98.對長度為n的順序表，等概率情況下插入一個元素時平均要移動元素的個數(shù)為()o

A.n/2

B.(n+l)/2

C.(n-l)/2

D.n

答案：A

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

A.無向圖

B.有向圖

C.稠密圖

D.稀疏圖

答案：C

lOO.n個頂點的強連通圖若只有n條邊，則該有向圖的形狀是()。

A.無回路

B.有回路

C.環(huán)狀

D.樹狀

答案：C

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

A.n-1

B.n

C.n(n-l)/2

D.n(n+l)/2

答案：A

102.

算法的時間復雜度取決于()。

A.問題的規(guī)模

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

C.A和B

D.以上都不是

第17/57頁

答案：c

103.

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

A.直接選擇排序

B.冒泡排序

C.快速排序

D.希爾排序

答案：B

104.

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

采用（）存儲方式最節(jié)省運算時間。

A.單鏈表

B.雙鏈表

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

D.容量足夠大的順序表

答案：D

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

式最節(jié)省運算時間（）。

A.單鏈表

B.順序表

C.雙鏈表

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

答案：B

106.

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

A.線性表

B.純表

C.再入表

D.遞歸表

答案：B

第18/57頁

107.對n個頂點和e條邊的有向圖，以鄰接矩陣存儲，則求圖中某頂點入度的時間復雜度為

()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">以下廣義表關系正確的是()。</span></span>

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

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

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

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

答案：D

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

A.先進先出

B.后進先出

C.隊尾刪除

D.隊頭插入

答案：A

110.某完全二叉樹有7個葉子，則其結點總數(shù)為()。

A.14

B.13

C.13或14

D.以上都不是

答案：C

111.

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

A.冒泡排序

B.歸并排序

C.希爾排序

D.直接插入排序

答案：C

112.若結點的存儲地址與結點內容有某種確定的關系，則相應的存儲結構應為()。

A.順序存儲結構

B.鏈式存儲結構

C.索引存儲結構

D.散列存儲結構

答案：D

第19/57頁

113.若只在線性表的首、尾兩端進行插入操作，宜采用的存儲結構為（）。

A.順序表

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

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

D.單鏈表

答案：C

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

A.ABCD

B.ACDB

C.DABC

D.DCBA

答案：C

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

A.n

B.n-1

C.n+1

D.n/2

答案：B

116.下述序列中，哪個可能是在二叉排序樹上查找35時所比較過的關鍵字序列？

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.一些符號構成的序列

B.有限個字母構成的序列

C.一個以上的字符構成的序列

D.有限個字符構成的序列

答案：D

118.

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

A.入隊

B.出隊

C.取隊頭元素

D.取隊尾元素

答案：B

119.

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

第20/57頁

A.便于隨機存取

B.花費的存儲空間較順序存儲少

C.便于插入和刪除

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

答案：C

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

2^n-l

A.A

B.B

C.C

D.D

答案：D

121.對長度為n的順序表，訪問第i個元素的時間是。。

A.O(n2)

B.O(n)

C.O(nlog2n)

D.O(l)

答案：D

122.二叉樹的葉子結點在前序、中序和后序遍歷序列中的相對次序()。

A.可能改變

B.一定會改變

C.一定不改變

D.可能變也可能不變

答案：C

123.若一個圖的邊集為{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)},則從頂點A開始對該圖進行廣

度優(yōu)先搜索，得到的頂點序列可能為()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.若一個圖中包含有k個連通分量，若要按照深度優(yōu)先搜索的方法訪問所有頂點，則必須

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

A.1

B.k

C.k-1

D.k+1

答案：B

125.在以單鏈表為存儲結構的線性表中，數(shù)據(jù)元素之間的邏輯關系用()。

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

第21/57頁

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

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

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

答案：C

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

A.ABCD

B.DCBA

C.任意順序

D.以上都不是

答案：A

127.線性表采用鏈式存儲時，其地址（）。

A.必須連續(xù)

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

C.一定不連續(xù)

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

答案：D

128.下面關于B樹和B+樹的敘述中，不正確的是

A.都是平衡的多叉樹

B.都是可用于文件的索引結構

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

D.都能有效地支持隨機檢索

答案：C

129.

以下敘述錯誤的是（）。

A.數(shù)據(jù)的三個層次是數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項

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

C.每種邏輯結構都有一個運算的集合

D.儲存結構中不僅要儲存數(shù)據(jù)的內容，還要把數(shù)據(jù)間的關系表示出來。

答案：B

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

可能的拓撲序列為（）o

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.對11個元素進行快速排序，最壞情況下需要進行（）趟6）方）11-1011/2口）108<5此〉2</5此>11

A.A

B.B

C.C

第22/57頁

D.D

答案：B

132.

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

A.10

B.8

C.16

D.以上都可以

答案：D

133.對包含n個關鍵字的散列表進行檢索，平均檢索長度是()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.下列排序算法中，當初始數(shù)據(jù)有序時，花費時間反而最多的是()。

A.起泡排序

B.希爾排序

C.堆排序

D.快速排序

答案：D

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

A.插入

B.選擇

C.希爾

D.快速

答案：D

136.算法分析是指()。

A.分析算法的正確性

B.分析算法的可讀性

C.分析算法的健壯性

D.分析算法的時空性能

答案：D

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

A.n

B.n*e

C.e

D.2*e

答案：D

第23/57頁

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

A.1

B.n-1

C.n

D.n+1

答案：C

139.若要在單鏈表中的結點*p之后插入一個結點*s,則應執(zhí)行的語句是()。

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個結點可構成()個不同形態(tài)的二叉樹。

A.2

B.3

C.4

D.5

答案：D

141.樹結構最適合用來表示()。

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

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

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

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

答案：C

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

A.直接選擇排序

B.冒泡排序

C.直接插入排序

D.希爾排序

答案：A

143.對n個結點的二叉樹，按()遍歷順序對結點編號(號碼為l~n)時，任一結點的編號等

于其左子樹中結點的最大編號加1,又等于其右子樹中結點的最小編號減1。

A.前根

B.中根

C后根

D層次

答案：B

144.設有向圖n個頂點和e條邊，進行拓撲排序時，總的計算時間為()。

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

A.A

第24/57頁

B.B

C.C

D.D

答案：D

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

A.鍵值有序的單鏈表

B.鍵值有序的順序表

C.鍵值有序的雙鏈表

D.鍵值無序的順序表

答案：B

146.設p指向單鏈表中的一個結點，s指向待插入的結點，則下述程序段的功能是（）。

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

A.結點*p與結點*s的數(shù)據(jù)域互換

B.在p所指結點的元素之前插入元素

C.在p所指結點的元素之后插入元素

D.在結點*p之前插入結點*s

答案：D

147.二叉樹的結構如下圖所示，其中序遍歷的序列為（）。<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語言中，串的存儲方式是（）。

A.順序存儲

B.散列存儲

C.索引存儲

D?鏈式存儲

答案：A

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

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

A.A

B.B

C.C

D.D

答案：C

二、判斷題

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

答案：錯誤

第25/57頁

151.如果根結點的左子樹和右子樹高度差不超過1,則該二叉樹是平衡二叉樹。

答案：錯誤

152.每一種邏輯結構只能對應一種存儲結構。

答案：錯誤

153.

單鏈表中取第i個元素的時間與i成正比。

答案：正確

154.不是所有的有向圖都可以進行拓撲排序，而能拓撲排序時，結果不一定唯一。

答案：正確

155.計算機的速度越快，算法的時間復雜性就越低。

答案：錯誤

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

答案：正確

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

答案：錯誤

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

答案：錯誤

159.算法的時間復雜性是指在計算機上的實際運行時間。

答案：錯誤

160.順序表插入和刪除時，移動元素的個數(shù)與該元素的位置有關。

答案：正確

161.線性結構可以順序存儲，也可以鏈接存儲。非線性結構只能鏈接存儲。

答案：錯誤

162.在棧的應用中，棧頂指針總是指向真正的棧頂。

答案：錯誤

163.

利用?？蓪⑦f歸程序轉化成非遞歸程序。

答案：正確

164.為了運算方便，鏈隊列一般帶頭結點。

答案：正確

第26/57頁

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

答案：正確

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

答案：正確

167.稀疏矩陣壓縮存儲后會喪失隨機存取特性。

答案：正確

168.

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

答案：錯誤

169?計算機的內、外存越大，算法的空間復雜性就越低。

答案：錯誤

170.任何樹或林都可轉化為二叉樹，反之，二叉樹可轉化為任何樹或林。

答案：錯誤

171.在數(shù)據(jù)結構中，算法的空間耗費包括代碼和數(shù)據(jù)兩部分。

答案：錯誤

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

答案：正確

173.如果n個頂點的無向圖有n條邊，則圖中肯定有回路。

答案：正確

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

答案：錯誤

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

答案：錯誤

176.

若有向圖中含有一個或多個環(huán)，則其頂點間不存在拓撲序列。

答案：正確

177.

無向圖中邊數(shù)等于鄰接矩陣中1的個數(shù)的一半；也等于鄰接表中的邊表結點數(shù)的一半。

答案：正確

178.

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

第27/57頁

答案：錯誤

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

答案：錯誤

180.

在二叉排序樹中，即使刪除一個結點后馬上再插入該結點，該二叉排序樹的形態(tài)也可能不

同。

答案：正確

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

出”的要求，故實際上已不是隊列了。

答案：錯誤

182.關鍵路徑是指起點到終點的最短路徑，它決定了整個工期的長短。

答案：錯誤

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

答案：錯誤

184.

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

答案：錯誤

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

答案：錯誤

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

答案：錯誤

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

答案：錯誤

188.不管樹的深度和形態(tài)如何，也不可能構造出一棵剛好有100個結點的哈夫曼樹。

答案：正確

189.拓撲排序可以分析某工程能否順利進行。

答案：正確

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

答案：正確

191.在線索二叉樹上，求結點的（遍歷）前趨和后繼時可利用線索得到，即不必進行遍歷了。

答案：錯誤

第28/57頁

192.二叉樹中可能所有結點的度都小于2。

答案：正確

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

答案：錯誤

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

答案：正確

195.數(shù)據(jù)的邏輯結構與計算機無關，但存儲結構依賴于計算機。

答案：正確

196.二叉排序樹上，以根到任一結點的路徑為界，則：路徑左邊結點〈路徑結點V路徑右

邊結點。

答案：錯誤

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

答案：錯誤

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

答案：錯誤

199.單鏈表是順序存取結構。

答案：正確

200.采用高速計算機，可以降低算法的時間復雜性。

答案：錯誤

201.利用哈夫曼編碼，可以進行文件壓縮。

答案：正確

202.圖G的生成樹T是G的子圖。

答案：正確

203.棧和隊列邏輯上都是線性表。

答案：正確

204.當問題具有先進先出特點時，就需要用到棧。

答案：錯誤

205.二叉樹中不可能有兩個結點在先根、中根和后根序列中的相對次序都不變。

答案：錯誤

206.在AOE網中關鍵路徑最多只有一條。

答案：錯誤

第29/57頁

207.數(shù)據(jù)的邏輯結構和運算集組成問題的數(shù)學模型，與計算機無關。

答案：正確

208.如果某種排序算法是不穩(wěn)定的，則該方法沒有實際的應用價值。

答案：錯誤

2O9.Shell排序的時間性能與增量序列的選取有關，但關系不大。

答案：錯誤

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

答案：錯誤

211.

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

答案：錯誤

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

答案：正確

213.

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

答案：錯誤

214.線索二叉鏈表就是用結點的空指針域來存放某種遍歷的前趨和后繼線索，所以線索二

叉鏈表中就沒有空指針了。

答案：錯誤

215.

鏈棧一般不需要頭結點，因為無頭結點的鏈棧運算也很方便。

答案：正確

216.數(shù)據(jù)結構的概念包括數(shù)據(jù)的邏輯結構、存儲結構和運算三個方面。

答案：正確

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

答案：正確

218.

如果網絡中有多條邊的權相同，則其最小生成樹就不會是唯一的。

答案：錯誤

219.n個結點的有向圖，若它有n(n—l)條邊，則它一定是強連通的。

答案：正確

第30/57頁

220.由普通樹轉換來的二叉樹，其根結點一定沒有右子樹。

答案：正確

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

答案：正確

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

答案：正確

223.

每個節(jié)點一個鏈域的鏈表是單鏈表，每個節(jié)點兩個鏈域的鏈表是雙鏈表。

答案：錯誤

224.哈夫曼樹中不存在度為1的結點。

答案：正確

225.空串是指長度為0的字符串。

答案：錯誤

226.樹和森林都可轉化為二叉樹，故對給定的二叉樹，不能區(qū)分是由樹還是森林轉換來的。

答案：錯誤

227.有向圖中邊數(shù)等于鄰接矩陣中1的個數(shù)；也等于鄰接表中的邊表結點數(shù)。

答案：正確

228.單鏈表中的頭結點就是單鏈表的第一個結點。

答案：錯誤

229.在拓撲序列中，若兩點Vi和Vj相鄰，則從Vi到Vj有路徑。

答案：錯誤

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

答案：錯誤

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

答案：錯誤

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

答案：正確

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

查找長度肯定比后者大。

答案：錯誤

234.二叉樹中至少有一個結點的度為2。

第31/57頁

答案：錯誤

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

答案：正確

236.

在順序表的某些位置插入和刪除結點時不需移動其它結點。

答案：正確

237.二叉排序樹是用來進行排序的。

答案：錯誤

238.對稱矩陣壓縮存儲后仍然可以隨機存取。

答案：正確

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

答案：正確

240.縮短關鍵路徑上活動的工期一定能夠縮短整個工程的工期。

答案：錯誤

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

答案：正確

242.有時冒泡排序的速度會快過快速排序。

答案：正確

243.將樹轉化為二叉樹后，原樹中的葉子結點在二叉樹中不一定也是葉子結點。

答案：正確

244.算法的正確性，一般不進行形式化的證明，而是用測試來驗證。

答案：正確

245.算法的時間復雜性越高，則計算機速度提高后，得到的收益就越大。

答案：錯誤

246.二分查找所對應的判定樹，是一棵理想平衡的二叉排序樹。

答案：正確

247.

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

答案：錯誤

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

答案：錯誤

第32/57頁

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

答案：正確

250.在鏈棧上進行進棧操作時，不需判斷棧滿。

答案：正確

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

答案：錯誤

252.

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

答案：錯誤

253.在線性結構中，每個結點都有一個直接前驅和一個直接后繼。

答案：錯誤

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

答案：錯誤

255.

若二叉樹中沒有度為1的結點，則為滿二叉樹。

答案：錯誤

256.

順序表可以按序號隨機存取。

答案：正確

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

答案：錯誤

258.

在開散列表中不會出現(xiàn)堆積現(xiàn)象。

答案：正確

259.

滿二叉樹是一種特殊的完全二叉樹。

答案：正確

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

答案：正確

第33/57頁

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

答案：錯誤

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

答案：正確

263.若將當前最長的關鍵活動的時間縮短2天，則整個工期可提前2天。

答案：錯誤

三、填空題

264.n個頂點的連通圖至少條邊，最多條邊。

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

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

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

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

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

答案：層次</p>

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

答案：先根</p>

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

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

269.內排序是指o

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

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

答案：l</p>

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

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

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

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

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

273.散列表的沖突處理方法有和兩種，對應的散列表分別稱為開散列

表和閉散列表。

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

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

答案：7</p>

第34/57頁

275.下圖所示帶權無向圖的最小生成樹的權為o<imgalt=""

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

答案：17</p>

276.

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

答案：4</p>

277.評價查找效率的主要標準是。

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

278

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

答案：對相同關鍵字排序前后相對位置不變</p>

279.

評價排序效率的主要標準是O

答案：關鍵字比較次數(shù)、移動次數(shù)</p>

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

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

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

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

答案：bt[16]

282.串“The"含有的子串個數(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>},則從頂點V0到頂

點V4的最短路徑長度為（）o

答案：7

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

出度為0的頂點個數(shù)為（），入度為1的頂點個數(shù)為（）o

答案:2,4

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

三項。

答案：行號、列號、值</p〉

286.

兩個串相等的充分必要條件是兩個串的長度相等且O

答案：對應字符相同</p>

287.某二叉樹中雙分支結點數(shù)為5個，單分支結點數(shù)為4個，則葉子結點數(shù)為個。

答案：6</p>

第35/57頁

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

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

289.n(>l)個頂點的強連通圖至少條邊，最多條邊。

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

290.順序棧在進行運算時，可能發(fā)生棧的上溢，在進行運算時，可能

發(fā)生棧的下溢。

答案：進棧、退棧</p>

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

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

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

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

該圖一定是圖。

答案：連通</p>

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

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

294.n個頂點的無向圖，最少有條邊，最多有條邊。

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

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

答案：linkedstring

296.在有向無環(huán)圖中，若存在一條從頂點i到頂點j的弧，則在頂點的拓撲序列中，頂點i與

頂點j的先后次序是。

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

297.十字鏈表中的結點需存儲非零元素的五個信息：行號、列號、值、、o

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

298.對n個頂點和e條邊的無向圖，采用鄰接矩陣和鄰接表表示時，求任一頂點度數(shù)的時間

復雜性分別為和0

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

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

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

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

答案：55、54</p>

301.對400個結點的完全二叉樹，葉子數(shù)為

答案：200</p〉

第36/57頁

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

答案：儲存、查找</p>

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

答案：O(l)</p>

304.

設元素al,a2,a3,a4,a5和a6依次入棧，出棧順序為a3,a5,a4,a6,a2,al,則棧的容

量至少為o

答案：4</p>

305.

帶頭結點的單鏈表L為空的判定條件是o

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

306.

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

答案：索引表查找、塊內查找</p>

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

答案：3

308.從n個結點的二叉排序樹中查找一個元素，平均時間復雜性大致為o

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

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

答案：100</p>

31O.Kruska噂法求最小生成樹的時間為，對圖比較有利。

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

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

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

312.

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

答案：ll</p>

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

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

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

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

315.在順序表中做插入操作時首先檢查______o

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