首页 > 试题广场 >

已知一段文本有1382个字符，使用了1382个字节进行存储，

[不定项选择题]
已知一段文本有1382个字符，使用了1382个字节进行存储，这段文本全部是由a、b、c、d、e这5个字符组成，a出现了354次，b出现了483次，c出现了227次，d出现了96次，e出现了232次，对这5个字符使用哈夫曼（Huffman）算法进行编码，则以下哪些说法正确（） 
  • 使用哈夫曼算法编码后，用编码值来存储这段文本将花费最少的存储空间
  • 使用哈夫曼算法进行编码，a、b、c、d、e这5个字符对应的编码值是唯一确定的
  • 使用哈夫曼算法进行编码，a、b、c、d、e这5个字符对应的编码值可以有多套，但每个字符编码的位（bit）数是确定的
  • b这个字符的哈夫曼编码值位数应该最短，d这个字符的哈夫曼编码值位数应该最长
查看正确选项
添加回答
Ziwen头像 Ziwen
D,
发表于 2014-11-21 11:52:48 回复(0)
想做樱木的圆寸少年头像 想做樱木的圆寸少年
A正确，Huffman树就是求最优解。可以有多套方案，但最终每套方案生成的编码长度都相同且都是最优解。
B错误，我们可以将左子树定为1右子树定为0也可以反之，不同的方案获得的编码值是不同的，但每个字符的编码长度是固定的。
C正确，不同的方案影响的只是通向节点的路径为0还是1，而不会影响Huffman树的层次结构
D正确，生成了Huffman树之后，我们就能看到，出现频率越高的节点越靠近根，深度越小即编码值尾数越短；出现频率越低的节点越远离根，深度越大即编码位数越长。
发表于 2016-01-14 17:13:37 回复(5)
寻#头像 寻#
看错了。。。B答案：哈弗曼编码不是唯一的，因为二叉树左右字数定义的0,1不同会影响到最后的编码。D答案：次数最小的应该放在最底层叶子节点，次数最大的应该最接近根节点。
发表于 2015-04-28 23:06:49 回复(0)
wenyanliu头像 wenyanliu
哈夫曼编码采用变长编码对源符号进行编码，变长编码表根据源符号出现概率得到，源符号出现概率越大，对应编码越短，反之越长。这样得到的编码平均长度和期望值最小，可以压缩存储。使用哈夫曼编码这几个字符对应的编码值不唯一，但是它们所占的编码位数唯一。所以答案为ACD
编辑于 2015-06-25 10:24:11 回复(0)
reallocing头像 reallocing
这题D选项有问题吧，b，a，e三个的编码长度一样，凭什么说b最短，就因为它频数最大～
发表于 2017-06-19 11:48:40 回复(6)
牛客488687号头像 牛客488687号
A肯定是错的，大二的时候撸过这个项目，事后发现压缩率跟7z zip 那些根本不能比
发表于 2016-09-11 18:23:58 回复(0)
为荣耀而战头像 为荣耀而战
其实D看漏了。很简单，1382个字符占用1382个字节，每个字符占一个字节存储，出现次数最多的，先用内存字节数也最多，因此，根据哈夫曼的数学原理，即树的带权路径和最小，编码最优。因此离树根最近的，必然应该编码它占用位数最少。
发表于 2015-09-22 00:08:27 回复(0)
疯行田下头像 疯行田下
霍夫曼编码是，电文总长最短的二进制前缀编码。
发表于 2015-06-16 14:35:37 回复(0)
x93008头像 x93008
A为啥要选？难道直接用字符储存不如编码节约空间？
发表于 2018-09-15 14:10:01 回复(1)
jlstmac头像 jlstmac
B和D？就大神指点
发表于 2014-11-05 11:38:41 回复(3)
Tudorlin头像 Tudorlin
难道没有比哈夫曼树更高效的压缩方法吗，看他说的这么绝对我都不敢选
编辑于 2024-01-14 19:59:59 回复(0)
陳丶奕丶迅头像 陳丶奕丶迅
哈夫曼树和哈夫曼编码不唯一，但是带权路径长度WPL唯一。
发表于 2022-08-08 11:55:56 回复(0)
帅猪头像 帅猪
Ａ选项不加前缀码能对？
发表于 2020-09-01 21:49:56 回复(0)
十三*头像 十三*
b最短 但是 d和c不应该是一样长的吗？
发表于 2020-08-21 20:27:01 回复(0)
DeepMachine头像 DeepMachine
看错题目
发表于 2019-07-17 16:51:24 回复(0)
这个名有人取了头像 这个名有人取了
关于D选项，从哈夫曼编码思想的角度，频率最高的编码就应该最短，频率最低的编码就应该最长，选项中说的是“应该”，提出的是要求，而实际是不是有和它一样长的，只有编码之后才知道，有也并不违背这个要求，所以D没毛病
发表于 2018-06-12 10:10:14 回复(0)
没变秃也没变强头像 没变秃也没变强
感觉A说的不是很严谨，最优解只是对于Huffman编码的储存来讲，但别的压缩方***比Huffman压缩更小，感觉有点不对
发表于 2018-04-10 18:12:03 回复(0)
sakura1314头像 sakura1314
觉得D选项说的不准确 编码后a、b、d应该都是2位，c和d是3位的
发表于 2017-12-04 09:23:43 回复(0)
青青子衿123456头像 青青子衿123456
Huffman树就是求最优解。可以有多套方案，但最终每套方案生成的编码长度都相同且都是最优解
发表于 2016-08-04 11:24:34 回复(1)
Blizard223头像 Blizard223
哈夫曼编码，每个元素编码的长度是确定的，但是编码的符号可以不同
发表于 2016-04-18 16:05:45 回复(0)
提交观点

问题信息

C++工程师 字符串 树 迅雷 2014
来自：迅雷2014C++研发...
上传者：jl-wu
难度：
21条回答 15196浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号