2. 计算机
  3. 下图标明了六个城市(A～F)之间的公路(每条公路旁标注了其长度公里数)。 为将部分公路改造成高速公路，使各个城市之间均可通过高速公路通达，至少要改造总计(1)公里的公路，这种总公里数最少的改造方案共有(2)个。 (2)

下图标明了六个城市(A～F)之间的公路(每条公路旁标注了其长度公里数)。 为将部分公路改造成高速公路，使各个城市之间均可通过高速公路通达，至少要改造总计(1)公里的公路，这种总公里数最少的改造方案共有(2)个。 (2)

admin2018-10-14  25
问题 下图标明了六个城市(A～F)之间的公路(每条公路旁标注了其长度公里数)。

    为将部分公路改造成高速公路，使各个城市之间均可通过高速公路通达，至少要改造总计(1)公里的公路，这种总公里数最少的改造方案共有(2)个。
(2)
选项 A、1
B、2
C、3
D、4
答案C
解析 这是一个典型的无向连通图的最小生成树问题(Minimum Spanning Tree)。
算法如下：
  任取一点，例如A，将其纳入已完成部分。点A与其他各点中的最小距离为AE=200．从而将边AE以及点E纳入已完成部分。
点A、E与其他各点B、C、D、F这两个集合之间的最短距离为AB=AF=300，任选其一，比如AB，从而将边AB与点B纳入已完成部分。
点A、B、E与点C、D、F两个集合的最短距离为AF=BF=300，任选其一，比如AF，从而将边AF与点F纳入已完成部分。
点A、B、E、F与点C、D两个集合之间的最短距离为FD=200，从而将边FD与点D纳入已完成部分。
点A、B、E、F、D与点C两个集合之间的最短距离为CD=300，从而将边CD与点C纳入已完成部分。
此时，所有6个点都已经接通，其边为AE、AB、AF、FD、cD，总长度为1300，如下图所示：

最优方案共有三个，即AB、AF、BF这个等边三角形任选2条边，剩下的两个备选方案是：
转载请注明原文地址:https://kaotiyun.com/show/xvFZ777K
本试题收录于： 信息系统项目管理师上午综合知识考试题库软考高级分类
0

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

软考高级

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