數據結構—選擇題

01-數據結構—判斷題

71.在數據結構中，從邏輯上可以把數據結構分為（）。

A. 動態結構和靜態結構

B. 緊湊結構和非緊湊結構

C. 線性結構和非線性結構

D. 內部結構和外部結構

答案：C

72.當輸入規模為n時，下列算法漸進復雜性中最低的是

A. 5n

B. n^2

C. 2n^2

D. n!

答案：A

73.下面代碼段的時間復雜度是（）。?x = 0;for (i = 1; i < n; i++) {? ? for (j = 1; j <= n - i; j++) {? ? ? ? x++;? ? }}?

A.O(n)

B.O(n^2)

C.O(n^3)

D.O(2^n)

答案：B

74.某線性表采用順序存儲結構，每個元素占4個存儲單元，首地址為100，則第12個元素的存儲地址為（）。

A. 144

B. 145

C. 147

D. 148

答案：A

75.在單鏈表中，若|p|所指的結點不是最后結點，在|p|之后插入|s|所指結點，則執行

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

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

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

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

答案：C

76.設|h|為不帶頭結點的單向鏈表。在|h|的頭上插入一個新結點|t|的語句是：

A. |h=t; t->next=h->next;|

B. |t->next=h->next; h=t;|

C. |h=t; t->next=h;|

D. |t->next=h; h=t;|

答案：D

77.線性表在 ▁▁▁▁▁ 情況下適合采用鏈式存儲結構。

A. 線性表中數據元素的值需經常修改

B. 線性表需經常插入或刪除數據元素

C. 線性表包含大量的數據元素

D. 線性表的數據元素包含大量的數據項

答案：B

78.若元素a、b、c、d、e、f依次進棧，允許進棧、退棧操作交替進行，但不允許連續三次進行退棧工作，則不可能得到的出棧序列是？

A. b c a e f d

B. c b d a e f

C. d c e b f a

D. a f e d c b

答案：D

79.設一個堆棧的入棧順序是1、2、3、4、5。若第一個出棧的元素是4，則最后一個出棧的元素必定是：

A. 1

B. 3

C. 5

D. 1或者5

答案：D

80.

A.1->2->3

B.2->3->4

C.4->1->2

D.答案不唯一

答案：B

81.在一個不帶頭結點的非空鏈式隊列中,假設f和r分別為隊頭和隊尾指針,則刪除結點的運算是( )。

A. r=f->next;

B. r=r->next;

C. f=f->next;

D. f=r->next

答案：C

82.已知二叉樹的前序遍歷序列為 ABDCEFG，中序遍歷序列為 DBCAFEG，則后序遍歷序列為 __

A. BDACEFG

B. DCBFGEA

C. ABCDEFG

D. GFEDCBA

答案：B

83.完全二叉樹的第4層有1個節點，該完全二叉樹總計有多少個節點( ).

A. 8

B. 9

C. 17

D. 16

答案：A

84.深度為k的完全二叉樹的第k層至少有（）個結點。

A.2k?1?1

B.2k?1+1

C.2k-1

D.2k+1

答案：C

85.具有65個結點的完全二叉樹其深度為（根的深度為1）：

A. 8

B. 7

C. 6

D. 5

答案：B

86.一個高度為h的滿二叉樹共有n個結點，其中有m個葉子結點，則有（）成立。

A. n=h+m

B. n=2m-1

C. m=h-1

D. h+m=2n

答案：B

87.一棵完全二叉樹上有62個結點，其中葉子結點的個數是（）

A. 31

B. 32

C. 33

D. 前述答案均不正確

答案：A

88.根據使用頻率為5個字符設計的哈夫曼編碼不可能是（）。

A. 111,110,10,01,00

B. 000,001,010,011,1

C. 100,11,10,1,0

D. 001,000,01,11,10

答案：C

89.(neuDS)在哈夫曼樹中，任何一個結點它的度都是（）。

A. 0或1

B. 1或2

C. 0或2

D. 0或1或2

答案：C

