2. 计算机
  3. 任意一个有向图的拓扑序列(33)。

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

admin2010-01-17  32
问题 任意一个有向图的拓扑序列(33)。
选项 A、可能不存在
B、有一个
C、一定有多个
D、有一个或多个
答案A
解析 本题考查有向图的拓扑序列结构。在有向图中，拓扑序列是通过拓扑排序后得到的所有结点的序列，拓扑排序是指由某个集合上的一个偏序得到该集合上的一个全序。例如，一个软件专业的学生要修课，但有些是基础课，它独立于其他课程，而有些课程必须要在修完某些专业课后才能修，这样各课程之间就形成了一种并立与优先的关系，有向图和它的拓扑序列可以表示这样的关系。对有向图进行拓扑排序的方法是：(1)在有向图中任选一个没有前驱的结点且输出；(2)从图中删除该结点和所有以它为尾的弧。重复上述两步，直到全部顶点均已输出，或当前图中不存在无前驱的结点为止。根据上述的说明我们可以知道，有向图的拓扑序列可能有一个或多个，但在有向图中出现有向环时，因为环意味着某项活动应该以自己为先决条件，在拓扑排序时，环中的结点是不能被排在序列中的，因此，不存在此有向图的拓扑序列。所以，对任意一个有向图而言，其拓扑序列可能不存在，也可能有一个或多个。
转载请注明原文地址:https://kaotiyun.com/show/7gjZ777K
本试题收录于： 程序员上午基础知识考试题库软考初级分类
0

程序员上午基础知识考试

软考初级

相关试题推荐
随机试题
最新回复(0)