2. 计算机
  3. 某带权有向图如图3-67所示。 若忽略边上的权，并将其看做AOV网，那么该AOV网的拓扑排序为(1)。若将该图视为AOE网，那么该AOE网的关键路径有(2)条，其长度为(3)。该AOE网的所有关键活动共有(4)个，V5的最早开始时间和最迟开始时间分

某带权有向图如图3-67所示。 若忽略边上的权，并将其看做AOV网，那么该AOV网的拓扑排序为(1)。若将该图视为AOE网，那么该AOE网的关键路径有(2)条，其长度为(3)。该AOE网的所有关键活动共有(4)个，V5的最早开始时间和最迟开始时间分

admin2019-06-12  27
问题 某带权有向图如图3-67所示。

   若忽略边上的权，并将其看做AOV网，那么该AOV网的拓扑排序为(1)。若将该图视为AOE网，那么该AOE网的关键路径有(2)条，其长度为(3)。该AOE网的所有关键活动共有(4)个，V5的最早开始时间和最迟开始时间分别是(5)。
选项 A、12、12
B、12、13
C、13、12
D、13、13
答案D
解析 拓扑排序的方法是重复执行下列步骤：①从图中选择一个入度为0的结点并输出之；②从图中删除此结点及其所有的出边，直到AOV网中不存在入度为0的顶点为止。在执行步骤①时可能有几个人度为0的结点，任选一个即可，从而导致可能会有多个拓扑排序。根据上述方法，显然可知 (1)选A。AOE网中从源点到汇点路径长度最长的路径叫做关键路径。该AOE网中共有3条关键路径：V1V2V4V6V5V7V8、V1V2V4V6V8、V1V3V5V7V8，其长度均为17。关键路径上的活动称为关键活动，也就是关键路径上所覆盖的有向边。此题中3条关键路径共覆盖了除a5外的所有其它活动，如图3-78所示。

事件Vk的最早发生时间是从源点到汇点的最长路径长度，Vk的最迟发生时间是在不推迟整个工程完成的前提下Vk最迟必须发生的时间。设关键路径长度为X，顶点Vk到汇点的最长路径长度为Y，则Vk的最迟发生时间为X-Y。
转载请注明原文地址:https://kaotiyun.com/show/ApRZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

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