算法分析与设计习题集

1、算法分析与设计习题集算法分析与设计习题集算法分析与设计习题集算法分析与设计习题集整理第一章算法引论一、填空题：1、算法运转所需要的计算机资源的量，称为算法复杂性，主要包含时间复杂度和空间复杂度。2、多项式A(n)amnmLa1na0的上界为O(nm)。3、算法的基本特色：输入、输出、确立性、有限性、可行性。4、怎样从两个方面谈论一个算法的利害：时间复杂度、空间复杂度。5、计算下边算法的时间复杂度记为：O(n3)。for(i=1;i=n;i+)for(j=1;j=n;j+)cij=0;for(k=1;k=n;k+)cij=cij+aik*bkj;6、描绘算法常用的方法：自然语言、伪代码、程序设计

2、语言、流程图、盒图、PAD图。7、算法设计的基本要求：正确性和可读性。8、计算下边算法的时间复杂度记为：O(n2)。for（i1；in;i+）y=y+1;for（j0；j=2nx；j+）9、计算机求解问题的步骤：问题分析、数学模型成立、算法设计与选择、算法表示、算法分析、算法实现、程序调试、结果整理文档编制。10、算法是指解决问题的方法或过程。11、算法由操作、控制结构、数据结构三因素构成。二、简答题：1、依据时间复杂度从低到高摆列：O(4n2)、O(logn)、O(3n)、O(20n)、O(2)、O(n2/3),O(n!)应当排在哪一位2/32n答：O(2)，O(logn)，O(n)，O(2

3、0n)，O(4n)，O(3)，O(n!)2、什么是算法算法的特色有哪些答：1）算法：指在解决问题时，依据某种机械步骤必然能够获得问题结果的办理过程。2）特色：1)算法有零个或多个输入；)算法有一个或多个输出；3)确立性；)有穷性3、给出算法的定义何谓算法的复杂性计算下例在最坏状况下的时间复杂性for(j=1;j=n;j+)(1)for(i=1;i=n;i+)(2)cij=0;(3)for(k=1;k=n;k+)(4)cij=cij+aik*bkj;(5)答：1）定义：指在解决问题时，依据某种机械步骤必然能够获得问题结果的办理过程。）算法的复杂性：指的是算法在运转过程中所需要的资源（时间、空间）

4、多少。所需资源越多，表示算法的复杂性越高3）该算法的主要元操作是语句5，其履行次数是n3次。故该算法的时间复杂度记O(n3).4、算法A和算法B解同一问题，设算法A的时间复杂性知足递归方程T(n)1,n1T(n)，4T(n/2)n,n1算法B的时间复杂性知足递归方程T(n)1,n1A时间复杂T(n)，若要使得算法aT(n/4)n,n1性的阶高于算法B时间复杂性的阶，a的最大整数值可取多少答：分别记算法A和算法B的时间复杂性为TA(n)和TB(n)，解相应的递归方程得：TTAB(n)O(n2)O(n),a4(n)O(nlogn),a4O(nlog4a),a4依题意，要求最大的整数a使得TB(n)

5、TA(n)。明显，当a4时，TB(n)TA(n)log4a2a2n=2写出其相的算法IntF(intn)if(n=1)return1;elseif(n=2)return2;elsereturnF(n-1)+F(n-2);2、a,b,c是3个塔座。开始，在塔座a上有一叠共n个，些自下而上，由大到小地叠在一同。各从小到大号1,2,n,要求将塔座a上的一叠移到塔座b上，并仍按同序叠置。在移恪守以下移：1：每次只好移1个；2：任何刻都不允将大的在小的之上；3：在足移1和2的前提下，可将移至a,b,c中任一塔座上。写出的解步并写出其相的算法解：第一步：将n1个子看作一个整体，从A移到C；第二步：将第n个

6、子移到B;第三步：将n1个子看作一个整体，从C移到B；写出其相的算法：voidhanoi(intn,inta,intb,intc)if(n0)hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);第二章分治算法（2）分治算法一、填空：1、在迅速排序、插入排序和合并排序算法中，2、合并排序算法使用的是分治3、二分找寻算法是利用分治插入排序算法的思想。算法思想的。算法不是分治算法。二、答：1、适适用分治算法求解的拥有的基本特色答：1)的模小到必然的程度就能够简单解决;能够分解若干个模小的同样，即拥有最子构性；）所分解出的各个子是相互独立的，即子之不包含公共的子。4

7、）利用分解出子解能够合并解;2、分治算法基本思想，解步三、算法：1、改写二分找算法：a1n是一个已排好序的数，改写二分找算法，使合适找寻元素中，返回小于x的最大元素地点i，和大于x的最小元素地点j；当找寻元素，i和j同样，均x在数中的地点。x不在数x在数中并分析其复度解：intbinsearch(intan,intx,)3）回溯将分解的两解大者取大，小者取小，合并目前的解。、第三章动向规划算法一、填空题：1、动向规划算法中储蓄子问题的解是为了防范重复求解子问题2、（最优子结构）是问题能用动向规划算法求解的前提。3、矩阵连乘问题的算法可由（动向规划。）算法设计实现。二、判断题：1、动向规划算法基

