第一章 单元测试
1、判断题：
算法是指解决问题的方法或过程，它包含一系列步骤，用来将输入数据转换成输出结果。
选项：
A:对
B:错
答案: 【对】
2、多选题：
使用伪代码描述算法具有（ ）等优点。
选项：
A:简单易懂
B:格式统一规范
C:容易修改
D:易于转化为程序语言代码
答案: 【简单易懂;容易修改;易于转化为程序语言代码】
3、多选题：
算法通常具有（ ）的性质。
选项：
A:输入：有零个或多个输入
B:确定性：组成算法的每条指令清晰、无歧义
C:有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限
D:输出：至少有一个输出
答案: 【输入：有零个或多个输入;确定性：组成算法的每条指令清晰、无歧义;有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限;输出：至少有一个输出】
4、判断题：
程序是算法用某种程序设计语言的具体实现，程序需满足算法的所有性质。
选项：
A:对
B:错
答案: 【错】
5、多选题：
常用的描述算法的形式有（ ）。
选项：
A:机器语言
B:程序流程图
C:自然语言
D:伪代码
答案: 【程序流程图;自然语言;伪代码】
6、单选题：
函数f(n)=20log3^n的渐进表达式是（ ）。
选项：
A:0(log(n))
B:0（n^2）
C:O(n)
D:0(1)
答案: 【O(n)】
7、多选题：
一个算法的优劣由（ ）决定。
选项：
A:代码长度
B:时间复杂度
C:使用的编程语言
D:空间复杂度
答案: 【时间复杂度;空间复杂度】
8、判断题：
如果存在正的常数C和自然数N0,使得当N≥N0时有f(N)≤Cg(N),则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(N)),即f(N)的阶不高于g(N）的阶。
选项：
A:错
B:对
答案: 【对】
9、单选题：
分析以下代码的时间复杂度：
int func(int n)
{
int i=1, k=0;
while(i<=n) {
k++;
i=i*2;
}
return k;
}
选项：
A:O(logn)
B:O(n)
C:O(n^2)
D:O(n/2)
答案: 【O(logn)】
10、多选题：
对于f(n)=n，下列说法正确的是（ ）。
选项：
A:f(n)=O(n^2)
B:f(n)=O(1/n)
C:f(n)=O(n)
D:f(n)=O(n^3)
答案: 【f(n)=O(n^2);f(n)=O(n);f(n)=O(n^3)】
第二章 单元测试
1、判断题：
递归函数是指在一个函数体中出现直接或间接调用该函数自身的函数。
选项：
A:对
B:错
答案: 【对】
2、单选题：
已知f(1)=1，f(n)=f(n-1)+n，那么f(50)的作用是( )。
选项：
A:计算1到50的和。
B:计算斐波拉契数列的第50个元素的值。
C:计算1到50的乘积。
D:计算50个1的和。
答案: 【计算1到50的和。】
3、多选题：
递归的优点包括( )。
选项：
A:结构清晰
B:容易用数学归纳法来证明算法的正确性
C:运行效率高
D:可读性强
答案: 【结构清晰;容易用数学归纳法来证明算法的正确性;可读性强】
4、单选题：
在经典的汉诺塔问题中，如果有5个圆盘需要从A柱移至C柱，最少需要移动( )步。
选项：
A:32
B:31
C:41
D:28
答案: 【31】
5、多选题：
分治法能解决的问题一般具有（ ）等特征。
选项：
A:该问题缩小到一定程度时可以容易地解决
B:最优子结构
C:分解出的子问题的解可以合并为原问题的解
D:子问题相互独立
答案: 【该问题缩小到一定程度时可以容易地解决;最优子结构;分解出的子问题的解可以合并为原问题的解;子问题相互独立】
6、判断题：
在使用分治法设计算法时，最好使子问题的规模大致相同，即将一个问题分成大小相等的多个子问题的处理方法是行之有效的。
选项：
A:错
B:对
答案: 【对】
7、单选题：
给定递归公式T(n)=4T(n/2)+O(n),由主定理可以得知T(n)=( )。
选项：
A:O(n^2)
B:O(nlogn)
C:O(n)
D:O(logn)
答案: 【O(n^2)】
8、单选题：
已知某楼房共20层，如果采用二分查找，请问最多猜( )次就能猜出任意一个楼层。
选项：
A:6
B:5
C:4
D:3
答案: 【5】
9、多选题：
关于快速排序的时间复杂度，( )是正确的。
选项：
A:在最坏情况下时间复杂度为O(n^2)
B:在平均情况下时间复杂度为O(nlogn)
C:在最好情况下时间复杂度为O(nlogn)
D:在平均情况下时间复杂度为O(n^2)
答案: 【在最坏情况下时间复杂度为O(n^2);在平均情况下时间复杂度为O(nlogn);在最好情况下时间复杂度为O(nlogn)】
10、单选题：
快速排序是对传统排序算法( )的一种改进。
选项：
A:冒泡排序
B:插入排序
C:选择排序
D:归并排序
答案: 【冒泡排序】
第三章 单元测试
1、多选题：
能够使用动态规划算法来求解的问题通常需要具备两个重要的性质，它们分别是( )。
选项：
A:递归调用
B:重叠子问题
C:最优子结构
D:贪心选择性质
答案:
2、多选题：
关于备忘录法，以下说法正确的是( )。
选项：
A:备忘录法为每个解过的子问题建立备忘录以备需要时查看，又称查表法。
B:备忘录法又称为记忆化搜索，它采用一种自底向上的方式求解问题。
C:备忘录法的控制结构与直接使用递归方法的控制结构相同。
D:备忘录法可以避免相同子问题的重复求解。
答案:
3、单选题：
字符序列abcde与字符序列abdge的最长公共子序列长度为( )，最长公共子串长度为( )。
选项：
A:4,1
B:3,5
C:4,2
D:4,6
答案:
4、单选题：
使用动态规划算法求两条长度分别为m和n的序列的最长公共子序列，其时间复杂度为( )。
选项：
A:O(n*m)
B:O(m^n)
C:O(n^2)
D:O(nlogm)
答案:
5、单选题：
输入数组（-1, 0, 1, -2, 3），它的最大子段和是( )。
选项：
A:4
B:2
C:1
D:3
答案:
6、单选题：
序列（1，7，3，4，9，2，3）的最长递增子序列的长度为( )。
选项：
A:2
B:4
C:3
D:1
答案:
7、单选题：
使用穷举法求解最长递增子序列的时间复杂度为( )。
选项：
A:O(nlogn)
B:O(n^2)
C:O(n*2^n)
D:O(n^n)
答案:
8、单选题：
使用动态规划算法求最大子段和的时间复杂度为( )。
选项：
A:O(n)
B:O(logn)
C:O(nlogn)
D:O(2^n)
答案:
9、多选题：
某工厂预计明年有A,B,C,D四个新建项目，每个项目的投资额分别为15,10,12,8（万元），投资收益分别为12,8,9,5（万元），投资总额为30万元，选择项目( )可以使总收益最大。（不允许部分投资某个项目）
选项：
A:D
B:A
C:B
D:C
答案:
10、判断题：
在使用动态规划算法求解0-1背包问题时，若m[i][j]=m[i+1][j-w[i]]+v[i]，说明第i个物品在剩余背包容量为j时可以装入，并且装入比不装入的背包总价值更大，装入后，背包剩余容量减少w[i]，价值增加v[i]。
选项：
A:对
B:错
答案:
第四章 单元测试
1、多选题：
能够使用贪心算法求解的问题需具备的基本要素包括( )。
选项：
A:贪心选择性质
B:递归调用
C:重复子问题
D:平衡子问题
E:最优子结构性质
答案:
2、多选题：
下列关于贪心算法与动态规划算法说法正确的是( )。
选项：
A:贪心算法与动态规划算法的主要区别是贪心算法要求问题具有贪心选择性质
B:贪心算法与动态规划算法的主要区别是动态规划算法要求问题具有贪心选择性质
C:贪心算法与动态规划算法求解的问题都具备最优子结构性质
D:贪心算法与动态规划算法求解的问题都具有重复子问题性质
答案:
3、单选题：
在解决活动安排问题时应首先对活动进行排序，排序的依据是( )。
选项：
A:按照活动开始时间降序排列
B:按照活动结束时间降序排列
C:按照活动开始时间升序排列
D:按照活动结束时间升序排列
答案:
4、单选题：
使用贪心算法求解最优装载问题，其时间复杂度为( )。
选项：
A:O(n2n)
B:O(n3n)
C:O(nlogn)
D:O(n5n)
答案:
5、多选题：
( )能够使用贪心算法求解。
选项：
A:0-1背包问题
B:最小生成树问题
C:单源最短路径问题
D:活动安排问题
E:部分背包问题
F:最优装载问题
答案:
6、多选题：
0-1背包问题与部分背包问题的区别在于( )。
选项：
A:若用贪心算法解决部分背包问题，只能得到近似最优解
B:在0-1背包问题中，物品只有装入和不装入两种情况，而部分背包问题允许只装入物品的一部分
C:没有区别，它们的含义相同
D:若用贪心算法解决0-1背包问题，只能得到近似最优解
答案:
7、单选题：
在求解部分背包问题时采用的贪心策略是( )。
选项：
A:选择重量最轻的物品
B:选择单位重量下价值最大的物品
C:选择单位价值下重量最大的物品
D:选择价值最大的物品
答案:
8、多选题：
Dijkstra算法可用于求解( )。
选项：
A:单源最短路径问题
B:每对顶点间最短路径问题
C:单终点最短路径问题
D:单对顶点最短路径问题
答案:
9、判断题：
Prim算法适合稀疏图，其时间复杂度只与边的数目有关。
选项：
A:错
B:对
答案:
10、单选题：
在对Dijkstra算法进行初始化时，如果两个顶点之间没有边，则它们之间的距离为( )。
选项：
A:无穷大
B:0
C:无穷小
D:-1
答案:
第五章 单元测试
1、多选题：
回溯法中的剪枝函数包括( )。
选项：
A:递归函数
B:随机数生成函数
C:约束函数
D:限界函数
E:虚函数
F:静态函数
答案:
2、单选题：
回溯法采用的搜索策略是( )。
选项：
A:启发式搜索
B:层次搜索
C:广度优先搜索
D:深度优先搜索
答案:
3、判断题：
回溯法的主要用途包括求问题的所有解、求问题的最优解和求问题的任一解。
选项：
A:对
B:错
答案:
4、多选题：
马的遍历问题能否有可行解，与( )有关。
选项：
A:马的遍历顺序
B:棋盘大小
C:马的初始位置
D:马的遍历深度
答案:
5、多选题：
在N皇后问题中，需要将棋盘当做一个二维数组来分析，对于该二维数组，以下说法正确的是( )。
选项：
A:对于任意一条右斜线上的两个点，它们的横坐标和纵坐标相加的值相同。
B:对于任意一条左斜线上的两个点，它们的横坐标和纵坐标相减的值相同。
C:对于任意一条左斜线上的两个点，它们的横坐标和纵坐标相加的值相同。
D:对于任意一条右斜线上的两个点，它们的横坐标和纵坐标相减的值相同。
答案:
6、判断题：
四皇后问题一共有2个可行解，八皇后问题一共有76个可行解。
选项：
A:错
B:对
答案:
7、单选题：
用m种颜色给n个顶点着色、且使一条边的两个顶点颜色不同，则对应的解空间树是一棵( )。
选项：
A:高为n的n叉树
B:高为m的n叉树
C:高为n的m叉树
D:高为m的m叉树
答案:
8、单选题：
任何一张地图只用( )种颜色就能使具有共同边界的国家着上不同的颜色。
选项：
A:2
B:3
C:4
D:6
答案:
9、判断题：
使用回溯法求解0-1背包问题时，计算右子树上界的方法是通过贪心策略求得上界，即将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包，此时得到的价值就是右子树中解的上界。
选项：
A:错
B:对
答案:
10、多选题：
关于使用回溯法求解0-1背包问题，以下说法正确的是( )。
选项：
A:使用限界函数剪去得不到更优解的右子树（不装该物品）。
B:使用约束函数剪去不合理的左子树（装该物品）。
C:使用约束函数剪去不合理的右子树（不装该物品）。
D:使用限界函数剪去得不到更优解的左子树（装该物品）。
答案:
第六章 单元测试
1、单选题：
分支限界法采用的搜索策略是( )。
选项：
A:启发式搜索
B:深度优先搜索
C:递归搜索
D:广度优先搜索
答案:
2、多选题：
根据活结点表的组织方式不同，分支限界法包括( )等形式。
选项：
A:二叉树式分支限界法
B:队列式分支限界法
C:栈式分支限界法
D:单调队列式分支限界法
E:优先队列式分支限界法
答案:
3、多选题：
关于回溯法和分支限界法，以下说法正确的是( )。
选项：
A:分支限界法通常用于求满足约束条件的一个解或特定意义下的最优解
B:在回溯法中，活结点的所有可行子结点均被遍历后才从栈中弹出
C:在分支限界法中，每个结点只有一次成为扩展结点的机会
D:回溯法通常用于求满足约束条件的所有解
答案:
4、多选题：
应用分支限界法的三个关键问题包括( )。
选项：
A:如何限制搜索的层次
B:如何组织活结点表
C:如何设计合适的剪枝函数
D:如何确定最优解的解向量
答案:
5、多选题：
关于分支限界法的基本思想，下列描述正确的是( )。
选项：
A:那些导致不可行解或导致非最优解的子结点被舍弃，其余子结点被加入活结点表中
B:一直持续到找到所求的解或活结点表为空时为止
C:活结点一旦成为扩展结点，就一次性产生其所有子结点
D:每一个活结点只有一次机会成为扩展结点
E:从活结点表中取下一结点成为当前扩展结点，并重复结点扩展过程
答案:
6、判断题：
优先队列式分支限界法将活结点表组织成一个优先队列，按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。
选项：
A:对
B:错
答案: 7、单选题：
队列具有( )的性质。
选项：
A:先进后出
B:先进先出
C:仅进不出
D:进出无序
答案:
8、判断题：
使用队列式分支限界法求解装载问题时，每次从队列Q中取出队首元素作为当前扩展结点。取队首元素后，判断当前Q是否为空。如Q非空，则将尾部标记-1加入Q，算法开始处理下一层的活结点。
选项：
A:对
B:错
答案:
9、判断题：
如果一个给定装载问题有解，则采用的装载策略为：首先将第一艘轮船尽可能装满；再将剩余的集装箱装上第二艘轮船。
选项：
A:错
B:对
答案:
10、单选题：
在装载问题中，如果右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量，则当( )时，可将其右子树剪去。
选项：
A:ew+r<=bestw
B:r<bestw
C:ew+r>bestw
D:r>=bestw
答案:
请先 ！