2. 计算机
  3. 阅读下列函数说明和c代码，将应填入(n)处的字句写在对应栏内。 【说明】 所谓货郎担问题，是指给定一个无向图，并已知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和最小。 应用贪婪法求解该问题。程

阅读下列函数说明和c代码，将应填入(n)处的字句写在对应栏内。 【说明】 所谓货郎担问题，是指给定一个无向图，并已知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和最小。 应用贪婪法求解该问题。程

admin2009-02-15  49
问题 阅读下列函数说明和c代码，将应填入(n)处的字句写在对应栏内。
    【说明】
   所谓货郎担问题，是指给定一个无向图，并已知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和最小。
   应用贪婪法求解该问题。程序先计算由各点构成的所有边的长度(作为边的权值)，按长度大小对各边进行排序后，按贪婪准则从排序后的各边中选择边组成回路的边，贪婪准则使得边的选择按各边长度从小到大选择。
   函数中使用的预定义符号如下：
       #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[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 1[M]);/*从端点关系表r中得出回路轨迹表*/
         void exchange(tdr a[M], int m, int b);
         /*调整表排序表，b表示是否可调，即是否有边长度相同的边存在*/
         void travling(tpd pd[M], int n, float dist, t1 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].p1=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.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);
   }
选项
答案(1) distance(pd[i],pd[j]) (2) !isCircuit(r,i,j) (3) selected(r,i,j) (4) h==n-1 (5) exchange(dr,m,b)
解析 本题主要是函数调用的问题。
   空(1)是计算各边的长度，根据函数的声明及说明，应填distance(pd，pd[j])。
   由注释可见空(2)是判断边(i，j)加入r后是否形成回路，若形成了回路，不加入。由语句“dist+=dr[k].x;”可知此处是将边加入，故此处应该是不形成回路条件。参照isCircuit函数声明及说明可知，若形成回路返回0，故空(2)填“!isCircuit(r,i,j)”。
   空(3)是将边(i,j)加入到r中，参照selected函数声明及说明，可得空(3)填selected(r, i,j)。
   由注释可见空(4)是最后一条边条件，变量h表示的是“选入端点关系表中的边数”，而 n各节点回路应该包含n条边，这点也可从后面h==n输出解看出，故空(4)填h==n-1。
   空(5)是进行调整，调用exchange函数，正确调用形式为exchange(dr,m,b)。
转载请注明原文地址:https://www.kaotiyun.com/show/puDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

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

软考中级

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