首页
登录
从业资格
山区某乡的6个村之间有山路如下图所示,其中的数字标明了各条山路(公里)。
山区某乡的6个村之间有山路如下图所示,其中的数字标明了各条山路(公里)。
考试题库
2022-08-02
50
问题
山区某乡的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.弱矩
随机试题
Kissing,strokingandwildembracesarecommonenough,andnowthequiet,ro
Forthispart,youareallowed30minutestowriteashortessayaboutacampus
Youshouldspendabout20minutesonQuestions14-26whicharebasedonReading
PresidentRichardNixonusedtosaythatthefirstcivilrightofeveryAmer
VCT检测后咨询应该注意的有:()A、所有检测结果必须认真核对,妥善保管 B、
患者,女,32岁。素有心悸、心慌。2天前不慎受凉,出现头痛、发热、恶寒、微汗,脉
220kV容量120MVA及以上变压器检测周期为()个月。(A)3(B)6
截至2015年底,中国创业投资各类机构数已达1775家,同比增长14.4%。其中
B
在微波通信系统中,属于馈线系统的是()。A.环形器 B.极化补偿器 C.极化
最新回复
(
0
)