Q69.
有一文字檔共有4 個符號，這些符號所對應的Huffman Code，其長度何者是可能出現？
電腦軟體設計共同科目 · 乙級 · Q69
難易度分析
3 / 5
此題需運用 Kraft 不等式驗證編碼長度的合法性，並要求對 Huffman 樹的葉節點分佈有正確理解，需經過邏輯推導與計算方能得出結論。
正確答案：①2 2 2 2
① 2 2 2 2:當四個符號的出現頻率相等時，Huffman 樹會建構出完全平衡的二元樹結構，每個符號的編碼長度均為 2，符合 Kraft 不等式（4 × 2⁻² = 1），因此是合法的編碼長度組合。
錯誤選項解析
- ② 3 2 2 2:此組合的 Kraft 總和為 2⁻³ + 3 × 2⁻² = 7/8 ≠ 1，違反前綴碼的 Kraft 等式條件。在 Huffman 編碼中，若有一個符號編碼長度為 3，則不可能同時存在三個長度為 2 的符號，因為完整二元樹的葉節點配置無法滿足此分佈。
- ③ 4 3 2 1:此組合的 Kraft 總和為 2⁻⁴ + 2⁻³ + 2⁻² + 2⁻¹ = 15/16 ≠ 1，不滿足前綴碼的必要條件。此外，Huffman 編碼中若存在長度為 1 的編碼，表示該符號直接連在根節點，剩餘三個符號無法在另一子樹中同時產生長度為 2、3、4 的配置。
- ④ 3 3 2 2:此組合的 Kraft 總和為 2 × 2⁻³ + 2 × 2⁻² = 3/4 ≠ 1，違反Kraft 等式。對於四個符號的 Huffman 樹，若兩個符號長度為 2、兩個為 3，表示樹結構不平衡且葉節點總數不足，無法構成完整的 Huffman 二元樹。
Learning Tip
"Huffman 編碼的核心考點在於 Kraft 不等式（Σ 2^(-lᵢ) = 1），任何合法的前綴碼編碼長度組合都必須滿足此條件。常見陷阱是僅憑直覺判斷編碼長度，而忽略以 Kraft 等式進行驗證。對於 n 個符號，可能的編碼長度組合取決於頻率分佈所決定的樹形結構，等頻率時產生平衡樹（所有編碼等長），頻率差異越大則編碼長度差異也越大。"
學員答題分佈
①2 2 2 20%
②3 2 2 20%
③4 3 2 10%
④3 3 2 20%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！