RuanKao.net 软考网(Beta 2.2)
首页 - 中级资格 -
软件设计师 - 2009年上半年软件设计师下午试题答案
2009年上半年软件设计师下午试题答案
【试题】阅读下列说明,回答问题1 和问题2,将解答填入答题纸的对应栏内。现需在某城市中选择一个社区建一个大型超市,使该城市的其它社区到该超市的距离总和最小。用图模型表示该城市的地图,其中顶点表示社区,边表示社区间的路线,边上的权重表示该路线的长度。现设计一个算法来找到该大型超市的最佳位置:即在给定图中选择一个顶点,使该顶点到其它各顶点的最短路径之和最小。算法首先需要求出每个顶点到其它任一顶点的最短路径,即需要计算任意两个顶点之间的最短路径;然后对每个顶点,计算其它各顶点到该顶点的最短路径之和;最后,选择最短路径之和最小的顶点作为建大型超市的最佳位置。【问题 1】(12 分)本题采用Floyd-Warshall 算法求解任意两个顶点之间的最短路径。 已知图G 的顶点集合为V={1,2,...,n } ,W= {Wij}n*n 为权重矩阵。设 d (k)ij=为从顶点i 到顶点j 的一条最短路径的权重。当k = 0 时,不存在中间顶点,因此d(0)ij=wij当k >0 时,该最短路径上所有的中间顶点均属于集合{1,2, ..., k}若中间顶点包括顶点 k ,则d(k)ij=d(k-1)ik+d(k-1)kj 若中间顶点不包括顶点k ,则d(k-1)ij=d(k-1)ij于是得到如下递归式。因为对于任意路径,所有的中间顶点都在集合{1,2, ..., n} 内,因此矩阵D(n) ={d(n)ij}n*n 给出了任意两个顶点之间的最短路径,即对所有i, j ∈V,d(n)ij 表示顶点i 到顶点 j 的最短路径。下面是求解该问题的伪代码,请填充其中空缺的 (1)至(6)处。 伪代码中的主要变量说明如下:W:权重矩阵n: 图的顶点个数www.RuanKao.net 专业实用 考生之家SP:最短路径权重之和数组,SP[i]表示顶点i 到其它各顶点的最短路径权重之和,i 从1 到nmin_SP:最小的最短路径权重之和min_v:具有最小的最短路径权重之和的顶点i:循环控制变量j:循环控制变量k:循环控制变量LOCATE -SHOPPINGMALL(W, n)1 D(0)=W
7 / 132 for (1)3 for i = 1 to n4 for j = 1 to n5 if d(k-1)ij≤≤d(k-1)ik+d(k-1)kj6 (2)7 else8 (3)9 for i = 1 to n10 SP[i] = 011 for j = 1 to n12 (4)13 min_SP = SP[1]14 (5)15 for i = 2 to n16 if min_SP > SP[i]17 min_SP = SP[i]18 min_v = i19 return (6)【问题2】(3 分)【问题】中伪代码的时间复杂度为(7)(用Ο 符号表示)。【答案】(1) k=1 to n(2)Dij(k)=dij(k‐1)(3)dij(k)=diK(k‐1)+dkj(k‐1)(4)sp[i]=sp[i]+dij(j)(5)min_v=1(6)min_SP(7) O(n3) 【以下正在生成完整试卷,需安装
PDF阅读工具】
相关链接
联系我们:

(站务、友情链接、投稿、反馈、纠错)
本站资源不断在完善更新。如果本站对你有用,请在你的博客、MSN、QQ上推荐给更多朋友,谢谢!
本站不接受广告。欢迎与本站交换友情链接,请做好链接后发邮件给我们。