关键路径是AOE网中()。A.最长的回路 B.最短的回路 C.从源点到终点的最长路径 D.从源点到终点的最短路径

正确答案：C

正确答案：C
解析：AOE(Activity On Edge)网是一个有向图，通常用来估算工程的完成时间，图中的顶点表示事件，有向边表示活动，边上的权表示完成这一活动所需的时间。AOE网没有有向回路，存在唯一的入度为O的开始顶点，及唯一的出度为O的结束顶点。对AOE网最关心的两个问题是：完成整个工程至少需要多少时间?哪些活动是影响工程进度的关键?这就引出两个概念：关键路径和关键活动。
  · 关键路径：从开始顶点到结束顶点的最长路径，路径的长度也是工程完成的最少时间。
  · 关键活动：关键路径上的所有活动，关键活动的最大特征是：该活动的最早开始时间等于该活动所允许的最迟开始时间。关键活动拖延时间，整个工程也要拖延时间。求关键路径只需求出起点到终点的最长路径。注意，关键路径不是唯一的。

正确答案：C
解析：带权连通图的某最小生成树的权值之和不一定小于其他生成树的权值之和；对于一个图而言，从源点到终点的最短路径也不一定是惟一的；任意一个AOE网中的关键路径也不一定惟一，因此，只有说法C正确。

正确答案：A

正确答案：B
解析：本题考查AOE网的知识。AOE网是用顶点表示活动，用边表示活动间的优先关系的有向图。在AOE网中，有些活动可以并行地进行，完成工程所需的最少时间是从开始点到完成点的最长路径，即关键路径。

答案：A

解析：

正确答案：A
解析：在带权有向图G中以顶点表示事件，以有向边表示活动，边上的权值表示该活动持续的时间，则这种带权有向图称为用边表示活动的网，简称AOE图。用AOE图表示一项工程计划时，对于一项工程来说，一般有一个开始状态和一个结束状态，所以在AOE网中至少有一个入度为0的开始顶点，称其为源点；另外，应有一个出度为。的结束顶点，称其为汇点。AOE中不应存在有向回路，否则整个工程无法完成。从源点到汇点的路径中，长度最长的路径称为关键路径，所以应选A。

正确答案：C
解析：在AOE网中，用顶点表示活动，用有向边vi，vi＞表示活动vi必须先于活动vi进行。如果在有向环的带权有向图中用有向边表示一个工程中的各项活动，用有向边上的权值表示活动的持续时间，用顶点表示事件，则这种有向图叫做用边表示活动的网络，简称AOE网络。关键路径是指在AOE网络中从源点到汇点的最长路径。拓扑排序、最短路径和计算关键路径都是有向图的重要运算。根据关键路径的定义，正确答案为C。

