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

试卷第 PAGE 1 页共 NUMPAGES 1 页 中级软件设计师填空试卷（中级软件设计师） 姓名:_____________ 年级:____________ 学号:______________ 题型 选择题 填空题 解答题 判断题 计算题 附加题 总分 得分 评卷人 得分 1、[说明] 若要在N个城市之间建立通信网络，只需要N-1条线路即可。如何以最低的经济代价建设这个网络，是一个网的最小生成树的问题。现要在8个城市间建立通信网络，其间拓扑结构如图所示，边表示城市间通信线路，边上标示的是建立该线路的代价。  无向图用邻接矩阵存储，元素的值为对应的权值。考虑到邻接矩阵是对称的且对角线上元素均为0，故压缩存储，只存储上三角元素(不包括对角线)。 现用Prim算法生成网络的最小生成树。由网络G=(V, E)构造最小生成树T=(U, TE)的Prim算法的基本思想是：首先从集合V中任取一顶点放入集合U中，然后把所有一个顶点在集合U里、另一个顶点在集合V-U里的边中，找出权值最小的边(u, v)，将边加入TE，并将顶点v加入集合U，重复上述操作直U=V为止。 函数中使用的预定义符号如下： #define MAX 32768 /*无穷大权，表示顶点间不连通*/ #define MAXVEX 30 /*图中顶点数目的最大值*/ typedef struct int StartVex, StopVex; /*边的起点和终点*/ float weight; /*边的权*/ Edge; typedef struct char vexs [MAXVEX]; /*顶点信息*/ float arcs [MAXVEX* (MAXVEX-1) /2]; /*邻接矩阵信息，压缩存储*/ int n; /*图的顶点个数*/ Graph; [函数] void PrimMST(Graph *pGraph, Edge mst []) int i, j, k, min, vx, vy; float weight, minWeight; Edge edge; for(i = 0;i ＜ pGraph-＞n-1; i++) mst[i].StartVex = 0; mst[i].StopVex = i+1; mst[i].weight = pGraph-＞arcs[i]; for(i = 0; i ＜______; i++) /*共n-1条边*/ minWeight = (float)MAX; min = i; /*从所有边(vx, vy)中选出最短的边*/ for(j = i; j ＜ pGraph-＞n-1; j++) if(mst[j].weight ＜ minWeight) minWeight =______; min = j; /*mst[min]最短的边(vx, vy), 将mst[min]加入最小生成树*/ edge = mst[min]; mst[min] = mst[i]; met[i] = edge; vx = ______; /*vx为刚加入最小生成树的顶点下标*/ /*调整mst[i+1]到mst[n-1]*/ for(j = i+1; j ＜ pGraph-＞n-1; j++) vy = mst[j].StopVex; if ______ /*计算(vx, vy)对应的边在压缩矩阵中的下标*/ k = pGraph-＞n*vy-vy*(vy+1)/2+vx-vy-1; else k = pGraph-＞n*vx-vx* (vx+1)/2+vy-vx-1; weight = ______; if(weight ＜ mst[j].weight) mst[j].weight = weight; mst[j].StartVex = vx;