2. 计算机
  3. 阅读下列函数说明和C代码，将应填入(n)处的字句写在对应栏内。 【说明】 函数int Toplogcal(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE网，图中顶点从1

阅读下列函数说明和C代码，将应填入(n)处的字句写在对应栏内。 【说明】 函数int Toplogcal(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE网，图中顶点从1

admin2009-05-15  77
问题 阅读下列函数说明和C代码，将应填入(n)处的字句写在对应栏内。
【说明】
   函数int Toplogcal(LinkedWDigraph G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下：
   typedef struct Gnode{                          /*邻接表的表节点类型*/
         int adjvex;                              /*邻接顶点编号*/
         int weieht;                              /*弧上的权值*/
         stract Gnode *nextarc;                   /*指示下一个弧的节点*/
   }Gnode;
   typedef struct Adjlist{                        /*邻接表的头节点类型*/
         char vdata;                              /*顶点的数据信息*/
         struct Gnode *Firstadj;                  /*指向邻接表的第一个表节点*/
   }Adjlist;
   typedef struct LinkedWDigraph{                 /*图的类型*/
        int n,e;                                  /*图中顶点个数和边数*/
        struct Adjlist *head;                     /*指向图中第一个顶点的邻接表的头节点*/
   }LinkedWDigraph;
   例如，某AOE网如图5-4所示，其邻接表存储结构如图5-5所示。
         
   int Toplogical(LinkedWDigraph G)
   {
          Gnode *p;
          int j,w,top=0;
          int *Stack,*ve,*indegree;
          ve=(int*)malloc((G.n+1)*sizeof(int));
          indegree=(int*)malloc((G.n+1)*sizeof(int));     /*存储网中各顶点的入度*/
          Stack=(int*)malloe((G.n+1)*sizeof(int));        /*存储入度为0的顶点的编号*/
          if(!ve||!indegree||!Stack)exit(0);
          for(j=1;j＜=G.n;j++){
                ve[j]=0;indegree[j]=0;
          }/*for*/
          for(j=1;j＜=G.n;j++){                            /*求网中各顶点的入度*/
               p=G.head[j].Firstadj;
               while(p){
                       (1);
                     p=p-＞nextarc;
               }/*while*/
          }/*for*/
          for(j=1;j＜=G.n;j++)                             /*求网中入度为0的顶点并保存其编号*/
                if(!indegree[j])Stack[++top]=j;
          while(top＞0){
                w=(2);
                printf("%c",G.head[w].vdata);
                p=G.head[w].Firstadj;
                while(p){
                       (3);
                      if(!indegree[p-＞adjvex])
                             Stack[++top]=p-＞adjvex;
                      if((4))
                             ve[p-＞adjvex]=ve[w]+p-＞weight;
                      p=p-＞nextarc;
                }/*while*/
          }/*while*/
          return  (5);
   }/*Toplogical*/
选项
答案(1) indegree[p-＞adjvex]++，及其等价形式 (2) Stack[top--]，及其等价形式 (3) indegree[p-＞adjvex]--，及其等价形式 (4) ve[w]+p-＞weight＞ve[p-＞adjvex]，及其等价形式 (5) ye[w)，及其等价形式
解析 本题考查AOE网络及其拓扑排序和关键路径，做题前需要先弄清楚图G的存储结构。
   根据注释，空(1)所在for循环用来统计AOE网中各顶点的入度。根据入度的定义及题中AOE网的存储结构，当p不为NULL时，应将p-＞adjvex对应的顶点的入度加1。又数组 indegree正是用来存储各顶点入度的，从紧接着的用来求入度为0的顶点的for循环可看出， indegree数组有效下标是从1到G.n，而顶点的编号正好也是从1开始，故空(1)应填 indegree[p-＞adjvex]++。
   各顶点入度统计结束后，收集入度为0的顶点并将其编号保存在栈Stack(数组模拟)中，栈顶指针为数组下表top。
   接下来根据各顶点入度进行拓扑排序输出。
   空(2)是给变量w赋值，紧接着将w对应的信息输出，根据拓扑排序算法，此处是选择一个入度为0的顶点输出。Stack栈存储的正是入度为0的顶点编号，故空(2)应填Stack[top--]。注意top指向的栈顶，因此不能写成Stack[--top]；另外，这里是出栈操作，不能写成Stack[top]。
   根据拓扑排序算法，接下来需要将变量w对应的顶点的所有出边删除，即将对应的顶点的入度减1。类似空(1)，空(3)应填indegree[p-＞adjvex]--。接着判断相应顶点的入度是否为0，为0时将其入栈。
   空(4)比较难确定，因程序中并未说明ve数组的用途，注意到函数需要返回关键路径的长度，而至此尚无任何相关语句。因此可以断言ve数组正是为了计算关键路径长度而设置的。关键路径是指从开始到结束点的最长路径，所以只要保证每到一个顶点vx，ve[vx]中存储的都是从开始顶点到vx的最长路径(即顶点vx的最早发生时间)即可。故空(4)应填“ve[w]+p-＞weight＞ve[p-＞adjvex]”。这样，空(5)很容易得出应填“ve[w]”。
转载请注明原文地址:https://www.kaotiyun.com/show/B5xZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

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