违法和不良信息举报 联系客服
免费注册 登录

任一个有向图的拓扑序列（）。

题目
单选题
任一个有向图的拓扑序列（）。
A

不存在

B

有一个

C

一定有多个

D

有一个或多个

如果没有搜索结果或未解决您的问题，请直接 联系老师 获取答案。
相似问题和答案

第1题：

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

A．1 2 3 4 5 6 7

B．1 5 2 6 3 7 4

C．5 1 2 6 3 4 7

D．5 1 2 3 7 6 4


正确答案：B
解析：本题考查有向图的应用。
  拓扑排序是将有向图中所有顶点排成一个线性序列的过程，并且该序列满足：若在图中存在从顶点vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点cj之前。
  对有向图进行拓扑排序的方法如下：
  ①在有向图中选择一个入度为零(没有前驱)的顶点且输出之；
  ②从网中删除该顶点及从该顶点出发的所有弧；
  ③重复上述两步，直至图中不存在入度为零的顶点为止。
  对题目中所给的有向图进行拓扑排序的顶点序列为：5126374、5126734、1526374、 1526734。

第2题：

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

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


正确答案：正确

第3题：

若有向图有2个有向回路,则其拓扑序列有()个。


参考答案：0

第4题：

任意一个有向图的拓扑序列()。

A、不存在

B、只有一个

C、一定有多个

D、有一个或多个


答案：D

第5题：

对于图4-1所示的有向图G，写出函数TopSort执行后得到的拓扑序列。若将函数TopSort中的队列改为栈，写出函数TopSort执行后得到的拓扑序列。


正确答案：队列：vl、v2、v5、v4、v3、v7、v6 栈：v1、v2、v5、v4、v7、v3、v6
队列：vl、v2、v5、v4、v3、v7、v6 栈：v1、v2、v5、v4、v7、v3、v6 解析：首先根据原图，可以得出本题中只有V3和V7是同时入队或入栈的。
[*]

第6题：

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

（57）

A. 包含回路

B. 是强连通图

C. 是完全图

D. 是有向树


正确答案：A

第7题：

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

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


参考答案：错误

第8题：

下面的有向图，其结点可以排成多少个不同的拓扑序列？

A．3

B．5

C．7

D．9


正确答案：C

第9题：

任意一个有向图的拓扑序列(33)。

A．可能不存在

B．有一个

C．一定有多个

D．有一个或多个


正确答案：A
解析：本题考查有向图的拓扑序列结构。在有向图中，拓扑序列是通过拓扑排序后得到的所有结点的序列，拓扑排序是指由某个集合上的一个偏序得到该集合上的一个全序。例如，一个软件专业的学生要修课，但有些是基础课，它独立于其他课程，而有些课程必须要在修完某些专业课后才能修，这样各课程之间就形成了一种并立与优先的关系，有向图和它的拓扑序列可以表示这样的关系。对有向图进行拓扑排序的方法是：(1)在有向图中任选一个没有前驱的结点且输出；(2)从图中删除该结点和所有以它为尾的弧。重复上述两步，直到全部顶点均已输出，或当前图中不存在无前驱的结点为止。根据上述的说明我们可以知道，有向图的拓扑序列可能有一个或多个，但在有向图中出现有向环时，因为环意味着某项活动应该以自己为先决条件，在拓扑排序时，环中的结点是不能被排在序列中的，因此，不存在此有向图的拓扑序列。所以，对任意一个有向图而言，其拓扑序列可能不存在，也可能有一个或多个。

第10题：

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

A.41235

B.43125

C.42135

D.41=325


正确答案：A

更多相关问题
相关内容