2. 计算机
  3. 阅读下列函数说明和C代码， [说明] 所谓货郎担问题，是指给定一个无向图，并已知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和最小。 应用贪婪法求解该问题，程序先计算由各点构成的所有边的长度(

阅读下列函数说明和C代码， [说明] 所谓货郎担问题，是指给定一个无向图，并已知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和最小。 应用贪婪法求解该问题，程序先计算由各点构成的所有边的长度(

admin2013-01-05  40
问题 阅读下列函数说明和C代码，
   [说明]
   所谓货郎担问题，是指给定一个无向图，并已知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和最小。
   应用贪婪法求解该问题，程序先计算由各点构成的所有边的长度(作为边的权值)，按长度大小对各边进行排序后，按贪婪准则从排序后的各边中选择组成回路的边，贪婪准则使得边的选择按各边长度从小到大选择。
   函数中使用的预定义符号如下：
   #define M 100
   typedef struct{/*x为两端点p1、p2之间的距离，p1、p2所组成边的长度*/
   float x；
   int p1，p2；
   }tdr；
   typedef struct{/*p1、p2为和端点相联系的两个端点，n为端点的度*/
   int n，p1，p2；
   }tr；
   typedef struct{/*给出两点坐标*/
   float x，y；
   }tpd；
   typedef int tl[M]；
   int n=10；
   [函数]
   float distance(tpd a，tpd b)；/*计算端点a、b之间的距离*/
   void sortArr(tdr a[M]，int m)；
   /*将已经计算好的距离关系表按距离大小从小到大排序形成排序表，m为边的条数*/
   int isCircuit(tr r[M]，int i，int j)；
   /*判断边(i，j)选入端点关系表r[M]后，是否形成回路，若形成回路返回0*/
   void selected(tr r[M]，int i，int j)；/*边(i，j)选入端点关系表r*/
   void course(tr r [M]，tl l[M])；/*从端点关系表r中得出回路轨迹表*/
   void exchange(tdr a[M]，int m，int b)；
   /*调整表排序表，b表示是否可调，即是否有长度相同的边存在*/
   void travling(tpd pd [M]，int n，float dist，tl locus[M])
   /*dist记录总路程*/
   {
   tdr dr[M]；/*距离关系表*/
   tr r[M]；/*端点关系表*/
   int i，j，k，h，m；/*h表示选入端点关系表中的边数*/
   int b；/*标识是否有长度相等的边*/
   k=0；
   /*计算距离关系表中各边的长度*/
   for(i=1；i＜n； i++){
   for(j=i+1；J＜=n；j++){
   k++;
   dr[k]．x=(1);
   dr[k]．pl=i;
   dr[k]．p2=j;
   }
   }
   m=k；
   sortArr(dr，m)；/*按距离大小从小到大排序形成排序表*/
   do{
   b=1;
   dist=0；
   k=h=0：
   do{
   k++；
   i=dr[k]．p1；
   j=dr[k]．p2；
   if((r(i]．n＜=1)&&(r[j]．n＜=1)){/*度数不能大于2*/
   if  (2)  {
   /*若边(i，j)加入r后形成回路，则不能加入*/
     (3);
   h++；
   dist+=dr[k]．x；
   }else if  (4)  {
   /*最后一边选入r成回路，则该边必须加入且得到解*/
   selected(r，i，j)；
   h++：
   dist+=dr[k]．x;
   }
   }
   }while((k !=n)  &&  (h !=n))；
   if(h==n){/*最后一边选入构成回路，完成输出结果*/
   course(r，locus)；
   }else(/*找不到解，调整dr，交换表中边长相同的边在表中的顺序，并将b置0*/
     (5);
   }
   }while(!b);
   }
(4)
选项
答案h==n-1
解析 由注释可见空(4)是最后一条边条件，变量h表示的是“选入端点关系表中的边数”，而n个节点回路应该包含n条边，这点也可从后面h==n输出解看出，故空(4)填h==n-1。
转载请注明原文地址:https://kaotiyun.com/show/rYDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

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

软考中级

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