首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下图标明了6个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(58)公里的公路,这种总公里数最少的改造方案共有(59)个。
下图标明了6个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(58)公里的公路,这种总公里数最少的改造方案共有(59)个。
admin
2009-03-25
60
问题
下图标明了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://jikaoti.com/ti/68J7FFFM
本试题收录于:
系统分析师上午综合知识考试题库软考高级分类
0
系统分析师上午综合知识考试
软考高级
相关试题推荐
在“我的电脑”窗口中,快速格式化一张软盘,并将ZCKS作为磁盘卷标。
利用我的电脑,将C盘"考试"文件夹中的"WKT.doc"文件改名为"考试.doc"。
在PPoint中,超级链接只有在()中起作用。A.幻灯片视图B.幻灯片放映C.幻灯片浏览视图D.大纲视图
在Excel97中,数据清单的第一行一般为()。A.文件名B.字段名C.标题D.建立日期
在PPoint97中,若要统计幻灯片的张数及字数等信息,则应执行()菜单中的“属性”命令。A.视图B.工具C.文件D.数据
pc机的标准输入设备是()。A.键盘B.鼠标C.扫描仪D.数码相机
PPoint中,设置幻灯片切换方式将弹出“幻灯片切换”对话框,对该对话框描述错误的是()。A.“全部应用”按钮表示每张幻灯片的切换都使用设置的切换方式B.“应用”按钮表示仅在当前幻灯片切换时,使用设置的切换方式C.效果区中的下拉列表框中提供了多种
word是一个非常优秀的()软件。A.数据库 B.cad C.字处理 D.图象处理
windows是()操作系统。A.单用户单务 B.单用户多任务 C.多用户多任务 D.多用户单任务
阅读以下关于一卡通信息化建设平台的叙述,回答下列问题。【说明】某部队院校早期的一卡通建设方案主要为保障校内师生的图书、食宿、医疗等服务,系统包括了一卡通专网建设、一卡通平台建设、一卡通数据中心以及校园门禁与校园网视频监控等内容。行政办公、家属区
随机试题
某市政府根据市人大建议,为了克服多头执法、执法扰民的弊端,发文成立了由公安、税务、工商、环保、城管、卫生等部门出人组成的综合执法队,该队集上述部门的职能于一身。综合执法队到农贸市场检查时,发现张某销售假化肥,于是决定处2000元罚款,没收库存化肥。张某不服
“芦长碗密枣核芋,紧皮细纹珍珠须”此话是用来形容质佳的()
动叶通道中,()。
对于圆管流来说,直径d=50mm,流量为0.002m3/s,则断面平均流速为()。
2006年10月某公司一批施工机械到岸价20000元,准予暂时进口,该机械至2007年10月10日仍留在境内使用;假如该机械的关税税率为10%,则海关应征关税()。
存储器容量1GB、1KB、1MB分别表示2的()次方字节。
根据下列资料,回答下列问题。2015年1—4月,民间固定资产投资为()亿元。
据调查,某省2006年小麦种植面积为2739万亩,比上年增加169万亩,预计总产量940万吨,比上年增加90万吨,平均单产343公斤/亩,其中预计白麦总产量558万吨,红麦总产量361万吨,还有少量花麦。2006年某省小麦生产有一个重要的特点,就
某市钟鼓楼上的古钟在沉寂了30多年后被人修好又开始正常运行了,经调查得知,修好古钟的人是林飞、吴昊、郑川、郭爽四人中的一人。但问到他们时,林飞说:“我没修过古钟。”郑川说:“是吴吴修的。”吴昊说:“是郭爽修的。”郭爽说:“我可没碰过古钟。”如果四个人中只有
下图中的立体图形①是由立体图形②、③和④组合而成,下列哪一项能够填入问号处?
最新回复
(
0
)