2、在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（)。A．G中有弧＜Vi，Vj＞B．G中有一条从Vi到Vj的路径C．G中没有弧＜Vi,Vj＞D．G中有一条从Vj到Vi的路径

题目

2、在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（)。

A．G中有弧＜Vi，Vj＞

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

C．G中没有弧＜Vi,Vj＞

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

相似考题

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

2.在有向图G的拓扑序列中,若顶点Vi在顶点Vj之前,则下列情形可能出现的是()AG中有弧BG中有一条从Vi到Vj的路径CG中没有DG中有一条从Vj到Vi的路径

3.阅读下列说明和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)

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

更多“2、在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（)。”相关问题

  • 第1题：

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

    A.G中有弧

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

    C.G中没有弧

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


    正确答案：D

  • 第2题：

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

    A.41235

    B.43125

    C.42135

    D.41=325


    正确答案：A

  • 第3题：

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


    正确答案:错误

  • 第4题：

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

    • A、G中有弧
    • B、G中有一条从Vi到Vj的路径
    • C、G中没有弧
    • D、G中有一条从Vj到Vi的路径

    正确答案:D

  • 第5题：

    在有向图G中，若对于任意一对顶点都存在两条方向相反的路径，则称有向图G为（）


    正确答案:强连通图

  • 第6题：

    在无向图中定义顶点Vi域Vj之间的路径为从Vi到达Vj的一个（）。

    • A、顶点序列
    • B、边序列
    • C、权值总和
    • D、边的条数

    正确答案:A

  • 第7题：

    在有向图G中，若任意两个顶点Vi和Vj都连通，从VI到Vj和从Vj到Vi都存在路径，则称该图为（）。


    正确答案:强连通图

  • 第8题：

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

    G中有弧

    B

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

    C

    G中没有弧

    D

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


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

  • 第9题：

    单选题
    在无向图中定义顶点vi与vj之间的路径为从vi到vj的一个（）。
    A

    顶点序列

    B

    边序列

    C

    权值总和

    D

    边的条数


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

  • 第10题：

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

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

  • 第11题：

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

    G中有弧

    B

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

    C

    G中没有弧

    D

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


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

  • 第12题：

    填空题
    在有向图G中，若对于任意一对顶点都存在两条方向相反的路径，则称有向图G为（）

    正确答案： 强连通图
    解析： 暂无解析

  • 第13题：

    在一个有向图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的路径。

  • 第14题：

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

    A.41235
    B.43125
    C.42135
    D.41325

    答案：A
    解析：
    拓扑排序通俗一点来讲，其实就是依次遍历没有前驱结点的结点。而某一时刻没有前驱结点的结点有可能存在多个，所以一个图的拓扑排序可能有多个。
    4号结点没有前戏，所以拓扑排序的第一个元素是4。当4访问完了就可以访问1，1号访问完了就可以访问2，2号访问完了就可以访问3或5。所以拓扑排序结果为：412(35)。


  • 第15题：

    在有向图的邻接表中，顶点Vi在表结点中出现的次数是顶点Vi的（）。

    • A、度
    • B、入度
    • C、出度
    • D、依附于顶点Vi的弧数

    正确答案:B

  • 第16题：

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


    正确答案:vi，vj，vk

  • 第17题：

    若在有向图G中存在一条弧i,Vj>，则称顶点Vj（）于顶点Vi。


    正确答案:邻接

  • 第18题：

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

    • A、G中有弧
    • B、G中有一条从Vi到Vj的路径
    • C、G中没有弧
    • D、G中有一条从Vj到Vi的路径

    正确答案:D

  • 第19题：

    单选题
    在有向图的邻接表中，顶点Vi在表结点中出现的次数是顶点Vi的（）。
    A

    度

    B

    入度

    C

    出度

    D

    依附于顶点Vi的弧数


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

  • 第20题：

    填空题
    在有向图G中，若任意两个顶点Vi和Vj都连通，从VI到Vj和从Vj到Vi都存在路径，则称该图为（）。

    正确答案： 强连通图
    解析： 暂无解析

  • 第21题：

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

    G中有弧<Vi，Vj>

    B

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

    C

    G中没有弧<Vi，Vj>

    D

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


    正确答案： D
    解析：

  • 第22题：

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

    对

    B

    错


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

  • 第23题：

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

    对

    B

    错


    正确答案： 对
    解析：

  • 第24题：

    填空题
    若在有向图G中存在一条弧i,Vj>，则称顶点Vj（）于顶点Vi。

    正确答案： 邻接
    解析： 暂无解析

相关内容