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

admin2019-07-12 29

问题某货车运输公司有一个中央仓库和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)

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

软考中级

SMTP协议用于(36)电子邮件。

在Linux中，要更改一个文件的权限设置可使用(32)________________命令。

在操作系统文件管理中，通常采用______来组织和管理外存中的信息。

能显示IP、ICMP、TCP、UDP统计信息的Windows命令是(42)。

现有4级指令流水线，分别完成取指、取数、运算、传送结果4步操作。若完成上述操作的时间依次为9nss。10ns、6ns、8ns，则流水线的操作周期应设计为__________ns。

SNMP采用UDP提供的数据报服务，这是由于()。

开放系统的数据存储有多种方式，属于网络化存储的是__________。(2009年下半年试题)

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

某银行为用户提供网上服务，允许用户通过浏览器管理自己的银行账户信息。为保障通信的安全，该Web服务器可选的协议是(45)。

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

在决策系统内处于核心主导地位的是()

A．从胸走手B．从手走头C．从头走足D．从足走腹E．从腹走胸

被告人徐某为未成年人，法院书记员到其住处送达起诉书副本，徐某及其父母拒绝签收。关于该书记员处理这一问题的做法，下列哪些选项是正确的?(2013年试卷2第70题)

()的实施是对绿色营销行为的“真实化”。

课堂管理的基本功能是()。

五彩瓷器的基本色调是红、黄、绿、蓝、紫，开始出现于清代。()

“意大利地图的形状像皮靴”是精加工策略中的()。

职场秀客是指职场上过于自我吹嘘、自我炫耀者。然而实际上，他们的能力并不怎么样。他们自吹自擂的行为不但不能为自己加分，反倒使同事们非常反感，不利于自身的发展。根据上述定义，下列不属于职场秀客的是：

施某犯贪污罪，被判无期徒刑。服刑12年后，因表现良好而获假释。在假释考验期内的第6年，施某故意致人重伤，被判刑9年。根据刑法规定，对施某应撤销假释，按数罪并罚的规定处理。对施某应适用何种刑罚幅度或刑种?()

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

软考中级

SMTP协议用于(36)电子邮件。

在Linux中，要更改一个文件的权限设置可使用(32)________________命令。

在操作系统文件管理中，通常采用______来组织和管理外存中的信息。

能显示IP、ICMP、TCP、UDP统计信息的Windows命令是(42)。

现有4级指令流水线，分别完成取指、取数、运算、传送结果4步操作。若完成上述操作的时间依次为9nss。10ns、6ns、8ns，则流水线的操作周期应设计为__________ns。

SNMP采用UDP提供的数据报服务，这是由于()。

开放系统的数据存储有多种方式，属于网络化存储的是__________。(2009年下半年试题)

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

某银行为用户提供网上服务，允许用户通过浏览器管理自己的银行账户信息。为保障通信的安全，该Web服务器可选的协议是(45)。

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

在决策系统内处于核心主导地位的是()

A．从胸走手B．从手走头C．从头走足D．从足走腹E．从腹走胸

被告人徐某为未成年人，法院书记员到其住处送达起诉书副本，徐某及其父母拒绝签收。关于该书记员处理这一问题的做法，下列哪些选项是正确的?(2013年试卷2第70题)

()的实施是对绿色营销行为的“真实化”。

课堂管理的基本功能是()。

五彩瓷器的基本色调是红、黄、绿、蓝、紫，开始出现于清代。()

“意大利地图的形状像皮靴”是精加工策略中的()。

职场秀客是指职场上过于自我吹嘘、自我炫耀者。然而实际上，他们的能力并不怎么样。他们自吹自擂的行为不但不能为自己加分，反倒使同事们非常反感，不利于自身的发展。根据上述定义，下列不属于职场秀客的是：

施某犯贪污罪，被判无期徒刑。服刑12年后，因表现良好而获假释。在假释考验期内的第6年，施某故意致人重伤，被判刑9年。根据刑法规定，对施某应撤销假释，按数罪并罚的规定处理。对施某应适用何种刑罚幅度或刑种?()

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