0*/
{if(t!=NULL)
{if((t->lchild==NULL)&&(t->rchild==NULL))________; countleaf(t->lchild,&count); ________ } }
13．以下程序是二叉链表树中序遍历的非递归算法，请填空使之完善。二叉树链表的结点类型的定义如下：
typedef struct node /*C语言/
{char data; struct node *lchild,*rchild;}*bitree;
void vst(bitree bt) /*bt为根结点的指针*/ { bitree p; p=bt; initstack(s); /*初始化栈s为空栈*/
while(p || !empty(s)) /*栈s不为空*/
if(p) { push (s,p); (1)___ ; } /*P入栈*/
else { p=pop(s); printf(“%c”,p->data);(2)__ __; }/*栈顶元素出栈*/
}
14．二叉树存储结构同上题，以下程序为求二叉树深度的递归算法，请填空完善之。
int depth(bitree bt) /*bt为根结点的指针*/ {int hl,hr;
if (bt==NULL) return((1)_ __); hl=depth(bt->lchild); hr=depth(bt->rchild);
if((2)_ __) (3)_ ____； return(hr+1); }
15．将二叉树bt中每一个结点的左右子树互换的C语言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队，出队和判别队列是否为空的函数，请填写算法中得空白处，完成其功能。
typedef struct node
{int data ; struct node *lchild, *rchild; }btnode; void EXCHANGE(btnode *bt) {btnode *p, *q;
if (bt){ADDQ(Q,bt);
while(!EMPTY(Q))
{p=DELQ(Q); q=(1)_ __; p->rchild=(2)_ __; (3)__ _=q;
if(p->lchild) (4)_ __; if(p->rchild) (5)_ __; }
} }//
24
四、应用题
1．树和二叉树之间有什么样的区别与联系？
2．分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
3．分别给出下图所示二叉树的先根、中根和后根序列。
4．一个深度为L的满K叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树，如果按层次顺序从1开始对全部结点进行编号，求：
1）各层的结点的数目是多少？
2）编号为n的结点的双亲结点（若存在）的编号是多少？
3）编号为n的结点的第i 个孩子结点（若存在）的编号是多少？
4）编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？ 请给出计算和推导过程。
5．将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果） D G A J H I E B C K N O L M F P 6．设二叉树BT的存储结构如下:
1 2 3 4 5 6 7 8 9 10 Lchild Data Rchild 0 0 J H 0 0 2 F 0 3 D 7 B 5 A 8 C 0 10 1 I 0 0 E G 9 4 0 0 0 其中BT为树根结点的指针，其值为6,Lchild,Rchild分别为结点的左、右孩子指针域,data
为结点的数据域。试完成下列各题:
（l）画出二叉树BT的逻辑结构;
（2）写出按前序、中序、后序遍历该二叉树所得到的结点序列; （3）画出二叉树的后序线索树。 7．设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文
的编码最短。
25
五、算法设计题
1．要求二叉树按二叉链表形式存储，
（1）写一个建立二叉树的算法。
（2）写一个判别给定的二叉树是否是完全二叉树的算法。
完全二叉树定义为：深度为K，具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应。此题以此定义为准。 2．设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。
3．有一二叉链表，试编写按层次顺序遍历二叉树的算法。
4．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。
5．对于二叉树的链接实现,完成非递归的中序遍历过程。
6．试写出复制一棵二叉树的算法。二叉树采用标准链接结构。。
7．请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。 二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。
8．已知二叉树以二叉链表存储，编写算法完成：对于树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
9．设一棵二叉树的根结点指针为T，C为计数变量，初值为0，试写出对此二叉树中结点计数的算法：BTLC（T，C）。
10．分别写出算法，实现在中序线索二叉树T中查找给定结点*p在中序序列中的前驱与后继。在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。
26
习题七 图
一、单项选择题
1.设有无向图G=（V，E）和G’=（V’,E’）,如G’为G的生成树，则下面不正确的说法是（ ）
A．G’为G的子图 B．G’为G的连通分量 C．G’为G的极小连通子图且V’=V D．G’是G的无环子图 2.任何一个带权的无向连通图的最小生成树（ ）
A．只有一棵 B．有一棵或多棵 C．一定有多棵 D．可能不存在 3．以下说法正确的是（ ）
A．连通分量是无向图中的极小连通子图。 B．强连通分量是有向图中的极大强连通子图。
C．在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧
A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 5．设无向图的顶点个数为n，则该图最多有（ ）条边。
2
A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n 6．要连通具有n个顶点的有向图，至少需要（ ）条边。
A．n-l B．n C．n+l D．2n
7．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。
A．1/2 B．2 C．1 D．4 8．下列哪一种图的邻接矩阵是对称矩阵？（ ）
A．有向图 B．无向图 C．AOV网 D．AOE网 9. 下列说法不正确的是（ ）。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 B．遍历的基本算法有两种：深度遍历和广度遍历 C．图的深度遍历不适用于有向图 D．图的深度遍历是一个递归过程
10．下面哪一方法可以判断出一个有向图是否有环（回路）：
A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径
11. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。
23
A. O(n) B. O(n+e) C. O(n) D. O(n) 12．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，
E={
A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7 C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7
13. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。
27
A．G中有弧
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路 15．下列关于AOE网的叙述中，不正确的是（ ）。
A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成
二、填空题
1．具有10个顶点的无向图，边的总数最多为______。
2. 设无向图 G 有n 个顶点和e 条边，每个顶点Vi 的度为di（1<=i<=n），则e=______
3. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。
4．下图中的强连通分量的个数为______个。
5．N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_______个非零元素。
6. 在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是__ ____。
7. 对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为______，邻接表的边结点个数为______。
8. 已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是______遍历方法。
9．构造连通网最小生成树的两个典型算法是__ ____。
10. 有向图G可拓扑排序的判别条件是__ ____。 11. Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按__ ____次序依次产生，该算法弧上的权出现___ ___情况时，不能正确产生最短路径。
12.有向图G=(V,E),其中 V(G)={0,1,2,3,4,5}，用
28