计科算法设计汇总

1、题组一选择题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、回溯

2、法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、种程序设计语言的具体实现。3、算法的“确定性”指的是组成算法的每条 指令 是清晰的，无歧义的。4.矩阵连乘问题的算法可由 动态规划 设计实现。6、算法是指解决问题的 一种方法 或 一个过程 。7、从分治法的一般设计模式可以看出，用它设计出的程序一般是 递归算法 。8、问题的 最优子结构性质 是该问题可用动态规划算法或贪心算法求解的关键特征。9、以深度优先方式系统搜索问题解的算法称为 回溯法 。10、数值概率算法常用于 数值问题 的求解。问答题6、考虑用哈夫曼算法来找字符a,b,c,d,e,f 的最优编码。这些字符出现在文件中的频数之比为 20:10:6:4:44:16。要求：（1）（4 分）简

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.一个算法就是一个有穷规则的

5、集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_,_,_,_,_。 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背包问题的回溯算法所需的计

6、算时间为_,用动态规划算法所需的计算时间为_。 9.动态规划算法的两个基本要素是_和_。 10.二分搜索算法是利用_实现的算法。 答案：一、填空1确定性有穷性可行性0个或多个输入一个或多个输出2.时间复杂性空间复杂性时间复杂度高低3.该问题具有最优子结构性质4.BABCD或CABCD或CADCD5.一个（最优）解6.子问题子问题子问题7.回溯法8.o(n*2n)o(minnc,2n)9.最优子结构重叠子问题10.动态规划法2、下列不是动态规划算法基本步骤的是（A）。A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解5.回溯法解旅行售货员问题时的解空间树是（A）。A、子集树B、排列树

7、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.输入

8、和输出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为边数）AO(n2)BO(mlogn)CO(nlogm)DO(mlogm)9.回溯法搜索状态空间

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.二分法搜

10、索算法是利用_实现的算法。答案：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或CADCD1.（ D ）是贪心算法与动态规划算法的共同点。A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质2.哈夫曼编码可以利用（ C ）算法实现。A、分治策略 B、动态规划法 C、贪心

11、法 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 子问题的解可

12、以合并 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、

13、O（n）二.填空题1.算法的复杂性有 (时间）复杂性和（空间）复杂性之分。2、程序是（算法）用某种程序设计语言的具体实现。 3、算法的“确定性”指的是组成算法的每条（指令）是清晰的，无歧义的。 4.矩阵连乘问题的算法可由（动态规划）设计实现。 5、拉斯维加斯算法找到的解一定是（正确解）。 6、算法是指解决问题的（一种方法）或（一个过程）。 7、从分治法的一般设计模式可以看出，用它设计出的程序一般是（递归算法）。 8、问题的（最优子结构性质）是该问题可用动态规划算法或贪心算法求解的关键特征。9、计算一个算法时间复杂度通常可以计算（循环次数）、(基本操作的频率)或计算步。 10.快速排序算法是基于

14、(分治策略)的一种排序算法。三、算法设计题 写出欧几里得迭代算法(注意是迭代算法) int Gcd(int m,int n) If(m=0)return n; If(n=0)return m; while(m0) int c=n%m;n=m; m=c; Return n; 题组五1.下列不属于一个好的算法应具有的特性的是（C） A.正确性 B.简明性 C无限性 D最优性 2.矩阵连乘问题的算法可由（B）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 3.广度优先是（A）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4.学校要举行运动会，请你

15、设计一个能够对运动员分数自动排序的软件，如果要设计此软件，以下最好的方法和步骤是（C） A.分析问题，编写程序，设计算法，调试程序 B.设计算法，编写程序，提出问题，调试程序 C.提出问题，设计算法，编写程序，调试程序 .设计算法，提出问题，编写程序，调试程序 5.用计算机程序解决实际问题的过程中，需要进行算法设计，算法指的是（A） A、解决问题的方法和步骤 B、数值计算的方法 C、实际问题的描述 D、最终结果 6.算法分析是（ C）。 A 将算法用某种程序设计语言恰当地表示出来 B 在抽象数据集合上执行程序，以确定是否会产生错误的结果 C 对算法需要多少计算时间和存储空间作定量分析 D 证明

16、算法对所有可能的合法输入都能算出正确的答案 7.用贪心法设计算法的关键是（ B ）。 A将问题分解为多个子问题来分别处理 B选好贪心准则 C获取各阶段间的递推关系式 D满足最优性原理 8.考虑背包问题：n=6，M=10，V(1:6)=(15,59,21,30,60,5)，W(1:6)=(1,5,2,3,6,1）。该问题的最大效益值为（C ）。若把它看着是0/1 背包问题，则最大效益值为（ B ）。 A101 B110 C115 D120 11.算法确认是（B ）。 A将算法用某种程序设计语言恰当地表示出来 B证明算法对所有可能的合法输入都能算出正确的答案 C对算法需要多少计算时间和存储空间作定

17、量分析 D在抽象数据集合上执行程序，以确定是否会产生错误的结果 12.算法与程序的区别在于算法具有（C ）。 A能行性 B确定性 C有穷性 D输入和输出 14.算法直接插入排序在A1.8=45,33,24,45,12,12,24,12上运行时执行的元素比较次数为（ D）。 A14 B28 C7 D22 15.二分搜索算法是利用（A）实现的算法。 A.分治法 B.动态规划法 C.贪心法 D.回溯法 二、填空题（每空2分，共15个空） 1算法一般分为：_【精确】算法和 【启发式】_算法。 2. 一个合法的递归定义包括两部分：_【基础情况 】_和_【 递归部分】_ 3. 一个算法的 【时间复杂度】_

18、是指算法运行所需要的时间。 4. 如果无向连通图G中不包含任何关节点，则称该图G为_【_双连通图。】_。 5. _【合并排序 】_的基本运算是把两个或多个有序序列合并成一个有序序列。 6. _【_贪心法】_和_【 动态规划法】_要求问题最优解具有最优子结构特性。 7. 使用剪枝函数的深度优先生成状态空间树中结点的求解方法称为_【回溯法】_ 9.所谓最优子结构性质是指【问题的最优解包含了其子问题的最优解】 10.回溯法的算法框架按照问题的解空间一般分为_【子集树】_ 算法框架与_【排列树】_算法框架 11.若序列A=xzyzzyx，B=zxyyzxz，请给出序列A和B的一个最长公共子序列_【_X

19、YZZ_】_。 简答题1、分治法的基本思想？分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归的解这些子问题，然后将各子问题的解合并得到原问题的解。2、简述动态规划的算法步骤。 找出最优解的性质，并刻画其结构特征； 递归地定义最优值； 以自底向上的方式计算出最优值； 根据计算最优值时得到的信息，构造最优解3、简述贪心算法与动态规划法的基本要素。贪心算法的基本要素：贪心选择性质和最优子结构性质。动态规划算法的基本要素是：最优子结构性质和子问题重叠性质。4、简述回溯法的算法步骤。1.针对所给问题，定义问题的解空间；2.确定易于搜索的解空间结构；

20、3.以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。算法设计大题1、 求两个数的最大公约数,欧几里德算法int gcd(int m, int n) int r; while (n!=0) r = m % n; m = n; n = r; return m; 2、写一函数，判断某个数是否素数，以及求11000之内的素数3、选择排序（冒泡排序）。4、顺序查找5、在n个元素中找最大值和最小值#includeusing namespace std;void maxmin(int a,int n,int &max,int &min) max = min = a0; for (int i = 1; i max) max = ai; if (ai min) min = ai; int main() int a = 4,7,2,5,9,6,8,3; int s, t; maxmin(a, 8, s, t);