算法练习题-2
算法
优解
16. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的
（ ）。
A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解
17. 实现最长公共子序列利用的算法是（ B ）。
A、分治策略 B、动态规划法 C、贪心法 D、回溯法
18. 能采用贪心算法求最优解的问题，一般具有的重要性质为：（ ）
A. 最优子结构性质与贪心选择性质
B．重叠子问题性质与贪心选择性质
C．最优子结构性质与重叠子问题性质
D. 预排序与递归调用
19 下列不是NPC问题的是（）
A 电路可满足性 B 0-1背包 C 顶点覆盖 D子集和
二、填空题
1、 算法的性质包括输入、输出、＿＿＿、有限性。
2、 动态规划算法的基本思想就将待求问题＿＿＿＿＿、先求
解子问题，然后从这些子问题的解得到原问题的解。
3、 设计动态规划算法的4个步骤：
（1） 找出＿＿＿＿，并刻画其结构特征。
（2） ＿＿＿＿＿＿＿。
（3） ＿＿＿＿＿＿＿。
根据计算最优值得到的信息，＿＿＿＿＿＿＿。
1.算法的复杂性有 时间 复杂性和 空间 复杂
性之分。
2、程序是 算法 用某种程序设计语言的具体实现。
4.矩阵连乘问题的算法可由 动态规划 设计实现。
8、问题的 最优子结构性质 是该问题可用动态规划算法或贪心算法求解的
关键特征。
