某货车运输公司有一个中央仓库和n个运输目的地，每天要从中央仓库将货物运输到所有运输目的地，到达每个运输目的地一次且仅一次，最后回到中央仓库。在两个地点i和i之间运输货物存在费用Cij，为求解旅行费用总和最小的运输路径，设计如下算法：首先选择离中央仓库最近的

admin2019-07-12 18

问题某货车运输公司有一个中央仓库和n个运输目的地，每天要从中央仓库将货物运输到所有运输目的地，到达每个运输目的地一次且仅一次，最后回到中央仓库。在两个地点i和i之间运输货物存在费用C_ij，为求解旅行费用总和最小的运输路径，设计如下算法：首先选择离中央仓库最近的运输目的地l，然后选择离运输目的地l最近的运输目的地2，……，每次在来访问过的运输目的地中选择离当前运输目的地最近的运输目的地，最后回到中央仓库。则该算法采用了(63)算法设计策略，其时间复杂度为(64)。
(64)

选项 A、Θ(n²)
B、Θ(n)
C、Θ(nlgn)
D、Θ(1)

答案A

解析贪心算法不考虑整体情况，以当前情况为基础作出最优选择。很明显，题目中用到的是贪心算法。分值算法是将规模为n的问题分解为k个子问题，这些子问题相互独立，且与原问题相同，然后将子问题的解合并得到原问题的解。动态规划算法与分值算法类似，但分解后的子问题往往不是独立的。回溯法要在包含问题的所有解的解空间中，按照深度优先的策略，从根节点出发搜索解空间。
在选择路径时，首先选择离中央仓库最近的运输目的地1，需要将所有n个目的地到中央仓库的距离进行比较，选择最近的作为目的地1，相当于从n个数中选择一个最小数，此时比较了

转载请注明原文地址:https://kaotiyun.com/show/ybCZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

软件设计师上午基础知识考试

软考中级

如下图所示，若路由器C的e0端口状态为down，则当主机A向主机C发送数据时，路由器C发送____________。

地址192．168．37．192／25是(1)，地址172．17．17．255／23是(2)。(1)

在Windows系统中，默认权限最低的用户组是____________。

下面关于ManChester编码的叙述中，错误的是______。

下面消除交换机上MAC地址漂移告警的方法中，描述正确的是_____________。①人工把发生漂移的接口shutdown②在接口上配置error-down，自动down掉漂移的端口③在接口上配置quit-vlan，使发生漂移的接口指定VLAN域内退

下图是一个软件项目的活动图，其中顶点表示项目里程碑，边表示包含的活动，边上的权重表示活动的持续时间，则里程碑__________在关键路径上。(2011年上半年试题)

100BASE-T4采用的编码技术为886T，利用_____________传输介质进行数据传输。

某公司用三台Web服务器维护相同的Web信息，并共享同一域名。在Windows的　DNS服务器中通过(36)操作，可以确保域名解析并实现负载均衡。

在IPSec-manual方式下，双方配置好后，仍然无法相互通信。同时若打开debugcryptopacket，则会出现以下信息：rec’dIPSECpacketfromIPADDRtoIPADDRdoesnotagreewith

如何理解无因管理之债的效力?(清华大学2009年研究生入学考试题“简述无因管理的适当管理及法律效果”)

一根已设计好的预应力混凝土轴心受拉构件，现将张拉控制应力提高10%(仍未超过张拉控制应力的上好值)，下面结论正确的是(　　)。

技术分析假说认为，即使没有外部因素影响，股票价格也可以改变原来的运动方向。(　　)

(2013年真题)小海家长给刘老师送贵礼，托其给小海换座位，刘老师收礼并换了座，其做法()。

“加法交换律”(某教科书四年级下册第3单元)的探究教学片段。教师：今天我们将像数学家一样，进行一次数学探究。老师首先给出如下四个算式请学生计算并观察。40+5656+4078+3535+78学

做好班主任工作的前提和基础是()。

雾霾的形成，因素很多，是个长期积累的过程。治理雾霾也不是________的，而是要打持久战，久久为功。填入画横线部分最恰当的一项是()。

3，5，16，82，1315，()

A_________personisonewhomyoutrust,butwhoharmsyousecretly.

ItisnotunusualforChinesechildrentogetmoneyfromtheirparents,grandparentsorrelativesduringtheSpringFestival.Th

软件设计师上午基础知识考试

软考中级

如下图所示，若路由器C的e0端口状态为down，则当主机A向主机C发送数据时，路由器C发送____________。

地址192．168．37．192／25是(1)，地址172．17．17．255／23是(2)。(1)

在Windows系统中，默认权限最低的用户组是____________。

下面关于ManChester编码的叙述中，错误的是______。

下面消除交换机上MAC地址漂移告警的方法中，描述正确的是_____________。①人工把发生漂移的接口shutdown②在接口上配置error-down，自动down掉漂移的端口③在接口上配置quit-vlan，使发生漂移的接口指定VLAN域内退

下图是一个软件项目的活动图，其中顶点表示项目里程碑，边表示包含的活动，边上的权重表示活动的持续时间，则里程碑__________在关键路径上。(2011年上半年试题)

100BASE-T4采用的编码技术为886T，利用_____________传输介质进行数据传输。

某公司用三台Web服务器维护相同的Web信息，并共享同一域名。在Windows的 DNS服务器中通过(36)操作，可以确保域名解析并实现负载均衡。

在IPSec-manual方式下，双方配置好后，仍然无法相互通信。同时若打开debugcryptopacket，则会出现以下信息：rec’dIPSECpacketfromIPADDRtoIPADDRdoesnotagreewith

如何理解无因管理之债的效力?(清华大学2009年研究生入学考试题“简述无因管理的适当管理及法律效果”)

一根已设计好的预应力混凝土轴心受拉构件，现将张拉控制应力提高10%(仍未超过张拉控制应力的上好值)，下面结论正确的是( )。

技术分析假说认为，即使没有外部因素影响，股票价格也可以改变原来的运动方向。( )

(2013年真题)小海家长给刘老师送贵礼，托其给小海换座位，刘老师收礼并换了座，其做法()。

“加法交换律”(某教科书四年级下册第3单元)的探究教学片段。教师：今天我们将像数学家一样，进行一次数学探究。老师首先给出如下四个算式请学生计算并观察。40+5656+4078+3535+78学

做好班主任工作的前提和基础是()。

雾霾的形成，因素很多，是个长期积累的过程。治理雾霾也不是________的，而是要打持久战，久久为功。填入画横线部分最恰当的一项是()。

3，5，16，82，1315，()

A_________personisonewhomyoutrust,butwhoharmsyousecretly.

ItisnotunusualforChinesechildrentogetmoneyfromtheirparents,grandparentsorrelativesduringtheSpringFestival.Th

某公司用三台Web服务器维护相同的Web信息，并共享同一域名。在Windows的　DNS服务器中通过(36)操作，可以确保域名解析并实现负载均衡。

一根已设计好的预应力混凝土轴心受拉构件，现将张拉控制应力提高10%(仍未超过张拉控制应力的上好值)，下面结论正确的是(　　)。

技术分析假说认为，即使没有外部因素影响，股票价格也可以改变原来的运动方向。(　　)