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

admin2019-07-12 19

问题某货车运输公司有一个中央仓库和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://jikaoti.com/ti/lrG7FFFM

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

在进行进度安排时，PERT图不能清晰地描述(1)，但可以给出哪些任务完成后才能开始另一任务。某项目X包含任务A、B、…、J，其PERT如下图所示(A=1表示该任务A的持续时间是1天)，则项目X的关键路路径是(2)。(2013年上半年试题)(2)

下面的光纤以太网标准中，支持1000m以上传输距离的是____________。

假设网络的生产管理系统采用B／S工作方式，经常上网的用户数为100个，每个用户每分钟平均产生11个事务，平均事务量大小为0．06MB，则这个系统需要的信息传输速率为(34)。

不同VLAN的数据帧必须通过__________传输。

利用______可以对软件的技术信息、经营信息提供保护。

在Linux操作系统中，存放有主机名及对应IP地址的文件是__________。(2008年下半年试题)

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

IEEE802．11采用了类似于802．3CSMMCD协议的CSMA／CA协议，之所以不采用CSMA／CD协议的原因是__________。(2011年下半年试题)

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

胎儿体内含氧量最低的器官是（）

不受气候影响的地下水是()。

按照《建设工程施工合同文本》通用条款规定，工程具备隐蔽条件后，施工单位进行自检，并在隐蔽前()以书面形式通知监理工程师验收。

下列哪些行为属于走私行为?()

孔子倡导的六艺是“礼、乐、射、御、诗、数”。()

为了使加盟供应链的企业都能受益，并且要使每个企业都有比竞争对手更强的竞争实力，就必须加强对供应链的构成及运作研究，由此形成的新的经营与运作模式是()。

课程评价过程中要经历把焦点集中在所研究的课程对象、（）等步骤。

HowtoBeanExpertI.BackgroundinformationaboutthespeakerA.BeinganexpertinanthropologyhimselfB.Startingconsider

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

软考中级

在进行进度安排时，PERT图不能清晰地描述(1)，但可以给出哪些任务完成后才能开始另一任务。某项目X包含任务A、B、…、J，其PERT如下图所示(A=1表示该任务A的持续时间是1天)，则项目X的关键路路径是(2)。(2013年上半年试题)(2)

下面的光纤以太网标准中，支持1000m以上传输距离的是____________。

假设网络的生产管理系统采用B／S工作方式，经常上网的用户数为100个，每个用户每分钟平均产生11个事务，平均事务量大小为0．06MB，则这个系统需要的信息传输速率为(34)。

不同VLAN的数据帧必须通过__________传输。

利用______可以对软件的技术信息、经营信息提供保护。

在Linux操作系统中，存放有主机名及对应IP地址的文件是__________。(2008年下半年试题)

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

IEEE802．11采用了类似于802．3CSMMCD协议的CSMA／CA协议，之所以不采用CSMA／CD协议的原因是__________。(2011年下半年试题)

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

胎儿体内含氧量最低的器官是（）

不受气候影响的地下水是()。

按照《建设工程施工合同文本》通用条款规定，工程具备隐蔽条件后，施工单位进行自检，并在隐蔽前()以书面形式通知监理工程师验收。

下列哪些行为属于走私行为?()

孔子倡导的六艺是“礼、乐、射、御、诗、数”。()

为了使加盟供应链的企业都能受益，并且要使每个企业都有比竞争对手更强的竞争实力，就必须加强对供应链的构成及运作研究，由此形成的新的经营与运作模式是()。

课程评价过程中要经历把焦点集中在所研究的课程对象、（）等步骤。

HowtoBeanExpertI.BackgroundinformationaboutthespeakerA.BeinganexpertinanthropologyhimselfB.Startingconsider

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