Q59.
設一個只包含根節點的二元樹之高度(Height)為1，則高度為6 的高度平衡二元樹(AVL 樹)至多有幾個節點？
電腦軟體設計共同科目 · 乙級 · Q59
難易度分析
3 / 5
本題要求區分 AVL 樹在特定高度下「最大」與「最少」節點數的計算邏輯。由於選項中設置了針對最少節點數及高度誤判的強干擾項，考生必須精確掌握對應的數學公式才能正確選出答案。
正確答案：④63
④ 63:高度為 h 的完全二元樹（AVL 樹的一種特例）最多節點數為 2ʰ - 1。代入 h = 6，得 2⁶ - 1 = 63 個節點。
錯誤選項解析
- ① 20:20 是高度為 6 的 AVL 樹的最少節點數，而非最多節點數。AVL 樹最少節點數遵循遞迴公式 N(h) = N(h-1) + N(h-2) + 1，計算得 N(6) = 20。
- ② 31:31 是高度為 5 的完全二元樹的最大節點數（2⁵ - 1 = 31），此選項混淆了樹的高度。
- ③ 32:32 等於 2⁵，與二元樹節點數公式無關。完全二元樹的最大節點數公式為 2ʰ - 1，而非 2 的冪次本身。
Learning Tip
"此類題型常考 AVL 樹的最少節點數 與 完全二元樹的最大節點數 的區別。最少節點數使用費氏數列遞迴 N(h) = N(h-1) + N(h-2) + 1，最大節點數使用公式 2ʰ - 1。解題時務必審題看清「至多」或「至少」的關鍵字，避免混淆。"
學員答題分佈
①200%
②310%
③320%
④630%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！