首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(66)公里的公路,这种总公里数最少的改造方案共有(67)个。
下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(66)公里的公路,这种总公里数最少的改造方案共有(67)个。
admin
2009-03-25
36
问题
下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(66)公里的公路,这种总公里数最少的改造方案共有(67)个。
选项
A、1
B、2
C、3
D、4
答案
C
解析
从图论上看,本题要求得到上图的最小支撑树(即选取部分边,使其保持连通,又使其总长度最小)。
如下算法可以逐步实现这个要求。
任取一点,例如A,将其纳入已完成部分。点A与其他各点中的最小距离为AE=200,从而将边AE以及点E纳入已完成部分。
点A、E与其他各点B、C、D、F这两个集合之间的最段距离为AB=AF=300,从而可以将边AB与点B(或边AF与点F)纳入已完成部分。
点A、B、E与点C、D、F两个集合的最短距离为AF=BF=300,从而可以将边AF(或边BF)与点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(如下图所示)。
连通这6个点的边至少需要5条,最短总长等于2个200以及3个300。图中共有4条边长300,其中,CD边在最短总长度方案中不可缺少,而AB、BF、AF中可以任选2条。因此,共有3个最短总长度的方案。除了上面给出的外,还可以有两种(如下图所示):
转载请注明原文地址:https://kaotiyun.com/show/T9GZ777K
本试题收录于:
信息系统项目管理师上午综合知识考试题库软考高级分类
0
信息系统项目管理师上午综合知识考试
软考高级
相关试题推荐
Bobisanewsecurityadministratoratafinancialinstitution.Theorganizationhasexperiencedsomesuspiciousactivityonone
一个安全工程师被指派去处理公司正在遭受的flood攻击。公司有一个提供电子商务服务的网站。安全策略要求公司可以应对各种攻击,还要保证网站的可用性。问:安全策略最应该关注的是?
YouconfigureyourWindows2000ProfessionalcomputerforInternetConnectionSharingandforTCP/IPfilteringasshowninthee
以下哪项是对射频技术的精确描述?A、尽可能远并尽可能快地发送尽可能多的数据B、向远程终端发送安全数据C、定期地发送少量数据D、利用加密技术短距离发送数据和语音
当AP试图加入一台控制器时,若启动(primed)信息均不可用,则ALP接下来将查询什么?A、一台主控制器B、一台初级(primer)控制器C、一台新的控制器D、一个新的子网
以下哪种状态不是AP正在发现并加入控制器的有效状态?A、发现B、加入C、镜像数据D、Hybrid-REAP
(1)2017年5月12日,新型“蠕虫”勒索病毒WannaCry在全球大规模爆发。这是一起利用NSA黑客武器库泄露的“永恒之蓝”发起的病毒攻击事件。国内连接校园网的电脑以及部分企业中了该病毒,造成许多高校毕业生的论文以及企业单位的文档被锁,需要支付高额赎金
业务需求、IT技术及服务内容和范围的不断变化,对服务能力提出了更高的要求。同时,随着IT服务运营过程中知识的不断沉淀和积累,以及客户期望值的不断提高,必然带来不间断的服务改进需求,所以需要对IT服务进行持续改进。服务持续改进的主要目标是,使得IT服务可以一
Aprojectmanagementtechniquethatiscurrentlyinwidespreaduseisthe(71).Thepurposeofthistechniqueistodetail,inhi
Softwarearchitecturereconstructionisaninterpretive,interactive,anditerativeprocessincludingmanyactivities.(71)involve
随机试题
女,28岁,发现乳腺肿物近1年,逐渐增大,现已有1.8~2cm,圆形。手术所见此肿物包膜清楚,完全摘除。切面区白色,编织样,其中似有黄色点状病变。组织学上包膜清,肿瘤由纤维及腺体组成。两者分化均良好,无明显异型性。请问此病应诊断为
氧气雾化吸入时,正确的是
我国《公路工程无机结合料稳定材料试验规程》(JTGE51—2009)测量回弹模量的方法有()。①室内抗压回弹模量试验方法(顶面法)。②室内抗压回弹模量试验方法(承载板法)。③动态抗压回弹模量试验方法。④劈裂回弹模量试验方法。⑤弯拉回弹
根据《中华人民共和国进出口关税条例》的规定,进口货物应按照:
对员工进行绩效评估时,提供给评分者一份与工作绩效相关的表述清单,评分者依据此清单为每个员工选择最恰当的表述表现的是()。
企业对面临的很多风险采取接受的态度,从而承担风险带来的后果,其原因包括()。
真理和谬误相互贯通的含义是指()。
某超市顾客甲与超市工作人员乙发生争执,并大打出手,乙说发现甲偷超市东西,甲否认。派出所民警赶到现场,为弄清该事件,派出所人员进行调查。下列调查行为对本案的解决,意义不大的是()。
Imusttrytomake______asIcanofthisprojectwhichIhaveundertaken.
TheImportanceofaGoodStartForthispart,youareallowed30minutestowriteanessaycommentingonthesaying"Agood
最新回复
(
0
)