算法复习练习题

复习总结练习题一、选择题1、将一个难以直接解决的大问题，分解成一些规模较小的相同问题，以便各个击破。这属于（）的解决方法。（）A、动态规划B、分治法C、贪心算法D、分支界限法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、7500B、75000C、750D、7500005、以下对于动态规划描述不正确的是（）A、动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干子问题B、适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的C、具体的动态规划算法多种多样，但是他们具有相同的填表格式D、动态规划求解问题时和分治法一样，对子问题重复计算多次6、以下增长最快的是（）A、log2nB、nlog2nC、n2D、2n7、以下哪种算法是以深度优先策略进行搜索的（）A、回溯法B、分支界限法C、贪心算法D、随机化算法8、下列哪一种算法是随机化算法（）A、贪心算法B、回溯法C、动态规划算法D、舍伍德算法9、用计算机解决问题的步骤一般为：（）①编写程序②设计算法③分析问题④调试程序A、①②③④B、③④①②C、②③①④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、log2nB、nlog2nC、n2D、2n16、在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是（）。A．回溯法B．分支限界法C．回溯法和分支限界法D．回溯法求解子集树问题17、有3个矩阵A维数是{10*100}，B维数是{100*5}，C维数是{5*50}，若按（（AB）C）计算，3个矩阵连乘积需要的乘法次数是（）A、7500B、75000C、750D、75000018、以下对于动态规划描述不正确的是（）A、动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干子问题B、适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的C、具体的动态规划算法多种多样，但是他们具有相同的填表格式D、动态规划求解问题时和分治法一样，对子问题重复计算多次19、以下描述正确的是（）A、递归算法只能直接调用自身B、递归函数是由函数自身给出定义的C、每个递归函数不一定都要有非递归定义的初始值D、以上都不正确20、以下哪种算法是以广度优先策略进行搜索的（）A、回溯法B、分支界限法C、贪心算法D、随机化算法21、将一个难以直接解决的大问题，分解成一些规模较小的相同问题，以便各个击破。这属于（）的解决方法。（）A、动态规划B、分治法C、贪心算法D、分支界限法22、以下对于动态规划描述不正确的是（）A、动态规划法与分治法类似，其基本思想也是将待求解问题分解成若干子问题B、适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的C、具体的动态规划算法多种多样，但是他们具有相同的填表格式D、动态规划求解问题时和分治法一样，对子问题重复计算多次23、有3个矩阵A维数是{10*100}，B维数是{100*5}，C维数是{5*50}，若按（（AB）C）计算，3个矩阵连乘积需要的乘法次数是（）A、7500B、75000C、750D、75000024、以下描述正确的是（）A、递归算法只能直接调用自身B、递归函数是由函数自身给出定义的C、每个递归函数不一定都要有非递归定义的初始值D、以上都不正确25、以下哪种算法是以深度优先策略进行搜索的（）A、回溯法B、分支界限法C、贪心算法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、按照渐近阶从低到高的顺序排列下列表达式：32,,,4,lognnnnn，结果为______。3、贪心算法的基本要素是：____________与_____________4、______和______是采用动态规划算法的两个基本要素。5、回溯法中的解空间树结构通常有两种，分别是______、______。6、多项式10()mmAnanana的上界为______。12、算法分析从——————和——————两个方面分析。13以深度优先方式系统搜索问题解的算法称为——————回溯法。14、数值概率算法常用于_____的求解。15、计算一个算法时间复杂度通常可以计算_____、基本操作的_____或计算步。二、简答题1、时间复杂性分析主要分哪三种情况，各有什么作用？2、动态规划算法的基本思想是什么？请简述动态规划算法主要设计步骤。3、动态规划算法的本质是什么？与分治法的区别是什么？4.动态规划与分治法的异同，深刻理解动态规划法的本质5.请简述分支限界法的算法思想以及两种主要的实现方法四、程序阅读题请阅读以下程序，写出程序输出结果及时间复杂度。1、#includeiostreamusingnamespacestd;intGetNumberOfOne(inti){intcount=0;unsignedintflag=1;while(flag){if(i&flag)count++;flag=flag1;}returncount;}intmain(){coutGetNumberOfOne(66)endl;return0;}2、#includestdio.h#includestring.hintIsSpecialStr(char*str,intn){if(n==1)return1;if(n==2&&str[0]==str[1])return1;elsereturnstr[0]==str[n-1]&&IsSpecialStr(str+1,n-2);}intmain(){char*str[3]={23423423,sadasdasd,aaaa};for(inti=0;i3;i++)if(IsSpecialStr(str[i],strlen(str[i])))printf(%s\n,str[i]);}五、算法设计与实现题1、给定一个存放整数的数组，重新排列数组使得数组左边为偶数，右边为奇数。2、最大子段和问题。3、求子集问题。问题描述：给定一个由数字字符组成的集合（数字字符数组），打印出各字符数字和要大于n的所有子集4、求最长下降序列问题（拦截导弹问题）