'計算機二級公共基礎部分選擇題練習（5）'

1、一棵二叉樹中共有80個葉子結點與70個度為1的結點，則該二叉樹中的總結點數為

A) 219 √B) 229 C) 230 D) 231

2、對長度為10的線性表進行冒泡排序，最壞情況下需要比較的次數為

A) 9 B) 10 √C) 45 D) 90

3、下列敘述中正確的是

A) 算法的效率只與問題的規模有關，而與數據的存儲結構無關

√B) 算法的時間複雜度是指執行算法所需要的計算工作量

C) 數據的邏輯結構與存儲結構是一一對應的

D) 算法的時間複雜度與空間複雜度一定相關

4、下列敘述中正確的是

A) 線性錶鏈式存儲結構的存儲空間一般要少於順序存儲結構

B) 線性錶鏈式存儲結構與順序存儲結構的存儲空間都是連續的

√C) 線性錶鏈式存儲結構的存儲空間可以是連續的，也可以是不連續的

5、某二叉樹共有12個結點，其中葉子結點只有1個。則該二叉樹的深度為（根結點在第1層）

A) 3 B) 6 C) 8 √D) 12

6、對長度為n的線性表作快速排序，在最壞情況下，比較次數為

A) n B) n-1 C) n(n-1) √D) n(n-1)/2

7、下列敘述中正確的是

A) 有且只有一個根結點的數據結構一定是線性結構

B) 每一個結點最多有一個前件也最多有一個後件的數據結構一定是線性結構

C) 有且只有一個根結點的數據結構一定是非線性結構

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

8、下列敘述中錯誤的是

A) 在雙向鏈表中，可以從任何一個結點開始直接遍歷到所有結點

B) 在循環鏈表中，可以從任何一個結點開始直接遍歷到所有結點

√C) 在線性單鏈表中，可以從任何一個結點開始直接遍歷到所有結點

D) 在二叉鏈表中，可以從根結點開始遍歷到所有結點

9、某二叉樹共有13個結點，其中有4個度為1的結點，則葉子結點數為

√A) 5 B) 4 C) 3 D) 2

10、設棧的順序存儲空間為S(1: 50),初始狀態為top=0。現經過一系列入棧與退棧運算後，top=20，則當前棧中的元素個數為

A) 30 B) 29 √C) 20 D) 19

11、下列敘述中正確的是

A) 棧與隊列都只能順序存儲 √B) 循環隊列是隊列的順序存儲結構

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

12、設某二叉樹的前序序列為ABC，中序序列為CBA，則該二叉樹的後序序列為

A) BCA √B) CBA C) ABC D) CAB

13、下列排序方法中，最壞情況下時間複雜度最小的是

A) 冒泡排序 B) 快速排序 √C) 堆排序 D) 直接插入排序

14、為了對有序表進行對分查找，則要求有序表

√A) 只能順序存儲

B) 只能鏈式存儲

C) 可以順序存儲也可以鏈式存儲

D) 任何存儲方式

15、設某二叉樹的後序序列為CBA，中序序列為ABC，則該二叉樹的前序序列為

A) BCA B) CBA √C) ABC D) CAB

16、下列敘述中正確的是

A) 存儲空間不連續的所有鏈表一定是非線性結構

B) 結點中有多個指針域的所有鏈表一定是非線性結構

C) 能順序存儲的數據結構一定是線性結構

√D) 帶鏈的棧與隊列是線性結構

17、算法時間複雜度的度量方法是

A) 算法程序的長度 √B) 執行算法所需要的基本運算次數C) 執行算法所需要的所有運算次數D) 執行算法所需要的時間

18、設循環隊列為Q(1: m)，初始狀態為front=rear=m。現經過一系列的入隊與退隊運算後，front=rear=1，則該循環隊列中的元素個數為

A) 1 B) 2 C) m-1 √D) 0或m

19、在最壞情況下

A) 快速排序的時間複雜度比冒泡排序的時間複雜度要小

B) 快速排序的時間複雜度比希爾排序的時間複雜度要小

√C) 希爾排序的時間複雜度比直接插入排序的時間複雜度要小

D) 快速排序的時間複雜度與希爾排序的時間複雜度是一樣的

20、在深度為7的滿二叉樹中，度為2的結點個數為

A) 64 √B) 63 C) 32 D) 31