根据程序说明及流程图、部分C源码，充分理解算法思想，填入(n)处。求解“背包问题”常用的方法有哪几种?各有什么样的特点?

admin2009-02-15 73

问题根据程序说明及流程图、部分C源码，充分理解算法思想，填入(n)处。
求解“背包问题”常用的方法有哪几种?各有什么样的特点?

选项

答案“背包问题”求解方法主要是一些启发式算法，如贪婪算法、递归算法等。应用递归算法的目的是穷举所有可能的解，从中选出最佳解。这种解法实际上是穷举了所有的可能，只是加了一些限制。如果所求的数据很大，这种算法的效率就不是很高，甚至是不可实现的。贪婪法不用穷举且速度快，但用贪婪法却不一定能找到最优解。由于贪婪法所得到的解与最优解存在很大的差距，当要求较高时，就会成为贪婪法致命的且无法挽救的缺陷。

解析本题考查的是考生对流程图的阅读能力。本题涉及的算法是背包问题。背包问题求解方法很多，考生首先要理解本题中的新方法，然后对照流程图阅读代码。(1)处应该为物品总重量；(2)处应该为物品总价值；(3)处应该为直到达到极限重量limit weight；(4)处应该为继续装物品；(5)处应该为比较当前结果与备份结果。问题2同样是考查有关基本概念的问题。根据软件设计师考试的趋势，本套题设计上有意识地增加了概念考查部分，希望考生能够加强对基本概念的理解与训练。

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

本试题收录于：软件设计师下午应用技术考试题库软考中级分类

软件设计师下午应用技术考试

软考中级

相关试题推荐

随机试题

最新回复(0)

根据程序说明及流程图、部分C源码，充分理解算法思想，填入(n)处。求解“背包问题”常用的方法有哪几种?各有什么样的特点?

软件设计师下午应用技术考试

软考中级

在结构化分析中，用数据流图描述(42)。当采用数据流图对银行客户关系管理进行分析时，(43)是一个加工。(43)

以下关于测试时机的叙述中，正确的是_______。①应该尽可能早地进行测试②软件中的错误暴露得越迟，则修复和改正错误所花费的代价就越高③应该在代码编写完成后开始测试④项目需求分析和设计阶段不需要测试人员参与

X软件公司的软件工程师张某兼职于Y科技公司，为完成Y科技公司交给的工作，做出了一项涉及计算机程序的发明。张某认为该发明是利用自己的业余时间完成的，可以以个人名义申请专利。此项专利申请权应归属()。

在程序执行过程中，Cache与主存的地址映像由()。

软件测试的对象包括__________。①需求规格说明书②概要设计文档③软件测试报告④软件代码⑤用户手册⑥软件开发人员

给系统增加特征越容易，说明软件的______越好。

设有关系模式R(A1，A2，A3，A4，A5，A6)，其中：函数依赖集F={A1→A2，A1A3→A4，A5A6→A1，A2A5→A6，A3A5→A6)，则_(21)是关系模式R的一个主键，R规范化程度最高达到__(

______ininterestednotonlyindescribinglanguagebutalsoinexplaininglanguage.

患者，女，26岁，右侧卵巢肿物2年，1小时前突然有下腹剧痛伴恶心、呕吐。妇科查体：子宫(-)，右侧附件有手拳大小的囊性肿物，边界清、活动差，左附件(-)，其诊断是

肺病及肝的五行传变是()

患者，男，50岁。半年来经常突发胸骨后疼痛，有窒息感，持续约1～5分钟，休息后迅速缓解。心电图示ST段下移及T波倒置。应首先考虑的是()

施工合同示范文本规定，属于承包人应当完成的工作有(　　)。

下列有关设计文件技术交底的说法，符合《建设工程质量管理条例》规定的是()。

或有事项具有的特征包括()。

面对大量涌来的西方文化，我们要主动选择自己要的，那些不要的，同时也要我们的传统文化，这样才能构建好社会主义特色的新文化。填入画横线部分最恰当的一项是：

TooLatetoRegretItWhenIwasajunior,Imetasecond-yearstudentinmydepartment.Hewasn’ttallorgood-looking,buthe

根据程序说明及流程图、部分C源码，充分理解算法思想，填入(n)处。 求解“背包问题”常用的方法有哪几种?各有什么样的特点?

软件设计师下午应用技术考试

软考中级

在结构化分析中，用数据流图描述(42)。当采用数据流图对银行客户关系管理进行分析时，(43)是一个加工。(43)

以下关于测试时机的叙述中，正确的是_______。①应该尽可能早地进行测试②软件中的错误暴露得越迟，则修复和改正错误所花费的代价就越高③应该在代码编写完成后开始测试④项目需求分析和设计阶段不需要测试人员参与

X软件公司的软件工程师张某兼职于Y科技公司，为完成Y科技公司交给的工作，做出了一项涉及计算机程序的发明。张某认为该发明是利用自己的业余时间完成的，可以以个人名义申请专利。此项专利申请权应归属()。

在程序执行过程中，Cache与主存的地址映像由()。

软件测试的对象包括__________。①需求规格说明书②概要设计文档③软件测试报告④软件代码⑤用户手册⑥软件开发人员

给系统增加特征越容易，说明软件的______越好。

设有关系模式R(A1，A2，A3，A4，A5，A6)，其中：函数依赖集F={A1→A2，A1A3→A4，A5A6→A1，A2A5→A6，A3A5→A6)，则___________(21)是关系模式R的一个主键，R规范化程度最高达到____________(

______ininterestednotonlyindescribinglanguagebutalsoinexplaininglanguage.

患者，女，26岁，右侧卵巢肿物2年，1小时前突然有下腹剧痛伴恶心、呕吐。妇科查体：子宫(-)，右侧附件有手拳大小的囊性肿物，边界清、活动差，左附件(-)，其诊断是

肺病及肝的五行传变是()

患者，男，50岁。半年来经常突发胸骨后疼痛，有窒息感，持续约1～5分钟，休息后迅速缓解。心电图示ST段下移及T波倒置。应首先考虑的是()

施工合同示范文本规定，属于承包人应当完成的工作有( )。

下列有关设计文件技术交底的说法，符合《建设工程质量管理条例》规定的是()。

或有事项具有的特征包括()。

面对大量涌来的西方文化，我们要主动选择自己要的，________那些不要的，同时也要________我们的传统文化，这样才能构建好社会主义特色的新文化。填入画横线部分最恰当的一项是：

TooLatetoRegretItWhenIwasajunior,Imetasecond-yearstudentinmydepartment.Hewasn’ttallorgood-looking,buthe

根据程序说明及流程图、部分C源码，充分理解算法思想，填入(n)处。求解“背包问题”常用的方法有哪几种?各有什么样的特点?

设有关系模式R(A1，A2，A3，A4，A5，A6)，其中：函数依赖集F={A1→A2，A1A3→A4，A5A6→A1，A2A5→A6，A3A5→A6)，则_(21)是关系模式R的一个主键，R规范化程度最高达到__(

施工合同示范文本规定，属于承包人应当完成的工作有(　　)。

面对大量涌来的西方文化，我们要主动选择自己要的，那些不要的，同时也要我们的传统文化，这样才能构建好社会主义特色的新文化。填入画横线部分最恰当的一项是：