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

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

admin2005-03-20  105
问题 阅读下列函数说明和c代码，将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
   函数int Toplogical(Linded WDipaph  G)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE-网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下：
    typedefstruct Gnode{               /* 邻接表的表结点类型*/
         iht adjvex;                  /* 邻接顶点编号*/
         iht weight;                 /* 弧上的权值*/
         street Gnode *nextarc;          /* 指示下一个弧的结点*/
   }Gnode;
   typedef struct Adjlist{           /* 邻接表的头结点类型*/
         char vdata;                  /*顶点的数据信息*/
         struct Gnode *Firstadj;        /* 指向邻接表的第一个表结点*/
   }Adjlist;
   typedef street LinkedWDigraph{      /* 图的类型*/
         int n, e;                  /* 图中顶点个数和边数*/
         struct Adjlist *head;         /*指向图中第一个顶点的邻接表的头结点 */
   } LinkedWDigraph;
   例如，某AOE-网如图5-1所示，其邻接表存储结构如图5-2所示。

【函数】
     iht Toplogical(LinkedWDigraph G)
     { Gnode *p;
       intj, w, top = 0;
       iht *Stack, *ye, *indegree;
       ye = (int *)malloe((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("%e  ", G.head[w].vdata);
          p = G.head[w].Firstadj;
          while (p) {
           (3);
      if ( !indegree [p→adjvex])
         Staek[++top] = p→adjvex;
    if( (4))
         ve[p→adjvex] = ve[w] + p→weight;
      p = p→nextarc;
     }/* while */
   }/* while */ return  (5); }/*Toplogieal*/
选项
答案(1)indegree【p→adjvex】++，及其等价形式 (2)Stack【top--】，及其等价形式 (3)indegree【p→adjvex】--，及其等价形式 (4)ve【w】+p→weight＞ve【p→adjvex】，及其等价形式 (5)ve【w】，及其等价形式
解析 本题考查的是数据结构中拓扑排序和求关键路径问题的算法。
   在AOE网中，入度为0的顶点为源点，出度为0的顶点为汇点。从源点到汇点的路径中，长度最长的路径称为关键路径。表示事件的顶点存在最早、最晚发生时间。若以顶点v1表示源点、顶点vn表示汇点，则汇点的最早发生时间和最晚发生时间是一致的，并且等于关键路径的长度。
   设顶点vj的最早发生时间用ve(j)表示，则ve(j)是指从源点v1到vj的最长路径长度(时间)。这个时间决定了所有从vj发出的弧所表示的活动能够开工的最早时间。
   ve(j)计算方法为
   
其中，T是所有到达顶点j的弧的集合；dut(＜i，j＞)是弧＜i，j＞上的权值；n是网中的顶点数(即汇点的序号)，如下图所示。　　
     
   显然，上式是一个从源点开始的递推公式。ve(j)的计算必须在 vj的所有前驱顶点的最早发生时间全部求出后才能进行。这样必须对 AOE网进行拓扑排序，然后按拓扑有序序列逐个求出各项点事件的最早发生时间。
   拓扑排序是将有向无环图中所有顶点排成一个线性序列的过程，并且该序列满足：若在有向图中从顶点vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。
   题目中给出的是AOE(Activity On Edge network)网，是一种赋权的有向无环图。
   对AOE网进行拓扑排序的方法如下：
   ①在AOE网中选择一个入度为0(没有前驱)的顶点且输出它。
   ②从网中删除该顶点及其与该顶点有关的所有边。
   ③重复上述两步，直至网中不存在入度为0的顶点为止。
   在拓扑排序过程中，有可能同时存在多个入度为0的顶点，函数中用顺序栈Stack[]暂存入度为0且没有进入拓扑序列的顶点。
   进行拓扑排序之前，应先求出网中每个顶点的入度并存入数组indegree[]中，从而，将“从网中删除该顶点及其与该顶点有关的所有边”的操作转换为“相关顶点的入度减一”，一旦发现某个顶点的入度变为0，就将其编号压入堆栈。从而将选择入度为0的顶点转化为从Stack中弹出栈顶元素所代表的顶点。
   题目中顶点从1开始编号，顶点vi的编号为i，以下代码用于求网中各个顶点的入度。
   for(j=1；j＜G.n;j++){    /*求网中各顶点的入度*/
   p=G.head【j】.Firstadj；
   while(p){
     (1)  ；    p=p→nextarc；
   }/*while*/
   }/*for*/
   在有向图中，若以v2为尾的弧有＜v2，v4>且权值为30、＜v2，v6．＞且权值为50，则其的邻接表表示形式如下图所示。　　　
   
   因此，扫描顶点v2的邻接表可以将邻接于v2的所有顶点的入度加10所以，空(1)处应填入“indegree【p→mdjvex】++”或其等价形式。
   以下代码实现拓扑排序并求解各个顶点时事件的最早发生时间。
   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*/
    由于入度为0的顶点由栈中弹出，而且根据w在后续代码中所起的作用，可知空(2)处应填入“Stack【top--】”。然后将邻接到顶点w的各个顶点(p→adjvex)的入度减一，所以，空(3)应填入“indegree【p→adjvex】--”或其等价形式。同时，对于顶点p→adjvex而言，当删除其所有引入边之后，从源点出发到达它的最长路径长度也就计算出来了，所以每删除一条到达顶点p→adjvex的引入边，都要查看一下最长路径长度是否需要更新。因此，空(4)填入“ve【w】+p→weight＞ve【p→adjvex】”或其等价形式。
   最后，汇点的最早发生时间即为该AOE网的关键路径长度。由于AOE网中汇点未必是编号最大的顶点，因此，当它必然是从栈中弹出的最后一个顶点，因此空(5)处填入“ve【w】”。
转载请注明原文地址:https://kaotiyun.com/show/cyDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

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

软考中级

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