11. (单选题, 5分) 假设电文A、B、C、D、E的权值为5、6、9、10、15,则报文AECDB的哈夫曼编码为()。(58同城2020校园招聘笔试)
时间: 2023-10-20 21:05:17 浏览: 94
先构造哈夫曼树如下:
```
50
/ \
21 29
/ \ / \
9 12 14 15
/ \
5 4
```
然后根据哈夫曼树可以得到A、E、C、D、B的编码分别为0、10、110、111、10,所以报文AECDB的哈夫曼编码为0110101110。
相关问题
有5个结点A,B,C,D,E,权值为7,9,5,6,18,构造一颗哈夫曼树(包含过程)
首先,将所有结点按照权值从小到大排序,得到序列A(7), C(5), D(6), B(9), E(18)。
接着,取出权值最小的两个结点C(5)和D(6),将它们合并成一个新结点CD(11),并将CD插入到序列中。现在序列为A(7), CD(11), B(9), E(18)。
再次取出权值最小的两个结点A(7)和CD(11),将它们合并成一个新结点ACD(18),并将ACD插入到序列中。现在序列为ACD(18), B(9), E(18)。
接下来,取出权值最小的两个结点B(9)和ACD(18),将它们合并成一个新结点BACD(27),并将BACD插入到序列中。现在序列为BACD(27), E(18)。
最后,取出权值最小的两个结点BACD(27)和E(18),将它们合并成一个新结点根节点(45)。这就是哈夫曼树的构造过程。哈夫曼树如下图所示:
```
45
/ \
/ \
27 18
/ \
/ \
9 ACD
/ \
/ \
7 11
/ \
/ \
C D
```
已知下列字符a、b、c、d、e、f、g的权值分别为4,13,8,5,3,9请构造哈夫曼树
首先将字符按照权值从小到大排序:e(3),g(9),a(4),d(5),c(8),f(9),b(13)。
然后选取权值最小的两个节点e和g,构造出一个新的节点,其权值为两个节点的权值之和12,把e和g作为新节点的左右子节点。此时剩余的节点为a、d、c、f、b。再次选取权值最小的节点a和d,构造出一个新的节点,其权值为两个节点的权值之和9,把a和d作为新节点的左右子节点。此时剩余的节点为c、f、b和新的节点(a+d)。
重复以上步骤,直到所有节点都被处理完,最终得到的哈夫曼树如下所示:
```
52
/ \
21 31
/ \ / \
9 12 13 18
/ \ / \ / \ / \
4 5 3 9 8 5 9 9
a d e g c f b 新节点
```
其中,根节点的权值为所有字符的权值之和,即4+13+8+5+3+9=42。