首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下面是求解该问题的伪代码,请填充其中空缺的(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
107
问题
下面是求解该问题的伪代码,请填充其中空缺的(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
软件设计师下午应用技术考试
软考中级
相关试题推荐
在数据库逻辑结构设计阶段,需要(20)阶段形成的(21)作为设计依据。(21)
在软件维护阶段,将专用报表功能改成通用报表功能,以适应将来可能的报表格式变化,则该维护类型为()维护。
编译器和解释器是两种基本的高级语言处理程序。编译器对高级语言源程序的处理过程可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等阶段,其中,___________并不是每个编译器都必需的。
《GB/T18905软件工程产品评价》中确定的通用评价过程包括四个方面,其中有关“规定评价”部分包含的内容有(67)。
在以下网络应用中,要求带宽最高的应用是(65)。
V模型是具有代表意义的测试模型,以下理解正确的是______。A.V模型认为测试阶段是与开发阶段并行的B.V模型是软件开发螺旋模型的变种,它反映了测试活动与分析和设计的关系C.V模型造成需求分析阶段隐藏的问题一直到后期的验收测试才被发现D.V模型是
某企业职工关系EMP(E_no,E_name,DEPT,E_addr,E_tel)中的属性分别表示职工号、姓名、部门、地址和电话;经费关系FUNDS(E_no,E_limit,E_used)中的属性分别表示职工号、总经费金额和已花费金额。若要查询部门为“开
以下关于软件测试原则的叙述中,正确的是______。①所有软件测试都应追溯到用户需求②尽早地和不断地进行软件测试③完全测试是不可能的④测试无法发现软件潜在的缺陷⑤需要充分注意测试中的群集现象
系统交付后,修改偶尔会出现乱码的问题,该行为属于________________维护。
在各种不同的软件需求中,()描述了产品必须要完成的任务,可以在用例模型中予以说明。
随机试题
肾病综合征的临床特征为______________、________________、_______________和_______________。
A.抗-HBeB.抗-HBsC.抗-HBcIgMD.抗-HBcIgGE.HBsAg慢性乙型肝炎的常见异常指标是()
小儿指纹分三关,从虎口到食指端依次为
下列有关桩承台构造方面的叙述不正确的是()。[2007年真题]
背景资料:淮江湖行洪区退水闸为大(1)工程,批复概算约3亿元,某招标代理机构组织了此次招标工作。在招标文件审查会上,专家甲、乙、丙、丁、戊分别提出了如下建议:甲:为了防止投标人哄抬报价,建议招标文件规定投标报价超过标底5%的为废标。乙:投标人
教育心理学的具体研究范畴是围绕学与教相互作用过程而展开的,由学习过程和教学过程这两个过程交织在一起、,
2013年3月12日.日本首相安倍晋三在日本国会众议院预算委员会上称“对于这一场大战的总结,并不是日本人自己做出的,应该说是战胜国一方做出的裁决”,对第二次世界大战结束后远东国际军事法庭对日本战犯审判(东京审判)的正确性提出质疑。言论一出立即引起国际舆论的
吴某(女)16岁,父母去世后无其他近亲,吴某的舅舅孙某(50岁,离异,有一个19岁的儿子)提出愿将吴某收养。下列表述正确的是()。
《楚辞》在中国诗史上占有重要的地位。它的出现,打破了《诗经》以后两三个世纪的沉寂而在诗坛上大放异彩。后人也因此将《诗经》与《楚辞》并称“风、骚”。
Fiftyvolunteerswerealphabeticallydividedintotwoequalgroups,GroupAtoparticipate【C1】______a7-weekexerciseprogram,a
最新回复
(
0
)