算法设计与分析复习题最终版

本文格式为Word版，下载可任意编辑——算法设计与分析复习题最终版一、填空题：

1、算法就是一组有穷的_____________，它们规定了解决某一特定类型问题的一系列运

算。

2、f(n)=6×2+n，f(n)的渐进上界是_____________。3、递归与分治算法应满足条件：____________与_____________。4、算法的繁杂性是______的度量，是评价算法优劣的重要依据。

5、以广度优先探寻或以最小花费方式探寻问题解的算法称为________________。6、算法满足的性质：输入、______、______、有限性。7、算法的繁杂性是______的度量，是评价算法优劣的重要依据。8、以________________方式探寻问题解的算法称为分支限界法。

9、贪心算法总是做出在当前看来________________的选择。也就是说贪心算法并不从整

体最优考虑，它所做出的选择只是在某种意义上的________________。

10、算法的“确定性〞指的是组成算法的每条_____________是明了的，无歧义的。11、任何可用计算机求解的问题所需的时间都与其_____________有关。

12、分支限界法主要有队列式（FIFO）分支限界法和________________分支限界法。13、贪心算法总是做出在当前看来________________的选择。也就是说贪心算法并不从整

体最优考虑，它所做出的选择只是在某种意义上的________________。14、大整数乘积算法是用_____________来设计的。

15、任何可用计算机求解的问题所需的时间都与其_____________有关。16、衡量一个算法好坏的标准是（）。17、二分探寻算法是利用（）实现的算法。

18、用探寻算法解旅行售货员问题时的解空间树是（）。19、0-1背包问题的回溯算法所需的计算时间为（）20、以下哪种算法是以深度优先策略进行探寻的（）21、（）是贪心算法与动态规划算法的共同点。

22、以下算法中寻常以自底向下的方式求解最优解的是（）。23、分支限界法解旅行售货员问题时，活结点表的组织形式是（）。24、回溯法探寻状态空间树是依照（）的顺序。

25、将一个难以直接解决的大问题，分解成一些规模较小的一致问题，以便各个击破。这

属于（）的解决方法。

26、Strassen矩阵乘法是利用（）实现的算法。27、备忘录方法是（）算法的变形。28、（）算法是以深度优先策略进行探寻的（）29、以下不是动态规划算法基本步骤的是（）。

A、找出最优解的空间结构C、算出最优解

B、构造最优解D、定义最优解

n

2

30、背包问题的贪心算法所需的计算时间为（）。

31、下面哪种函数是回溯法中为避免无效探寻采取的策略（）A、递归函数

32、以下描述正确的是（）

A、递归算法只能直接调用自身B、递归函数是由函数自身给出定义的

C、每个递归函数不一定都要有非递归定义的初始值D、以上都不正确

33、以下描述不正确的是（）

A、组成算法的每条指令是没有歧义的B、算法中每条指令的执行时间是有限的

C、在算法的循环结构中，指令的执行次数可以无限D、组成算法的每条指令是明了的

34、下面哪种函数是回溯法中为避免无效探寻采取的策略（）

A、递归函数C、随机数函数

B、剪枝函数D、探寻函数

B、剪枝函数

D、探寻函数

C、随机数函数

35、二分探寻算法是利用（）实现的算法。

A、分治策略B、动态规划法C、贪心法D、回溯法36、衡量一个算法好坏的标准是（）。

37、用探寻算法解旅行售货员问题时的解空间树是（）。38、算法分析中,记号O表示()

39、（）算法中寻常以自底向下的方式求解最优解的是（）。40、（）是贪心算法与动态规划算法的共同点。41、回溯法探寻状态空间树是依照（）的顺序。

二、简答题：

1.阐述回溯算法与分枝限界算法的区别和联系，各自强调改善那方面以提高效率，各适合那些问题？

2、采用动态规划算法必需满足的条件是什么？动态规划算法是通过什么问题的什么特3、陈述算法在最坏状况下的时间繁杂度和平均时间繁杂度；这两种评估算法繁杂性的方法各自有什么实际意义？

4、比较贪心算法与动态规划算法的异同，它们都有那些优势和劣势？5、简述分支限界法和回溯法的异同

6、简述分治法所能解决的问题一般具有的特征。性提高效率的？

7、简述动态规划的算法步骤。

三、程序阅读题：

请阅读以下程序，描述程序功能，并分析时间繁杂度。

1、#includeusingnamespacestd;

voidPrintMultiplicationTable(intn){

if(n==1){

coutusingnamespacestd;char*str=\intn=4;intx[4];

voidBackTrack_SubSet(intt){

if(t==n){

for(inti=0;iusingnamespacestd;boolIsPowerOfTwo(intn){

if(nusingnamespacestd;

inlinevoidSwap(inta=b;b=temp;}

voidPerm(intlist[],intm,intk=0){

if(k==m-1){

for(inti=0;iusing