2. 计算机
  3. 有8口海上油井，相互间距离如下表所示(单位：海里)。其中1号井离海岸最近，为5海里。现要从海岸经1号井铺设油管将各井连接起来，则铺设输油管道的最短长度为( )海里。

有8口海上油井，相互间距离如下表所示(单位：海里)。其中1号井离海岸最近，为5海里。现要从海岸经1号井铺设油管将各井连接起来，则铺设输油管道的最短长度为( )海里。

admin2019-08-25  2.3K+
问题 有8口海上油井，相互间距离如下表所示(单位：海里)。其中1号井离海岸最近，为5海里。现要从海岸经1号井铺设油管将各井连接起来，则铺设输油管道的最短长度为(        )海里。
   
选项 A、9．1
B、9．2
C、10．1
D、10．2
答案D
解析 本题实际是求连通图的最小生成树问题。我们采用Krusckal算法。
    第l步，我们在表中找出一个最小值一一0．5，可见是顶点8与顶点7间的连接(简记为8～7)，我们把这两个点连起来；
    第2步，在表中剩余的连接间再找出一个最小值一一0．6，可见是7～6，把这两个点再连起来。
    第3步，在表中剩余的连接之间再找一个最小值一一0．7，可见是5～1、5～4，把5与1连起来，再把5与4也连起来。
    第4步，在表中剩余的连接间再找出一个最小值一一0．8，可见是8～5，把这两个顶点连起来。
    第5步，在表中剩余的连接间再找出一个最小值一一0．9，可见是8～4、4～1、6～5、3～2，但1、4、5、6、8都已经是在同一颗树中，所以无需连接，所以仅需把3和2连起来。
    第6步，在表中剩余的连接间再找出一个最小值一一1．0，可见是8～3、8～6，但8与6已经在同一棵树中，所以仅把8和3连接起来。
    至此，所以顶点已经在同一棵树中，这棵树就是最小生成树。我们把所有连接的权值加起来：
    0．5+0．6+0．7+0．7+0．8+0．9+1．0=5．2
    其中1号油井距离海岸最近，为5海里。因此5．2+5=10．2
转载请注明原文地址:https://kaotiyun.com/show/qbUZ777K
本试题收录于： 信息系统项目管理师上午综合知识考试题库软考高级分类
0

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

软考高级

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