首页 > 试题广场 >

下面其中哪个是正确的?

[单选题]

面是三个关于有向图运算的叙述()

(1) 求有向图结点的拓扑序列,其结果必定是唯一的

(2) 求两个指向结点间的最短路径,其结果必定是唯一的

(3) 求AOE网的关键路径,其结果必定是唯一的

其中哪个是正确的?

  • 只有(1)
  • (1)和(2)
  • 都正确
  • 都不正确
选D
(1)项:有向图的拓扑序列有可能有多个,例如:学生在学习数据结构前必须学习离散数学和计算机基础,学习高等数学却不需要,然后必须学习了高等数学和数据结构才可以学习算法分析与设计,所以在进行拓扑排序时可以将高数在数据结构前学也可以在数据结构后学,这就形成了两种拓扑排序。因此A项错误
(2)项:权值不一样,就会导致最短路径不一样
C项:

首先,在AOE网中,从始点到终点具有最大路径长度(该路径上的各个活动所持续的时间之和)的路径为关键路径。

计算关键路径,只需求出上面的四个特征属性,然后取e(i)=l(i)的边即为关键路径上的边(关键路径可能不止一条)。

先来看看四个特征属性的含义:

Ø Ve(j):是指从始点开始到顶点Vk的最大路径长度


计算技巧:

(1)从前向后,取大值:直接前驱结点的Ve(j)+到达边(指向顶点的边)的权值,有多个值的取较大者

(2)首结点Ve(j)已知,为0


Ø  Vl(j):在不推迟整个工期的前提下,事件vk允许的最晚发生时间


计算技巧:

(1)从后向前,取小值:直接后继结点的Vl(j) –发出边(从顶点发出的边)的权值,有多个值的取较小者;

(2)终结点Vl(j)已知,等于它的Ve(j))


Ø  e(i): 若活动ai由弧<vk,vj>表示,则活动ai的最早开始时间应该等于事件vk的最早发生时间。因而,有:e[i]=ve[k];(即:边(活动)的最早开始时间等于,它的发出顶点的最早发生时间)

Ø  l(i): 若活动ai由弧<vk,vj>表示,则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。 因而有:l[i]=vl[j]-len<vk,vj>1(为边(活动)的到达顶点的最晚发生时间减去边的权值

所以(3)错误
综上,本题选择D项
编辑于 2020-07-09 10:04:25 回复(0)
D
发表于 2020-05-02 16:08:39 回复(0)