算法分析复习题含答案

一、选择题1、衡量一种算法好坏的原则是（C）。（A）运行速度快（B）占用空间少（C）时间复杂度低（D）代码短2、记号O的定义对的的是（A）。（A）O(g(n))={f(n)|存在正常数c和n0使得对所有nn0有：0f(n)cg(n)}；（B）O(g(n))={f(n)|存在正常数c和n0使得对所有nn0有：0cg(n)f(n)}；（C）O(g(n))={f(n)|对于任何正常数c>0，存在正数和n0>0使得对所有nn0有：0f(n)<cg(n)}；（D）O(g(n))={f(n)|对于任何正常数c>0，存在正数和n0>0使得对所有nn0有：0cg(n)<f(n)}；3、二分搜索算法是运用（A）实现的算法。（A）分治方略（B）动态规划法（C）贪心法（D）回溯法4、使用分治法求解不需要满足的条件是（A）。（A）子问题必须是同样的（B）子问题不可以反复（C）子问题的解可以合并（D）原问题和子问题使用相似的措施解5、合并排序算法是运用（

A）实现的算法。（A）分治方略 （B）动态规划法 （C）贪心法 （D）回溯法6、实现大整数的乘法是运用（C）的算法。（A）贪心法 （B）动态规划法 （C）分治方略 （D）回溯法7、如下不可以使用分治法求解的是（D）。（A）棋盘覆盖问题（B）选择问题（C）归并排序（D）0/1背包问题8、实现循环赛日程表运用的算法是（A）。（A）分治方略 （B）动态规划法 （C）贪心法 （D）回溯法9、实现棋盘覆盖算法运用的算法是（A）。（A）分治法 （B）动态规划法 （C）贪心法 （D）回溯法10、矩阵连乘问题的算法可由（B）设计实现。（A）分支界线算法（B）动态规划算法（C）贪心算法（D）回溯算法11、实现大整数的乘法是运用的算法（C）。（A）贪心法 （B）动态规划法 （C）分治方略 （D）回溯法12、最长公共子序列算法运用的算法是（

B

）。（A）分支界线法（B）动态规划法（C）贪心法（D）回溯法13、下列算法中一般以自底向上的方式求解最优解的是（B）。（A）备忘录法 （B）动态规划法 （C）贪心法 （D）回溯法14、下列是动态规划算法基本要素的是（

D

）。（A）定义最优解（B）构造最优解（C）算出最优解（D）子问题重叠性质15、下列不是动态规划算法基本环节的是（A）。（A）找出最优解的解空间（B）构造最优解（C）算出最优解（D）定义最优解16、能采用贪心算法求最优解的问题，一般具有的重要性质为：（A）（A）最优子构造性质与贪心选择性质（B）重叠子问题性质与贪心选择性质（C）最优子构造性质与重叠子问题性质（D）预排序与递归调用17、下面问题（B）不能使用贪心法处理。（A）单源最短途径问题 （B）N皇后问题（C）最小花费生成树问题 （D）背包问题18、如下不可以使用分治法求解的是（D）。（A）棋盘覆盖问题（B）选择问题（C）归并排序（D）0/1背包问题19、备忘录措施是那种算法的变形（

B

）。（A）分治法

（B）动态规划法

（C）贪心法

（D）回溯法

20、下列算法中一般以深度优先方式系统搜索问题解的是（D）。（A）备忘录法 （B）动态规划法 （C）贪心法 （D）回溯法21、下面哪种函数是回溯法中为防止无效搜索采用的方略（B）（A）递归函数 （B）剪枝函数 （C）随机数函数 （D）搜索函数22、回溯法在问题的解空间树中，按（D）方略，从根结点出发搜索解空间树。（A）广度优先（B）活结点优先（C）扩展结点优先（D）深度优先23、回溯法的效率不依赖于下列哪些原因（

D

）。（A）.满足显约束的值的个数

（B）计算约束函数的时间

（C）

计算限界函数的时间

（D）

确定解空间的时间24、回溯法解0-1背包问题时的解空间树是（

A

）。

（A）子集树

（B）排列树

（C）深度优先生成树

（D）广度优先生成树

25、回溯法解旅行售货员问题时的解空间树是（

B

）。

（A）子集树

（B）排列树

（C）深度优先生成树

（D）广度优先生成树

26、一种问题可用动态规划算法或贪心算法求解的关键特性是问题的（B）。（A）重叠子问题（B）最优子构造性质（C）贪心选择性质（D）定义最优解27、下列算法中不能处理0/1背包问题的是（A）（A）贪心法（B）动态规划（C）回溯法（D）分支限界法28、下面问题（B）不能使用贪心法处理。（A）单源最短途径问题（B）N皇后问题（C）最小生成树问题（D）背包问题29、矩阵连乘问题的算法可由（B）设计实现。（A）分支界线算法（B）动态规划算法（C）贪心算法（D）回溯算法30、贪心算法与动态规划算法的重要区别是（

