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

1、深度為5的完全二叉樹的結點數不可能是

√A) 15 B) 16 C) 17 D) 18

2、下列敘述中正確的是

√A) 循環隊列是順序存儲結構 B) 循環隊列是鏈式存儲結構

C) 循環隊列是非線性結構 D) 循環隊列的插入運算不會發生溢出現象

3、下列敘述中正確的是

A) 所有數據結構必須有根結點 B) 所有數據結構必須有終端結點（即葉子結點）

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

√D) 沒有根結點或沒有葉子結點的數據結構一定是非線性結構

4、下列關於算法的描述中錯誤的是

A) 算法強調動態的執行過程，不同於靜態的計算公式

B) 算法必須能在有限個步驟之後終止

C) 算法設計必須考慮算法的複雜度

√D) 算法的優劣取決於運行算法程序的環境

5、線性表的鏈式存儲結構與順序存儲結構相比，鏈式存儲結構的優點有

A) 節省存儲空間 √B) 插入與刪除運算效率高C) 便於查找 D) 排序時減少元素的比較次數

6、深度為７的完全二叉樹中共有125個結點，則該完全二叉樹中的葉子結點數為

A) 62 √B) 63 C) 64 D) 65

7、下列敘述中正確的是

A) 所謂有序表是指在順序存儲空間內連續存放的元素序列

B) 有序表只能順序存儲在連續的存儲空間內

√C) 有序表可以用鏈接存儲方式存儲在不連續的存儲空間內

D) 任何存儲方式的有序表均能採用二分法進行查找

8、下列敘述中正確的是

A) 結點中具有兩個指針域的鏈表一定是二叉鏈表

√B) 結點中具有兩個指針域的鏈表可以是線性結構，也可以是非線性結構

C) 二叉樹只能採用鏈式存儲結構

D) 循環鏈表是非線性結構

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

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

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

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

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

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

10、帶鏈的棧與順序存儲的棧相比，其優點是

A) 入棧與退棧操作方便 B) 可以省略棧底指針

√C) 入棧操作時不會受棧存儲空間的限制而發生溢出

11、某二叉樹的前序序列為ABCD，中序序列為DCBA，則後序序列為

A) BADC √B) DCBA C) CDAB D) ABCD

12、下列關於算法複雜度敘述正確的是

A) 最壞情況下的時間複雜度一定高於平均情況的時間複雜度

√B) 時間複雜度與所用的計算工具無關

C) 對同一個問題，採用不同的算法，則它們的時間複雜度是相同的

D) 時間複雜度與採用的算法描述語言有關

13、設有棧S和隊列Q，初始狀態均為空。首先依次將A,B,C,D,E,F入棧，然後從棧中退出三個元素依次入隊，再將X,Y,Z入棧後，將棧中所有元素退出並依次入隊，最後將隊列中所有元素退出，則退隊元素的順序為

A) DEFXYZABC √B) FEDZYXCBA C) FEDXYZCBA D) DEFZYXABC

14、下列敘述中正確的是

A) 有兩個指針域的鏈表稱為二叉鏈表B) 循環鏈表是循環隊列的鏈式存儲結構

C) 帶鏈的棧有棧頂指針和棧底指針，因此又稱為雙重鏈表

√D) 結點中具有多個指針域的鏈表稱為多重鏈表

15、某二叉樹共有845個結點，其中葉子結點有45個，則度為1的結點數為

A) 400 B) 754 √C) 756 D) 不確定

16、設數據集合為D={ 1,3,5,7,9 }，D上的關係為R，下列數據結構B=（D，R）中為非線性結構的是

A) R={ (5,1), (7,9), (1,7), (9,3) }

B) R={ (9,7), (1,3), (7,1), (3,5) }

C) R={ (1,9), (9,7), (7,5), (5,3) }

√D) R={ (1,3), (3,5), (5,9) }

17、深度為7的二叉樹共有127個結點，則下列說法中錯誤的是

√A) 該二叉樹有一個度為1的結點 B) 該二叉樹是滿二叉樹

C) 該二叉樹是完全二叉樹 D) 該二叉樹有64個葉子結點

18、下列敘述中正確的是

A) 非線性結構只能採用鏈式存儲結構B) 非線性結構只能用多重鏈表表示

C) 所有數據結構既可以採用順序存儲結構，也可以採用鏈式存儲結構

√D) 有的非線性結構也能採用順序存儲結構

19、某二叉樹的中序序列為BDCA，後序序列為DCBA，則前序序列為

A) DCBA B) BDCA √C) ABCD D) BADC

20、某完全二叉樹共有256個結點，則該完全二叉樹的深度為

A) 7 B) 8 √C) 9 D) 10