1、6、 活动选择问题就是在所给的活动集合中，选出（ ）的相容活动子集。 A、当前可选活动中结束时间最早的活动 B、当前可选活动中开始时间最早的活动 C、当前可选活动中冲突数量最少的活动 D、当前可选活动中持续时间最长的活动7、一个长度为n英寸的钢管的最优切割问题，总共有（ ）个不同的子问题。 A、n+1 B、n2 C、nlogn D、logn8、 最优二叉搜索树的时间复杂度为（ ）。 A、O（n） B、O（n!） C、O（n2） D、O（nlogn）9、 算法的每种运算必须要有确切的定义,不能有二义性,以下符合算法确定性运算的是（ ） A、5/0 B、将6或7与x相加 C、未赋值变量参与运算 D
2、、f（n）=f（n-1）+2,f（1）=10,n为自然数10、 对于三个物体的背包问题，问题相关的数据为n=3, M=20,P=（25,24,15）,W（18,15,10）。 下面给出的四个可行解中，最好的是（ ） A、（1/2，1/3，1/4） B、（1，2/15，0） C、（0，2/3，1） D、（0，1，1/2）11、 递归函数f（n）=f（n-1）+n（n1）的递归出口是（ ）。 A、f（0）=0 B、f（1）=1 C、f（0）=1 D、f（n）=n12、下面关于快速排序的说法，正确的是（ ）快速排序的速度和数据无关，是一个固定的值快速排序的速度在分解的均匀的时候效果最好，速度最快快速
3、排序主要的时间花在合并上面快速排序在分解均匀的适合速度最慢13、 下面关于货郎担问题的描述，正确的是（ ） A、货郎担问题是求取具有最大成本的周游路线问题 B、货郎担问题适合使用贪心算法求问题的最优解 C、货郎担问题存在多项式时间算法 D、货郎担问题可以通过动态规划算法实现14、 实现快速排序算法如下： QuickSort （A, p, r）IF p Max MaxAi;else if AiMin MinAi;return Max,Min其时间复杂度是（ ）。2n2（n-1）3n3（n-1）31、 快速排序法的基本思想是对输入的数组按以下三个步骤进行排序（ ）。 A、分解，合并，递归求解 B、
4、合并，递归求解，分解 C、递归求解，分解，合并 D、分解，递归求解, 合并32、 合并排序法的基本思想是：将待排序元素分成大小大致相同的（ ）个子集合，分别对每个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。 A、4 B、3 C、2 D、533、 在最优二叉搜索树问题中，我们的优化目标是（ A、只经过最少次数的比较就可以找到概率最大的元素 B、经过最多次数的比较就可以找到概率最小的元素 C、找到每个元素所需要的平均比较次数为最小 D、元素搜索代价的数学期望为最小34、 下面是贪心算法的基本要素的是（ A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解35、 分
5、治法所能解决的问题应具有的关键特征是（ ）。 A、该问题的规模缩小到一定的程度就可以容易地解决 B、该问题可以分解为若干个规模较小的相同问题 C、利用该问题分解出的子问题的解可以合并为该问题的解 D、该问题所分解出的各个子问题是相互独立的36、 T（n）=2n3+10n2log（n）+30n的渐近时间复杂度为（ ）。 A、O（n2log（n） B、O（n4） C、O（n3）37、 在钢管切割问题里，如果用rn表示长度为n英寸的钢管的最优切割方案所获得的最大收益，且已知rn所代表的最优解里，第一刀切下了3英寸，则下述公式正确的是（ ）。 A、rn = p3 + rn-3 B、rn = rn 3
6、C、rn = rn-3 + 3 D、rn = r3 + p338、 （ ）是贪心算法与动态规划算法的共同点。 D、最优子结构性质39、下列关于选择排序和冒泡排序的稳定性的说法，正确的是（ ）。选择排序是稳定的，冒泡排序是稳定的。选择排序是不稳定的，冒泡排序是不稳定的。选择排序是稳定的，冒泡排序是不稳定的。40、 Edmonds-Karp算法中寻找增广路径的方法是（ A、深度优先算法 B、广度优先算法 C、Prim算法 D、Dijkstra算法41、使用分治法求解不需要满足的条件是（ ）。 A、子问题必须是一样的42、 在流网络中，对于源节点，从其它节点流进去的流与从该节点流向其它节点的流是相等
7、的。 A、在流网络中，对于任何节点，从其它节点流进去的流与从该节点流向其它节点的流是相等的。在流网络中，对于汇节点，从其它节点流进去的流与从该节点流向其它节点的流是相等的。 C、在流网络中，对于非源和非汇的节点，从其它节点流进去的流与从该节点流向其它节点的流是相等的。 D、在流网络中，对于非源和非汇的节点，从其它节点流进去的流与从该节点流向其它节点的流是相等的。43、 在矩阵连乘问题的动态规划解决方案里，我们的所做的顶层决策是（ A、第一次矩阵乘法发生的位置 B、最后一次矩阵乘法发生的位置 C、结果矩阵维数最小的位置 D、结果矩阵列数最小的位置44、 关于0-1背包问题的下述形式化公式描述：下
8、述说法不正确的是（ ）。 A、i 表示物品的重量 B、C表示背包容量 C、xi=0表示编号为i的物品不被选择 D、求解目标是最大化装入背包内的物品的总价值45、 在活动安排问题中，如果把全部活动按照结束时间递增序排序后，按贪心算法，我们总是安排 （46、找零钱问题中，定义 Cj为兑换j 所需要的硬币的最少数量，考虑下述递归表达式，下列关于对i的寻优的最恰当描述是（ A、考虑找出的第一个硬币面值的各种可能性 B、考虑先找给客户几分钱 C、考虑最多可以用几个硬币 D、考虑最少可以用几个硬币47、 Huffman编码问题中，我们的优化目标是（ A、所有字符编码长度的数学期望为最小 B、给频度高的字符
9、以最短的编码 C、给频度最低的字符以最长的编码 D、给每个字符相同长度的编码48、 一个有n个结点的带权无向图，其生成树应有（ ）条边。 A、n B、n-1 D、n/249、 算法必须具备输入、输出和（ ）等5个特性。 A、可执行性、可移植性和可扩充性 B、可行性、确定性和有穷性 C、确定性、有穷性和稳定性 D、易读性、稳定性和安全性50、 当问题的规模n趋向无穷大时，（ ）的数量级（阶）称为算法的渐进时间复杂度。 A、时间复杂度 B、空间复杂度 C、冗余度 D、迭代次数51、 对于n个元素的排序问题，n2时,只要作（ ）次比较即可排好序。 A、3 B、2 C、1 D、452、 递归算法不能适
10、用以下场合（ ）。 A、数据的定义形式按递归定义 B、数据之间的关系（即数据结构）按递归定义 C、问题解法按递归算法实现 D、概率问题53、 在最优二叉搜索树问题中，定义ei, j 为 ki,.,kj的最优二叉查找树的期望搜索成本，而我们需要通过寻优来确定最优二叉查找树的根结点的下标r,则r的取值范围为（ ）。 A、irj B、 irj C、ir D、ian/2 D、x=an/256、 下列算法中通常以自底向上的方式求解最优解的是（ A、备忘录法57、备忘录方法的递归方式是 （自顶向下自右向左忽上忽下自底向上58、 算法指的是（ ）。 A、计算方法 B、排序方法 C、解决问题的方法和过程 D、
11、调度方法59、应用Johnson法则的流水作业调度采用的算法是（ ） A、贪心算法分治法动态规划算法60、 贪心算法与动态规划算法的主要区别是（ A、最优子结构 B、贪心选择性质 C、构造最优解61、对于矩阵链连乘的子问题mi,j，当i=j时表明该矩阵链有两个矩阵。 正确 错误错误62、算法就是一组无穷的规则（ ）63、问题的规模越小，解题所需的计算时间往往也越少，从而也较容易处理。正确64、动态规划和分治法在分解子问题方面的不同点是前者分解出的子问题有重叠的，而后者分解出的子问题是相互独立（不重叠）的（ ）。65、每一个递归定义都有其边界条件。66、 贪心算法并不从整体最优考虑,它所做出的选
12、择只是在某种意义上的局部最优选择。67、用浮点数来表示大型整数，只能近似地表示它的大小（ ）68、多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果。69、 子问题之间不包含公共的子问题，这个条件涉及到分治法的效率。70、裴波那契数列的定义：f（n）=f（n-1）+f（n-2）,f（0）=1,f（1）=2，其数据的定义形式不是按递归定义。71、程序性能是指运行一个程序所需的内存大小和时间多少。72、一个操作所需的时间和操作数的类型无关（ ）73、 要想在电脑上扩大所处理问题的规模，有效的途径是降低算法的计算复杂度。74、 在JAVA语言中,执行特定
13、认为的任务的函数或过程统称为方法。75、与分治法不同的是，适合于用动态规划求解的问题经分解得到子问题往往是互相不独立的（ ）。76、归并排序是指将数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一个含n个元素的分好类的序列。如果分割后子问题还很大，则继续分治，直到一个元素。 （ ）77、与分治法不同的是，适合于用动态规划求解的问题经分解得到子问题往往是互相独立的（ ）。78、对所有问题,贪心算法不能都得到整体最优解 （ ）。79、算法重要特性是确定性、可实现性、输入、输出、有穷性（ ）。80、 0-1背包问题，无论物件的顺序如何排列，动态规划总能获得最优解。81、指数时间算法
14、只有在n取值非常小时才实用。82、 动态规划法其具体形式是多种多样的，但都具有相同的填表格式。83、 一般来说，对一个有序序列二分法（即把任意大小的问题尽可能地等分为两个子问题）较为有效。84、 如果各子问题是不独立的，一般用动态规划法比分治法较差。85、动态规划对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。86、 当一个问题具有最优子结构性质时只能用动态规划方法求解。87、Huffmann编码树所对应的编码并不一定是前缀码。88、 通常，在分析一个算法的计算复杂性时，都将加法和乘法运算当作是基本运算来处理。89、 问题的计算复杂性一般是随着问题规模的增加而减小。90、 子问题之间不包含公共的子问题，这个条件涉及到分治法的效率。91、Prim算法是一种动态规划算法。92、 标准动态规划是在研究多阶段决策问题时推导出来的，具有严格的数学形式，适合用于理论上的分析。93、 问题解法按递归算法实现的问题适用于递归求解。94、一般认为，执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处理速度的常数。 ）95、 如果一类活动过程一个阶段的决策确定以后，常影响到下一个阶段的决策，则称它为多阶段决策问题。96、对于矩阵链连乘的子问题mi,j，其对应的si,j用于记录该矩阵链最后一次乘法发生的位置。
