60.设二叉树以二叉链表形式存储，请编写一个求叶子结点总数的算法。 解：可以用两种方法解决这个问题。 方法一：设置一个初始值为0的变量leafNum进行计数，在对二叉树进行遍历过程中判断当前访问的结点是否为叶子结点，若为叶子结点，则leafNum加一。因此当遍历完成整个二叉树后，leafNum的值即为叶子结点的数目。算法如下： int leafNum=0;
void countLeaf(BinTree t) {
if (t==Null)
return;
if (t->Lchild==Null && t->Rchild==Null)
leafNum++; else {
countLeaf(t->Lchild); countLeaf(t->Rchild); } }
方法二：根据二叉树的特点可知：当二叉树为空时，叶子结点总数为0；当二叉树只有一个结点时，叶子结点数为1；否则，叶子结点数等于左右子树叶子结点数之和。因此，可以定义二叉树t的叶子结点数目leaf(t)的递归计算模型为：
当t?Null时?0,?leaf(t)??1,当t为叶子时
?leaf(t??Lchild)?leaf(t??Rchild),否则?根据这个计算模型，可以编写如下算法：
int leaf(BinTree t) {
if (t==Null) return(0);
if (t->Lchild==Null && t->Rchild==Null) return(1);
return(leaf(t->Lchild)+leaf(t->Rchild)); }
进一步讨论：(1)二叉树的许多操作都可以借助遍历过程来完成。一般说来，当需要对二叉树的部分或全部结点进行某种操作时，可以在对二叉树遍历过程中，对结点执行相应的操作。本题实际上可以看成是对所有叶子结点进行计数，因此，可以在遍历中完成。(2)许多问题都可以利用二叉树的特点定义一个计算模型，这种模型通常具有递归性，运用这种递归模型很容易写出相应的递归算法。例如，求二叉树的结点总数，可以写出如下算法模型：
26
当t?Null时?0,nodes(t)???nodes(t??Lchild)?nodes(t??Rchild)?1,否则
请读者自己编写算法。
61．求二叉树的结点总数（请读者自己编写算法）
62.写出中序线索化二叉树中查找结点*p中序后继的算法。
解：在中序二叉树中，查找p指针(指向)的结点其后继分两种情况： (1) 若p->rtag=1则p->rchild即指向其后继结点；
(2) 若p->rtag=0则*p结点的中序后继必为其右子树中第一个中序遍历到的结点，即，从*p
的右孩子开始，沿着左指针链向下找，直找到一个没有左孩子的结点，这个结点又称为*p的右子树中“最左下”的结点。 其参考算法如下： tbtree *succ(tbtree *p) { tbtree *q;
if (p->rtag==1)
return (p->rchild); /*由后继线索直接得到*/ else
{q=p->rchild; /*查找*p右子树中“最左下”结点*/ while (q->ltag==0) q=q->lchild; return (q); } }
63.试写出先序遍历二叉树的算法。
解：设t为根指针，存储结构为二叉链表，类型为bitree,参考递归算法如下：
preorder(t) /*先序遍历二叉树*/
bitree t; /*树t以二叉链表存储，类型为btree*/ { if (t) /*树非空*/
{ printf(t->data) /*访问根结点*/
preorder(t->lchild)； /*遍历左子树*/ preorder(t->rchild)； /*遍历右子树*/ }
} /*preorder*/
(也可以给出非递归算法，从略。) 64.试写出后序遍历二叉树的算法。
解：设t为根指针，存储结构为二叉链表，类型为bitree,参考递归算法如下：
postorder(t) /*后序遍历二叉树*/
bitree t; /*树t以二叉链表存储，类型为btree*/ { if (t) /*树非空*/ { … ； /*遍历左子树*/ … ； /*遍历右子树*/ … ； /*访问根结点*/
27
}
} /*postorder*/
(也可以给出非递归算法，从略。)
65.已知在以二叉链表存储的二叉树t中，p为指向二叉树中某个结点的指针，试编写一个算法输出结点p的所有祖先(假定树中结点数据为字符型)。
解：根据祖先结点的定义，如果结点r是p的祖先，那么p必定是在r的左子树或右子树中的结点。因此，我们定义函数inTree(t,p)检查p是否为子树t中的结点，并在这个过程中输出p的祖先。基本思想为：
(1)若t==Null,则返回0，表明p不在子树t中； (2)若t==p,则返回1，表明p包含在子树t中；
(3)若inTree(t->Lchild,p)==1或者inTree(t->Rchild,p)==1,则t为p的祖先，输出t并返回1； (4)否则，返回0。
根据这一思路，可编写如下参考递归算法： int inTree(BinTree t,BinTree p) {
if (t==Null) return(0); if (t==p) return(1);
if (inTree(t->Lchild,p) || (inTree(t->Rchild,p)) { pritf(“%c”,t->data); return(1); }
return(0); }
进一步讨论：(1)在上述算法中，我们通过检查p是否为子树t中的结点来输出p的所有祖先。实际上检查p是否子树t中的结点的过程等价于二叉树的前序遍历，即首先判断根结点是否为p，若不是，再去检查p是否为t的左子树或右子树中的结点。本算法中，p的祖先结点的输出顺序为：p的父结点、祖父结点……最后输出根结点。(2)我们可以从另一个角度来解决这个问题。根据祖先结点的定义，如果结点r是p的祖先，那么它必须满足下列条件之一：
① p为r的左孩子或右孩子；
② r的左孩子或右孩子为p的祖先。 根据这个思路可编写递归算法如下： int ancestor(BinTree t,BinTree p) {
if (t==Null) return(0);
if (t->Lchild==p || t->Rchild==p ||
ancestor(t->Lchild,p) || ancestor(t->Rchild,p)) { printf(“%c”,t->data); return(1); }
return(0);
28
}
(也可以给出非递归算法，从略。)
习题7
判断题：
1.在n个结点的无向图中，若边数 > n-1，则该图必是连通图。（ ╳ ） (中科院软件所1997年研究生试题) 2.邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适用。（ ╳ ）
3.图的深度优先搜索序列和广度优先搜索序列不一定是唯一的。( √ ) 4.有回路的图不能进行拓扑排序。( √ )
5.任何AOV网拓扑排序的结果都是唯一的。( ╳ ) 6.在AOV-网中，如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径。( √ )
7.图的邻接矩阵中矩阵元素的行数只与顶点个数有关（ √ ） 8.图的邻接矩阵中矩阵中非零元素个数与边数有关（ √ ）
9.在拓扑排序序列中，任意两个相继结点V i和Vj都存在从V i到Vj的路径（FALSE ）
10.若一个图的邻接矩阵为对称矩阵，则该图必为无向图。（ ）
11.任一AOE网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条（ TRUE ）
单选题：
13.在一个图中，所有顶点的度数之和等于所有边数的( A )倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的( C )倍。 A. 1/2 B. 2 C. 1 D. 4 14.具有n个顶点的有向图最多有( B )条边。 (北航1999年研究生试题。)
A．n B. n(n-1) C. n(n+1) D. n2 15.在一个具有n个顶点的无向图中，要连通全部顶点至少需要( C )条边。 A. n B. n+1 C. n-1 D. n/2
16.一个有n个顶点的无向连通图，它所包含的连通分量个数为( B )。 A．0 B. 1 C. n D. n+1 17. n个顶点的强连通图至少有( A )条边。
A. n B. n-1 C. n+1 D. n(n-1)
18. 在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为( A )。
A．s B. s-1 C. s+1 D. n 19. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为( ① A )；所有邻接表中的结点总数是( ② C )。
29
(题源：李春葆，C版习题解析，P274，9.2.1(单选)_8)
① A. n B. n+1 C. n-1 D. n+e ② A. e/2 B. e C. 2e D. n+e 作一次“第一条”边，再作一次其它边的“相邻接”边. )
20. 对于一个有向图，若一个顶点的入度为k1、出度为k2，则对应邻接表中该顶点的单链表中的结点数为( B )。
A．k1 B. k2 C. k1-k2 D. k1+k2
21. 在有向图G的拓扑序列中，若顶点vi在顶点vj之前，则下列情况下不可能出现的是( D )。
A．G中有弧
22. 在一个无向图中，若两个顶点之间的路径长度为k，则该路径上的顶点数为( B )。
A．k B. k+1 C. k+2 D. 2k
23. 采用邻接表存储的图的深度优先遍历类似于二叉树的( B )。 A．中序遍历 B. 先序遍历 C. 后序遍历 D. 按层次遍历 24.用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( A )。
(中科院软件所1998年研究生试题。)
A．逆拓扑有序的 B. 拓扑有序的 C. 无序的 25.关键路径是事件结点网络中的( A )。
A．从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C． 最长的回路 D. 最短的路径
26.下面不正确的说法是( A )。
(1)在AOE-网工程中，减少任一关键活动上的权值后，整个工期也就相应的减小 (2)AOE-网工程工期为关键活动上的权之和
(3)在关键路径上的活动都是关键活动，而关键活动也必在关键路径上 (南京理工大2000年研究生试题。)
A．(1) B. (2) C. (3) D. (1)(3) 27.下面的叙述中不正确的是( B )。 (北工大1999年研究生试题。)
A.关键活动不按期完成就会影响整个工程的完成时间 B.任何一个关键活动提前完成，将使整个工程提前完成 C.所有关键活动都提前完成，则整个工程将提前完成 D.某些关键活动若提前完成，将使整个工程提前完成
28.采用邻接表存储的图的广度优先遍历类似于二叉树的( A )。 A．按层次遍历 B. 中序遍历 C. 后序遍历 D. 先序遍历 29.一个图中包含k个连通分量，若按深度优先(DFS)搜索方法访问所有结点，则必须调用( A )次深度优先遍历算法。
A．k B. 1 C. k-1 D. k+1 30.以下说法正确的是( B )。 (全国2991年自考题。)
30