2. 计算机
  3. 某省6个城中(A～F)之间的网络通信线路(每条通信线路旁标注厂其长度公里数)如图1-4所示。 如果要将部分千兆通信线路改造成万兆通信线路，以提升各个城市网络之间的通信容量，则至少要改造总计(61)公里的通信线路，这种总公里数最少的改造方案共有(62)

某省6个城中(A～F)之间的网络通信线路(每条通信线路旁标注厂其长度公里数)如图1-4所示。 如果要将部分千兆通信线路改造成万兆通信线路，以提升各个城市网络之间的通信容量，则至少要改造总计(61)公里的通信线路，这种总公里数最少的改造方案共有(62)

admin2010-01-17  60
问题 某省6个城中(A～F)之间的网络通信线路(每条通信线路旁标注厂其长度公里数)如图1-4所示。
   如果要将部分千兆通信线路改造成万兆通信线路，以提升各个城市网络之间的通信容量，则至少要改造总计(61)公里的通信线路，这种总公里数最少的改造方案共有(62)个。

选项 A、1
B、2
C、3
D、4
答案C
解析 从图上看，本题要求得到图1-4的最小支撑树(即选取部分边，使其保持连通，又使其总长度最小)。如下算法可以逐步实现这个要求。
   任取一点，例如A，将其纳入已完成部分。点A与其他各点中的最小距离为AE=200，从而将边AE及点E纳入已完成部分。
   点A、E与其他各点B、C、D、F这两个集合之间的最短距离为AB=AF=300，从而可以将边AB与点B(或边AF与点F)纳入已完成部分。
   点A、B、E与点C、D、F两个集合的最短距离为AF=BF=300，从而可以将边AF(或边BF)与点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，总长度为200×2+300×3=1300，如图1-6所示。
      
   连通这6个点的边至少需要5条，最短总长等于2个200及3个300。图1-4中共有4条边长为300，其中，CD边在最短总长度方案中不可缺少，而AB、BF、AF中可以任选2条。因此，共有3个最短总长度的方案。另两种改造方案分别如图1-7和图1-8所示。
转载请注明原文地址:https://kaotiyun.com/show/9WGZ777K
本试题收录于： 信息系统项目管理师上午综合知识考试题库软考高级分类
0

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

软考高级

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