您的位置： 文档网所有分类高等教育工学 数据结构第七章图练习及答案

数据结构第七章图练习及答案

1． 拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。

数据结构第七章图练习及答案

2．写出求以下AOE网的关键路径的过程。要求：给出每一个事件和每一个活动的最早开始时间和最晚开始时间。

数据结构第七章图练习及答案

【解析】解题关键是弄清拓扑排序的步骤

（1）在AOV网中，选一个没有前驱的结点且输出；（2）删除该顶点和以它为尾的弧；（3）重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】（1）0132465 （2）0123465

【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下 （1）求事件的最早发生时间ve(j), 最晚发生时间vl(j);

（2）最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到 vl(0);

（3）计算e(i),l(i)：设ai由弧<j,k>表示，持续时间记为dut<j,k>，则有下式成立 e(i)=ve(j)

l(i)=vl(k)-dut(<j,k>)

（4）找出e(i)-l(i)=0的活动既是关键活动。 【答案】

第1页

你可能喜欢

  • 数据结构练习
  • 关键路径
  • 数据结构考研真题
  • 数据结构习题解析
  • 数据结构二叉树
  • 数据结构算法
  • 数据库设计

数据结构第七章图练习及答案的相关文档搜索

数据结构第七章图练习及答案相关文档

最新文档

返回顶部