资源描述：
《计科算法设计汇总.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、题组一选择题1、二分搜索算法是利用（ A ）实现的算法。A、分治策略 B、动态规划法 C、贪心法 D、回溯法7、衡量一个算法好坏的标准是（C）。A运行速度快B占用空间少C时间复杂度高低D代码短8、以下不可以使用分治法求解的是（D）。A棋盘覆盖问题B选择问题C归并排序D0/1背包问题14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）16．最长公共子序列算法利用的算法是（ B ）。A、分支界限法B、动态规划法C、贪心法D、回溯法17．实现棋盘覆盖算法利用的算
2、法是（ 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
3、（nlogn） C、O（2n） D、O（n）填空题1.算法的复杂性有时间复杂性和空间复杂性之分。2、程序是算法 用某种程序设计语言的具体实现。3、算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的。4.矩阵连乘问题的算法可由动态规划设计实现。6、算法是指解决问题的一种方法或一个过程。7、从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。8、问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。9、以深度优先方式系统搜索问题解的算法称为回溯法。10、数值概率算法常用于数值问题的求解。问答题6、考虑用哈夫曼算法
4、来找字符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）、根据题中数据构造哈夫曼树如下图所
5、示。由此可以得出a,b,c,d,e,f的一组最优的编码：01,0000,00010,00011,1,001。题组二1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。2.算法的复杂性有_____________和___________之分，衡量一个算法好坏的标准是______________________。3.某一问题可用动态规划算法求解的显著特征是_______________________
6、_____________。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背包问题的回溯算法所需的计算
7、时间为_____________,用动态规划算法所需的计算时间为____________。9.动态规划算法的两个基本要素是___________和___________。10.二分搜索算法是利用_______________实现的算法。答案： 一、填空 1．确定性 有穷性 可行性 0个或多个输入 一个或多个输出 2.时间复杂性 空间复杂性 时间复杂度高低 3. 该问题具有最优子结构性质 4.{BABCD}或{CABCD}或{CADCD｝ 5.一个（最优）解 6.子问题 子问题 子问题 7.回溯法 8. o(n*2n) o(m
8、in{nc
