計算機二級基礎知識試題及答案
選擇題-公共基礎知識-資料結構與演算法(共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
