計算機二級基礎知識試題及答案

　　選擇題-公共基礎知識-數據結構與算法(共32題)

第1組

161) 下列敍述中正確的是

A)循環隊列是線性結構

B)循環隊列是線性邏輯結構

C)循環隊列是鏈式存儲結構

D)循環隊列是非線性存儲結構

答案：A

162) 設某棵樹的度為3，其中度為3,2,1的結點個數分別為3,0,4。則該樹中的葉子結點數為

A)7

B)8

C)6

D)不可能有這樣的樹

答案：A

163) 設有一個棧與一個隊列的初始狀態均為空。現有一個序A,B,C,D,E,F,G,H，先分別將序列中的前4個元素依次入棧，後4個元素依次入隊;然後分別將棧中的元素依次退棧，再將隊列中的元素依次退隊。最後得到的序列為

A)D,C,B,A,E,F,G,H

B)D,C,B,A,H,G,F,E

C)A,B,C,D,E,F,G,H

D)A,B,C,D,H,G,F,E

答案：A

164) 下列敍述中錯誤的是

A)具有兩個以上指針域的鏈式結構一定屬於非線性結構

B)具有兩個以上葉子結點的數據結構一定屬於非線性結構

C)具有兩個根結點的數據結構一定屬於非線性結構

D)具有一個根結點且只有一個葉子結點的數據結構也可能是非線性結構

答案：A

第2組

165) 下列結構中屬於線性結構鏈式存儲的是

A)雙向鏈表

B)循環隊列

C)二叉鏈表

D)二維數組

答案：A

166) 下列敍述中錯誤的是

A)循環鏈表的存儲空間是連續的.

B)循環鏈表中有一個表頭結點

C)循環鏈表的表頭指針與循環鏈表中最後一個結點的指針均指向表頭結點

D)循環鏈表實現了空表與非空表運算的統一

答案：A

167)度為3的一棵樹共有30個結點，其中度為3,1的結點個數分別為3,4。 則該樹中的葉子結點數為

A)15

B)16

C)14

D)不可能有這樣的樹

答案：A

168) 在長度為97的順序有序表中作二分查找，最多需要的比較次數為

A)7

B)96

C)48

D)6

答案：A

第3組

169) 下列結構中屬於非線性結構的是

A)二叉鏈表

B)二維數組

C)循環隊列

D)雙向鏈表

答案：A

【解析】二叉鏈表是二叉樹的物理實現，是一種存儲結構，不屬於線性結構。故答案為A。

170) 從表中任何一個結點位置出發就可以不重複地訪問到表中其他所有結點的鏈表是

A)循環鏈表

B)雙向鏈表

C)單向鏈表

D)二叉鏈表

答案：A

155) 在帶鏈隊列中，經過一系列正常的操作後，如果front=rear，則隊列中的元素個數為

A)0 或 1

B)0

C)1

D)隊列滿

答案：A

172) 設某棵樹的度為3，其中度為3,1,0的結點個數分別為3,4,15。則該樹中總結點數為

A)30

B)22

C)35

D)不可能有這樣的樹

答案：A

第4組

173) 下列敍述中正確的是

A)數組是長度固定的線性表

B)矩陣是非線性結構

C)對線性表只能作插入與刪除運算

D)線性表中各元素的數據類型可以不同

答案：A

174) 在快速排序法中，每經過一次數據交換(或移動)後

A)能消除多個逆序

B)只能消除一個逆序

C)不會產生新的逆序

D)消除的逆序個數一定比新產生的逆序個數多

答案：A

175) 線性表的長度為n。在最壞情況下，比較次數為n-1的算法是

A)尋找最大項

B)同時尋找最大項與最小項

C)順序查找

D)有序表的插入

答案：A

176) 設某棵樹的度為3，其中度為2,1,0的結點個數分別為3,4,15。則該樹中總結點數為

A)不可能有這樣的樹

B)30

C)22

D)35

答案：A

第5組

177) 下列敍述中錯誤的是

A)只有一個根結點和一個葉子結點的結構必定是線性結構

B)非空線性結構中只有一個結點沒有前件

C)非空線性結構中只有一個結點沒有後件

D)向量是線性結構

答案：A

178) 在希爾排序法中，每經過一次數據交換後

A)能消除多個逆序

B)只能消除一個逆序

C)不會產生新的逆序

D)消除的逆序個數一定比新產生的逆序個數多

答案：A

151) 帶鏈棧空的條件是

A)top=bottom=NULL

B)top=-1 且 bottom=NULL

C)top=NULL 且 bottom=-1

D)top=bottom=-1

答案：A

180) 下列敍述中正確的是

A)所有的線性結構都可以採用順序存儲結構

B)能採用順序存儲的必定是線性結構

C)具有兩個以上指針的鏈表必定是非線性結構

D)循環隊列是隊列的鏈式存儲結構

答案：A

第6組

94) 設某二叉樹中共有140個結點，其中有40個度為1的結點。則

A)該二叉樹中有51個葉子結點

B)該二叉樹中有50個葉子結點

C)該二叉樹中有51個度為2的結點

D)該二叉樹中有50個度為2的結點

E)不可能有這樣的二叉樹

答案：E

182) 設二叉樹的前序序列為ABDEGHCFIJ，中序序列為DBGEHACIFJ。則按層次輸出(從上到下，同一層從左到右)的序列為

A)ABCDEFGHIJ

B)DGHEBIJFCA

C)JIHGFEDCBA

D)GHIJDEFBCA

答案：A

183) 設循環隊列的存儲空間為Q(1: 50)，初始狀態為front=rear=50。經過一系列正常的操作後，front-1=rear。為了在該隊列中尋找值最大的元素，在最壞情況下需要的比較次數為

A)48

B)49

C)1

D)0

答案：A

184) 設順序表的長度為40，對該表進行冒泡排序。在最壞情況下需要的比較次數為

A)780

B)820

C)40

D)41

答案：A

第7組

185) 設表的長度為n。在下列算法中，最壞情況下時間複雜度最高的是

A)希爾排序

B)循環鏈表中尋找最大項

C)有序鏈表查找

D)堆排序

答案：A

186) 設循環隊列的存儲空間為Q(1: 50)，初始狀態為front=rear=50。經過一系列正常的操作後，front=rear-1。 為了在該隊列中尋找值最大的元素，在最壞情況下需要的比較次數為

A)0

B)1

C)49

D)50

答案：A

187) 設二叉樹的前序序列為ABDEGHCFIJ，中序序列為DBGEHACIFJ。則後序序列為

A)DGHEBIJFCA

B)JIHGFEDCBA

C)GHIJDEFBCA

D)ABCDEFGHIJ

答案：A

188) 設順序表的長度為16，對該表進行簡單插入排序。在最壞情況下需要的比較次數為

A)120

B)60

C)30

D)15

答案：A

第8組

189) 下列結構中為非線性結構的是

A)樹

B)向量

C)二維表

D)矩陣

答案：A

190) 設表的長度為n。在下列結構所對應的算法中，最壞情況下時間複雜度最低的是

A)循環鏈表中尋找最大項

B)有序鏈表查找

C)堆排序

D)希爾排序

答案：A

159) 帶鏈隊列空的條件是

A)front=rear=NULL

B)front=-1 且 rear=NULL

C)front=NULL 且 rear=-1

D)front=rear=-1

答案：A

192) 設二叉樹的後序序列為DGHEBIJFCA，中序序列為DBGEHACIFJ。則前序序列為

A)ABDEGHCFIJ

B)JIHGFEDCBA

C)GHIJDEFBCA

D)ABCDEFGHIJ

答案：A