1、2013年 4月考试算法设计分析第二次作业 一、单项选择题（本大题共 30分，共 15 小题，每小题 2 分） 1. 优先队列的分支限界法将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。优先队列中规定的结点优先级常用一个与该结点相关的数值 p 来表示。结点优先级的高低与 p 值大小相关，根据问题的不同情况，采用（ ）来描述优先队列。 A. 先进先出队列 B. 后进先出的栈 C. 最大堆或最小堆 D. 随机序列 2. 阶乘函数用递归定义 Public static int factorial(int n) if(n=0) return 1;
2、 return () ; A. n*factorial(n) B. n*factorial(n-1) C. n*factorial(n-2) D. n*factorial(n+1) 3. （ ）能够求得问题的解 ,但却无法有效地判定解的正确性 A. 数值概率算法 B. 蒙特卡罗算法 C. 拉斯维加斯算法 D. 舍伍得算法 4. 对于 n个元素的排序问题。 n 2时 ,只要作（ ）次比较即可排好序 A. 3 B. 2 C. 1 D. 4 5. 一般地讲，当一个问题的所有子问题都至少要解一次时，用动态规划算法和备忘录算法相比： （ ） A. 效果一样 动态规划效果好 B. 备忘录方法效果好 C.
3、无法判断 D. 哪个效果好 6. 分支限界法与回溯法都是在问题的解空间树 T上搜索问题的解 ,二者（ ） A. 求解目标不同 ,搜索方式相同 B. 求解目标不同 ,搜索方式也不同 C. 求解目标相同 ,搜索方式不同 D. 求解目标相同 ,搜索方式也相同 7. 递归算法不能适用以下场合（ ） A. 数据的定义形式按递归定义 B. 数据之间的关 系 (即数据结构 )按递归定义 C. 问题解法按递归算法实现 D. 概率问题 8. 当子问题之间包含公共的子子问题则分治法要做许多不必要的工作 ,重复地解公共的子问题 ,此时一般用（ ）法较好 A. 动态规划 B. 分治 C. 贪心 D. 概率 9. 分治
4、法所能解决的问题应具有的关键特征是（ ）。 A. 该问题的规模缩小到一定的程度就可以容易地解决 B. 该问题可以分解为若干个规模较小的相同问题 C. 利用该问题分解出的子问题的解可以合并为该问题的解 D. 该问题所分解出的各个子问题是相互独立的 10. 对于货箱 装船问题 ,根据贪心策略 ,首先选择（ ）的货箱 ,然后选 （ ）的货箱 ,如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱 A. 最轻 次轻 B. 最重 次重 C. 最轻 次重 D. 最重 次轻 11. 用回溯法解 n后问题时，用完全 n叉树表示解空间。可行性约束 place剪去不满足行、列和斜线约束的子树， place
5、 中的 if判断条件应为（ ） A. (Math.abs(k-j) = = Math.abs(xj-xk) | (xj = = xk) B. (Math.abs(k-j) = = Math.abs(xj-xk) C. (xj = = xk) D. 以上都不正确 12. 分支限界法的搜索策略是：在扩展结点处，先生成其（ ）儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找
6、出一个最优解。 A. 一个 B. 二个 C. 任意多个 D. 所有的 13. 能够用动态规划解决的问题还有一个显著特征（ )这个性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就不具备优势。 A. 子问题的可求解性 B. 子问题的独立性 C. 子问题的可合并性 D. 子问题的重叠性 14. 在任何一个的棋盘覆盖中，用到的 L型骨牌个数恰为（ ）。 A. (4k-1)/3 B. (4k-1)/2 C. (2k-1)/3 D. (2k-1)/2 15. 动态规划的时间复杂度为（ ） A. O(n) B. O(n!) C. O(n2) D. O(n3) 二、判断题
7、（本大题共 70 分，共 20 小题，每小题 3.5 分） 1. 从分治法的一般设计模式可以看出，用它设计出的程序一般是一个递归过程。因此，分治法的计算效率通常可以用递归方程来进行分析。（ ） 2. 多阶段决策问题中，每一个阶段可能有若干个决策可供选择 ( ) 3. 拉斯维加斯算法不会得到不正确的解，但有时找不到解。 （ ） 4. 在通往边界条件的递归调用过程中，系统用堆栈保存的每次调用的中间结果是局部变量和返回地址值。 ( ) 5. 要想在电脑上扩大所处理问题的规模 ,有效的途径是提高算法的 计算复杂度。 ( ) 6. 程序必须满足算法具有数据输出的性质 ( ) 7. 反复应用分治手段，可以
8、使子问题与原问题类型一致而其规模却不断缩小 ( ) 8. 一个算法产生一个或多个输出，它们是同输入有某种特定关系的量 ( ) 9. 最优子结构性质特征反映了递归思想的应用 ( ) 10. 递归边界本身并不使用递归的定义 ( ) 11. 用分治法求解一个问题，所需的时间是由子问题的个数、大小以及把这个问题分解为子问题所需的工作总量来确定的。 ( ) 12. 应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少 包含问题的一个（最优）解。 （ ） 13. 好的约束函数能显著地减少所生成的结点数，但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之
9、间的折衷。 （ ） 14. 一个递归定义必须是有确切含义的 ,必须一步比一步简单，最后是有终结的，不能无限循环下去 ( )。 15. 最优子结构性质是应用分治法的前提 ( ) 16. 操作系统，它是一个在无限循环中执行的程序，因而不是一个算法。 ( ) 17. 有些数据结构如二叉树等，由于其本身的递归特性、特别适合用递归的形式来描述。 ( ) 18. 概率算法的一个基本特征是，对所求问题的同一个实例用同一个算法求解两次一定能得到完全相同的效果。 （ ） 19. 问题可以分解为若干个规模较小的相同问题，即称该问题具有最优子结构性质 ( ) 20. 递推是从内边界条件出发，通过递推式达到边界条件。 ( ) 答案： 一、单项选择题（ 30 分，共 15 题，每小题 2 分） 1. C 2. B 3. B 4. C 5. B 6. B 7. D 8. A 9. C 10. A 11. A 12. D 13. D 14. A 15. C 二、判断题（ 70 分，共 20 题，每小题 3.5 分） 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.