正确答案：是一道要求读者掌握数据结构中拓扑排序和求关键路径问题的算法分析及设计题。本题的解答思路如下。 AOE网(Activity On Edge network边表示活动的网)是一个带权的有向无环图其中顶点表示事件弧表示活动权表示活动持续的时间。通常AOE网可以用来估算工程的完成时间。 在AOE网中入度为0的顶点为源点出度为0的顶点为汇点。由于有些活动可以并行地执行因此从源点到汇点的路径中长度最长的路径称为关键路径(路径长度即指路径上各种活动持续时间之和)。表示事件的顶点存在最早、最晚发生时间。若以顶点V1表示源点、顶点Vn表示汇点则汇点的最早发生时间和最晚发生时间是一致的并且等于关键路径的长度。 设顶点Vj的最早发生时间用ve(j)表示则ve(j)是指从源点V1到Vj的最长路径长度(时间)。这个时间决定了所有从Vj发出的弧所表示的活动能够开工的最早时间。 ve(j)计算方法为 其中T是所有到达顶点j的弧的集合；dut(Ij＞)是弧Ij＞上的权值；n是网中的顶点数(即汇点的序号)。 显然上式是一个从源点开始的递推公式。Ve(j)的计算必须在Vj的所有前驱顶点的最早发生时间全部求出后才能进行。这样必须对AOE网进行拓扑排序然后按拓扑有序序列逐个求出各顶点事件的最早发生时间。 拓扑排序是将有向无环图中所有顶点排成一个线性序列的过程并且该序列满足：若在有向图中从顶点Vi到Vj有一条路径则在该线性序列中顶点Vi必然在顶点Vj之前。可见拓扑排序序列是由有向图中的所有顶点构成的一个线性序列在这个序列中体现了所有顶点之间的优先关系。 对AOE网进行拓扑排序的步骤如下： ①首先在AOE网中选择一个入度为0(没有前驱)的顶点且输出它。 ②然后从网中删除该顶点并且删除以该顶点为始点的所有引出边。 ③重复上述两个步骤直至网中不存在入度为0的顶点为止。 在拓扑排序过程中有可能同时存在多个入度为0的顶点函数中用顺序栈Stack[]暂存入度为0且没有进入拓扑序列的顶点。 本试题所给出的算法首先申请了3块连续的地址空间分别用来存放关键路径长度、网中各顶点的入度及入度为0的顶点编号它们的首地址分别存放在指针变量Ve、indegree、Stack中。 算法主体是由3个for循环和3个while循环组成。第1个for循环即for(j=1;j=G.n;j++){ve[j]=0; indegree[j]=O;}主要完成数组初始化的功能。 进行拓扑排序之前应先求出网中每个顶点的入度并存入数组indegree[]中从而将“从网中删除该顶点及其与该顶点有关的所有边”的操作转换为“相关顶点的入度减1”一旦发现某个顶点的入度变为0就将其编号压入堆栈。从而将选择入度为0的顶点转化为从Stack中弹出栈顶元素所代表的顶点。 题目中顶点从1开始编号顶点Vi的编号为i第2个for循环代码主要完成求网中各个顶点的入度的功能。 在有向图中若以V2为尾的弧有V2V4＞且权值为30、V2V6＞且权值为50则其的邻接表表示形式是：V2→430→650＾。 因此扫描顶点V2的邻接表可以将邻接于V2的所有顶点的入度加1即(1)空缺处应填入“indegree[p -＞adjvex)++”或其等价形式。 第3个for循环语句主要完成求网中入度为0的顶点并保存其编号的功能。以下代码实现拓扑排序并求解各个顶点时事件的最早发生时间。 由于入度为0的顶点由栈中弹出根据变量w在后续代码中所起的作用——存放网中没有直接前驱的顶点并通过printf语句输出可知(2)空缺处应填入“Stack[top--]”或其等价形式。 然后在网中删除没有直接前驱的顶点和以该顶点为始点的所有引出边并通过内嵌的while循环语句把这些引出边对应的终点的入度减1即将邻接到顶点w的各个顶点(p-＞adjvex)的入度减1再判断它们是否也是入度为0的顶点。因此(3)空缺处应填入“indegree[p-＞adjvex]——”或其等价形式。 同时对于顶点p-＞adjveX而言当删除其所有引入边之后从源点出发到达它的最长路径长度也就计算出来了所以每删除一条到达顶点p-＞adjvex的引入边都要查看一下最长路径长度是否需要更新。因此(4)空缺处填入“ve[w]+p-＞weight＞ve[p-＞adjvex]”或其等价形式。 算法程序的最后部分通过return语句返回该图的关键路径长度即汇点的最早发生时间(该AOE网的关键路径长度)。由于AOE网中汇点未必是编号最大的顶点但它必然是从栈中弹出的最后一个顶点因此(5)空缺处填入“ve[w]”或其等价形式。
是一道要求读者掌握数据结构中拓扑排序和求关键路径问题的算法分析及设计题。本题的解答思路如下。 AOE网(Activity On Edge network，边表示活动的网)是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续的时间。通常，AOE网可以用来估算工程的完成时间。 在AOE网中，入度为0的顶点为源点，出度为0的顶点为汇点。由于有些活动可以并行地执行，因此从源点到汇点的路径中，长度最长的路径称为关键路径(路径长度即指路径上各种活动持续时间之和)。表示事件的顶点存在最早、最晚发生时间。若以顶点V1表示源点、顶点Vn表示汇点，则汇点的最早发生时间和最晚发生时间是一致的，并且等于关键路径的长度。 设顶点Vj的最早发生时间用ve(j)表示，则ve(j)是指从源点V1到Vj的最长路径长度(时间)。这个时间决定了所有从Vj发出的弧所表示的活动能够开工的最早时间。 ve(j)计算方法为 其中，T是所有到达顶点j的弧的集合；dut(I,j＞)是弧I,j＞上的权值；n是网中的顶点数(即汇点的序号)。 显然，上式是一个从源点开始的递推公式。Ve(j)的计算必须在Vj的所有前驱顶点的最早发生时间全部求出后才能进行。这样必须对AOE网进行拓扑排序，然后按拓扑有序序列逐个求出各顶点事件的最早发生时间。 拓扑排序是将有向无环图中所有顶点排成一个线性序列的过程，并且该序列满足：若在有向图中从顶点Vi到Vj有一条路径，则在该线性序列中，顶点Vi必然在顶点Vj之前。可见，拓扑排序序列是由有向图中的所有顶点构成的一个线性序列，在这个序列中体现了所有顶点之间的优先关系。 对AOE网进行拓扑排序的步骤如下： ①首先在AOE网中选择一个入度为0(没有前驱)的顶点且输出它。 ②然后从网中删除该顶点，并且删除以该顶点为始点的所有引出边。 ③重复上述两个步骤，直至网中不存在入度为0的顶点为止。 在拓扑排序过程中，有可能同时存在多个入度为0的顶点，函数中用顺序栈Stack[]暂存入度为0且没有进入拓扑序列的顶点。 本试题所给出的算法首先申请了3块连续的地址空间，分别用来存放关键路径长度、网中各顶点的入度及入度为0的顶点编号，它们的首地址分别存放在指针变量Ve、indegree、Stack中。 算法主体是由3个for循环和3个while循环组成。第1个for循环，即for(j=1;j=G.n;j++){ve[j]=0; indegree[j]=O;}，主要完成数组初始化的功能。 进行拓扑排序之前，应先求出网中每个顶点的入度并存入数组indegree[]中，从而将“从网中删除该顶点及其与该顶点有关的所有边”的操作转换为“相关顶点的入度减1”，一旦发现某个顶点的入度变为0，就将其编号压入堆栈。从而将选择入度为0的顶点转化为从Stack中弹出栈顶元素所代表的顶点。 题目中顶点从1开始编号，顶点Vi的编号为i，第2个for循环代码主要完成求网中各个顶点的入度的功能。 在有向图中，若以V2为尾的弧有V2,V4＞且权值为30、V2,V6＞且权值为50，则其的邻接表表示形式是：V2→4，30→6，50＾。 因此，扫描顶点V2的邻接表可以将邻接于V2的所有顶点的入度加1，即(1)空缺处应填入“indegree[p -＞adjvex)++”或其等价形式。 第3个for循环语句主要完成求网中入度为0的顶点并保存其编号的功能。以下代码实现拓扑排序并求解各个顶点时事件的最早发生时间。 由于入度为0的顶点由栈中弹出，根据变量w在后续代码中所起的作用——存放网中没有直接前驱的顶点，并通过printf语句输出，可知(2)空缺处应填入“Stack[top--]”或其等价形式。 然后，在网中删除没有直接前驱的顶点和以该顶点为始点的所有引出边，并通过内嵌的while循环语句把这些引出边对应的终点的入度减1，即将邻接到顶点w的各个顶点(p-＞adjvex)的入度减1，再判断它们是否也是入度为0的顶点。因此(3)空缺处应填入“indegree[p-＞adjvex]——”或其等价形式。 同时，对于顶点p-＞adjveX而言，当删除其所有引入边之后，从源点出发到达它的最长路径长度也就计算出来了，所以每删除一条到达顶点p-＞adjvex的引入边，都要查看一下最长路径长度是否需要更新。因此，(4)空缺处填入“ve[w]+p-＞weight＞ve[p-＞adjvex]”或其等价形式。 算法程序的最后部分，通过return语句返回该图的关键路径长度，即汇点的最早发生时间(该AOE网的关键路径长度)。由于AOE网中汇点未必是编号最大的顶点，但它必然是从栈中弹出的最后一个顶点，因此(5)空缺处填入“ve[w]”或其等价形式。

正确答案：C

答案：B

解析：