首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(66)公里的公路,这种总公里数最少的改造方案共有(67)个。
下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(66)公里的公路,这种总公里数最少的改造方案共有(67)个。
admin
2009-03-25
83
问题
下图标明了六个城市(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
信息系统项目管理师上午综合知识考试
软考高级
相关试题推荐
DNSisapopulartargetforattackersduetoitsstrategicroleontheInternet.Whattypeofattackusesrecursivequeriestop
在安全审计时发现服务器管理员没有经过培训,应该?
情境题,一个公司规定“专利未发布前,知道此信息的员工不能买股票,除非已对公众公布”,次日,该公司在报纸上发布该消息,问员工能不能买股票
一个安全工程师被指派去处理公司正在遭受的flood攻击。公司有一个提供电子商务服务的网站。安全策略要求公司可以应对各种攻击,还要保证网站的可用性。攻击者可能带来的威胁是?
出口时设置智能卡读卡器的作用:
控制器能够实现下列哪些功能?(选择所有正确答案)A、关联B、客户端正在漫游时重新关联C、认证过程D、在客户端之间的帧交换与握手
BSS代表什么?A、基本服务信号B、基本服务分离C、基本服务集D、基本信号服务器
B公司是一家专门提供信息技术服务的供应商,其IT服务事业部设置有热线中心、备件中心、技术服务中心和客户服务中心。其中热线中心主要负责400电话的接听、咨询类问题解答和事件的派单工作;备件中心主要负责相关设备的备品和备件储备计划、采购和备件日常维护管理工作;
业务需求、IT技术及服务内容和范围的不断变化,对服务能力提出了更高的要求。同时,随着IT服务运营过程中知识的不断沉淀和积累,以及客户期望值的不断提高,必然带来不间断的服务改进需求,所以需要对IT服务进行持续改进。服务持续改进的主要目标是,使得IT服务可以一
IT服务营销过程共分四个阶段,下面______不属于这四个阶段的内容。
随机试题
他汀类药物通过抑制胆固醇的内源性合成降低血脂。因胆固醇主要在夜间合成,半衰期短的药物适宜睡前服用。半衰期长、体内作用时间久、可在每天任何固定时间服药的是
设f(x)是以2π为周期的周期函数,它在(一π,π)上的表达式为f(x)=x2+x,求f(x)的傅里叶级数展开式。
下列引起上消化道出血的胃肠道疾病中,最为常见的是()。
甲某诉乙公司侵犯其专利权纠纷一案,经过区人民法院与市中级人民法院两审终审后,省高级人民法院再审过程中,发现区人民法院与市中级人民法院审理过程中,均遗漏了丙某这一共同专利权人。此时,省高级人民法院的下列哪一做法是正确的?
建设工程合同管理的根本目的是( )。
100MW及以上的汽轮发电机,励磁顶值电压倍数一般为()。
环境影响是人类的经济和社会活动对环境的作用导致的环境变化以及由此引起的对人类社会和经济的效应。下列关于环境影响的说法正确的有()。
下列说法中,不属于投机性资本流动的是()。
“率真、耿直”反映的个性心理现象是()
考虑价格错觉模型的货币政策。假设政府要把如下目标函数最小化:W(u,π)=u2+βπ2,其中u是实际失业率,丌是实际通货膨胀率。现在假设这个经济体的失业率和通货膨胀率之间存在如下关系:u=un-α(π-πe),其中un是自然失业率,πe是居民的预期通货膨胀
最新回复
(
0
)