1、2014 年 9 月份考试算法设计分析第二次作业一、单项选择题（本大题共 50 分，共 20 小题，每小题 2.5 分）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. 上界函数 bound 计算结点所相应价值的上界。 private static double bound (int i) /计算结点所相应价值的上界 double cleft = c-cw; /剩余容量 double b = cp; /价值上界 / 以物品单位重量价值递减序装填剩余容量 while (i=n b += pi; i+; /装填剩余容量装满背包 if (i=n) （ ） ; return b; A. b
3、 += pi B. b = pi/wi*cleftC. b += pi/wi*cleft D. b = pi4. 在动态规划算法中，问题的最优子结构性质使我们能够以 （ ）的方式递归地从子问题的最优解逐步构造出整个问题的最优解。A. 自左向右B. 自右向左C. 自上向下D. 自底向上5. （ ）能够求得问题的解,但却无法有效地判定解的正确性A. 数值概率算法B. 蒙特卡罗算法C. 拉斯维加斯算法D. 舍伍得算法6. 拉斯维加斯算法的一个显著特征是它所做的随机性决策有可能导致算法找不到所需的解。因此通常用一个（ ）方法表示拉斯维加斯型算法。A. boolean 型 B. 概率C. 统筹D. 自定
4、义7. 对于 n 个元素的排序问题。 n 2 时,只要作（ ）次比较即可排好序A. 3B. 2C. 1D. 48. 旅行售货员问题：算法中 while 循环的终止条件是排列树的一个 （ ）成为当前扩展结点。A. 根结点B. 父结点C. 子结点D. 叶结点9. 一般地讲，当一个问题的所有子问题都至少要解一次时，用动态规划算法和备忘录算法相比： （ ）A. 效果一样 动态规划效果好B. 备忘录方法效果好C. 无法判断D. 哪个效果好10. 分支限界法与回溯法都是在问题的解空间树 T 上搜索问题的解,二者（ ）A. 求解目标不同,搜索方式相同B. 求解目标不同,搜索方式也不同C. 求解目标相同,搜索
5、方式不同D. 求解目标相同,搜索方式也相同11. 回溯法以深度优先的方式搜索解空间树，而分支限界法则以（ ）方式搜索解空间树。A. 深度优先B. 广度优先C. 递归D. 遍历12. 当子问题之间包含公共的子子问题则分治法要做许多不必要的工作,重复地解公共的子问题,此时一般用（ ）法较好A. 动态规划B. 分治C. 贪心D. 概率13. 分治法所能解决的问题应具有的关键特征是（ ）。A. 该问题的规模缩小到一定的程度就可以容易地解决B. 该问题可以分解为若干个规模较小的相同问题C. 利用该问题分解出的子问题的解可以合并为该问题的解D. 该问题所分解出的各个子问题是相互独立的14. 由边界条件出发
6、,通过递推式求 f(n)的值,从边界到求解的全过程十分清楚的是（ ）A. 贪心B. 递推C. 递归D. 概率15. 对于货箱装船问题,根据贪心策略,首先选择（ ）的货箱,然后选 （ ）的货箱,如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱A. 最轻 次轻B. 最重 次重C. 最轻 次重D. 最重 次轻16. 用回溯法解 n 后问题时，用完全 n 叉树表示解空间。可行性约束 place 剪去不满足行、列和斜线约束的子树，place 中的 if 判断条件应为（ ）A. (Math.abs(k-j) = = Math.abs(xj-xk) | (xj = = xk)B. (Math.a
7、bs(k-j) = = Math.abs(xj-xk)C. (xj = = xk)D. 以上都不正确17. 分支限界法的搜索策略是：在扩展结点处，先生成其（ ）儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。A. 一个B. 二个C. 任意多个D. 所有的18. 能够用动态规划解决的问题还有一个显著特征（ )这个性质并不是动态规划适用的必要条件，但是如果该
8、性质无法满足，动态规划算法同其他算法相比就不具备优势。A. 子问题的可求解性B. 子问题的独立性C. 子问题的可合并性D. 子问题的重叠性19. 在任何一个 的棋盘覆盖中，用到的 L 型骨牌个数恰为（ ）。22A. (4k-1)/3B. (4k-1)/2C. (2k-1)/3D. (2k-1)/2 20. 动态规划的时间复杂度为（ ）A. O(n)B. O(n!)C. O(n2)D. O(n3)二、判断题（本大题共 50 分，共 20 小题，每小题 2.5 分）1. 从分治法的一般设计模式可以看出，用它设计出的程序一般是一个递归过程。因此，分治法的计算效率通常可以用递归方程来进行分析。（ ）2
9、. 贪心法只能求满足某些约束条件的可行解的范围。（ ）3. 分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间树 T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解。 （ ）4. 拉斯维加斯算法不会得到不正确的解，但有时找不到解。 （ ）5. 在通往边界条件的递归调用过程中，系统用堆栈保存的每次调用的中间结果是局部变量和返回地址值。( )6. 程序必须满足算法具有数据输出的性质( )7. 分治与递归经常同时应用在算法设计之中，并由此产生许多高效算法。( )8. 任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。( )9. 对同一个问题，动态规划算
10、法和分治算法计算复杂性是一样的。（ ）10. 最优子结构性质特征反映了递归思想的应用 ( )11. 用分治法求解一个问题，所需的时间是由子问题的个数、大小以及把这个问题分解为子问题所需的工作总量来确定的。( )12. 应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。 （ ）13. 好的约束函数能显著地减少所生成的结点数，但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。 （ ）14. 一个递归定义必须是有确切含义的,必须一步比一步简单，最后是有终结的，不能无限循环下去( )。15. 最优子结构性质是应
11、用分治法的前提( )16. 操作系统，它是一个在无限循环中执行的程序，因而不是一个算法。( )17. 有些数据结构如二叉树等，由于其本身的递归特性、特别适合用递归的形式来描述。( )18. 概率算法的一个基本特征是，对所求问题的同一个实例用同一个算法求解两次一定能得到完全相同的效果。 （ ）19. 问题可以分解为若干个规模较小的相同问题，即称该问题具有最优子结构性质( )20. 递推是从内边界条件出发，通过递推式达到边界条件。( )答案：一、单项选择题（50 分，共 20 题，每小题 2.5 分）1. C 2. B 3. C 4. D 5. B 6. A 7. C 8. D 9. B 10. B 11. A 12. A 13. C 14. B 15. A 16. A 17. D 18. D 19. A 20. C 二、判断题（50 分，共 20 题，每小题 2.5 分）1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.
