工学

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

题目
填空题
有向图G可拓扑排序的判别条件是（）。
如果没有搜索结果，请直接 联系老师 获取答案。
如果没有搜索结果，请直接 联系老师 获取答案。
相似问题和答案

第1题：

下面()方法可以判断出一个有向图是否有环。

A.深度优先遍历

B、拓扑排序

C.求最短路径

D、求关键路径


参考答案：B

第2题：

对无环有向图进行拓扑排序一定能够得到完整的拓扑序列。()

此题为判断题(对，错)。


正确答案：正确

第3题：

为便于判别有向图中是否存在回路,可借助于()。

A.广度优先搜索算法

B.最小生成树算法

C.最短路径算法

D.拓扑排序算法


参考答案：D

第4题：

拓扑排序运算只能用于()

A.带权有向图

B.连通无向图

C.有向无环图

D.无向图


正确答案：C

第5题：

设某有向无环图的顶点个数为n、弧数为e，那么用邻接表存储该图时，实现上述拓扑排序算法的函数TopSort的时间复杂度是(6)。

若有向图采用邻接矩阵表示(例如，图4-1所示有向图的邻接矩阵如图4-3所示)，且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作，那么对于有n个顶点、e条弧的有向无环图，实现上述拓扑排序算法的时问复杂度是(7)。


正确答案：(6)O(n+e) (7)O(n2)
(6)O(n+e) (7)O(n2) 解析：邻接表：对有n个顶点和e条弧的有向图而言，在拓扑排序中，若有向图无环，则每个顶点进出队列各一次，共执行e次，搜索算法时间复杂度是由n和e共同决定的，所以总的时间复杂度为O(n+e)。
当用邻接矩阵：对于每个顶点，查找相邻边的时间复杂度是O(n)，一共有n个顶点，所以总的时间复杂度是O(n2)。

第6题：

拓扑排序算法仅适用于有向无环图。()


参考答案：错误

第7题：

在对有向无环图执行拓扑排序算法之后,入度数组中所有元素的值均为0。()

此题为判断题(对，错)。


参考答案：对

第8题：

● 拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点vi到vj有一条路径，则在该线性序列中，顶点 vi 必然在顶点 vj之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定 （57）

（57）

A. 包含回路

B. 是强连通图

C. 是完全图

D. 是有向树


正确答案：A

第9题：

设有向无环图G中的有向边集合E={,,,},则下列属于该有向图G的一种拓扑排序序列的是()。

A.1,2,3,4

B.2,3,4,1

C.1,4,2,3

D.1,2,4,3


正确答案：A

第10题：

已知有向图G=(V，A)，其中V={a，b，C，d，e}，A={＜a，b＞，＜a，c＞，＜d，c＞，＜d，e＞，＜b，e＞，＜c，e＞}，对该图进行拓扑排序，下面序列中()不是拓扑排序

A.a，d，c，b，e
B.d，a，b，c，e
C.a，b，d，c，e
D.a，b，c，d，e

答案：D
解析：

更多相关问题
相关内容