首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
有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
信息系统项目管理师上午综合知识考试
软考高级
相关试题推荐
行为型模式是对在不同对象之间划分责任和算法的抽象化,它可以分为类行为模式和对象行为模式。下列行为型模式中属于类行为模式的是()。
某软件公司项目组开发了一套应用软件,其软件著作权人应该是()。
软件测试是为了发现错误而执行程序的过程。检验软件是否满足用户需求的测试称为(1)。(2)是维护中常用的方法,其目的是检验修改所引起的副作用。黑盒测试法主要根据(3)来设计测试用例。(3)
在下列体系结构中,最适合于多个任务并行执行的体系结构是(4)。流水线控制方式下,(5)是全局性相关,流水线机器对全局性相关的处理不包括(6)。静态流水线是指(7)。假设并行(阵列)处理器的16个处理器编号为0—15,采用单级Cube3网络互联时,与13号处
通常,软件开发环境可由环境机制和工具集构成。按功能划分,环境机制又可分为(94);工具集也可分为贯穿整个开发过程的工具和解决软件生命周期中某一阶段问题的工具,分别属于上述两类工具的是(95)。软件开发环境的核心是(96)。软件开发环境具有集成性、开放性、(
面向对象程序设计的基本思想是通过建立和客观实际相对应的对象,并通过这些对象的组合来创建具体的应用。对象是(6)。对象的三要素是指对象的(7)。(8)均属于面向对象的程序设计语言。而面向对象的程序设计语言必须具备(9)特征。Windows下的面向对象程序设计
OMT(Object Modelling Technique)方法的第一步是从问题的陈述入手,构造系统模型。系统模型由对象模型、(14)组成。对象模型是从实际系统导出的类的体系,即类的属性、子类与父类之间的继承关系以及类之间的(15)关系。
用UML建立业务模型是理解企业业务过程的第一步。使用活动图(activitydiagram)可显示业务工作流的步骤、决策点,以及完成每一步骤的角色和对象。它强调______。
数据挖掘就是要智能化和自动化地把数据转换为有用的信息和知识,目前已有多种数据挖掘方法。如果需要一个示例数据库(该库中的每个元组都有一个给定的类标识)做训练集时,该方法称为______。A.特征描述B.分类分析C.聚类分析D.关联规则挖掘
Projectselectionmethodsinvolvemeasuringvalueorattractivenesstotheprojectownerorsponsorandmayincludeotherorganiz
随机试题
垄断资本是怎样利用国家来为其经济利益服务的?
A.妊娠满28周后,胎儿及附属物全部从母体排出B.孕满28周至不满37周娩出者C.孕满42周及以后分娩者D.孕满37周而不满42周分娩者E.孕不满28周,胎儿不足1000g而娩出者
划分委托监理合同包的工作范围时,通常考虑的因素包括( )。
课堂教学、科学研究与社会实践是高校培养合格人才的三个基本途径。()
道德修养与社会实践密切相连。一个人只有在日常生活中,即在与别人、与集体发生的各种关系中,才较清楚地认识到自己的行为哪些是道德的,哪些是不道德的。同样,克服不道德的思想和行为,也只有在社会实践中才能实现。这段文字意在说明()。
根据以下资料,回答下列问题。2017年我国成年国民图书阅读率为59.1%,比上年增加0.3个百分点;报纸阅读率为37.6%,比上年降低2.1个百分点;期刊阅读率为25.3%,比上年增加1个百分点。2017年我国成年
婴儿主要的思维形式是
张教授:莎士比亚名下的戏剧和诗歌,其实不是他写的,而是伊丽莎白一世写的。莎士比亚是个没有受过多少教育的乡下人,而伊丽莎白一世则完全具有完成这些天才作品的知识和教养。李研究员:你的断定是不能成立的。因为如果伊丽莎白写了像《哈姆雷特》这样的名剧的话,她早
READINGPASSAGE1Youshouldspendabout20minutesonQuestions1-13,whicharebasedonReadingPassage1below. Cleaner
A、Wecanonlyovercomedifficultieswithfriends’help.B、Ourbreathingwillbedeepandregular.C、Ourstresslevelswillrise.
最新回复
(
0
)