首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下图标明了6个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(58)公里的公路,这种总公里数最少的改造方案共有(59)个。
下图标明了6个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(58)公里的公路,这种总公里数最少的改造方案共有(59)个。
admin
2009-03-25
57
问题
下图标明了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
系统分析师上午综合知识考试
软考高级
相关试题推荐
将桌面上的XXX.doc文件彻底删除(用快捷键)。
在C盘上搜索第二个字符为e的文件和文件夹。
利用Excel97的“条件格式”功能,可动态地为选定区域内各单元格自动设置格式,“条件格式”对话框提供了最多()个条件表达式。A.1B.2C.3D.4
Excel2000中,使用()在单元格中应用公式A.常用工具栏B.直接键盘输入C.插入菜单D.格式工具栏
在Word文档编辑中对正文的段落进行格式化时,一般采用标尺中的()快捷键、格式菜单等方法。
在普通视图中只出现()方向的标尺。
在Word的编辑状态,假设被编辑文档中的文字有“四号”、“五号”、“16”磅、“18”磅四种,下列关于所设定字号大小的比较中,正确的是()。A.“四号”大于“五号”B.“四号”小于“五号”C.“16”磅大于“18”磅D.字的大小一样,字体不同
()又称协议转换器,主要用于连接不同结构体系的网络或局域网与主机之间的连接。
Thefollowingscenariowillbeusedtoanswerquestions28and29.Seanhasbeenhiredasbusinesscontinuitycoordinator.Heha
某大型国有企业主要从事无线电频谱管理、无线电台站管理、无线电监测、无线电设备管理、无线电管理信息化等业务技术工作,随着业务的不断深入,信息系统已经逐步成为中心开展业务工作、提高管理水平的重要手段。目前由中心信息管理处负责运行维护的信息系统涉及内、外网网络、
随机试题
对于如图所示的AOE网,写出其关键路径。
设函数z=sin(x+y),则()
中毒的治疗原则包括
含生物碱类成分的药材有
A.溶液片B.分散片C.泡腾片D.多层片E.口含片可避免复方制剂中不同药物之间的配伍变化的是()。
在采用风险回避对策时需要注意的问题有( )。
下列情形中,建设工程施工合同可认定为无效的有()
两个朋友结伴去旅行,因为缺水被困沙漠。其中一个去找水,临行前他拔出一支手枪对同伴说:“里面有5颗子弹,你每隔一小时就向天空放一枪,这样我就不会迷失方向,找到水便能循着枪声返回你身边了。”同伴等啊等,等枪里还剩下最后一颗子弹时,找水的人还没回来,是被风沙吞
人民警察有下列哪项情形,错误比较严重又不宜给予行政开除处分的,应当予以辞退?()
一、注意事项一、本试卷由给定资料与作答要求两部分构成。考试时限为150分钟。其中,阅读给定资料参考时限为40分钟,作答参考时限为110分钟。满分100分。二、第一题、第二题、第五题,所有考生都必须作答。第三题仅限报考行政执法类、市(
最新回复
(
0
)