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

admin2018-10-14 30

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

选项 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://jikaoti.com/ti/w9m7FFFM

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

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

软考高级

相关试题推荐

随机试题

最新回复(0)

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

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

软考高级

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

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

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

Theideaofworkingabroadreally________me,forIhaveneverbeenabroad.

火灾报警控制器不能显示火灾报警控制器已屏蔽设备的类别和地址总数。()

作为糖与脂肪代谢交叉点的物质是

A、靠近抗原孔B、靠近抗体孔C、在两孔之间D、呈多条沉淀线E、不出现沉淀线双扩试验平板法中，若抗原含量较大，则反应沉淀线应

尿路结石成分最多见的是

男，32岁。左上腹被撞伤后钝痛1天，突发腹痛加重3小时。查体：P140次／分，BP60／45mmHg，面色苍白，四肢厥冷，双肺呼吸音清，心率140次／分，上腹中度压痛，肌紧张，移动性浊音(+)。腹腔穿刺抽出不凝血。最可能的诊断是

用重量法测定大气中总悬浮颗粒物的浓度。采样流量为1．2m3／min，连续采样24h，现场气温为15℃，大气压力为98．6kPa，采样前后滤膜增重302mg，则大气中总悬浮颗粒物浓度为()。

Youwillnowreadashortpassageandthenlistentoatalkonthesameacademictopic.Youwillthenbeaskedaquestionabout