第六章 树和二叉树作业
一、选择题（每题2分，共24分）。
1. 一棵二叉树的顺序存储情况如下：
树中，度为2的结点数为（ C ）。
A．1      B．2      C．3      D．4
2. 一棵“完全二叉树”结点数为25，高度为（ B ）。
A．4      B．5      C．6      D．不确定
3．下列说法中，（ B ）是正确的。
A.  二叉树就是度为2的树 
B.  二叉树中不存在度大于2的结点
C.  二叉树是有序树 
D.  二叉树中每个结点的度均为2
4.一棵二叉树的前序遍历序列为ABCDEFG,它的中序遍历序列可能是（ B ）。
A.  CABDEFG          B.  BCDAEFG 
C.  DACEFBG          D.  ADBCFEG
5．线索二叉树中的线索指的是（ C ）。
A．左孩子      B.遍历        C.指针        D.标志
6. 建立线索二叉树的目的是（ A ）。
A. 方便查某结点的前驱或后继   
B. 方便二叉树的插入与删除
C. 方便查某结点的双亲         
D.  使二叉树的遍历结果唯一
7. 有abc三个结点的右单枝二叉树的顺序存储结构应该用（ D ）示意。
A.
a
b
c
B.
a
b
^
c
C.
a
b
^
^
c
D.
a
^
b
二叉树前序中序后序图解
^
^
^
c
8. 一颗有2046个结点的完全二叉树的第10层上共有（ B ）个结点。
A.  511        B.  512        C.  1023      D.  1024
9. 一棵完全二叉树一定是一棵（ A ）。
A.  平衡二叉树            B.  二叉排序树   
C.  堆                    D.  哈夫曼树
10．某二叉树的中序遍历序列和后序遍历序列正好相反，则该二叉树一定是（ C ）的二叉树。
A．空或只有一个结点            B．高度等于其结点数
C．任一结点无左孩子            D．任一结点无右孩子
11．一棵二叉树的顺序存储情况如下：
      1  2  3  4  5  6  7  8  9  10  11  12  13  14  15
      A  B  C  D  E  0  F  0  0  G  H    0    0  0    X
结点D的左孩子结点为（ D ）。
A．E                B．C              C．F              D．没有
12．一棵“完全二叉树”结点数为25，高度为（ B ）。
A．4                B．5              C．6              D．不确定
二、填空题（每空3分，共18分）。
1.  树的路径长度：是从树根到每个结点的路径长度之和。对结点数相同的树来说，路径长度最短的是 完全 二叉树。
2. 在有n个叶子结点的哈夫曼树中，总结点数是  2n-1 。
3. 在有n个结点的二叉链表中，值为非空的链域的个数为   n-1   。
4. 某二叉树的中序遍历序列和后序遍历序列正好相反，则该二叉树一定是  任一结点无左孩子  的二叉树。
5. 深度为 k 的二叉树最多有             个结点，最少有   k  个结点。
三、综合题（共58分）。
1. 假定字符集{a，b，c，d，e，f }中的字符在电码中出现的次数如下：
字符
a
b
c
d
e
f
频度
9
12
20
23
15
5
构造一棵哈夫曼树（6分），给出每个字符的哈夫曼编码（4分），并计算哈夫曼树的加权路径长度WPL（2分）。 （符合WPL最小的均为哈夫曼树，答案不唯一）
哈夫曼编码:
a:1110  b:10  c:00  d:10  e:01  f:1111
WPL=208
2. 假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字符构成，它们在电文中出现的频率分别为{0.31,0.16,0.10,0.08,0.11,0.20,0.04}。要求：
(1)为这7个字符设计哈夫曼树（6分）。
(2)据此哈夫曼树设计哈夫曼编码（4分）。
(3)假设电文的长度为100字符，使用哈夫曼编码比使用3位二进制数等长编码使电文总长压缩多少？（4分）
(1) 为这7个字符设计哈夫曼树为（符合WPL最小的均为哈夫曼树，答案不唯一）：
(2) 哈夫曼编码为：
a:01;b:001;c:100;d:0001;e:101;f:11;g:0000
(3) 假设电文的长度为100字符，使用哈夫曼编码比使用3位二进制数等长编码使电文总长压缩多少？
采用等长码，100个字符需要300位二进制数，采用哈夫曼编码发送这100个字符需要261二进制位，压缩了300-261=39个字符。压缩比为39/300=13%。
3. 二叉数T的（双亲到孩子的）边集为：
{ <A,B>, <A,C>, <D,A>, <D,E>, <E,F>, <F,G> }
请回答下列问题：
（1）T的根结点（2分）：
（2）T的叶结点（2分）：
（3）T的深度（2分）：
（4）如果上述列出边集中，某个结点只有一个孩子时，均为其左孩子；某个结点有两个孩子时，则先列出了连接左孩子的边后列出了连接右孩子的边。画出该二叉树其及前序线索（6分）。
(1)T的根结点 ：D
(2)T的叶结点 ：B，C，G,
(3)T的深度 ：4
(4)该二叉树其及前序线索为：
4．现有以下按前序和中序遍历二叉树的结果：
前序：ABCEDFGHI  中序：CEBGFHDAI
画出该二叉树的逻辑结构图（5分），并在图中加入中序线索（5分）。
5．有电文：ABCDBCDCBDDBACBCCFCDBBBEBB。
用Huffman树构造电文中每一字符的最优通讯编码。画出构造的哈夫曼树，并给出每个字符的哈夫曼编码方案。（符合WPL最小的均为哈夫曼树，答案不唯一）
（1）构造哈夫曼树（6分）：
（2）哈夫曼编码方案（4分）：
A：0001  B：1  C：01  D：001
E：00000  F：00001

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。