中级软件设计师填空试卷（中级软件设计师）_2.docVIP

试卷第 PAGE 1 页共 NUMPAGES 1 页 中级软件设计师填空试卷（中级软件设计师） 姓名:_____________ 年级:____________ 学号:______________ 题型 选择题 填空题 解答题 判断题 计算题 附加题 总分 得分 评卷人 得分 1、[说明] 所谓货郎担问题，是指给定一个无向图，并已知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和最小。 应用贪婪法求解该问题，程序先计算由各点构成的所有边的长度(作为边的权值)，按长度大小对各边进行排序后，按贪婪准则从排序后的各边中选择组成回路的边，贪婪准则使得边的选择按各边长度从小到大选择。 函数中使用的预定义符号如下： #define M 100 typedef struct/为两端点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 t1[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], t1 1 [W]);/*从端点关系表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 = ______; dr[k].p1 = i; dr[k].p2 = j; m = k; sortArr (dr, m);/*按距离大小从小到大排序形成排序表*/ do b = i; dist = 0; k = h = 0; do k++; i = dr[k].p1; j = dr[k].p2; if((r[i].n ＜= 1) h++; dist += dr[k].x; else if(______) selected(r, i, j); /*最后一边选入r成回路，完成输出结果*/ h++; dist += dr[k].x; while((k != n) if((h == n)) /*最后一边选入构成回路, 完成输出结果*/ course(r, locus); else/*找不到解, 调整dr, 交换表中边长相同的边在表中的顺序, 并将b置0*/ ______; while(!b);