90.設給定權值總數有n 個，其哈夫曼樹的結點總數為( )。

A. 不確定

B. 2n

C. 2n+1

D. 2n-1

答案：D

91.對 n 個互不相同的符號進行哈夫曼編碼。若生成的哈夫曼樹共有 115 個結點，則 n 的值是：

A.56

B.57

C.58

D.60

答案：C

92.一段文本中包含對象{a,b,c,d,e}，其出現次數相應為{3,2,4,2,1}，則經過哈夫曼編碼后，該文本所占總位數為：

A. 12

B. 27

C. 36

D. 其它都不是

答案：B

93.在存儲數據時，通常不僅要存儲各數據元素的值，而且還要存儲（）。

A. 數據的處理方法

B. 數據元素的類型

C. 數據元素之間的關系

D. 數據的存儲方法

答案：C

94.下面程序的時間復雜度為（）。For(i = 0; i < m; i++)For(j = 0; j < n; j++ )A[i][j] = i?j;

A. O(m2m^2m2)

B. O(n2n^2n2)

C. O(m × n)

D. O(m + n)

答案：C

95.算法分析的兩個主要方面是（）。

A. 空間復雜度和時間復雜度

B. 正確性和簡明性

C. 可讀性和文檔性

D. 數據復雜性和程序復雜性

答案：A

96.順序表中第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（）。

A. 100

B. 105

C. 108

D. 110

答案：C

97.用數組表示線性表的優點是（）。

A. 便于插入和刪除操作

B. 便于隨機存取

C. 可以動態地分配存儲空間

D. 不需要占用一片相鄰的存儲空間

答案：B

98.帶頭結點的單鏈表|h|為空的判定條件是：

A. |h == NULL;|

B. |h->next == NULL;|

C. |h->next == h;|

D. |h != NULL;|

答案：B

99.假設有5個整數以1、2、3、4、5的順序被壓入堆棧，且出棧順序為3、5、4、2、1，那么為了獲得這樣的輸出，堆棧大小至少為：

A. 2

B. 3

C. 4

D. 5

答案：C

100.設一個棧的輸入序列是1、2、3、4、5，則下列序列中，是棧的合法輸出序列的是？

A. 3 2 1 5 4

B. 5 1 2 3 4

C. 4 5 1 3 2

D. 4 3 1 2 5

答案：A

101.為解決計算機主機與打印機之間速度不匹配問題，通常設置一個打印數據緩沖區，主機將要輸出的數據依次寫入該緩沖區，而打印機則依次從該緩沖區中取出數據。該緩沖區的邏輯結構應該是？

A. 堆棧

B. 隊列

C. 樹

D. 圖

答案：B

102.在一個不帶頭結點的非空鏈式隊列中,假設f和r分別為隊頭和隊尾指針,則插入s所指的結點運算是( )。

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

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

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

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

答案：B

103.二叉樹中第5層（根的層號為1）上的結點個數最多為：

A. 8

B. 15

C. 16

D. 32

答案：C

104.完全二叉樹的第5層有3個節點，該完全二叉樹總計有多少個節點( ).

A. 18

B. 19

C. 35

D. 34

答案：A

105.深度為k的完全二叉樹至少有(1)個結點，至多有(2)個結點。

A.(1)2k-1 (2)2k-1

B.(1)2k (2)2^{k}-1

C.(1)2^{k} (2)2^{k}+1

D.(1)2^{k-1}(2)2^{k}-1

答案：D

106.在一棵完全二叉樹中，其根的序號為1，（）可判定序號為 p和q 的兩個結點是否在同一層。

答案：A

107.如果一個完全二叉樹最底下一層為第六層（根為第一層）且該層共有8個葉結點，那么該完全二叉樹共有多少個結點？

A. 31

B. 39

C. 63

D. 71

答案：B

109.已知字符集{ a, b, c, d, e, f, g, h }。若各字符的哈夫曼編碼依次是 0100, 10, 0000, 0101, 001, 011, 11, 0001，則編碼序列 0100011001001011110101 的譯碼結果是

A.acgabfh

