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

一、填空题：

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、#include using namespace std;

void PrintMultiplicationTable(int n) {

if(n == 1) {

cout<<\ return; }

PrintMultiplicationTable(n-1); for(int i = 1; i <= n; i++)

cout<

int main() {

PrintMultiplicationTable(9); return 0; } 2、

#include using namespace std; char* str = \int n = 4; int x[4];

void BackTrack_SubSet(int t) {

if( t == n ) {

for(int i = 0 ; i < n; i++) if(x[i] == 1)

cout<< str[i] <<\ cout<

for(int PossibleValue = 0 ; PossibleValue <=1;PossibleValue++) {

x[t] = PossibleValue; BackTrack_SubSet(t+1); } }

int main() {

BackTrack_SubSet(0); }

3、

#include using namespace std; bool IsPowerOfTwo(int n) {

if( n < 2)

return false; if( n == 2)

return true; if(n % 2 == 0)

return IsPowerOfTwo(n / 2); else

return false; }

int main() {

cout<

#include using namespace std;

inline void Swap(int &a,int &b) {

int temp = a; a = b; b = temp; }

void Perm(int list[],int m,int k = 0) {

if (k == m-1) {

for(int i=0;i

cout<

cout<

for(int i=k;i

Swap(list[k],list[i]); Perm(list,m,k+1);

Swap(list[k],list[i]); } } }

int main() {

int a[] = {1,2,3,4};

Perm(a,sizeof(a) / sizeof(int)); }