算法练习题-2
算法
一、选择题
1、 下列哪些问题不能用贪心法求解？
A) 霍夫曼编码问题 B) 单源最短路径问题
C) 0-1背包问题 D) 最小生成树问题 （ ）
2、二分搜索算法是利用（ ）实现的算法。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
2、下列不是动态规划算法基本步骤的是（ A ）。
A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解
4．下列算法中通常以自底向上的方式求解最优解的是（ ）。
A、备忘录法 B、动态规划法 C、贪心法
5、衡量一个算法好坏的标准是（）。
A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短
6．最长公共子序列算法利用的算法是（ ）。
A、分支界限法 B、动态规划法 C、贪心法 D、回溯法
7.下面是贪心算法的基本要素的是（ ）。
A、重叠子问题 B、构造最优解 C、贪心选择性质
8、下面关于NP问题说法正确的是（）
A NP问题都是不可能解决的问题
B P类问题包含在NP类问题中
C NP完全问题是P类问题的子集
D NP类问题包含在P类问题中 D、定义最优解 D、回溯法
9下列哪些问题是典型的NP完全问题：
A．排序问题 B．n-后问题 C．m-着色问题 D．旅行商问题
10. （ ）是贪心算法与动态规划算法的共同点。
A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质
11. 矩阵连乘问题的算法可由（ B）设计实现。
A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法
12、下面问题（）不能使用贪心法解决。
A 单源最短路径问题 B 活动选择问题
C 最小花费生成树问题 D 最优二叉搜索树问题
13．实现合并排序利用的算法是（ ）。
A、分治策略
B、动态规划法 B、构造最优解 C、贪心法 D、回溯法 D、子问题14．下列是动态规划算法基本要素的是（ ）。 A、定义最优解
重叠性质
A、最优子结构 C、算出最优解 15．贪心算法与动态规划算法的主要区别是（ ）。 B、贪心选择性质 C、构造最优解 D、定义最
