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

admin2019-04-22 38

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

选项 A、
B、
C、
D、

答案A

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

(n²)。

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

在IBMNetView中，使用性能轮询与(1)来检测网络故障并响应。对第三方面言，NetView在某种程度上提供了一些灵活性，在系统告警和事件中允许(2)。NetView也使用了(3)，这使得利用NetView采集来的数据开发扩展应用变得相对容易。Sun

以下关于OSPF的区域(Area)的叙述中，正确的是(19)。

某软件项目的活动图如下图所示，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，边上的数字表示活动的持续时间(天)。完成该项目的最少时间为_____________天。

两个站点采用二进制指数后退算法进行避让，3次冲突之后再次冲突的概率是(59)________________。

查看OSPF接口的开销、状态、类型、优先级等的命令是；查看OSPF在接收报文时出错记录的命令是。

在下面4种病毒中，()可以远程控制网络中的计算机。

一个项目为了修正一个错误而进行了变更。这个变更被修正后，却引起以前可以正确运行的代码出错。__________最可能发现这一问题。(2009年下半年试题)

报文摘要算法SHA．1输出的位数是(44)。

采用连续播放静止图像的方法产生运动的效果，即使用计算机产生图形、图像运动的技术称之为(58)。(59)采用实时绘制的方式显示一幅矢量图，当图形放大或缩小时，都保持光滑的线条，不会影响质量，也不会改变文件的容量。

A．超急性排斥反应B．急性体液性排斥反应C．急性细胞性排斥反应D．慢性排斥反应E．移植物抗宿主反应由内皮细胞表面HLA分子的抗体所介导

下列哪项属于病理性汗出()

A．技术和质量文件B．质量和销售C．进行生产D．文件和记录E．指导和监督委托生产药品受托方应当按照规定保存所有受托生产药品的()

被告人王某故意杀人案经某市中级法院审理，认为案件事实清楚，证据确实、充分。请根据下列条件，回答下列题。(2010年试卷2第95～97题)如王某被判处无期徒刑，附加剥夺政治权利，下列选项正确的是：

当城市工程管线竖向位置发生矛盾时,关于其处理原则错误的是()。

教育是培养人的工作，在确定培养人的规格时受到社会生产力发展水平的影响。()

要选修数理逻辑课，必须已修普通逻辑课，并对数学感兴趣。有些学生虽然对数学感兴趣，但并没修过普通逻辑课，因此，有些对数学感兴趣的学生不能选修数理逻辑课。以下哪项的逻辑结构与题干的最为类似?

WhyisitdifficultforthemantoleanEnglish?

MiracleoftheForestWhenyouwalkintoaNationalForest,youreallybelieveyouarethefirstpersonwhohaseverbeenhe

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

软考中级

在IBMNetView中，使用性能轮询与(1)来检测网络故障并响应。对第三方面言，NetView在某种程度上提供了一些灵活性，在系统告警和事件中允许(2)。NetView也使用了(3)，这使得利用NetView采集来的数据开发扩展应用变得相对容易。Sun

以下关于OSPF的区域(Area)的叙述中，正确的是(19)。

某软件项目的活动图如下图所示，其中顶点表示项目里程碑，连接顶点的边表示包含的活动，边上的数字表示活动的持续时间(天)。完成该项目的最少时间为_____________天。

两个站点采用二进制指数后退算法进行避让，3次冲突之后再次冲突的概率是(59)________________。

查看OSPF接口的开销、状态、类型、优先级等的命令是________________；查看OSPF在接收报文时出错记录的命令是________________。

在下面4种病毒中，()可以远程控制网络中的计算机。

一个项目为了修正一个错误而进行了变更。这个变更被修正后，却引起以前可以正确运行的代码出错。__________最可能发现这一问题。(2009年下半年试题)

报文摘要算法SHA．1输出的位数是(44)。

采用连续播放静止图像的方法产生运动的效果，即使用计算机产生图形、图像运动的技术称之为(58)。(59)采用实时绘制的方式显示一幅矢量图，当图形放大或缩小时，都保持光滑的线条，不会影响质量，也不会改变文件的容量。

A．超急性排斥反应B．急性体液性排斥反应C．急性细胞性排斥反应D．慢性排斥反应E．移植物抗宿主反应由内皮细胞表面HLA分子的抗体所介导

下列哪项属于病理性汗出()

A．技术和质量文件B．质量和销售C．进行生产D．文件和记录E．指导和监督委托生产药品受托方应当按照规定保存所有受托生产药品的()

被告人王某故意杀人案经某市中级法院审理，认为案件事实清楚，证据确实、充分。请根据下列条件，回答下列题。(2010年试卷2第95～97题)如王某被判处无期徒刑，附加剥夺政治权利，下列选项正确的是：

当城市工程管线竖向位置发生矛盾时,关于其处理原则错误的是()。

教育是培养人的工作，在确定培养人的规格时受到社会生产力发展水平的影响。()

要选修数理逻辑课，必须已修普通逻辑课，并对数学感兴趣。有些学生虽然对数学感兴趣，但并没修过普通逻辑课，因此，有些对数学感兴趣的学生不能选修数理逻辑课。以下哪项的逻辑结构与题干的最为类似?

WhyisitdifficultforthemantoleanEnglish?

MiracleoftheForestWhenyouwalkintoaNationalForest,youreallybelieveyouarethefirstpersonwhohaseverbeenhe

查看OSPF接口的开销、状态、类型、优先级等的命令是；查看OSPF在接收报文时出错记录的命令是。