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

考试课程： 班级： 姓名： 学号： 算法分析考试试卷（A卷） ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 --------------------------------------------------------- 课程名称 算法分析 编号 题号 得分 评阅人 一 二 三 四 总分 一、填空题（每小题3分，共30分） 1、一个算法的优劣可以用 空间复杂度 与 时间复杂度 来衡量。 2、这种不断回头寻找目标的方法称为 回溯法 。 3、直接或间接地调用自身的算法称为 递归算法 。 4、? 记号在算法复杂性的表示法中表示 紧致界 。 5、由分治法产生的子问题往往是 原问题较小模式 ，这就为使用 递归技术 提供了方便。 6、建立计算模型的目的是为了使 问题的计算复杂性分析有一个共同的客观尺度 。 7、下列各步骤的先后顺序是 ②③④① 。①调试程序 ②分析问题 ③设计算法 ④编写程序。 8、最优子结构性质的含义是 问题最优解包含其子问题最优解 。 9、贪心算法从初始阶段开始，每一个阶段总是作一个使 局部最优 的贪心选择。 10、拉斯维加斯算法找到的解一定是 正确的 。 二、选择题（每小题2分，共20分） 1、哈夫曼编码可利用（ C ）算法实现。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是基本计算模型的是（ B ）。 A、RAM B、ROM C、RASP D、TM 3、下列算法中通常以自顶向下的方式求解最优解的是（ C）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 - 1 -

4、在对问题的解空间树进行搜索的方法中,一个活结点有多次机会成为活结点的是( A ) A、回溯法 B、分支限界法 C、回溯法和分支限界法 D、动态规划 5、秦始皇吞并六国使用的远交近攻，逐个击破的连横策略采用了以下哪种算法思想？ B A、 递归；B、分治；C、迭代；D、模拟。 6、FIFO是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 7、投点法是（ B ）的一种。 A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法 8、若线性规划问题存在最优解，它一定不在（ C ） A．可行域的某个顶点上 B．可行域的某条边上 C．可行域内部 D．以上都不对 9、在一般输入数据的程序里，输入多多少少会影响到算法的计算复杂度，为了消除这种影响可用（ B ）对输入进行预处理。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 10、若L是一个NP完全问题，L经过多项式时间变换后得到问题l，则l是( A ). A、P类问题 B、NP难问题 C、NP完全问题 D、P类语言 三、简答题（每小题5分，共20分） 1、采用高级程序设计语言表达算法，主要好处是： 高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作； 高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高； 高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高； 把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。 2、由于贪心算法是一种只顾眼前的步骤，而难以顾及全局步骤的算法，所以它通常表现出哪些特点？ ①不能保证最后求得的解是最佳的；即多半是近似解。（少数问题除外） ②策略容易发现（关键：提取清楚问题中的维度）， 而且运用简单，被广泛运用。 ③策略多样，结果也多样。 ④算法实现过程中，通常用到辅助算法：排序 3、求下列函数的渐近表达式： n?10n-1; 14+5/n+1/n2; 2(n2?10n-1)?n2?0;由渐近表达式的定义易知： ① 因为：limn??n2?10n-1(14?5/n?1/ n2)?14?0;由渐 n是n?10n-1;的渐近表达式。 ② 因为：limn??14?5/n?1/ n222近表达式的定义易知： 14是14+5/n+1/ n2的渐近表达式。 4、简述动态规划算法的基本步骤 - 2 -

考试课程： 班级： 姓名： 学号： ------------------------------------------------- 密 ---------------------------------- 封 ----------------------------- 线 --------------------------------------------------------- 四、算法设计题（每小题15分，共30分） 1、假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树并计算各个节点处的限界函数值，最后给出装载方案及背包中物品的重量和价值。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30 x1?1x2?1x3?1ax1?0ax2?0jaix4?1ax4?0x3?0ax5?0dx4?1ex4?0bx6?0x5?1ex5?0hgcx7?0ex6?0Q1 f 2、用单纯形法解下列线性规划问题 maxz??x2?3x3?2x5?7?12?10 x1?3x2?x3?2x5x4?2x2?4x3x6?4x2?3x3?8x5xi?01） 填写初始单纯型表 i?1,2,3,4,5,6 - 3 -

3）填写最终单纯型表并给出最优解 目标函数的最大值为： 最优解为： - 4 -

参考答案 一、填空

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?0Q1

f - 5 -

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)重量为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 ，背包效益为170。即在背包中装入物品F、B、G、D、A时达到最大效益，为170，

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分）

- 6 -

本文来源：https://www.bwwdw.com/article/rcyd.html