首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下面是求解该问题的伪代码,请填充其中空缺的(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
28
问题
下面是求解该问题的伪代码,请填充其中空缺的(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)作为设计依据。(20)
在以下网络应用中,要求带宽最高的应用是(65)。
当用户需求不清晰、需求经常发生变化、系统规模不太大时,最适宜采用的软件开发方法是__________。
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的数字表示活动的持续时间(天)。活动EH最多可以晚开始①天而不影响项目的进度。由于某种原因,现在需要同一个工作人员完成BC和BD,则完成该项目的最少时间为②天
根据输入输出等价类边界上的取值来设计用例的黑盒测试方法是______。
某软件项目的活动图如下图所示,其中顶点表示项目里程碑,连接顶点的边表示包含的活动,边上的数字表示活动的持续时间(天),则完成该项目的最少时间为________________天。活动FG的松弛时间为________________天。
系统交付后,修改偶尔会出现乱码的问题,该行为属于________________维护。
测试记录包括、(64)。①测试计划或包含测试用例的测试规格说明。②测试期间出现问题的评估与分析。③与测试用例相关的所有结果,包括在测试期间出现的所有失败。④测试中涉及的人员身份。
某汽车维修公司有部门、员工和顾客等实体,各实体对应的关系模式如下:部门(部门代码,部门名称,电话)员工(员工代码,姓名,部门代码)顾客(顾客号,姓名,年龄,性别)维修(顾客号,故障情况,维修日期,员工代码)假设每个部门允许有多部电话,则电话属性为
下面为C语言程序,边界值问题可以定位在(45)。 int data(3), int i, for(i=1, i<=3, i++)data(i)=100
随机试题
治疗心阴虚,心火旺的心烦失眠宜选治疗阴虚血热的吐血,衄血,便血,崩漏宜选
【2010年第83题】无黏结预应力钢筋混凝土梁具有许多优点,以下哪一种说法是不正确的?
下列各项中,计算建筑面积的有()。
CIIA考试分为标准(国际通用知识)考试和国家知识考试两部分。其中,国际通用知识考试的内容不会涉及()。
下列不属于抵债资产的保管方式的是()。
下列对于软件测试的描述中正确的是()。
下面关于常成员函数的说法中正确的是()。
Ithinkhe’sthemostcharming,most______manI’veeverknown.
Byusingacheckcard,aconsumerreceivescreditaswellasamonthlybillwhenabuyingisdone.Whenyourequestcash,them
A、Acollegedegree.B、Goodcreditrecord.C、Livinginthecollege.D、Anageofatleast18years.D选项中的Goodcreditrecord,Anage
最新回复
(
0
)