一、选择题1、 下列什么问题不能用贪心法求解？ （ ）A) 霍夫曼编码问题 B) 单源最短路径问题C) 0-1背包问题 D) 最小生成树问题2、二分搜索算法是借助（ ）实现的算法。A、分治策略 B、动态规划法 C、贪心法 D、回溯法2、下列不是动态规划算法基本步骤的是（A ）。A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解4．下列算法中一般以自底向下的方法求解最优解的是（ ）。A、备忘录法 B、动态规划法 C、贪心法 D、回溯法5、衡量一个算法优劣的标准是（）。A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短6．最长公共子序列算法借助的算法是（ ）。A、分支界限法 B、动态规划法 C、贪心法 D、回溯法7.下面是贪心算法的基本要素的是（ ）。A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解8、下面关于NP问题说法正确的是（）A NP问题都是不可能解决的问题B P类问题包含在NP类问题中C NP完全问题是P类问题的子集D NP类问题包含在P类问题中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、动态规划法 C、贪心法 D、回溯法14．下列是动态规划算法基本要素的是（ ）。A、定义最优解 B、构造最优解 C、算出最优解 D、子问题重叠性质15．贪心算法与动态规划算法的主要区别是（ ）。A、最优子结构 B、贪心选择性质 C、构造最优解 D、定义最优解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、问题的 最优子结构性质 是该问题可用动态规划算法或贪心算法求解的关键特点。16、 贪心选择性质 是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。19.贪心算法的基本要素是 贪心选择 质和 最优子结构 性质 。21. 动态规划算法的基本思想是将待求解问题分解成若干 子问题 ，先求解 子问题 ，然后从这种 子问题 的解得到原问题的解。22.算法是由若干条指令组成的有穷序列，且要满足输入、 输出 、确定性和 有限性 四条性质。26、 贪心选择性质 是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
27.快速排序算法是基于 分治策略 的一种排序算法。28.动态规划算法的两个基本要素是. 最优子结构 性质和 重叠子问题 性质 。三、简答题（本题25分，每小题5分）1、设计动态规划算法的主要步骤为：2、贪心算法的基本要素是哪些，并简单解释其涵义（1）所谓贪心选择性质：是指（所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到）。（2）最优子结构性质：是指（问题的最优解包含了其子问题的最优解）。3 用动态规划法求A10*30B30*20C20*10D10*200运算量最小的乘积次序。要求写出求解过程，并将结果填入字段m[4][4]中。4、叙述贪心算法和动态规划算法的基本思想，并比较两种算法的优缺。5、何谓P、NP、NPC问题6、顶点覆盖、集合覆盖、旅行商问题的实例求解4、 有11个待安排的活动，它们具有下表所示的开始时间与结束时间，如果以贪心算法求解这种活动的最优安排（即为活动安排问题：在所给的活动集合中选出最大的相容活动子集合），得到的最大相容活动子集合为活动（ {1，4，8，11} ）。
