2. 从业资格
  3. 煤气公司想要在某地区高层住宅楼之间铺设煤气管道并与主管道相连，位置如下图所示，节

煤气公司想要在某地区高层住宅楼之间铺设煤气管道并与主管道相连，位置如下图所示，节

免费题库2022-08-02  26
问题 煤气公司想要在某地区高层住宅楼之间铺设煤气管道并与主管道相连，位置如下图所示，节点代表各住宅的楼和主管道位置，线上数字代表两节点间距离（单位：百米），则煤气公司铺设的管道总长最短为 （ ） 米A.1800  B.2200  C.2000 D.2100
选项 A.1800
B.2200
C.2000
D.2100
答案 B
解析 这是一道最小生成树的问题，可以采用克鲁斯卡尔算法。依次寻找连通每个节点之间的最小距离（最小边），如果和已选取的边构成回路，则放弃，选取次小边。技巧是边的选择方案不构成回路，最后连通节点的边的数量为N-1条，N为节点数。题目中，间距最小的是5号楼到1号楼的间距为3，间距次小的是3号楼到4号楼的间距为4；然后是1号楼到4号楼的间距为5，或者4号到5号楼的间距为5；5号楼到6号楼最小间距为5；2号楼到6号楼最小间距为5，结果为3+4+5+5+5=22。所以结果为22×100=2200米。
转载请注明原文地址:https://tihaiku.com/congyezige/2296057.html
本试题收录于： 高级信息系统项目管理师题库软件水平考试初中高级分类

高级信息系统项目管理师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)