首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下面是求解该问题的伪代码,请填充其中空缺的(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
admin
2010-04-08
104
问题
下面是求解该问题的伪代码,请填充其中空缺的(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(n
3
)
解析
问题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(n
3
)。第9~12行,计算任意两点之间的最短路径之和,有两重循环,故时间复杂度为0(n
2
)。第15—18行,在所有点的最短路径之和中找到最小的最短路径之和,时间复杂度为O(n)。故算法总的时间复杂度为O(n
3
)。
转载请注明原文地址:https://kaotiyun.com/show/PSDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
将高级语言程序翻译为机器语言程序的过程中,常引入中间代码,其好处是()。
CMM模型将软件过程的成熟度分为5个等级。在(21)使用定量分析来不断地改进和管理软件过程。
高级程序设计语言中用于描述程序中的运算步骤、控制结构及数据传输的是(20)。
对于测试中所发现错误的管理是软件测试的重要环节,以下关于错误管理原则的叙述正确的是()。
下述说法错误的是(46)。
标准符合性测试中的标准分类包括______。①数据内容类标准②通信协议类标准③开发接口类标准④信息编码类标准
某系统中有一个中央数据存储,模块A负责接收新来的数据并修改中央数据存储中的数据,模块B负责访问中央数据存储中的数据,则这两个模块之间的耦合类型为________________。若将这两个模块及中央数据合并成一个模块,则该模块的内聚类型为_________
在一个完整的功能测试过程中,______不属于应该编写的测试文档。A.测试需求文档B.测试用例文档C.测试标准D.问题报告单
某汽车维修公司有部门、员工和顾客等实体,各实体对应的关系模式如下:部门(部门代码,部门名称,电话)员工(员工代码,姓名,部门代码)顾客(顾客号,姓名,年龄,性别)维修(顾客号,故障情况,维修日期,员工代码)假设每个部门允许有多部电话,则电话属性为
随机试题
Ingeneral,oursocietyisbecomingoneofgiantenterprisesdirectedbyabureaucraticmanagementinwhichmanbecomesasmall,
在判断甲状腺结节良恶性时,下列哪项错误()(2005年)
患儿8个月,夜间常哭闹、多汗、睡眠不安。查体见方颅、肋骨串珠。下列护理措施中错误的是
一切技术分析方法都是以价量关系为研究对象的。()
应用财务报表的主要目标有()。
导致市场失灵的主要原因有()。
中华人民共和国公民有言论、出版、集会、结社、游行、示威和罢工的自由。()
一条虫子沿长6分米,宽4分米,高5分米的长方体的棱爬行。如果它只能进不能退,并且同一条棱不能爬两次,那么它最多能爬()分米。
请在“答题”菜单中选择相应的命令。并按照题自要求完成下面的操作。注意:以下的文件必须保存在考生文件夹下。请根据提供的素材文件“ppt素材.docx”中的文字、图片设计制作演示文稿,并以文件名“ppt.pptx”存盘,具体要求如下:1.将素材文件中每个
Whatwillmanbelikeinthefuture—in5000oreven50000yearsfromnow?Wecanonlymakeaguess,ofcourse,butwecanbes
最新回复
(
0
)