树与二叉树转换，森林与二叉树的转换，哈夫曼编码例题详解

╰+攻爆jí腚メ 2022-12-19 11:59 145阅读 0赞

1.  二叉树的前序序列和后序序列正好相反，则该二叉树一定是（B）

*  A.空或只有一个结点
 *  **B.高度等于其结点数**
 *  C.任一结点无左孩子
 *  D.任一结点无右孩子

2.任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（A）

*  **A.肯定不发生改变**
 *  B.肯定发生改变
 *  C.不能确定
 *  D.有时发生变化

**答案解析**

\[解析\] 如果用符号D表示访问根结点，用L表示遍历左子树，用 R表示遍历右子树，那么前序、中序、后序遍历可分别表示为：DLR、 LDR、LRD。**由此可见，在三种遍历序列中L和R的相对次序都是L在前、R在后。**所以，任何一棵二叉树的叶结点在前序、中序、后序序列中的相对次序都不会发生改变。

3.为5个使用频率不等的字符设计哈夫曼编码，不可能的方案是（D）

*  A.001,001,010,011,1
 *  B.0000,0001,001,01,1
 *  C.000,001,01,10,11
 *  **D.00,100,101,110,111**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70][]

4.设哈夫曼编码的长度不超过4，若已经对两个字符编码为1和01，则最多还可以为（C）个字符编码。

A.2

B.3

**C.4**

D.5

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 1][]

5.具有100个结点的完全二叉树的叶子结点数为【填空1】

**【填空1】50**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 2][]

6.设森林中有4棵树，树中结点的个数依次为n1,n2,n3,n4,则把森林转换成二叉树后，其根节点的右子树上有【填空1】个结点，根节点的左子树上有【填空2】个结点。

**【填空1】n2+n3+n4**

**【填空2】n1-1**

7.某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是【填空1】。

**【填空1】CDBGFEA**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 3][]

8.在有n个叶子的哈夫曼树中，分支结点的总数为【填空1】

**【填空1】n-1**

9.已知某字符串S中共有8种字符，各种字符分别出现2次，1次，4次，5次，7次，3次，4次和9次，对该字符串用\{0,1\}来进行前缀编码，该字符串的编码至少有【填空1】位。

**【填空1】98**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 4][]

10.已知二叉树的中序序列为CBEDAFIGH，后序序列为CEDBIFHGA，试构造该二叉树？

注：请用文字或上传图片作答。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 5][]

11.对给定的一组键值W=\{5,2,9,11,8,3,7\},试构造相应的哈夫曼树，并计算它的带全路径长度WPL。

注：请用文字或上传图片作答。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 6][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70]: /images/20221120/23d98b476454467cbc47ff1e1bf72d9c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201107170058821.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201107163217139.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201107170210731.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201107170245212.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20201107170305277.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20201107170325166.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk4NzAxNg==,size_16,color_FFFFFF,t_70