问答题
【说明】
函数int Toplogcal(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下：
typedef struct Gnode{ /*邻接表的表节点类型*/
int adjvex; /*邻接顶点编号*/
int weieht; /*弧上的权值*/
stract Gnode *nextarc; /*指示下一个弧的节点*/
}Gnode;
typedef struct Adjlist{ /*邻接表的头节点类型*/
char vdata; /*顶点的数据信息*/
struct Gnode *Firstadj; /*指向邻接表的第一个表节点*/
}Adjlist;
typedef struct LinkedWDigraph{ /*图的类型*/
int n,e; /*图中顶点个数和边数*/
struct Adjlist *head; /*指向图中第一个顶点的邻接表的头节点*/
}LinkedWDigraph;
例如，某AOE网如图5-4所示，其邻接表存储结构如图5-5所示。
【正确答案】
【答案解析】(1) indegree[p-＞adjvex]++，及其等价形式
(2) Stack[top--]，及其等价形式
(3) indegree[p-＞adjvex]--，及其等价形式
(4) ve[w]+p-＞weight＞ve[p-＞adjvex]，及其等价形式
(5) ye[w)，及其等价形式
[分析]
本题考查AOE网络及其拓扑排序和关键路径，做题前需要先弄清楚图G的存储结构。
根据注释，空(1)所在for循环用来统计AOE网中各顶点的入度。根据入度的定义及题中AOE网的存储结构，当p不为NULL时，应将p-＞adjvex对应的顶点的入度加1。又数组 indegree正是用来存储各顶点入度的，从紧接着的用来求入度为0的顶点的for循环可看出， indegree数组有效下标是从1到G.n，而顶点的编号正好也是从1开始，故空(1)应填 indegree[p-＞adjvex]++。
各顶点入度统计结束后，收集入度为0的顶点并将其编号保存在栈Stack(数组模拟)中，栈顶指针为数组下表top。
接下来根据各顶点入度进行拓扑排序输出。
空(2)是给变量w赋值，紧接着将w对应的信息输出，根据拓扑排序算法，此处是选择一个入度为0的顶点输出。Stack栈存储的正是入度为0的顶点编号，故空(2)应填Stack[top--]。注意top指向的栈顶，因此不能写成Stack[--top]；另外，这里是出栈操作，不能写成Stack[top]。
根据拓扑排序算法，接下来需要将变量w对应的顶点的所有出边删除，即将对应的顶点的入度减1。类似空(1)，空(3)应填indegree[p-＞adjvex]--。接着判断相应顶点的入度是否为0，为0时将其入栈。
空(4)比较难确定，因程序中并未说明ve数组的用途，注意到函数需要返回关键路径的长度，而至此尚无任何相关语句。因此可以断言ve数组正是为了计算关键路径长度而设置的。关键路径是指从开始到结束点的最长路径，所以只要保证每到一个顶点vx，ve[vx]中存储的都是从开始顶点到vx的最长路径(即顶点vx的最早发生时间)即可。故空(4)应填“ve[w]+p-＞weight＞ve[p-＞adjvex]”。这样，空(5)很容易得出应填“ve[w]”。