Q76.
若要對一組訊息AAABCDDDDEEE 做二進位數的編碼，其中每個字元代碼為可變長度，當使用霍夫曼碼(Huffman Codes)來進行編碼時，此訊息編碼後最少需要多少位元？
電腦軟體設計共同科目 · 乙級 · Q76
難易度分析
4 / 5
本題屬於計算型題目，要求考生不僅要掌握可變長度編碼的核心概念，還必須正確執行建構霍夫曼樹的完整過程，並將各字元的出現頻率與對應碼長進行加權計算，對邏輯推導與計算精準度有一定要求。
正確答案：①26
① 26:霍夫曼編碼根據字元出現頻率建構最優二元樹，頻率高的字元分配較短編碼。本題 A(3次)配2位元、D(4次)配2位元、E(3次)配2位元、B與C各1次配3位元，總位元數為 3×2 + 4×2 + 3×2 + 1×3 + 1×3 = 26 位元。
錯誤選項解析
- ② 36:36 位元是將所有字元以固定長度編碼（如每個字元用 3 位元）計算的結果，但霍夫曼編碼屬於可變長度編碼，會根據頻率動態調整碼長，因此不會達到此數值。
- ③ 15:15 位元遠低於資訊熵下限，即使以理想壓縮也無法達到。本題共有 5 個相異字元，至少需要 log₂(12) 的平均碼長，15 位元違反霍夫曼編碼的數學原理。
- ④ 30:30 位元可能是誤用等長編碼（如每字元 2.5 位元取整數）或霍夫曼樹建構錯誤所致。正確做法應依貪婪演算法由最小頻率兩兩合併，才能得到最優 26 位元的結果。
Learning Tip
"霍夫曼編碼的核心考點在於正確建構霍夫曼樹：每次挑選頻率最小的兩個節點合併，直到剩下一個根節點。常考陷阱包含：(1) 合併順序錯誤導致碼長計算不正確；(2) 混淆固定長度與可變長度編碼的差異；(3) 忽略總位元數需將「各字元碼長 × 出現次數」後加總。實務上霍夫曼編碼廣泛應用於 ZIP 壓縮與 JPEG 影像編碼，理解其貪婪策略的最優性證明為資料結構重點。"
學員答題分佈
①260%
②360%
③150%
④300%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！