itgle.com

37、判断有向图中是否存在回路,除了可以用拓扑排序外,还可以采用()。A.深度优先遍历算法B.最短路径Dijkstra算法C.广度优先遍历算法D.求关键路径的方法

题目

37、判断有向图中是否存在回路,除了可以用拓扑排序外,还可以采用()。

A.深度优先遍历算法

B.最短路径Dijkstra算法

C.广度优先遍历算法

D.求关键路径的方法


相似考题
更多“37、判断有向图中是否存在回路,除了可以用拓扑排序外,还可以采用()。”相关问题
  • 第1题:

    判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用求最短路径的Dijkstra方法。()

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


    参考答案:错误

  • 第2题:

    判定一个有向图中是否存在回路可以利用(52)方法。

    A.求最小生成树

    B.求最短路径

    C.拓扑排序

    D.图的遍历


    正确答案:C
    解析:拓扑排序方法可以判定一个有向图中是否存在回路,所以答案为C。

  • 第3题:

    判断有向图是否存在回路,除了可以利用拓扑排序方法外,还可以利用______。

    A.求关键路径的方法

    B.求最短路径的Dijkstra方法

    C.深度优先遍历算法

    D.广度优先遍历算法


    正确答案:C
    解析:本题考查AOV的运算,要检测一个工程是否可行,首先就应检查对应的AOV网是否存在回路,检测的一种方法就是对有向图构造其顶点的拓扑有序序列,而对AOV网进行拓扑排序主要考虑顶点的入度,相应的,若在AOV网中考查各项点的出度,这种排序就称为逆排序。同时,还可以利用深度优先遍历进行拓扑排序,因为图中无环,则由图中某点出发进行深度优先遍历时,最先退出DFS函数的顶点即是出度为零的顶点,它是拓扑有序序列中最后的一个顶点。由此,按退出DFS函数的先后记录下来的顶点序列即为逆向的拓扑有序序列。

  • 第4题:

    判断一个有向图是否存在回路的方法除了可以利用拓扑排序方法外。还可以用()。

    A.求关键路径的方法
    B.求最短路径的Dijkstra方法
    C.广度优先遍历算法
    D.深入度优先遍历算法

    答案:D
    解析:
    判断一个图是否存在回路的方法包括:(1)设图G是n个顶点的无向图,若G的边数e>=n,则图G中一定有回路存在。(2)设图G是n个顶点的无向连通图,若G的每个顶点的度>=2,则图G中一定有回路存在。(3)利用拓扑排序算法可以判断图中是否存在回路。即在拓扑排序输出结束后所余下的顶点均有前驱,则说明只得到了部分顶点的拓扑有序序列,图中存在有回路。(4)利用深度优先遍历算法可以判定图G中是否存在回路。对于无向图来说,若深度优先遍历过程中遇到了回边则必定存在环;对于有向图来说,这条回边可能是指向深度优先森林中另一棵生成树上顶点的弧;但是,如果从有向图上的某个项点v出发进行深度优先遍历,若在dfs(v)结束之前出现一条认顶点v到顶点v的回边,因u在生成树上是v的孙子,则有向图必定存在半含顶点u和顶点v的环。

  • 第5题:

    下面()可以判断出一个有向图中是否有环(回路)。

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

    正确答案:B

  • 第6题:

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


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

  • 第7题:

    判定一个有向图是否存在回路,除了可以利用拓扑排序的方法外,还可以利用()。

    • A、求关键路径的方法
    • B、求最短路径的Dijkstra方法
    • C、深度优先遍历算法
    • D、广度优先遍历算法

    正确答案:C

  • 第8题:

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

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

    正确答案:B

  • 第9题:

    单选题
    判定一个有向图是否存在回路,除了可以利用拓扑排序的方法外,还可以利用()。
    A

    求关键路径的方法

    B

    求最短路径的Dijkstra方法

    C

    深度优先遍历算法

    D

    广度优先遍历算法


    正确答案: D
    解析: 暂无解析

  • 第10题:

    单选题
    下面哪一方法可以判断出一个有向图是否有环(回路)()。
    A

    求节点的度

    B

    拓扑排序

    C

    求最短路径

    D

    求关键路径


    正确答案: D
    解析: 暂无解析

  • 第11题:

    单选题
    判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以用()。
    A

    求关键路径的方法

    B

    求最短路径的方法

    C

    广度优先遍历算法

    D

    深度优先遍历算法


    正确答案: C
    解析: 当有向图中无回路时,从某顶点出发进行深度优先遍历时,出栈的顺序(退出DFSTraverse算法)即为逆向的拓扑序列。

  • 第12题:

    单选题
    下面()可以判断出一个有向图中是否有环(回路)。
    A

    广度优先遍历

    B

    拓扑排序

    C

    求最短路径

    D

    求关键路径


    正确答案: C
    解析: 暂无解析

  • 第13题:

    采用邻接表存储的图的深度优先遍历算法类似于树的(22),用邻接表存储的图的广度优先遍历算法类似于树的(23),判断有向图是否存在回路,除了可以利用拓扑排序方法外,还可以利用(24)。

    A.中序遍历

    B.先序遍历

    C.后序遍历

    D.按层次遍历


    正确答案:B
    解析:采用邻接表存储的图的深度优先遍历算法类似于树的先序遍历。

  • 第14题:

    可以判断一个有向图中是否含有回路的方法为()。

    A.广度优先遍历

    B.深度优先遍历

    C.拓扑排序

    D.求最短路径


    正确答案:C

  • 第15题:

    判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以用()。

    A.广度优先遍历算法
    B.深度优先遍历算法
    C.求关键路径的方法
    D.求最短路径的方法

    答案:B
    解析:
    当有向图中无回路时,从某顶点出发进行深度优先遍历时,出栈的顺序(退出DFSTraverse算法)即为逆向的拓扑序列。

  • 第16题:

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


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

  • 第17题:

    下面哪一个方法可以判断出一个有向图中是否有环回路()

    • A、深度优先遍历
    • B、拓扑排序
    • C、求最短路径
    • D、求关键路径

    正确答案:A,B

  • 第18题:

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


    正确答案:正确

  • 第19题:

    判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以用()。

    • A、求关键路径的方法
    • B、求最短路径的方法
    • C、广度优先遍历算法
    • D、深度优先遍历算法

    正确答案:D

  • 第20题:

    单选题
    下列方法中可以判断出一个有向图是否有环(回路)的是(  )。
    A

    广度优先遍历

    B

    拓扑排序

    C

    求最短路径

    D

    求关键路径


    正确答案: A
    解析:

  • 第21题:

    多选题
    下面哪一个方法可以判断出一个有向图中是否有环回路()
    A

    深度优先遍历

    B

    拓扑排序

    C

    求最短路径

    D

    求关键路径


    正确答案: D,C
    解析: 暂无解析

  • 第22题:

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

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

  • 第23题:

    判断题
    有回路的有向图不能完成拓扑排序。
    A

    B


    正确答案:
    解析: 暂无解析

  • 第24题:

    问答题
    对于一个有向图,不用拓扑排序,如何判定图中是否存在环?

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