有回路的图不能进行拓扑排序。

第1题：

第2题：

第3题：

第4题：

通过拓扑排序能够得到拓扑序列的图一定是一个（）的图。

正确答案:有向无环

第5题：

对一个有向图进行拓扑排序，一定可以将图的所有顶点按其关键码大小排列到一个拓扑有序的序列中。

正确答案:错误

第6题：

有回路的有向图不能完成拓扑排序。

正确答案:正确

第7题：

有向图G可拓扑排序的判别条件是（）。

正确答案:没有回路

第8题：

下面哪一方法可以判断出一个有向图是否有环（回路）（）。

• A、求节点的度
• B、拓扑排序
• C、求最短路径
• D、求关键路径

正确答案:B

第9题：

第10题：

第11题：

第12题：

第13题：

第14题：

第15题：

拓扑排序的主要功能是什么？对于一个存在拓扑序列的有向图，通过拓扑排序得到的拓扑序列是否惟一？

正确答案:拓扑排序的主要功能是检测一个有向图中是否存在回路。对于一个存在拓扑序列的有向图，通过拓扑排序得到的拓扑序列不一定惟一。

第16题：

有回路的图不能进行拓扑排序。

正确答案:正确

第17题：

对于一个有向图，不用拓扑排序，如何判定图中是否存在环？

正确答案:对于无向图，如果在深度优先遍历中遇到回边，则必定存在环。对于有向图，如果从有向图的某个顶点v出发的遍历，在DFS(v)结束之前出现了一条从顶点u指向v的回边，则此有向图必定存在环。因为u在深度优先生成树上是v的子树，即存在u到v的路径，现在又出现一条从u指向v的弧，则它们必然构成一条回路。

第18题：

假定一个有向图的边集为{，，< c，f>，< d，c>，< e，b>，< e，d>}，对该图进行拓扑排序得到的顶点序列为（）

正确答案:aebdcf

第19题：

下面给出的四种操作中，能够检测出一个有向图是否存在回路的是（）。

• A、广度优先搜索
• B、拓扑排序
• C、求最短路径
• D、求关键路径

正确答案:B

第20题：

第21题：

第22题：

第23题：

第24题：