中级软件设计师下午试题模拟62

VIP免费

2025-03-26 8 0 105.91KB 10 页 5.9玖币

侵权投诉

中级软件设计师下午试题模拟 62

试题一

1 、【说明】

 所谓货郎担问题，是指给定一个无向图，并已知各边的权，在这样的图中，要找一个闭合回路，

使回路经过图中的每一个点，而且回路各边的权之和最小。

 应用贪婪法求解该问题。程序先计算由各点构成的所有边的长度(作为边的权值)，按长度大小

对各边进行排序后，按贪婪准则从排序后的各边中选择边组成回路的边，贪婪准则使得边的选择按

各边长度从小到大选择。

 函数中使用的预定义符号如下：

   #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[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);

 }

试题二

2 、 [说明]

 下面的流程图(如图所示)用N - S 盒图形式描述了数组 A中的元素被划分的过程。其划分方

法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的

元素向高下标端移动。当划分结束时，基准数定位于 A[i]，并且数组中下标小于 i的元素的值均小

于基准数，下标大于 i的元素的值均大于基准数。设数组 A 的下界为 low，上界为 high，数组中

的元素互不相同。例如，对数组(4，2，8，3，6)，以 4为基准数的划分过程如下：

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

中级软件设计师下午试题模拟62试题一1、【说明】所谓货郎担问题，是指给定一个无向图，并已知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和最小。应用贪婪法求解该问题。程序先计算由各点构成的所有边的长度(作为边的权值)，按长度大小对各边进行排序后，按贪婪准则从排序后的各边中选择边组成回路的边，贪婪准则使得边的选择按各边长度从小到大选择。函数中使用的预定义符号如下： #defineM100 typedefstruct{/*x为两端点p1、p2之间的距离，p1、p2所组成边的长度*/ floatx; intp1,...

展开>> 收起<<

中级软件设计师下午试题模拟62.doc

共10页,预览2页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

中级软件设计师下午试题模拟62

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: