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

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

admin2014-11-13  117
问题 阅读下列说明和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*／
设某有向无环图的顶点个数为n、弧数为e，那么用邻接表存储该图时，实现上述拓扑排序算法的函数TopSo~的时间复杂度是(6)。若有向图采用邻接矩阵表示(例如，图15—3所示有向图的邻接矩阵如图15—5所示)，且将函数TopSort中有关邻接表的操作修改为针对邻接矩阵的操作，那么对于有n个顶点、e条弧的有向无环图，实现上述拓扑排序算法的时间复杂度是(7)。
选项
答案(6)0(n+e)(7)O(n2)
解析 以邻接表为存储结构时，计算各项点入度的时间复杂度为O(e)，建立零入度顶点队列的时间复杂度为O(n)。在拓扑排序过程中，  (图中无环情况下)每个顶点进出队列各1次，入度减1的操作在while循环中共执行e次，所以总的时间复杂度为O(n+e)。以邻接矩阵为存储结构时，计算各顶点入度时需要遍历整个矩阵，因此时间复杂度为O(n2)，建立零入度顶点队列的时间复杂度为O(n)。在拓扑排序过程中，  (图中无环情况下)每个顶点进出队列各1次，实现入度减1操作时需遍历每个顶点的行向量1遍(时间复杂度为O(n))，所以总的时间复杂度为O(n2)。
转载请注明原文地址:https://www.kaotiyun.com/show/YZDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

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

软考中级

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