二叉树的前序序列和后序序列正好相反，则该二叉树一定是（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,1B.0000,0001,001,01,1C.000,001,01,10,11D.00,100,101,110,111

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

A.2

B.3

C.4

D.5

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

【填空1】50

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

【填空1】n2+n3+n4

【填空2】n1-1

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

【填空1】CDBGFEA

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

【填空1】n-1

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

【填空1】98

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

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

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

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