首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。 为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(1)公里的公路,这种总公里数最少的改造方案共有(2)个。 (2)
下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。 为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(1)公里的公路,这种总公里数最少的改造方案共有(2)个。 (2)
admin
2018-10-14
40
问题
下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。
为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(1)公里的公路,这种总公里数最少的改造方案共有(2)个。
(2)
选项
A、1
B、2
C、3
D、4
答案
C
解析
这是一个典型的无向连通图的最小生成树问题(Minimum Spanning Tree)。
算法如下:
任取一点,例如A,将其纳入已完成部分。点A与其他各点中的最小距离为AE=200.从而将边AE以及点E纳入已完成部分。
点A、E与其他各点B、C、D、F这两个集合之间的最短距离为AB=AF=300,任选其一,比如AB,从而将边AB与点B纳入已完成部分。
点A、B、E与点C、D、F两个集合的最短距离为AF=BF=300,任选其一,比如AF,从而将边AF与点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,如下图所示:
最优方案共有三个,即AB、AF、BF这个等边三角形任选2条边,剩下的两个备选方案是:
转载请注明原文地址:https://kaotiyun.com/show/xvFZ777K
本试题收录于:
信息系统项目管理师上午综合知识考试题库软考高级分类
0
信息系统项目管理师上午综合知识考试
软考高级
相关试题推荐
企业应用集成是一个战略意义上的方法,它从服务和信息角度将多个信息系统绑定在一起,提供实时交换信息和影响流程的能力。(29)提供企业之间的信息共享能力,(30)在用户使用角度能够对集成系统产生一个“整体”的感觉。
某工厂仓库有一名保管员,该仓库可存放n箱零件。该工厂生产车间有m名工人,只要仓库空闲,工人将生产好的整箱零件放入仓库,并由保管员登记入库数量;该工厂销售部有k名销售员,只要仓库库存数能满足客户要求,便可提货,并由保管员登记出库数量。规定工人和销售员不能同时
某工厂仓库有一名保管员,该仓库可存放n箱零件。该工厂生产车间有m名工人,只要仓库空闲,工人将生产好的整箱零件放入仓库,并由保管员登记入库数量;该工厂销售部有k名销售员,只要仓库库存数能满足客户要求,便可提货,并由保管员登记出库数量。规定工人和销售员不能同时
某公司所生产的U盘使用了其品牌产品“移动硬盘”的注册商标,那么,该公司(34)的商标专用权。
某教授1996年3月1日自选将我国《计算机软件保护条例》译成英文,投递给某刊物,于1996年6月1日发表。国家有关机关认为该教授的译文质量很高,经与该教授协商,于1997年2月10日发文将该译文定为官方正式译文。该教授对其译文(19)。
净室软件工程(Cleanroom)是软件开发的一种形式化方法,可以开发较高质量的软件。它使用(91)进行分析和建模,并且将(92)作为发现和排除错误的主要机制。使用(93)测试来获取认证软件可靠性所需要的信息。
操作员甲和乙录入数据错误概率均为1/1000。为了录入一批重要数据,通常采取甲、乙两人分别独立地录入这批数据,然后由程序对录入数据逐个进行比较,对不一致处再与原数据比较后进行修改,这种录入数据的方式,其错误率估计为(57)。
某软件企业2004年初计划投资1000万人民币开发一套中间件产品,预计从2005年开始,年实现产品销售收入1500万元,年市场销售成本1000万元。该产品的系统分析员张工根据财务总监提供的贴现率,制作了如下的产品销售现金流量表16-9。根据表中的数据,该产
假设需要把25盒磁带数据(每盒磁带数据量40GB)从甲地传输到乙地,甲、乙相距1km,可以采用的方法有汽车运输和TCP/IP网络传输,网络传输介质可选用双绞线、单模光纤、多模光纤等。通常情况下,采用(12)介质,所用时间最短。
进程P1、P2、P3、P4、P5的前趋图如下。若用PV操作控制进程并发执行的过程,则需要相应于进程执行过程设置5个信号量S1、S2、S3、S4和S5,且信号量初值都等于零。下图中a处应填写(50);b和c、d和e处应分别填写(51)
随机试题
患者,男,28岁。3天来尿道口红肿,尿急、尿频、尿痛,淋沥不止,尿液混浊如脂,尿道口溢脓,舌红苔黄腻,脉滑数。西医诊断为急性淋病。治疗应首选()
A、湿法制粒压片B、结晶药物直接压片C、干法制粒压片D、粉末直接压片E、空白颗粒压片药物较不稳定,遇湿热分解,可压性、流动性均不太好且量较大
对违约责任者以法律制裁,要求当事人在签定合同时,要考虑( )。
王先生夫妇年龄相差不大,打算购买年金型的保险产品找到理财规划师进行咨询。理财规划师建议他们购买()比较合适。
公司制期货交易所总经理应当由()。
下列风险中,属于业主或投资商风险的有()。
下面关于基础代谢的问题,哪一个说法正确()。
体育能力具有一般能力的特征,又是一种特殊能力,是由个体的()和运动技术及技能所构成的一种身心品质的综合体。
民警在宣传群众工作中会经常采用召开座谈会的方法,这也是公安机关开展群众工作的一个优良传统。民警小李要在社区召开一次座谈会,需要做到的有()。
A、 B、 C、 Cthat是关系代词,先行词是thedocuments“文件”,(C)中的them是指那些文件。
最新回复
(
0
)