试题
考点

数据结构-树和森林-赫夫曼树

面5笔5

哈弗曼编码是一种无损二进制熵编码算法，其加权路径长度最小，字符串“alibaba”的二进制哈弗曼编码有___位（bit）

A.11

B.12

C.13

D.14

前往“校大”小程序，刷题更快
最新校招难题刷题，快来进刷题群吧
解答

正确答案是 C

各字符出现的频率分别为： a (3), b (2), l (1), i (i)。

构造哈夫曼树：
        7
     /     \
(1)4      a(0)
   /  \
 2     b
/ \
l  i

a: 0         
b: 10
l: 111
i: 110

alibaba编码长度为：  1+3+3+2+1+2+1 = 13

评论

阿然

2022-01-26 23:00:00

没看这篇帖子之前完全不懂该咋答
0 0

假期

2021-02-01 23:52:28

Ccccccccc
0 0

期待

2021-02-01 11:09:10

最优二叉树算法
0 0

子不语

2021-10-08 10:27:51

哈弗曼编码又叫前缀编码，不能有任何一个编码是其他的前缀

0 1

小茉莉

2018-10-13 11:46:55

根据字符出现的次数，构造哈夫曼树

a出现3次       b出现 2       l出现 1      i出现 1
             7
        4        3
   2      2

1   1                       3+2*2+1*3+1*3 = 3+4+3+3 = 13
0 0

人间喜剧

2018-10-13 11:46:45

哈弗曼树又叫做最优二叉树，是权值越大的点离根节点越近，导致整个树权值最小 方法：选择值最小的两个点作为左右节点，然后和作为父节点，在剩下的点以及父节点中选择最小的两个依次构造，形成哈弗曼树 左边数值是0，右边是1 哈弗曼编码是将各个点的值加起来最小 长度计算就是把各个点的值乘以路径长加起来 例a(3),b(2),l(1),i(1) 长度就是3(l+i)+2b+1a;把abli换成他们对应的3 2 1 1就是13  
0 0

人间喜剧

2018-10-13 11:46:34

先利用不同的字母的权重,构建最优Huffman树 ,然后进行Huffman编码,每一个不同的字符都是由一定的二进制数进行表示,然后进行相加
在本题中 假如

a:1;一位
b:01;二位
i :001;三位

L:000;三位
则长度 alibaba 就是1*3+3+3+2*2=13
0 0

皮皮鲁

2018-10-13 11:46:23

应该选c，构造哈夫曼树的最短路径，越接近根节点，权值越小，a,b,l,i从多到少，从根节点开始，左0右1构造哈夫曼树，依次为a(0)b(10)l(110)i(111)这样哈夫曼编码为0 110 111 10 0 10 0共13位，此为最短  
0 0

小小精灵

2018-10-13 11:46:13

哈弗曼树又叫做最优二叉树，是权值越大的点离根节点越近，导致整个树权值最小

方法：选择值最小的两个点作为左右节点，然后和作为父节点，在剩下的点以及父节点中选择最小的两个依次构造，形成哈弗曼树
左边数值是0，右边是1
哈弗曼编码是将各个点的值加起来最小
长度计算就是把各个点的值乘以路径长加起来
例a(3),b(2),l(1),i(1)

长度就是3(l+i)+2b+1a;把abli换成他们对应的3 2 1 1就是13
0 0

先锋

2018-10-13 11:45:57

构造哈弗曼树：

1、首先a(3)、b(2)、i(1)、l(1)分别单独构成一个树（节点），节点的权重是字符出现的频率；
2、先将权重最小的两个节点结合组成一个新的节点（新节点的权重为子节点的权重之和），然后依次这样进行，最终所有的节点组成一个树；
3、对于每个节点，其左边值为0，右边值为1；所有的叶节点均为文本中出现的字符。
   weight(2)                                     weight(4)                                         weight(7)                                 
                                                      0/            \1                                           0/    \1
     0 /   \ 1                ->    weight(2)                  b(2)     ->                   weight(4)    a(3)
                                       0 /   \1                                                            0/   \1
     l(1) i(1)                     l(1)    i(1)                                              weight(2)    b(2)
                                                                                                        0 /  \1
                                                                                                       l(1)   i(1)

所以，对于a/b/l/i 他们对应的霍夫曼编码
a:1;
b:01;
i :001;
L:000;

长度：1+3+3+2+1+2+1=13
0 0

加载更多