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

admin2009-02-15 45

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

选项

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

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

转载请注明原文地址:https://jikaoti.com/ti/C2i7FFFM

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

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

软考中级

相关试题推荐

随机试题

最新回复(0)

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

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

软考中级

安全日志是软件产品的一种被动防范措施，是系统重要的安全功能，因此安全日志测试是软件系统安全性测试的重要内容，下列不属于安全日志测试基本测试内容的是_______。

在面向对象方法中，______是一种概念、抽象或具有状态、行为和标识的事物。

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

设系统中有R类资源m个，现有n个进程互斥使用。若每个进程对R资源的最大需求为w，那么当m、n、w取下表的值时，对于下表中的a～e五种情况，(26)两种情况可能会发生死锁。对于这两种情况，若将(27)，则不会发生死锁。

在WindowsXP操作系统中，用户利用“磁盘管理”程序可以对磁盘进行初始化、创建卷，(23)。通常将“C：\Windows\nyprogram.exe”文件设置成只读和隐藏属性，以便控制用户对该文件的访问，这一级安全管理称之为(24)安全管理。

某软盘有40个磁道，磁头从一个磁道移至另一个磁道需要5ms。文件在磁盘上非连续存放，逻辑上相邻数据块的平均距离为10个磁道，每块的旋转延迟时间及传输时间分别为100ms和25ms，则读取一个100块的文件需要时间为(24)。

在分层体系结构中，(41)实现与实体对象相关的业务逻辑。在基于Java，EE技术开发的软件系统中，常用(42)技术来实现该层。(42)

以下关于数据流图的叙述中，不正确的是()。

阅读以下说明和图，填补流程图中的空缺。【说明】某汽车制造工厂有两条装配线。汽车装配过程如图10-6所示，即汽车底盘进入装配线，零件在多个工位装配，结束时汽车自动完成下线工作。(1)e0和e1表示底盘分别进入装配线0和

在装配中，对特征引用集进行编辑时，基于特征的组件阵列：

Why!Ihavenothingtoconfess.______youwantmetosay?

男性，60岁。10天前行胃癌根治术，近3天来体温38℃左右，胸片正常，尿常规未见异常，腹部伤口愈合好，已拆线，上腹部B超未见积液，查体发现左小腿微肿，腓肠肌有压痛。可能的诊断是

计算I=，其中力为z2=x2+y2，z=1所围成的立体，则正确的解法是()。

非分组型终端是指()。

科学管理的中心问题是()。

A.weareallbookedupforFlight802onthatday.B.I’dliketomakeareservationtoBostonnextweek.C.whataboutthefar

某公司发行的长期债券面值为1000元／张，共10000张，年利息率为10％，每年年末付息，到期还本，期限为10年。债券按面值溢价12％发行，筹资费用为发行价的12％，公司的所得税率为25％，该债券的税后资金成本为()

以使用价值为生产目的，以自给自足为特征的经济形式是()

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

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

软考中级

安全日志是软件产品的一种被动防范措施，是系统重要的安全功能，因此安全日志测试是软件系统安全性测试的重要内容，下列不属于安全日志测试基本测试内容的是_______。

在面向对象方法中，______是一种概念、抽象或具有状态、行为和标识的事物。

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

设系统中有R类资源m个，现有n个进程互斥使用。若每个进程对R资源的最大需求为w，那么当m、n、w取下表的值时，对于下表中的a～e五种情况，(26)两种情况可能会发生死锁。对于这两种情况，若将(27)，则不会发生死锁。

在WindowsXP操作系统中，用户利用“磁盘管理”程序可以对磁盘进行初始化、创建卷，(23)。通常将“C：\Windows\nyprogram.exe”文件设置成只读和隐藏属性，以便控制用户对该文件的访问，这一级安全管理称之为(24)安全管理。

某软盘有40个磁道，磁头从一个磁道移至另一个磁道需要5ms。文件在磁盘上非连续存放，逻辑上相邻数据块的平均距离为10个磁道，每块的旋转延迟时间及传输时间分别为100ms和25ms，则读取一个100块的文件需要时间为(24)。

在分层体系结构中，(41)实现与实体对象相关的业务逻辑。在基于Java，EE技术开发的软件系统中，常用(42)技术来实现该层。(42)

以下关于数据流图的叙述中，不正确的是()。

在装配中，对特征引用集进行编辑时，基于特征的组件阵列：

Why!Ihavenothingtoconfess.______youwantmetosay?

男性，60岁。10天前行胃癌根治术，近3天来体温38℃左右，胸片正常，尿常规未见异常，腹部伤口愈合好，已拆线，上腹部B超未见积液，查体发现左小腿微肿，腓肠肌有压痛。可能的诊断是

计算I=，其中力为z2=x2+y2，z=1所围成的立体，则正确的解法是()。

非分组型终端是指()。

科学管理的中心问题是()。

A.weareallbookedupforFlight802onthatday.B.I’dliketomakeareservationtoBostonnextweek.C.whataboutthefar

某公司发行的长期债券面值为1000元／张，共10000张，年利息率为10％，每年年末付息，到期还本，期限为10年。债券按面值溢价12％发行，筹资费用为发行价的12％，公司的所得税率为25％，该债券的税后资金成本为()

以使用价值为生产目的，以自给自足为特征的经济形式是()

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

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