首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下图标明了6个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(58)公里的公路,这种总公里数最少的改造方案共有(59)个。
下图标明了6个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(58)公里的公路,这种总公里数最少的改造方案共有(59)个。
admin
2009-03-25
85
问题
下图标明了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
系统分析师上午综合知识考试
软考高级
相关试题推荐
利用我的电脑,将C盘"考题"文件夹删除。
利用快捷菜单将桌面上的图标"按名称"排列。
用Word97对文档进行分栏设置,最多能分的栏数是()。A.3栏B.5栏C.11栏D.2栏
现在计算机正朝两极方向发展,这两极是()。A.专用机B.微型机C.巨型机D.通用机
在普通视图中只出现()方向的标尺。
在Excel97中,工作薄窗口冻结的形式包括()。A.水平冻结B.垂直冻结C.水平、垂直同时冻结D.以上全部
关于Excel中创建图表,叙述正确的是______A.嵌入式图表建在工作表之内,与数据同时显示B.如果需要修饰图表,只能使用格式栏上的按钮C.创建了图表之后,便不能修改D.图表工作表建在工作表之外,与数据分开显示
常说的计算机是486.586.686等指的是()。A.cpu的型号B.计算机中cpu的价格C.内存储器的容量D.cpu的执行速度
internet的通信协议是()协议。
将文本中的H2中的“2”设置为下标显示。
随机试题
男,30岁。既往有乙型肝炎病史。近1个月来右上腹反复疼痛,查体:肝肋下3cm,质硬,有结节感。实验检查应首选下列哪项
下列建筑工程中,适合采用成本加酬金合同的有()。
许多分析师倾向于使用价格与每股现金流比率作为股票估价的指标,常用到的现金流形式有()Ⅰ收益加非现金支付Ⅱ经营现金流Ⅲ调整的经营现金流Ⅳ股权自由现金流
产品的生产过程中,需要设置和运用的账户有()。[2013年真题]
期货经纪合同对下达交易指令的方式未作约定或者约定不明确的,期货公司进行期货交易造成损失,除下列( )情况外,期货公司应当赔偿客户的损失。
下列不属于商业银行理财顾问服务的是()。
某电视机有限公司在组织筹建阶段,由出资人共同协商推荐董事候选人,下列候选人中()不能担当董事。
下列法律中,没有专门对少年儿童受教育的权利作出规定的是()。
晚清小说《官场现形记》是谁写的?(厦门大学2011翻译硕士)
A、mostsoutherly.B、Shapedlikeacomma.C、Mostrecentlydiscovered.D、Richinnaturalrecourses.D文中提到“becauseoftheextreme
最新回复
(
0
)