2. 计算机
  3. 阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】对有向图进行拓扑排序的方法是： (1)初始时拓扑序列为空： (2)任意选择一个入度为0的顶点，将其放入拓扑序列中，同时从图中删除该顶点以及从该顶点出发的弧； (3)重复(2)，

阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】对有向图进行拓扑排序的方法是： (1)初始时拓扑序列为空： (2)任意选择一个入度为0的顶点，将其放入拓扑序列中，同时从图中删除该顶点以及从该顶点出发的弧； (3)重复(2)，

admin2014-11-13  24
问题 阅读下列说明和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的顶点保存在队列中*／
i f(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
转载请注明原文地址:https://kaotiyun.com/show/aZDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)