13计科算法设计程序.docx

题组一选择题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.时间复杂性??