2. 计算机
  3. 下面是求解该问题的伪代码，请填充其中空缺的(1)至(6)处。伪代码中的主要变量说明如下： W：权重矩阵 n：图的顶点个数 sP：最短路径权重之和数组，SP[i]表示顶点i到其他各顶点的最短路径权重之和，i从1到n rain_SP：最小的最短路径权重之和 m

下面是求解该问题的伪代码，请填充其中空缺的(1)至(6)处。伪代码中的主要变量说明如下： W：权重矩阵 n：图的顶点个数 sP：最短路径权重之和数组，SP[i]表示顶点i到其他各顶点的最短路径权重之和，i从1到n rain_SP：最小的最短路径权重之和 m

admin2010-04-08  101
问题
下面是求解该问题的伪代码，请填充其中空缺的(1)至(6)处。伪代码中的主要变量说明如下：
W：权重矩阵
n：图的顶点个数
sP：最短路径权重之和数组，SP表示顶点i到其他各顶点的最短路径权重之和，i从1到n
rain_SP：最小的最短路径权重之和
min_v：具有最小的最短路径权重之和的顶点
i：循环控制变量
j：循环控制变量
k：循环控制变量
LOCATE-SHOPPINGMALL(W，n)
1  D(0)=W
2 for(1)
3    for i=1 t0 n
4    for j=1 t0 n
5   
6   (2)
7    else
8   (3)
9  for i=1 to n
10    sP  =O
11    for j=1 to n
12   (4)
13  min  sP=sP[1]
14   (5)
15  for i=2 t0 n
16    if min  sP>sP
17    min  sP=sP
18    min V=i
19 return (6)
[问题1]中伪代码的时间复杂度为 (7)   (用0符号表示)。
选项
答案(7)O(n3)
解析 问题1：本问题考查算法流程。第(1)空表示主循环，k是循环控制变量，故第(1)空填k=1to n。第(2)和(3)空根据题意和递归式，可分别得到答案为
[*]
和计算了任意两个顶点之问的最短路径之后，对每个顶点，开始统计其到所有其他顶点的最短路径之和，因此第(4)空填SP=SP+dy(n)。第13和第14行初始化，假设最小的到所有其他顶点的最短路径之和为第一个顶点的最小路径之和，大型超市的最佳位置为第一个顶点，故第(5)空填rain_v=l。最后要求返回大型超市的最佳位置，即到所有其他顶点的最短路径之和最小的顶点。
问题2：本问题考查[问题1]中的伪代码2—8行，计算任意两点之间的最短路径，有三重循环，故时间复杂度0(n3)。第9～12行，计算任意两点之间的最短路径之和，有两重循环，故时间复杂度为0(n2)。第15—18行，在所有点的最短路径之和中找到最小的最短路径之和，时间复杂度为O(n)。故算法总的时间复杂度为O(n3)。
转载请注明原文地址:https://kaotiyun.com/show/PSDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)