B E C K F H D
L G I M J
5、画出和下列二叉树相应的森林。
答：注意根右边的子树肯定是森林， 而孩子结点的右子树均为兄弟。
五、算法设计题
1、编写递归算法，计算二叉树中叶子结点的数目。
解：思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。
void Leaf(BitTree bt,int *count) {
if (bt) {
Leaf(bt->lchild,&count); //计算左子树的叶子结点个数 if (bt->lchild==NULL&&bt->rchild==NULL) (*count)++;
Leaf(bt->rchild,&count); //计算右子树的叶子结点个数 }}2.写出求二叉树深度的算法，先定义二叉树的抽象数据类型。 解： int depth(liuyu*root) /*统计层数*/
{int d,p; /*注意每一层的局部变量d,p都是各自独立的*/ p=0;
if(root==NULL)return(p); /*找到叶子之后才开始统计*/
21
else{
d=depth(root->lchild);
if(d>p) p=d; /*向上回朔时，要挑出左右子树中的相对大的那个深度值*/ d=depth(root->rchild); if(d>p)p=d; } p=p+1; return(p); }
3、求二叉树中以元素值为x的结点为根的子树的深度。
解：int Get_Sub_Depth(Bitree T,int x)//求二叉树中以值为x的结点为根的子树深度 { if(T->data==x)
{ printf(\找到了值为x的结点,求其深度 exit 1; } } else {
if(T->lchild) Get_Sub_Depth(T->lchild,x);
if(T->rchild) Get_Sub_Depth(T->rchild,x); //在左右子树中继续寻找 } }//Get_Sub_Depth
4、编写按层次顺序（同一层自左至右）遍历二叉树的算法。
解：思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。 这是一个循环算法，用while语句不断循环，直到队空之后自然退出该函数。
技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队，??以此产生了按层次输出的效果。 void LayerOrder(Bitree T)//层序遍历二叉树 { InitQueue(Q); //建立工作队列
EnQueue(Q,T);
while(!QueueEmpty(Q)) {
DeQueue(Q,p); visit(p);
if(p->lchild) EnQueue(Q,p->lchild);
22
if(p->rchild) EnQueue(Q,p->rchild); }
}//LayerOrder
5、二叉树按二叉链表形式存储，编写算法判别给定二叉树是否为完全二叉树。
答：int IsFull_Bitree(Bitree T)//判断二叉树是否完全二叉树,是则返回1,否则返回0 { InitQueue(Q); flag=0;
EnQueue(Q,T); //建立工作队列 while(!QueueEmpty(Q)) { {
DeQueue(Q,p); if(!p) flag=1;
else if(flag) return 0; else
{ EnQueue(Q,p->lchild);
EnQueue(Q,p->rchild); //不管孩子是否为空,都入队列 } }//while return 1; }//IsFull_Bitree
6、计算二叉树上单分支结点数目。 int Onchild(BiTree T)//单分支节点的 {
int num1,num2,n=0; if(T==NULL) return(0); else
if((T->lchild==NULL&&T->rchild!=NULL)||(T->lchild!=NULL&&T->rchild==NULL)) n=1;
num1=Onchild(T->lchild); num2=Onchild(T->rchild); return(num1+num2+n); }
7、写出在中序线索二叉树里；找指定结点在后序下的前驱结点的算法。
[题目分析]在后序序列中，若结点p有右子女，则右子女是其前驱，若无右子女而有左子女，
23
则左子女是其前驱。若结点p左右子女均无，设其中序左线索指向某祖先结点f（p是f右子树中按中序遍历的第一个结点），若f有左子女，则其左子女是结点p在后序下的前驱；若f无左子女，则顺其前驱找双亲的双亲，一直继续到双亲有左子女（这时左子女是p的前驱）。还有一种情况，若p是中序遍历的第一个结点，结点p在中序和后序下均无前驱。
BiThrTree InPostPre (BiThrTree t,p)
//在中序线索二叉树t中，求指定结点p在后序下的前驱结点q {BiThrTree q;
if (p->rtag==0) q=p->rchild; //若p有右子女，则右子女是其后序前驱
else if (p->ltag==0) q=p->lchild; //若p无右子女而有左子女，左子女是其后序前驱。 else if(p->lchild==null) q=null;//p是中序序列第一结点，无后序前驱 else //顺左线索向上找p的祖先，若存在，再找祖先的左子女 {while(p->ltag==1 && p->lchild!=null) p=p->lchild;
if(p->ltag==0) q=p->lchild; //p结点的祖先的左子女是其后序前驱
else q=null; //仅右单枝树（p是叶子），已上到根结点，p结点无后序前驱 }
return(q); }//结束InPostPre
8、线索二叉树有数据域data，左右孩子域lchild和rchild，左右标志ltag及rtag，规定标志为1对应的孩子域是线索，0则为指向孩子的指针。规定在储存线索二叉树时，完成下面中序线索化过程。（存储线索二叉树，不增加头结点，只在原有的由tree指向的二叉树中增加线索，线索化前所有的标志tag都是0）。
/* pre是同tree类型相同的指针，初值是null */ thread_inorder (tree) { if(tree!=null)
{ thread_inorder((1)____);
if(tree->lchild==(2)______) { tree->ltag=1; tree->lchild=pre; } if((3)___ == null){ (4)_______; (5)_______;}
pre=p; thread-inorder((6)_______); } }
（1）tree->lchild (2)null (3)pre->rchild (4)pre->rtag=1 (5) pre->right=tree; (6) tree->right (注（4）和（5）顺序可换)
24
第七章 图 一、单选题
1、在一个图中，所有顶点的度数之和等于图的边数的（ C ）倍。 A、1/2 B、1 C、 2 D、4
2、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）倍。 A、1/2 B、1 C、2 D、4 3、有8个结点的无向图最多有（ B ）条边。
A、14 B、28 C、56 D、112 4、一个n个顶点的连通无向图，其边的个数至少为（ A ）。
A、n-1 B、n C、n+1 D、nlogn； 5、有8个结点的有向完全图有（ C ）条边。
A、14 B、28 C、56 D、112 6、用邻接表表示图进行广度优先遍历时，通常是采用（ B ）来实现算法的。 A、栈 B、队列 C、 树 D、图 7、用邻接表表示图进行深度优先遍历时，通常是采用（ A ）来实现算法的。 A、栈 B、队列 C、树 D、图 8、下面关于求关键路径的说法不正确的是（ C ）。 A、求关键路径是以拓扑排序为基础的
B、一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C、一个事件的最迟开始时间为以该事件为尾的活动最迟开始时间与该活动持续时间的差 D、关键活动一定位于关键路径上
9、已知图的邻接矩阵如下，根据算法思想，则从顶点0出发，按深度优先遍历的结点序列是（ D ）。
?0?1??1?1??1??0??1100100110001001100110101101000011011??1?0??0?0??1?0??A、0 2 4 3 1 5 6 B、0 1 3 5 6 4 2 C、0 4 2 3 1 6 5 D、0 1 3 4 2 5 6 10、下列关于AOE网的叙述中，不正确的是（ B ）。
A、关键活动不按期完成就会影响整个工程的完成时间 B、任何一个关键活动提前完成，那么整个工程将会提前完成
25