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

算法练习题---算法概述一、选择题1、下面关于算法的描述，正确的是（）A、一个算法只能有一个输入B、算法只能用框图来表示C、一个算法的执行步骤可以是无限的D、一个完整的算法，不管用什么方法来表示，都至少有一个输出结果2、一位爱好程序设计的同学，想通过程序设计解决“韩信点兵”的问题，他制定的如下工作过程中，更恰当的是（）A、设计算法，编写程序，提出问题，运行程序，得到答案B、分析问题，编写程序，设计算法，运行程序，得到答案C、分析问题，设计算法，编写程序，运行程序，得到答案D、设计算法，提出问题，编写程序，运行程序，得到答案3、下面说法正确的是（）A、算法+数据结构=程序B、算法就是程序C、数据结构就是程序D、算法包括数据结构4、衡量一个算法好坏的标准是（）。A、运行速度快B、占用空间少C、时间复杂度低D、代码短5、解决一个问题通常有多种方法。若说一个算法“有效”是指()。A、这个算法能在一定的时间和空间资源限制内将问题解决B、这个算法能在人的反应时间内将问题解决C、这个算法比其他已知算法都更快地将问题解决D、A和C6、算法分析中，记号O表示（），记号表示（）。A.渐进下界B.渐进上界C.非紧上界D.非紧下界7、以下关于渐进记号的性质是正确的有：（）A.f(n)(g(n)),g(n)(h(n))f(n)(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、记号O的定义正确的是（）。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)}；C.O(g(n))={f(n)|对于任何正常数c0，存在正数和n00使得对所有nn0有0f(n)cg(n)}；D.O(g(n))={f(n)|对于任何正常数c0，存在正数和n00使得对所有nn0有：0cg(n)f(n)}；9、记号的定义正确的是（）。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)}；C．O(g(n))={f(n)|对于任何正常数c0，存在正数和n00使得对所有nn0有：0f(n)cg(n)}；D．O(g(n))={f(n)|对于任何正常数c0，存在正数和n00使得对所有nn0有：0cg(n)f(n)}；二、填空题1、算法的性质包括输入、输出、、、有限性。4、算法的复杂性是的度量，是评价算法优劣的重要依据。6、计算机的资源最重要的是时间和空间资源。因而，算法的复杂性有和之分。7、算法复杂度依赖于三方面：、和算法本身。8、程序是用某种程序设计语言的具体实现。9、算法是指解决问题的或步骤的描述。11、计算一个算法时间复杂度通常可以计算、或计算步。16、任何可用计算机求解的问题所需的时间都与其有关。算法练习题---递归与分治策略一、选择题10、Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（）A.voidhanoi(intn,intA,intC,intB){if(n0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}B.voidhanoi(intn,intA,intB,intC){if(n0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}11、二分搜索算法是利用（）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法12、以下不可以使用分治法求解的是（）。A棋盘覆盖问题B选择问题C归并排序D0/1背包问题13、实现循环赛日程表利用的算法是（）。A、分治策略B、动态规划法C、贪心法D、回溯法14、实现棋盘覆盖算法利用的算法是（）。A、分治法B、动态规划法C、贪心法D、回溯法15、Strassen矩阵乘法是利用（）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法16、使用分治法求解不需要满足的条件是（）。A子问题必须是一样的B子问题不能够重复C子问题的解可以合并D原问题和子问题使用相同的方法解17、实现合并排序利用的算法是（）。A、分治策略B、动态规划法C、贪心法D、回溯法18、实现大整数的乘法是利用的算法（）。A、贪心法B、动态规划法C、分治策略D、回溯法二、填空题5、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相且与原问题相同。10、从分治法的一般设计模式可以看出，用它设计出的程序一般是。14、快速排序算法是基于的一种排序算法。17、快速排序算法的性能取决于三、简答题3、分治法所能解决的问题一般具有的几个特征是：答：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质;C.voidhanoi(intn,intC,intB,intA){if(n0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}D.voidhanoi(intn,intC,intA,intB){if(n0){hanoi(n-1,A,C,B);move(n,a,b);hanoi(n-1,C,B,A);}}（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。4、分治法与动态规划法的异同。答：相同点：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。不同点：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。8、老板有一袋金块（共n块，n是2的幂（n=2）），最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重的金块。答：n≤2，识别出最重和最轻的金块，一次比较就足够了。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(k0){printf(%d\n,k);f(k-1);f(k-1);}}四、算法填空5.快速排序voidQuickSort(inta[],intp,intr){if(pr){intq=Partition(a,p,r);;//对左半段排序;//对右半段排序}}6.排列问题voidperm(intlist[],intk,intm){//产生[list[k:m]的所有排列if(){//只剩下一个元素for(inti=0;i=m;i++)coutlist[i];coutendl;}else//还有多个元素待排列，递归产生排列for(){swap(list[k]，list[i]);;swap(list[k],list[i]);}}五、算法题1.给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x，返回其在数组中的位置，如果未找到返回-1。写出二分搜索的算法，并分析其时间复杂度。templateclassTypeintBinarySearch(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(xa[middle])left=middle+1;elseright=middle-1;}Return-1;}时间复杂性为O(logn)2.利用分治算法写出合并排序的算法，并分析其时间复杂度voidMergeSort(Typea[],intleft,intright){if(leftright)//至少有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、构造最优解C、算出最优解D、定义最优解20、最长公共子序列算法利用的算法是（）。A、分支界限法B、动态规划法C、贪心法D、回溯法21、动态规划算法的基本要素为（）A.最优子结构性质与贪心选择性质B．重叠子问题性质与贪心选择性质C．最优子结构性质与重叠子问题性质D.预排序与递归调用22、矩阵连乘问题的算法可由（）设计实现。A、分支界限算法B、动态规划算法C、贪心算法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(thissumsum){sum=thissum;besti=i;bestj=j;}}}returnsum;}21、所谓最优子结构性质是指。三、简答题1、请叙述动态规划算法与贪心算法的异同。答：共同点：都需要最优子结构性质，不同点：（1）动态规划：每一步作一个选择—依赖于子问题的解。贪心方法：每一步作一个选择—不依赖于子问题的解。（2）动态规划方法的条件：子问题的重叠性质。贪心方法的条件：最优子结构性质；贪心选择性质。（3）动态规划：自底向上求解；贪心方法：自顶向下求解。2、设计动态规划算法的主要步骤为：答：（1）找出最优解的性质，并刻划其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。4、分治法与动态规划