首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。 为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(1)公里的公路,这种总公里数最少的改造方案共有(2)个。 (2)
下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。 为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(1)公里的公路,这种总公里数最少的改造方案共有(2)个。 (2)
admin
2018-10-14
19
问题
下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。
为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(1)公里的公路,这种总公里数最少的改造方案共有(2)个。
(2)
选项
A、1
B、2
C、3
D、4
答案
C
解析
这是一个典型的无向连通图的最小生成树问题(Minimum Spanning Tree)。
算法如下:
任取一点,例如A,将其纳入已完成部分。点A与其他各点中的最小距离为AE=200.从而将边AE以及点E纳入已完成部分。
点A、E与其他各点B、C、D、F这两个集合之间的最短距离为AB=AF=300,任选其一,比如AB,从而将边AB与点B纳入已完成部分。
点A、B、E与点C、D、F两个集合的最短距离为AF=BF=300,任选其一,比如AF,从而将边AF与点F纳入已完成部分。
点A、B、E、F与点C、D两个集合之间的最短距离为FD=200,从而将边FD与点D纳入已完成部分。
点A、B、E、F、D与点C两个集合之间的最短距离为CD=300,从而将边CD与点C纳入已完成部分。
此时,所有6个点都已经接通,其边为AE、AB、AF、FD、cD,总长度为1300,如下图所示:
最优方案共有三个,即AB、AF、BF这个等边三角形任选2条边,剩下的两个备选方案是:
转载请注明原文地址:https://kaotiyun.com/show/xvFZ777K
本试题收录于:
信息系统项目管理师上午综合知识考试题库软考高级分类
0
信息系统项目管理师上午综合知识考试
软考高级
相关试题推荐
在操作系统中,虚拟输入/输出设备通常采用(46)来实现。
某订单处理系统中,“创建新订单”和“更新订单”两个用例都需要检查客户的账号是否正确,为此定义一个通用的用例“核查客户账户”。用例“创建新订单”和“更新订单”与用例“核查客户账户”之间是(1)。
逆向工程过程的抽象层次是指可从源代码中抽取出来的设计信息的精制程度。抽象层次分为四层,其中“最低层”抽象能够导出过程的设计表示文档,“低层”抽象能够导出程序和数据结构信息,“中层”能够导出(1),“高层”抽象能够导出(2)。
某教授1996年3月1日自选将我国《计算机软件保护条例》译成英文,投递给某刊物,于1996年6月1日发表。国家有关机关认为该教授的译文质量很高,经与该教授协商,于1997年2月10日发文将该译文定为官方正式译文。该教授对其译文(19)。
某市标准化行政主管部门制定并发布的工业产品安全的地方标准,在其行政区域内是(21)。
在层次化网络设计方案中,(75)是核心层的主要任务。
软件测试是为了发现错误而执行程序的过程。检验软件是否满足用户需求的测试称为(114)。(115)是维护中常用的方法,其目的是检验修改所引起的副作用。黑盒测试法主要根据(116)来设计测试用例。
净室软件工程(Cleanroom)是软件开发的一种形式化方法,可以开发较高质量的软件。它使用(91)进行分析和建模,并且将(92)作为发现和排除错误的主要机制。使用(93)测试来获取认证软件可靠性所需要的信息。
在磁盘调度管理中,应先进行移臂调度,再进行旋转调度。若磁盘移动臂位于22号柱面上,进程的请求序列如下表所示。若采用最短移臂调度算法,则系统的响应序列应为(47),其平均移臂距离为(48)。(48)
设三个煤场A1、A2、A3分别能供应煤7、12、11万吨,三个工厂B1、B2、B3分别需要煤10、10、10万吨,从各煤场到各工厂运煤的单价(百元/吨)见下表方框内的数字。只要选择最优的运输方案,总的运输成本就能降到()百万元。
随机试题
夜间驾驶机动车超车遇前车不让路时怎样处置?
肾细胞癌的临床病理特点有()
关于卵巢周期性变化错误的是
与电源直接接触所致电烧伤的主要特点是()
如果杨某拿到工钱后就将老板的儿子交还而没有提出再拿5万元的要求,则杨某的行为是否构成犯罪?如果杨某在老板未拿5万元来赎儿子之前,出于良知,将老板的儿子放回,则杨某的行为是否属于犯罪中止?为什么?
常用的授权形式中,()根据银行信用评级政策,对不同信用等级的客户分别授予不同的权限。
习近平总书记在论述“四个全面”战略布局之间的关系时指出,()是我们的战略目标,其他三项是三大战略举措。
关于保护管辖原则,下列说法不正确的是()
在正向市场中,期货价格高出现货价格的部分与()的高低有关。
【B1】【B8】
最新回复
(
0
)