算法复习题

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

复习题第1页共6页一、选择题1、衡量一个算法好坏的标准是()。(A)运行速度快(B)占用空间少(C)时间复杂度低(D)代码短2、函数nn1032的渐进表达式是()。(A)O(23n)(B)O(3)(C)O(n10)(D)O(2n)3、以下不可以使用分治法求解的是()。(A)棋盘覆盖问题(B)选择问题(C)归并排序(D)0/1背包问题4、二分搜索算法是利用()实现的算法。(A)分治策略(B)动态规划法(C)贪心法(D)回溯法5、二分搜索算法的时间复杂性为()。(A)O(2n)(B)O(n)(C)O(nlog)(D)O(nnlog)6、快速排序算法的时间复杂性为()。(A)O(2n)(B)O(n)(C)O(nlog)(D)O(nnlog)7、实现大整数的乘法是利用()的算法。(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)0/1背包问题14、下列算法中不能解决0/1背包问题的是()(A)贪心法(B)动态规划(C)回溯法(D)分支限界法15、算法是由若干条指令组成的有穷序列,而且满足以下性质()(A)输入:有0个或多个输入(B)输出:至少有一个输出(C)确定性:指令清晰,无歧义(D)有限性:指令执行次数有限,而且执行时间有限A(1)(2)(3)B(1)(2)(4)C(1)(3)(4)D(1)(2)(3)(4)16、函数32n+10nlogn的渐进表达式是().A.2nB.32nC.nlognD.10nlogn17、能采用贪心算法求最优解的问题,一般具有的重要性质为:()(A)最优子结构性质与贪心选择性质(B)重叠子问题性质与贪心选择性质(C)最优子结构性质与重叠子问题性质(D)预排序与递归调用复习题第2页共6页18、回溯法在问题的解空间树中,按()策略,从根结点出发搜索解空间树。(A)广度优先(B)活结点优先(C)扩展结点优先(D)深度优先19、下面哪种函数是回溯法中为避免无效搜索采取的策略()(A)递归函数(B)剪枝函数(C)随机数函数(D)搜索函数(A)运行速度快(B)占用空间少(C)时间复杂度低(D)代码短20、备忘录方法是那种算法的变形()。21、下列算法中通常以深度优先方式系统搜索问题解的是()。(A)备忘录法(B)动态规划法(C)贪心法(D)回溯法22、回溯法解旅行售货员问题时的解空间树是()。(A)子集树(B)排列树(C)深度优先生成树(D)广度优先生成树23、Strassen矩阵乘法是利用()实现的算法。(A)分治策略(B)动态规划法(C)贪心法(D)回溯法24.采用广度优先策略搜索的算法是()。(A)分支界限法(B)动态规划法(C)贪心法(D)回溯法25、背包问题的贪心算法所需的计算时间为()(A)O(n2n)(B)O(nlogn)(C)O(2n)(D)O(n)二、填空题1、程序是算法用某种程序设计语言的具体实现。2、算法的“确定性”指的是组成算法的每条指令是清晰的,无歧义的。3.算法是由若干条指令组成的有穷序列,且要满足输入、输出、确定性和有限性四条性质。4、计算一个算法时间复杂度通常可以计算循环次数、基本操作的频率或计算步。5.算法的复杂性有时间复杂性和空间复杂性之分。6、从分治法的一般设计模式可以看出,用它设计出的程序一般是递归算法。7.动态规划算法的两个基本要素是最优子结构和重叠子问题。8、问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。9、贪心选择性质是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。10.动态规划算法的基本思想是将待求解问题分解成若干子问题,先求解子问题,然后从这些问题得到原问题的解。11.快速排序算法是基于分治策略的一种排序算法。12.任何可用计算机求解的问题所需的时间都与其规模有关。13.快速排序算法的性能取决于划分的对称性。14.回溯法搜索解空间树时,常用的两种剪枝函数为约束函数和限界函数。15、以深度优先方式系统搜索问题解的算法称为回溯法。16、使用回溯法进行状态空间树裁剪分支时一般有两个标准:约束条件和目标函数的界,N皇后问题和0/1背包问题正好是两种不同的类型,其中同时使用约束条件和目标函数的界进复习题第3页共6页行裁剪的是0/1背包问题,只使用约束条件进行裁剪的是N皇后问题。三、算法填空1、以下是计算xm的值的过程intpower(x,m){//计算xm的值并返回。y=(1);i=m;while(i--0)y=y*x;returny;}2、给定已按升序排好序的n个元素a[0:n-1],现要在这n个元素中找出一特定元素x的二分搜索算法templateclassTypeintBinarySearch(Typea[],constType&x,intl,intr){while(l=r){intm=((l+r)/2);if(x==a[m])returnm;if(xa[m])r=m-1;elsel=m+1;}return-1;}3、速排序templateclassTypevoidQuickSort(Typea[],intp,intr){if(pr){intq=Partition(a,p,r);QuickSort(a,p,q-1);//对左半段排序QuickSort(a,q+1,r);//对右半段排序}}4、快速排序中的划分函数Partition确定以基准元素a[p]对子数组a[p:r]进行划分templateclassTypevoidPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p];while(true){while(a[++i]x&&ir);while(a[--j]x);if(i=j)break;Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;复习题第4页共6页}5、合并排序描述如下:templateclassTypevoidMergesort(Typea[],intleft,intright){if(leftright){inti=(left+right)/2;Mergesort(a,left,i);//对左半段排序Mergesort(a,i+1,right);//对右半段排序Merge(a,b,left,i,right);//合并到数组bCopy(a,b,left,right);//复制到数组a}}6、函数Merge合并两个排好序的数组段到一个新的数组b中。voidMerge(Typec[],Typed[],intl,intm,intr){inti=l,j=m+1,k=l;while((i=m)&&(j=r))if(c[i]=c[j])d[k++]=c[i++];elsed[k++]=c[j++];if(im)for(intq=j;q=r;q++)d[k++]=c[q];elsefor(intq=i;q=m;q++)d[k++]=c[q];}7、计算最长公共子序列的算法如下:voidLCSLength(intm,intn,char*x,char*y,intc,int**b){inti,j;for(i=1;i=m;i++)c[i][0];for(i=1;i=n;i++)c[0][i];for(i=1;i=m;i++)for(j=1;j=n;j++);{if(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=3;}}}8、列问题TemplateclassTypevoidperm(Typelist[],intk,intm){//产生[list[k:m]的所有排列if(k==m){//只剩下一个元素for(inti=0;i=m;i++)coutlist[i];coutendl;}复习题第5页共6页else//还有多个元素待排列,递归产生排列for(inti=k;i=m;i++){swap(list[k],list[i]);perm(list,k+1;m);swap(list[k],list[i]);}}9、0-1背包问题templateclassTypevoidknapsack(Typev,intw,intc,intn,Type**m){intjMax=min(w[n]-1,c);for(intj=0;j=jMax;j++)m[n][j]=0;for(intj=w[n];j=c;j++)m[n][j]=v[n];for(inti=n-1;i1;i--){jMax=min(w[i]-1,c);for(intj=0;j=jMax;j++)m[i][j]=m[i+1][j];for(intj=w[i];j=c;j++)m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}m[1][c]=m[2][c];if(c=w[1])m[1][c]=max(m[2][c],m[2][c-w[1]]+v[1]);}10、按上述算法knapsack计算后,m[1][c]给出所求的0-1背包问题的最优值。相应的最优解可由算法traceback计算voidtraceback(intc,intn,intx[]){for(inti=1;in;i++){if(m[i][c]==m[i+1][c])x[i]=0;else{x[i]=1;c-=w[i];}}x[n]=(m[n][c])?1:0;}四、简答题1、算法的渐进时间复杂性的含义?答:当问题的规模n趋向无穷大时,影响算法效率的重要因素是T(n)的数量级,而其他因素仅是使时间复杂度相差常数倍,因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。2、为什么用分治法设计的算法一般有递归调用?答:当子问题的规模还很大时,必须继续使用分治法,反复分治,必然要用到递归。复习题第6页共6页3、为什么要分析最坏情况下的算法时间复杂性?答:最坏情况下的时间复杂性决定算法的优劣,并且最坏情况下的时间复杂性较平均时间复杂性更具有可操作性。4、简述分治法的基本思想。答:分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同;对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止;将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。5、分治法所能解决的问题一般应具有哪些特征?答:(1)该问题的规模缩小到一定的程度就可以容易地解决;(2)该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质;(3)利用该问题分解出的子问题的解可以合并为该问题的解;(4)该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。6、简述分治法的基本步骤。答:分治法在每一层递归上都有三个步骤:(1)分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;(2)解决:若子问题规模较小而容易被解

1 / 6
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功