B.adbagbb

C.afbeagd

D.afeefgd

答案：D

110.由分別帶權為9、2、5、7的四個葉子結點構成一棵哈夫曼樹，該樹的帶權路徑長度為：

A. 23

B. 37

C. 44

D. 46

答案：C

111.設有13個值，用它們構成一棵哈夫曼樹，則該哈夫曼樹共有結點數是（）。

A. 13

B. 12

C. 26

D. 25

答案：D

112.設哈夫曼樹中有199個結點，則該哈夫曼樹中有（）個葉子結點。

A. 99

B. 100

C. 101

D. 102

答案：B

113.設一段文本中包含字符{a, b, c, d, e}，其出現頻率相應為{3, 2, 5, 1, 1}。則經過哈夫曼編碼后，文本所占字節數為：

A.40

B.36

C.25

D.12

答案：C

114.

A.集合結構

B.線性結構

C.樹形結構

D.圖狀結構

答案：A

115.數據結構可以從邏輯上分成 ▁▁▁▁▁ 兩大類。

A. 動態結構和靜態結構

B. 緊湊結構和非緊湊結構

C. 線性結構和非線性結構

D. 內部結構和外部結構

答案：C

116.以下關于數據結構的說法中錯誤的是（）。

A. 數據結構相同，對應的存儲結構也相同

B. 數據結構涉及數據的邏輯結構、存儲結構和施加其上的操作3個方面

C. 數據結構操作的實現與存儲結構有關

D. 定義邏輯結構時可不考慮存儲結構

答案：A

117.計算機所處理的數據一般具有某種關系，這是指（）。

A. 數據與數據之間存在的某種關系

B. 數據元素與數據元素之間存在的某種關系

C. 元素內數據項與數據項之間存在的某種關系

D. 數據文件內記錄與記錄之間存在的某種關系

答案：B

118.在計算機的存儲器中表示時，邏輯上相鄰的兩個元素對應的物理地址也是相鄰的，這種存儲結構稱之為( )

A. 邏輯結構

B. 順序存儲結構

C. 鏈式存儲結構

D. 以上都正確

答案：B

119.在計算機中存儲數據時，通常不僅要存儲各數據元素的值，而且還要存儲( )。

A. 數據的處理方法

B. 數據元素的類型

C. 數據元素之間的關系

D. 數據的存儲方法

答案：C

120.數據元素在計算機存儲器內表示時，物理相對位置和邏輯相對位置相同并且是連續的，稱之為（）。

A. 邏輯結構

B. 順序存儲結構

C. 鏈式存儲結構

D. 以上都不對

答案：B

121.在數據結構中，與所使用的計算機無關的是數據的( )結構。

A. 邏輯

B. 存儲

C. 邏輯和存儲

D. 物理

答案：A

122.通常要求同一邏輯結構中的所有數據元素具有相同的特性，這意味著( )

A. 數據元素具有同一特點

B. 不僅數據元素所包含的數據項的個數要相同，而且對應的數據項的類型要一致

C. 每個數據元素都一樣

D. 數據元素所包含的數據項的個數要相等

答案：B

123.以下屬于順序存儲結構優點的是（）。

A. 存儲密度大

B. 插入運算方便

C. 刪除運算方便

D. 可方便地用于各種邏輯結構的存儲表示

答案：A

124.被計算機加工的數據元素不是孤立的，它們彼此之間一般存在某種關系，通常把數據元素之間的這種關系稱為

A. 規則

B. 結構

C. 集合

D. 運算

答案：B

125.與數據元素本身的形式、內容、相對位置、個數無關的是數據的（）。

A. 存儲結構

B. 存儲實現

C. 邏輯結構

D. 運算實現

答案：C

126.數據在計算機內存中的表示是指（）。

A. 數據的存儲結構

B. 數據結構

C. 數據的邏輯結構

D. 數據元素之間的關系

答案：A

127.樹形結構中元素之間存在（）關系。

A. 一對一

B. 一對多

C. 多對多

D. 多對一

答案：B

