首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(66)公里的公路,这种总公里数最少的改造方案共有(67)个。
下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(66)公里的公路,这种总公里数最少的改造方案共有(67)个。
admin
2009-03-25
80
问题
下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(66)公里的公路,这种总公里数最少的改造方案共有(67)个。
选项
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/T9GZ777K
本试题收录于:
信息系统项目管理师上午综合知识考试题库软考高级分类
0
信息系统项目管理师上午综合知识考试
软考高级
相关试题推荐
Computerprogramsthatarebasedonhumanlogicbyusing"if/then"statementsandinferenceenginesarecalled______.
Thetrustedcomputingbase(TCB)ensuressecuritywithinasystemwhenaprocessinonedomainmustaccessanotherdomaininord
YouplantoinstallWindows2000Serveron10newcomputers.Theseserverswillprovidefileandprintservicesinbranchoffice
下列哪个程序是为供应商设计,使其生产可兼容硬件?A、CCXB、CompatibilityProgramC、CCAD、CiscoClientPortabilityProgram
用无线网络管理,什么设备用于同时追踪多台设备?A、WCSB、WCS导航器C、定位设备D、非法AP探测器
客户端流量被发送到目的地之前,经隧道返回到锚点控制器,这一过程称为什么?A、对称隧道B、非对称隧道C、锚点漫游D、2层漫游
哪3种方法需要IP地址?(选择所有正确答案)A、利用控制台电缆和控制台端口对其进行控制B、若有IP地址则可远程登录到其上C、若有IP地址则可对其进行Web浏览D、若有IP地址则可运用SSH接人
(1)2017年5月12日,新型“蠕虫”勒索病毒WannaCry在全球大规模爆发。这是一起利用NSA黑客武器库泄露的“永恒之蓝”发起的病毒攻击事件。国内连接校园网的电脑以及部分企业中了该病毒,造成许多高校毕业生的论文以及企业单位的文档被锁,需要支付高额赎金
由于业务发展的需要,甲公司IT部门计划建立起一套对IT服务管理流程进行持续性改进的机制,IT部门通过对企业远景、业界最佳经验以及对现状的评估和回顾,对现有流程的差距进行分析,找出差距后,通过考虑风险、问题和机会,对整体的流程改进方向和目的进行策划。以提高服
根据战略规划的一般理论,IT战略规划始于对信息技术内外部环境(现状)的分析,其终极任务是()。
随机试题
简述热月政变的原因及其性质。(南京大学2003年世界史真题)
以________的性质为标准对税收进行分类是世界各国普遍采用的分类方式,也是各国税收分类中最基本、最重要的方式。
关于CT图像后处理的叙述,不正确的是
既能芳香化湿,又可理气安胎的药物是
A.戒毒治疗药品B.戒毒辅助药品C.第三类戒毒药D.化妆品E.保健品
【案情】2010年10月2日午夜,A市某区公安人员在辖区内巡逻时,发现路边停靠的一辆轿车内坐着三个年轻人(朱某、尤某、何某)形迹可疑,即上前盘查。经查,在该车后备厢中发现盗窃机动车工具,遂将三人带回区公安分局进一步审查。案件侦查终结后,区检察院向
专业报关企业必须是具有境内法人地位的经济实体,通常称为独立法人。()
互斥投资方案的选优决策中,一般适宜采用()作为决策依据。
WhendidKoizumidissolvetheHouseofRepresentatives?
Drunkendriving—sometimescalledAmerican’ssociallyacceptedformofmurder—hasbecomeanational【C1】______Everyhourof
最新回复
(
0
)