关于J初赛模拟哈夫曼编码
  • 板块学术版
  • 楼主murder_drones
  • 当前回复6
  • 已保存回复6
  • 发布时间2024/8/11 16:06
  • 上次更新2024/8/11 17:02:56
查看原帖
关于J初赛模拟哈夫曼编码
610393
murder_drones楼主2024/8/11 16:06

在J组初赛模拟中的第8题,题意如下:

  1. 假设有一组字符{g,h,i,j,k,l},它们对应的频率分别为 8%,14%,17%,20%,23%,18%。

请问以下哪个选项是字符 g,h,i,j,k,l 分别对应的一组哈夫曼编码?( )

A. g: 1100, h: 1101, i: 111, l: 10, k: 00, j: 01
B. g: 0000, h: 001, i: 010, l: 011, k: 10, j: 11
C. g: 111, h: 110, i: 101, l: 100, k: 01, j: 00
D. g: 110, h: 111, i: 101, l: 100, k: 0, j: 01

答案里似乎选C,但是我模拟的结果似乎并不相同。

g:8 h:14 i:17 j:20 k:23 l:18
先选择g与h,得gh:22

gh:22 i:17 j:20 k:23 l:18
再选择i与l,得il:35

gh:22 il:35 j:20 k:23
选择gh与j,得ghj:42

ghj:42 il:35 k:23
再选择il与k,得ilk:58

ghj:42 ilk:58
再选择ghj与ilk,得ghjilk:100

容易发现,所有可能的树形态同构,不存在选项中的C形态,即g和i第一位不可能相同,我想问的是,我的理解或计算是否有问题?

2024/8/11 16:06
加载中...