首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
有8口海上油井,相互间距离如下表所示(单位:海里)。其中1号井离海岸最近,为5海里。现要从海岸经1号井铺设油管将各井连接起来,则铺设输油管道的最短长度为( )海里。
有8口海上油井,相互间距离如下表所示(单位:海里)。其中1号井离海岸最近,为5海里。现要从海岸经1号井铺设油管将各井连接起来,则铺设输油管道的最短长度为( )海里。
admin
2019-08-25
2.2K+
问题
有8口海上油井,相互间距离如下表所示(单位:海里)。其中1号井离海岸最近,为5海里。现要从海岸经1号井铺设油管将各井连接起来,则铺设输油管道的最短长度为( )海里。
选项
A、9.1
B、9.2
C、10.1
D、10.2
答案
D
解析
本题实际是求连通图的最小生成树问题。我们采用Krusckal算法。
第l步,我们在表中找出一个最小值一一0.5,可见是顶点8与顶点7间的连接(简记为8~7),我们把这两个点连起来;
第2步,在表中剩余的连接间再找出一个最小值一一0.6,可见是7~6,把这两个点再连起来。
第3步,在表中剩余的连接之间再找一个最小值一一0.7,可见是5~1、5~4,
把5与1连起来,再把5与4也连起来
。
第4步,在表中剩余的连接间再找出一个最小值一一0.8,可见是8~5,把这两个顶点连起来。
第5步,在表中剩余的连接间再找出一个最小值一一0.9,可见是8~4、4~1、6~5、3~2,
但1、4、5、6、8都已经是在同一颗树中,所以无需连接
,所以仅需把3和2连起来。
第6步,在表中剩余的连接间再找出一个最小值一一1.0,可见是8~3、8~6,
但8与6已经在同一棵树中,
所以仅把8和3连接起来。
至此,所以顶点已经在同一棵树中,这棵树就是最小生成树。我们把所有连接的权值加起来:
0.5+0.6+0.7+0.7+0.8+0.9+1.0=5.2
其中1号油井距离海岸最近,为5海里。因此5.2+5=10.2
转载请注明原文地址:https://kaotiyun.com/show/qbUZ777K
本试题收录于:
信息系统项目管理师上午综合知识考试题库软考高级分类
0
信息系统项目管理师上午综合知识考试
软考高级
相关试题推荐
下列关于面向对象的分析与设计的描述,正确的是(5)。
RIPv2对RIPv1协议的改进之一为路由器必须有选择地将路由表中的信息发送给邻居,而不是发送整个路由表。具体地说,一条路由信息不会被发送给该信息的来源,这种方案称为(65),其作用是(66)。(66)
给定关系模式R<U,F>,U={A,B,C,D,E},F={B→A,D→A,A→E,AC→B},则R的候选关键字为(42),分解ρ={R1(ABCE),R2(CD)}(43)。(42)
OSPF协议把网络划分成4种区域(Area),其中()不接受本地自治系统以外的路由信息,对自治系统以外的目标采用默认路由0.0.0.0。
在多个用户共享数据库时,对同一资料的(6)操作可能破坏数据库的(7)。因此数据库管理机制要解决丢失更新、不一致以及(8)等问题。解决的方法主要有加锁技术和时标技术。在加锁技术中,(9)要求太严,(10)会产生死锁。
原型化方法是用户和设计者之间执行的一种交互过程,适用于(106)系统。它从用户界面设计开始,首先形成(107),用户(108)并就(109)提出意见。它是一种(110)型的设计过程。
某商品的订购量、市场需求、利润情况见表16-6。在三种市场需求概率相等的情况下,订购250台的利润期望值为(50)元,订购(51)台的利润期望值为最大。去年该商品的市场需求情况见表16-7,市场需求100台的概率为(52),根据去年市场需求概率,订购250
信息战略规划报告应由3个主要部分组成:摘要、规划和附录。其中摘要涉及的主题包括信息战略规划所涉及的范围、企业的业务目标和战略重点、信息技术对企业业务的影响、对现有信息环境的评价、推荐的系统战略、推荐的技术战略、推荐的组织战略、推荐的行动计划等,其中系统战略
①至④是风险管理中的4个活动,其恰当的顺序是(1)。风险识别的一个方法是(2)。①选择风险管理工具②研究风险处理方法③风险评估处理结果④风险识别、确认和度量(1)
Projectselectionmethodsinvolvemeasuringvalueorattractivenesstotheprojectownerorsponsorandmayincludeotherorganiz
随机试题
InAfricaweexperienceenormousproblemsofunderdevelopment,illiteracy,massiveinternalandexternaldebts,thepopulatione
构建证券组合的原因是()
求过点P(2,1,3)且与直线垂直相交的直线方程L。
肝郁型月经先后无定期的主要症状不包括
简述犯罪预备的概念和特征。
房地产开发企业甲急欲销售其开发的某住宅区的最后1套别墅,遂打电话向乙、丙、丁发出售房要约,并声明该要约的有效期为1个月。要约发出后第10日,甲与乙签订买卖合同并交付该别墅,乙支付了全部房款,但未办理产权变更登记。第21日,甲与不知情的丙签订买卖合同并办理了
由y=x3,x=2,y=0所围成的图形绕x轴旋转所得的体积为()。
背景资料某公路隧道为单洞双向行驶两车道隧道,全长4279m,最大埋深1049m。隧道净空宽度9.14m,净空高度6.98m,净空面积为56.45m2。该隧道其围岩主要为弱风化硬质页岩,属Ⅳ—Ⅴ级围岩,稳定性较差。根据该隧道的地质条件和开挖断面宽度
施工项目定期的经常性的中间成本分析是()。
新中国成立初期,中国的新民主主义社会的主要经济成分是
最新回复
(
0
)