2. 计算机
  3. 阅读下列函数说明和C代码，将应填入(n)处的字句写上。 [说明] 若要在N个城市之间建立通信网络，只需要N-1条线路即可。如何以最低的经济代价建设这个网络，是一个网的最小生成树的问题。现要在8个城市间建立通信网络，其问拓扑结构如图5-1所示

阅读下列函数说明和C代码，将应填入(n)处的字句写上。 [说明] 若要在N个城市之间建立通信网络，只需要N-1条线路即可。如何以最低的经济代价建设这个网络，是一个网的最小生成树的问题。现要在8个城市间建立通信网络，其问拓扑结构如图5-1所示

admin2010-12-17  67
问题 阅读下列函数说明和C代码，将应填入(n)处的字句写上。
   [说明]
   若要在N个城市之间建立通信网络，只需要N-1条线路即可。如何以最低的经济代价建设这个网络，是一个网的最小生成树的问题。现要在8个城市间建立通信网络，其问拓扑结构如图5-1所示，边表示城市间通信线路，边上标示的是建立该线路的代价。
   [图5-1]
   
   无向图用邻接矩阵存储，元素的值为对应的权值。考虑到邻接矩阵是对称的且对角线上元素均为0，故压缩存储，只存储上三角元素(不包括对角线)。
   现用Prim算法生成网络的最小生成树。由网络G=(V，E)构造最小生成树T=(U，TE)的Prim算法的基本思想是：首先从集合V中任取一顶点放入集合U中，然后把所有一个顶点在集合U里、另一个顶点在集合V-U里的边中，找出权值最小的边(u，v)，将边加入TE，并将顶点v加入集合U，重复上述操作直到U=V为止。
   函数中使用的预定义符号如下：
   #define MAX 32768 /*无穷大权，表示顶点间不连通*/
   #define MAXVEX 30 /*图中顶点数目的最大值*/
   typedef struct{
       int startVex，stopVex;    /*边的起点和终点*/
       float weight;    /*边的权*/
   }Edge;
   typedef struct{
       char vexs[MAXVEX];    /*顶点信息*/
       float arcs[MAXVEX*(MAXVEX-1)/2];    /*邻接矩阵信息，压缩存储*/
       int n;    /*图的顶点个数*/
   }Graph;
   [函数]
   void PrimMST(Graph*pGraph, Edge mst[])
       {
           int i,j,k,min,vx,vy;
           float weight，minWeight;
           Edge edge;
           for(i=0; i＜pGraph-＞n-1；i++){
               mst.StartVex=0;
               mst.StopVex=i+1;
               mst.weight=pGraph-＞arcs;
           }
           for(i=0；i＜(1)；i++){/*共n-1条边*/
               minWeight=(float)MAX;
               min=i;
               /*从所有边(vx，vy)中选出最短的边*/
               for(j=i; j＜pGraph-＞n-1; j++){
                   if(mst[j].weight＜minWeight){
                       minWeight=(2);
                       min=j；
                   }
               }
               /*mst[minl是最短的边(vx，vy)，将mst[min]加入最小生成树*/
               edge=mst[min]；
               mst[min]=mst;
               mst=edge;
               vx=(3);/*vx为刚加入最小生成树的顶点下标*/
               /*调整mst[i+1]到mst[n-1]*/
               for(j=i+1；j＜pGraph-＞n-1；j++){
                   vy=mst[j].StopVex;
                   if( (4) ){/*计算(vx，vy)对应的边在压缩矩阵中的下标*/
                       k=pGraph-＞n*vy-vy*(vy+1)/2+vx-vy-1；
                   }else{
                       k=pGraph-＞n*vx-vx*(vx+1)/2+vy-vx-1;
                   }
                   weight(5)；
                   if(weight＜mst[j].weight){
                       mst[j].weight=weight;
                       mst[j].StartVex=vx;
                   }
               }
           }
       }
(5)
选项
答案pGraph-＞arcs[k]
解析 由注释“n-1条边”可得，(1)处应为pGraph-＞n-1。
   空(2)有关程序段是选出权值最小的边，minWeight表示的是最小权值，因此空(2)应填mst[j].weight。
   “vx为刚加入最小生成树的顶点下标”，因此空(3)应填mst.StopVex。
   邻接矩阵是压缩存储的，只存储上三角阵，因此下标需要进行转换。比较if及else块，可发现两算式区别在于vx、vy互换，由邻接矩阵的对称性可得空(4)处应填vy＜vx。
   空(5)相关程序段是进行调整，应填pGraph-＞arcs[k]。
转载请注明原文地址:https://kaotiyun.com/show/8vDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

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

软考中级

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