如图5-40所示AOE网:1)列出各事件的最早、最迟发生时间2)列出各活动的最早、最迟发生时间3)找出该

己知AOE网中顶点v1～v7分别表示7个事件，弧a1～a10分别表示10个活动，弧上的数值表示每个活动花费的时间，如图8-9所示。那么，该网的关键路径的长度为(40)，活动 a6的松弛时间(活动的最迟开始时间—活动的最早开始时间)为(41)。

A．7

B．9

C．10

D．11

下表给出了某工程各工序之间的优先关系和各工序所需时间。(1)画出相应的AOE网； (2)列出各事件的最早发生时间，最迟发生时间；(3)找出关键路径并指明完成该工程所需最短时间。

【山东大学2002七(15分)】【北京交通大学1995六(15分)】

求出下面AOE网中的关键路径(要求给出各个顶点的最早发生时间和最迟发生时间，并画出关键路径)。【北京交通大学2005五、2(5分)】

某带权有向图如图3-67所示。

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

A．V1、V2、V3、V4、V6、V5、V7、V8

B．V1、V3、V5、V2、V4、V6、V7、V8

C．V1、V2、V3、V4、V5、V6、V7、V8

D．V1、V2、V3、V5、V6、V4、V7、V8

阅读下列函数说明和c代码，将应填入(n)处的字句写在答题纸的对应栏内。

【说明】

函数int Toplogical(Linded WDipaph G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE-网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下：

typedefstruct Gnode{ /* 邻接表的表结点类型*/

iht adjvex; /* 邻接顶点编号*/

iht weight; /* 弧上的权值*/

street Gnode *nextarc; /* 指示下一个弧的结点*/

}Gnode;

typedef struct Adjlist{ /* 邻接表的头结点类型*/

char vdata; /*顶点的数据信息*/

struct Gnode *Firstadj; /* 指向邻接表的第一个表结点*/

}Adjlist;

typedef street LinkedWDigraph{ /* 图的类型*/

int n, e; /* 图中顶点个数和边数*/

struct Adjlist *head; /*指向图中第一个顶点的邻接表的头结点 */

} LinkedWDigraph;

例如，某AOE-网如图5-1所示，其邻接表存储结构如图5-2所示。

【函数】

iht Toplogical(LinkedWDigraph G)

{ Gnode *p;

intj, w, top = 0;

iht *Stack, *ye, *indegree;

ye = (int *)malloe((G.n+1) * sizeof(int));

indegree = (int *)malloc((G.n+1)*sizeof(int)); /* 存储网中各顶点的入度*/

Stack = (int *)malloe((G.n+1)*sizeof(int)); /* 存储入度为0的顶点的编号*/

if(!ve||!indegree || !Stack) exit(0);

for (j = 1;j ＜= G.n;j++) {

ve[j] = 0; indegree[j]= 0;

}/*for*/

for(j= 1;j<=G.n;j++) { /* 求网中各顶点的入度*/

p = G.head[j].Firstadj;

while (p) {

(1); p = p→nextarc;

}/*while*/

}/*for*/

for (j = 1; j ＜= G.n; j++) /*求网中入度为0的顶点并保存其编号*/

if (!indegree[j]) Stack[++top] =j;

while (top ＞ 0) {

w=(2);

printf("%e ", G.head[w].vdata);

p = G.head[w].Firstadj;

while (p) {

(3);

if ( !indegree [p→adjvex])

Staek[++top] = p→adjvex;

if( (4))

ve[p→adjvex] = ve[w] + p→weight;

p = p→nextarc;

}/* while */

}/* while */ return (5); }/*Toplogieal*/

AOV网中，结点表示(1)，边表示(2)。AOE网中，结点表示(3)，边表示(4)。【北京理工大学2001七、3(2分)】

在AOE图中，关键路径上活动的时间延长多少，整个工程的时间也就随之延长多少。( )【大连海事大学2001一、16(1分)】

此题为判断题(对，错)。

下列关于AOE网的叙述中，不正确的是( )。【北方交通大学1999一、7(3分)】【北京工业大学1999一、1(2分)】【哈尔滨工业大学2004二、3(1分)】

A．关键活动不按期完成就会影响整个工程的完成时间

B．任何一个关键活动提前完成，那么整个工程将会提前完成

C．所有的关键活动提前完成，那么整个工程将会提前完成

D．某些关键活动若提前完成，那么整个工程将会提前完成

在AOE(Activuty On Edge)网中，从源点到汇点路径上各个活动的时间总和最长的路径称为__________。【哈尔滨工业大学2005一、2(1分)】

关键路径是AOE网中从源点到汇点的最短路径。( )【北京交通大学2005三、8(2分)】

此题为判断题(对，错)。