数算coursera图答案

《数算coursera图答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Feedback—图Help窗体顶端Question1下图中的强连通分量的个数为多少个？AnswerforQuestion1Youentered:YourAnswerScoreExplanation3Correct1.00分别为最左边1个点，中间4个点和最右边1个点。Total1.00/1.00Question2如果无向图G=(V,E)是简单图，并且

2、V

3、=n>0，那么图G最多包含多少条边？AnswerforQuestion2Youentered:PreviewHelpYourAnswerScoreExplanatio

4、nn*(n-1)/2Correct1.00∑i=0n−1i=n(n−1)2Total1.00/1.00Question3下面关于图的说法正确的有YourAnswerScoreExplanation对于有向图，每个结点的出度必须要等于入度。Correct0.25所有结点的出度之和与入度之和，但是每个结点并没有出度和入度相等的性质。将有向图的一个强连通分量中的边全部反向仍然是强连通分量。Correct0.25原来强连通分量中的点必须能够互达，边全部反向后，仍然能够互达。而原来强连通分量外的点和强连通分量内的点之间的边没有变

5、化，以前不能互达现在还是不能，这样保证了仍然是极大的强连通子图。对于一个连通图，一定存在一种给边添加方向的方案使得这个图变成强连通图。Correct0.25两个结点用一条边相连，能够形成一个连通图，但是不管怎么给边定向都不能使其成为强连通图。对于无向图，所有结点的度数加起来一定是偶数。Correct0.25结点度数是边数的2倍，故一定为偶数。Total1.00/1.00Question4有向图G如下图所示，请写出所有拓扑排序序列。所有的顶点都直接用其数字标号表示，如拓扑排序序列为v1 v2 v3 v4，那么请写成123

6、4（中间没有空格）。不同的拓扑排序序列按照字典序排序，中间用一个空格隔开。AnswerforQuestion4Youentered:YourAnswerScoreExplanation123413242134Correct1.00Total1.00/1.00Question5无向图G=(V,E)，其中：V={a,b,c,d,e,f}, E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历（优先访问编号小的结点），得到的顶点序列为？注意：答案中没有空格Answ

7、erforQuestion5Youentered:YourAnswerScoreExplanationabedfcCorrect1.00Total1.00/1.00Question6当各边上的权值满足什么要求时，宽度优先搜索算法可用来解决单源最短路径问题？YourAnswerScoreExplanation均互不相等不一定相等均相等Correct1.00宽度优先搜索算法的搜索状态树是一层一层的扩展结点的，而当边权均相等时，步数越少距离越短，所以可以直接用宽度优先搜索算法解决。Total1.00/1.00Question

8、7下列关于最短路算法的说法正确的有：YourAnswerScoreExplanation当图中不存在负权回路但是存在负权边时，Dijkstra算法不一定能求出源点到所有点的最短路。Correct0.25即使是只有负权边，也会导致以前已经被选出来更新其它结点最短路值的结点的最短路值被更新，造成错误。Dijkstra算法不能用于每对顶点间最短路计算。Correct0.25可以执行多次Dijkstra算法实现这一要求。Floyd算法也能够用于单源最短路计算。Correct0.25计算出每对顶点之间的最短路，自然也能得出单源点

9、最短路。Floyd算法不能处理图中有负权回路的情况。Correct0.25只要在Floyd算法执行完成之后，图中还能进行松弛操作，即存在负权回路。Total1.00/1.00Question8请使用Kruskal算法求出下图的最小生成树，依次写出每次被选择的合法的合并代价最小的边的编号（如果同时存在多条边满足要求，选择编号最小的）。顶点a到顶点b(a

10、reExplanation0235142512Correct1.00Total1.00/1.00Question9请使用Prim算法从结点0出发求下图的最小生成树，依次写出每次被加入到最小生成树中边的编号（如果同时存在多条边满足要求，选择编号最小的）。顶点a到顶点b(a