128.算法的時間復雜度取決于（）

A. 問題的規模

B. 待處理數據的初態

C. A和B

答案：C

129.算法分析的兩個主要方面是( )

A. 空間復雜度和時間復雜度

B. 正確性和簡明性

C. 可讀性和文檔性

D. 數據復雜性和程序復雜性

答案：A

130.

A.O(m × n × t)

B.O(m + n + t)

C.O(m + n × t)

D.O(m × t + n)

答案：A

131.

A.n^{2}

B.n^{2}/2

C.n(n+1)

D.n(n+1)/2

答案：D

132.以下程序段的時間復雜度是 For (int i = 0; i ? i < n; i++) { printf("%d\n", i); }

答案：B

133.

答案：B

134.算法的時間復雜度取決于（）。

A. 問題的規模

B. 待處理數據的初態

C. 計算機的配置

D. A和B

答案：D

135.

A.O(n)

B.O(n^2)

C.O(1)

答案：D

136.

A.O(1)

C.O(n)

答案：B

137.

A.O(n)

B.O(100)

C.O(1)

D.O(404)

答案：C

138.下面敘述正確的是？

A. 算法的執行效率與數據的存儲結構無關

B. 算法的空間復雜度是指算法程序中指令（或語句）的條數

C. 算法的有窮性是指算法必須能在執行有限個步驟之后終止

D. 其他三種描述都不對

答案：C

139.計算算法的時間復雜度屬于（）。

A. 事前統計的方法

B. 事前分析估算的方法

C. 事后統計的方法

D. 事后分析估算的方法

答案：B

140.

A.O(N)

B.O(N^2)

C.O(N^3)

D.O(N^4)

答案：C

141.

A.O(N^3)

B.O(N^4)

C.O(N^5)

D.O(N^6)

答案：B

142.

答案：A

143.

A.O(n)

B.O(n ^ 2)

D.O(1)

答案：D

144.

B.O(n)

C.O(2 ^ n)

答案：D

145.

A.O(n ^ 2)

B.O(n)

答案：C

146.T(n)表示當輸入規模為n時的算法效率，以下算法中效率最優的是( )。

A.T(n)=T(n-1)+1,T(1)=1

B.T(n)=2n^2

C.T(n)=T(n/2)+1,T(1)=1

答案：C

147.對于順序存儲的長度為NNN的線性表，訪問結點和增加結點的時間復雜度為：

A.O(1), O(1)

B.O(1), O(N)

C.O(N), O(1)

D.O(N), O(N)

答案：B

148.在N個結點的順序表中，算法的時間復雜度為O(1)的操作是

答案：A

149.若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用哪種存儲方式最節省時間？

A. 雙鏈表

B. 單循環鏈表

C. 帶頭結點的雙循環鏈表

D. 順序表

答案：D

150.數組A[1..5,1..6]每個元素占5個單元，將其按行優先次序存儲在起始地址為1000的連續的內存單元中，則元素A[5,5]的地址為：

A. 1120

B. 1125

C. 1140

D. 1145

答案：C

151.(neuDS)線性表的順序存儲結構是一種( )

A. 隨機存取的存儲結構

B. 順序存取的存儲結構

C. 索引存取的存儲結構

D. 散列存取的存儲結構

答案：A

152.若線性表最常用的操作是存取第i個元素及其前驅的值，則采用( )存儲方式節省時間。

A.單鏈表

B.雙向鏈表

C.單循環鏈表

D.順序表

答案：D

解析：若線性表最常用的操作是存取第 i 個元素及其前驅元素的值,則采用存儲方式最節省運算時間

153.若長度為n的線性表采用順序結構，在第i個數據元素之前插入一個元素，需要它依次向后移動（）個元素。

A. n-i

B. n-i+1

C. n-i-1

D. i

答案：B

154.以下說法錯誤的是（）。

A. 求表長、定位這兩種運算在采用順序存儲結構時實現的效率不比采用鏈式存儲結構

B. 順序存儲的線性表可以隨機存取

