高考申論題
112年
[電力工程] 計算機概論
第 一 題
📖 題組：
假設有一串文字由字母 a, b, c, d, e, f 所組成，並且每個字母出現的頻率如下表所示。若欲將此串文字進行霍夫曼編碼（Huffman Encoding）成 01 字元字串，請回答下列問題： 字母 a b c d e f 出現頻率 16% 10% 8% 25% 35% 6%
假設有一串文字由字母 a, b, c, d, e, f 所組成，並且每個字母出現的頻率如下表所示。若欲將此串文字進行霍夫曼編碼（Huffman Encoding）成 01 字元字串，請回答下列問題： 字母 a b c d e f 出現頻率 16% 10% 8% 25% 35% 6%
📝 此題為申論題，共 2 小題
小題 (一)
請產生霍夫曼樹（Huffman Tree），並詳細畫出產生的過程。不失一般性，請將出現頻率低的置於左子樹，出現頻率高的置於右子樹，出現頻率相同時則可任意擇一置於左子樹，另一個置於右子樹。（10 分）
思路引導 VIP
面對霍夫曼樹（Huffman Tree）建構題，首先應聯想到使用貪婪演算法（Greedy Algorithm），將所有字元依頻率由小到大排序。接著重複「選取兩個最小節點合併」的動作，並嚴格遵守題目所規定的「左小右大」放置原則，逐步畫出樹狀結構。
小題 (二)
承(一)，若將霍夫曼樹中之左子樹標 0，右子樹標 1，請寫出各字母的霍夫曼碼。（5 分）
思路引導 VIP
遇到霍夫曼編碼（Huffman Encoding）題型，考生應先利用貪婪演算法（Greedy Algorithm），從頻率最小的兩個節點開始逐步合併以建構霍夫曼樹（Huffman Tree）。建樹完成後，嚴格遵循題目「左子樹標 0、右子樹標 1」的規則，從根節點（Root）向下走訪至各葉節點（Leaf Node），即可求得無編碼衝突的字首碼（Prefix Code）。