Q147.
形成6 層之AVL 平衡樹(Balanced Tree)，最少的節點數是多少？
電腦軟體設計共同科目 · 乙級 · Q147
難易度分析
3 / 5
此題需要運用特定的遞迴公式進行多步驟計算，且容易與其他二元樹類型的節點數定義相混淆，因此需要對 AVL 樹的平衡特性有精確的記憶與計算能力。
正確答案：②20
② 20:20 為正確答案。AVL 平衡樹最小節點數公式為 N(h) = N(h-1) + N(h-2) + 1，代入計算：N(1)=1、N(2)=2、N(3)=4、N(4)=7、N(5)=12、N(6)=12+7+1=20。
錯誤選項解析
- ① 19:19 不符合 AVL 樹最小節點數的遞迴公式計算結果。AVL 樹最小節點數遵循 Fibonacci 數列變體，6 層時計算結果並非 19。
- ③ 21:21 大於最小節點數要求。雖然 21 個節點確實可以形成 6 層 AVL 樹，但題目問的是「最少」節點數，正確最小值為 20。
- ④ 22:22 同樣大於最小節點數。此數值可構成 6 層 AVL 樹，但不符合「最少節點數」的條件，偏離遞迴公式的計算結果。
Learning Tip
"此類題型常考 AVL 樹最小節點數遞迴公式 N(h) = N(h-1) + N(h-2) + 1，其原理是維持 平衡因子 ≤ 1 的前提下，讓左右子樹高度差恰好為 1 時節點數最少。容易與「完全二元樹」的最小節點數混淆，需注意 AVL 樹允許不平衡的極限狀態，節點數比完全二元樹更少。實務上建議背誦前幾項數列：1, 2, 4, 7, 12, 20, 33... 以快速作答。"
學員答題分佈
①190%
②200%
③210%
④220%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！