11. (单选题, 5分) 假设电文A、B、C、D、E的权值为5、6、9、10、15,则报文AECDB的哈夫曼编码为()。(58同城2020校园招聘笔试)
时间: 2023-10-20 19:07:37 浏览: 40
先按照权值从小到大排列,得到A(5)、B(6)、C(9)、D(10)、E(15)。构造哈夫曼树:
```
45
/ \
15 30
/ \ / \
A B 9 21
/ \
C D
/ \
E 空
```
从叶子节点到根节点,0表示向左走,1表示向右走,得到编码:
A: 000
E: 01
C: 100
D: 101
B: 11
因此,报文AECDB的哈夫曼编码为:000100011011。
相关问题
有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。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)