C. 由于順序存儲要求連續的存儲區域，所以在存儲管理上不夠靈活

D. 線性表的鏈式存儲結構優于順序存儲結構

答案：D

155.線性表L=（a1, a2 ,……，an ）用一維數組表示，假定刪除線性表中任一元素的概率相同（都為1/n），則刪除一個元素平均需要移動元素的個數是（）。

A. n/2

B. (n+1)/2

C. (n-1)/2

D. n

答案：C

156.在包含 n 個數據元素的順序表中，▁▁▁▁▁ 的時間復雜度為 O(1)

答案：A

157.順序表是線性表的( )

A. 鏈式存儲結構

B. 順序存儲結構

C. 索引存儲結構

D. 散列存儲結構

答案：B

158.線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址

A. 必須是連續的

B. 連續或不連續都可以

C. 部分地址必須是連續的

D. 一定是不連續的

答案：B

159.線性表L在什么情況下適用于使用鏈式結構實現？

A. 需不斷對L進行刪除插入

B. 需經常修改L中的結點值

C. L中含有大量的結點

D. L中結點結構復雜

答案：A

160.鏈表不具有的特點是：

A. 插入、刪除不需要移動元素

B. 方便隨機訪問任一元素

C. 不必事先估計存儲空間

D. 所需空間與線性長度成正比

答案：B

161.在具有NNN個結點的單鏈表中，實現下列哪個操作，其算法的時間復雜度是O(N)O(N)O(N)？

A. 在地址為ppp的結點之后插入一個結點

B. 刪除開始結點

C. 遍歷鏈表和求鏈表的第iii個結點

D. 刪除地址為ppp的結點的后繼結點

答案：C

162.對于一個具有N個結點的單鏈表，在給定值為x的結點后插入一個新結點的時間復雜度為

A.O(1)

B.O(N/2)

C.O(N)

D.O(N^2)

答案：C

163.在單鏈表中，將 s 所指新結點插入到 p 所指結點之后，其語句應該為 ▁▁▁▁▁ 。

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

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

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

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

答案：B

164.從棧頂指針為|ST|的鏈棧中刪除一個結點且用|X|保存被刪結點的值，則執行：

A. |X= ST->data;|

B. |X= ST; ST = ST->next;|

C. |X= ST->data; ST = ST->next;|

D. |ST = ST->next; X= ST->data;|

答案：C

165.某隊列允許在其兩端進行入隊操作，但僅允許在一端進行出隊操作。若元素a、b、c、d、e依次入此隊列后再進行出隊操作，則不可能得到的出隊序列是：

A. b a c d e

B. d b a c e

C. e c b a d

D. d b c a e

答案：D

A. 2和0

B. 2和2

C. 2和4

D. 2和6

答案：A

A. |front+size|

B. |front+size-1|

C. |(front+size)%m|

D. |(front+size-1)%m|

答案：D

168.若用一個大小為6的數組來實現循環隊列，且當前rear和fornt的值分別為0和3。從當前隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為（）。

A. 1和5

B. 2和4

C. 4和2

D. 5和1

答案：B

169.設一數列的順序為1，2，3，4，5，6，通過隊列操作可以得到（）的輸出序列。

A. 3,2,5,6,4,1

B. 1,2,3,4,5,6

C. 6,5,4,3,2,1

D. 4,5,3,2,6,1

答案：B

170.在一個順序存儲的循環隊列中，若隊尾指針指向隊尾元素的后一個位置，則隊頭指針一般指向隊頭元素的（）。

A. 前一個位置

B. 后一個位置

C. 當前位置

D. 后兩個位置

答案：C

171.在由n個元素組成的順序存儲的循環隊列sq中，假定f和r分別為隊頭指針和隊尾指針，則判斷隊滿的條件是（）。

A. f ==（r+1）%n

B. （r - 1）%n==f

C. f == r

D. （f + 1）%n == f

答案：A

172.循環順序隊列中是否可以插入下一個元素（）。

A. 與隊頭指針和隊尾指針的值有關

B. 只與隊尾指針的值有關，與隊頭指針的值無關

