未定量。
7二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常
用的是三种：前序法（即按NLR次序），后序法（即按LRN次序）和中序法（也称对称序法，
即按LNR次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是
FEBGCHD，则它的后序序列必是
FEGHDCB
。
解：法1：先由已知条件画图，再后序遍历得到结果；
法2：不画图也能快速得出后序序列，只要找到根的位置特征。由前
序先确定root，由中序先确定左子树。例如，前序遍历BEFCGDH中，
根结点在最前面，是B；则后序遍历中B一定在最后面。
法3：递归计算。如B在前序序列中第一，中序中在中间（可知左
右子树上有哪些元素），则在后序中必为最后。如法对B的左右子树同
1
f样处理，则问题得解。
8中序遍历的递归算法平均空间复杂度为O
。答：即递归最大嵌套层数，即栈的占用单元数。精确值应为树的深度k1，包括叶子的空域也递归了一次。9用5个权值32451构造的哈夫曼（Huffma
）树的带权路径长度是33。
解：先构造哈夫曼树，得到各叶子的路径长度之后便可求出WPL＝（4＋5＋3）×2＋（1＋2）×333
15
9
6
4533
（注：两个合并值先后不同会导致编码不同，即哈夫曼编码不唯一）（注：合并值应排在叶子值之后）
1
2
（注：原题为选择题：Ａ．32
Ｂ．33
Ｃ．34
Ｄ．15）
三、单项选择题（每小题1分，共11分）
（C）1．不含任何结点的空树
。
（Ａ）是一棵树
（Ｂ）是一棵二叉树
（Ｃ）是一棵树也是一棵二叉树
（Ｄ）既不是树也不是二叉树
答：以前的标答是B，因为那时树的定义是
≥1
（C）2．二叉树是非线性数据结构，所以
。
（Ａ）它不能用顺序存储结构存储
（Ｂ）它不能用链式存储结构存储
（Ｃ）顺序存储结构和链式存储结构都能存储（Ｄ）顺序存储结构和链式存储结构都不能使用
（C）3具有
0个结点的完全二叉树的深度为
。
Ａlog2
Ｂlog2
Ｃlog2
1
Ｄlog2
1
注1：x表示不小于x的最小整数；x表示不大于x的最大整数，它们与含义不同！
注2：选（A）是错误的。例如当
为2的整数幂时就会少算一层。似乎log2
1是对的？
（A）4．把一棵树转换为二叉树后，这棵二叉树的形态是
。
（Ａ）唯一的
（Ｂ）有多种
（Ｃ）有多种，但根结点都没有左孩子（Ｄ）有多种，但根结点都没有右孩子
5从供选择的答案中，选出应填入下面叙述？内的最确切的解答，把相应编号写在答卷的对r