首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
山区某乡的6个村之间有山路如下图所示,其中的数字标明了各条山路的长度(公里)。 乡政府决定沿山路架设电话线。为实现村村通电话,电话线总长至少为(59)公里。
山区某乡的6个村之间有山路如下图所示,其中的数字标明了各条山路的长度(公里)。 乡政府决定沿山路架设电话线。为实现村村通电话,电话线总长至少为(59)公里。
admin
2018-04-25
28
问题
山区某乡的6个村之间有山路如下图所示,其中的数字标明了各条山路的长度(公里)。
乡政府决定沿山路架设电话线。为实现村村通电话,电话线总长至少为(59)公里。
选项
A、11
B、14
C、18
D、33
答案
B
解析
本题需要在给定的图上寻找最小支撑树。
图由若干个结点以及结点之间的连线组成,每条连线上标记了权数(本题为长度)。
最小支撑树实际上是其中的一个子图,它包括所有的结点以及部分连线,这些连线需要连接所有的结点,但其总权数(长度)最小。
从本题应用看,就是要在上述山路图中确定部分山路,使其能连接6个村,又能使总长度最短。
最小支撑树的求解方法:先选择最短的一条线(如有多条,可以任选一条),它已经连接了2个点。从这2点出发,再找出能连接其他一个点的最短线(如有多条,可以任选一条)。这样,就已经用2条线连接了3个点。依此类推,逐步做下去,连线也逐步增多,连接的点也逐步增多,直到所有的点都连上为止。这样求出的若干条连线以及所有结点就组成了最小支撑树。
本题求出的一种最小支撑树如下:
其连线的总长度等于14公里,连接了6个村。
在同一个图中,最小支撑树的方案可能有多个,但其连线的总长度是相等的。
这是运筹学求解最优问题的普遍原则:最优值如果有,则必是唯一的,但达到最优值的方案可能不止一个。
转载请注明原文地址:https://jikaoti.com/ti/cGJ7FFFM
本试题收录于:
系统分析师上午综合知识考试题库软考高级分类
0
系统分析师上午综合知识考试
软考高级
相关试题推荐
请将工具栏中的“信息检索”工具按钮删除。
在newbook1的工作表1中,将单元格B8的值设置为当前时间。
请添加自定义项目符号中的第4行第2列作为当前文本的项目符号。
请将“huahuan”图片添加为图片项目符号,再应用到当前文本中。
设置D列单元格的日期格式为“年*月*日”不受操作系统设置的影响。
下列叙述中,不属于数据库系统的是()。
OSI参考模型的物理层和数据链路层解决的是()。
人类主要通过()技术,实现了世界范围的信息资源共享,世界变成一个“地球村”。
某公司研发一种语音识别软件系统,需要对用户的语音指令进行音节分割、重音判断、语法分析和语义分析,最终对用户的意图进行推断。针对上述功能需求,该语音识别软件应该采用______架构风格最为合适。
随着软件开发工具的积累与自动化工具的增多,软件开发环境进入了第三代 ICASE(integrated Computer-Aided Software Engineering)阶段。ICASE信息库(repository)不仅定义了面向对象的数据库管理系统,
随机试题
在()图上只画两根负载线,而不画增载线和卸载线。
不属于栀子的炮制规格是
作业层端部脚手板探头长度应取150mm,其板长两端均应与支承杆可靠地固定。()
用于制作切割刀具的钻石(已加工,未安装)()
__________toherself,Brendabegantoweephysterically.
下列各项属于流程式生产的特点的是()。
确定人工费支出极限的方法,不包括()。
甲男与乙女原系出自同一祖父母的堂兄妹,后来乙女为他人收养,依照我国婚姻法的规定,他们()。
有一个数是123,它与十六进制数53相等,那么该数值是
JeffBezosTakingthelongviewA)JeffBezos,thefounderandchiefexecutiveofAmazon,owesmuchofhissuccesstohisability
最新回复
(
0
)