Q148.
形成7 層之AVL 平衡樹(Balanced Tree)，最少的節點數是多少？
電腦軟體設計共同科目 · 乙級 · Q148
難易度分析
4 / 5
本題要求運用特定的遞迴公式進行多步驟數值計算，且需區分 AVL 樹與其他類比樹狀結構的平衡條件差異，對計算精準度與對特定演算法公式的掌握度有較高要求。
正確答案：③33
③ 33:33 為正確答案。根據 AVL 樹最小節點公式 N(h) = N(h-1) + N(h-2) + 1，其中 N(0)=0、N(1)=1，依序計算至 N(7) = N(6) + N(5) + 1 = 20 + 12 + 1 = 33。
錯誤選項解析
- ① 31:31 是高度為 6 的 AVL 樹最小節點數，而非高度 7 的結果。AVL 樹最小節點遞迴公式為 N(h) = N(h-1) + N(h-2) + 1，計算至 h=6 時為 20，h=7 時為 33。
- ② 32:32 並非 AVL 樹最小節點遞迴公式所產生的數值。AVL 樹因需維持左右子樹高度差不超過 1 的平衡條件，其最小節點數遵循類費氏數列增長，不會出現 32 此數值。
- ④ 34:34 大於高度 7 的 AVL 樹最小節點數。最小節點數是維持平衡條件的下限值，34 雖可形成 7 層 AVL 樹，但不符合「最少節點數」的題目要求。
Learning Tip
"AVL 樹最小節點數是資料結構常考題型，關鍵在於熟記遞迴公式 N(h) = N(h-1) + N(h-2) + 1。常見陷阱是與完全二元樹的最小節點數混淆（完全二元樹 h 層最少為 2^(h-1) 個節點），兩者平衡條件不同，計算方式也截然不同。實務上建議手算前幾項 N(0)~N(7) 以快速作答。"
學員答題分佈
①310%
②320%
③330%
④340%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！