算法分析复习题(含答案)

1、一、选择题1、衡量一个算法好坏的标准是A运行速度快B占用空间少2、记号0的定义正确的选项是A。 A B CC 。C时间复杂度低D代码短存在正常数存在正常数 对于任何正常数 c>0 ，存在正数和D0(g(n) = f(n) |0(g(n) = f(n) |0(g(n) = f(n) | 有： 0 f(n)<cg(n) 0(g(n) = f(n) | 有： 0 cg(n) < f(n) 对于任何正常数 c>0 ，存在正数和n0 有： 0 f(n)cg(n) ；n0 有： 0 cg(n)f(n) ；n0 >0 使得对所有n n0n0 >0 使得对所有n n0c和n

2、O使得对所有n c 和 n0 使得对所有 n3、 二分搜索算法是利用A实现的算法。A分治策略B动态规划法C贪心法4、 使用分治法求解不需要满足的条件是A 。B子问题不能够重复 D原问题和子问题使用相同的方法解 实现的算法。D回溯法A子问题必须是一样的C子问题的解可以合并5、合并排序算法是利用A分治策略B6、实现大整数的乘法是利用A贪心法B动态规划法 C 的算法。动态规划法DC贪心法c分治策略DD回溯法回溯法7、以下不可以使用分治法求解的是A棋盘覆盖问题B选择问题8、实现循环赛日程表利用的算法是A分治策略B动态规划法9、实现棋盘覆盖算法利用的算法是A分治法B动态规划法10、矩阵连乘问题的算法可由

3、 B 。DC归并排序。贪心法。C贪心法设计实现。C贪心算法0/1 背包问题ACD回溯法D回溯法A分支界限算法B动态规划算法11、实现大整数的乘法是利用的算法A贪心法B动态规划法12、最长公共子序列算法利用的算法是A分支界限法B动态规划法13、以下算法中通常以自底向上的方式求解最优解的是A备忘录法B动态规划法14、以下是动态规划算法根本要素的是A定义最优解B构造最优解15、以下不是动态规划算法根本步骤的是A找出最优解的解空间B构造最优解16、能采用贪心算法求最优解的问题，一A最优子结构性质与贪心选择性质 C最优子结构性质与重叠子问题性质17、下面问题 B 不能使用贪心法解决。A单源最短路径问题B

4、C最小花费生成树问题D18、以下不可以使用分治法求解的是D 。A棋盘覆盖问题B选择问题。C分治策略B 。 C 贪心法BC贪心法D 。C算出最优解A 。C算出最优解D回溯算法D回溯法D 。DD回溯法回溯法子问题重叠性质D定义最优解A 般具有的重要性质为： B重叠子问题性质与贪心选择性质D预排序与递归调用N皇后问题背包问题C归并排序D 0/1 背包问题A分治法B动态规划法C贪心法D回溯法20、 以下算法中通常以深度优先方式系统搜索问题解的是D 。A备忘录法B动态规划法C贪心法D回溯法21、 下面哪种函数是回溯法中为防止无效搜索采取的策略B A递归函数B剪枝函数C随机数函数 D搜索函数22、 回溯法

5、在问题的解空间树中，按D 策略，从根结点出发搜索解空间树。A广度优先B活结点优先C扩展结点优先D深度优先23、回溯法的效率不依赖于以下哪些因素 A . 满足显约束的值的个数 C计算限界函数的时间24、回溯法解 0-1 背包问题时的解空间树是A子集树B排列树生成树25、回溯法解旅行售货员问题时的解空间树是A子集树B排列树D。B计算约束函数的时间D 确定解空间的时间A。 C深度优先生成树D广度优先B。 C深度优先生成树D广度优先生成树26、一个问题可用动态规划算法或贪心算法求解的关键特征是问题的B 。A分支界限算法B动态规划算法C贪心算法30、贪心算法与动态规划算法的主要区别是B 。A最优子结构B

6、贪心选择性质C构造最优解D回溯算法D定义最优解A重叠子问题B最优子结构性质C贪心选择性质D定义最优解27、以下算法中不能解决0/1 背包问题的是A A贪心法B动态规划C回溯法D分支限界法28、下面问题 B 不能使用贪心法解决。A单源最短路径问题BN皇后问题C最小生成树问题D背包问题29、矩阵连乘问题的算法可由B 设计实现。、简答题1. 算法重要特性是什么？2. 算法分析的目的是什么？3. 算法的时间复杂性与问题的什么因素相关？4. 算法的渐进时间复杂性的含义？5. 最坏情况下的时间复杂性和平均时间复杂性有什么不同？6. 简述二分检索折半查找算法的根本过程。7. 背包问题的目标函数和贪心算法最优

7、化量度相同吗？8. 采用回溯法求解的问题，其解如何表示？有什么规定？9. 回溯法的搜索特点是什么？10. n 皇后问题回溯算法的判别函数 place 的根本流程是什么？11. 为什么用分治法设计的算法一般有递归调用？12. 为什么要分析最坏情况下的算法时间复杂性？13. 简述渐进时间复杂性上界的定义。14. 二分检索算法最多的比拟次数？15. 快速排序算法最坏情况下需要多少次比拟运算？16. 贪心算法的根本思想？17. 回溯法的解Xi,X2,Xn的隐约束一般指什么？18. 阐述合并排序的分治思路。19. 快速排序的根本思想是什么。20. 什么是直接递归和间接递归？消除递归一般要用到什么数据结构

8、？21. 试述分治法的根本思想。22. 设计动态规划算法有哪些主要步骤？23. 分治法与动态规划法的异同？24. 备忘录方法和动态规划算法相比有何异同？简述之。参考答案：1. 输入、输出、确定性、有限性、可实现性。2. 分析算法占用电脑资源的情况，对算法做出比拟和评价，设计出更好的算法。3. 算法的时间复杂性与问题的规模相关，是问题大小 n 的函数。4当问题的规模 n 趋向无穷大时，影响算法效率的重要因素是 T(n) 的数量级，而其他因素仅 是使时间复杂度相差常数倍，因此可以用T(n) 的数量级 (阶) 评价算法。时间复杂度 T(n)的数量级 ( 阶)称为渐进时间复杂性。5. 最坏情况下的时间

9、复杂性和平均时间复杂性考察的是 n 固定时，不同输入实例下的算法所 耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：W(n) = max T(n , I) , I Dn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：A(n)=刀 PT(n ,1) I Dn6. 设输入是一个按非降次序排列的元素表Ai : j和x，选取A(i+j)/2 与x比拟，如果A(i+j)/2=x ，那么返回(i+j)/2 ，如果 A(i+j)/2<x ，贝U Ai : (i+j)/2-1 找 x，否那么在 A (i+j)/2+1: j找x。上述过程被反复递归调用。7. 不相同。目标函数：获得

10、最大利润。最优量度：最大利润 / 重量比。8. 问题的解可以表示为 n元组：xi,x2, Xn，Xi S, S为有穷集合，Xi S, xi,x 2, xn具备完备性，即X1,x 2, xn是合理的，那么X1,x 2, x(i<n) 定合理。9. 在解空间树上跳跃式地深度优先搜索,即用判定函数考察xk 的取值,如果 xk 是合理的就搜索 xk 为根节点的子树,如果 xk 取完了所有的值,便回溯到 xk-1 。10. 将第K行的皇后分别与前 k-1行的皇后比拟，看是否与它们相容，如果不相容就返回false , 测试完毕那么返回 true 。1 1 .子问题的规模还很大时,必须继续使用分治法,

11、反复分治,必然要用到递归。12. 最坏情况下的时间复杂性决定算法的优劣,并且最坏情况下的时间复杂性较平均时间复杂 性游可操作性。13. T(n)是某算法的时间复杂性函数，f(n)是一简单函数，存在正整数No和C, nNo,有T(n)<f(n) ,这种关系记作 T(n)=O(f(n)。14. 二分检索算法的最多的比拟次数为 log n 。15. 最坏情况下快速排序退化成冒泡排序，需要比拟n2次。16. 是一种依据最优化量度依次选择输入的分级处理方法。根本思路是：首先根据题意,选取 一种 量度标准；然后 按这种量度标准对这 n 个输入排序,依次选择输入量参加局部解中。 如果当前这个输入量的参

12、加,不满足约束条件,那么不把此输入加到这局部解中。17. 回溯法的解X1,X2,Xn的隐约束一般指个元素之间应满足的某种关系。18. 讲数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一个含n个元素的分好类的序列。如果分割后子问题还很大,那么继续分治,直到一个元素。19. 快速排序的根本思想是在待排序的N个记录中任意取一个记录， 把该记录放在最终位置后，数据序列被此记录分成两局部。所有关键字比该记录关键字小的放在前一局部，所有比它 大的放置在后一局部，并把该记录排在这两局部的中间，这个过程称作一次快速排序。之 后重复上述过程，直到每一局部内只有一个记录为止。20. 在定义一个

13、过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，这称为直接递归。如果过程或者函数P调用过程或者函数 Q Q又调用P,这个称为间接递归。消除递归一般要用到栈这种数据结构。21. 分治法的根本思想是将一个规模为 n的问题分解为k个规模较小的子问题，这些子问题互相 独立且与原问题相同。 递归地解这些子问题， 然后将各个子问题的解合并得到原问题的解。22. 设计动态规划算法的主要步骤为：1找出最优解的性质，并刻划其结构特征。 2递归地定义最优值。 3以自底向上 的方式计算出最优值。 4根据计算最优值时得到的信息，构造最优解。23. 分治法与动态规划法的相同点是： 将待求解的问题分解成假设干个子问题， 先求解子问题， 然后从这些子问题的解得到原问题的解。两者的不同点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独 立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。24. 备忘录方法是动态规划算法的变形