算法期末复习题

1、v1.0可编辑可修改14算法分析与设计期末复习题目一、选择题1.下列算法中通常以自底向上的方式求解最优解的是（B回溯法A、备忘录法R动态规划法C、贪心法D2、衡量一个算法好坏的标准是（C）。A运行速度快B占用空间少C时间复杂度低D代码短3、以下不可以使用分治法求解的是（D）。A棋盘覆盖问题B选择问题C归并排序D0/1背包问题4 .下列是动态规划算法基本要素的是（D）。子问题A、定义最优解B、构造最优解C、算出最优解D、重叠性质5 .采用广度优先策略搜索的算法是（A）。回溯法A、分支界限法B、动态规划法C、贪心法D6、合并排序算法是利用（A）实现的算法。A、分治策略B、动态规划法C、贪心法D、回

2、溯法7、下列不属于影响程序执行时间的因素有哪些（C）A.算法设计的策略B.问题的规模C.编译程序产生的机器代码质量D.计算机执行指令的速度8、使用分治法求解不需要满足的条件是（A）。A子问题必须是一样的B子问题不能够重复C子问题的解可以合并D原问题和子问题使用相同的方法解9、下面问题（B）不能使用贪心法解决A单源最短路径问题C最小花费生成树问题B N皇后问题D背包问题10 .一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（B）。A重叠子问题R最优子结构性质G贪心选择性质D定义最优解11 .以深度优先方式系统搜索问题解的算法称为（D）。A、分支界限算法算法B、概率算法12 .实现最长公

3、共子序列利用的算法是（A、分治策略B、动态规划法13 .下列算法具有最优子结构的算法是A.概率算法B .回溯法 C14 .算法分析是（C）C、贪心算法D、回溯B）。C、贪心法D回溯法（D）.分支限界法 D .动态规划法A.将算法用某种程序设计语言恰当地表示出来B.在抽象数据集合上执行程序，以确定是否会产生错误的结果C.对算法需要多少计算时间和存储空间作定量分析D.证明算法对所有可能的合法输入都能算出正确的答案15衡量一个算法好坏的标准是（C）16A.运行速度快B.占用空间少C.时间复杂度低D.代码短16 .二分搜索算法是利用（A）实现的算法。A.分治法B.动态规划法C.贪心法D.回溯法17 .

4、用贪心法设计算法的关键是(B)。A.将问题分解为多个子问题来分别处理B.选好最优量度标准C.获取各阶段间的递推关系式D.满足最优性原理18.找最小生成树的算法Kruskal的时间复杂度为(D)(其中n为无向图的结点数，m为边数)2、1 .O(n)B.O(mlogn)C.O(nlogm)D.O(mlogm)19 .回溯法搜索状态空间树是按照(C)的顺序。A.中序遍历B.广度优先遍历C.深度优先遍历D.层次优先遍历20 .采用广度优先策略搜索的算法是(A)。A.分支界限法B.动态规划法C.贪心法D.回溯法21 .函数32n+10nlogn的渐进表达式是(B).(2n)B.O(32n)C.O(nlo

5、gn)D.O(10nlogn)22 .二分搜索算法的时间复杂性为(C)。(n2)(n)(10gn)d.o(nlogn)23、快速排序算法的时间复杂性为(D)。(n2)(n)(logn)d.O(1n10gn)24、算法是由若干条指令组成的有穷序列，而且满足以下性质(D)A.输入：有0个或多个输入B.输出：至少有一个输出C.确定性：指令清晰，无歧义D.有限性：指令执行次数有限，而且执行时间有限A.(1)(2)(3)B.(1)(2)(4)C.(1)(3)(4)D.(1)(2)(3)(4)25、背包问题的贪心算法所需的计算时间为(B)A.O(n2n)B.O(nlogn)(2n)(n)26 .下列算法中

6、不能解决0/1背包问题的是(A)A贪心法B动态规划C回溯法D分支限界法27 .在寻找n个元素中第k小元素问题中，若使用快速排序算法思想，运用分治算法对n个元素进行划分，应如何选择划分基准下面(D)答案解释最合理。A.随机选择一个元素作为划分基准B.取子序列的第一个元素作为划分基准C.用中位数的中位数方法寻找划分基准D.以上皆可行。但不同方法，算法复杂度上界可能不同28.分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题(C)。A.问题规模相同，问题性质相同B.问题规模相同，问题性质不同C.问题规模不同

7、，问题性质相同D.问题规模不同，问题性质不同29、下面是贪心算法的基本要素的是(C)。A、重叠子问题R构造最优解G贪心选择Tt质D定义最优解230.函数3n10n的渐进表达式是(D)。-22A.O(3n)B.0(3)C.0(10n)(n)二、填空题1、解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是动态规划，需要排序的是回溯法,分支限界法。2、使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进行裁剪的是0/1背包问题,只使用约束条件进行裁剪的是N皇后问题。3 .

