绪论 单元测试
1、单选题：
山东师范大学的管教授在哪个问题上给出了比较好的解决方法。
选项：
A:邮递员问题
B:背包问题
C:装载问题
D:最大团问题
答案: 【邮递员问题】
第一章 单元测试
1、多选题：
算法具备的四个基本性质是（）
选项：
A:输入
B:输出
C:确定性
D:有限性
答案: 【输入;
输出;
确定性;
有限性】
2、判断题：
算法就是程序
选项：
A:对
B:错
答案: 【错】
3、单选题：
描述渐进上界的符号是（）
选项：
A:O
B:Ω
C:θ
D:ω
答案: 【O】
4、单选题：
f(n)=3n2+n+1,下面不正确的是()
选项：
A:f(n)=O(n2)
B:f(n)=O(3n2)
C:f(n)=O(2n)
D:f(n)=O(n3)
答案: 【f(n)=O(2n)】
5、判断题：
在算法分析中，我们希望找到更加高阶的上界函数
选项：
A:对
B:错
答案: 【错】
第二章 单元测试
1、单选题：
Strassen 矩阵乘法是利用（ ）实现的算法。
选项：
A:分治策略
B:动态规划法
C:贪心法
D:回溯法
答案: 【分治策略】
2、单选题：
使用分治法求解不需要满足的条件是（ ）
选项：
A:子问题必须是一样的
B:子问题不能够重复
C:子问题的解可以合并
D:原问题和子问题使用相同的方法解
答案: 【子问题必须是一样的】
3、单选题：
实现棋盘覆盖算法利用的算法是（ ）。
选项：
A:分治法
B:动态规划法
C:贪心法
D:回溯法
答案: 【分治法】
4、单选题：
实现循环赛日程表利用的算法是（ ）。
选项：
A:动态规划法
B:贪心法
C:回溯法
D:分治策略
答案: 【分治策略】
5、判断题：
从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法
选项：
A:对
B:错
答案: 【对】
第三章 单元测试
1、多选题：
动态规划算法一般分成（ ）三个阶段。
选项：
A:分段
B:分析
C:求解
D:汇总
答案: 【分段;
分析;
求解】
2、多选题：
动态规划的基本要素有（ ）？
选项：
A:最优子结构
B:子问题的重叠性质
C:备忘录方法
答案: 【最优子结构;
子问题的重叠性质;
备忘录方法】
3、判断题：
用动态规划法求解的问题都可以分解为相互重叠的子问题。
选项：
A:对
B:错
答案: 【对】
4、单选题：
动态规划法利用递推关系式（ ）计算，实现动态规划过程。
选项：
A:循环
B:递归
C:自顶向下
D:自底向上
答案: 【自底向上】
5、判断题：
最优子结构是问题可以用动态规划法求解的前提。
选项：
A:对
B:错
答案: 【对】
第四章 单元测试
1、判断题：
贪心算法中每次做出的贪心选择都是全局最优选择。
选项：
A:对
B:错
答案: 【错】
2、单选题：
下面问题不能使用贪心法解决的是
选项：
A:单源最短路径问题
B:N皇后问题
C:最小花费生成树问题
D:背包问题
答案: 【N皇后问题】
3、单选题：
背包问题的贪心算法所需的计算时间为
选项：
A:O（n2n）
B:O（nlogn）
C:O（2n）
D:O（n）
答案: 【O（nlogn）】
4、判断题：
哈夫曼编码是自底向上构造的
选项：
A:对
B:错
答案: 【对】
5、单选题：
Kruskal算法的时间复杂度是
选项：
A:O（n）
B:O（eloge）
C:O（2n）
D:O（nlogn）
答案: 【O（eloge）】
第五章 单元测试
1、判断题：
回溯法就是穷举法
选项：
A:对
B:错
答案: 【错】
2、判断题：
回溯法使用的是广度优先遍历
选项：
A:对
B:错
答案: 【错】
3、判断题：
回溯法必须寻找一个限界函数
选项：
A:对
B:错
答案: 【错】
4、多选题：
使用回溯法时可以考虑以下哪些方面()
选项：
A:解的向量形式
B:解空间结构
C:约束函数
D:解的最优子结构性质
答案: 【解的向量形式;
解空间结构;
约束函数】
5、判断题：
回溯法在处理n皇后问题时，必须把解空间组织成子集树。
选项：
A:对
B:错
答案: 【错】
第六章 单元测试
1、判断题：
分支限界法特别适合求解最优值问题。
选项：
A:对
B:错
答案: 【对】
2、多选题：
分支限界法可以根据选择活动节点的不同分成().
选项：
A:FIFO队列式分支限界法
B:优先队列式分支限界法
C:广度优先分支限界法
D:深度优先分支限界法
答案: 【FIFO队列式分支限界法;
优先队列式分支限界法】
3、多选题：
在使用分支限界法解决TSP问题是，可以怎样确定限界函数().
选项：
A:使用贪心法估算上界
B:每行最小值累加估算下界
C:每行最小两个值累加除以2估算下界
D:随机找一个回路作为下界
答案: 【使用贪心法估算上界;
每行最小值累加估算下界;
每行最小两个值累加除以2估算下界】
4、判断题：
分支限界法比回溯法效率高
选项：
A:对
B:错
答案: 【错】
5、判断题：
分支限界法只适合求极大值问题
选项：
A:对
B:错
答案: 【错】
评论0