1．已知一算术表达式的中缀形式为ABCDE，后缀形式为ABCDE，其前缀形式为（）。
A．ABCDEB．ABCDEC．ABCDED．ABCDE参考答案：D
3．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。A．250B．500C．254D．505E．以上答案都不对
参考答案：E8．在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个。
A．4B．5C．6D．7参考答案：C10．具有10个叶结点的二叉树中有（）个度为2的结点。
A．8B．9C．10D．11参考答案：B
53．由3个结点可以构造出（A．2B．3C．4
参考答案：D
）种不同的二叉树。D．5
47．引入二叉线索树的目的是（）。A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删
除C．为了能方便的找到双亲D．使二叉树的遍历结果唯一
19．将如下由三棵树组成的森林转换为二叉树。
DA
EBC
F参考答案：
A
B
D
EGC
H
F
I
KO
J
LM
P
N
O
G
HI
J
KL
MNO
P
f反过来，将一个二叉树转化成森林或树？（注意：转化成森林的结果和转化成树的结果不一样）21．设某二叉树的前序遍历序列为ABCDEFGGI，中序遍历序列为BCAEDGHFI，试画出该二叉树。参考答案：
A
B
D
CE
F
G
I
H
27．设二叉树T的存储结构如下：
12345678910
Lchild
00237580101
Data
JHFDBACEGI
Rchild
0009400000
其中Lchild、Rchild分别为结点的左、右孩子指针域，Data为结点的数据域，若根指针T
的值为6，试：1画出二叉树的逻辑结构；2写出按前序、中序、后序遍历该二叉树所得
到的结点序列；3画出二叉树的后序线索树。
参考答案：
前序序列：ABCEDFHGIJ中序序列：ECBHFDJIGA后序序列：ECHFJIGDBA
31．假定用于通讯的电文仅有8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这8个字母设计哈夫曼编码树。参考答案：
f各字母编码如下：c10110c210c30010c40111c5000c6010c711c80011注意虽然哈夫曼树的带权路径长度是唯一的，但形态不唯一。
33．设T是一棵二叉树，除叶子结点外，其它结点的度皆为2，若T中有6个叶结点，试问：1树T的最大深度和最小可能深度分别是多少？2树T中共有多少非叶结点？3若叶结点的权值分别为1、2、3、4、5、6，请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wpl。参考答案：1最大深度6，最小深度4；2非叶结点数5；3哈夫曼树见下图，其带权路径长度wpl51。
34．一棵深度为Ｈ的满ｋ叉树有如下性质：第Ｈ层上的结点都是叶r