首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(66)公里的公路,这种总公里数最少的改造方案共有(67)个。
下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(66)公里的公路,这种总公里数最少的改造方案共有(67)个。
admin
2009-03-25
82
问题
下图标明了六个城市(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
信息系统项目管理师上午综合知识考试
软考高级
相关试题推荐
TheNISTorganizationhasdefinedbestpracticesforcreatingcontinuityplans.Whichofthefollowingphasesdealswithidentif
可重复使用是在CMMI的哪个阶段?
下面哪项是不道德的??
为每个用户创立了数据库的多个实例,如果区分
这个技术是通过什么技术实现控制?
公司运维外包服务,问什么时候跟服务提供商确定安全要求?
当有802.11b客户端在802.11g小区中时,802.11g客户端将使用哪两种保护方法?(选择两项)A、RTS/CTSB、LMIC、CTStoselfD、RTStoself
用于从自主模式升级到轻型模式的协议是什么?A、FTPB、TFTPC、SCPD、SSH
最近某公司接了一个信息系统运维的项目,而且非常重视,任命了有丰富售后服务经验的张某为系统规划与管理师,全权授权张某负责该项目,并要求他负责企业运维服务能力建设和提升。张某也学习了大量项目管理知识和运维管理知识,并将相关知识运用在该项目中。项目中发生的具体事
以下关于在IPv6中任意播地址的叙述中,错误的是______。
随机试题
就艺术品的鉴赏过程而言,接受者对艺术品有了直观的了解后,将接受活动进一步展开与深化,使意象得以重建,这一过程我们称为()
马克思、恩格斯关于打碎资产阶级国家机器的思想第一次明确提出于()。
社会生活在本质上是实践的,这是因为()
DuringtheAmericanWarofIndependence,womenwereinvolvedintheactivefightinginthreeways.First,asmembersofadistin
经济效益与费用识别的基本要求有()。
对培训的情感成果进行评估时,其测量方法不包括()。(2008年5月二级真题)
在公民享有的宪法基本权利体系中,最基础的权利是()。
(2007年真题)“马锡五审判方式”产生于
Whatisthepurposeofthetalk?
WhatdidsatelliteobservationsshowaboutdeforestationintheAmazon?
最新回复
(
0
)