首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(66)公里的公路,这种总公里数最少的改造方案共有(67)个。
下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(66)公里的公路,这种总公里数最少的改造方案共有(67)个。
admin
2009-03-25
84
问题
下图标明了六个城市(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
信息系统项目管理师上午综合知识考试
软考高级
相关试题推荐
CPUsandoperatingsystemscanworkintwomaintypesofmultitaskingmodes.Whatcontrolsaccessandtheuseofsystemresource
PADDING技术使用在哪种密码上?
黑客使用硬件密钥存储比软件密钥存储的优势是?
公司进行信息安全评估,打算把所有应用程序维护外包,问对服务提供商什么是最重要的?
一个安全经理到一家公司,发现其有洪泛攻击,为了解决此问题,且又要公司相关WEB上的应用不能停止,应采用的方式为:
Cisco无线定位设备最多可提供对多少个客户端进行实时跟踪?A、1500B、2500C、3500D、5000
对于802.11a,下列哪种调制技术是无效的?A、BPSKB、QPSKC、Barker11D、QAM
当没有802.11b客户端在802.11b/g小区时,在AP的信标(beacon)中将会出现什么样的信息?A、NON_ERPpresent:yes;UseProtection:noB、NON_ERPpresent:no;UseProtectio
李涛是某公司一名技术骨干,沟通能力比较强,因此项目部张经理委派他担任一个中等项目的项目经理。李涛负责的项目有以下特点:(1)项目刚刚完成立项,从项目的技术可行性分析预计规模为100人月,涉及5个需求部门。(2)项目涉及与合作方的实时联机交易和批量文件交
王先生加入一家新成立的大型企业担任CIO,企业刚完成主要IT系统的建设,逐步进入稳定维护期,需要玉先生尽快组织建立成熟的服务运营管理体系,对相关工作提供科学合理的考核管理。王先生借鉴了成熟的ITSS服务标准,根据管理要素分别组织了不同的工作小组,包含过程
随机试题
阿莫西林对耐药金黄色葡萄球菌引起的感染效果良好。
肠易激综合征(IBS)最主要的症状是
患者每因情绪紧张发生腹痛泄泻,且胸胁胀闷,嗳气食少,矢气频作,舌淡红,脉弦。治疗应首选的方剂是
某患者女性,21岁,心慌、多汗半年来诊。既往无哮喘病史。查体:体型消瘦,双眼稍突出,甲状腺Ⅱ度肿大,双叶上极可闻及血管杂音,无颈静脉怒张,心界不大,心率120次/min,律绝对不齐,第一心音强弱不等,脉短绌,双下肢无水肿。患者应采用哪些治疗方案
既是肾上腺素能仅受体激动药又是肾上腺素能D受体激动药的是
善于治疗筋急项强不可转侧的药物是()肝肾不足,腰腿疼痛可应用的药物是()
气瓶安全泄压装置包括()。
垄断资本主义阶段,取代商品输出成为这个阶段经济特征的是()。
高考临近,随着H1N1在我国出现,现在要你制作一套高考期间的防控H1N1的紧急预案,你的方案是什么?
请编写函数fun,其功能是:将放在字符串数组中的M个字符串(每串的长度不超过N),按顺序合并组成一个新的字符串。例如,若字符串数组中的M个字符串为{“AAAA”,“BBBBBBB”,“CC”},则合并后的字符串内容应该是“AAAABBBBBBBC
最新回复
(
0
)