首页
登录
从业资格
山区某乡的6个村之间有山路如下图所示,其中的数字标明了各条山路(公里)。
山区某乡的6个村之间有山路如下图所示,其中的数字标明了各条山路(公里)。
考试题库
2022-08-02
85
问题
山区某乡的6个村之间有山路如下图所示,其中的数字标明了各条山路(公里)。
乡政府决定沿山路架设电话线。为实现村村通电话,电话线总长至少为( )公里。A.11B.14C.18D.33
选项
A.11
B.14
C.18
D.33
答案
B
解析
本题需要在给定的图上寻找最小支撑树。图由若干个结点以及结点之间的连线组成,每条连线上标记了权数(本题为长度)。最小支撑树实际上是其中的一个子图,它包括所有的结点以及部分连线,这些连线需要连接所有的结点,但其总权数(长度)最小。从本题应用看,就是要在上述山路图中确定部分山路,使其能连接6个村,又能使总长度最短。最小支撑树的求解方法:先选择最短的一条线(如有多条,可以任选一条),它已经连接了2个点。从这2点出发,再找出能连接其他一个点的最短线(如有多条,可以任选一条)。这样,就已经用2条线连接了3个点。依此类推,逐步做下去,连线也逐步增多,连接的点也逐步增多,直到所有的点都连上为止。这样求出的若干条连线以及所有结点就组成了最小支撑树。本题求出的一种最小支撑树如下:
其连线的总长度等于14公里,连接了6个村。在同一个图中,最小支撑树的方案可能有多个,但其连线的总长度是相等的。这是运筹学求解最优问题的普遍原则:最优值如果有,则必是唯一的,但达到最优值的方案可能不止一个。
转载请注明原文地址:https://tihaiku.com/congyezige/2401748.html
本试题收录于:
高级系统分析师题库软件水平考试初中高级分类
高级系统分析师
软件水平考试初中高级
相关试题推荐
()不属于网络传输系统。A.综合布线系统(PDS) B.同步数字序列(SDH
下图空白处应该是() A.资深监理工程师 B.总监代表 C.技术总
请将下图中空白处进行计算并写出正确答案
下图空白处应该是() A.资深监理工程师 B.总监代表 C.技术总监
下图空白处应该是() A.业主单位 B.公司财务 C.监理 D.项目经
下图是一个传统的()模型示意图。 A.智慧城市 B.云计算 C.大数
下图是RACI图,其中R代表的是() A.对任务负责人 B.参与人物 C
下图是典型的“香蕉”曲线法其中曲线A表示的是() A.最合理时间计划
下图是典型的() A.甘特图 B.鱼刺图 C.帕累托图 D.时标网络图
下图中的项目组织结构属于()。 A.项目型组织 B.职能型组织 C.弱矩
随机试题
•ReadthearticiebelowaboutafinancialplanOftheIMF。•Inmostof
Partsofthefollowingtextaremissing.Whilelisteningtothetape,comple
HowtoWriteaBookReviewⅠ.ThedefinitionofabookreviewA
[originaltext]M:Honey,thebasketballgameisabouttostartAndcouldyoubri
金融租赁公司设立的境内专业子公司,注册资本最低限额为()万元人民币或等值的可
提出假设常用的方式主要有两种:______和______。
党的十八大以来,国务院确定的全国第一个生态文明的先行示范区是( )。A.海南
下列场所,宜选用全淹没应用方式的开式细水雾灭火系统的是( )。A.油浸变压器室
进度计划的调整措施包括()。A.增加资源投入 B.消除时差 C.赶工
可补充中枢中正常的神经递质的抗帕金森药是A、溴隐亭 B、司来吉兰 C、左旋多
最新回复
(
0
)