首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下图标明了6个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(58)公里的公路,这种总公里数最少的改造方案共有(59)个。
下图标明了6个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(58)公里的公路,这种总公里数最少的改造方案共有(59)个。
admin
2009-03-25
86
问题
下图标明了6个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(58)公里的公路,这种总公里数最少的改造方案共有(59)个。
选项
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/Q2LZ777K
本试题收录于:
系统分析师上午综合知识考试题库软考高级分类
0
系统分析师上午综合知识考试
软考高级
相关试题推荐
隐藏桌面上的"我的电脑"图标。
在Word中把一个已经打开的文件以新的名字存盘,起备份旧文件的作用,应选()命令。A.自动保存B.保存C.另存为D.全部保存
将用户用高级语言编写的源程序转换成目标程序是通过哪一种程序来实现的()A.编译程序B.编辑程序C.操作系统D.汇编程序
对于PPoint中的视图模式,以下说法错误的是()。A.幻灯片浏览视图下不能设置放映方式B.幻灯片视图注重于对幻灯片的文本和对象进行详细操作C.每种视图模式在演示文稿的制作和显示中有不同的作用D.大纲视图便于查看和编排演示文稿的大纲
HTML文本显示状态代码中,SUP/SUP表示______。A.文本加注下标线B.文本加注上标线C.文本闪烁D.文本或图片居中
对数据排序时,下列操作错误的是()A.选清单中任意一个单元格B.选清单做排序操作C.选清单中任意一行排序D.选工作表中任意一个单元格排序
pc机的标准输入设备是()。A.键盘B.鼠标C.扫描仪D.数码相机
对于PPoint来说,以下说法正确的是()。A.启动PPoint后直到关闭的过程中,只能建立或编辑一个演示文稿文件B.启动PPoint后直到关闭的过程中,可以建立或编辑多个演示文稿文件C.启动PPoint后,不能编辑多个演示文稿文件D.启动PP
下列关于队列的叙述中正确的是______。
Hereisagraphicofabusinesscontinuitypolicy.Whichcomponentismissingfromthisgraphic?
随机试题
下列添加剂名称不属于“食品名称”的规定标示具体名称的是()。
求函数f(x)=x+的单调区间、极值、凹凸区间及拐点.
患儿,症见面色白,全身浮肿,按之没指,大便溏薄,神倦畏寒,四肢不温,腰酸肢冷。治疗应首选
南京某锅炉厂将其生产用的锅炉设备(价值80万元)向保险公司投了火灾保险。2010年9月18日.由于监控温度计的表失灵,炉温急剧上升,在危急万分时刻,锅炉设备随时有爆炸的危险。为了防止锅炉爆炸,有关人员决定立即向锅炉内投入大量冷却剂降温,从而避免了事故发生
目前我国采用的国债发行方式主要有()三种方式。
银监会于2012年颁布的《商业银行资本管理办法(试行)》中关于信息披露的要求,则侧重于商业银行资本计量和管理相关信息的披露。()
根据《物权法》的规定,债务人或者第三人有权处分的下列财产可以抵押的有()。
法约尔模型的主要特点有()。
“心理不健康状态”的预测效度是指()。
OxfordandCambridgeUniversityBoatClubshavebothtakentheopportunitytotraveltoSpainthismonthtotraininlesstestin
最新回复
(
0
)