首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下面是求解该问题的伪代码,请填充其中空缺的(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
90
问题
下面是求解该问题的伪代码,请填充其中空缺的(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
软件设计师下午应用技术考试
软考中级
相关试题推荐
假设某公司营销系统有营销点关系S(营销点,负责人姓名,联系方式)、商品关系P(商品名,条形码,型号,产地,数量,价格),其中,营销点唯一标识S中的每一个元组。每个营销点可以销售多种商品,每一种商品可以由不同的营销点销售。关系S和P的主键分别为(15),S
在统一建模语言(UML)中,描述系统与外部系统及用户之间交互的图是(8)。
计算机各功能部件之间的合作关系如下图所示。假设图中虚线表示控制流,实线表示数据流,那么a、b和c分别表示(5)。
某企业研发信息系统的过程中,______不属于数据库管理员(DBA)的职责。
高级程序设计语言中用于描述程序中的运算步骤、控制结构及数据传输的是(20)。
在以阶段划分的编译器中,符号表管理和()贯穿于编译器工作始终。
V模型是具有代表意义的测试模型,以下理解正确的是______。A.V模型认为测试阶段是与开发阶段并行的B.V模型是软件开发螺旋模型的变种,它反映了测试活动与分析和设计的关系C.V模型造成需求分析阶段隐藏的问题一直到后期的验收测试才被发现D.V模型是
在结构化分析方法中,用于行为建模的模型是①,其要素包括②。①处应填入?
在一个完整的功能测试过程中,______不属于应该编写的测试文档。A.测试需求文档B.测试用例文档C.测试标准D.问题报告单
网络测试类型包括________。①网络可靠性测试②网络可接受性测试③网络瓶颈测试④网络容量规划测试
随机试题
男性,45岁。反复发生夜间呼吸困难1个月,加重1天就诊。体格检查:血压180/110mmHg,呼吸急促,双肺散在哮鸣音,双肺底细湿啰音,心率130次/min。在没有确诊情况下,不宜应用的药物
A.骨髓B.法氏囊C.脾脏D.胸腺E.淋巴结绝大多数T细胞分化成熟的场所是
男,19岁,患病一周,牙龈乳头坏死,前牙唇侧明显,坏死形成溃疡处凹陷,表面灰白色假膜,触之出血明显,口腔有腐性口臭。体温37.8℃,颏下淋巴结肿痛,既往未出现全身明显异常现象。有辅助诊断意义的检查是
A.气血两虚证B.肾阴亏虚证C.阴阳两虚证D.肾虚血瘀证E.阳虚水停证再生障碍性贫血患者,面色晦暗,头晕耳鸣,腰膝酸软,皮肤紫斑,肌肤甲错,舌质紫暗,脉细。其中医证型是()
在环境温度不低于4℃,且不高于70℃的环境中适用的是()。
公司运用债券投资,不仅取得一笔营运资本,而且还向债权人购得一项以公司总资产为基础资产的( )。
某公司目前的资本来源包括每股面1元的普通股800万股和平均利率为10%的3000万元债务。该公司现在拟投产一个新产品,该项目需要投资4000万元,预期投产后每年可增加营业利润(息税前盈余)400万元。该项目备选的筹资方案有三个:①按11%的利率发行债券
教师如何引导幼儿在动手操作的过程中感受科学探究的过程和方法?
爱国统一战线的政治基础是()
Couldyou______meahandwhenyouhavefinishedyourwork?
最新回复
(
0
)