发布时间 : 星期三 文章算法设计与分析试卷试题(A)(附答案)更新完毕开始阅读ba97f09b68eae009581b6bd97f1922791788be29
cheng
参考答案 一、填空
1、空间复杂度 时间复杂度 2、回溯法 3、递归算法 4、渐进确界或紧致界 5、原问题的较小模式 递归技术 6、问题的计算复杂性分析有一个共同的客观尺度 7、②③④① 8、问题的最优解包含其子问题的最优解 9、局部最优 10、
正确的
二、选择 1 2 3 4 5 6 7 8 9 10 C B C A B A B C B A 三、简答题
1、高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作； 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； 高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；
把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。
2、 ①不能保证最后求得的解是最佳的；即多半是近似解。（少数问题除外）
②策略容易发现（关键：提取清楚问题中的维度）， 而且运用简单，被广泛运用。 ③策略多样，结果也多样。
④算法实现过程中，通常用到辅助算法：排序
(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?0Q1cheng
f cheng
a．40?40?30?50?35?150?115?190.625 (1,1,1,1,7,0,0)
408b. 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)
d. 40?40?30?35?30?150?105?167.5 (1,1,1,0,1,3,0)
4e. 40?40?50?35?30?150?130?175
601(1,1,0,1,1,,0)
34 (1,1,0,1,1,0,)7f. 40?40?50?35?10?150?130?170.71
35g. 40?40?50?30?160
(1,1,0,1,0,1,0)
h. 40?40?35?30?10?150?140?146.85 (1,1,0,0,1,1,2)
357i.40?30?50?35?30?150?125?167.5(1,0,1,1,1,5,0)
6012150?145j. 40?30?50?35?30??157.5(0,1,1,1,1,1,0)
6012在Q1处获得该问题的最优解为(1,1,1,1,0,0,1)，背包效益为170。即在背包中装入物品F、B、G、D、A时达到最大效益，为170，重量为150。【结论2分】
2、初始单纯型表如下： 1）（5分） z x1 x4 x6 0 7 12 10 x2 -1 3 -2 -4 x3 3 -1 4 3 x5 -2 2 0 8 2）第一步入基变量x3、离基变量x4 第二步入基变量x2、离基变量x1 3）（6分） z x2 x3 x6 11 4 5 11 x1 -1/5 5/2 1/5 1 x4 -4/5 1/10 3/10 -1/2 x5 -12/5 4/5 2/5 10 目标函数的最大值为11 最优解为：x*=(0,4,5,0,0,11)
（其中表格填写占11分，目标函数的最大值2分，最优解为占2分）
cheng