C. 只與數組大小有關，與隊首指針和隊尾指針的值無關

D. 與曾經進行過多少次插入操作有關

答案：A

173.判斷一個循環隊列QU（最多元素為MaxSize）為空的條件是（）。

A. QU.front == QU.rear

B. QU.front != QU.rear

C. QU.front == (QU.rear + 1) % MaxSize

D. QU.front != (QU.rear + 1) % MaxSize

答案：A

174.(neuDS)在循環順序隊列中，假設以少用一個存儲單元的方法來區分隊列判滿和判空的條件，front和rear分別為隊首和隊尾指針，它們分別指向隊首元素和隊尾元素的下一個存儲單元，隊列的最大存儲容量為maxSize，則隊列的判空條件是（）。

A. front==rear

B. front!=rear

C. front==rear+1

D. front==(rear+1)% maxSize

答案：A

175.(neuDS)在循環順序隊列中，假設以少用一個存儲單元的方法來區分隊列判滿和判空的條件，front和rear分別為隊首和隊尾指針，它們分別指向隊首元素和隊尾元素的下一個存儲單元，隊列的最大存儲容量為maxSize，則隊列的判滿條件是（）。

A. front==rear

B. front!=rear

C. front==rear+1

D. front==(rear+1)% maxSize

答案：D

176.(neuDS)在循環順序隊列中，假設以少用一個存儲單元的方法來區分隊列判滿和判空的條件，front和rear分別為隊首和隊尾指針，它們分別指向隊首元素和隊尾元素的下一個存儲單元，隊列的最大存儲容量為maxSize，則隊列的長度是（）。

A. rear-front

B. rear-front+1

C. (rear-front+maxSize)%maxSize

D. (rear-front+1)%maxSize

答案：C

177.在一個鏈隊列中，front和rear分別為頭指針和尾指針，則插入一個結點s的操作為（）。

A. front=front->next

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

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

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

答案：C

178.在少用一個元素空間的循環隊列(m為最大隊列長度)是滿隊列的條件（）。

A.(rear+1)==front

B.front==(front+1)%m

C.rear==front

D.(rear+1)%m==front

答案：D

179.設一個循環隊列Q[maxSize]的隊頭指針為front，隊尾指針為rear，隊列最大容量為maxSize，此外該隊列再沒有其他數據成員，則隊列的隊滿條件是（）。

A. Q.front == Q.rear

B. Q.front+Q.rear >= maxSize

C. Q.front == (Q.rear +1) % maxSize

D. Q.rear == (Q.f ront+1) % maxSize

答案：C

180.關于棧和隊列的下列說法正確的是（）

A.棧的插入操作是在棧頂進行，插入時需將棧內所有元素后移；

B.棧是后進先出的結構，出棧時除了棧頂元素，其余元素無需移動；

C.循環隊列的出隊操作刪除的是隊頭元素，采用循環隊列存儲時，其余隊列元素均需移動；

D.鏈隊列的入隊操作在表尾進行，操作時間與隊列長度成正比

答案：B

181.循環隊列存儲在數組A[0..m]中，其頭尾指針分別為front和rear，頭指針front總是指向隊頭元素，尾指針rear總是指向隊尾元素的下一個位置，則入隊時的操作為（）。

A. rear=rear+1

B. rear=(rear+1)%(m-1)

C. rear=(rear+1)%m

D. rear=(rear+1)%(m+1)

答案：D

182.現有隊列 Q 與棧 S，初始時 Q 中的元素依次是{ 1, 2, 3, 4, 5, 6 }（1在隊頭），S 為空。若允許下列3種操作：（1）出隊并輸出出隊元素；（2）出隊并將出隊元素入棧；（3）出棧并輸出出棧元素，則不能得到的輸出序列是：

A. 1, 2, 5, 6, 4, 3

B. 2, 3, 4, 5, 6, 1

C. 3, 4, 5, 6, 1, 2

D. 6, 5, 4, 3, 2, 1

答案：C

