首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
有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
信息系统项目管理师上午综合知识考试
软考高级
相关试题推荐
在一个单CPU的计算机系统中,采用可剥夺式(也称抢占式)优先级的进程调度方案,且所有任务可以并行使用I/O设备。下表列出了三个任务T1、T2、T3的优先级、独立运行时占用CPU和I/O设备的时间。如果操作系统的开销忽略不计,这三个任务从同时启动到全部结束的
系统设计是根据系统分析的结果,完成系统的构建过程。系统设计的主要内容包括(27);系统总体结构设计的主要任务是将系统的功能需求分配给软件模块,确定每个模块的功能和调用关系,形成软件的(28)。(27)
IDEF(IntegrationDefinitionMethod,集成定义方法)是一系列建模、分析和仿真方法的统称,每套方法都是通过建模来获得某种特定类型的信息。其中,IDEF0可以进行(24)建模;IDEF1可以进行(25)建模;(26)可以进行面向
数据库概念结构设计阶段的工作步骤依次为()。
在下面所列举的逻辑测试覆盖中,测试覆盖最强的是(38),最弱的是(39)。软件测试工具有多种,其中(40)对源程序的数据流和控制流进行分析,发现语义错误:(41)通过对程序的执行流进行探测,检查有关变量的逻辑值。在下面的个人所得税程序中满足
软件方法学是以软件方法为研究对象的学科。从开发风范上看,可分为(99)。从性质上看,可分为(100)。从适应范围来看,可分为(101)。形式方法的目的是把软件作为数学来重新发现。形式方法被用来避免系统中的(102)、不一致性。软件自动化方法是指利用计算机使
价值工程是许多企业采用的一种管理方法。价值工程的目标是(41),价值工程中产品价值的含义是(42),而价值工程的核心是(43)。某工厂生产一种产品,主要零部件有6个,现在成本为2000元。用相对值的功能评价法,列出产品价值分析如表16-5所示。现打算把该
基准程序是目前公认的性能测试的较好方法。TPC基准程序是由(2)开发的基准测试程序。目前使用较多的TPC基准测试程序规范是(3)和工(4)前者测试对象是联机订货系统,测试结果以每分钟事务处理量(TPM)来衡量后者主要用来表示联机事务处理中数据库和硬件的性能
软件测试通常可分为单元测试、集成测试、确认测试和系统测试,其中确认测试主要用于发现(44)阶段的错误。在集成测试时,通常可采用自顶向下增殖式集成和自底向上增殖式集成。在自底向上增殖式集成时,对每个被集成的模块(45)。对那些为众多用户开发的软件(如操作系统
根据《软件文档管理指南GB/T16680—1996》,文档策略是有上级(资深)管理者准备并支持的,对下级开发单位或开发人员提供指导。支持有效文档策略的基本条件中不包括(51)。
随机试题
Idon’tthinkit’snecessaryforustodiscussthisquestionanyfurther.()
计算机网络中为了防止黑客攻击服务器所采用的关键技术是_______技术。
胆囊无痛性肿大伴黄疸,见于()
为一位急性肺栓塞的患者进行身体评估,可获得的体征有
肘横纹(平肘尖)至腕掌(背)侧横纹的骨度分寸是
香港特别行政区的下列哪一项职务可由特区非永久性居民担任?(2008年试卷一第16题)
工业安装工程的特征是有()。
颜色为黄色的地面标志包括()。
关于转让旧房及建筑物土地增值税扣除项目的税务处理,下列说法正确的是()。
教育现代化的核心是()。
最新回复
(
0
)