题组一选择题1、二分搜索算法是利用（ A ）实现的算法。
A、分治策略B、动态规划法C、贪心法D、回溯法7、衡量一个算法好坏的标准是（C ）。
A 运行速度快B 占用空间少C 时间复杂度高低D 代码短8、以下不可以使用分治法求解的是（D ）。
A 棋盘覆盖问题B 选择问题C 归并排序D 0/1背包问题14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。
A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）16．最长公共子序列算法利用的算法是（ B ）。
A、分支界限法B、动态规划法C、贪心法D、回溯法17．实现棋盘覆盖算法利用的算法是（ A ）。
A、分治法B、动态规划法C、贪心法D、回溯法18.下面是贪心算法的基本要素的是（ C ）。
A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解31、下列算法中不能解决0/1背包问题的是（A ）A 贪心法B 动态规划C 回溯法D 分支限界法32、回溯法搜索状态空间树是按照（C ）的顺序。
A 中序遍历B 广度优先遍历C 深度优先遍历D 层次优先遍历34．实现合并排序利用的算法是（ A ）。
A、分治策略B、动态规划法C、贪心法D、回溯法40、背包问题的贪心算法所需的计算时间为（ B ）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）填空题1.算法的复杂性有时间复杂性和空间复杂性之分。
2、程序是算法用某种程序设计语言的具体实现。
3、算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的。
4.矩阵连乘问题的算法可由动态规划设计实现。
6、算法是指解决问题的一种方法或一个过程。
7、从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。
8、问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
9、以深度优先方式系统搜索问题解的算法称为回溯法。
10、数值概率算法常用于数值问题的求解。
问答题6、考虑用哈夫曼算法来找字符a,b,c,d,e,f 的最优编码。
这些字符出现在文件中的频数之比为20:10:6:4:44:16。
要求：（1）（4 分）简述使用哈夫曼算法构造最优编码的基本步骤；（2）（5 分）构造对应的哈夫曼树，并据此给出a,b,c,d,e,f 的一种最优编码。
解：1）、哈夫曼算法是构造最优编码树的贪心算法。
其基本思想是，首先所有字符对应n 棵树构成的森林，每棵树只有一个结点，根权为对应字符的频率。
然后，重复下列过程n-1 次：将森林中的根权最小的两棵树进行合并产生一个新树，该新树根的两个子树分别是参与合并的两棵子树，根权为两个子树根权之和。
2）、根据题中数据构造哈夫曼树如下图所示。
由此可以得出a,b,c,d,e,f 的一组最优的编码：01,0000,00010,00011, 1,001。
题组二1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。
2.算法的复杂性有_____________和___________之分，衡量一个算法好坏的标准是______________________。
3.某一问题可用动态规划算法求解的显著特征是____________________________________。
4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列_____________________________。
5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。
6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。
7.以深度优先方式系统搜索问题解的算法称为_____________。
8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。
9.动态规划算法的两个基本要素是___________和___________。
10.二分搜索算法是利用_______________实现的算法。
答案：一、填空1．确定性有穷性可行性0个或多个输入一个或多个输出2.时间复杂性空间复杂性时间复杂度高低3.该问题具有最优子结构性质4.{BABCD}或{CABCD}或{CADCD｝5.一个（最优）解6.子问题子问题子问题7.回溯法8.o(n*2n)o(min{nc,2n})9.最优子结构重叠子问题10.动态规划法2、下列不是动态规划算法基本步骤的是（A）。
A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解5.回溯法解旅行售货员问题时的解空间树是（A）。
A、子集树B、排列树C、深度优先生成树D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（B）。
A、备忘录法B、动态规划法C、贪心法D、回溯法7、衡量一个算法好坏的标准是（C）。
A运行速度快B占用空间少C时间复杂度低D代码短9.实现循环赛日程表利用的算法是（A）。
A、分治策略B、动态规划法C、贪心法D、回溯法题组三1.算法分析是（C）A.将算法用某种程序设计语言恰当地表示出来B.在抽象数据集合上执行程序,以确定是否会产生错误的结果C.对算法需要多少计算时间和存储空间作定量分析D.证明算法对所有可能的合法输入都能算出正确的答案2.算法与程序的区别在于算法具有（C）A.能行性B.确定性C.有穷性D.输入和输出4.衡量一个算法好坏的标准是（C）A.运行速度快B.占用空间少C.时间复杂度低D.代码短5.二分搜索算法是利用（A）实现的算法。
A.分治法B.动态规划法C.贪心法D.回溯法6.下面问题（B）不能使用贪心法解决。
A.单源最短路径问题B.N皇后问题C.最小代价生成树问题D.背包问题7．用贪心法设计算法的关键是（B）。
A.将问题分解为多个子问题来分别处理B.选好最优量度标准C.获取各阶段间的递推关系式D.满足最优性原理8.找最小生成树的算法Kruskal的时间复杂度为（D）（其中n为无向图的结点数，m为边数）A．O(n2)B．O(mlogn)C．O(nlogm)D．O(mlogm)9.回溯法搜索状态空间树是按照（C）的顺序。
A.中序遍历B.广度优先遍历C.深度优先遍历D.层次优先遍历10.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（B）A.重叠子问题B.最优子结构性质C.最优量度标准性质D.定义最优解1.算法的复杂性有______和______之分,衡量一个算法好坏的标准是_____________。
2.某一问题可用动态规划算法求解的显著特征是_________________________。
3.若序列A={xzyzzyx}，B={zxyyzxz}，请给出序列A和B的一个最长公共子序列__________________。
4.动态规划算法的基本思想是将待求解问题分解成若干___________先求解_________,然后从这些_____________的解得到原问题的解。
5.0-1背包问题的回溯算法所需的计算时间为____________,用动态规划算法所需的计算时间为________________。
6.二分法搜索算法是利用___________实现的算法。
答案：1.时间、空间时间复杂度空间复杂度。
2.算法效率 3.xyzz.4.子问题子问题子问题5.o（n*2n）6.动态规划法2.算法的复杂性有_____________和___________之分，衡量一个算法好坏的标准是______________________。
2.时间复杂性/空间复杂性/时间复杂度高低3.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列_____________________________。
3.{BABCD}或{CABCD}或{CADCD｝1.（D ）是贪心算法与动态规划算法的共同点。
A、重叠子问题B、构造最优解C、贪心选择性质D、最优子结构性质2.哈夫曼编码可以利用（C ）算法实现。
A、分治策略B、动态规划法C、贪心法D、回朔法题组四1、二分搜索算法是利用（ A ）实现的算法。
A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是（ A ）。
A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3.回溯法的效率不依赖于下列哪些因素（ D ）A.满足显约束的值的个数B. 计算约束函数的时间C. 计算限界函数的时间D. 确定解空间的时间4. 矩阵连乘问题的算法可由（B）设计实现。
A、分支界限算法B、动态规划算法C、贪心算法D、回溯算法5、使用分治法求解不需要满足的条件是（A ）。
A 子问题必须是一样的B 子问题不能够重复C 子问题的解可以合并D 原问题和子问题使用相同的方法解6．贪心算法与动态规划算法的主要区别是（ B ）。
A、最优子结构B、贪心选择性质C、构造最优解D、定义最优7. 以深度优先方式系统搜索问题解的算法称为( D ) 。
A、分支界限算法B、概率算法C、贪心算法D、回溯算法8. 实现最长公共子序列利用的算法是（ B ）。
A、分治策略B、动态规划法C、贪心法D、回溯法9、衡量一个算法好坏的标准是（C ）。
A 运行速度快B 占用空间少C 时间复杂度低D 代码短10、哈弗曼编码的贪心算法所需的计算时间为（ B ）。
A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）二.填空题1.算法的复杂性有(时间）复杂性和（空间）复杂性之分。
2、程序是（算法）用某种程序设计语言的具体实现。
3、算法的“确定性”指的是组成算法的每条（指令）是清晰的，无歧义的。
4.矩阵连乘问题的算法可由（动态规划）设计实现。
5、拉斯维加斯算法找到的解一定是（正确解）。
6、算法是指解决问题的（一种方法）或（一个过程）。
7、从分治法的一般设计模式可以看出，用它设计出的程序一般是（递归算法）。
8、问题的（最优子结构性质）是该问题可用动态规划算法或贪心算法求解的关键特征。
9、计算一个算法时间复杂度通常可以计算（循环次数）、(基本操作的频率)或计算步。
10.快速排序算法是基于(分治策略)的一种排序算法。
三、算法设计题写出欧几里得迭代算法(注意是迭代算法)int Gcd(int m,int n){If(m==0)return n;If(n==0)return m;while(m>0){int c=n%m;n=m;m=c;}Return n;}题组五1.下列不属于一个好的算法应具有的特性的是（C）A.正确性B.简明性C无限性D最优性2.矩阵连乘问题的算法可由（B）设计实现。