183.循環隊列存儲在數組A[0..n-1]中，其頭尾指針分別為f和r，頭指針f總是指向隊頭元素，尾指針r總是指向隊尾元素的下一個位置，假設隊列不空，元素出隊時頭尾指針的操作為（）。

A. f=(f+1)%n

B. f=f+1

C. r=(r+1)%n

D. f=(f+1)%(n-1)

答案：A

184.用鏈接方式存儲的隊列，在進行刪除運算時（）。

A. 僅修改頭指針

B. 僅修改尾指針

C. 頭、尾指針都要修改

D. 頭、尾指針可能都要修改

答案：D

185.已知循環隊列的存儲空間為數組A[21]，front指向隊頭元素的前一個位置，rear指向隊尾元素，假設當前front和rear的值分別為8和3，則該隊列的長度為（）。

A. 5

B. 6

C. 16

D. 17

答案：C

186.循環隊列的引入，目的是為了克服( )。

A. 假溢出問題

B. 真溢出問題

C. 空間不夠用

D. 操作不方便

答案：A

187.循環隊列的隊滿條件為 ( )。

A. (sq.rear+1) % maxsize ==(sq.front+1) % maxsize

B. (sq.front+1) % maxsize ==sq.rear

C. (sq.rear+1) % maxsize ==sq.front

D. sq.rear ==sq.front

答案：C

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

A. 都是先進先出

B. 都是先進后出

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

D. 沒有共同點

答案：C

189.已知初始為空的隊列 Q 的一端僅能進行入隊操作，另外一端既能進行入隊操作又能進行出隊操作。若 Q 的入隊序列是 1、2、3、4、5，則不能得到的出隊序列是：

A. 5、4、3、1、2

B. 5、3、1、2、4

C. 4、2、1、3、5

D. 4、1、3、2、5

答案：D

190.在下述結論中，正確的是：①只有一個結點的二叉樹的度為0;②二叉樹的度為2；③二叉樹的左右子樹可任意交換；④深度為K的完全二叉樹的結點個數小于或等于深度相同的滿二叉樹。

A. ①④

B. ②④

C. ①②③

D. ②③④

答案：A

191.完全二叉樹的第6層有2個節點，該完全二叉樹總計有多少個節點( ).

A. 33

B. 34

C. 66

D. 65

答案：A

192.完全二叉樹的第8層有7個節點，該完全二叉樹總計有多少個節點( ).

A. 134

B. 135

C. 263

D. 262

答案：A

193.設高為h的二叉樹（規定葉子結點的高度為1）只有度為0和2的結點，則此類二叉樹的最少結點數和最多結點數分別為：

答案：B

194.設一棵非空完全二叉樹 TTT 的所有葉節點均位于同一層，且每個非葉結點都有 2個子結點。若 TTT 有 kkk 個葉結點，則 TTT 的結點總數是：

B.2k

C.k^2

答案：A

解析：一棵非空完全二叉樹T的所有葉結點均位于同一層，且每個非葉結點都有2個子結點就是滿二叉樹。?則有 k = 2^(h-1)?T的結點總數n=2^(h-1)-1+k = 2k-1

195.已知一棵完全二叉樹的第6層（設根為第1層）有8個葉結點，則該完全二叉樹的結點個數最多是：

A. 39

B. 52

C. 111

D. 119

答案：C

196.一棵完全二叉樹上有1001個結點，其中葉子結點的個數是（）。

A. 250

B. 500

C. 254

D. 501

答案：D

197.具有1102個結點的完全二叉樹一定有__個葉子結點。

A. 79

B. 551

C. 1063

D. 不確定

答案：B

198.對NNN（N≥2N\ge 2N≥2）個權值均不相同的字符構造哈夫曼樹。下列關于該哈夫曼樹的敘述中，錯誤的是：

A. 樹中一定沒有度為1的結點

B. 樹中兩個權值最小的結點一定是兄弟結點

C. 樹中任一非葉結點的權值一定不小于下一層任一結點的權值

D. 該樹一定是一棵完全二叉樹

答案：D

