___________，它共有___________个叶子结点和___________个分支结点。
8、设深度为 h 的二叉树只有度为 0 和 2 的结点，该二叉树的结点数可能达到的最大值为___________，最小值为___________。
9、已知按先序遍历二叉树的结果为ABC，则共有___________种不同的二叉树可以得到这一遍历结果。
四、解答题
1、已知一棵二叉树的先序遍历序列是ABCDEFGHIJK，中序遍历序列是CDBGFEAHJIK，请构造出该二叉树，并给出该二叉树的后序遍历序列。 2、已知五个权值分别为9，2，5，7，14的叶子结点：
①构造一棵赫夫曼树； ②求此树的带权路径长度。 3、将下图所示的森林转化为二叉树。
ABCE4、已知二叉树的二叉链表定义如下： typedef char TElemType； typedef struct BiTNode { TElemType data；
struct BiTNode *lchild，*rchild； }*BiTree；
FDHGIJ
BiTree root；//root是指向以下二叉树根结点A的指针
- 21 -
ABCE
void traversal(BiTree T) { if (T) {
printf(\，T->data)； traversal(T->lchild)； printf(\，T->data)； traversal(T->rchild)； } }
试回答下列问题：
⑴给出算法traversal(root)的输出结果； ⑵分析算法traversal的时间复杂度。
5、已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k 的
结点，问该树中有多少个叶子结点？
6、已知在一棵含有n 个结点的树中，只有度为k 的分支结点和度为0的叶子结点。试求该树含有的叶子结点的数目。 7、找出所有满足下列条件的二叉树：
⑴它们在先序遍历和中序遍历时，得到的结点访问序列相同； ⑵它们在后序遍历和中序遍历时，得到的结点访问序列相同； ⑶它们在先序遍历和后序遍历时，得到的结点访问序列相同。 8、对第3题中森林分别进行先序遍历和中序遍历，给出遍历结果。
- 22 -
DFG
9、一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各为多少？
10、已知一棵二叉树的层次遍历序列是ABCDEFGHIJ，中序遍历序列是DBGEHJACIF，请
构造出该二叉树。
五、算法设计题
注：下列各题中的二叉树如未特殊说明均采用二叉链表作为存储结构。
1、参照课本提供的CreateBiTree和PreOrderTraverse算法，完成对下图所示二叉树的创建以及先序、中序和后序遍历操作。
ABCE2、 求二叉树中分支结点和叶子结点的数目。 3、 求二叉树的深度。
4、 销毁二叉树中的所有结点，要求在销毁每一个结点前，输出该结点的数据域。 5、 编写从上至下、从左到右按层次遍历二叉树的算法。
6、 编写递归算法：将二叉树中所有结点的左、右子树相互交换。 7、 编写算法判别给定二叉树是否为完全二叉树。
8、 编写递归算法：输出在二叉树的先序序列中第k个位置的结点的数据域。
9、 一棵二叉树的繁茂度定义为各层结点数的最大值与树的深度的乘积，编写算法求二叉树
的繁茂度。
10、为二叉链表的结点中增加DescNum域，编写算法求二叉树每个结点的子孙数目并存入
其DescNum域。
11、已知一颗二叉树的先序序列和中序序列，写一个建立该二叉树的二叉链表存储结构的算
法。
12、给出二叉树中的一个非根节点（由指针p所指），求它的兄弟节点（要求用指针q指向
它，若没有兄弟节点，这q为空）。
- 23 -
DFG
13、设计一个中序遍历非递归算法。 14、设计一个后序遍历非递归算法。
15、已知n个节点的完全二叉树已经顺序存储在一维数组A[1…n]中，试设计一算法将其变
成二叉链表存储的完全二叉树。
- 24 -
第 7 章 图
一、单选题
1、 在一个图中，所有顶点的度数之和等于图的边数的 倍。
A. 1/2 B.1 C. 2 D. 4
2、 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 A. 1/2 B.1 C. 2 D. 4 3、 有8个结点的无向图最多有
条边。
倍。
A. 14 B. 28 C. 56 D. 112 4、 有 8 个结点的有向完全图有 条边（弧）。
A. 14 B. 28 C. 56 D． 112 5、 用邻接表表示图进行广度优先遍历时，通常采用 来实现算法的。
A．栈 B．队列 C. 树 D．图 6、 用邻接表表示图进行深度优先遍历时，通常采用 来实现算法的。
A．栈 B．队列 C. 树 D．图 7、 深度优先遍历类似于二叉树的 。
A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历 8、 广度优先遍历类似于二叉树的 。
A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历 9、 对如下图所示的无向图 G ，若从顶点 Vl 开始，按深度优先搜索法进行遍历，则可能
的访问顺序为
。
A. Vl V2 V5 V8 V4 V6 V7 V3 B. Vl V2 V3 V4 V5 V6 V7 V8 C. VI V2 V3 V4 V8 V5 V6 V7 D. Vl V2 V4 V5 V8 V3 V6 V7
顺序为
。
10、对如图所示的无向图，若从顶点 V1开始，按广度优先搜索法进行遍历，则可能访问的
A. VI V2 V3 V4 V5 V6 V7 V8 B. VI V2 V6 V3 V4 V7 V8 V5 C. VI V2 V6 V3 V4 V5 V7 V8 D. VI V2 V4 V7 V3 V8 V6 V5
- 25 -