山区某乡的6个村之间有山路如下图所示，其中的数字标明了各条山路的长度(公里)。乡政府决定沿山路架设电话线。为实现村村通电话，电话线总长至少为(59)公里。

admin2018-04-25 40

问题山区某乡的6个村之间有山路如下图所示，其中的数字标明了各条山路的长度(公里)。

乡政府决定沿山路架设电话线。为实现村村通电话，电话线总长至少为(59)公里。

选项 A、11
B、14
C、18
D、33

答案B

解析本题需要在给定的图上寻找最小支撑树。
图由若干个结点以及结点之间的连线组成，每条连线上标记了权数(本题为长度)。
最小支撑树实际上是其中的一个子图，它包括所有的结点以及部分连线，这些连线需要连接所有的结点，但其总权数(长度)最小。
从本题应用看，就是要在上述山路图中确定部分山路，使其能连接6个村，又能使总长度最短。
最小支撑树的求解方法：先选择最短的一条线(如有多条，可以任选一条)，它已经连接了2个点。从这2点出发，再找出能连接其他一个点的最短线(如有多条，可以任选一条)。这样，就已经用2条线连接了3个点。依此类推，逐步做下去，连线也逐步增多，连接的点也逐步增多，直到所有的点都连上为止。这样求出的若干条连线以及所有结点就组成了最小支撑树。
本题求出的一种最小支撑树如下：

其连线的总长度等于14公里，连接了6个村。
在同一个图中，最小支撑树的方案可能有多个，但其连线的总长度是相等的。
这是运筹学求解最优问题的普遍原则：最优值如果有，则必是唯一的，但达到最优值的方案可能不止一个。

转载请注明原文地址:https://kaotiyun.com/show/5CLZ777K

本试题收录于：系统分析师上午综合知识考试题库软考高级分类

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

软考高级

相关试题推荐

随机试题

最新回复(0)

山区某乡的6个村之间有山路如下图所示，其中的数字标明了各条山路的长度(公里)。乡政府决定沿山路架设电话线。为实现村村通电话，电话线总长至少为(59)公里。

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

软考高级

在newbook1的工作表1中，在单元格A3输入“2000年”，利用鼠标左键，在A3：I3区域按年份数字递增顺序进行填充。

请对工作簿Book1设置密码123456，同时对其结构进行保护。

请选定已命名的单元格区域A1B3。

请为上海的销售情况建立趋势线。

为工作表A1：Ⅲ0单元格区域的数据在新工作表中创建数据透视表，并将字段“工资”添加到数据透视表中。

软件设计中，有利于提高模块独立性的一个准则是______。

关系操作的特点是（）操作。

以下程序运行时输出到屏幕的结果中第一行是 (8) ，第二行是(9) ，第三行是(10) 。算法提示:将Fibonacci数列(1，1，2，3，5，8，13，…)前6个数填入a数组。#include#defineN3intmain(){i

数据库的系统设计分为概念结构设计和逻辑结构设计。在概念结构设计时，一般采用 (1) 模型作为描述工具，因为该模型能充分地反映现实世界事物之间的联系，且易于理解和更改。

TCP／IP模型的最低层为()。

侵犯商业秘密行为的种类包括()。

下列属于理论联系实际内容的有

对于土工格栅条带拉伸试验，单筋试样应有足够长度。试样的夹持线在节点处，除被夹钳夹持住的节点或交叉组织外，还应包含至少()排节点或交叉组织。

普通螺栓受剪连接主要有五种破坏形式，即：①螺杆剪断；②孔壁挤压破坏；③构件拉断；④端部钢板剪断；⑤螺杆受弯破坏。试问，在设计时应按下述()组序号进行计算。

根据FIDIC《施工合同条件》，助手在授权范围内向()发出的指示，具有与工程师指示同样的效力。

在我国货币政策间接传导过程中，运用货币政策工具首先影响到的是货币政策的()。

存款利息的计算方法是本金×利息率。（）

VitruvianGymAspartofour10thanniversarycelebration,wearegivingnewmembersthechancetotryoutanyofourfitnesscl

HowmuchdoestheWorldBanksupposetospendinfacingtheagriculturalchallenges?

HighwaysEarlyinthe20thcentury,mostofthestreetandroadsintheU.S.weremadeofdirt,brick,andcedarwoodblocks

山区某乡的6个村之间有山路如下图所示，其中的数字标明了各条山路的长度(公里)。 乡政府决定沿山路架设电话线。为实现村村通电话，电话线总长至少为(59)公里。

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

软考高级

在newbook1的工作表1中，在单元格A3输入“2000年”，利用鼠标左键，在A3：I3区域按年份数字递增顺序进行填充。

请对工作簿Book1设置密码123456，同时对其结构进行保护。

请选定已命名的单元格区域A1B3。

请为上海的销售情况建立趋势线。

为工作表A1：Ⅲ0单元格区域的数据在新工作表中创建数据透视表，并将字段“工资”添加到数据透视表中。

软件设计中，有利于提高模块独立性的一个准则是______。

关系操作的特点是（）操作。

以下程序运行时输出到屏幕的结果中第一行是 (8) ，第二行是(9) ，第三行是(10) 。算法提示:将Fibonacci数列(1，1，2，3，5，8，13，…)前6个数填入a数组。#include#defineN3intmain(){i

数据库的系统设计分为概念结构设计和逻辑结构设计。在概念结构设计时，一般采用 (1) 模型作为描述工具，因为该模型能充分地反映现实世界事物之间的联系，且易于理解和更改。

TCP／IP模型的最低层为()。

侵犯商业秘密行为的种类包括()。

下列属于理论联系实际内容的有

对于土工格栅条带拉伸试验，单筋试样应有足够长度。试样的夹持线在节点处，除被夹钳夹持住的节点或交叉组织外，还应包含至少()排节点或交叉组织。

普通螺栓受剪连接主要有五种破坏形式，即：①螺杆剪断；②孔壁挤压破坏；③构件拉断；④端部钢板剪断；⑤螺杆受弯破坏。试问，在设计时应按下述()组序号进行计算。

根据FIDIC《施工合同条件》，助手在授权范围内向()发出的指示，具有与工程师指示同样的效力。

在我国货币政策间接传导过程中，运用货币政策工具首先影响到的是货币政策的()。

存款利息的计算方法是本金×利息率。（）

VitruvianGymAspartofour10thanniversarycelebration,wearegivingnewmembersthechancetotryoutanyofourfitnesscl

HowmuchdoestheWorldBanksupposetospendinfacingtheagriculturalchallenges?

HighwaysEarlyinthe20thcentury,mostofthestreetandroadsintheU.S.weremadeofdirt,brick,andcedarwoodblocks

山区某乡的6个村之间有山路如下图所示，其中的数字标明了各条山路的长度(公里)。乡政府决定沿山路架设电话线。为实现村村通电话，电话线总长至少为(59)公里。