首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下面是求解该问题的伪代码,请填充其中空缺的(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
94
问题
下面是求解该问题的伪代码,请填充其中空缺的(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
软件设计师下午应用技术考试
软考中级
相关试题推荐
假设磁盘块与缓冲区大小相同,每个盘块读入缓冲区的时间为10μs,由缓冲区送至用户区的时间是5μs,系统对每个磁盘块数据的处理时间为2μs。若用户需要将大小为10个磁盘块的Docl文件逐块从磁盘读入缓冲区,并送至用户区进行处理,那么采用单缓冲区需要花费的时间
关于软件著作权产生的时间,下面表述正确的是(10)。
程序中常采用变量表示数据,变量具有名、地址、值、作用域、生存期等属性。关于变量的叙述,(19)是错误的。
某公司内部使用wb.xyz.com.cn作为访问某服务器的地址,其畔wb是______。
国标16260中,在描述外部(内部)效率度量时,给出了若干针对计算机系统时间消耗的定义,以下描述项中正确的有(31)。①响应时间是指从按下传送键到得到结果为止所需要的时间。②处理时间是指从接受一个消息到送出它的结果之间计算机的历时时间。③周转时间是指
对某商店业务处理系统采用数据流图(DFD)进行功能建模,其中“检查订货单”是其中的一个①。由于在进行订货单检查时,需要根据客户的欠款情况、订单金额等多个条件判断是否采取发出催款单、准备货物、发出发货单等行为,此时适合采用②进行描述。②处
对于下面的有向图,其邻接矩阵是一个①的矩阵。采用邻接链表存储时,顶点0的表结点个数为2,顶点3的表结点个数为0,顶点1的表结点个数为②个。②处应填入?
按照开发阶段划分,软件测试可以分为______。①单元测试②集成测试③系统测试④确认测试⑤用户测试⑥验收测试⑦第三方测试
某软件公司项目组的程序员在程序编写完成后均按公司规定撰写文档,并上交公司存档。此情形下,该软件文档著作权应由______享有。
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的数字表示活动的持续时间(天),则完成该项目的最少时间为________________天。活动FG的松弛时间为________________天。
随机试题
班杜拉提出的强化包括哪几种形式?
合同规定甲公司应当在8月30日向乙公司交付一批货物。8月中旬,甲公司把货物运送到乙公司。此时乙公司有权应当如何处理?()
者行孙以自己个人财产设立一家个人独资企业,从事广告用品的印刷,主要收入用于家庭共同开支。但后来由于经营不善,该企业经清算后解散,但仍有几个债务没有清偿。则:()
(2011年)圆管流的下临界雷诺数()。
阅读下列材料,按要求完成教学设计任务。材料一《普通高中化学课程标准(实验)》内容标准为:“通过实验了解氯、氮、硫、硅等非金属及其重要化合物的主要性质,认识其在生产中的应用和对生态环境的影响”。活动与探究建议:“实验氯气的漂白性”。材料二
化学与生活密切相关,下列说法正确的是()。
某疗养院同一个房间的四位病友,把他们的年龄(均为整数)两两相加得到6个不同的数,已知其中5个数为:99,113,125,130,144,四人中年龄最大者与年龄最小者岁数之和为()岁。
46.下面哪一项对人们座位的安排(从妹妹开始,经桌头再到另一边)是可以接受的?47.若爷爷坐在小明的对面,则奶奶必须与下面哪一个人相邻?
设z=f[xg(y),x-y],其中f二阶连续可偏导,g二阶可导,求.
Bumrateisthespeedatwhichastartupbusinessconsumesmoney.Myratewouldbe$50,000amonthwhenmynewmediacompanys
最新回复
(
0
)