{BiTree Q[];//Q是队列，元素为二叉树结点指针，容量足够大
front=1;rear=1;last=1;//front队头指针,rear队尾指针,last同层最右结点在队列中的位置
temp=0; maxw=0; //temp记局部宽度, maxw记最大宽度 Q[rear]=bt; //根结点入队列
while(front<=last)
{p=Q[front++]; temp++; //同层元素数加1
if (p->lchild!=null) Q[++rear]=p->lchild; //左子女入队 if (p->rchild!=null) Q[++rear]=p->rchild; //右子女入队 if (front>last) //一层结束， {last=rear;
if(temp>maxw) maxw=temp;//last指向下层最右元素, 更新当前最大宽度 temp=0; }//if
}//while
return (maxw); }//结束width
（6）用按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目。 int Level(BiTree bt) //层次遍历二叉树，并统计度为1的结点的个数 {int num=0; //num统计度为1的结点的个数
if(bt){QueueInit(Q); QueueIn(Q,bt)；//Q是以二叉树结点指针为元素的队列
while(!QueueEmpty(Q))
{p=QueueOut(Q); printf(p->data); //出队,访问结点
if(p->lchild && !p->rchild ||!p->lchild && p->rchild)num++;//度为
1的结点
if(p->lchild) QueueIn(Q,p->lchild); //非空左子女入队 if(p->rchild) QueueIn(Q,p->rchild); //非空右子女入队 } }//if(bt)
return(num); }//返回度为1的结点的个数
（7）求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。 [题目分析]因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。
void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度
{BiTree p=bt,l[],s[]; //l, s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点
int i，top=0,tag[],longest=0;
while(p || top>0)
{ while(p) {s[++top]=p；tag[top]=0; p=p->Lc;} //沿左分枝向下 if(tag[top]==1) //当前结点的右分枝已遍历
{if(!s[top]->Lc && !s[top]->Rc) //只有到叶子结点时，才查看路径长度
if(top>longest) {for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--;}
//保留当前最长路径到l栈，记住最高栈顶指针，退栈
}
else if(top>0) {tag[top]=1; p=s[top].Rc;} //沿右子分枝向下 }//while(p!=null||top>0) }//结束LongestPath
（8）输出二叉树中从每个叶子结点到根结点的路径。
[题目分析]采用先序遍历的递归方法，当找到叶子结点*b时，由于*b叶子结点尚未添加到path中，因此在输出路径时还需输出b->data值。对应的递归算法如下： void AllPath(BTNode *b,ElemType path[],int pathlen) {
int i;
if (b!=NULL) {
if (b->lchild==NULL && b->rchild==NULL) //*b为叶子结点 {
cout << \到根结点路径:\ for (i=pathlen-1;i>=0;i--) cout << endl; } else
{
path[pathlen]=b->data; //将当前结点放入路径中 pathlen++; //路径长度增1 AllPath(b->lchild,path,pathlen); //递归扫描左子树 AllPath(b->rchild,path,pathlen); //递归扫描右子树 pathlen--; //恢复环境 } } }
第6章
1．选择题
图
（1）在一个图中，所有顶点的度数之和等于图的边数的（ ）倍。 A．1/2 B．1 C．2 D．4
（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A．1/2 B．1 C．2 D．4
（3）具有n个顶点的有向图最多有（ ）条边。
2
A．n B．n(n-1) C．n(n+1) D．n
（4）n个顶点的连通图用邻接距阵表示时，该距阵至少有（ ）个非零元素。 A．n B．2(n-1) C．n/2 D．n （5）G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。
A．7 B．8 C．9 D．10 （6）若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（ ）图。
A．非连通 B．连通 C．强连通 D．有向
（7）下面（ ）算法适合构造一个稠密图G的最小生成树。
A． Prim算法 B．Kruskal算法 C．Floyd算法 D．Dijkstra算法 （8）用邻接表表示图进行广度优先遍历时，通常借助（ ）来实现算法。 A．栈 B. 队列 C. 树 D．图 （9）用邻接表表示图进行深度优先遍历时，通常借助（ ）来实现算法。 A．栈 B. 队列 C. 树 D．图 （10）深度优先遍历类似于二叉树的（ ）。
A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历 （11）广度优先遍历类似于二叉树的（ ）。
A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历 （12）图的BFS生成树的树高比DFS生成树的树高（ ）。
A．小 B．相等 C．小或相等 D．大或相等 （13）已知图的邻接矩阵如图6.25所示，则从顶点0出发按深度优先遍历的结果是
?0?1??1?1??1??0??1100100110001001100110101101000011011??1?0??0?0??1?0??2
A．0 2 4 3 1 5 6
B．0 1 3 6 5 4 2 C．0 1 3 4 2 5 6 D．0 3 6 1 5 4 2
（ ）。
图6.25 邻接矩阵
（14）已知图的邻接表如图6.26所示，则从顶点0出发按广度优先遍历的结果是（ ），按深度优先遍历的结果是（ ）。
A．0 1 3 2 B．0 2 3 1 C．0 3 2 1 D．0 1 2 3
图6.26 邻接表
（15）下面（ ）方法可以判断出一个有向图是否有环。
A．深度优先遍历 B．拓扑排序 C．求最短路径 D．求关键路径 2．应用题
（1）已知如图6.27所示的有向图，请给出： ① 每个顶点的入度和出度； ② 邻接矩阵；
③ 邻接表；
④ 逆邻接表。
图6.27 有
（2）已知如图6.28所示的无向网，请给出： ① 邻接矩阵； ② 邻接表； ③ 最小生成树 a b c d e f g h
→ b 4 → c 3 → a 4 → c 5 → a 3 → b 5 → b 5 → c 5 → b 9 → d 7 → d 6 → e 3 → d 5 → f 2 → c 5 → d 4 → d → d → e → f → g → h → g 5 5 7 3 2 6 6 → e → h → f ^ ^ ^ ^
? 4 ? 5 5? ? 3 ??????????????59???5???5??43??9????????? 5 ? ?4??????6?????
图6.28 无
5 ? 5 ? ? ?
?76547?3??63?2?5?2?6
9 ^ 5 ^ 6 → g 5 → h 4^
（3）已知图的邻接矩阵如6.29所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。