5多选下列关于最短路算法的说法正确的有：Therightstatementsofthefollowingare:
A.当图中不存在负权边时，Dijkstra算法能求出每对顶点间最短路径。Whenthegraphdoesn’tcontainedgeofnegativeweight,Dijkstraalgorithmcancalculatetheshortestpathofeachpairofvertices.
B.当图中不存在负权回路但是存在负权边时，Dijkstra算法不一定能求出源点到所有点的最短路。Whenthegraphdoesn’tcontaincircuitofnegativeweight,butcontainstheedgeofnegativeweight.Dijkstraalgorithmcan’tguaranteethecorrectnessofthealgorithm.
C.当图中存在负权回路时，Dijkstra算法也一定能求出源点到所有点的最短路。Whenthegraphcontainsthecircuitofnegativeweight,Dijkstraalgorithmcancertainlycalculatetheshortestpathformthesinglesourcetoallthevertices.
D.Dijkstra算法不能用于每对顶点间最短路计算。Dijkstraalgorithmcan’tbeappliedtocalculatetheshortestpathofeachpairofvertices.
6填空下图中的强连通分量的个数为多少个？Howmanystronglyconnectedgraphsintheundergraph?
7填空如果无向图G=(V,E)是简单图，并且|V|=n>0，那么图G最多包含多少条边？IfundirectedgraphG=(V,E)issimplegraph,and|V|=n>0,thenhowmanyedgescangraphGcontainsatmost？（Thereisonlyonecorrectanswer）
8填空有向图G如下图所示，请写出所有拓扑排序序列。所有的顶点都直接用其数字标号表示，如拓扑排序序列为，那么请写成1234（中间没有空格）。不同的拓扑排序序列按照字典序排序，中间用一个空格隔开。DirectedgraphGlookslikefollowinggraph,pleaselistallthetopologicalordersequences.Alltheverticesaremarkedbynumbersdirectly.LiketopologicalordersequenceV1V2V3V4,wewriteitas1234(withnoblankspace).Differenttopologicalordersequencesaresortedaccordingtoalphabetorder,andseparatedbyablankspace.
9填空无向图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)}，对该图进行深度优先遍历（优先访问编号小的结点），得到的顶点序列为？注意：答案中没有空格UndirectedG=(V,E),concretely:V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},performdepth-firsttraversal(visitthevertexofsmallnumberfirstly),whatverticessequencedoweget? Notice:noblankspaceinanswer.
数据结构与算法
北京大学
军职在线答案
大学网课