登录
|
注册
投稿
|
充值
|
收藏
首页
找答案
试卷
网课
教材
求助
网课类
计算机
管理学
经济学
外语
哲学
法学
理学
工学
历史
教育教学
文学文化
农林园艺
医药卫生
艺术设计
其他
高职高专
中职中专
公务员
公务员考试
事业单位招录
政法干警
公开遴选
招警考试
军转干
选调生
大学生村官
三支一扶
教师资格
干部教育
计算机
职称计算机
等级考试
软件水平
计算机认证
计算机应用能力
IT技能
高教类
哲学类
经济学类
法学类
教育学
历史学
理学类
工学类
农学类
医学类
管理学类
艺术学类
语言文学类
军事学
通识课
财经类
会计职称
注册会计师
经济师
银行从业资格
证券从业资格
期货从业资格
税务师
审计师
基金从业资格
统计师
学历类
研究生考试
普通高考
自学考试
成人高考
高职单招
小升初
中考
医药类
兽医资格
执业医师
执业药师
卫生技术资格
护士执业资格
执业助理医师
医技职称
资格类
法律职业资格
导游资格
社会工作者
职业资格证书
人力资源师
出版专业资格
心理咨询师
通信工程师
工程类
一级消防工程师
一级建造师
二级建造师
一级造价工程师
二级造价工程师
安全工程师
监理工程师
二级消防工程师
建筑八大员
房地产经纪人
土建职称
公路检测工程师
注册建筑师
语言类
公共英语
出国英语
英语翻译资格
汉语水平考试
大学四六级
商务英语
职称英语
益智类
古典诗词
党建党史
人文历史
科普教育
文明礼仪
法律法规
时政财经
K12教育
小学语文
小学数学
小学英语
初中语文
初中数学
初中英语
初中政治
初中历史
初中地理
初中物理
初中生物
高中语文
高中数学
高中英语
高中历史
高中政治
高中地理
高中物理
高中化学
高中生物
初中化学
导航
您当前的位置:
首页
>
计算机
>
软件水平
问题:
★收藏
[问答题] 现需在某城市中选择一个社区建一个大型超市,使该城市的其它社区到该超市的距离总和最小。用图模型表示该城市的地图,其中顶点表示社区,边表示社区间的路线,边上的权重表示该路线的长度。现设计一个算法来找到该大型超市的最佳位置:即在给定图中选择一个顶点,使该顶点到其它各顶点的最短路径之和最小。算法首先需要求出每个顶点到其它任一顶点的最短路径,即需要计算任意两个顶点之间的最短路径;然后对每个顶点,计算其它各顶点到该顶点的最短路径之和;最后,选择最短路径之和最小的顶点作为建大型超市的最佳位置。【问题1】(12分)本题采用Floyd-Warshall算法求解任意两个顶点之间的最短路径。已知图G的顶点集合为V={1,2,...,n},W={Wij}n*n为权重矩阵。设d(k)ij为从顶点i到顶点j的一条最短路径的权重。当k=0时,不存在中间顶点,因此d(0)ij=wij;当k>0时,该最短路径上所有的中间顶点均属于集合{1,2,...,k}若中间顶点包括顶点k,则d(k)ij=d(k-1)ik+d(k-1)kj;若中间顶点不包括顶点k,则d(k)ij=d(k-1)ij。于是得到如下递归式
因为对于任意路径,所有的中间顶点都在集合{1,2,...,n}内,因此矩阵D(n)={d(n)ij}n*n给出了任意两个顶点之间的最短路径,即对所有i,j∈V,d(n)ij表示顶点i到顶点j的最短路径。下面是求解该问题的伪代码,请填充其中空缺的(1)至(6)处。伪代码中的主要变量说明如下:W:权重矩阵n:图的顶点个数SP:最短路径权重之和数组,SP[i]表示顶点i到其它各顶点的最短路径权重之和,i从1到nmin_SP:最小的最短路径权重之和min_v:具有最小的最短路径权重之和的顶点i:循环控制变量j:循环控制变量k:循环控制变量
【问题2】(3分)【问题1】中伪代码的时间复杂度为(7)(用Ο符号表示)。
Tags:
软件水平考试中级软件设计师试题及答案
答案解析:
╋纠错
查看答案解析
您可能感兴趣的问题
SQL Error: select * from ***_ecms_ask2 where id in(4441,4354,4446,,4438,4491,4456,4396,157,4406) limit 10
相关问题
[问答题]某企业拟构建一个高效、低成本、符合企业实际发展需要的办公自动化系统 。工程师小李主要承担该系统的公告
[问答题]以下C++代码实现一个简单乐器系统,音乐类(Music)可以使用各类乐器(Instument)进行演奏和调音等操作。对部分
[问答题]某公司拟研制一款高空监视无人直升机,该无人机采用遥控一自主复合型控制实现垂直升降。该直升机飞行控制系统
[问答题]"背包问题"的基本描述是:有一个背包,能盛放的物品总重量为S,设有N件物品,其重量分别为w1,w2,...wn,希望从N件物品中选
[问答题]某饭店在不同的时段提供多种不同的餐饮,其菜单的结构图如图5-1所示。现在采用组合(Composition)模式来构造该
[问答题]某饭店在不同的时段提供多种不同的餐饮,其菜单的结构图如图5-1所示。现在采用组合(Composition)模式来构造该
[问答题]某公司欲建设一个房屋租赁服务系统,统一管理房主和租赁者的信息,提供快捷的租赁服务。本系统的主要功能描述如
[问答题]某软件公司为共享单车租赁公司开发一套单车租赁服务系统,公司项目组对此待开发项目进 行了分析,具体描述如下:1
[问答题]以下Java代码实现一个简单乐器系统,音乐类(Music)可以使用各类乐器(Instrument)进行演奏和调音等操作。对部
[问答题]某图像预览程序要求能够查看 BMP 、JPEG 和 GIF 三种格式的文件,且能够在 Windows 和Linux 两种操作系统上运
关于我们
|
用户指南
|
版权声明
|
给我留言
|
联系我们
|
积分商城
|
答案求助
|
网站地图
Copyright © 2024
www.daanwo.com
All Rights Reserved
沪ICP备19038360号-2
用户登录
快速注册
×
记住我,保持登录
登 录
忘记密码?
找回密码
用户名:
密码:
重复密码:
激活邮箱:
(务必正确)
我已阅读并接受《
服务条款
》
注 册