(2012年上半年上午试题63、64)某货车运输公司有一个中央仓库和n个运输目的地，每天要从中央仓库将货物运输到所有运输目的地，到达每个运输目的地一次且仅一次，最后回到中央仓库。在两个地点i和j之间运输货物存在费用Cij，为求解旅行费用总和最小的运输路径，

admin2021-01-13 49

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

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

答案A

解析

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

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

软考中级

在程序流程图(见图6-21)中，若要某个房间I被选中，则需要满足什么条件?如果限制该算法最多输出K个可供选择的房间号，则在程序流程图(见图6-21)中“I＞N”(a所指向的判断框中)应修改为(4)。

企业信息整合、共享需要一个代表企业身份的信息，该信息应该具有唯一性和易管理性，上述表格中信息项(1)代表企业身份最合适。请用200字以内文字简要说明WebService涉及到的主要协议及其作用(XML、HTTP等除外)。

请将图4-15中各实体之间的联系补充完整。结合[问题2]所完成的实体—联系模式，以“存货表(商品编码，数量)”为例，用下画线指出其他各关系模式的主键。(“关系模式标记规则”见本题[附]部分)

函数intToplogical(LinkedWDigraphG)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下：ty

所谓灵活性是指导游讲解要()。

设计过程最根本的目标就是努力使设计出来的设备能逼近在(　　)过程中确认的设备质量的目标。

某打桩工程合同约定，第一个月计划完成工程桩120根；单价为1．2万元／根。时值月底，经确认的承包商实际完成的工程桩为110根；实际单价为1．3万元／根。在第一个月度内，该打桩工程的计划工作预算费用(BCWS)为()万元。

一张航空货运单用于()时间、()地点托运的由承运人承运的运往()目的站同一收货人的一件或多件货物。

股权投资基金托管人的首要职责是()。

建立团队层面绩效考核指标的方法包括()。

许多研究表明，儿童自我意识发生于大约出生后()。

(50)是软件生命周期中时间最长的阶段。

设有一个商店的数据库，记录客户及其购物情况，由三个关系组成：商品(商品号,商品名,单价,商品类别,供应商)，客户(客户号,姓名,地址,电邮,性别,身份证号)，购买(客户号,商品号,购买数量)，则关系购买的键为

Afterits【L1】tothe【L2】in2001,Chinahastakenstepstowardsopeningupits【L3】__.Asaconditionforjoiningt

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

软考中级

在程序流程图(见图6-21)中，若要某个房间I被选中，则需要满足什么条件?如果限制该算法最多输出K个可供选择的房间号，则在程序流程图(见图6-21)中“I＞N”(a所指向的判断框中)应修改为(4)。

企业信息整合、共享需要一个代表企业身份的信息，该信息应该具有唯一性和易管理性，上述表格中信息项(1)代表企业身份最合适。请用200字以内文字简要说明WebService涉及到的主要协议及其作用(XML、HTTP等除外)。

请将图4-15中各实体之间的联系补充完整。结合[问题2]所完成的实体—联系模式，以“存货表(商品编码，数量)”为例，用下画线指出其他各关系模式的主键。(“关系模式标记规则”见本题[附]部分)

函数intToplogical(LinkedWDigraphG)的功能是对图G中的顶点进行拓扑排序，并返回关键路径的长度。其中图G表示一个具有n个顶点的AOE网，图中顶点从1～n依次编号，图G的存储结构采用邻接表表示，其数据类型定义如下：ty

所谓灵活性是指导游讲解要()。

设计过程最根本的目标就是努力使设计出来的设备能逼近在( )过程中确认的设备质量的目标。

某打桩工程合同约定，第一个月计划完成工程桩120根；单价为1．2万元／根。时值月底，经确认的承包商实际完成的工程桩为110根；实际单价为1．3万元／根。在第一个月度内，该打桩工程的计划工作预算费用(BCWS)为()万元。

一张航空货运单用于()时间、()地点托运的由承运人承运的运往()目的站同一收货人的一件或多件货物。

股权投资基金托管人的首要职责是()。

建立团队层面绩效考核指标的方法包括()。

许多研究表明，儿童自我意识发生于大约出生后()。

(50)是软件生命周期中时间最长的阶段。

设有一个商店的数据库，记录客户及其购物情况，由三个关系组成：商品(商品号,商品名,单价,商品类别,供应商)，客户(客户号,姓名,地址,电邮,性别,身份证号)，购买(客户号,商品号,购买数量)，则关系购买的键为

Afterits【L1】______tothe【L2】______in2001,Chinahastakenstepstowardsopeningupits【L3】______.Asaconditionforjoiningt

设计过程最根本的目标就是努力使设计出来的设备能逼近在(　　)过程中确认的设备质量的目标。

Afterits【L1】tothe【L2】in2001,Chinahastakenstepstowardsopeningupits【L3】__.Asaconditionforjoiningt