2019年本院真题，所有题目均已附上答案和个人分析。因为没有从老师那里要到答案，可能有些地方的解答表述不太妥当，但也足够解答题目了。这里把题目和解析一是为了自己日后算法比赛的快速复习回忆知识点，另一是为了造福在算法苦海中苦苦挣扎的各位同学。
希望本文能发挥它该有的作用，如发现任何表述或逻辑问题，请私信我或在下方评论区回复。
一、选择
1、关于NP问题说法正确的是（）
A、NP问题都是不可能解决的问题
B、P类问题包含在NP类问题中
C、NP完全问题是P类问题的子集
D、NP类问题包含在P类问题中
答案：B
解析：P类问题包含在NP类问题中。至于NPC问题，是NP问题中可在多项式时间复杂度中分析的问题，而P类问题是在多项式时间可解决。
2、算法分析中,记号Ω表示（）
A、渐进下界
B、渐进上界
C、非紧上界
D、非紧下界
答案：A
解析：渐进上界O，渐进下界Ω，紧渐进界Θ，非紧上界ω，非紧下界o。
3、Fibonacci数列递归的边界条件有（）条
A、1
B、2
C、3
D、4
答案：B
解析：直接或间接递归调用自身的函数为递归函数，递归函数由边界条件和递归方程组成。
4、使用分治算法求解不需要满足的条件是（）
A、子问题必须是一样的
B、子问题不能够重复
C、子问题的解可以合并
D、原问颗和子问题采用相同的方法解
答案：A
解析：分治算法不要求子问题必须是一样的，但子问题必须相互独立，否则应该使用动态规划算法或贪心算法。
5、Strassen矩阵乘法是利用（）实现的算法
A、分治策略
B、动态规划
C、贪心算法
D、回溯法
答案：A
解析：使用分治策略解决矩阵乘法可将2*2阶矩阵的乘法减少至7次。
6、下列不是动态规划算法基本步骤的是（）
A、找出最优解的性质
B、构造最优解
C、计算最优解
D、定义最优解
答案：B
解析：动态规划解决问题分为四步：
（1）找出最优解的形式，并刻画其结构特征
（2）递归地定义最优值
（3）以自底向上的方式计算最优值
（4）根据计算最优值时的信息，构造最优解
在只需要求出最优值的情形下，步骤④可以省略。
7、在有7个顶点的凸多边形的三角剖分中，有（）
A、5条弦和6个三角形
B、4条弦和5个三角形
C、5条弦和5个三角形
D、4条弦和4个三角形
答案：B
解析：凸多边形三角剖分问题中，n个顶点对应n-2个三角形和n-3条边。
8、备忘录方法是（）的变形
A、分治法
B、动态规划法
C、贪心法
D、回溯法
答案：B
解析：动态规划法具备最优子结构性质和重叠子问题性质，而动态规划法的变性为备忘录方法。注意动态规划法时自底向上求解。
9、不可以使用分治法求解的是（）
A、棋盘覆盖
B、线性时间选择
C、合并排序
D、0-1背包问题
答案：D
解析：0-1背包因其具有子问题重叠性质，不使用分治法求解。
10、在大整数乘法运算中，使用分治法可以把乘法次数减少到（）次
A、4
B、3
C、2
D、1
答案：B
解析：大整数乘法中将乘法次数由4次减少为3次。
11、合并排序的平均时间复杂度为（）
A、n
B、n2
C、n*1og n
D、2n
答案：C
解析：合并排序使用分治算法，平均和最坏时间复杂度都是nlog n。
12、在最接近点对问题中，考虑两点分处不同区域情况，己知一点坐标后，另一点可以考虑在另一侧划分成6个矩形区域内部，使得每个区域最多只能出现（）个点
A、4
B、6
C、2
D、1
答案：D
解析：根据鸽笼定理，在另一侧划分的2d^d的大矩形可划分为6个小矩形，每个小矩形最多只能出现一个点。
13、通常以自底向上方式求最优解的是（）
A、分治法
B、动态规划
C、贪心法
D、回溯法
答案：B
解析：自底向上求最优解的是动态规划，自顶向下求最优解的是备忘录算法和贪心算法。
14、使用动态规划算法求解捡硬币问题，当coins={5,1,2,10,6,2}时，最优解为（）
A、13
B、21
C、17
D、12
答案：C
解析：最优解为17，选择5，10，2三枚硬币。
15、用动态规划法求解最大子段和问题，时间复杂度为（）
A、log n
B、n
C、n2
D、n* log n
答案：B
解析：最大子段和可以用三种方法求解，分别是暴力算法、分治法和动态规划算法，时间复杂度分别为：O(n^2)，O(nlogn)，O(n)。
16、矩阵连乘问题可由（）算法实现
A、分支限界
B、动态规划
C、贪心
D、回溯
答案：B
解析：矩阵连乘问题由动态规划算法求解。
17、一个问题可以使用动态规划算法或者贪心算法求解的关键特征是问题具有（）
A、重叠子问题性质
B、最优子结构性质
C贪心选择性质
D、递归性质
答案：B
解析：最优子结构性质是使用动态规划算法或者贪心算法求解的关键特征。
18、哈夫曼编码贪心算法所需的计算时间为（）
A、n2n
B、n1og n
C、2n
D、n
答案：B
解析：哈夫曼编码贪心算法所需的计算时间为n*1og n
19、最小生成树可以使用（）算法求解
A、Prim
B、Kruskal
C、Prim和Kruskal
D、Dijkstra
答案：C
解析：Prim和Kruskal都可以解决最小生成树问题，Prim算法解决疏松图，Kruskal算法解决稠密图。
20、贪心算法能得到（）
A、长江游艇问题的解
B、电路布线问题的解
C、背包问题的解
D、旅行售货员问题的解
答案：C
解析：贪心算法能解决背包问题的解，但0-1背包不能用动态规划算法解决。
21、以下活动安排问题的最优解包含（）项活动
A、2
B、3
C、4
D、5
答案：C
解析：活动安排问题的策略是每次都选和之前己选活动相容且结束时间最早的活动，使用动态规划算法求解。
22、证明贪心算法不能求解该问题一般使用（）
A、数学归纳法
B、演绎法
C、举反例
D、反证法
答案：D
解析：使用反证法反证贪心算法不能求解某一个问题。
23、最优装载问题的贪心策略是（）
A、选择当前价值最大的箱子
B、选择当前重量最重的箱子
C、选择当前价值最小的箱子
D、选择当前重量最轻的箱子
答案：D
解析：选择当前重量最轻的箱子，再选择当前重量次轻的箱子。
24、最小生成树问题的重要应用方向为（）
A、电路布线
B、删数问题
C、遍历图顶点
D、数据分组
答案：C
解析：最小生成树应用于图论知识的实际问题，解决遍历图顶点问题，也有其他不同的作用。例如：要在n个城市之间铺设光缆，主要目标是要使这n个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。
25、贪心算法与动态规划算法的主要区别是具有（）
A、最优子结构性质
B、贪心选择性质
C、可以构造最优解的能力
D、重叠子问题性质
答案：B
解析：贪心算法与动态规划算法的最大区别在于用贪心算法求解的题目具有贪心选择性质，用贪心算法求解的所有题目均可以用动态规划算法求解，反之不成立。
26、以深度优先方式系统搜索问题解的算法是（）
A、分支限界法
B、概率算法
C、贪心算法
D、回溯法
答案：D
解析：回溯法使用深度优先策略，分支限界法使用广度优先或最大效益(最小耗费)优先的策略。
27、两艘船的装载问题用回溯法求解（）
A、总能求得最优解，保证两艘船都装满
B、效率低于贪心算法,通常不用
C、可以求出解，但不一定能把两艘船装满
D、无法求解,也不能保证两艘船都装满
答案：C
解析：两艘船的装载问题类似于特殊的0-1背包问题，用回溯法(深度优先剪枝，但本质还是穷举)无法保证将两艘船都装满(会留下剩余的不可利用的空间)。
28、使用回溯法求解0-1背包问题（）
A、效率比动态规划算法好很多
B、效率比分支限界法算法好很多
C、效率比贪心算法差很多
D、效率比分治法差很多
答案：A
解析：回溯法求解0-1背包问题时间复杂度为O(2^n)，而动态规划算法求解的时间复杂度为O(n*2的n次方)。
29、批处理作业调度问题的解空间树为（）
A、排列树
B、子集树
C、n叉树
D、随问题而动态变化的树
答案：A
解析：作业调度问题的解空间树为排列树。
30、符号三角形问题有解时，第一行的符号个数不可以为（）个
A、4
B、6
C、7
D、8
答案：B
解析：要满足符号三角形的特性，需要整体的符号个数n(n-1)/2非奇数(n为第一行的符号个数)，只有这样才满保证+号和-号各占n(n-1)/4。
31、四皇后问题如果不考虑对称性，一共有（）个解
A、无
B、1
C、2
D、4
答案：C
解析：四皇后问题不考虑对称性的话，共有4个解。
32、关于着色问题，在一个平面或者球面中，一般情况下使用最多（）种颜色，即可保证任意两个相邻区域颜色不同
A、4
B、5
C、6
D、7
答案：A
解析：4色猜想不多说了。
33、回溯算法的效率不依赖于下列哪项因素（）
A、满足显约束值的个数
B、计算约束函数的时间
C、计算限界函数的时间
D、确定解空间的时间
答案：D
解析：回溯算法的效率依赖于满足显约束值的个数、计算约束函数的时间、计算限界函数的时间等。
34、回溯法和分支限界法求解问题的解空间树不会是（）
A、有序树
B、排列树
C、子集树
D、无序树
答案：D
解析：解空间树都是有序树。有序树的定义为：若将树中每个结点的各子树看成是从左到右有次序的(即不能互换),则称该树为有序树(Ordered Tree) 。
35、优先队列式分支限界法选取扩展节点的原则是（）
A、先进先出
B、后进先出
C、节点的优先级
D、从上到下,从左到右
答案：C
解析：在队列式分治限界法中，拓展节点按照节点的优先级为顺序，这里的优先级一般为最小耗费优先。
36、能求解布线问题的算法是（）
A、分支限界法
B、动态规划法
C、回溯法
D、分治法
答案：A
解析：布线问题：与拓展节点相邻且可达的方格成为可行节点被加入活结点队列中，使用分支限界法求解。
37、解图的最大团问题,等价于求其补图的（）
A、最小团
B、最大点独立集
C、最小点独立集
D、最小生成树
答案：B
解析：解图的最大团问题,等价于求其补图的最大点独立集。
38、装载问题或最优装载问题，通常不使用（）方法求解
A、动态规划
B、贪心法
C、回溯法
D、分支限界法
答案：C
解析：回溯法求解装载问题或最优装载问题的时间复杂度较高，一般不用其求解。
39、关于连续邮资问题，以下说法不正确的是（）
A、第一张邮票的面值只能是1
B、可以用回溯法或分支限界法求解
C、己选定x[1:i-1]，最大连续邮资区间是[1:r]，接下来x[i]的可取值范围是[x[i+1:r+1]
D、当n=5和m-4时，面值为(1,3,11,15,32)的5种邮票可以贴出邮资的最大连续邮资区间是1到70
答案：C
解析：x[i]接下来的可取值范围为[x[i-1]+1:r+1]。
40、下列算法中有时找不到问题解的是（）
A、蒙特卡洛算法
B、拉斯维加斯算法
C、舍伍德算法
D、数值概率算法
答案：B
解析拉斯维加斯算法有时找不到问题的解，但只要找到解就一定是正确的。
