1、若某線性表中最常用的操作是在最後一個元素之後插入一個元素和删除第一個元素，則采用____存儲方式最節省運算時間。
- • A：單連結清單
- • B：僅有頭指針的單循環連結清單
- • C：雙連結清單
- • D：僅有尾指針的單循環連結清單
解析
選項A、單連結清單插入最後一個元素需要周遊連結清單到最後一個元素。 選項B、僅有頭指針，删除第一個元素友善，但是末尾插入一個元素同選項A。 選項C、雙連結清單，友善來回周遊但是末尾插入一個元素依舊需要周遊整個連結清單。 選項D、最節約運算時間。
答案：D
2、設某連結清單中最常用的操作是在連結清單的尾部插入或删除元素，則選用下列____存儲方式最節省運算時間。
- • A：單向連結清單
- • B：單向循環連結清單
- • C：雙向連結清單
- • D：雙向循環連結清單
解析
某連結清單中最常用的操作是在連結清單的尾部插入或删除元素時雙向循環清單最節省運算時間。
答案：D
3、在含有n個結點的二叉排序樹中查找某個關鍵字的結點時，最多進行（）次比較。
- • A：n/2
- • B：
- • C：
- • D：n
解析
當輸入序列是一個有序序列時，構造的二叉排序樹是一個單支樹，當查找一個不存在的關鍵字值或最後一個結點的關鍵字值時，需要n次比較。
答案：D
4、含有20個結點的平衡二叉樹的最大深度為（）。
- • A：4
- • B：5
- • C：6
- • D：7
解析
平衡二叉樹結點數的遞推公式為=1，=1，=2，=1++（h為平衡二叉樹高度，為構造此高度的平衡二叉樹所需的最少結點數）。通過遞推公式可得，構造5層平衡二叉樹至少需要12個結點，構造6層至少需要20個結點。
答案：C
5、具有5層結點的AVL至少有（）個結點。
- • A：10
- • B：12
- • C：15
- • D：17
解析
設表示高度為h的平衡二叉樹中含有的最少結點數，則有=1，=2，=++1，由此求出=12，對應的AVL如下圖所示。
答案：B
6、下列關于紅黑樹的說法中，不正确的是（）。
- • A：一棵含有n個結點的紅黑樹的高度至多為2
- • B：如果一個結點是紅色的，則它的父結點和孩子結點都是黑色的
- • C：從一個結點到其子孫結點的所有路徑上包含相同數量的黑結點
- • D：紅黑樹的查詢效率一般要優于含有相同結點數的AVL樹
解析
選項A、B和C都是紅黑樹的性質。AVL是高度平衡的二叉查找樹，紅黑樹是适度平衡的二叉查找樹，從這一點可以看出AVL的查找效率往往更優。
答案：D
7、下列關于紅黑樹和AVL樹的描述中，不正确的是（）。
- • A：兩者都屬于自平衡的二叉樹
- • B：兩者查找、插入、删除的時間複雜度都相同
- • C：紅黑樹插入和删除過程至多有2次旋轉操作
- • D：紅黑樹的任一結點的左右子樹高度之差不超過2倍
解析
自平衡的二叉排序樹是指在插入和删除時能自動調整以保持其所定義的平衡性，紅黑樹和AVL都屬于自平衡二叉樹，A正确。
在紅黑樹中删除結點時，情況1可能變為情況2、3或4，情況2會變為情況3，可能會出現旋轉次數超過2次的情況，故C錯誤。
答案：C
8、下列關于紅黑樹的說法中，正确的是（）。
- • A：紅黑樹是一種特殊的平衡二叉樹
- • B：如果紅黑樹的所有結點都是黑色的，那麼它一定是一棵滿二叉樹
- • C：紅黑樹的任何一個分支結點都有兩個非空孩子結點
- • D：紅黑樹的子樹也一定是紅黑樹
解析
答案：B
9、将關鍵字1,2,3,4,5,6,7一次插入初始為空的紅黑樹T，則T中紅結點的個數是（）。
- • A：1
- • B：2
- • C：3
- • D：4
解析
關鍵字1,2,3,4,5,6,7一次插入紅黑樹後的形态變化如下圖所示：
答案：C
10、将關鍵字5,4,3,2,1一次插入初始為空的紅黑樹T，則T的最終形态是（）。
解析
關鍵字5,4,3,2,1一次插入紅黑樹後的形态變化如下：