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

admin2018-04-25 31

问题山区某乡的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)公里。

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

软考高级

利用菜单，给单元格A1添加底纹和图案。

获得“工具”菜单的“选项”对话框的帮助信息。

请利用编辑栏插入函数。

请为演示文稿添加自定义数字签名，名称为“tianyu”，目的为“加密”。

数据库系统的核心是()。

软件工程的出现是由于()。

数据库、数据库系统和数据库管理系统之间的关系是()。

程序改错【题目】以下程序的功能是:求1000000以内的所有平方回文数｡平方回文数是指该整数为某一整数的平方，且该整数的各位数字呈中心对称｡正确程序的输出结果如下:1000000以内的平方回文数为:12148467610201123211464140

某流水线浮点加法器分为5级，若每1级所需要的时间分别是6ns，7ns，8ns，9ns和　6ns，则此流水线的最大加速比为(1)。若每级的时间均为7ns，则．最大加速比为(2)。

肾病综合征病人应用环磷酰胺最严重的不良反应是

下列对市场调节理解不正确的是()

根据《担保法》的规定，(　　)抵押人可以自行决定用于抵押。

支气管哮喘发作的患者采取端坐位属于()。

下列属于人体免疫器官的有()。

下列物理常识说法不正确的是：

Everycountrywithamonetarysystemofitsownhastohavesomekindofmarketinwhichdealersinbills,notes,andotherform

Wecankeepthebooks______amonth.

Everyyeartelevisionstationsreceivehundredsofcomplaintsabouttheloudnessofadvertisements.However,federalrulesforbi

Educationisoneofthekeywordsofourtime.Amanwithoutaneducation,manyofusbelieve,isanunfortunatevictimofadver

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

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

软考高级

利用菜单，给单元格A1添加底纹和图案。

获得“工具”菜单的“选项”对话框的帮助信息。

请利用编辑栏插入函数。

请为演示文稿添加自定义数字签名，名称为“tianyu”，目的为“加密”。

数据库系统的核心是()。

软件工程的出现是由于()。

数据库、数据库系统和数据库管理系统之间的关系是()。

程序改错【题目】以下程序的功能是:求1000000以内的所有平方回文数｡平方回文数是指该整数为某一整数的平方，且该整数的各位数字呈中心对称｡正确程序的输出结果如下:1000000以内的平方回文数为:12148467610201123211464140

某流水线浮点加法器分为5级，若每1级所需要的时间分别是6ns，7ns，8ns，9ns和 6ns，则此流水线的最大加速比为(1)。若每级的时间均为7ns，则．最大加速比为(2)。

肾病综合征病人应用环磷酰胺最严重的不良反应是

下列对市场调节理解不正确的是()

根据《担保法》的规定，( )抵押人可以自行决定用于抵押。

支气管哮喘发作的患者采取端坐位属于()。

下列属于人体免疫器官的有()。

下列物理常识说法不正确的是：

Everycountrywithamonetarysystemofitsownhastohavesomekindofmarketinwhichdealersinbills,notes,andotherform

Wecankeepthebooks______amonth.

Everyyeartelevisionstationsreceivehundredsofcomplaintsabouttheloudnessofadvertisements.However,federalrulesforbi

Educationisoneofthekeywordsofourtime.Amanwithoutaneducation,manyofusbelieve,isanunfortunatevictimofadver

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

某流水线浮点加法器分为5级，若每1级所需要的时间分别是6ns，7ns，8ns，9ns和　6ns，则此流水线的最大加速比为(1)。若每级的时间均为7ns，则．最大加速比为(2)。

根据《担保法》的规定，(　　)抵押人可以自行决定用于抵押。