B

）。（A）最优子构造（B）贪心选择性质（C）构造最优解（D）定义最优解二、简答题算法重要特性是什么？算法分析的目的是什么？算法的时间复杂性与问题的什么原因有关？算法的渐进时间复杂性的含义？最坏状况下的时间复杂性和平均时间复杂性有什么不一样？简述二分检索（折半查找）算法的基本过程。背包问题的目的函数和贪心算法最优化量度相似吗？采用回溯法求解的问题，其解怎样表达？有什么规定？回溯法的搜索特点是什么？n皇后问题回溯算法的鉴别函数place的基本流程是什么？为何用分治法设计的算法一般有递归调用？为何要分析最坏状况下的算法时间复杂性？简述渐进时间复杂性上界的定义。二分检索算法最多的比较次数？迅速排序算法最坏状况下需要多少次比较运算？贪心算法的基本思想？回溯法的解（x1,x2,……xn）的隐约束一般指什么？论述合并排序的分治思绪。迅速排序的基本思想是什么。什么是直接递归和间接递归？消除递归一般要用到什么数据构造？试述分治法的基本思想。设计动态规划算法有哪些重要环节？分治法与动态规划法的异同？备忘录措施和动态规划算法相比有何异同？简述之。参照答案：1.输入、输出、确定性、有限性、可实现性。2.分析算法占用计算机资源的状况，对算法做出比较和评价，设计出更好的算法。3.算法的时间复杂性与问题的规模有关，是问题大小n的函数。4．当问题的规模n趋向无穷大时，影响算法效率的重要原因是T(n)的数量级，而其他原因仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。5.最坏状况下的时间复杂性和平均时间复杂性考察的是n固定期，不一样输入实例下的算法所耗时间。最坏状况下的时间复杂性取的输入实例中最大的时间复杂度：W(n)=max{T(n，I)},I∈Dn平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：A(n)=∑P(I)T(n，I)I∈Dn6.设输入是一种按非降次序排列的元素表A[i：j]和x，选用A[(i+j)/2]与x比较，假如A[(i+j)/2]=x，则返回(i+j)/2，假如A[(i+j)/2]<x，则A[i：(i+j)/2-1]找x，否则在A[(i+j)/2+1：j]找x。上述过程被反复递归调用。7.不相似。目的函数：获得最大利润。最优量度：最大利润/重量比。8.问题的解可以表达为n元组：（x1,x2,……xn），xi∈Si,Si为有穷集合，xi∈Si,（x1,x2,……xn）具有完备性，即（x1,x2,……xn）是合理的，则（x1,x2,……xi）(i<n)一定合理。9.在解空间树上跳跃式地深度优先搜索，即用鉴定函数考察x[k]的取值，假如x[k]是合理的就搜索x[k]为根节点的子树，假如x[k]取完了所有的值，便回溯到x[k-1]。10.将第K行的皇后分别与前k-1行的皇后比较，看与否与它们相容，假如不相容就返回false，测试完毕则返回true。11.子问题的规模还很大时，必须继续使用分治法，反复分治，必然要用到递归。12.最坏状况下的时间复杂性决定算法的优劣，并且最坏状况下的时间复杂性较平均时间复杂性游可操作性。13.T(n)是某算法的时间复杂性函数，f(n)是一简朴函数，存在正整数No和C，n〉No，有T(n)<f(n)，这种关系记作T(n)=O(f(n))。14.二分检索算法的最多的比较次数为logn。15.最坏状况下迅速排序退化成冒泡排序，需要比较n2次。16.是一种根据最优化量度依次选择输入的分级处理措施。基本思绪是：首先根据题意，选用一种量度原则；然后按这种量度原则对这n个输入排序，依次选择输入量加入部分解中。假如目前这个输入量的加入，不满足约束条件，则不把此输入加到这部分解中。17.回溯法的解（x1,x2,……xn）的隐约束一般指个元素之间应满足的某种关系。18.讲数组一分为二，分别对每个集合单独排序，然后将已排序的两个序列归并成一种含n个元素的分好类的序列。假如分割后子问题还很大，则继续分治，直到一种元素。19.迅速排序的基本思想是在待排序的N个记录中任意取一种记录，把该记录放在最终位置后，数据序列被此记录提成两部分。所有关键字比该记录关键字小的放在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间，这个过程称作一次迅速排序。之后反复上述过程，直到每一部分内只有一种记录为止。20.在定义一种过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己自身，这称为直接递归。假如过程或者函数P调用过程或者函数Q，Q又调用P，这个称为间接递归。消除递归一般要用到栈这种数据构造。21.分治法的基本思想是将一种规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相似。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。22.设计动态规划算法的重要环节为：（1）找出最优解的性质，并刻划其构造特性。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。23.分治法与动态规划法的相似点是：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。两者的不一样点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题