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

admin2010-04-08 86

问题

下面是求解该问题的伪代码，请填充其中空缺的(1)至(6)处。伪代码中的主要变量说明如下：
W：权重矩阵
n：图的顶点个数
sP：最短路径权重之和数组，SP表示顶点i到其他各顶点的最短路径权重之和，i从1到n
rain_SP：最小的最短路径权重之和
min_v：具有最小的最短路径权重之和的顶点
i：循环控制变量
j：循环控制变量
k：循环控制变量
LOCATE-SHOPPINGMALL(W，n)
1  D⁽⁰⁾=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(n³)

解析问题1：本问题考查算法流程。第(1)空表示主循环，k是循环控制变量，故第(1)空填k=1to n。第(2)和(3)空根据题意和递归式，可分别得到答案为
[*]
和计算了任意两个顶点之问的最短路径之后，对每个顶点，开始统计其到所有其他顶点的最短路径之和，因此第(4)空填SP=SP+dy⁽ⁿ⁾。第13和第14行初始化，假设最小的到所有其他顶点的最短路径之和为第一个顶点的最小路径之和，大型超市的最佳位置为第一个顶点，故第(5)空填rain_v=l。最后要求返回大型超市的最佳位置，即到所有其他顶点的最短路径之和最小的顶点。
问题2：本问题考查[问题1]中的伪代码2—8行，计算任意两点之间的最短路径，有三重循环，故时间复杂度0(n³)。第9～12行，计算任意两点之间的最短路径之和，有两重循环，故时间复杂度为0(n²)。第15—18行，在所有点的最短路径之和中找到最小的最短路径之和，时间复杂度为O(n)。故算法总的时间复杂度为O(n³)。

转载请注明原文地址:https://kaotiyun.com/show/PSDZ777K

本试题收录于：软件设计师下午应用技术考试题库软考中级分类

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

相关试题推荐

随机试题

最新回复(0)

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

软考中级

根据ANSI/IEEE829标准，(62)属于《测试案例说明》中的内容。　　　　①输入说明　　②测试目的　　③环境要求　　④特殊要求

传统编译器进行词法分析、语法分析、代码生成等步骤的处理时，前一阶段处理的输出是后一阶段处理的输入，则采用的软件体系结构风格是①。该体系结构的优点不包括②。②处应填入？

给定包含n个正整数的数组A和正整数x，要判断数组A中是否存在两个元素之和等于x。先用插入排序算法对数组A进行排序，再用以下过程P来判断是否存在两个元素之和等于x。low=l；high=n；while(high＞low)ifA[low]+A[hig

在结构化分析方法中，用于行为建模的模型是①，其要素包括②。①处应填入？

假设关系R1和R2如下图所示：若进行R1R2运算，则结果集分别为(1)元关系，共有(2)个元组。(1)

一个程序的控制流图中有8个节点、12条边。在测试用例数最少的情况下，确保程序中每个可执行语句至少执行一次所需测试用例数的上限是________________。

下面为C语言程序，边界值问题可以定位在(45)。　　　　int　data(3),　　　　int　i,　　　　for(i=1,　i＜=3,　i++)data(i)=100

进行根尖诱导时的药物首选

有两方案现金流量及产量如表a所示，要求的收益率为13%。[问题]试用最低价格法对两方案进行比较。

在同一工程中计算疏浚与吹填工程土方量时，竣工后应采用与()相同的计算方法。

出渣是隧道施工的基本作业之一，出渣作业能力的强弱决定了在整个作业循环中的()。

出票人签发空头支票，银行应予以退票，并按票面金额处以5%但不低于1000元的罚款。()

下列金融服务项目下，金融机构发挥了经纪和交易功能的是()。

针对某一方面的心理发展通过在同一时段内对不同年龄的儿童进行比较，迅速找到差异所在的方法，称为()。

从所给的四个选项中，选择最合适的一个填入问号处，使之呈现一定的规律性：

某汽车销售中心以每辆18万元售出两辆小汽车，与成本相比较，其中一辆获利20％，另一辆则亏损10％，则该中心该笔交易的盈亏额是(　　)。

下列关于生产力的含义和结构阐述正确的有．