首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。 为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(1)公里的公路,这种总公里数最少的改造方案共有(2)个。 (2)
下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。 为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(1)公里的公路,这种总公里数最少的改造方案共有(2)个。 (2)
admin
2018-10-14
44
问题
下图标明了六个城市(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
信息系统项目管理师上午综合知识考试
软考高级
相关试题推荐
企业应用集成是一个战略意义上的方法,它从服务和信息角度将多个信息系统绑定在一起,提供实时交换信息和影响流程的能力。(29)提供企业之间的信息共享能力,(30)在用户使用角度能够对集成系统产生一个“整体”的感觉。
UML的事物是对模型中最具有代表性的成分的抽象,(2)是模型的静态部分,描述概念或物理元素;(3)用来描述、说明和标注模型的任何元素。
从A村通过B村再到C村已有一条通信线路。A村与B村间通信线路的可靠度为0.90,B村与C村间通信线路的可靠度为0.70。现在计划在A村与C村之间再直接建一条新的通信线路(见下图)。试问,这条新建通信线路的可靠度至少应该为(59)时,才使A村与C村之间的
某订单处理系统中,“创建新订单”和“更新订单”两个用例都需要检查客户的账号是否正确,为此定义一个通用的用例“核查客户账户”。用例“创建新订单”和“更新订单”与用例“核查客户账户”之间是(1)。
某工厂仓库有一名保管员,该仓库可存放n箱零件。该工厂生产车间有m名工人,只要仓库空闲,工人将生产好的整箱零件放入仓库,并由保管员登记入库数量;该工厂销售部有k名销售员,只要仓库库存数能满足客户要求,便可提货,并由保管员登记出库数量。规定工人和销售员不能同时
某IP网络连接如图2-2所示,在这种配置下IP全局广播分组不能够通过的路径是(72)。
软件测试是为了发现错误而执行程序的过程。检验软件是否满足用户需求的测试称为(114)。(115)是维护中常用的方法,其目的是检验修改所引起的副作用。黑盒测试法主要根据(116)来设计测试用例。
一般来说,在软件维护过程中,大部分工作是由(49)引起的。在软件维护的实施过程中,为了正确、有效地修改程序,需要经历以下三个步骤:分析和理解程序、修改程序和(50)。(51)的修改不归结为软件的维护工作。
COCOMO模型能够依据待开发软件的规模来估计软件开发的工期。若COCOMO模型公式为:MM=3.0×(KDSI)1.12其中,KDSI为预计应交付的源程序千行数,MM为开发该软件所需的人月数。设软件开发的生产率为每个人月能编写的最终能交付的源程
设三个煤场A1、A2、A3分别能供应煤7、12、11万吨,三个工厂B1、B2、B3分别需要煤10、10、10万吨,从各煤场到各工厂运煤的单价(百元/吨)见下表方框内的数字。只要选择最优的运输方案,总的运输成本就能降到()百万元。
随机试题
EDTA配位滴定法,消除其它金属离子干扰常用的方法有()。
100,84,96,76,74的平均差为()
原则型谈判法:
组织结构的特性包括()
类风湿关节炎湿热痹阻证,治疗宜选()
A.湿性重浊B.湿性黏滞C.湿性趋下D.湿性阻遏气机E.湿性损伤阳气患者大便黏腻不爽,小便涩滞不畅,舌苔黏腻等,体现湿邪的性质特点是()。
现房抵押登记应当出具()。
水运工程建设项目施工单项合同估价在()万元人民币以上的工程,必须进行招标。
4G移动通信系统支持的终端最高移动速度为()km/h。
在经济持续繁荣增长时期,资金供不应求,利率下降;当经济萧条市场疲软时,利率会随着资金需求的减少而上升。( )
最新回复
(
0
)