首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下图标明了6个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(58)公里的公路,这种总公里数最少的改造方案共有(59)个。
下图标明了6个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(58)公里的公路,这种总公里数最少的改造方案共有(59)个。
admin
2009-03-25
77
问题
下图标明了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
系统分析师上午综合知识考试
软考高级
相关试题推荐
在WindowsXP的桌面上新创建名为"附件"的文件夹图标。
利用写字板新建一个类型为"文本文档"的文件,内容为"祝你取得成功!"。保存在C:\,文件名为LX1.TXT。
在桌面显示"IE"图标(不是快捷方式)。
在Excel中,函数ABS(ROUND(-1.478,2))的计算结果是()。A.-1.478B.1.48C.-1.48D.1.5
在一张PPoint幻灯片播放后,要使下一张幻灯片内容的出现呈水平盒状收缩方式或垂直百叶窗方式,应()。A.单击“幻灯片放映”→“预设动画”进行设置B.单击“幻灯片放映”→“设置放映方式”进行设置C.单击“幻灯片放映”→“自定义动画”进行设置D.
WORD中,如果已在“选项”的“编辑”标签中选中了“即点即输”但编辑文档时仍不能用()A.所编辑文档取消了WORD97功能B.打开为旧版本C.没有选用的模式D.当前视图为普通视图
下列叙述正确的是______A.进行打印预览时必须开启打印机B.使用“文件”菜单中的“打开”命令可以打开一个以存在的.DOC文件C.Word2000可将正在编辑的文档另存为一个纯文本(.TXT)文件D.Word2000允许同时打开多个文件
windows是()操作系统。A.单用户单务 B.单用户多任务 C.多用户多任务 D.多用户单任务
某市公安局信息中心机房于2003年建立,目前IT设备支撑着警综系统、八大资源库、110联动项目、政法网、警用地理信息系统,市局OA系统等;2018年,某市公安局提出《某市公安局直属单位信息化机房及硬件基础设施建设和运维统筹实施方案》,将信息中心运维范围进一
阅读以下说明,回答问题1至问题5,将解答填入答题纸对应的解答栏内。【说明】某高校校园网使用3个出口,新老校区用户均通过老校区出口访问互联网,其中新老校区距离20公里,拓扑结构如图2-1所示,学校服务器区网络拓扑结构如图2-2所示。目前存储中使用较
随机试题
《联合国国际货物销售合同公约》排除了一些特殊标的物的货物买卖,公约排除的货物销售不包括()
下列选项中属于职业道德作用的是()。
【2010年第117题】关于抗震设防地区多层砌块房屋圈梁设置的下列叙述,哪项不正确?
关于上海证券交易所法人清算模式中的资金划入,说法不正确的是( )。
甲公司是一家高科技环保企业,其自主研发的智能呼吸窗刚推向市场,即受到消费者欢迎,产品供不应求,企业一直处于满负荷生产状态。为满足持续增长的订单要求,公司决定增加一条生产流水线。甲公司所实施的产能计划属于()。
在确定作业数量时,究竟应划分和确定多少作业,应遵循()原则,在“粗分”和“细分”之间进行权衡。
“以僧为师”,“以(书)吏为师”是古代()的教育特点。
定金的数额由当事人约定,但不能超过主合同标的额的()。
下列()是C+4.语言的有效标识符。
窗体设计中,决定了按【Tab】键时焦点在各个控件之间移动顺序的属性是()。
最新回复
(
0
)