资源描述：
《中级软件设计师下午试题模拟62》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、中级软件设计师下午试题模拟62试题一1、 【说明】 所谓货郎担问题，是指给定一个无向图，并已知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和最小。 应用贪婪法求解该问题。程序先计算由各点构成的所有边的长度(作为边的权值)，按长度大小对各边进行排序后，按贪婪准则从排序后的各边中选择边组成回路的边，贪婪准则使得边的选择按各边长度从小到大选择。 函数中使用的预定义符号如下： #defineM100 typedefstruct{/*x为两端点p1、p2之间的距离，p1、p
2、2所组成边的长度*/ floatx; intp1,p2; }tdr; typedefstruct{/*p1、p2为和端点相联系的两个端点，n为端点的度*/ intn,P1,p2; }tr; typedefstruct{/*给出两点坐标*/ floatx,y; }tpd; typedefinttl[M]; intn=10; 【函数】 floatdistance(tpda,tpdb);/*计算端点a、b之间的距离*/ voidsor
3、tArr(tdra[M],intm); /*将已经计算好的距离关系表按距离大小从小到大排序形成排序表，m为边的条数*/ intisCircuit(tr[M],inti,intj); /*判断边(i,j)选入端点关系表r[M]后，是否形成回路，若形成回路返回0*/ voidselected(trr[M],inti,intj);/*边(i,j)选入端点关系表r*/ voidcourse(trr[M],tl1[M]);/*从端点关系表r中得出回路轨迹表*/ voidexchange(
4、tdra[M],intm,intb); /*调整表排序表，b表示是否可调，即是否有边长度相同的边存在*/ voidtravling(tpdpd[M],intn,floatdist,t1locus[M]) /*dist记录总路程*/ { tdrdr[M];/*距离关系表*/ trr[M];;/*端点关系表*/ inti,j,k,h,m;/*h表示选入端点关系表中的边数*/ intb;/*标识是否有长度相等的边*/ k=0;
5、 /*计算距离关系表中各边的长度*/ 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
6、; 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; }elseif( (4) ){
7、 /*最后一边选入r成回路，则该边必须加入且得到解*/ selected(r,i,j); h++; dist+=dr[k].x; } } }while((k!=n)&&(h!=n)); if(h==n){/*最后一边选入构成回路，完成输出结果*/ course(r,locus); }else{/*找不到解，调整dr，交换表中边长相同的边在表中的顺序，并将
8、b置0*/ (5) ; } }while(!b); }试题二2、 [说明] 下面的流程图(如图所示)用N-S盒图形式描述了数组A中的元素被划分的过程。其划分方法是：以数组中的第一个元素作为基准数，将小于基准数的元素向低下标端移动，而大于基准数的元素向
