2. 计算机
  3. 某乡8个小村(编号为1～8)之间的距离如下表(单位：km)。1号村离水库最近，为5km，从水库开始铺设水管将各村连接起来，最少需要铺设________长的水管(为便于管理和维修，水管分叉必须设在各村处)。

某乡8个小村(编号为1～8)之间的距离如下表(单位：km)。1号村离水库最近，为5km，从水库开始铺设水管将各村连接起来，最少需要铺设________长的水管(为便于管理和维修，水管分叉必须设在各村处)。

admin2023-02-21  61
问题 某乡8个小村(编号为1～8)之间的距离如下表(单位：km)。1号村离水库最近，为5km，从水库开始铺设水管将各村连接起来，最少需要铺设________长的水管(为便于管理和维修，水管分叉必须设在各村处)。
选项 A、6．3km
B、11．3km
C、11．8km
D、16．8km
答案B
解析 本题考查应用数学一运筹学-图论应用的基础知识。为解决这类问题，可以按最短距离逐村铺设水管进行连接。
从水库到①村先铺设水管，距离为5km。
离①村最近的④村距离为1km，因此铺设水管①-④。
离①、④村最近的为⑧村，④-⑧距离为1km，因此铺设水管④-⑧。
离①、④、⑧村最近的为⑦村，⑦-⑧距离为O．5km，因此铺设水管⑧-⑦。
离①、④、⑦、⑧村最近的为⑥村，⑦-⑥距离为O．8km，因此铺设水管⑦-⑥。
②、③、⑤村中，离①、④、⑥、⑦、⑥村最近的为③村，⑧-③距离为1km，因此铺设水管⑧-③。
②、⑤村中，离①、③、④、⑥、⑦、⑧村最近的为②村，③-②距离为1km，因此铺设水管③-②。
⑤村离①、②、③、④、⑥、⑦、⑧村最近的为②村，②-⑤距离为1km，因此铺设水管②-⑤。至此，所有8村均已与水库连接，如下图：

因此，从水库开始连接各村水管的最小总长度为：5+5×1+0．5+0．8=11．3km。
这种解决方法，虽然连接方式可能不唯一，但最小总长度是确定的。
转载请注明原文地址:https://kaotiyun.com/show/K10D777K
本试题收录于： 系统分析师上午综合知识考试题库软考高级分类
0

系统分析师上午综合知识考试

软考高级

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