算法练习题-分章节-带答案

算法练习题---算法概述、选择题1、下面关于算法的描述，正确的是( )A、一个算法只能有一个输入B、算法只能用框图来表示C一个算法的执行步骤可以是无限的D一个完整的算法，不管用什么方法来表示，都至少有一个输出结果2、一位爱好程序设计的同学，想通过程序设计解决“韩信点兵”的问题，他制定的如下工作过程中，更恰当的是( )A设计算法，编写程序，提出问题，运行程序，得到答案R分析问题，编写程序，设计算法，运行程序，得到答案G分析问题，设计算法，编写程序，运行程序，得到答案D设计算法，提出问题，编写程序，运行程序，得到答案TOC\o"1-5"\h\z3、下面说法正确的是( )A算法+数据结构=程序B、算法就是程序G数据结构就是程序 D、算法包括数据结构4、衡量一个算法好坏的标准是( )0A运行速度快B、占用空间少 G时间复杂度低 D代码短5、解决一个问题通常有多种方法。若说一个算法“有效”是指( )。A、这个算法能在一定的时间和空间资源限制内将问题解决B、这个算法能在人的反应时间内将问题解决C、这个算法比其他已知算法都更快地将问题解决DA和C6、算法分析中，记号。表示( )，记号。表示( )。A.渐进下界 B.渐进上界 C.非紧上界 D.非紧下界7、以下关于渐进记号的性质是正确的有：( )A.f(n)-O(g(n)),g(n)-G'(h(n))=f(n)-O(h(n))B.f(n)=O(g(n)),g(n)=O(h(n))=h(n)=O(f(n))C.O(f(n))+O(g(n))=O(min{f(n),g(n)})D.f(n)=O(g(n))=g(n)=O(f(n))8、记号。的定义正确的是( )。A.O(g(n))={f(n)|存在正常数c和n0使得对所有n至n0有：0-f(n)-cg(n)}；B.O(g(n))={f(n)|存在正常数c和n0使得对所有n^n0有：0-cg(n)-f(n)}；

