(最新整理)算法复习练习题

1、(完整)算法复习练习题(完整)算法复习练习题 编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（(完整)算法复习练习题）的内容能够给您的工作和学习带来便利。同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快 业绩进步，以下为(完整)算法复习练习题的全部内容。复习总结练习题一、选择题1、 将一个难以直接解决的大问题，分解成一些规模较小的相同问题，以便各个击破.这属于（ ）的解决方法。

2、( ）a、动态规划b、分治法c、贪心算法d、分支界限法2、 以下描述正确的是（ ）a、递归算法只能直接调用自身b、递归函数是由函数自身给出定义的c、每个递归函数不一定都要有非递归定义的初始值d、以上都不正确3、 以下描述不正确的是（ ）a、组成算法的每条指令是没有歧义的b、算法中每条指令的执行时间是有限的c、在算法的循环结构中，指令的执行次数可以无限 d、组成算法的每条指令是清晰的4、 有3个矩阵a维数是10100,b维数是1005,c维数是550，若按（ab）c）计算，3个矩阵连乘积需要的乘法次数是（ ）a、7500b、75000c、750d、7500005、 以下对于动态规划描述不正确的是

3、（ ）a、动态规划法与分治法类似,其基本思想也是将待求解问题分解成若干子问题b、适合于用动态规划求解的问题,经分解得到的子问题往往不是互相独立的c、具体的动态规划算法多种多样，但是他们具有相同的填表格式d、动态规划求解问题时和分治法一样，对子问题重复计算多次6、 以下增长最快的是（ ）a、log2nb、nlog2nc、n2d、2n7、 以下哪种算法是以深度优先策略进行搜索的（ ）a、回溯法b、分支界限法c、贪心算法d、随机化算法8、 下列哪一种算法是随机化算法( ） a、 贪心算法 b、 回溯法 c、动态规划算法 d、舍伍德算法9、 用计算机解决问题的步骤一般为：（）编写程序 设计算法 分析问

4、题 调试程序 a、b、c、d、10、 在对问题的解空间树进行搜索的方法中，一个活结点有多次机会成为活结点的是（ ）。a、回溯法 b、分支限界法c、回溯法和分支限界法 d、回溯法求解子集树问题11、 以下描述不正确的是（ ）a、组成算法的每条指令是没有歧义的b、算法中每条指令的执行时间是有限的c、在算法的循环结构中，指令的执行次数可以无限 d、组成算法的每条指令是清晰的12、 用计算机解决问题的步骤一般为：( ）编写源代码 设计算法 分析问题 调试程序 ab。 c. d. 13、 衡量一个算法好坏的标准是( ). a、运行速度快 b、占用空间少 c、时间复杂度低 d、代码短14、 下面关于算法的

5、错误说法是a、算法必须有输出 b、算法必须在计算机上用某种语言实现 c、算法不一定有输入 d、算法必须在有限步执行后能结束15、 以下增长最慢的是（ ）a、log2nb、nlog2nc、n2d、2n16、 在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是（ )。a回溯法 b分支限界法c回溯法和分支限界法 d回溯法求解子集树问题17、 有3个矩阵a维数是10*100，b维数是100*5，c维数是550,若按(（ab)c)计算，3个矩阵连乘积需要的乘法次数是（ ）a、7500b、75000c、750d、75000018、 以下对于动态规划描述不正确的是（ ）a、动态规划法

6、与分治法类似，其基本思想也是将待求解问题分解成若干子问题b、适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的c、具体的动态规划算法多种多样，但是他们具有相同的填表格式d、动态规划求解问题时和分治法一样,对子问题重复计算多次19、 以下描述正确的是（ ）a、递归算法只能直接调用自身b、递归函数是由函数自身给出定义的c、每个递归函数不一定都要有非递归定义的初始值d、以上都不正确20、 以下哪种算法是以广度优先策略进行搜索的（ ）a、回溯法b、分支界限法c、贪心算法d、随机化算法21、 将一个难以直接解决的大问题，分解成一些规模较小的相同问题,以便各个击破.这属于（ ）的解决方法.（

7、 ）a、动态规划b、分治法c、贪心算法d、分支界限法22、 以下对于动态规划描述不正确的是（ )a、动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干子问题b、适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的c、具体的动态规划算法多种多样，但是他们具有相同的填表格式d、动态规划求解问题时和分治法一样,对子问题重复计算多次23、 有3个矩阵a维数是10*100,b维数是100*5，c维数是550，若按（ab）c）计算，3个矩阵连乘积需要的乘法次数是（ ）a、7500b、75000c、750d、750000 24、 以下描述正确的是（ ）a、递归算法只能直接调用自身b、递

8、归函数是由函数自身给出定义的c、每个递归函数不一定都要有非递归定义的初始值d、以上都不正确25、 以下哪种算法是以深度优先策略进行搜索的( )a、回溯法b、分支界限法c、贪心算法d、随机化算法26、 动态规划算法适用于解最优化问题，以下哪个不是动态规划法解决问题的步骤（ ）a、找出最优解的性质，并刻画其结构特征b、递归地定义最优值c、以自顶向下的方式计算出最优值d、根据计算最优值时得到的信息，构造最优解27、 在对问题的解空间树进行搜索的方法中，一个活结点有多次机会成为活结点的是（ )。a、回溯法 b、分支限界法c、回溯法和分支限界法 d、回溯法求解子集树问题28、 。实现最大子段和利用的算法

9、是（）。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。贪心算法

10、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、 按照渐近阶

11、从低到高的顺序排列下列表达式：，结果为_.3、 贪心算法的基本要素是:_与_4、 _和_是采用动态规划算法的两个基本要素。5、 回溯法中的解空间树结构通常有两种，分别是_、_。6、 多项式的上界为_.12、算法分析从和-两个方面分析。13以深度优先方式系统搜索问题解的算法称为-回溯法。14、数值概率算法常用于_的求解.15、计算一个算法时间复杂度通常可以计算_、基本操作的_或计算步。二、简答题1、时间复杂性分析主要分哪三种情况，各有什么作用？2、动态规划算法的基本思想是什么？请简述动态规划算法主要设计步骤。 3、动态规划算法的本质是什么？与分治法的区别是什么？4. 动态规划与分治法的异同，深刻

12、理解动态规划法的本质 5. 请简述分支限界法的算法思想以及两种主要的实现方法四、程序阅读题 请阅读以下程序,写出程序输出结果及时间复杂度。1、include iostreamusing 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（）coutgetnumberofone（66）#include string。hint isspecialstr（char str,int n）if(n = 1）return 1;if（n = 2 & str0 = str1）return 1;elsereturn str0 = strn-1 & isspecialstr（str+1，n-2）；int main（)char str3 = ”23423423”，sadasdasd”,”aaaa”;for（int i