煤气公司想要在某地区高层住宅楼之间铺设煤气管道并与主管道相连，位置如下图所示，结点代表各住宅楼和主管道位置，线上数字代表两节点间距离(单位：百米)。则煤气公司铺设的管道总长最短为( )米。

admin2018-10-14 64

问题煤气公司想要在某地区高层住宅楼之间铺设煤气管道并与主管道相连，位置如下图所示，结点代表各住宅楼和主管道位置，线上数字代表两节点间距离(单位：百米)。则煤气公司铺设的管道总长最短为( )米。

选项 A、1 800
B、2 200
C、2 000
D、2 100

答案B

解析这是一个典型的无向连通图的最小生成树问题(Minimum Spanning Tree)。
算法如下：
  任取一点，例如①，将其纳入已完成部分。点①与其他各点中的最小距离为①⑤=3，从而将边①⑤以及点⑤纳入已完成部分。
  点①、⑤与其他各点②、③、④、⑥这两个集合之间的最短距离为①④=⑤⑥=5，任选其一，比如①④，从而将边①④与点④纳入已完成部分。
  点①、④、⑤与点②、③、⑥两个集合的最短距离为③④=4，从而将边③④与点③纳入已完成部分。
  点①、③、④、⑤与点②、⑥两个集合之间的最短距离为⑤⑥=5，从而将边⑤⑥与点⑥纳入已完成部分。
  点①、③、④、⑤、⑥与点②两个集合之间的最短距离为②⑥=5，从而将边②⑥与点②纳入已完成部分。
  此时，所有6个点都已经接通，其边为AE、AB．AF、FD．CD，总长度为22(百米)．如下图所示：

转载请注明原文地址:https://kaotiyun.com/show/uvFZ777K

本试题收录于：信息系统项目管理师上午综合知识考试题库软考高级分类

信息系统项目管理师上午综合知识考试

软考高级

相关试题推荐

随机试题

最新回复(0)

煤气公司想要在某地区高层住宅楼之间铺设煤气管道并与主管道相连，位置如下图所示，结点代表各住宅楼和主管道位置，线上数字代表两节点间距离(单位：百米)。则煤气公司铺设的管道总长最短为( )米。

信息系统项目管理师上午综合知识考试

软考高级

UML的事物是对模型中最具有代表性的成分的抽象，(2)是模型的静态部分，描述概念或物理元素；(3)用来描述、说明和标注模型的任何元素。

在数据处理应用中，有时需要用多项式函数曲线来拟合一批实际数据。以下图中，(55)体现了三次多项式曲线的特征。

某企业拥有多个应用系统，分别采用不同的语言和平台独立构建而成，企业需要集成来自不同系统的数据，并使用可定制格式的数据频繁地、立即地、可靠地、异步地传输数据。以下集成方式，最能满足这种要求的是(32)。

数字签名的功能不包括(7)。

一般来说，在软件维护过程中，大部分工作是由(49)引起的。在软件维护的实施过程中，为了正确、有效地修改程序，需要经历以下三个步骤：分析和理解程序、修改程序和(50)。(51)的修改不归结为软件的维护工作。

图16-4标出了某地区的运输网：各节点之间的运输能力如表16-10所示(单位：万吨/小时)：从节点①到节点⑥的最大运输能力(流量)可以达到(65)万吨/小时。

进程P1、P2、P3、P4、P5的前趋图如下：若用PV操作控制进程并发执行的过程，则需要设置4个信号量S1、S2、S3和S4，且信号量初值都等于零。下图中a和b应分别填写(50)，c和d应分别填写(51)，e和f应分别填写(52)。

下牙槽神经入

关于卵巢黄体形成与退化，下列哪项叙述不正确：

[2011年，第58题]图4．11-5所示装置中，已知质量m=200kg，弹簧刚度k=100N／cm，则图中各装置的振动周期为()。

施工总承包管理与施工总承包模式的区别包括()。

工程项目年度计划的表格部分包括()。

资金时间价值计算的基本方法可以归结为()。

某企业采用随机模式控制现金的持有量。下列事项中，能够使现金返回线上升的有()。

食品配料清单应按照配料加入量的递增顺序排列。()

有下面程序代码：PrivateSubCommandlSlick()DtrnsignAsintegersign=1a=1：b=2Fork=1To5c=a+sign*ba=b：b=cPrintc；sign=-signNex