算法设计与分析试卷(A)及答案

______________________________________________________________________________________________________________

精品资料

______________________________________________________________________________________________________________

精品资料 3）填写最终单纯型表并给出最优解 目标函数的最大值为： 最优解为： ______________________________________________________________________________________________________________

参考答案 一、填空

1、空间复杂度 时间复杂度 2、回溯法 3、递归算法 4、渐进确界或紧致界 5、原问题的较小模式 递归技术 6、问题的计算复杂性分析有一个共同的客观尺度 7、②③④① 8、问题的最优解包含其子问题的最优解 9、局部最优 10、

正确的

二、选择 1 C

三、简答题

1、高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作； 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； 高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；

把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。

2、 ①不能保证最后求得的解是最佳的；即多半是近似解。（少数问题除外）

②策略容易发现（关键：提取清楚问题中的维度）， 而且运用简单，被广泛运用。

精品资料

2 B 3 C 4 A 5 B 6 A 7 B 8 C 9 B 10 A ______________________________________________________________________________________________________________

③策略多样，结果也多样。

④算法实现过程中，通常用到辅助算法：排序

(n2?10n-1)?n2?0;由渐近表达式的定义易知： 3、解：① 因为：limn??n2?10n-1 n是n?10n-1;的渐近表达式。

22(14?5/n?1/ n2)?14?0;由渐近表达式的定义易知： ② 因为：lim2n??14?5/n?1/ n 14是14+5/n+1/ n2的渐近表达式。 4、 找出最优解的性质，并刻划其结构特征。

递归地定义最优值。

以自底向上的方式计算出最优值。

根据计算最优值时得到的信息，构造最优解。 四、算法设计题

1、按照单位效益从大到小依次排列这7个物品为：FBGDECA。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】

x1?1x2?1x3?1ax1?0ax2?0jaix4?1ax4?0x3?0ax5?0dx4?1ex4?0bx6?0x5?1ex5?0hgcx7?0ex6?0Q1f 408a．40?40?30?50?35?150?115?190.625 (1,1,1,1,7,0,0) b. 40?40?30?50?30?150?115?177.5(1,1,1,1,0,7,0)

6012c．40?40?30?50?10?170

60 (1,1,1,1,0,0,1)

4d. 40?40?30?35?30?150?105?167.5 (1,1,1,0,1,3,0) e. 40?40?50?35?30?150?130?175

601(1,1,0,1,1,,0)

3精品资料