首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下图标明了6个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(58)公里的公路,这种总公里数最少的改造方案共有(59)个。
下图标明了6个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(58)公里的公路,这种总公里数最少的改造方案共有(59)个。
admin
2009-03-25
76
问题
下图标明了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
系统分析师上午综合知识考试
软考高级
相关试题推荐
在“我的电脑”窗口中,快速格式化一张软盘,并将ZCKS作为磁盘卷标。
利用动态键盘在写字板上输入希腊字母ψ和η,然后保存为C:\SPF1.RTF。
利用开始菜单打开WindowsXP的"MS-DOS方式",设置字体为8*18。
在桌面显示"IE"图标(不是快捷方式)。
在Excel97的编辑栏中,总是显示()的内容或公式。A.上一单元格B.当前行C.当前列D.当前单元格
在Word97的编辑状态,执行“文件”菜单中的“保存”命令后()。A.将所有打开的文档存盘B.只能将当前文档存储在原文件夹的文件内C.可以将当前文档存储在已有的任意文件夹内D.可以先建立一个新文件夹,再将文档存储在该文件夹内
用“ATC”3个英文字母输入为代替“认证管理中心”6个汉字,应用()功能。A.文字校对B.自动更正C.自动摘要D.替换
WORD中,如果已在“选项”的“编辑”标签中选中了“即点即输”但编辑文档时仍不能用()A.所编辑文档取消了WORD97功能B.打开为旧版本C.没有选用的模式D.当前视图为普通视图
在Excel97中,工作薄窗口冻结的形式包括()。A.水平冻结B.垂直冻结C.水平、垂直同时冻结D.以上全部
论IT服务风险管理风险是在实现服务目标过程中所带来的不确定性和可能性,风险一旦发生,会对服务产生某种影响。请以“IT服务风险管理”为题,分别从以下三个方面进行论述:(1)概要叙述你参与管理过的IT服务项目(项目的背景、项目规模、目的、项目内容、组织结构
随机试题
黄某2011年10月因医疗事故受到吊销医师执业证书的行政处罚,2012年9月向当地卫生行政部门申请重新注册。卫生行政部门经过审查决定对黄某不予注册,理由是黄某的行政处罚自处罚决定之日起至申请注册之日止不满
《中华人民共和国环境影响评价法》规定:(),应当在该规划草案报送审批前,举行论证会、听证会,或者采取其他形式,征求有关单位、专家和公众对环境影响报告书草案的意见。
关于水泥混凝土路面施工安全要点的说法错误的是()。
一般地,算术平均收益率要小于几何平均收益率。( )
中国证监会只能对保荐机构及其保荐代表人从事保荐业务的情况进行定期现场检查,且需提前通知。( )
甲、乙、丙、丁、戊共同出资设立一个有限合伙企业,甲、乙、丙为普通合伙人,丁、戊为有限合伙人。执行事务合伙人甲提议接收庚为新合伙人,乙、丙反对,丁、戊同意。合伙协议对新合伙人入伙的表决办法未作约定。因未得到全体合伙人一致同意所以庚不得入伙。()
在党的十一届三中全会上,我国正式提出了社会主义经济是公有制基础上的有计划的商品经济的科学论断。()
十八届三中全会指出,公有制为主体、多种所有制经济共同发展的基本经济制度,是中国特色社会主义制度的重要支柱,也是社会主义市场经济体制的根基。公有制经济和非公有制经济都是社会主义市场经济的重要组成部分,都是我国经济社会发展的重要基础。必须毫不动摇巩固和发展公有
Psychologiststakecontrastiveviewsofhowexternalrewards,from【C1】______praisetocoldcash,affectmotivationandcreativit
A、Aboutfourthirty.B、Aboutfivethirty.C、Aboutthreethirty.D、Aboutthree,CWhenwillMr.Smithcomeback?问史密斯先生什么时候会回来?C选项“
最新回复
(
0
)