阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
【说明】对有向图进行拓扑排序的方法是：
(1)初始时拓扑序列为空：
(2)任意选择一个入度为0的顶点，将其放入拓扑序列中，同时从图中删除该顶点以及从该顶点出发的弧；
(3)重复(2)，直到不存在入度为0的顶点为止(若所有顶点都进入拓扑序列则完成拓扑排序，否则由于有向图中存在回路无法完成拓扑排序)。函数int*TopSoa(LinkedDigraphG)的功能是对有向图G中的顶点进行拓扑排序，返回拓扑序列中的顶点编号序列，若不能完成拓扑排序，则返回空指针。其中，图G中的顶点从1开始依次编号，顶点序列为v1，v2，…，vn，图G采用邻接表示，其数据类型定义如下：
#def ine NAXVNUM 50 ／*最大顶点数*／
typedef structArcNode( ／*表节点类型*／
int adjvex； ／*邻接顶点编号*／
struct ArcNode*nextarc； ／*指示下一个邻接顶点*／
}ArcNode：
typedef struct Adj List( ／*头节点类型*／
char vdata； ／*顶点的数据信息*／
ArcNode*firstarc； ／*指向邻接表的第一个表节点*／
}Adj List；
typedef struct LinkedDigraph( ／*图的类型*／
int n； ／*图中顶点个数*／
AdjLiSt Vhead[MAXVNUM]； ／*所有顶点的头节点数组*／
}LinkedDigraph；
例如，某有向图G如图15．3所示，其邻接表如图15-4所示。
函数T0pSon中用到了队列结构(Queue的定义省略)，实现队列基本操作的函数原型如表15—2所示：
【C代码】
int *TopSort(LinkedDigraph G) {
ArcNode*P； ／*临时指针，指示表节点*／
Queue Q；／*临时队列，保存入度为0的顶点编号*／
int k=0； ／*临时变量，用作数组元素的下标*／
int j=0，W=0； ／*临时变量，用作顶点编号*／
int*toporder，*inDegree；
toporder=(int*)malloc((G．n+1)*Si zeof(int))； ／*存储拓扑序列中的顶点编号*／
inDegree=(int*)malloc((G．n+1)*sizeof(int))； ／*存储图G中各顶点的入度*／
if(!inDegree I I!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)；
whi le(!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*／
函数T0pSon中用到了队列结构(Queue的定义省略)，实现队列基本操作的函数原型如表15—2所示：
【C代码】
int *TopSort(LinkedDigraph G) {
ArcNode*P； ／*临时指针，指示表节点*／
Queue Q；／*临时队列，保存入度为0的顶点编号*／
int k=0； ／*临时变量，用作数组元素的下标*／
int j=0，W=0； ／*临时变量，用作顶点编号*／
int*toporder，*inDegree；
toporder=(int*)malloc((G．n+1)*Si zeof(int))； ／*存储拓扑序列中的顶点编号*／
inDegree=(int*)malloc((G．n+1)*sizeof(int))； ／*存储图G中各顶点的入度*／
if(!inDegree I I!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)；
whi le(!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*／
问答题
根据以上说明和C代码，填充C代码中的空(1)～(5)。
【正确答案】正确答案：(1)InitQueue(&Q)(2)DeQueue(&Q，＆w)(3)inDegree[p．>adjvex] 或其等价形式(4)inDegree[p一>adjvex]或其等价形式(5)k
【答案解析】解析：本题考查数据结构和算法中的拓扑排序算法。在拓扑排序过程中，需要将入度为O的顶点临时临时存储起来。函数中用一个队列暂存入度为0且没有进入拓扑序列的顶点。显然，空(1)处应填入InitQueue(＆Q)。根据注释，空(2)处应填入DeQueue(＆Q，&w)，实现队头元素出队列的处理。题中图采用邻接表存储结构，当指针p指向vi邻接表中的节点时，p一>adjvex表示vi的一个邻接顶点，删除Vi至顶点p一>adjvex的弧的操作实现为顶点p一>adjvex的入度减1，因此，空(3)处应填入inDegree[．p一>adIjvex]，当顶点p一>adjvex的入度为0时，需要将其加入队列，因此空(4)处也应填入inDegree[p>adjvex]。空(5)处判断是否所有顶点都加入拓扑序列，算法中变量k用于对加入序列的项点计数，因此，空(5)处应填入“k
问答题
对于图15—3所示的有向图G，写出函数TopSoa执行后得到的拓扑序列。若将函数T0pSort中的队列改为栈，写出函数TopSon执行后得到的拓扑序列。
【正确答案】正确答案：队列方式：v1 v2 v5 v4 v3 v7 v6 或者1 2 5 4 3 7 6栈方式：v1 v2 v5 v4 v7 v3 v6 或者1 2 5 4 7 3 6
【答案解析】解析：使用栈和队列的差别在于拓扑序列中顶点的排列次序可能不同。对于本题中的有向图，在使用队列的方式下： (1)开始时仅顶点v1的入度为0，因此顶点v1入队； (2)对头顶点v1出队，并进入拓扑序列，然后删除从顶点v1出发的弧后，仅使顶点v2的入度为0，因此顶点v2入队； (3)队头顶点v1出队，并进入拓扑序列，然后删除从顶点v2出发的弧后，仅使顶点v5的入度为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。
问答题
设某有向无环图的顶点个数为n、弧数为e，那么用邻接表存储该图时，实现上述拓扑排序算法的函数TopSo~的时间复杂度是(6)。若有向图采用邻接矩阵表示(例如，图15—3所示有向图的邻接矩阵如图15—5所示)，且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作，那么对于有n个顶点、e条弧的有向无环图，实现上述拓扑排序算法的时间复杂度是(7)。
【正确答案】正确答案：(6)0(n+e)(7)O(n
2
)
【答案解析】解析：以邻接表为存储结构时，计算各项点入度的时间复杂度为O(e)，建立零入度顶点队列的时间复杂度为O(n)。在拓扑排序过程中， (图中无环情况下)每个顶点进出队列各1次，入度减1的操作在while循环中共执行e次，所以总的时间复杂度为O(n+e)。以邻接矩阵为存储结构时，计算各顶点入度时需要遍历整个矩阵，因此时间复杂度为O(n
2
)，建立零入度顶点队列的时间复杂度为O(n)。在拓扑排序过程中， (图中无环情况下)每个顶点进出队列各1次，实现入度减1操作时需遍历每个顶点的行向量1遍(时间复杂度为O(n))，所以总的时间复杂度为O(n
2
)。