首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。 为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(1)公里的公路,这种总公里数最少的改造方案共有(2)个。 (2)
下图标明了六个城市(A~F)之间的公路(每条公路旁标注了其长度公里数)。 为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计(1)公里的公路,这种总公里数最少的改造方案共有(2)个。 (2)
admin
2018-10-14
50
问题
下图标明了六个城市(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
信息系统项目管理师上午综合知识考试
软考高级
相关试题推荐
微内核的操作系统(OS)结构如下图所示,图中①和②分别工作在(51)方式下,与传统的OS结构模式相比,采用微内核的OS结构模式的优点是提高了系统的灵活性、可扩充性,(52)。
企业应用集成是一个战略意义上的方法,它从服务和信息角度将多个信息系统绑定在一起,提供实时交换信息和影响流程的能力。(29)提供企业之间的信息共享能力,(30)在用户使用角度能够对集成系统产生一个“整体”的感觉。
某软件的工作量是20000行,由4人组成的开发小组开发,每个程序员的生产效率是5000行/人年,而每对程序员的沟通成本是250行/人年,则该软件需要开发(39)年。
某工厂仓库有一名保管员,该仓库可存放n箱零件。该工厂生产车间有m名工人,只要仓库空闲,工人将生产好的整箱零件放入仓库,并由保管员登记入库数量;该工厂销售部有k名销售员,只要仓库库存数能满足客户要求,便可提货,并由保管员登记出库数量。规定工人和销售员不能同时
甲厂、乙厂同为生产电冰箱的厂家。甲厂得知乙厂研制出提高电冰箱质量和性能的技术方法后,遂以不正当方式获取了该技术,并加以利用。甲厂侵犯了乙厂的(17)。
在面向对象技术中,一个子类的对象同时又属于父类,它继承了父类的一切属性,这种多态性称为(34)。同一个算子在不同的表达式中可能有不同的操作意义,这种多态性称为(35)。编译程序根据上下文判定算子的操作意义,这称为(36)。
3DES在DES的基础上,使用两个56位的密钥K1和K2,发送方用K1加密,K2解密,再用K1加密。接受方用K1解密,K2加密,再用K1解密,这相当于使用(53)倍于DES的密钥长度的加密效果。
X.509数字证书格式中包含的元素有①证书版本、②证书序列号、③签名算法标识、④证书有效期、⑤证书发行商名字、⑥证书主体名、⑦主体公钥信息和⑧(34)。
进程P1、P2、P3、P4、P5的前趋图如下。若用PV操作控制进程并发执行的过程,则需要相应于进程执行过程设置5个信号量S1、S2、S3、S4和S5,且信号量初值都等于零。下图中a处应填写(50);b和c、d和e处应分别填写(51)
若某计算机系统是由500个元器件构成的串联系统,且每个元器件的失效率均为10-7/h,在不考虑其他因素对可靠性的影响时,该计算机系统的MTBF为______小时。
随机试题
依赖性(dependence)
椎动脉起源于
社会主义道德建设的核心是()
关于转座子的叙述,错误的是
男性30岁,由5m高处跌下2小时。腹痛,腹肌紧张,有压痛和反跳痛,肠鸣音弱。血压104/70mmHg,脉率120次/min。血红蛋白80g/I_.。X线检查:右侧第9、10肋骨骨折,右侧膈肌升高。最可能的诊断是
一休克病人BP70/50mmHg,CVP4cmH2O,P90次/分,正确的诊断与处理是()。
下列属于价值型股票的是()。
下列叙述中正确的是()。
A、 B、 C、 D、 B图片中表现的是一名女子在使用电脑的情景。从圈中我们可以看出她的手正放在键盘上,所以选项(B)typingonakeyboard符合这一场景,是正确答案。如果没有听清选项(D)中
WhichofthefollowingstatementsisNOTtrueaboutlife150yearsago?
最新回复
(
0
)