8、本因素的是最优子结构。2、最优子结构性质是指原问题的最优解包含其子问题的最优解。3、动向规划算法求解问题时，分解出来的子问题相互独立。（）（）（X）三、简答题：1、动向规划算法解题步骤答：找出最优解的性质，并刻划其结构特色;（即原问题的最优解，包含了子问题的最优解）递归地定义最优值;（即子问题拥有重叠性，由子问题定义原问题）以自底向上的方式计算出最优值;依据计算最优值时获得的信息，结构最优解;2、动向规划算法基本思想答：动向规划算法与分治法近似，其基本思想也是将待求解问题分解成若干个子问题；可是经分解获得的子问题经常不是相互独立的。不同样子问题的数量经常只有多项式量级。在用分治法求解时，有些子

9、问题被重复计算了很多次；假如能够保留已解决的子问题的答案，而在需要时再找出已求得的答案，就能够防范大批重复计算，进而获得多项式时间算法。3、动向规划与分治算法异同点4、动向规划算法的基本因素四、算法与算：1、Xx1,x2,L,xm和Yy1,y2,L,yn的最公共子序列Zz1,z2,L,zk。：若用cij序列Xix1,x2,L,xi和Yjy1,y2,L,yj公共子序列度。求：用划法求解,算最的公式算最的算法以及结构最解的算法2、江游艇俱部在江上置了n个游艇出租站1,2n.旅客可在些游艇出租站租用游艇，并在下游的任何一个游艇出租站游艇。游艇出租站i到游艇出租站j之的租金r(i，j)，此中1=ij=

10、n；求：用划法求解,算最（最少租金）的公式算最（最少租金）的算法并分析其复度解：ri,j0ijminri,krk1,jijikj算最算法publicstaticvoidmatrixChain(intp,intm,ints)intn=;for(inti=1;i=n;i+)mii=0;要求：出Dijkstra算法的迭代程，算源到个点的最短路径（用表表示）解：本123表4-2解：迭代过程：第章回溯算法一、填空题1、回溯法与分支限界法找寻方式不同样，回溯法按深度优先找寻解空间，分支限界法按广度优先或最小耗资优先找寻解空间。二、判断题1、回溯法中限界函数的目的是剪去得不到最优解的子树。2、分支限界法近似

11、于回溯法，也是一种在问题的解空间树找寻方式是同样的。（）T上找寻问题解的算法，二者的X）三、简答题1、简述回溯法和分支限界法的同样点和不同样点2、什么是子集树什么是摆列树什么叫满m叉树3、回溯算法的基本思想回溯算法的解题步骤四、算法设计题1、n皇后问题44格的棋盘上搁置相互不受攻击的4个皇后。依据国际象棋的规则，皇后能够攻击与之处在同一行或同一列或同一斜线上的棋子。用回溯算法解决4皇后问题：结构求解该问题的解空间树设计该4皇后问题的回溯算法解：解空间树回溯算法2、01背包问题：假定有3个物件，它们的重量和价值以下表所示。若这些物件均不可以够够被切割，且背包容量M10，问应当怎样装入使背包中物件

12、的总价值最大用回溯算法求解该01背包问题：ABC结构求解该问题的解空间树物件设计该01背包问题的回溯算法重量655解：1）解空间树;价值4225302)3、图的着色问题：以以以下图给定无向连通图G和m种不同样的颜色；用这m种颜色为图G的各个极点着色，能否有一种方法使得图G中每一条边的两个极点着不同样颜色；求：结构求解该问题的解空间树设计该图的着色问题回溯算法12354解：1）解空间树：）算法:doublemcoloring(intmm)intm=mm;法1：行列式（FIFO先进先出）分支限界法?从根结点1开始；将活结点组织成一个行列；?初始时活结点行列为空，结点加入行列，结点1为目前扩展结点；

13、1?结点1的孩子结点2、9为可行结点，故舍弃目前结点1，将2、9加入活结点行列；29?先进先出原则，2作为目前扩展结点，其孩子结点3、6；因为结点3是不可以行结点舍弃；将结点6加入活结点行列；96?先进先出原则，9作为目前扩展结点，其孩子结点10、13;结点10、13是可行结点加入活结点行列；61013ntValue();ntValue();回溯法解TSP问题时的解空间树是（A）。A、子集树B、摆列树C、深度优先生成树D、广度优先生成树6以下算法中平常以自底向上的方式求解最优解的是（B）。、备忘录法B、动向规划法C、贪婪法D、回溯法7、权衡一个算法利害的标准是（C）。A运转速度快B占用空间少C

