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

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

admin2011-01-29  76
问题 阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。
    【说明】
    对有向图进行拓扑排序的方法是：
    (1)初始时拓扑序列为空；
    (2)任意选择一个入度为0的顶点，将其放入拓扑序列中，同时从图中删除该顶点以及从该顶点出发的弧；
    (3)重复(2)，直到不存在入度为0的顶点为止(若所有顶点都进入拓扑序列则完成拓扑排序，否则由于有向图中存在回路无法完成拓扑排序)。
    函数int*TopSort(LinkedDigraph G)的功能是对有向图G中的顶点进行拓扑排序，返回拓扑序列中的顶点编号序列，若不能完成拓扑排序，则返回空指针。其中，图G中的顶点从1开始依次编号，顶点序列为vl，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如图4-1所示，其邻接表如图4-2所示。

    函数TopSort中用到了队列结构(Queue的定义省略)，实现队列基本操作的函数原型如下表所示：

【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)*sizeof(int))；／*存储拓扑序列中的顶点编号*／
    inDegree=(int*)malloc((G．n+1)*sizeof(int))；／*存储图G中各顶点的入度*／
    if(!inDegree｜｜!topOrder)  return NULL；
    (1)；                           ／*构造一个空队列*／
    for(j=1；j<=Gn；j++){            ／*初始化*／
       topOrder[j]=0；inDegree[j]=0；
    }
    for(j=1；j<=Gn；j++)            ／*求图G中各顶点的入度*／
    for(p=G．Vhead[j]．firstarc；p；p=p->nextarc)
       inDegree[P->adjvex]+=1；
    for(j=i；j<=G．n；J++)          ／*将图G中入度为0的顶点保存在队列中*／
    if(0==inDegree[j])   EnQueue(&Q，j)；
    while(! IsEmpty(Q)){
    (2);                           ／*队头顶点出队列并用w保存该顶点的编号*／
       topOrder[k++]=w；          ／*将顶点W的所有邻接顶点的入度减l(模拟删除顶点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->adjvexj (5)k!=G．N
解析 根据空(1)的后面注释是构造一个空队列，程序的开始已经定义了一个队列Q，那么此处只需初始化这个队列即可，所以空(1)应填InitQueue(&Q)。
    根据空(2)后面的解释，如果队列不空，那么就将队列的元素依次出队列，所以空(2)应为DeQueue(＆Q，＆w)。
    空(3)、(4)上下端的功能是将顶点w的所有邻接顶点的入度减l，数组inDegree中存放各个顶点的入度，所以空(3)应为inDegree[p->adjvex]，并判断与顶点w相邻的顶点有没有入度为零的顶点，如果有，就把这个顶点入队列，所以空(4)也填inDegree[p->adjvex]。
    最后，最外层循环结束，如果拓扑序列中元素的个数k不等于定点数n，那么就说明有向图中存在环，返回NULL上，所以空(5)填k!=G．n。
转载请注明原文地址:https://www.kaotiyun.com/show/pqDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

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

软考中级

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