1、在下圖所示的平衡二叉樹中插入關(guān)鍵字48后得到一棵新平衡二叉樹，在新平衡二叉樹中，關(guān)鍵字37所在結(jié)點的左、右子結(jié)點中保存的關(guān)鍵字分別是（）。
- A：13,48
- B：24,48
- C：24,53
- D：24,90
解析
插入48后，該二叉樹根結(jié)點的平衡因子由-1變?yōu)?2，失去平衡，需要進行兩次旋轉(zhuǎn)（先右旋后左旋）操作。
答案：C
2、若平衡二叉樹的高度為6，且所有非葉子結(jié)點的平衡因子均為1，則該平衡二叉樹的結(jié)點總數(shù)為（）。
- A：12
- B：20
- C：32
- D：33
解析
所有非葉結(jié)點的平衡因子均為1，即平衡二叉樹滿足平衡的最少結(jié)點情況，如下圖所示。對于高度為n、左右子樹的高度分別為n-1和n-2、所有非葉結(jié)點的平衡因子均為1的平衡二叉樹，計算總結(jié)點數(shù)的公式為=
+
+1，
=1，
=2,
=2+1+1=4，可推出
=20。
畫圖法：先畫出
答案：B
3、若將關(guān)鍵字1,2,3,4,5,6,7依次插入初始為空的平衡二叉樹T，則T中平衡因子為0的分支結(jié)點的個數(shù)是（）。
- A：0
- B：1
- C：2
- D：3
解析
利用7個關(guān)鍵字構(gòu)建平衡二叉樹T，平衡因子為0的分支結(jié)點個數(shù)為3，構(gòu)建的平衡二叉樹及構(gòu)造與調(diào)整過程如下圖所示。
答案：D
4、現(xiàn)有一棵無重復(fù)關(guān)鍵字的平衡二叉樹（AVL），對其進行中序遍歷可得到一個降序序列。下列關(guān)于該平衡二叉樹的敘述中，正確的是（）。
- A：根結(jié)點的度一定為2
- B：樹中最小元素一定是葉結(jié)點
- C：最后插入的元素一定是葉結(jié)點
- D：樹中最大元素一定是無左子樹
解析
只有兩個結(jié)點的平衡二叉樹的根結(jié)點的度為1，A錯誤。
中序遍歷后可以得到一個降序序列，樹中最小元素一定無左子樹（可能有右子樹），因此不一定是葉結(jié)點，B錯誤。
最后插入的結(jié)點可能會導(dǎo)致平衡調(diào)整，而不一定是葉結(jié)點，C錯誤。
答案：D
5、在任意一棵非空平衡二叉樹（AVL樹）
中，刪除某結(jié)點v之后形成平衡二叉樹
，再將v插入形成平衡二叉樹
。下列關(guān)于與的敘述中，正確的是（）。
Ⅰ、若v是的葉結(jié)點，則
與
可能不相同
Ⅱ、若v不是的葉結(jié)點，則
與
一定不相同
Ⅲ、若v不是的葉結(jié)點，則
與
一定相同
- A：僅Ⅰ
- B：僅Ⅱ
- C：僅Ⅰ、Ⅱ
- D：僅Ⅰ、Ⅲ
解析
在非空平衡二叉樹中插入結(jié)點，在失去平衡調(diào)整前，一定插入在葉結(jié)點的位置。
若刪除的是的葉結(jié)點，則刪除后平衡二叉樹可能不會失去平衡，即不會發(fā)生調(diào)整，再插入此結(jié)點得到的二叉平衡樹
與
相同；若刪除后平衡二叉樹失去平衡而發(fā)生調(diào)整，再插入結(jié)點得到的二叉平衡樹
與
可能不同。Ⅰ正確。
對于比較絕對的說法Ⅱ和Ⅲ，通常只需舉出反例即可。
例如，如下圖所示，刪除結(jié)點0，平衡二叉樹失衡調(diào)整，再插入結(jié)點0后，平衡二叉樹和以前不同。
若刪除的是
若刪除的是的非葉結(jié)點，且刪除和插入操作后導(dǎo)致了平衡二叉樹的調(diào)整，則該結(jié)點有可能通過旋轉(zhuǎn)后繼續(xù)變成非葉結(jié)點，
與
相同。例如，如下圖所示，刪除結(jié)點2，用右孩子結(jié)點3填補，再插入結(jié)點2，平衡二叉樹失衡調(diào)整，調(diào)整后的平衡二叉樹和以前相同。
答案：A
6、下圖所示是一棵（）。
- A：4階B樹
- B：4階B+樹
- C：3階B樹
- D：3階B+樹
解析
關(guān)鍵字數(shù)量比子樹數(shù)量少1，所以不是B+樹，而是B樹。又因為m階B樹結(jié)點關(guān)鍵字數(shù)最多為m-1，有一個結(jié)點關(guān)鍵字個數(shù)為3，所以不可能為3階。
答案：A
7、下列關(guān)于m階B樹的說法中，錯誤的是（）。
- A：根結(jié)點至多有m棵子樹
- B：所有葉結(jié)點都在同一層次上
- C：非葉結(jié)點至少有m/2（m為偶數(shù)）或（m+1）/2（m為奇數(shù)）棵子樹
- D：根結(jié)點中的數(shù)據(jù)是有序的
解析
除根結(jié)點外的所有非終端結(jié)點至少有m/2
棵子樹。對于根結(jié)點，最多有m棵子樹，若其不是葉結(jié)點，則至少有2棵子樹。
答案：C
8、以下關(guān)于m階B樹的說法中，正確的是（）。
Ⅰ、每個結(jié)點至少有兩棵非空子樹
Ⅱ、樹中每個結(jié)點至多有m-1個關(guān)鍵字
Ⅲ、所有葉結(jié)點在同一層
Ⅳ、插入一個元素引起B(yǎng)樹結(jié)點分裂后，樹長高一層
- A：Ⅰ、Ⅱ
- B：Ⅱ、Ⅲ
- C：Ⅲ、Ⅳ
- D：Ⅰ、Ⅱ、Ⅳ
解析
每個非根的內(nèi)部結(jié)點必須至少有m/2
棵子樹，而根結(jié)點至少要有兩棵子樹，所以Ⅰ不正確。Ⅱ、Ⅲ顯然正確。對于Ⅳ，插入一個元素引起B(yǎng)樹結(jié)點分裂后，只要從根結(jié)點到該元素插入位置的路徑上至少有一個結(jié)點未滿，B樹就不會長高，如圖1所示；只有當結(jié)點的分裂傳到根結(jié)點，并使根結(jié)點也分裂時，才會導(dǎo)致樹高增1，如圖2所示，因此Ⅳ錯誤。
答案：B
9、具有n個關(guān)鍵字的m階B樹，應(yīng)有（）個葉結(jié)點。
- A：n+1
- B：n-1
- C：mn
- D：nm/2
解析
B樹的葉結(jié)點對應(yīng)查找失敗的情況，對有n個關(guān)鍵字的查找集合進行查找，失敗可能性有n+1種。
答案：A
10、高度為5的3階B樹至少有（）個結(jié)點，至多有（）個結(jié)點。
- A：32
- B：31
- C：120
- D：121
解析
由m階B樹的性質(zhì)可知，根結(jié)點至少有2棵子樹；根結(jié)點外的所有非終端結(jié)點至少有m/2
棵子樹，結(jié)點數(shù)最少時，3階B樹形狀至少類似于一棵滿二叉樹，即高度為5的B樹至少有
-1=31個結(jié)點。
由于每個結(jié)點最多有m棵子樹，所以當結(jié)點數(shù)最多時，3階B樹形狀類似于滿三叉樹，結(jié)點數(shù)為(-1)/2=121。
