Q253.
有一文字檔共有4 個符號，這些符號所對應的霍夫曼碼(Huffman Codes)，那些長度不可能出現？
電腦軟體設計共同科目 · 乙級 · Q253
難易度分析
4 / 5
本題屬於複選題，要求考生將特定數學定理應用於驗證多個組合的正確性，而非簡單的定義記憶。由於需精確計算各選項是否符合前綴碼的數學條件，且必須判定所有選項才能得出最終答案，因此提升了分析與推論的複雜度。
正確答案 (複選)：②, ④
- ② 3 2 2 2:Σ = 2⁻³ + 3 × 2⁻² = 1/8 + 6/8 = 7/8 ≠ 1，違反 Kraft 等式，無法建構出對應的前綴碼二元樹，故此長度組合不可能出現。
- ④ 3 3 2 2:Σ = 2 × 2⁻³ + 2 × 2⁻² = 1/4 + 1/2 = 3/4 ≠ 1，同樣違反 Kraft 等式，無法形成合法的前綴碼，故此組合不可能出現。
錯誤選項解析
- ① 2 2 2 2:此組合滿足 Kraft 不等式：4 × 2⁻² = 1，對應一棵完整平衡二元樹，四個符號機率相等時即可產生此編碼長度。
- ③ 3 3 2 1:Σ = 2 × 2⁻³ + 2⁻² + 2⁻¹ = 1/4 + 1/4 + 1/2 = 1，符合 Kraft 等式，對應機率分佈懸殊時的偏斜霍夫曼樹結構。
Learning Tip
"霍夫曼編碼的核心考點在於 Kraft 不等式（Σ 2^(-lᵢ) = 1），任何合法的碼長組合必須使總和恰好等於 1。常見陷阱是僅憑直覺判斷碼長分佈，而忽略以數學公式驗證。實務上需牢記：四符號可能出現的合法碼長僅有 {2,2,2,2}（等機率平衡樹）與 {3,3,2,1}（機率懸殊偏斜樹）兩種組合。"
學員答題分佈
①2 2 2 20%
②3 2 2 20%
③3 3 2 10%
④3 3 2 20%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！