8、贪心算法基本要素有最优度量标准和最优子结构。4 .回溯法解旅行售货员问题时的解空间树是排列树。5 .二分搜索算法是利用分治策略实现的算法。6 .算法的复杂性有旺回复杂性和空间复杂性之分。7、程序是算法用某种程序设计语言的具体实现。8、算法的“确定性”指的是组成算法的每条指令是清晰的、无歧义的。9 .矩阵连乘问题的算法可由动态规划设计实现。10 .回溯法搜索解空间树时，常用的两种剪枝函数为约束函数和限界函数。11 .任何可用计算机求解的问题所需的时间都与其规模有关。12 .快速排序算法的性能取决于划分的对称性。13 .背包问题的贪心算法voidKnapsack(intn,floatM,float

9、v,floatw,floatx口)Sort(n,v,w);inti;for(i=1;i<=n;i+)xi=0;floatc=M;for(i=1;i<=n;i+)if(wi>c)break;xi=1;c-=wi;if(i<=n)xi=c/wi;14 .下面算法的基本运算是加法(或：赋值)运算，该算法中第4步执行了2n-1次。算法COUNT输入：正整数n(n=2k)。输出：count的值。1. count=02. whilen>=13. forj=1ton4. count=count+15. endfor6. n=n/27. endwhileendCOUNT15 .算

10、法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有限性四条性质。16 .快速排序、插入排序和选择排序算法中，快速排序算法是分治算法17 .下面算法的基本语句是S=S+i*j;一算法的时间复杂度是2O(n)intfun(intn)intS=0;for(inti=1;i<=n;i+)for(intj=1;j<ni;j+)S=S+i*j;returnS;18 .最小生成树的prim算法应用的是贪心算法思想。19 .分治算法的基本步骤包括分解子问题，递归求解子问题，合并解20 .归并排序和快速排序在平均情况下的时间复杂度都是O(nlogn),但是最坏2情况下两种算法有区别，其中

11、归并排序为_O(nlogn)，快速排序为_O(n)二、算法设计1 .下面是用回溯法求解图的m着色问题的算法(求出所有解)。图的m着色问题：给定一个无向连通图G和m种颜色，给图G的所有顶点着色，使得任何两相邻顶点的颜色不同。已有函数color(k)用于在前k-1个顶点已着色的情况下，判断第k个顶点是否可着颜色xk;是则返回true,否则返回falseo输入：正整数m,n和含n个顶点的无向连通图G的邻接矩阵graph。输出：图G的m着色问题的所有解，若无解，则输出nosolution。flag=falsek=1;x1=0whilek>=1while(1)xk=xk+1ifcolor(k)th

12、enif(2)thenflag=true;outputx1.nelsek=(3)(4)endifendifendwhile(5)endwhileifnotflagthenoutput“nosolutionendm-COLORINGxk<m(2)k=n(3)k+1xk=0(5)k=k-12.下面是求解矩阵链乘问题的动态规划算法。矩阵链乘问题：给出n个矩阵M,M2,，Mn,Mi为ri门+1阶矩阵，i=1,2,，n,求计算MMM所需的最少数量乘法次数。记Mi,j=MM+iM,i<=j。设Ci,j,1<=i<=j<=n,表示计算Mj的所需的最少数量乘法次数，则.0，ijC

13、i，jminCi,k-1Ck,jMg1,ijikJ算法MATCHAIN输入：矩阵链长度n,n个矩阵的阶r1.n+1,其中r1.n为n个矩阵的行数，rn+1为第n个矩阵的列数。输出：n个矩阵链乘所需的数量乘法的最少次数。fori=1tonCi,i=O)ford=1ton-1fori=1ton-dj=_J2)Ci,j=8fork=i+1tojx=(3)ifx<Ci,jthen(4)=xendifendforendforendforreturn(5)endMATCHAIN(1)0(2)i+d(3)Ci,k-1+Ck,j+ri*rk*rj+1Ci,j(5)C1,n3.下面是用回溯法解n皇后问题的

14、算法(求出所有解)。n皇后问题：在nxn棋盘上放置n个皇后使得任何两个皇后不能互相攻击。(如果两个皇后处在同一行，或同一列，或同一斜线上，则她们能互相攻击。)算法NQUEENS输入：正整数n0输出：n皇后问题的所有解x1.n,若无解，则输出Nosolutionflag=falsek=1;x1=0while_(1)whilexk<nxk=(2)ifplace(k)thenifk=nthenflag=true;outputx1.nelsek=(3)(4)endifendifendwhile(5)endwhileifnotflagthenoutput“Nosolution”endNQUEENS

15、过程place(k)递归的快速排序算法：template<classType>voidQuicksort(Typea,intlow,inthigh)if()inti=Partition(a,low,high);QuickSort(a,low,i-1);(2);解：(1)low<high(2)QuickSort(a,i+1,high)5、n后问题的递归的回溯算法，设已经存在全局变量n代表皇后个数。voidQueen二Backtrack(intt)if()sum+;个物品，其重量分别为(3,2,1,4,5),价值分别为(25,20,15,40,50),背包容量为6.写出求解过程(

16、设计表格和填写表格)解：设计一个二维表V(i,j)表示将前i个物品装进容量为j的背包所能获得的最大价值，根据以下递推式填表：若w>j,V(i,j)=V(i1,j)若wi<=j,V(i,j)=maxV(i-1,j),V(i-1,j-wi)+vij=0j=1j=2j=3j=4j=5j=6i=00000000i=100025252525i=2002025254545i=30152035404560i=40152035405560i=50152035405565V(5,6)即为问题的最优解，最大价值为65。经过回溯得到物品组合为第3和第5个物品装入背包。4.归并排序算法对下列实例排序，写出算法执行过程。A=(48,12,61,3,5,19,32,7)解：拆分：48,12,61,348,1261,348 12 61合并：12,483,613, 12,48, 613,5, 7,125,19,32,75,1932,735193275,197,325,7,19,32,19,32,48,615、简述分治法的基本思想。答：分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同；对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易