阅读下列说明和C代码，回答问题。
[说明]
对有向图进行拓扑排序的方法是：
(1)初始时拓扑序列为空。
(2)任意选择一个入度为0的顶点，将其放入拓扑序列中，同时从图中删除该顶点以及从该顶点出发的弧。
(3)重复(2)，直到不存在入度为0的顶点为止(若所有顶点都进入拓扑序列则完成拓扑排序，否则由于有向图中存在回路无法完成拓扑排序)。
函数int* TopSort(LinkedDigraph G)的功能是对有向图G中的顶点进行拓扑排序，返回拓扑序列中的顶点编号序列，若不能完成拓扑排序，则返回空指针。其中，图G中的顶点从1开始依次编号，顶点序列为v1，v2，...，vn，图G采用邻接表示，其数据类型定义如下。
#define MAXVNUM 50 /*最大顶点数*/
typedef struct ArcNode /*表节点类型*/
int adjvex; /*邻接顶点编号*/
struct ArcNode *nextarc; /*指示下一个邻接顶点*/
ArcNode；
typedef struct AdjList /*头节点类型*/
char vdata; /*顶点的数据信息*/
ArcNode *firstarc;
/*指向邻接表的第一个表结点*/AdjList;
typedef struct LinkedDigraph
/*图的类型*/
int n;
/*图中顶点个数*/AdjList Vhead [MAXVNUM]；
/*所有顶点的头结点数组*/
LinkedDigraph;
例如，某有向图G如图8.8所示，其邻接表如图8.9所示。
函数TopSort中用到了队列结构(Queue的定义省略)，实现队列基本操作的函数原型如下表所示：
[C代码]
int *TODSort (LinkedDigraph G) ArcNode *p;
/*临时指针，指示表结点*/
Queue Q;/*临时队列，保存入度为0的顶点编号*/
int k=0；
/*临时变量，用作数组元素的下标*/
int j=0，w=0；
/*临时变量，用作顶点编号*/
int *topOrdert *inDegree;
topOrder=(int*)malloc((G.n+1)*sizeof (int));/*存储拓扑序列中的顶点编号*/
inDegree=(int+)malloc( (G.n+l)+sizeof (int))j/*存储图G中各顶点的入度*/
if (!inDegree || !topOrder) return NULL;
(1) ;/*构造一个空队列*/
for(j=1;j＜=G.n; j++) /*初始化*/
topOrder[j] =0;
inDegree[j] =0;for(j=1；j＜=G.n；j++)
/*求图G中各顶点的入度*/
for(p=G.Vhead[j].firstarc; p;p=p-＞nextarc)
inDegree [p-＞ adjvex] +=1;
for(j=1；j＜=G．n; j++) /*将图G中入度为0的顶点保存在队列中*/
if(0==inDegree[j] )EnQueue(＆Q,j)；
while(!IsEmpty (Q))
(2) ; /*队头顶点出队列并用w保存该顶点的编号*/
topOrder[k++]=w;
/*将顶点w的所有邻接顶点的入度减1(模拟删除顶点w及从该顶点出发的弧的操作)*/
for(p=G.Vhead[w].firstarc; p;p=p-＞nextarc)
(3) -=1；
if (0== (4) ) EnQueue (＆Q, p-＞adjvex);
/*for*/
/*while*/
free (inDegree)；
if ( (5) )
return NULL;
return topOrder;
/*TopSort*/
[问题1]
根据以上说明和C代码，填充C代码中的空(1)～(5)。
[问题2]
对于图8.8所示的有向图G，写出函数TopSort执行后得到的拓扑序列。若将函数TopSort中的队列改为栈，写出函数TopSort执行后得到的拓扑序列。
[问题3]
设某有向无环图的顶点个数为n、弧数为e，那么用邻接表存储该图时，实现上述拓扑排序算法的函数TopSort的时间复杂度是 (6) 。
若有向图采用邻接矩阵表示(例如，图8.8所示有向图的邻接矩阵如图8.10所示)，且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作，那么对于有n个顶点、e条弧的有向无环图，实现上述拓扑排序算法的时间复杂度是 (7) 。
参考答案：
[问题A]
(A) InitQueue(＆Q)
(B) DeQueue(＆Q,＆w)
(C) inDegree[p-＞adjvex] 或其等价形式
(D) inDegree[p-＞adjvex] 或其等价形式
(E)k＜G.n 或k!=G.n 或其等价形式
[问题B]
队列方式：vA vB vE vD vC vG vF 或者A B E D C G F
栈方式：vA vB vE vD vG vC vF 或者A B E D G C F
[问题C]
(F)D(n+e) (G)O(nB)
解析：
[要点解析] 本题考查数据结构和算法中的拓扑排序算法。
[问题1]
在拓扑排序过程中，需要将入度为0的顶点临时存储起来。函数中用一个队列暂存入度为0且没有进入拓扑序列的顶点。显然，空(1)处应填入InitQueue(＆Q)。
根据注释，空(2)处应填入DeQueue(＆Q，＆W)，实现队头元素出队的处理。
题中图采用邻接表存储结构，当指针p指向Vi邻接表中的结点时，p-＞adjvex表示vi的一个邻接顶点，删除vi至顶点p-＞adjvex的弧的操作实现为顶点p-＞adjvex的入度减1，因此，空(3)处应填入inDegree[p-＞adjvex]，当顶点p-＞adjvex的入度为0时，需要将其加入队列，因此空(4)处也应填入inDegree[p-＞adjvex]。
空(5)处判断是否所有顶点都加入拓扑序列，算法中变量k用于对加入序列的顶点计数，因此，空(5)处应填入“k＜G.n”或“k!=G.n”。
[问题2]
使用栈和队列的差别在于拓扑序列中顶点的排列次序可能不同。对于本题中的有向图，在使用队列的方式下：
(1)开始时仅顶点v1的入度为0，因此顶点v1入队。
(2)对队头顶点v1出队，并进入拓扑序列，然后删除从顶点v1出发的弧后，仅使顶点v2的入度为0，因此顶点V2入队。
(3)队头顶点v1出队，并进入拓扑序列，然后删除从顶点v2出发的弧后，仅使顶点v2的入度为i，因此顶点v5入队。
(4)队头顶点v5出队，并进入拓扑序列，然后删除从顶点v5出发的弧后，仅使顶点v4的入度为0，因此顶点v4入队。
(5)队头顶点v4出队，并进入拓扑序列，然后删除从顶点v4出发的弧后，仅使顶点v3和v的入度为0，因此顶点v3和v7依次入队。
(6)队头顶点v3出队，并进入拓扑序列，然后删除从顶点v3出发的弧后，没有产生新的入度为0的顶点。
(7)队头顶点v7出队，并进入拓扑序列，然后删除从顶点v7出发的弧后，使顶点v6的入度为0，因此顶点v6入队。
(8)队头顶点v6出队，并进入拓扑序列，然后删除从顶点v6出发的弧后，没有产生新的入度为0的顶点，队列已空，因此结束拓扑排序过程，得到的拓扑序列为v1 v2 v5 v4 v3 v7 v6。
使用栈保存入度为0的顶点时，前4步都是一样的，因为每次仅有一个元素进栈，因此出栈序列与入栈序列一致。到第5步时，v3和v7依次入栈后，出栈时的次序为v7和v3，因此得到的拓扑序列为v1 v2 v5 v4 v7 v3 v6。
[问题3]
以邻接表为存储结构时，计算各顶点入度的时间复杂度为O(e)，建立零入度顶点队列的时间复杂度为O(n)。在拓扑排序过程中，(图中无环情况下)每个顶点进出队列各1次，入度减1的操作在while循环中共执行e次，所以总的时间复杂度为O(n+e)。
以邻接矩阵为存储结构时，计算各项点入度时需要遍历整个矩阵，因此时间复杂度为O(n2)，建立0入度顶点队列的时间复杂度为O(n)。在拓扑排序过程中，(图中无环情况下)每个顶点进出队列各1次，实现入度减1操作时需遍历每个顶点的行向量1遍(时间复杂度为O(n))，所以总的时间复杂度为O(n2)。