拓扑序列是有向无环图中所有顶点的一个线性序列，若有向图中存在弧或存在从顶点v到w的路径，则在该有向图的任一拓扑序列中，v一定在w之前。下面有向图的拓扑序列是（ ）。 A.41235 B.43125 C.42135 D.41325

题目
拓扑序列是有向无环图中所有顶点的一个线性序列，若有向图中存在弧或存在从顶点v到w的路径，则在该有向图的任一拓扑序列中，v一定在w之前。下面有向图的拓扑序列是（ ）。

A.41235
B.43125
C.42135
D.41325
相似考题

1.在有向无环图中,若存在一条从顶点i到顶点j的弧,则在顶点的拓扑序列中,顶点i与顶点j的先后次序是()。

2.拓扑序列是无环有向图中所有顶点的一个线性序列，图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系，(52)为下图所示有向图的一个拓扑序列。A．1 2 3 4 5 6 7B．1 5 2 6 3 7 4C．5 1 2 6 3 4 7D．5 1 2 3 7 6 4

3.● 拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点vi到vj有一条路径，则在该线性序列中，顶点 vi 必然在顶点 vj之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定 （57）（57）A. 包含回路B. 是强连通图C. 是完全图D. 是有向树

4.若有向图中含有一个或多个环,则其顶点间不存在拓扑序列。()此题为判断题(对，错)。

