2. 计算机
  3. 在由许多项目组成的大型工程中，用顶点表示项目，有向边表示项目之间开始的先后秩序关系，这种用顶点表示活动的图称为AOV网络，其常用的一种存储结构是(15)。 为规划整个工程的实现，通常要对上述的顶点进行(16)排序，据此可获得项目的(17)序列。但并不是所有

在由许多项目组成的大型工程中，用顶点表示项目，有向边表示项目之间开始的先后秩序关系，这种用顶点表示活动的图称为AOV网络，其常用的一种存储结构是(15)。 为规划整个工程的实现，通常要对上述的顶点进行(16)排序，据此可获得项目的(17)序列。但并不是所有

admin2009-02-15  25
问题 在由许多项目组成的大型工程中，用顶点表示项目，有向边表示项目之间开始的先后秩序关系，这种用顶点表示活动的图称为AOV网络，其常用的一种存储结构是(15)。
为规划整个工程的实现，通常要对上述的顶点进行(16)排序，据此可获得项目的(17)序列。但并不是所有图都能获得这样的系列，如(18)图就不能获得这种序列。因为在这种情况下，所体现的先后关系不是(19)。
选项 A、自反的
B、对称的
C、非自反的
D、非对称的
答案C
解析 简单地说，由某个集合上的一个偏序得到该集合上的一个操作，这个操作称之为拓扑排序。偏序和全序的定义是：若X上的关系R是自反的、反对称的和传递的，则称只是集合X上的偏序关系。设只是集合X上的偏序，如果对每个x,yX，必有xRy，则称只是集合X上的全序关系。总地来说就是，偏序指集合中仅有部分成员之间可比较，而全序指集合中全体成员之间均可比较。全序也称为拓扑有序，而由偏序定义得到拓扑有序的操作便是拓扑排序。
   一个偏序的有向图可用来表示施工流程图。在图中，用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网，简称AOV网。在网中，不应该出现有向环，因为存在环意味着某项活动应以自己为先决条件。若设计出这样的流程图，工程便无法进行。
   进行拓扑排序的方法为：(1)在有向图中选一个没有前驱的顶点且输出它；(2)从图中删除该顶点和所有以它为尾的弧；重复这两步，直至全部顶点均己输出，或者当前图中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环。针对这两步操作，可采用邻接表作有向图的存储结构，且在头结点中增加一个存入顶点入度。入度为0的顶点即为没有前驱的顶点，删除顶点及以它为尾的弧的操作，则可换弧头顶点的入度减1来实现。
   所以(15)AOV网络最常用的一种存储结构为邻接表；(16)和(17)分别为拓扑排序和拓扑序列；(18)和(19)是说明若图中有环，则不是反自反的，则不能得到拓扑序列。
转载请注明原文地址:https://kaotiyun.com/show/PtxZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

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