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

admin2018-10-14 48

问题下图标明了六个城市(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://www.kaotiyun.com/show/xvFZ777K

本试题收录于：信息系统项目管理师上午综合知识考试题库软考高级分类

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

软考高级

相关试题推荐

随机试题

最新回复(0)

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

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

软考高级

微内核的操作系统(OS)结构如下图所示，图中①和②分别工作在(51)方式下，与传统的OS结构模式相比，采用微内核的OS结构模式的优点是提高了系统的灵活性、可扩充性，(52)。

甲公司支出20万元购买了某市场预测信息，由于此信息的采纳，甲公司多得到了100万元的利润，对甲公司而言，这个市场预测信息的(35)。

根据图10-5所示的UML类图可知，类Car和类Boat中的move()方法(59)。

某市标准化行政主管部门制定并发布的工业产品安全的地方标准，在其行政区域内是(21)。

一般来说，在软件维护过程中，大部分工作是由(49)引起的。在软件维护的实施过程中，为了正确、有效地修改程序，需要经历以下三个步骤：分析和理解程序、修改程序和(50)。(51)的修改不归结为软件的维护工作。

一般来说，在软件维护过程中，大部分工作是由(49)引起的。在软件维护的实施过程中，为了正确、有效地修改程序，需要经历以下三个步骤：分析和理解程序、修改程序和(50)。(51)的修改不归结为软件的维护工作。

若某计算机系统是由500个元器件构成的串联系统，且每个元器件的失效率均为10-7/h，在不考虑其他因素对可靠性的影响时，该计算机系统的MTBF为______小时。

()需要个体或组织在精神和心理上得到调整，达到新的平衡方能解决。

根据企业所得税法律制度的规定，企业发生的下列支出中，在计算应纳税所得额时准予扣除的是()。

关于金融负债的初始计量，下列说法中错误的是()。

以美国教育家杜威为代表的现代教育学流派倡导的“三中心”是()。

假如政府希望通过改变汇率来减少贸易逆差，那应采取什么样的货币政策?(2013年中南大学965西方经济学)

有如下程序：#includeusingnamespacestd；classObj{staticinti；public：Obj(){i++；}一Obj(){i一一；}staticintgetVal(){retumi；}}

下列关于函数参数的叙述中，错误的是

Herearethethreemostcommonmistakeslanguagelearnersmake—andhowtocorrectthem.RigidthinkingLinguistshavefound

UniversitiesBranchOutA)Asneverbeforeintheirlonghistory,universitieshavebecomeinstrumentsofnationalcompetitionas

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

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

软考高级

微内核的操作系统(OS)结构如下图所示，图中①和②分别工作在(51)方式下，与传统的OS结构模式相比，采用微内核的OS结构模式的优点是提高了系统的灵活性、可扩充性，(52)。

甲公司支出20万元购买了某市场预测信息，由于此信息的采纳，甲公司多得到了100万元的利润，对甲公司而言，这个市场预测信息的(35)。

根据图10-5所示的UML类图可知，类Car和类Boat中的move()方法(59)。

某市标准化行政主管部门制定并发布的工业产品安全的地方标准，在其行政区域内是(21)。

一般来说，在软件维护过程中，大部分工作是由(49)引起的。在软件维护的实施过程中，为了正确、有效地修改程序，需要经历以下三个步骤：分析和理解程序、修改程序和(50)。(51)的修改不归结为软件的维护工作。

一般来说，在软件维护过程中，大部分工作是由(49)引起的。在软件维护的实施过程中，为了正确、有效地修改程序，需要经历以下三个步骤：分析和理解程序、修改程序和(50)。(51)的修改不归结为软件的维护工作。

若某计算机系统是由500个元器件构成的串联系统，且每个元器件的失效率均为10-7/h，在不考虑其他因素对可靠性的影响时，该计算机系统的MTBF为______小时。

()需要个体或组织在精神和心理上得到调整，达到新的平衡方能解决。

根据企业所得税法律制度的规定，企业发生的下列支出中，在计算应纳税所得额时准予扣除的是()。

关于金融负债的初始计量，下列说法中错误的是()。

以美国教育家杜威为代表的现代教育学流派倡导的“三中心”是()。

假如政府希望通过改变汇率来减少贸易逆差，那应采取什么样的货币政策?(2013年中南大学965西方经济学)

有如下程序：#includeusingnamespacestd；classObj{staticinti；public：Obj(){i++；}一Obj(){i一一；}staticintgetVal(){retumi；}}

下列关于函数参数的叙述中，错误的是

Herearethethreemostcommonmistakeslanguagelearnersmake—andhowtocorrectthem.RigidthinkingLinguistshavefound

UniversitiesBranchOutA)Asneverbeforeintheirlonghistory,universitieshavebecomeinstrumentsofnationalcompetitionas

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