D．pre(x)>pre(y)且post(x)>post(y)
16．每棵树都能惟一地转换成对应的二叉树，由树转换的二叉树中，一个结点N的左孩子是它在原树对应结点的 (23) ，而结点N的右孩子是它在原树里对应结点的 (24) 。 (23)—(24)：A．最左孩子 B．最右孩子 C．右邻兄弟 D．左邻兄弟
17．二叉树在线索化后，仍不能有效求解的问题是 (25) 。 (25)：A．前序线索树中求前序直接后继结点 B．中序线索树中求中序直接前驱结点 C．中序线索树中求中序直接后继结点 D．后序线索树中求后序直接后继结点
18．一棵具有124个叶子结点的完全二叉树，最多有 (26)个结点。 (26)：A．247 B．248 C．249 D．250 。
19．实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最有效的存储结构是采用 （27） 。
(27)：A. 二叉链表 B．孩子链表 C．三叉链表 D．顺序表 二、填空题
1.树中任意结点允许有 （1）孩子结点，除根结点外，其余结点 （2） 双亲结点。 2.若一棵树的广义表表示为A(B(E，F)，C(C(H，I，J，K)，L)，D(M(N)))。则该树的度为 (3) ，树的深度为 (4) ，树中叶子结点个数为 (5) 。
3．若树T中度为1、2、3、4的结点个数分别为4、3、2、2，则T中叶子结点的个数是 (6) 。
4．一棵具有n个结点的二叉树，若它有m个叶子结点，则该二叉树中度为1的结点个数是 (7) 。
5．深度为k(k>0)的二叉树至多有 (8) 个结点，第i层上至多有 (9) 个结点。 6．已知二叉树有52个叶子结点，度为1的结点个数为30则总结点个数为 (10) 。 7．已知二叉树中有30个叶子结点，则二叉树的总结点个数至少是 （11） 。 8．高度为6的完全二叉树至少有 (12) 个结点。
9．一个含有68个结点的完全二叉树，它的高度是 (13) 。
10．已知一棵完全二叉树的第6层上有6个结点(根结点的层数为1)，则总的结点个数至少是 (14) ，其中叶子结点个数是 （15） 。
11．已知完全二叉树第6层上有10个叶子结点，则这棵二叉树的结点总数最多是 （16） 。 12．一棵树转换成二叉树后，这棵二叉树的根结点一定没有 (17) 孩子，若树中有m个分支结点，则与其对应的二叉树中无右孩子的结点个数为 （18） 。 13．若用二叉链表示具有n个结点的二叉树，则有 （19） 个空链域。 14．具有m个叶子结点的哈夫曼树，共有 （20）个结点。
15．树的后根遍历序列与其对应的二叉树的 （21） 遍历序列相同。 16．线索二叉树的左线索指向其 （22） ，右线索指向其 （23） 。 三、应用题
9
1．具有n个结点的满二叉树的叶子结点个数是多少? 2．列出前序遍历序列是ABC的所有不同的二叉树。
3．已知二叉树的层次遍历序列为ABCDEFGHIJK，中序序列为DBGEHJACIKF，请构造一棵二叉树。
4．已知二叉树的中序遍历序列是ACBDGHFE，后序遍历序列是ABDCFHEG，请构造一棵二叉树。
5．已知二叉树的前序、中序和后序遍历序列如下，其中有一些看不清的字母用*表示，请先填写*处的字母，再构造一棵符合条件的二叉树，最后画出带头结点的中序线索链表。 (1)前序遍历序列是：*BC***G* (2)中序遍历序列是：CB*EAGH* (3)后序遍历序列是：*EDB**FA
6．将下图所示的森林转换成一棵二叉树，并画出这棵二叉树的顺序存储结构。
7．将下图所示的二叉树还原成森林。
8．对于给定的一组权值{3，5，6，7，9}，请构造相应的哈夫曼树，并计算其带权路径长度。
四、算法设计题
1．请设计一个算法，求以孩子兄弟链表表示的树中叶子结点个数。
2．请编写一个算法，实现将以二叉链表存储的二叉树中所有结点的左、右孩子进行交换。 3．请编写一个算法，将以二叉链表存储的二叉树输出其广义表表示形式。
4．请编写一个算法，判断以二叉链表存储的二叉树是否为完全二叉树。
5．假设二叉树采用链接存储方式存储，编写一个二叉树先序遍历和后序遍历的非递归算法。..
6．已知一棵二叉树用二叉链表存储，t指向根结点，p指向树中任一结点。请编写一个
10
非递归算法，实现求从根结点t到结点p之间的路径。
第六章 图
一、单项选择题
1．下面关于图的存储结构的叙述中正确的是 (1) 。
(1)：A．用邻接矩阵存储图占用空间大小只与图中顶点有关，与边数无关 B．用邻接矩阵存储图占用空间大小只与图中边数有关，而与顶点数无关 C．用邻接表存储图占用空间大小只与图中顶点数有关，而与边数无关 D．用邻接表存储图占用空大小只与图中边数有关，而与顶点数无关 2．下面关于对图的操作的说法不正确的是 (2) 。 (2)：A:寻找关键路径是关于带权有向图的操作 B．寻找关键路径是关于带权无向图的操作 C．连通图的生成树不一定是惟一的 D．带权无向图的最小生成树不一定是惟一的
3．下面的各种图中，哪个图的邻接矩阵一定是对称的 (3) 。 (3)：A．AOE网 B．AOV网 C．无向图 D．有向图 4．在AOE网中关于关键路径叙述正确的是 (4) 。
(4)：A．从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所需的最短时间
B．从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所
需的最短时间
C．从开始顶点到完成顶点的具有最大长度的路径，关键路径长度是完成整个工程所
需的最长时间
D．从开始顶点到完成顶点的具有最小长度的路径，关键路径长度是完成整个工程所
需的最短时间
5．一个具有n个顶点e条边的图中，所有顶点的度数之和等于 （5）。 (5)：A．n B．2n C．e D．2e 6．具有8个顶点的无向图最多有 (6) 条边。 (6)：A．8 B．28 C．56 D．72 7．具有8个顶点的有向图最多有 (7) 条边。 (7)：A．8 B．28 C．56 D．78 8．深度优先遍历类似于二叉树的 (8) 。
(9)：A．前序遍历 B．中序遍历 C．后序遍历 D．层次遍历 9．广度优先遍历类似于二叉树的 (9) 。
(9)：A．前序遍历 B．中序遍历 C．后序遍历 D．层次遍历 10．任一个连通图的生成树 (10) 。
（l0）：A．可能不存在 B．只有一棵 C．一棵或多棵 D．一定有多棵
11
11．下列关于连通图的BFS和DFS生成树高度论述正确的是 （11）。 (11)：A．BFS生成树高度
12．G是一个非连通无向图，共有28条，则该图至少有解 (12) 个顶点。 (12)：A．7 B．8 C．9 D.10 二、判断题
1．一个图的邻接矩阵表示是惟一的。 ( ) 2．一个图的邻接表表示是惟一的。 ( ) 3．无向图的邻接矩阵一定是对称矩阵。 ( ) 4．有向图的邻接矩阵一定是对称矩阵。 ( )
5．有向图用邻接表表示，顶点vi的出度是对应顶点vj链表中结点个数。 ( ) 6．有向图用邻接表表示，顶点vi的度是对应顶点vj链表中结点个数。 ( ) 7．有向图用邻接矩阵表示，删除所有从顶点i出发的弧的方法是，将邻接矩阵的i行全部元素置为0。 ( )
8．若从无向图中任一顶点出发，进行一次深度优先搜索，就可以访问图中所有顶点，则该图一定是连通的。 ( )
9．在非连通图的遍历过程中，调用深度优先搜索算法的次数等于图中连通分量的个数。 ( )
10．具有n个顶点的有向强连通图的邻接矩阵中至少有n个小于∞的非零元素。 ( )
11．一个连通图的生成树是一个极小连通子图。 ( ) 12．在有数值相同的权值存在时，带权连通图的最小生成树可能不惟一。 ( ) 13．在AOE网中仅存在一条关键路径。 ( ) 14．若在有向图的邻接矩阵中，主对角线以下的元素均为0，则该图一定存在拓扑有序序列。 ( ) 15．若图C的邻接表表示时，表中有奇数个边结点，则该图一定是有向图。 ( ) 16．在AOE网中，任何一个关键活动提前完成，整个工程都会提前完成。 ( ) 17．图的深度优先遍历序列一定是惟一的。 ( ) 18．有向无环图的拓扑有序序列一定是惟一的。 ( ) 19．拓扑排序输出的顶点个数小于图中的顶点个数，则该图一定存在环。 ( ) 三、填空题
1．在一个具有n个顶点的完全无向图和完全有向图中分别包含有 (1) 和 (2) 条边。 2．具有n个顶点的连通图至少具有 (3) 条边。
3．具有n个顶点e条边的有向图和无向图用邻接表表示，则邻接表的边结点个数分别为（4）和 （5） 条。
12
