首页 > 试题广场 >

假设某段通信电文仅由 6 个字母 ABCDEF 组成，字母在

[单选题]
假设某段通信电文仅由 6 个字母 ABCDEF 组成，字母在电文中出现的频率分别为 2，3，7，15，4，6。根据这些频率作为权值构造哈夫曼编码，最终构造出的哈夫曼树带权路径长度与字母 B 的哈夫曼编码分别为______。(这里假定左节点的值小于右节点的值) 
  • 86，1011
  • 70，1000
  • 86，0001
  • 70，0010
  • 92，1000
  • 92，0100
添加回答
推荐
编号2015头像 编号2015
A
长度计算为（2+3）*4+（4+6+7）*3+15*1=86

所以B的编码（也就是3）为1011

编辑于 2016-04-17 17:01:03 回复(20)
喜刷刷头像 喜刷刷
所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度。这里就是2*4+3*4+4*3+6*3+7*3+15*1=86

发表于 2015-08-06 13:25:41 回复(15)
孤天祭头像 孤天祭
假定左结点的值小于右结点的值，最后标号左0右1
发表于 2020-07-28 21:16:13 回复(0)
菩提旭光头像 菩提旭光
编辑于 2015-08-22 17:25:23 回复(0)
ByronDo头像 ByronDo
算法要求选取根结点权值最小的两棵二叉树作为左右子树构造一棵新的二叉树，但并没有要求哪一棵作左子树，哪一棵作右子树，所以左右子树的顺序是任意的。如果是这样的话，有多个答案，C也可。希望大家可以讨论下。                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   
发表于 2015-03-10 17:02:31 回复(2)
蛊声孒头像 蛊声孒

左小右大根据哈夫曼编码标出来0和1，然后顺着线就可以把路径长度跟码写出来了
长度：37+22+9+5+3=86
编码：1011
编辑于 2015-09-24 21:06:42 回复(11)
Acamy头像 Acamy
得到B(对应3)的编码为1011

一棵哈夫曼树的带权路径长度等于树中所有的叶结点的权值乘上其到根结点的路径长度。
所以 长度： （2+3）*4+（4+6+7）*3+15*1=86  
发表于 2017-07-03 15:47:10 回复(2)
edutiantang头像 edutiantang
哈夫曼树构建如下：


得到B的编码为1011

一棵哈夫曼树的带权路径长度等于树中所有的叶结点的权值乘上其到根结点的路径长度。
所以 长度： （2+3）*4+（4+6+7）*3+15*1=86  
编辑于 2016-09-06 22:06:53 回复(1)
新玥头像 新玥
哈夫曼编码规则是每次取权值最小的两个结点构造树
发表于 2018-09-28 09:20:03 回复(0)
┮澈兮Д头像 ┮澈兮Д
叉
忽略了 左结点的值小于右结点的值
不错 只选A
发表于 2015-04-14 14:39:49 回复(0)
卡卡girl头像 卡卡girl
重点在最后一句：假设左结点值小于右结点···
发表于 2015-08-29 11:00:51 回复(0)
牛客218196695号头像 牛客218196695号
(1)这个题哈弗曼编码是左子树为'0' ,右子树为'1' ,
(2)一棵哈夫曼树的带权路径长度等于树中所有的叶结点的权值乘上其到根结点的路径长度 

发表于 2020-06-05 11:57:15 回复(0)
牛客321509759号头像 牛客321509759号
没看到左结点小于右结点
发表于 2023-05-28 10:14:56 回复(0)
一叶舟troy头像 一叶舟troy

![](https://files.mdnice.com/user/5197/5cfeb367-e54f-4aef-bdcb-0b623c8a278b.png)

step1. 
创建一个优先级队列（小）
 -  【2 3】 4 6 7 15
step2.  重复 
 pop 2个最小的，然后累计和添加进去 
 
 - [4 5  6 7  15 
 - [6 7] 9  15 
 - 9 13 15 
 - 15 22 
 
step3 左节点的值小于右节点的值

发表于 2021-08-04 14:10:17 回复(0)
乌拉拉哼哼哈嘿头像 乌拉拉哼哼哈嘿
发表于 2021-06-22 09:24:47 回复(0)
YkekeY头像 YkekeY
注意假定条件：左节点的值小于右节点的值
发表于 2021-05-05 12:07:32 回复(0)
天尊墨宇头像 天尊墨宇
选A
B(对应3)的编码为1011
棵哈夫曼树的带权路径长度等于树中所有的叶结点的权值乘上其到根结点的路径长度。
所以 长度： （2+3）*4+（4+6+7）*3+15*1=86  

发表于 2020-06-22 09:07:38 回复(0)
麒麟央宗头像 麒麟央宗
我其实不太懂为何此处6和7要单独拿出来作为一个新的树。但是之前的4就可以直接加在之前的树里。
发表于 2019-08-14 14:35:07 回复(0)
水鬼头像 水鬼

编辑于 2019-08-23 10:15:19 回复(0)
面试好难呀头像 面试好难呀

构造的哈夫曼树如上图所示，绿色为叶节点，结点内容包括字符+权值，如A(2)表示字符A的权值为2（权值==频率）；

 
所以哈夫曼树带权路径长度 = 15*1+4*3+2*4+3*4+6*3+7*3=86
B的哈夫曼码为：1011
发表于 2019-04-23 14:47:22 回复(0)
午夜阳光1头像 午夜阳光1
哈夫曼树的不唯一，注意后面的限定条件。
发表于 2018-05-07 22:08:43 回复(0)
提交观点

问题信息

树
来自：阿里巴巴2015研发工...
难度：
43条回答 29069浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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