算法复习练习题

复习总结练习题

一、选择题

1、 将一个难以直接解决的大问题，分解成一些规模较小的相同问题，以便各个击破。这属于（ ）

的解决方法。（ ）

A、动态规划 B、分治法 C、贪心算法 2、 以下描述正确的是（ ）

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

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

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

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

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

4、 有3个矩阵A维数是{10*100}，B维数是{100*5}，C维数是{5*50}，若按（（AB）C）计算，3个矩

阵连乘积需要的乘法次数是（ ） A、7500

B、75000

C、750

D、750000

D、分支界限法

5、 以下对于动态规划描述不正确的是（ ）

A、动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干子问题 B、适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的 C、具体的动态规划算法多种多样，但是他们具有相同的填表格式 D、动态规划求解问题时和分治法一样，对子问题重复计算多次 6、 以下增长最快的是（ ）

A、log2n

B、nlog2n

C、n

2

D、2

n

7、 以下哪种算法是以深度优先策略进行搜索的（ ）

A、回溯法

B、分支界限法

C、贪心算法

D、随机化算法

8、 下列哪一种算法是随机化算法（ ） A、 贪心算法 B、 回溯法 C、动态规划算法 D、舍伍德算法 9、 用计算机解决问题的步骤一般为：（）

①编写程序 ②设计算法 ③分析问题 ④调试程序 A、①②③④ C、②③①④

B、③④①② D、③②①④

10、 在对问题的解空间树进行搜索的方法中，一个活结点有多次机会成为活结点的是（ ）。

A、回溯法

B、分支限界法

C、回溯法和分支限界法 D、回溯法求解子集树问题

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

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

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

12、 用计算机解决问题的步骤一般为：（ ）

①编写源代码 ②设计算法 ③分析问题 ④调试程序 A．①②③④

B. ③④①②

C. ②③①④

D. ③②①④

13、 衡量一个算法好坏的标准是（ ）。

A、运行速度快 B、占用空间少 C、时间复杂度低 D、代码短 14、 下面关于算法的错误说法是

A、算法必须有输出 B、算法必须在计算机上用某种语言实现 C、算法不一定有输入 D、算法必须在有限步执行后能结束 15、 以下增长最慢的是（ ）

A、log2n

B、nlog2n

C、n

2

D、2

n

16、 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（ ）。

A．回溯法

B．分支限界法

C．回溯法和分支限界法 D．回溯法求解子集树问题

17、 有3个矩阵A维数是{10*100}，B维数是{100*5}，C维数是{5*50}，若按（（AB）C）计算，3个矩

阵连乘积需要的乘法次数是（ ） A、7500

B、75000

C、750

D、750000

18、 以下对于动态规划描述不正确的是（ ）

A、动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干子问题 B、适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的 C、具体的动态规划算法多种多样，但是他们具有相同的填表格式 D、动态规划求解问题时和分治法一样，对子问题重复计算多次 19、 以下描述正确的是（ ）

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

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

20、 以下哪种算法是以广度优先策略进行搜索的（ ）

A、回溯法

B、分支界限法

C、贪心算法

D、随机化算法

21、 将一个难以直接解决的大问题，分解成一些规模较小的相同问题，以便各个击破。这属于（ ）

的解决方法。（ ）

A、动态规划 B、分治法 C、贪心算法

22、 以下对于动态规划描述不正确的是（ ）

A、动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干子问题 B、适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的 C、具体的动态规划算法多种多样，但是他们具有相同的填表格式 D、动态规划求解问题时和分治法一样，对子问题重复计算多次

23、 有3个矩阵A维数是{10*100}，B维数是{100*5}，C维数是{5*50}，若按（（AB）C）计算，3个矩

阵连乘积需要的乘法次数是（ ） A、7500

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

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

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

25、 以下哪种算法是以深度优先策略进行搜索的（ ）

A、回溯法

B、分支界限法

C、贪心算法

D、随机化算法

B、75000

C、750

D、750000 D、分支界限法

26、 动态规划算法适用于解最优化问题，以下哪个不是动态规划法解决问题的步骤（ ）

A、找出最优解的性质，并刻画其结构特征 B、递归地定义最优值

C、以自顶向下的方式计算出最优值

D、根据计算最优值时得到的信息，构造最优解

27、 在对问题的解空间树进行搜索的方法中，一个活结点有多次机会成为活结点的是（ ）。

A、回溯法

B、分支限界法

C、回溯法和分支限界法 D、回溯法求解子集树问题 28、 . 实现最大子段和利用的算法是（ ）。 A、分治策略

B、动态规划法 C、贪心法 D、回溯法

29、 优先队列式分支限界法选取扩展结点的原则是（ ）。 A、先进先出

B、后进先出

C、结点的优先级 D、随机

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

A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）

31、 广度优先是（ ）的一搜索方式。

A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 32、 舍伍德算法是（ ）的一种。

A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法 33、 在下列算法中有时找不到问题解的是（ ）。

A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 34、 下列哪一种算法是随机化算法（ ）

A. 贪心算法B. 回溯法C.动态规划算法D.舍伍德算法

35、 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ ）。 A、重叠子问题

B、最优子结构性质

C、贪心选择性质 D、定义最优解

36、 采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间

复杂度为 ( ) 。

A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 37、 以深度优先方式系统搜索问题解的算法称为 ( ) 。 A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法

38、 实现最长公共子序列利用的算法是（ ）。

A、分治策略 B、动态规划法 C、贪心法 D、回溯法

二、填空题

1、 递归与分治算法应满足条件：____________与_____________ 2、 按照渐近阶从低到高的顺序排列下列表达式：

2n,n,,4n3,nlogn，结果为______。

3、 贪心算法的基本要素是：____________与_____________

4、 ______和______是采用动态规划算法的两个基本要素。

5、 回溯法中的解空间树结构通常有两种，分别是______、______。 6、

mA(n)?an???a1n?a0的上界为______。 m多项式

12、算法分析从——————和——————两个方面分析。

13以深度优先方式系统搜索问题解的算法称为——————回溯法 。 14、数值概率算法常用于_____的求解。

15、计算一个算法时间复杂度通常可以计算_____ 、 基本操作的_____或计算步。

二、简答题

1、时间复杂性分析主要分哪三种情况，各有什么作用？

2、动态规划算法的基本思想是什么？请简述动态规划算法主要设计步骤。 3、动态规划算法的本质是什么？与分治法的区别是什么？ 4. 动态规划与分治法的异同，深刻理解动态规划法的本质 5. 请简述分支限界法的算法思想以及两种主要的实现方法

四、程序阅读题 请阅读以下程序，写出程序输出结果及时间复杂度。

1、

#include using namespace std;

int GetNumberOfOne(int i){ int count = 0;

unsigned int flag = 1; while(flag){

if(i & flag) count ++; flag = flag << 1; }

return count; }

int main() {

cout<

#include #include

int IsSpecialStr(char* str,int n) { if(n == 1) return 1; if(n == 2 && str[0] == str[1]) return 1; else return str[0] == str[n-1] && IsSpecialStr(str+1,n-2); }

int main() { char* str[3] = {\ for(int i = 0; i < 3; i++) if(IsSpecialStr(str[i],strlen(str[i]))) printf(\}

五、算法设计与实现题

1、给定一个存放整数的数组，重新排列数组使得数组左边为偶数，右边为奇数。 2、最大子段和问题。

3、求子集问题。问题描述：给定一个由数字字符组成的集合（数字字符数组），打印出各字符数字和要大于n的所有子集

4、求最长下降序列问题（拦截导弹问题）

本文来源：https://www.bwwdw.com/article/hv7p.html