现需在某城市中选择一个社区建一个大型超市，使该城市的其它社区-名校题库网

题目详情

全站导航

首页试卷试题资讯

试卷导航

建筑工程职业资格公务员财会类医卫类外语类计算机类学历类

试题导航

建筑工程职业资格公务员财会类医卫类外语类计算机类学历类

现需在某城市中选择一个社区建一个大型超市，使该城市的其它社区到该超市的距离总和最小。用图模型表示该城市的地图，其中顶点表示社区，边表示社区间的路线，边上的权重表示该路线的长度。现设计一个算法来找到该大型超市的最佳位置：即在给定图中选择一个顶点，使该顶点到其它各顶点的最短路径之和最小。算法首先需要求出每个顶点到其它任一顶点的最短路径，即需要计算任意两个顶点之间的最短路径；然后对每个顶点，计算其它各顶点到该顶点的最短路径之和；最后，选择最短路径之和最小的顶点作为建大型超市的最佳位置。

【问题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)ij=d(k-1)ij。于是得到如下递归式

中级软件设计师,历年真题,2009年上半年（下午）《软件设计师》真题因为对于任意路径，所有的中间顶点都在集合{1，2，...，n｝内，因此矩阵D(n)=｛d(n)ij｝n*n给出了任意两个顶点之间的最短路径，即对所有i，j∈V，d(n)ij表示顶点i到顶点j的最短路径。

下面是求解该问题的伪代码，请填充其中空缺的(1)至(6)处。伪代码中的主要变量说明如下：

W：权重矩阵

n：图的顶点个数

SP：最短路径权重之和数组，SP[i]表示顶点i到其它各顶点的最短路径权重之和，i从1到n

min_SP：最小的最短路径权重之和

min_v：具有最小的最短路径权重之和的顶点

i：循环控制变量

j：循环控制变量

k：循环控制变量

中级软件设计师,历年真题,2009年上半年（下午）《软件设计师》真题

【问题2】（3分）

【问题1】中伪代码的时间复杂度为（7）（用Ο符号表示）。

正确答案及解析

正确答案

解析

【问题1】

（1）k=1 to n

（2）中级软件设计师,历年真题,2009年上半年（下午）《软件设计师》真题

（3）中级软件设计师,历年真题,2009年上半年（下午）《软件设计师》真题

（4）中级软件设计师,历年真题,2009年上半年（下午）《软件设计师》真题

（5）min_v=1

（6）min_v

【问题2】

（7）O(n3)

本题考查的是算法的设计和分析技术。

【问题1】

本问题考查算法流程。第（1）空表示主循环，k是循环控制变量，故第（1）空填k=1?to?n。第（2）和（3）空根据题意和递归式，可分别得到答案为中级软件设计师,历年真题,2009年上半年（下午）《软件设计师》真题和。计算了任意两个顶点之间的最短路径之后，对每个顶点，开始统计其到所有其他顶点的最短路径之和，因此第（4）空填。第13和第14行初始化，假设最小的到所有其他顶点的最短路径之和为第一个顶点的最小路径之和，大型超市的最佳位置为第一个顶点，故第（5）空填min_v=1。最后要求返回大型超市的最佳位置，即到所有其他项点的最短路径之和最小的顶点，故第（6）空填min_v。

【问题2】

本问题考查【问题1】中的伪代码第2~8行，计算任意两点之间的最短路径，有三重循环，故时间复杂度为O（n3）。第9~12行，计算每个点到任意其他点的最短路径之和，有两重循环，故时间复杂度为O（n2）。第15~18行，在所有点的最短路径之和中找到最小的最短路径之和，时间复杂度为O（n）。故算法总的时间复杂度为O（n3）。

包含此试题的试卷

2009年上半年（下午）《软件设计师》真题

你可能感兴趣的试题

问答题

阅读以下说明，回答问题1至问题4，【说明】某公司在Windows Server 2008上为公司用户提供Web和Ftp服务。公司域名为gkys.com。WEB服务器主机名为www。内部服务器使用公司内部自己安装的ＤＮＳ服务器解析。【问题1】为了满足公司网络提供WEB、FTP和DNS服务的要求，管理员安装服务器角色时，需要从下图所示的界面中选中（1）、（2）进行安装，没有FTP服务器选项的原因是（3）。