绪论单元测试
1.山东师范大学的管教授在哪个问题上给出了比较好的解决方法。
A:邮递员问题
B:背包问题
C:装载问题
D:最大团问题
答案:A
第一章测试
2.算法具备的四个基本性质是（）
A:输入
B:有限性
C:确定性
D:输出
答案:ABCD
3.算法就是程序
A:错
B:对
答案:A
4.描述渐进上界的符号是（）
A:Ω
B:ω
C:O
D:θ
答案:C
5.f(n)=3n2+n+1,下面不正确的是()
A:f(n)=O(n3)
B:f(n)=O(n2)
C:f(n)=O(2n)
D:f(n)=O(3n2)
答案:C
6.在算法分析中，我们希望找到更加高阶的上界函数
A:错
B:对
答案:A
第二章测试
7.Strasn 矩阵乘法是利用（ ）实现的算法。
A:贪心法
B:分治策略
C:动态规划法
D:回溯法
答案:B
8.使用分治法求解不需要满足的条件是（ ）
A:子问题不能够重复
B:子问题的解可以合并
C:子问题必须是一样的
D:原问题和子问题使用相同的方法解
答案:C
9.实现棋盘覆盖算法利用的算法是（ ）。
A:分治法
B:回溯法
C:动态规划法
D:贪心法
答案:A
10.实现循环赛日程表利用的算法是（ ）。
A:贪心法
B:回溯法
C:分治策略
D:动态规划法
答案:C
11.从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法
A:对
B:错
答案:A
第三章测试
12.动态规划算法一般分成（ ）三个阶段。
A:求解
B:分析
C:分段
D:汇总
答案:ABC
13.动态规划的基本要素有（ ）？
A:备忘录方法
B:最优子结构
C:子问题的重叠性质
答案:ABC
14.用动态规划法求解的问题都可以分解为相互重叠的子问题。
A:对
B:错
答案:A
15.动态规划法利用递推关系式（ ）计算，实现动态规划过程。
A:循环
B:递归
C:自底向上
D:自顶向下
答案:C
16.最优子结构是问题可以用动态规划法求解的前提。
A:错
B:对
答案:B
第四章测试
17.贪心算法中每次做出的贪心选择都是全局最优选择。
A:对
B:错
答案:B
18.下面问题不能使用贪心法解决的是
A:N皇后问题
B:最小花费生成树问题
C:背包问题
D:单源最短路径问题
答案:A
19.背包问题的贪心算法所需的计算时间为
A:O（n2n）
B:O（n）
C:O（nlogn）
D:O（2n）
答案:C
20.哈夫曼编码是自底向上构造的
A:错
B:对
答案:B
21.Kruskal算法的时间复杂度是
A:O（eloge）
B:O（n）
C:O（nlogn）
D:O（2n）
答案:A
第五章测试
22.回溯法就是穷举法
A:错
B:对
答案:A
23.回溯法使用的是广度优先遍历
A:对
B:错
答案:B
24.回溯法必须寻找一个限界函数
A:对
B:错
答案:B
25.使用回溯法时可以考虑以下哪些方面()
A:约束函数
B:解空间结构
C:解的向量形式
D:解的最优子结构性质
答案:ABC
26.回溯法在处理n皇后问题时，必须把解空间组织成子集树。
A:错
B:对
答案:A
第六章测试
27.分支限界法特别适合求解最优值问题。
A:错
B:对
答案:B
28.分支限界法可以根据选择活动节点的不同分成().
A:深度优先分支限界法
B:FIFO队列式分支限界法
C:广度优先分支限界法
D:优先队列式分支限界法
答案:BD
29.在使用分支限界法解决TSP问题是，可以怎样确定限界函数().
A:随机找一个回路作为下界
B:每行最小值累加估算下界
C:使用贪心法估算上界
D:每行最小两个值累加除以2估算下界
答案:BCD
30.分支限界法比回溯法效率高
A:对
B:错
答案:B
31.分支限界法只适合求极大值问题
A:错
B:对
答案:A
第七章测试
32.连续傅里叶(Fourier)变换实质上是实函数在复数域上分解与合成。（ ）
A:对
B:错
答案:A
33.离散傅里叶(Fourier)变换实质上是实数列利用基函数在复数域上分解与合成。（ ）
A:对
B:错
答案:A
34.余弦变换(DCT)是傅里叶变换的特例，且离散余弦变换(DCT)主要应用于图像压缩。（ ）
A:对
B:错
答案:A
35.小波分析方法的应用主要有( )
A:图像边缘检测，图像压缩和重建
B:语音信号处理
C:时频分析
D:地震信号分析
答案:ABCD