更多“拓扑序列是有向无环图中所有顶点的一个线性序列，若有向图中存在弧或存在从顶点v到w的路径，则在该有向图的任一拓扑序列中，v一定在w之前。下面有向图的拓扑序列是（ ）。 ”相关问题

  • 第1题：

    在有向图G的拓扑序列中,若顶点Vi在顶点Vj之前,则下列情形可能出现的是()

    AG中有弧

    BG中有一条从Vi到Vj的路径

    CG中没有

    DG中有一条从Vj到Vi的路径


    参考答案：ABC

  • 第2题：

    阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。

    【说明】

    对有向图进行拓扑排序的方法是：

    (1)初始时拓扑序列为空；

    (2)任意选择一个入度为0的顶点，将其放入拓扑序列中，同时从图中删除该顶点以及从该顶点出发的弧；

    (3)重复(2)，直到不存在入度为0的顶点为止(若所有顶点都进入拓扑序列则完成拓扑排序，否则由于有向图中存在回路无法完成拓扑排序)。

    函数int*TopSort(LinkedDigraph G)的功能是对有向图G中的顶点进行拓扑排序，返回拓扑序列中的顶点编号序列，若不能完成拓扑排序，则返回空指针。其中，图G中的顶点从1开始依次编号，顶点序列为vl，v2，…，vn，图G采用邻接表表示，其数据类型定义如下：

    define MAXVNUM 50 ／*最大顶点数*／

    typedef struct ArcNode｜ ／*表结点类型*／

    int adjvex； ／*邻接顶点编号*／

    struct ArcNode*nextarc； ／*指示下一个邻接顶点*／

    {ArcNode；

    typedef struct AdjList{ ／*头结点类型*／

    char vdata； ／*顶点的数据信息*／

    ArcNode*firstarc； ／*指向邻接表的第一个表结点*／

    }AdjList；

    typedef struct LinkedDigraph ／*图的类型*／

    int n： ／*图中顶点个数*／

    AdjList Vhead[MAXVNUM]； ／*所有顶点的头结点数组*／

    }LinkedDigraph；

    例如，某有向图G如图4-1所示，其邻接表如图4-2所示。

    函数TopSort中用到了队列结构(Queue的定义省略)，实现队列基本操作的函数原型如下表所示：

    【C代码】

    int*TopSort(LinkedDigraph G){

    ArcNode*P； ／*临时指针，指示表结点*／

    Queue Q； ／*临时队列，保存入度为0的顸点编号*／

    int k=0； ／*临时变量，用作数组元素的下标*／

    int j=0，w=0； ／*临时变量，用作顶点编号*／

    int*topOrder，*inDegree；

    topOrder=(int*)malloc((G．n+1)*sizeof(int))；／*存储拓扑序列中的顶点编号*／

    inDegree=(int*)malloc((G．n+1)*sizeof(int))；／*存储图G中各顶点的入度*／

    if(!inDegree｜｜!topOrder) return NULL；

    (1)； ／*构造一个空队列*／

    for(j=1；j<=Gn；j++){ ／*初始化*／

    topOrder[j]=0；inDegree[j]=0；

    }

    for(j=1；j<=Gn；j++) ／*求图G中各顶点的入度*／

    for(p=G．Vhead[j]．firstarc；p；p=p->nextarc)

    inDegree[P->adjvex]+=1；

    for(j=i；j<=G．n；J++) ／*将图G中入度为0的顶点保存在队列中*／

    if(0==inDegree[j]) EnQueue(&Q，j)；

    while(! IsEmpty(Q)){

    (2); ／*队头顶点出队列并用w保存该顶点的编号*／

    topOrder[k++]=w； ／*将顶点W的所有邻接顶点的入度减l(模拟删除顶点w及该顶点出发的弧的操作)*／

    for(p=G．Vhead[w]．firstarc；p；p=p->nextarc){

    (3)-=1；

    if(0== (4) ) EnQueue(&Q，P->adjvex)；

    }／*for*／

    ｝/ * while*/

    free(inDegree)；

    if( (5) )

    return NULL；

    return topOrder；

    ｝/*TopSort*/

    根据以上说明和C代码，填充C代码中的空(1)


    正确答案：(1)InitQueue(&Q) (2)DeQueue(&Q&w) (3)inDegree[p->adjvex] (4)inDegree[p->adjvexj (5)k!=G．N
    (1)InitQueue(&Q) (2)DeQueue(&Q，&w) (3)inDegree[p->adjvex] (4)inDegree[p->adjvexj (5)k!=G．N 解析：根据空(1)的后面注释是构造一个空队列，程序的开始已经定义了一个队列Q，那么此处只需初始化这个队列即可，所以空(1)应填InitQueue(&Q)。
    根据空(2)后面的解释，如果队列不空，那么就将队列的元素依次出队列，所以空(2)应为DeQueue(＆Q，＆w)。
    空(3)、(4)上下端的功能是将顶点w的所有邻接顶点的入度减l，数组inDegree中存放各个顶点的入度，所以空(3)应为inDegree[p->adjvex]，并判断与顶点w相邻的顶点有没有入度为零的顶点，如果有，就把这个顶点入队列，所以空(4)也填inDegree[p->adjvex]。
    最后，最外层循环结束，如果拓扑序列中元素的个数k不等于定点数n，那么就说明有向图中存在环，返回NULL上，所以空(5)填k!=G．n。

  • 第3题：

    拓扑序列是有向无环图中所有顶点的一个线性序列，若有向图中存在弧或存在从顶点v到w的路径，则在该有向图的任一拓扑序列中，V一定在w之前。下面有向图的拓扑序列是( )

    A.41235

    B.43125

    C.42135

    D.41=325


    正确答案：A

  • 第4题：

    在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。


    正确答案:错误

  • 第5题：

    若已知有向图G=（V，E），其中，顶点的集合为V={v1，v2，v3，v4，v5}，弧的集合为E={， ，，，，}，则G的拓扑序列有哪些？（写出结论即可）


    正确答案:G的拓扑序列有3个，分别是v1,v2,v3,v4,v5；v1,v3,v2,v4,v5和v1,v3,v4,v2,v5。

  • 第6题：

    如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。


    正确答案:回路

  • 第7题：

    用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出相应的顶点，则输出的顶点序列是（）。

    • A、逆拓扑有序
    • B、拓扑有序
    • C、无序
    • D、深度优先遍历序列

    正确答案:A

  • 第8题：

    填空题
    如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。

    正确答案： 回路
    解析： 暂无解析

  • 第9题：

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

    对

    B

    错


    正确答案： 错
    解析： 暂无解析

  • 第10题：

    判断题
    在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。
    A

    对

    B

    错


    正确答案： 错
    解析： 暂无解析

  • 第11题：

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

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

  • 第12题：

    判断题
    在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧。
    A

    对

    B

    错


    正确答案： 对
    解析：

  • 第13题：

    任何有向图的顶点都可以排成拓扑有序序列,而且拓扑序列不唯一。()

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


    参考答案：错误

  • 第14题：

    在一个有向图G的拓扑序列中,顶点Vi排列在Vj之前,说明图G中(59)。A.一定存在弧B.

    在一个有向图G的拓扑序列中，顶点Vi排列在Vj之前，说明图G中（59）。

    A.一定存在弧＜vi,vj＞

    B.一定存在弧＜vj,vi＞

    C.可能存在vi到vj的路径，而不可能存在vj到vi的路径

    D.可能存在vj到vi的路径，而不可能存在vi到vj的路径


    正确答案：C
    拓扑序列是拓扑排序的产出物。对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。由此可见，如果Vi排列在Vj之前，说明可能存在vi到vj的路径，而不可能存在vj到vi的路径。

  • 第15题：

    拓扑序列是无环有向图中所有顶点的一个线性序列，图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系。对于图中的有向图， ( ) 不是其的一个拓扑序列。

    A.1526374
    B.1526734
    C.5123764
    D.5126374

    答案：C
    解析：
    拓扑序列是将有向图中所有顶点排成一个线性序列，并且该序列满足：若在图中存在从顶点Vi到Vj的路径，则在该线性序列中，顶点i必然在顶点Vj之前。对有向图进行拓扑排序的方法如下：① 在有向图中选择一个入度为零(没有前驱)的顶点且输出之：② 从有向图中删除该顶点及从该顶点出发的所有弧；③ 重复上述两步，直至图中不存在入度为0的顶点为止。对于图3-4所示的有向图，进行拓扑排序的顶点序列有：5126374、5126734、1526374和1526734。而选项C的"5123764"不是其中的一个拓扑序列。

  • 第16题：

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


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

  • 第17题：

    在一个有向图中，若存在弧，则在其拓扑序列中，顶点vi，vj，vk的相对次序为（）。


    正确答案:vi，vj，vk

  • 第18题：

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


    正确答案:错误

  • 第19题：

    单选题
    用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出相应的顶点，则输出的顶点序列是（）。
    A

    逆拓扑有序

    B

    拓扑有序

    C

    无序

    D

    深度优先遍历序列


    正确答案： B
    解析： 暂无解析

  • 第20题：

    单选题
    用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是（  ）。
    A

    逆拓扑有序

    B

    拓扑有序

    C

    无序的

    D

    无法判断


    正确答案： B
    解析：

  • 第21题：

    填空题
    在一个有向图中，若存在弧，则在其拓扑序列中，顶点vi，vj，vk的相对次序为（）。

    正确答案： vi，vj，vk
    解析： 暂无解析

  • 第22题：

    填空题
    假定一个有向图的边集为{，，，，，}，对该图进行拓扑排序得到的顶点序列为（）

    正确答案： aebdcf
    解析： 暂无解析

  • 第23题：

    单选题
    在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情况下不可能出现的是（）。
    A

    G中有弧

    B

    G中有一条从Vi到Vj的路径

    C

    G中没有弧

    D

    G中有一条从Vj到Vi的路径


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

相关内容