霍夫曼編碼將頻繁出現的字元採用短編碼， 出現頻率較低的字元採用長編碼。 具體的操作過程為：i)以每個字元的出現頻率作為關鍵字構建最小優先順序佇列；ii)取出關鍵字最小的兩個結點生成子樹， 根節點的關鍵字為孩子節點關鍵字之和， 並將根節點插入到最小優先順序佇列中， 直至得到一棵最優編碼樹。
霍夫曼編碼方案是基於______策略的。 用該方案對包含a到f6個字元的檔進行編碼， 檔包含100000個字元， 每個字元的出現頻率(用百分比表示)如表1-3所示， 則與固定長度編碼相比， 該編碼方案節省了______存儲空間。
表1-3 某檔中每個字元出現的頻率
字元
a
b
c
d
e
f
出現頻率(%)
18
32
4
8
12
26
64、 A．分治 B．貪心 C．動態規劃 D．回溯
65、 A．21% B．27% C．18% D．36%
1.在刷軟體設計師題的時候碰到了上面這個題目， 後面的答案簡單的介紹了一下， 沒有介紹21%這個值是怎麼算來的， 所以想一探究竟（其實很簡單， 只能說自己基礎差了）
64、B
65、A
[解析] 依題意， 霍夫曼編碼方案是基於貪心策略的。 用該方案對包含a～f6個字元的檔進行編碼， 檔包含100000個字元， 每個字元的出現頻率(用百分比表示)如表1-3所示， 則與固定長度編碼相比， 該編碼方案節省了21%的存儲空間。
2.題目的關鍵點在與最優編碼樹,所以要先構建這個最優編碼樹。
最終得到結果18*2（00）+26*2（10）+32*2（11）+12*3（011）+4*4（0100）+8*4（0101）=236*1000
固定長度編碼所以得知原來的編碼結果為300*1000
236/3≈79；100-79=21；所以結果是A
總結：蹭一蹭， 也許能發現其中的道理。