第一章 单元测试
1、判断题：
算法就是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。
选项：
A:错
B:对
答案: 【对】
2、判断题：
计算机的资源最重要的是内存和运算资源。因而，算法的复杂性有时间和空间之分。
选项：
A:错
B:对
答案: 【对】
3、判断题：
时间复杂度是指算法最坏情况下的运行时间。
选项：
A:错
B:对
答案: 【错】
4、单选题：
下面关于算法的说法中正确的是（ ）。
（1）求解某一问题的算法是唯一的。
（2）算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。
（3）算法的每一条指令是清晰无歧义的。
（4）算法可以用某种程序设计语言具体实现，所以算法和程序是等价的。
选项：
A:（2）（3）
B:（1）（3）
C:（2）（4）
D:（1）（2）
答案: 【（2）（3）
】
5、单选题：
描述算法的基本方法有（ ） 。
（1）自然语言
（2）流程图
（3）伪代码
（4）程序设计语言
选项：
A:（1）(2)（3）(4)
B:（1）（2）（3）
C:（2）（3）(4)
D:（1）（3）(4)
答案: 【（1）(2)（3）(4)
】
6、单选题：
算法分析是（ ）。
选项：
A:将算法用某种程序设计语言恰当地表示出来
B:证明算法对所有可能的合法出入都能算出正确的答案
C:对算法需要多少计算时间和存储空间作定量分析
D:在抽象数据数据集合上执行程序，以确定是否产生错误结果
答案: 【对算法需要多少计算时间和存储空间作定量分析
】
7、单选题：
下面算法段所需计算时间的下界为（ ）。 其中odd(n)，判断n是否为奇数，若是则返回值为真，否则为假。 while(n>1) if(odd(n)) n=3*n+1; else n=n/2;
选项：
A:logn
B:n3
C:n2
D:3n
答案: 【logn】
8、单选题：
下面函数中增长率最低的是（ ）。
选项：
A:logn
B:n2
C:2n
D:n
答案: 【logn】
9、多选题：
下面属于算法的特性有( )。
选项：
A:确定性：组成算法的每条指令是清晰，无歧义的。
B:输入：有0个或多个外部量作为算法的输入。
C:有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。
D:输出：算法产生至少一个量作为输出。
答案: 【确定性：组成算法的每条指令是清晰，无歧义的。
;输入：有0个或多个外部量作为算法的输入。
;有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。
;输出：算法产生至少一个量作为输出。
】
10、单选题：
10.下面算法的时间复杂度为（ ）。 int sum(int n) { if(n == 1) return 1; else return n + sum(n-1); }
选项：
A:O(1)
B:O(logn)
C:
O(n2)
D:O(n)
答案: 【O(n)】
第二章 单元测试
1、判断题：
直接或间接调用自身的算法称为递归算法。（ ）
选项：
A:错
B:对
答案: 【对】
2、判断题：
递归算法的基本原则包括基准情形、不断推进、设计法则和合成效益法则。（ ）
选项：
A:错
B:对
答案: 【对】
3、判断题：
使用分治法解决的一个问题时，需要将一个大的问题分解成若干个子问题，这些子问题可以和原问题相同，也可以不同。（ ）
选项：
A:对
B:错
答案: 【错】
4、判断题：
适合于用分治法求解的问题，经分解得到的子问题可以不是互相独立的。（ ）
选项：
A:对
B:错
答案: 【错】
5、单选题：
设当n＞1时，T（n）=2T（n/2）+O（n），则此分治法的时间复杂度为（ ）。
选项：
A:Θ(n2)
B:Θ（n）
C:Θ（nlogn）
D:Θ（logn）
答案: 【Θ（nlogn）
】
6、单选题：
设当n＞1时，T（n）=27T（n/3）+O（n2），则此分治法的时间复杂度为（ ）。
选项：
A:Θ（n2logn）
B:Θ（n）
C:Θ(n3)
D:Θ（n2）
答案: 【Θ(n3)】
7、单选题：
二分查找有序表（2，8，13，24，33，41，52，58，63，100 ），若查找表中元素51，则其依次和表中元素（ ）进行比较，查找结果是失败。
选项：
A:33，9，41，52
B:56，41，52
C:33，56，41，52
D:56，52
答案: 【33，56，41，52
】
8、单选题：
对于棋盘覆盖问题的分治算法，使用主定理进行算法分析时，k、m、d的值分别为（ ）。
选项：
A:k=2，m=4，d=1
B:k=4，m=2，d=0
C:k=4，m=2，d=1
D:k=2，m=4，d=0
答案: 【k=4，m=2，d=0
】
9、单选题：
下列选项中，不可能是快速排序第2趟排序结果的是（ ）。
选项：
A:{2，7，5，6，4，3，9}
B:{2，3，5，4，6，7，9}
C:{3，2，5，4，7，6，9}
D:{4，3，2，5，7，6，9}
答案: 【{3，2，5，4，7，6，9}
】
10、单选题：
采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是（ ）。
选项：
A:递归次数与初始初始数据的排列次序无关
B:递归次数与每次划分后得到的分区处理顺序无关
C:每次划分后，先处理较短的分区可以减少递归次数
D:每次划分后，先处理较长的分区可以减少递归次数
答案: 【递归次数与每次划分后得到的分区处理顺序无关
】
第三章 单元测试
1、判断题：
动态规划算法是以空间换时间的时空权衡技术（ ）。
选项：
A:错
B:对
答案: 【】
2、判断题：
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。（ ）
选项：
A:对
B:错
答案: 【】
3、判断题：
适合于用动态规划法求解的问题，经分解得到的子问题不是互相独立的。（ ）
选项：
A:对
B:错
答案: 【】
4、判断题：
0-1背包问题实例的动态规划表中某一行值的序列总是非递减的（ ）。
选项：
A:对
B:错
答案: 【】
5、判断题：
求解某一问题的算法是唯一的。
选项：
A:对
B:错
答案: 【】
6、单选题：
下列算法通常以自底向上的方式求解的是（ ）。
选项：
A:回溯法
B:贪心法
C:备忘录法
D:动态规划算法
答案: 【
】
7、单选题：
下列是动态规划基本要素的是（ ）
选项：
A:子问题重叠性质
B:构造最优解
C:算出最优解
D:定义最优解
答案: 【
】
8、单选题：
一个问题使用动态规划算法的关键特征是（ ）。
选项：
A:最优子结构性质
B:定义最优解
C:贪心选择性质
D:重叠子问题
答案: 【
】
9、单选题：
备忘录法是（ ）的变形。
选项：
A:回溯法
B:动态规划
C:贪心法
D:分治法
答案: 【
】
10、单选题：
要计算矩阵连乘积A1A2A3A4A5A6，其中各矩阵维数分别为A1（30×35），A2（35×15），A3（15×5），A4（5×10），A5（10×20），A6（20×25）。使用动态规划算法，记录最优值的数组中，元素m[2][4]的值为（ ）。
选项：
A:6000
B:2625
C:750
D:4375
答案: 【
】
第四章 单元测试
1、判断题：
贪心算法一定能产生最优解。（ ）
选项：
A:错
B:对
答案: 【】
2、判断题：
贪心算法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须消耗的大量时间。（ ）
选项：
A:错
B:对
答案: 【】
3、判断题：
贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。（ ）
选项：
A:错
B:对
答案: 【】
4、单选题：
下列算法中通常以自底向上的方式求解最优解的是( )
选项：
A:动态规划法
B:回溯法
C:贪心法
D:分治法
答案: 【
5、单选题：
背包问题的贪心算法所需的计算时间为( )
选项：
A:O(n2^n)
B:O(2^n)
C:O(nlogn)
D:O(n)
答案: 【】
6、单选题：
采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为( )
选项：
A:O(n)
B:O(nlogn)
C:O(2^n)
D:O(n2^n)
答案: 【】
7、判断题：
如果e是加权连通图中权重最小的边，它必定是图的每一棵最小生成树的边。( )
选项：
A:对
B:错
答案: 【】
8、判断题：
Prim算法是一种为加权连通图构造最小生成树的贪心算法。（ ）
选项：
A:错
B:对
答案: 【】
9、判断题：
Kruskal算法按照权重的升序把边包含进来，以构造最小生成树,并使得这种包含不会产生回路。为了保证这种检查的效率，需要应用一种所谓的并查算法。（ ）
选项：
A:对
B:错
答案: 【】
10、判断题：
对于不含有负权重值的图，Dijkstral算法总能产生一个正确的解。（ ）
选项：
A:错
B:对
答案: 【】
第五章 单元测试
1、单选题：
回溯法在问题的解空间树中，按（ ）策略，从根结点出发搜索解空间树。
选项：
A:扩展结点优先
B:广度优先
C:深度优先
D:活结点优先
答案: 【
】
2、单选题：
回溯法的算法框架按照问题的解空间一般分为子集树算法框架与（ ）算法框架。
选项：
A:排列树
B:二叉树
C:深度优先生成树
D:广度优先生成树
答案: 【】
3、判断题：
判断：回溯算法是尝试搜索算法中最为基本的一种算法，其采用了一种走不通就掉头的思想作为其控制结构。（ ）
选项：
A:错
B:对
答案: 【】
4、单选题：
用回溯法解0/1背包问题时，该问题的解空间结构为（ ）结构。
选项：
A:排列树
B:子集树
C:都可以
D:都不对
答案: 【】
5、单选题：
旅行售货员问题的解空间树是（ ）。
选项：
A:排列树
B:子集树
C:都可以
D:都不对
答案: 【】
6、单选题：
下面哪种函数是回溯法中为避免无效搜索采取的策略（ ）
选项：
A:递归函数
B:剪枝函数
C:随机数函数
D:搜索函数
答案: 【】
7、单选题：
回溯法的效率不依赖于下列哪些因素（ ）
选项：
A:确定解空间的时间
B:计算约束函数的时间
C:满足显约束的值的个数
D:计算限界函数的时间
答案: 【
】
8、单选题：
关于回溯搜索法的介绍下面（ ）是不正确描述。
选项：
A:回溯算法在生成解空间的任一结点时先判断该结点是否可能包含问题的解如果肯定不包含则跳过对该结点为根的子树的搜索逐层向祖先结点回溯
B:回溯法是一种既带系统性又带有跳跃性的搜索算法
C:回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径
D:回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解。
答案: 【
】
9、单选题：
用回溯法求解子集树问题，子集树有2^n个叶结点，遍历该子集树的算法时间复杂度通常为（ ）
选项：
A:O(n)
B:O(n^2)
C:O(2^n)
D:O(logn)
答案: 【】
10、单选题：
回溯法主要有迭代回溯法和（ ）回溯法两种编程实现方法。
选项：
A:并行
B:深度优先
C:递归
D:非递归
答案: 【
第六章 单元测试
1、单选题：
分支限界法在问题的解空间树中，按（ ）策略，从根结点出发搜索解空间树
选项：
A:扩展结点优先
B:活结点优先
C:深度优先
D:广度优先
答案: 【】
2、单选题：
常见的两种分支限界法为（ ）
选项：
A:广度优先分支限界法和深度优先分支限界法
B:排列树法和子集树法
C:队列式（FIFO）分支限界法与优先队列式分支限界法
D:队列式（FIFO）分支限界法与堆栈式分支限界法
答案: 【
】
3、单选题：
优先队列式分支限界法选取扩展结点的原则是（ ）。
选项：
A:结点的优先级
B:后进先出
C:随机
D:先进先出
答案: 【】
4、单选题：
分支限界法的搜索策略是：在扩展结点处，先生成其（ ）儿子结点（分支），然后再从当前的活结点表中选择下一个扩展对点。
选项：
A:二个
B:一个
C:所有的
D:任意多个
答案: 【
】
5、单选题：
优先队列式分支限界法通常用以下（ ）数据结构来实现。
选项：
A:二叉查找树
B:栈
C:堆
D:队列
答案: 【
6、判断题：
判断：分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法，两者的求解目标是相同的。（ ）
选项：
A:错
B:对
答案: 】
7、判断题：
判断：旅行商问题中，分支限界法的目标是找出满足约束条件的所有解。（ ）
选项：
A:错
B:对
答案: 【
8、判断题：
判断：优先队列式分支限界为了加速搜索的进程，按照优先队列中规定的优先级，选取优先级最高的结点，成为当前扩展结点。（ ）
选项：
A:对
B:错
答案: 【】
9、判断题：
判断：优先队列式分支限界法中，限界函数的选择将影响算法性能。（ ）
选项：
A:对
B:错
答案: 【】
10、单选题：
用分支限界法设计算法的步骤不包括：（ ）
选项：
A:针对所给问题，定义问题的解空间
B:确定易于搜索的解空间结构
C:定义最优子结构
D:以广度优先或以最小耗费（最大收益）优先的方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
答案: 【】
请先 ！