发布时间 : 星期三 文章数据结构（C语言版）（第2版）课后习题答案更新完毕开始阅读b177ff4fa88271fe910ef12d2af90242a895abf4
{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--; //恢复环境 }
}// if (b!=NULL) }//算法结束
43
第6章 图
1．选择题
（1）在一个图中，所有顶点的度数之和等于图的边数的（ ）倍。 A．1/2 B．1 C．2 D．4 答案：C
（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A．1/2 B．1 C．2 D．4 答案：B
解释：有向图所有顶点入度之和等于所有顶点出度之和。 （3）具有n个顶点的有向图最多有（ ）条边。
A．n B．n(n-1) C．n(n+1) D．n2 答案：B
解释：有向图的边有方向之分，即为从n个顶点中选取2个顶点有序排列，结果为n(n-1)。 （4）n个顶点的连通图用邻接距阵表示时，该距阵至少有（ ）个非零元素。 A．n B．2(n-1) C．n/2 D．n2 答案：B
（5）G是一个非连通无向图，共有28条边，则该图至少有（ ）个顶点。 A．7 B．8 C．9 D．10 答案：C
解释：8个顶点的无向图最多有8*7/2=28条边，再添加一个点即构成非连通无向图，故
至少有9个顶点。
（6）若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（ ）图。
A．非连通 B．连通 C．强连通 D．有向 答案：B
解释：即从该无向图任意一个顶点出发有到各个顶点的路径，所以该无向图是连通图。 （7）下面（ ）算法适合构造一个稠密图G的最小生成树。
A． Prim算法 B．Kruskal算法 C．Floyd算法 D．Dijkstra算法 答案：A
解释：Prim算法适合构造一个稠密图G的最小生成树，Kruskal算法适合构造一个稀疏
图G的最小生成树。
（8）用邻接表表示图进行广度优先遍历时，通常借助（ ）来实现算法。 A．栈 B. 队列 C. 树 D．图 答案：B
解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。
44
（9）用邻接表表示图进行深度优先遍历时，通常借助（ ）来实现算法。 A．栈 B. 队列 C. 树 D．图 答案：A
解释：广度优先遍历通常借助队列来实现算法，深度优先遍历通常借助栈来实现算法。 （10）深度优先遍历类似于二叉树的（ ）。
A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历 答案：A
（11）广度优先遍历类似于二叉树的（ ）。
A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历 答案：D
（12）图的BFS生成树的树高比DFS生成树的树高（ ）。
A．小 B．相等 C．小或相等 D．大或相等 答案：C
解释：对于一些特殊的图，比如只有一个顶点的图，其BFS生成树的树高和DFS生
成树的树高相等。一般的图，根据图的BFS生成树和DFS树的算法思想，BFS生成树的树高比DFS生成树的树高小。
（13）已知图的邻接矩阵如图6.30所示，则从顶点v0出发按深度优先遍历的结果是（ ）。
图6.30 邻接矩阵
（14）已知图的邻接表如图6.31所示，则从顶点v0出发按广度优先遍历的结果是（ ），按深度优先遍历的结果是（ ）。
图6.31 邻接表
A．0 1 3 2 答案：D、D
B．0 2 3 1 C．0 3 2 1 D．0 1 2 3
45
（15）下面（ ）方法可以判断出一个有向图是否有环。
A．深度优先遍历 B．拓扑排序 C．求最短路径 D．求关键路径 答案：B 2．应用题
（1）已知图6.32所示的有向图，请给出： ① 每个顶点的入度和出度； ② 邻接矩阵； ③ 邻接表；
④ 逆邻接表。
图6.32 有向图 图6.33 无向网
答案：
（2）已知如图6.33所示的无向网，请给出： ① 邻接矩阵； ② 邻接表； ③ 最小生成树 答案：
46