算法分析复习题目及答案

一。选择题1、二分搜索算法是利用（A）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是（A）。A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解7、衡量一个算法好坏的标准是（C）。A运行速度快B占用空间少C时间复杂度低D代码短8、以下不可以使用分治法求解的是（D）。A棋盘覆盖问题B选择问题C归并排序D0/1背包问题14．哈弗曼编码的贪心算法所需的计算时间为（B）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）18.下面是贪心算法的基本要素的是（C）。A、重叠子问题B、构造最优解C、贪心选择性质D、定义最优解24.（D）是贪心算法与动态规划算法的共同点。A、重叠子问题B、构造最优解C、贪心选择性质D、最优子结构性质25.矩阵连乘问题的算法可由（B）设计实现。A、分支界限算法B、动态规划算法C、贪心算法D、回溯算法27、Strassen矩阵乘法是利用（A）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法29、使用分治法求解不需要满足的条件是（A）。A子问题必须是一样的B子问题不能够重复C子问题的解可以合并D原问题和子问题使用相同的方法解30、下面问题（B）不能使用贪心法解决。A单源最短路径问题BN皇后问题C最小花费生成树问题D背包问题31、下列算法中不能解决0/1背包问题的是（A）A贪心法B动态规划C回溯法D分支限界法34．实现合并排序利用的算法是（A）。A、分治策略B、动态规划法C、贪心法D、回溯法35．下列是动态规划算法基本要素的是（D）。A、定义最优解B、构造最优解C、算出最优解D、子问题重叠性质36．下列算法中通常以自底向下的方式求解最优解的是（B）。A、分治法B、动态规划法C、贪心法D、回溯法38、合并排序算法是利用（A）实现的算法。A、分治策略B、动态规划法C、贪心法D、回溯法40、背包问题的贪心算法所需的计算时间为（B）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）41．实现大整数的乘法是利用的算法（C）。A、贪心法B、动态规划法C、分治策略D、回溯法44．贪心算法与动态规划算法的主要区别是（B）。A、最优子结构B、贪心选择性质C、构造最优解D、定义最优解47.背包问题的贪心算法所需的计算时间为（B）。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）52.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（B）。A、重叠子问题B、最优子结构性质C、贪心选择性质D、定义最优解53．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为(B)。A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）55.实现最长公共子序列利用的算法是（B）。A、分治策略B、动态规划法C、贪心法D、回溯法二、填空题1.算法的复杂性有时间复杂性和空间复杂性之分。2、程序是算法用某种程序设计语言的具体实现。3、算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的。4.矩阵连乘问题的算法可由动态规划设计实现。7、从分治法的一般设计模式可以看出，用它设计出的程序一般是递归算法。8、问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。11、计算一个算法时间复杂度通常可以计算循环次数、基本操作的频率或计算步。16、贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。17、矩阵连乘问题的算法可由动态规划设计实现。19.贪心算法的基本要素是贪心选择质和最优子结构性质。21.动态规划算法的基本思想是将待求解问题分解成若干子问题，先求解子问题，然后从这些子问题的解得到原问题的解。22.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。23、大整数乘积算法是用分治法来设计的。26、贪心选择性质是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。27.快速排序算法是基于分治策略的一种排序算法。28.动态规划算法的两个基本要素是.最优子结构性质和重叠子问题性质。。34.任何可用计算机求解的问题所需的时间都与其规模有关。35.快速排序算法的性能取决于划分的对称性。三、算法填空1.背包问题的贪心算法voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);inti;for(i=1;i=n;i++)x[i]=0;floatc=M;for(i=1;i=n;i++){if(w[i]c)break;x[i]=1;c-=w[i];}if(i=n)x[i]=c/w[i];}4.贪心算法求活动安排问题templateclassTypevoidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;intj=1;for(inti=2;i=n;i++){if(s[i]=f[j]){A[i]=true;j=i;}elseA[i]=false;}}5.快速排序templateclassTypevoidQuickSort(Typea[],intp,intr){if(pr){intq=Partition(a,p,r);QuickSort(a,p,q-1);//对左半段排序QuickSort(a,q+1,r);//对右半段排序}}Partition()四、问答题1.分治法的基本思想时将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。2设计动态规划算法的主要步骤为：（1）找出最优解的性质，并刻划其结构特征。（2）递归地定义最优值。（3）以自底向上的方式计算出最优值。（4）根据计算最优值时得到的信息，构造最优解。3.分治法与动态规划法的相同点是：将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。两者的不同点是：适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的。而用分治法求解的问题，经分解得到的子问题往往是互相独立的。6.分治法所能解决的问题一般具有的几个特征是：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质;（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）原问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。五、算法题*1.给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素x，返回其在数组中的位置，如果未找到返回-1。写出二分搜索的算法，并分析其时间复杂度。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.利用分治算法写出合并排序的算法，并分析其时间复杂度1.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)。6．哈弗曼编码算法