199.為五個使用頻率不同的字符設計哈夫曼編碼，下列方案中哪個不可能是哈夫曼編碼？

A. 00，100，101，110，111

B. 000，001，01，10，11

C. 0000，0001，001，01，1

D. 000，001，010，011，1

答案：A

200.下列敘述錯誤的是（）。

A.一棵哈夫曼樹的帶權路徑長度等于其中所有分支結點的權值之和

B.當一棵具有n 個葉子結點的二叉樹的WPL 值為最小時，稱其樹為哈夫曼樹，其二叉樹的形狀是唯一的

C.哈夫曼樹是帶權路徑長度最短的樹，路徑上權值較大的結點離根較近

D.哈夫曼樹的結點個數不能是偶數

答案：B

解析：樹的形狀是唯一的

202.已知字符集{ a, b, c, d, e, f }，若各字符出現的次數分別為{ 6, 3, 8, 2, 10, 4 }，則對應字符集中各字符的哈夫曼編碼可能是：

A.00, 1011, 01, 1010, 11, 100

B.00, 100, 110, 000, 0010, 01

C.10, 1011, 11, 0011, 00, 010

D.0011, 10, 11, 0010, 01, 000

答案：A

203.由權值分別為3，8，6，2，5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（）。

A. 24

B. 48

C. 72

D. 53

答案：D

204.由權值分別為8，4，6，5，7的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為（）。

A. 30

B. 60

C. 69

D. 90

答案：C

205.下列說法不正確的是：

A. 圖的遍歷是從給定的源點出發每一個頂點僅被訪問一次

B. 遍歷的基本算法有兩種：深度遍歷和廣度遍歷

C. 圖的深度遍歷是一個遞歸過程

D. 圖的深度遍歷不適用于有向圖

答案：D

206.圖的深度優先遍歷類似于二叉樹的：

A. 先序遍歷

B. 中序遍歷

C. 后序遍歷

D. 層次遍歷

答案：A

207.如果從無向圖的任一頂點出發進行一次深度優先搜索可訪問所有頂點，則該圖一定是：

A. 連通圖

B. 完全圖

C. 有回路的圖

D. 一棵樹

答案：A

208.

A.V1,V2,V3,V4,V7,V6,V5

B.V1,V5,V4,V7,V6,V2,V3

C.V1,V5,V6,V4,V7,V2,V3

D.V1,V5,V4,V7,V6,V3,V2

答案：D

209.圖的深度優先遍歷遞歸算法，要用一種稱為（）的數據結構。

A. 棧

B. 隊列

C. 順序表

D. 鏈表

答案：A

210.如果無向圖G必須進行兩次廣度優先搜索才能訪問其所有頂點，則下列說法中不正確的是：

A. G肯定不是完全圖

B. G中一定有回路

C. G一定不是連通圖

D. G有2個連通分量

答案：B

211.圖的廣度優先遍歷類似于二叉樹的：

A. 先序遍歷

B. 中序遍歷

C. 后序遍歷

D. 層次遍歷

答案：D

212.以下算法的功能是（）。Void graph1( adjmatrix GA, int i, int n, int ?visited){ int k, j; Queue q;Cout<<i<<‘ ‘; visited[i]= 1; InitQueue( q);EnQueue (q, i); while ( !EmptyQueue(q) ) { k= OutQueue (q);For( j=0; j<n; j++) { if ( GA[k][j] != 0 && GA[k][j] != MaxValue && !visited[j] ) {Cout<<j<<‘ ‘; visited[j] = 1;EnQueue (q, j); } } }}

A. 從頂點i出發進行深度優先遍歷

B. 從頂點i出發進行廣度優先遍歷

C. 輸出頂點i的各鄰接點

D. 輸出從頂點i出發到各頂點的路徑

答案：B

213.在圖的廣度優先遍歷算法中用到一個隊列，每個頂點最多進隊____次。

A. 1

B. 2

C. 3

D. 不確定

答案：A

214.用鄰接表表示圖進行廣度優先遍歷時，通常借助（）來實現算法。