为： 2*i 。
（19）给定如下图所示的二叉树，其前序遍历序列为： ABEFHCG 。
HE F G B H（20）给定如下图所示的二叉树，其层次遍历序列为： ABCEFGH 。
A C E F G B A C B C C A B C A A B A B C （17）三个结点可以组成 2 种不同形态的树。
（18）将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，其左孩子结点的编号
三．选择题
（1）树最适合用来表示（ D ）。
A．有序数据元素 B．无序数据元素
C．元素之间无联系的数据 D．元素之间有分支的层次关系 （2）前序为A，B，C的二叉树共有（ D ）种。 A．2
B．3
C．4
D．5
（3）根据二叉树的定义，具有3个结点的二叉树有（ C ）种树型。
41
A．3 B．4 C．5 D．6
（4）在一棵具有五层的满二叉树中，结点的总数为（ B ）
A．16 B．31 C．32 D．33 （5）具有64个结点的完全二叉树的深度为（ C ） A．5
B．6
C．7
D．8
（6）任何一棵二叉树的叶结点在前序、中序、后序遍历序列中的相对次序（ A ）。 A．不发生改变 B．发生改变 C．不能确定 D．以上都不对 （7）A，B为一棵二叉树上的两个结点，在中序遍历时，A在B前的条件是（ C ）。 A．A在B右方 B．A是B祖先 C．A在B左方 D．A是B子孙 （8）下列4棵树中，（ B ）不是完全二叉树。
A． B． C． D．
D E FG D E F D E A BD E F C G A B C B A C B A C D B A C （9）如右图所示的二叉树，后序遍历的序列是（ D ） A． ABCDEFGHI
B． ABDHIECFG C． HDIBEAFCG D． HIDEBFGCA
（10）对于下边的二叉树，其中序序列为（ A ）
A．DBEHAFCG B．DBHEAFCG C．ABDEHCFG D．ABCDEFGH
H I A B D E H F C G 为（ D ）。 A． ACBED
B．DECAB
（11）某二叉树的后序遍历序列为：DABEC，中序遍历序列为: DEBAC，则前序遍历序列
C．DEABC D．CEDBA
（12）具有n（n>1）个结点的完全二叉树中，结点i（2i>n）的左孩子结点是（ D ）。
42
A．2i B．2i+1 C．2i-1 D．不存在
（若2i<=n，则答案为A）
（13）把一棵树转换为二叉树后，这棵二叉树的形态是（ A ）。
A．唯一的 B．有多种
C．有多种，但根结点都没有左孩子 D．有多种，但根结点都没有右孩子 （14）将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为45的结点的左孩子编号为（ B ）。 A．46
B．47
C．90
D．91
（15）将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为49的结点的右孩子编号为（ B ）。 A．98 （ B ）。
A．正确 B．错误 （17）下列陈述正确的是（ D ）。
A．二叉树是度为2的有序树 树之分
（18）用5个权值{3, 2, 4, 5, 1}构造的哈夫曼树的带权路径长度是（ B ）。
Ａ．32 Ｂ．33 Ｃ．34 Ｄ．15 （ 先构造哈夫曼树，WPL=（1+2）*3+（3+4+5）*2=33 ）
（19）在树结构中，若结点B有4个兄弟，A是B的父亲结点，则A的度为为（ C ）。 A．3 B．4 C．5 D．6 （20）二叉树的叶结点个数比度为2的结点的个数（ C ）。 A．无关
B．相等
C．多一个 D．少一个
B．二叉树中结点只有一个孩子时无左右之分 D．二叉树中最多只有两棵子树，且有左右子
C．二叉树中必有度为2的结点
C．不确定 D．都有可能
B．99
C．50
D．100
（16）二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索，这种说法
四. 简答题
（1）已知一棵树边的集合如下，请画出此树，并回答问题。
{(L,M),(L,N),(E,L),(B,E),(B,D),(A,B),(G,J),(G,K),(C,G),(C,F),(H,I),(C,H),(A,C)} ①哪个是根结点？ ②哪些是叶结点？ ③哪个是G的双亲？ ④哪些是G的祖先？ ⑤哪些是G的孩子？ ⑥哪些是E的子孙？
⑦哪些是E的兄弟？哪些是F的兄弟？ ⑧结点B和N的层次各是多少？ ⑨树的深度是多少？ ⑩以结点C为根的子树的深度是多少？ ?树的度数是多少？ 答：
① A是根结点。
② 叶结点：M，N，D，J，K，F，I。 ③ G的双亲：C。 ④ G的祖先：A，C。 ⑤ G的孩子：J，K。
43
⑥ E的子孙：L，M，N。
⑦ E的兄弟：D；F的兄弟：G，H。
⑧ 结点B的层次为2；结点N的层次是5。 ⑨ 树的深度是5。
⑩ 以结点C为根的子树的深度是3。 ?树的度数是3。
（2）设下列二叉树是与某森林对应的二叉树，试回答下列问题。
A B D H I E C F J L G K ①森林中有几棵树？
②每一棵树的根结点分别是什
么？
③第一棵树有几个结点？ ④第二棵树有几个结点？ ⑤森林中有几个叶结点？ 解： ①4 ②A,C,G,K ③6
④2
⑤7
（3）二叉树按中序遍历的结果为：ABC，试问有几种不同形态的二叉树可以得到这一遍历结果？并画出这些二叉树。
答：有5种不同形态的二叉树可以得到这一遍历结果，如下图所示。
A AC B A C B B A A C B C C B （4）分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 答：
3个结点的树：
3个结点的二叉树树：
44