14、时间复杂度低D代码短8、以下不可以够够使用分治法求解的是（D）。A棋盘覆盖问题B选择问题C合并排序D0/1背包问题实现循环赛日程表利用的算法是（A）。、分治策略B、动向规划法C、贪婪法D、回溯法10、实现最长公共子序列利用的算法是（B）。A、分治策略B、动向规划法C、贪婪法D、回溯法11下边不是分支界限法找寻方式的是（D）。、广度优先B、最小耗资优先C、最大效益优先D、深度优先12以下算法中平常以深度优先方式系统找寻问题解的是（D）。A、备忘录法B、动向规划法C、贪婪法D、回溯法13.一个问题可用动向规划算法或贪婪算法求解的重点特色是问题的（B）。A、重叠子问题B、最优子结构性质C、贪婪选择性

15、质D、定义最优解14广度优先是（A）的一找寻方式。A、分支界限法B、动向规划法C、贪婪法D、回溯法15背包问题的贪婪算法所需的计算时间为（B）。A、O（n2）nB、O（nlogn）C、O（2）nD、O（n）16实现最大子段和利用的算法是（B）。、分治策略B、动向规划法C、贪婪法D、回溯法17实现棋盘覆盖算法利用的算法是（A）。、分治法B、动向规划法C、贪婪法D、回溯法下边是贪婪算法的基本因素的是（C）。、重叠子问题B、结构最优解C、贪婪选择性质D、定义最优解回溯法的效率不依靠于以下哪些因素（D）A.知足显拘束的值的个数C.计算限界函数的时间B.计算拘束函数的时间D.确立解空间的时间下边哪一种函

16、数是回溯法中为防范无效找寻采纳的策略（B）A递归函数剪枝函数C。随机数函数D.找寻函数21、以深度优先方式系统找寻问题解的算法称为(D)。A、分支界限算法B、概率算法C、贪婪算法D、回溯算法22、贪婪算法与动向规划算法的主要差别是（B）。、最优子结构B、贪婪选择性质C、结构最优解D、定义最优解采纳最大效益优先找寻方式的算法是（A）。、分支界限法B、动向规划法C、贪婪法D、回溯法（D）是贪婪算法与动向规划算法的共同点。A、重叠子问题B、结构最优解C、贪婪选择性质D、最优子结构性质25.矩阵连乘问题的算法可由（B）设计实现。A、分支界限算法B、动向规划算法C、贪婪算法D、回溯算法26.0-1背包问

17、题的回溯算法所需的计算时间为（A）A、O（n2n）B、O（nlogn）C、O（2n）D、O（n）27、背包问题的贪婪算法所需的计算时间为（B）A、O（n2）B、O（nlogn）C、O（2）D、O（n）29、使用分治法求解不需要知足的条件是（A）。A子问题必然是同样的B子问题不可以够够重复C子问题的解能够合并D原问题和子问题使用同样的方法解30、下边问题（B）不可以够使用贪婪法解决。nnA单源最短路径问题BN皇后问题C最小开支生成树问题D背包问题31、以下算法中不可以够解决0/1背包问题的是（A）A贪婪法B动向规划C回溯法D分支限界法32、回溯法找寻状态空间树是依据（C）的次序。A中序遍历B广度

18、优先遍历C深度优先遍历D层次优先遍历33、采纳广度优先策略找寻的算法是（A）。、分支界限法B、动向规划法C、贪婪法D、回溯法34实现合并排序利用的算法是（A）。A、分治策略B、动向规划法C、贪婪法D、回溯法35以下是动向规划算法基本因素的是（D）。A、定义最优解B、结构最优解C、算出最优解D、子问题重叠性质36以下算法中平常以自底向下的方式求解最优解的是（B）。A、分治B、动向规划法C、贪婪法D、回溯法二、填空题算法的复杂性有时间复杂性和空间复杂性之分。2、程序是算法用某种程序设计语言的详细实现。3、算法的“确立性”指的是构成算法的每条指令是清楚的，无歧义的。矩阵连乘问题的算法可由动向规划设计实现。5、算法是指解决问题的一种方法或一个过程。6、迅速排序算法的性能取决于区分的对称性。7、从分治法的一般设计模式能够看出，用它设计出的程序一般是递归算法8、问题的最优子结构性质是该问题可用动向规划算法或贪婪算法求解的重点特色。9、以深度优先方式系统找寻问题解的算法称为回溯法。10、任何可用计算机求解的问题所需的时间都与其规模有关。11、计算一个算法时间复杂度平常能够计算或计算步。循环次数、基本操作的频次12、回溯法找寻解空间树时，常用的两种剪枝函数为拘束函数和限界函数14、解决0/1背