地特四等申論題
110年
[統計] 資料處理概要
第 五 題
某機器共有 7 個指令，分別為 A~G。假設其出現的機率分別如下：
A：0.25 B：0.20 C：0.15 D：0.13 E：0.12 F：0.10 G：0.05
若以哈夫曼編碼（Huffman coding）方式將指令編碼，且左子樹編碼為 0，右子樹編碼為 1，則指令 A~G 的編碼分別為何？（12 分）
📝 此題為申論題
思路引導 VIP
遇到此題，首先聯想到霍夫曼編碼（Huffman coding）的核心策略：貪婪演算法（Greedy Algorithm）。請將所有指令依出現機率由小到大排序，每次取出最小的兩個節點合併為新節點，並重新排序，重複此動作直到建立一棵完整的二元樹。最後由根節點出發，依題目要求的「左0右1」原則進行路徑標記，即可得出最佳前綴碼（Prefix code）。
🤖
AI 詳解
AI 專屬家教
【解題思路】本題運用貪婪演算法（Greedy Algorithm）建構霍夫曼樹（Huffman Tree），藉由反覆合併機率最小的兩個節點來產生無歧義的最佳前綴碼（Prefix Code）。 【詳解】 已知各指令出現機率：A(0.25)、B(0.20)、C(0.15)、D(0.13)、E(0.12)、F(0.10)、G(0.05)。
▼ 還有更多解析內容