A. 贪心算法 B. 递归算法 C. 迭代算法
D. 动态规划算法
66. 二分查找只适用（ B ）存储结构。 A. 堆 B. 顺序 C. 任意顺序 D. 栈
67. 应用分治法的两个前提是（ A ）。 A. 问题的可分性和解的可归并性 B. 问题的可分性和解的存在性 C. 问题的复杂性和解的可归并性 D. 问题的可分性和解的复杂性
68. 优先队列的分支限界法将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。优先队列中规定的结点优先级常用一个与该结点相关的数值p来表示。结点优先级的高低与p值大小相关，根据问题的不同情况，采用（ C ）来描述优先队列。 A. 先进先出队列 B. 后进先出的栈 C. 最大堆或最小堆 D. 随机序列
69. 阶乘函数用递归定义 Public static int factorial（int n） {if（n==0）return 1；return（ B ）：} A. n*factorial(n) B. n*factorial(n-1) C. n*factorial(n-2) D. n*factorial(n+1)
70. （ B ）能够求得问题的解但却无法有效地判定解的正确性。 A. 数值概率算法 B. 蒙特卡罗算法 C. 拉斯维加斯算法 D. 舍伍得算法
71. 对于n个元素的排序问题。n＝2时只要作（ C ）次比较即可排好序。 A. 3 B. 2 C. 1 D. 4
72. 一般地讲，当一个问题的所有子问题都至少要解一次时，用动态规划算法和备忘录算法相比：（ B ）。 A. 效果一样
B. 动态规划效果好 C. 备忘录方法效果好 D. 无法判断哪个效果好
73. 分支限界法与回溯法都是在问题的解空间树T上搜索问题的解，二者（ B ）。 A. 求解目标不同搜索方式相同 B. 求解目标不同搜索方式也不同 C. 求解目标相同搜索方式不同 D. 求解目标相同搜索方式也相同
74. 递归算法不能适用以下场合（ D ）。 A. 数据的定义形式按递归定义
B. 数据之间的关系即数据结构按递归定义 C. 问题解法按递归算法实现 D. 概率问题
75. 若当子问题之间包含公共的子子问题时，则分治法要做许多不必要的工作，重复地解公共的子问题，此时一般用（ A ）法较好。 A. 动态规划 B. 分治 C. 贪心 D. 概率
76. 分治法所能解决的问题应具有的关键特征是（ C ）。 A. 该问题的规模缩小到一定的程度就可以容易地解决 B. 该问题可以分解为若干个规模较小的相同问题
C. 利用该问题分解出的子问题的解可以合并为该问题的解 D. 该问题所分解出的各个子问题是相互独立的
77. 对于货箱装船问题根据贪心策略首先选择（ A ）的货箱然后选 （ A ）的货箱如此下去直到所有货箱均装上船或船上不能再容纳其他任何一个货箱。 A. 最轻 次轻 B. 最重 次重 C. 最轻 次重 D. 最重 次轻
78. 用回溯法解n后问题时，用完全n叉树表示解空间。可行性约束place剪去不满足行、列和斜线约束的子树，place中的if判断条件应为（ A ）。 A. (Math.abs(k-j)==Math.abs(x[j]-x[k]))||x[j]==x[k]) B. (Math.abs(k-j)==Math.abs(x[j]-x[k]))
C. (x[j]-x[k])
D. 以上都不正确
79. 分支限界法的搜索策略是：在扩展结点处，先生成其（ D ）儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。 A. 一个 B. 二个 C. 任意多个 D. 所有的
80. 能够用动态规划解决的问题还有一个显著特征（ D ）这个性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法相比就不具备优势。 A. 子问题的可求解性 B. 子问题的独立性 C. 子问题的可合并性 D. 子问题的重叠性
81. 在任何一个2?2的棋盘覆盖中，用到的L型骨牌个数恰为（ A ）。 A. (4k?1)/3 B. (4?1)/2 C. (2?1)/3 D. (2?1)/2
82. 以Bitonic旅行路线问题为例，动态规划的时间复杂度为（ C ）。 A. O(n) B. O(n!) C. O(n2) D. O(n3)
83. 一个算法应该包含如下几条性质除了（ A ）。 A．二义性 B．有限性 C．正确性 D． 可终止性
84. 解决一个问题通常有多种方法。若说一个算法“有效”是指（ D ）。
kkkkkA. 这个算法能在一定的时间和空间资源限制内将问题解决 B．这个算法能在人的反应时间内将问题解决 C．这个算法比其他已知算法都更快地将问题解决 D． A和C
85. 当输入规模为n时算法增长率最小的是（ B ） 。 A．5n B．20log2n C．2n D．3nlog3n
86．渐进算法分析是指（ B ） 。
A. 算法在最佳情况、最差情况和平均情况下的代价
B. 当规模逐步往极限方向增大时对算法资源开销“增长率”上的简化分析 C. 数据结构所占用的空间
D. 在最小输入规模下算法的资源代价
87．当上下限表达式相等时我们使用下列哪种表示法来描述算法代价?（ C ） A．大O表示法 B．大Ω表示法 C．Θ表示法 D． 小o表示法
88. 采用“顺序搜索法”从一个长度为N的随机分布数组中搜寻值为K的元素，以下对顺序搜 索法分析正确的是（ B ）。
A．最佳情况、最差情况和平均情况下顺序搜索法的渐进代价都相同 B．最佳情况的渐进代价要好于最差情况和平均情况的渐进代价 C．最佳情况和平均情况的渐进代价要好于最差情况的渐进代价
D．最佳情况的渐进代价要好于平均情况的渐进代价而平均情况的渐进代价要好于最差情况的渐进代价
89．递归通常用（ C ）来实现。 A. 有序的线性表 B. 队列 C. 栈 D. 数组
90. 分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题分别解决子问题最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题（ C ）。 A问题规模相同，问题性质相同 B问题规模相同，问题性质不同
2C问题规模不同，问题性质相同 D问题规模不同，问题性质不同 91．在寻找n个元素中第k小元素问题中如快速排序算法思想运用分治算法对n个元素进行划分如何选择划分基准下面（ D ）答案解释最合理。 A．随机选择一个元素作为划分基准 B．取子序列的第一个元素作为划分基准 C．用中位数的中位数方法寻找划分基准
D．以上皆可行。但不同方法算法复杂度上界可能不同
92. 对于01背包问题和背包问题的解法下面（ C ）答案解释正确。 A．01背包问题和背包问题都可用贪心算法求解
B．01背包问题可用贪心算法求解但背包问题则不能用贪心算法求解 C．01背包问题不能用贪心算法求解但可以使用动态规划或搜索算法求解而背包问题则可以用贪心算法求解
D．因为01背包问题不具有最优子结构性质所以不能用贪心算法求解
93．关于回溯搜索法的介绍下面（ D ）是不正确描述。
A．回溯法有“通用解题法”之称它可以系统地搜索一个问题的所有解或任意解 B．回溯法是一种既带系统性又带有跳跃性的搜索算法
C．回溯算法在生成解空间的任一结点时先判断该结点是否可能包含问题的解如果肯定不包含则跳过对该结点为根的子树的搜索逐层向祖先结点回溯
D．回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径
94. 关于回溯算法和分支限界法以下（ A ）是不正确描述。 A回溯法中每个活结点只有一次机会成为扩展结点
B分支限界法中活结点一旦成为扩展结点就一次性产生其所有儿子结点在这些儿子结点中那些导致不可行解或导致非最优解的儿子结点被舍弃其余儿子加入活结点表中 C回溯法采用深度优先的结点生成策略
D分支限界法采用广度优先或最小耗费优先最大效益优先的结点生成策略
95. 优先队列通常用以下（ B ）数据结构来实现。
A．栈 B．堆 C．队列
D．二叉查找树
96. 在分支限界算法中根据从活结点表中选择下一扩展结点的不同方式可有几种常用分类，以下（ D ）描述最为准确。
A采用FIFO队列的队列式分支限界法