B.O(g(n))={f(n)|C.O(g(n))={f(n)|对于任何正常数c>0,存在正数和n0>0使得对所有n^n0有0C.O(g(n))={f(n)|领n)<cg(n)};D.O(g(n))={f(n)|对于任何正常数c>0,存在正数和n0>0使得对所有n之n0有：0Mcg(n)<f(n)};9、记号C的定义正确的是( )。O(g(n))={f(n)|O(g(n))={f(n)|CO(g(n))={f(n)|存在正常数c和n0使得对所有n至n0有：0Mf(n)O(g(n))={f(n)|O(g(n))={f(n)|CO(g(n))={f(n)|存在正常数c和n0使得对所有n之n0有：0Mcg(n)工f(n)}；对于任何正常数c>0,存在正数和n0>0使得对所有n2n0有:0S(n)<cg(n)}；D.O(g(n))={f(n)| 对于任何正常数c>0,存在正数和n0>0使得对所有n之n0有:0-cg(n)<f(n)};、填空题1、算法的性质包括输入、输出、、 、有限性。4、算法的复杂性是的度量，是评价算法优劣的重要依据。6、计算机的资源最重要的是时间和空间资源。因而，算法的复杂性有和之分。7、算法复杂度依赖于三方面：、和算法本身。8、程序是用某种程序设计语言的具体实现。9、算法是指解决问题的或步骤的描述。11、计算一个算法时间复杂度通常可以计算、或计算步。16、任何可用计算机求解的问题所需的时间都与其有关。算法练习题---递归与分治策略一、选择题10、Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（ ）voidhanoi(intn,intA,intC,intB){if(n>0){hanoi(n-1,A,C,B);

move(n,a,b);hanoi(n-1,C,B,A);}}voidhanoi(intn,intA,intB,intC){if(n>0){hanoi(n-1,A,C,B);

move(n,a,b);hanoi(n-1,C,B,A);}}voidhanoi(intn,intC,intB,intA){if(n>0){hanoi(n-1,A,C,B);

move(n,a,b);hanoi(n-1,C,B,A);}}voidhanoi(intn,intC,intA,intB){if(n>0){hanoi(n-1,A,C,B);

move(n,a,b);hanoi(n-1,C,B,A);}}11、二分搜索算法是利用（ ）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法TOC\o"1-5"\h\z12、以下不可以使用分治法求解的是（ ）。A棋盘覆盖问题 B 选择问题 C 归并排序 D0/1 背包问题13、实现循环赛日程表利用的算法是（ ）。A、分治策略 B、动态规划法 C、贪心法 D回溯法14、实现棋盘覆盖算法利用的算法是（ ）0A、分治法B、动态规划法 C、贪心法D、回溯法15、Strassen矩阵乘法是利用（ ）实现的算法。A、分治策H& R动态规划法 C、贪心法D回溯法16、使用分治法求解不需要满足的条件是（）。A子问题必须是一样的 B子问题不能够重复C子问题的解可以合并 D原问题和子问题使用相同的方法解17、实现合并排序利用的算法是（ ）0A、分治策略 B、动态规划法 C、贪心法 D回溯法18、实现大整数的乘法是利用的算法（ ）。

A、贪心法A、贪心法B、动态规划法C、分治策略二、填空题5、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相且与原问题相同。10、从分治法的一般设计模式可以看出，用它设计出的程序一般是。14、快速排序算法是基于的一种排序算法。17、快速排序算法的性能取决于三、简答题3、分治法所能解决的问题一般具有的几个特征是：答：(1)该问题的规模缩小到一定的程度就可以容易地解决；(2)该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质 ；(3)利用该问题分解出的子问题的解可以合并为该问题的解；(4)原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。4、分治法与动态规划法的异同。答：相同点：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。不同点：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。8、老板有一袋金块(共n块，n是2的幕(n>=2)),最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重的金块。答：n02,识别出最重和最轻的金块，一次比较就足够了。n>2,第一步，把这袋金块平分成两个小袋A和B。第二步，分别找出在A和B中最重和最轻的金块。设A中最重和最轻的金块分别为HA与LA,以此类推，B中最重和最轻的金块分别为HB和LB。第三步，通过比较HA和HB，可以找到所有金块中最重的；通过比较LA和LB,可以找到所有金块中最轻的。在第二步中，若n>2,则递归地应用分而治之方法。9、Tom很顽皮。一天,他把假币投到储钱罐里。之后，他担心爸爸揍它，想从N个钱币里找出那个假币。他知道假币的重量比其他钱币轻，但不知道如何找到它，于是禁不住哭了。也许你能帮他。请描述一个通过使用天平找到假币的算法，并分析你算法的运行时间。11、对下面的递归算法，写出调用f(4)的执行结果。voidf(intk){if(k>0){printf("%d\n",k);f(k-1)；f(k-1)；}}四、算法填空.快速排序voidQuicksort(inta口，intp,intr){if(P<r){intq=Partition(a,p,r);;// 对左半段排序;// 对右半段排序}}.NF歹I」问题voidperm(intlist口，intk,intm){//产生[list[k:m] 的所有排列if(J {//只剩下一个元素for(inti=0;i<=m;i++)cout<<list[i];cout<<endl;}else// 还有多个元素待排列，递归产生排列for( —) {swap(list[k] ,list[i]);swap(list[k],list[i]);}}五、算法题.给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x,返回其在数组中的位置，如果未找到返回-1。写出二分搜索的算法，并分析其时间复杂度。template<classType>intBinarySearch(Typea[],constType&x,intn){//在a[0:n]中搜索 x，找到 x时返回其在数组中的位置，否则返回-1Intleft=0;intright=n-1;While(left<=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(x>a[middle])left=middle+1;elseright=middle-1;}Return-1;}时间复杂性为O(logn).利用分治算法写出合并排序的算法，并分析其时间复杂度voidMergeSort(Typea[],intleft,intright){if(left<right)// 至少有2个元素{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}}算法在最坏情况下的时间复杂度为O(nlogn)。算法练习题---动态规划一、选择题19、下列不是动态规划算法基本步骤的是A、找出最优解的性质B、构造最优解20、最长公共子序列算法利用的算法是(A分支界Bg法 R动态规划法21、动态规划算法的基本要素为(A.最优子结构性质与贪心选择性质C.最优子结构性质与重叠子问题性质22、矩阵连乘问题的算法可由(()。C、算出最优解D、定义最优解)。G贪心法 D回溯法)B.重叠子问题性质与贪心选择性质D. 预排序与递归调用)设计实现。A分支界限算法 B、动态规划算法 G贪心算法 D.分治法23、下列算法中通常以自底向上的方式求解最优解的是( )。A、备忘录法B、动态规划法 C、贪心法 D回溯法24、应用Johnson法则的流水作业调度采用的算法是( )A.贪心算法 B.分支限界法C.分治法D.动态规划算法25、下列不是动态规划算法基本步骤的是( )。题目不好A、找出最优解的性质 B、构造最优解 C、算出最优解 D定义最优解、填空题2、动态规划算法的基本思想就将待求问题、先求解子问题，然后从这些子问题的解得到原问题的解。3、设计动态规划算法的4个步骤：(1),并刻画其结构特征。(2)。 (3)。(4)根据计算最优值得到的信息，。12、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是,需要排序的是,。18、下面程序段的所需要的计算时间为。intMaxSum(intn,int*a,int&besti,int&bestj){intsum=0;for(inti=1;i<=n;i++){intthissum=0;for(intj=i;j<=n;j++){thissum+=a[j];if(thissum>sum){sum=thissum;besti=i; bestj=j;}}returnsum;}21、所谓最优子结构性质是指 三、简答题1、请叙述动态规划算法与贪心算法的异同。答：共同点：都需要最优子结构性质，不同点：(1)动态规划：每一步作一个选择一依赖于子问题的解。贪心方法：每一步作一个选择一不依赖于子问题的解 。(2)动态规划方法的条件：子问题的重叠性质。贪心方法的条件：最优子结构性质；贪心选择性质。(3)动态规划：自底向上求解；贪心方法：自顶向下求解。2、设计动态规划算法的主要步骤为：答：(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。4、分治法与动态规划法的异同。答：相同点：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。不同点：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。四、算法填空2.最大子段和：动态规划算法intMaxSum(intn,inta口){intsum=0,b=0 ;//sum存储当前最大的b[j],b存储b[j]for(intj=1 ;j<=n;j++){if(b>0)b+=a[j] ;else; //一旦某个区段和为负，则从下一个位置累和if(b>sum)sum士}returnsum算法练习题---贪心算法一、选择题TOC\o"1-5"\h\z26、能采用贪心算法求最优解的问题，一般具有的重要性质为： （ ）A.最优子结构性质与贪心选择性质 B.重叠子问题性质与贪心选择性质C.最优子结构性质与重叠子问题性质 D. 预排序与递归调用27、贪心算法与动态规划算法的共同点是（ ）。A重叠子问题 R构造最优解 C、贪心选择性质 D、最优子结构性质28、贪心算法与动态规划算法的主要区别是（ ）。A最优子结才B、贪心选择Tt质 G构造最优解 D定义最优解29、哈弗曼编码的贪心算法所需的计算时间为（ ）。AO（n2n） BO（nlogn） C、O（2n） D>O（n）30、下面是贪心算法的基本要素的是（ ）。A、重叠子问题 R构造最优解 C、贪心选择Tt质 D定义最优解31、下面问题（B）不能使用贪心法解决。A单源最短路径问题 BN皇后问题 C 最小花费生成树问题 D背包问题32、背包问题的贪心算法所需的计算时间为（ ）A、O（n2n） B、O（nlogn） C、O（2n）D、O（n）45、下列算法中不能解决0/1背包问题的是（ ）A贪心法B 动态规划 C回溯法D 分支限界法二、填空题19、有11个待安排的活动，它们具有下表所示的开始时间与结束时间，如果以贪心算法求解这些活动的最优安排（即为活动安排问题：在所给的活动集合中选出最大的相容活动子集合），得到的最大相容活动子集合为活动。i1234567891011S[i]130535688212f[i]456789101112131420、所谓贪心选择性质是指 所求问题的整体最优解可以通过一系列局部最优的选择、 即贪心选择来达至U O21、所谓最优子结构性质是指 问题的最优解包含了其子问题的最优解 。四、算法填空.背包问题的贪心算法voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);inti;floatc=M;for(i=1;i<=n;i++)x[i]=0;for(i=1;i<=n;i++){if(w[i]>c)break;x[i]=1;；}}.贪心算法求装载问题voidLoading(intx口，intw口，intc,intn){int*t=newint[n+1];;for(inti=1;i<=n;i++)x[i]=0;for(inti=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1; ; }}.贪心算法求活动安排问题template<classType>voidGreedySelector(intn,Types[],Typef口，boolA口){ —; intj=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){ ; ; }elseA[i]=false;}}五、算法题5、试用贪心算法求解下列问题：将正整数 n分解为若干个互不相同的自然数之和，使这些自然数的乘积最大。voiddicomp(intn,inta口){k=1；if(n<3){a[1]=0;return;}if(n<5){a[k]=1;a[++k]=n-1;return;}a[1]=2;n-=2;while(n>a[k]){k++;a[k]=a[k-1]+1; n-=a[k];}if(n==a[k]){a[k]++;n--;}for(inti=0;i<n;i++)a[k-i]++;}算法练习题一回溯法一、选择题33、回溯法在问题的解空间树中，按( )策略，从根结点出发搜索解空间树。A.广度优先B. 活结点优先 C. 扩展结点优先 D. 深度优先TOC\o"1-5"\h\z34、下面哪种函数是回溯法中为避免无效搜索采取的策略( )A.递归函数 B.剪枝函数 C。随机数函数 D.搜索函数35、回溯法的效率不依赖于以下哪一个因素？( )A.产生x[k]的时间； B. 满足显式约束的x[k]值的个数；C.问题的解空间的形式； D. 计算上界函数bound的时间；36、回溯法的效率不依赖于下列哪些因素( )

A.满足显约束的值的个数 B.计算约束函数的时间C.计算限界函数的时间 D.确定解空间的时间37、下列算法中通常以深度优先方式系统搜索问题解的是( )。A、备忘录法 R动态规划法 C、贪心法 D回溯法38、回溯法搜索状态空间树是按照( )的顺序。A中序遍历B广度优先遍历C深度优先遍历D层次优先遍历39、程序块( )是回溯法中遍历排列树的算法框架程序。B.voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))

backtrack(t+1);A.voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);A.voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);if(legal(t))backtrack(t+1);swap(x[t],x[i]);}}C.voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))backtrack(t-1);}}D.voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);if(legal(t))backtrack(t+1);}}、填空题12、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是,需要排序的是,。13、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界， N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是,只使用约束条件进行裁剪的是。15、回溯法是一种既带有又带有的搜索算法。22、回溯法是指。23、用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。 在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n),则回溯法所需的计算空间通常为。24、回溯法的算法框架按照问题的解空间一般分为算法框架与算法框架。25、用回溯法解0/1背包问题时，该问题的解空间结构为结构。26、用回溯法解批处理作业调度问题时，该问题的解空间结构为结构。27、旅行售货员问题的解空间树是。28、用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时(渐进时间上限)。BoolColor::OK(intk){for(intj=1;j<=n;j++)if((a[k][j]==1)&&(x[j]==x[k]))returnfalse;returntrue;}三、简答题5、分支限界法与回溯法的异同答：相同点：都是一种在问题的解空间树T中搜索问题解的算法。不同点：(1)求解目标不同； (2)搜索方式不同；(3)对扩展结点的扩展方式不同； (4)存储空间的要求不同四、算法填空10.用回溯法解0/1背包问题时，计算结点的上界的函数如下所示，请在空格中填入合适的内容：TypepKnap<Typew,Typep>二Bound(inti)// 计算上界{Typewcleft=c-cw;// 乘U余容量Typepb=cp;// 结点的上界// 以物品单位重量价值递减序装入物品while(i<=n&&w[i]<=cleft){ ; 4.}// 装满背包if(i<=n) returnb;}五、算法题.N皇后回溯法boolQueen::Place(intk)// 检查x[k]位置是否合法{for(intj=1;j<k;j++)if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))returnfalse;returntrue;}voidQueen二Backtrack(intt){if(t>n)sum++;elsefor(inti=1;i<=n;i++){x[t]=i;if( 约束函数)Backtrack(t+1);}}.请写出用回溯法解装载问题的函数。装载问题：有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱inwi<c1c2的重量为wi,且口 。装载问题要求确定是否有一个合理的装载方案可将这 n个集装箱装上这2艘轮船。如果有，找出一种装载方案。voidbacktrack(inti)// 搜索第i层结点{if(i>n)// 到达叶结点if(cw>bestw)// 更新最优解bestx,bestw;return;{for(j=1;j<=n;j++)bestx[j]=x[j];Bestw=cw;}r-=w[i];if(cw+w[i]<=c)//搜索左子树{x[i]=1;cw+=w[i];backtrack（i+1）;cw-=w[i];}if（cw+r>bestw）// 搜索右子树{x[i]=0; backtrack（i+1）;}r+=w[i];}算法练习题一分支限界法一、选择题40、常见的两种分支限界法为（ ）A.广度优先分支限界法与深度优先分支限界法；B.队列式（FIFO）分支限界法与堆栈式分支限界法；C.排列树法与子集树法；D.队列式（FIFO）分支限界法与优先队列式分支限界法；41、分支限界法在问题的解空间树中，按（ ）策略，从根结点出发搜索解空间树A.广度优先 B. 活结点优先 C. 扩展结点优先 D. 深度优先TOC\o"1-5"\h\z42、下面不是分支界限法搜索方式的是（ ）0A、广度优先 R最小耗费优先 C、最大效益优先 D深度优先43、分支限界法解旅行售货员问题时，活结点表的组织形式是（ ）0A、最小堆 R最大堆 C、栈 D数组44、优先队列式分支限界