A.21%
B.27%
C.18%
D.36%
正確答案：A
根據(jù)題目對(duì)霍夫曼編碼的描述，我們不難知道，每次都是選擇當(dāng)前最小的情況，這符合貪心算法總是找當(dāng)前看來(lái)最優(yōu)的情況，因此屬于貪心策略。如果對(duì)包含100，000個(gè)字符，且這些字符都屬于a到f。那么如果采用固定長(zhǎng)度的編碼，針對(duì)于每個(gè)字符需要3位來(lái)編碼（因?yàn)橛?個(gè)不同的字符，至少需要3位才能表示6種不同的變化）。那么對(duì)100000個(gè)字符編碼，其編碼長(zhǎng)度為300000。如果采用霍夫曼編碼，那么首先我們就要根據(jù)字符出現(xiàn)的頻率構(gòu)造出其霍夫曼樹。首先選擇出現(xiàn)頻率最低的4和8，生成子樹，其父節(jié)點(diǎn)為12，然后放入出現(xiàn)頻率隊(duì)列中，后面的采用同樣的道理，以此類推。構(gòu)造出的霍夫曼樹如下圖所示：由圖可以知道，a的編碼為00，b的編碼為11，c的編碼為0100，d的編碼為0101，e的編碼為011，f的編碼為10。因此總的編碼長(zhǎng)度為（2*18%+2*32%+4*4%+4*8%+3*12%+2*26%）*100000=23600，因此節(jié)省的存儲(chǔ)空間大小為30000-23600=6400。因此節(jié)省的存儲(chǔ)空間為比例為6400/30000=21%。

點(diǎn)擊查看答案