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

admin2018-10-14 55

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

选项 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)

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

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

软考高级

甲公司支出20万元购买了某市场预测信息，由于此信息的采纳，甲公司多得到了100万元的利润，对甲公司而言，这个市场预测信息的(35)。

某软件开发团队欲开发一套管理信息系统，在项目初期，用户提出了软件的一些基本功能，但是没有详细定义输入、处理和输出需求。在这种情况下，该团队在开发过程应采用(19)。

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

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

现有污染源无组织排放玻璃棉尘、石英粉尘、矿渣棉尘的监控浓度限值(监控点与参照点浓度差值)是（）mg／m3。

或有负债是指过去的交易或事项形成的潜在义务，其存在须通过未来不确定事项的发生或不发生予以证实，不会涉及现时义务。()

上课时，学生被突然飞进来的小鸟吸引，这种心理现象是()

关于中国的铁路，下列说法错误的是()。

赫尔巴特所代表的传统教育思想的核心一般被概括为：教材中心、课堂中心和()。

计算机软件分为系统软件和应用软件，属于系统软件的是

CiscoPIX525防火墙用来允许数据流从具有较低安全级接口流向较高安全级接口的配置命令是()。

A、5types.B、4percent.C、10gram.D、8meters.AHowmanydifferentmodelsofthiscardoyouoffer?

Thephrase"Americandream"generallyreferstothehopesonehasforhisownwell-beinginAmerica.Itisnotnecessarilyasel