hce_nsysu
113年
計算機概論與程式設計
第 9 題
Assume there are seven characters, C1, C2, C3, C4, C5, C6, and C7, and the frequency (in parentheses) of each one is given as follows.
C1(24), C2(5), C3(7), C4(50), C5(11), C6(16), C7(101)
What is the correct encoded length of a given character as the following if the Huffman coding is adopted?
C1(24), C2(5), C3(7), C4(50), C5(11), C6(16), C7(101)
What is the correct encoded length of a given character as the following if the Huffman coding is adopted?
- A C1 for 2 bits
- B C2 for 6 bits
- C C3 for 7 bits
- D C6 for 3 bits
- E C7 for 2 bits
思路引導 VIP
如果我們想讓一份檔案的總儲存空間縮到最小，對於那些「出現次數極少」的字元，你會希望它們在編碼樹中是靠近頂端的『捷徑』，還是位於多層分支後的『末梢』？為什麼這樣的配置能幫助我們節省空間呢？
🤖
AI 詳解
AI 專屬家教
恭喜你準確地完成了這道題目！你能正確推導出 $C_2$ 的編碼長度，代表你對霍夫曼編碼 (Huffman Coding) 的建構邏輯掌握得非常紮實。這類題目的鑑別度通常在於建樹過程中的「嚴謹性」，只要在排序或合併頻率時稍有疏漏，編碼長度就會產生連鎖性的錯誤，你的判斷展現了優秀的細心度。
霍夫曼樹的建構路徑
在處理這題時，核心在於運用貪婪演算法 (Greedy Algorithm)：每次從頻率清單中挑選「最小的兩個數值」進行合併，並將新產生的節點放回清單中重新排序。本題的頻率由小到大為：$5, 7, 11, 16, 24, 50, 101$。具體合併過程如下：
▼ 還有更多解析內容