算法分析与设计习题集整理

1、精选文档算法分析与设计习题集整理第一章算法引论一、填空题：1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。2、多项式的上界为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、描述算法常用的方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD图。7、算法设计的基本要求：正确性

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

3、( 4n2)，O( 3n)，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、处理过程。 2）算法的复杂性：指的是算法在运行过程中所需要的资源（时间、空间）多少。 所需资源越多，表明算法的复杂性越高 3）该算法的主要元操作是语句5，其执行次数是n3次。故该算法的时间复杂度记为O(n3). 4、算法A和算法B解同一问题，设算法A的时间复杂性满足递归方程，算法B的时间复杂性满足递归方程，若要使得算法A时间复杂性的阶高于算法B时间复杂性的阶，a的最大整数值可取多少？答：分别记算法A和算法B的时间复杂性为和，解相应的递归方程得： 依题意，要求最大的整数a使得。显然，当a4时， a2写出其相应的递归算法？Int F(int n) if(n=1) return 1; else if

5、(n=2) return 2; else return F(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；写出其相应的递归算法：void hanoi(int n, int a, int b, int c) if (n 0) hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); 第二章 分治算法（2）分治算法一、填空题：1、在快速排序、插入排序和合并排序算法中， 插入排序 算法不是分治算法。2、合并排序算法使用的是 分治 算法设计的思想。3、二分搜索算法是利用 分治 算法思想设计的。二、简答题：1、适合用分治算法求解的问题具有的基本特征？答：1)该问题的规模缩小到一定的程度就可以容易解决;2)该问

7、题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； 3）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 4）利用该问题分解出子问题解可以合并为该问题解;2、分治算法基本思想，解题步骤？ 三、算法设计题：1、改写二分查找算法：设a1n是一个已经排好序的数组，改写二分查找算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i，和大于x的最小元素位置j；当搜索元素x在数组中时，i和j相同，均为x在数组中的位置。并分析其时间复杂度？ 解：int binsearch( int an, int x ,) /x待查数据int mid, i , j; low=

8、1; int high=n;while(lowx) high=mid-1; /继续在左边查找else / (amid=2）个元素的集合中寻找极大元和极小元。用分治法（二分法）可以用较少比较次数地解决上述问题：1）将数据等分为两组（两组数据可能差1），目的是分别选取其中的最大（小）值。2)递归分解直到每组元素的个数2,可简单地找到最大(小)值.3）回溯时将分解的两组解大者取大，小者取小，合并为当前问题的解。 、 第三章动态规划算法一、填空题：1、动态规划算法中存储子问题的解是为了 避免重复求解子问题 。2、（ 最优子结构 ）是问题能用动态规划算法求解的前提。3、矩阵连乘问题的算法可由（动态规划

9、）算法设计实现。二、判断题：1、动态规划算法基本要素的是最优子结构。 （ ）2、最优子结构性质是指原问题的最优解包含其子问题的最优解。 （ ）3、动态规划算法求解问题时，分解出来的子问题相互独立。 （ X）三、简答题：1、动态规划算法解题步骤？答：找出最优解的性质，并刻划其结构特征;（即原问题的最优解，包含了子问题的最优解）递归地定义最优值;（即子问题具有重叠性，由子问题定义原问题）以自底向上的方式计算出最优值;根据计算最优值时得到的信息，构造最优解;2、动态规划算法基本思想？答：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题；但是经分解得到的子问题往往不是互相独立的。

10、不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次；如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。3、动态规划与分治算法异同点？4、动态规划算法的基本要素？ 四、算法设计与计算题：1、和的最长公共子序列为。问：若用记录序列和公共子序列长度。求：用动态规划法求解时,计算最优值的递归公式？ 设计计算最优值的算法？以及构造最优解的算法？2、长江游艇俱乐部在长江上设置了n个游艇出租站1,2n.游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i

11、，j)，其中1=ij=n；求：用动态规划法求解时,计算最优值（最少租金）的递归公式？设计计算最优值（最少租金）的算法？并分析其时间复杂度？解：计算最优值算法public static void matrixChain(int p, int m, int s) int n=p.length-1; for (int i = 1; i = n; i+) mii = 0; /1个站 for (int r = 2; r = n; r+) for (int i = 1; i = n - r+1; i+) int j=i+r-1; m i j = mii + mi+1 j; s i j = i; /断点位置

12、在i处 for (int k = i+1; k j; k+) int t = m i k + mk+1 j; if (t mij) m i j = t; s i j = k; 构造最优解算法public void traceback( int s,int I,int j)if(i=j) return;traceback( s, i, s i j );traceback( s, s i j+1, j );System.out.println(“A”+ i +“，”+ s i j + “A”+ s i j+1 +“,”+ j ) /(m i, s i j ) (m s i j+1, j )时间复杂

13、度：O(n3)第 4 章 贪心算法一、填空题：1、某单位给每个职工发工资（精确到元）。为了保证不要临时兑换零钱, 且取款的张数最少，统计所需各种币值(100,50,20,10,5,2,1元共七种)的张数。贪心算法如下：void greedy_zhaoling ( float GZ, int B , int S ) /GZ应发工资 for( j=1, j=7;j+) /贪心选择，依次给最大币种 A= GZ/B j ; /A表示对应j币种张数 S j= S j +A ; /S j存放对应j币种总张数 GZ= GZ-A*B j ; for(i=1;i=7;i+) print( B i , “-”,

14、S i ); /输出币种和对应张数 2、贪心算法的两个基本要素是（贪心选择性 ）和（ 最优子结构 ）。 3、给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为M，应如何选择装入背包的物品，使得装入背包中物品的总价值最大。贪心算法如下：float greedy_knapsack ( float M, float w , float p , float x ) / x 背包问题最优解, w 物品重量， P 物品价值 int n=w.length;float pp=0;float mmM; /pp计算当前总价值，mm背包剩余载重for( int i=1;i=n; i+ ) flo

15、at ww i= p i / w i ； /计算物品单位价值ww x i=0; /初始化Mergesort ( w , n ); /按单位价值将物品排序， 便于贪心选择for( int i=1; i=n; i+ ) /贪心选择，总是选择价值最大放入背包 if ( w i=mm ) /当前物品小于背包剩余载重 x i=1; mm= mm - w i ; pp= pp + p i ; else x i=mm/w i; pp= pp + x i*p i ; break; /i部分放入背包return pp;二、判断题：1、满足贪心选择性质必满足最优子结构性质。 （ X ）三、简答题： 1、贪心算法的

16、基本思想？2、贪心算法的基本要素？3、贪心算法与动态规划算法的异同?四、算法设计题：1、假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量M150，如果使用贪心方法求解此背包问题（背包不超载的前提下，装载的物品价值达到最大）。物品ABCDEFG重量35306050401025价值10403050354030利用贪心算法求解该问题时，为了进行贪心选择，首先应该做什么？ 然后进行贪心装载，给出一种正确的物品装载顺序？并给出其最优装载方案？ 利用贪心思想设计该普通背包问题的贪心算法？分析其时间复杂度？解： 1）依据不同的标准对这些物品进行排序，标准有重量、价值、单位价值；

17、 2）重量从小到大：FGBAEDC ,得到的贪心解为：FGBAE 全部放入,D放入20% ，得到价值为165； 价值从大到小 ：DFBEGCA ，得到的贪心解为：DFBE 全部放入,G放入80% ，得到价值为189； 单位价值从大到小 ：FBGDECA ，得到的贪心解为：FBGD 全部放入,E放入87.5% ，得到价值为190.625； 3)显然使用单位价值得出最佳转载方案。 、2、设有n个活动集合，其中每个活动都要求使用同一资源，如足球场，而在同一时间只能有一个活动使用该资源。每个活动i都有一个要求使用该资源起始时间si和结束时间fi，且si n ) / 搜索到叶子节点 sum+; /着色方

18、案数加1 for (int i=1; i=n; i+) system.out.print( x i ); /输出解,顶点i着颜色x i else / 搜索到中间节点 for(int i=1; i=m; i+) x t=i; /顶点t着颜色i=1m if( ok( t ) ) backtrack(t+1); boolean ok( int k) /当前着色顶点与以前相邻顶点是否同色 for(int j=1; j=n; j+) if( a k j&( x j=x k ) ) /数组a是图的邻接矩阵 /当前顶点k到j有边：a k j，且色同：x j=x k return false; else re

19、turn true;算法分析（m种颜色，n个节点） 计算限界函数，一重for循环时间复杂度：O(n); 在最坏的情况下每一个内节点都需要判断约束，内节点个数：1+m+m2+ m3+mn-1=(mn-1)/(m-1)个；故图的m着色问题的回溯算法，时间复杂度为：O(n*mn)。第六章 分支限界算法一、填空题1、按照活结点表的组织方式的不同，分支限界法包括 队列式分支限界算法 和 优先队列式分支限界算法 两种形式。2、回溯法与分支限界法搜索方式不同，回溯法按 深度优先 搜索解空间，分支限界法按 广度优先或最小耗费优先 搜索解空间。3、队列分支限界算法中，通常用队列 实现，体现先进先出原则 的原则。

20、4、优先队列式分支限界算法，通常采用堆实现。6、回溯法与分支限界算法求解问题时，需要构造对该问题的解空间结构,其解空间结构通常有3种形式，分别是 子集树 、排列树、 满m叉树 。二、判断题1、分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法，两者的搜索方式是相同的。（X）三、简答题1、简述分支限界法的基本思想与解题步骤？2、分支限界算法与回溯算法异同点？四、算法设计题1、01背包问题：假设有3个物品，它们的重量和价值如下表所示。若这些物品均不可以被分割，且背包容量M10，问应该如何装入使背包中物品的总价值最大？物品ABC重量655价值422530用分支限界算法求解该01背包

21、问题： 构造求解该问题的解空间树？ 给出队列式分支限界算法的求解过程？如设计该01背包问题的分支限界算法？并分析其时间复杂度？（队列式分支限界，带上界函数）、多段图最短路径问题求：构造求解该问题的解空间树？ 给出队列式分支限界算法的求解过程？设计该问题的分支限界算法？并分析其时间复杂度？（队列式分支限界，带上界函数）解：2）求解过程：）算法描述： 法:队列式分支限界法double shortest( int i) while (true) /队列不空， 搜索问题的解空间 for ( int j=1; j=n;j+)/儿子结点入队 if (a i j Float.MAX_VALUE) / 顶点i

22、到顶点j可达 dist j= dist i +a i j; / dist i记录源到顶点的距离 p j=enode.i; / p j记录顶点j的前驱 enQueue(v j, j); / 结点j加入队列 ew = (Integer) queue.remove().intValue();/ 取队首下一扩展结点 if (ew = -1) / 同一层尾部标记ew = -1：同一层结点处理结束 if (queue.isEmpty() return dist i;/判断队列是否为空 else queue.put(new Integer(-1); / 同层结点尾部标志 ew = (Integer) que

23、ue.remove().intValue(); / 取下一扩展结点 i+; / 进入下一层 时间复杂度：第七章 概率算法1、什么叫概率算法？答：概率算法允许算法在执行的过程中随机选择下一个计算步骤。2、概率算法有一个基本特征？答：基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。3、概率算法可以分为哪4类？答：1)数值概率算法 2)蒙特卡罗算法 3)拉斯维加斯算法 4)舍伍德算法4、在概率算法中使用的随机数都是一定程度上随机的，即伪随机数；一般随机数通过线性同余法方法产生。第八章 NP完全性理论1、什么是易解问题？什么是难解问题？难解问题分为哪两类？答：1）易解问题

24、：人们将存在多项式时间 算法的问题称为易解问题;2）难解问题：将需要在指数时间内解决的问题称为难解问题；3）难解问题有两类： 1）不可判定问题 2）非决定的难处理问题 。2、什么是不可判定问题？什么是非决定的难处理问题？答：1）不可判定问题 ：该类问题是不能解问题，它们太难了，以至于根本就不存在能求解它们的任何算法。2）非决定的难处理问题： 这类问题是可判定的（即可解的）。 但是，这类问题即使使用非决定的计算机，也不能在多项式时间内求解它们。3、什么是P类问题？什么是NP完全问题？答：1）P类问题：是一类能够用确定性算法在多项式时间内求解的判断问题。事实上，所有易解问题都属于P类问题。2）NP

25、完全问题：对于某问题，很难找到其多项式时间的算法(或许根本不存在)，但是如果给了该问题的一个答案，则可以在多项式时间内判定或验证这个答案是否正确。 这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。4、列出几个典型的NP完全问题？答：（1）图着色问题COLORING（2）路径问题LONG-PATH （3）顶点覆盖问题VERTEX-COVER（4）子集和问题SUBSET-SUM（5）哈密尔顿回路问题HAM-CYCLE（6）旅行商问题TSP（7）装箱问题BIN-PACKING ， 能否用k个箱子来装n个物品；第九章近似算法1、 所有NP完全问题都还没有多项式时间的算法，然而许多NP完全问

26、题都具有很重要的意义，对于这类问题通常可以采取以下几种解题策略？答：）只对问题的特殊实例求解； ）用动态规划或分支限界法求解。 ）启发式方法求解 ）只求近似解2、 利用近似算法求解NP完全问题时，近似算法应该满足下面两个基本的要求？答：1）算法的时间复杂性：要求算法能在n的多项式时间内完成。2）解的近似程度：算法的近似解应满足一定的精度。通常，用来衡量精度的标准有近似比和相对误差。1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优

27、解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 6下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题

28、 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 11下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质

29、C、贪心选择性质 D、定义最优解 14广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15背包问题的贪心算法所需的计算时间为（ B ）。 A、O（n2） nB、O（nlogn） C、O（2） nD、O（n） 16实现最大子段和利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 17实现棋盘覆盖算法利用的算法是（ A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 18.下面是贪心算法的基本要素的是（ C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 19.回溯法的效率不依赖于下列哪些因素

30、（ D ） A.满足显约束的值的个数 C. 计算限界函数的时间 B. 计算约束函数的时间 D. 确定解空间的时间 20.下面哪种函数是回溯法中为避免无效搜索采取的策略（ B ） A递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 21、以深度优先方式系统搜索问题解的算法称为 ( D ) 。 A、分支界限算法 B、概率算法 C、贪心算法 D、回溯算法 22、贪心算法与动态规划算法的主要区别是（ B ）。 A、最优子结构 B、贪心选择性质 C、构造最优解 D、定义最优解 23. 采用最大效益优先搜索方式的算法是（ A ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 24. （ D

31、 ）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 25. 矩阵连乘问题的算法可由（ B）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 26. 0-1背包问题的回溯算法所需的计算时间为（ 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 原问题

32、和子问题使用相同的方法解 30、下面问题（B ）不能使用贪心法解决。 nnA 单源最短路径问题 B N皇后问题 C 最小花费生成树问题 D 背包问题 31、下列算法中不能解决0/1背包问题的是（A ） A 贪心法 B 动态规划 C 回溯法 D 分支限界法 32、回溯法搜索状态空间树是按照（C ）的顺序。 A 中序遍历 B 广度优先遍历 C 深度优先遍历 D 层次优先遍历 33、采用广度优先策略搜索的算法是（ A ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 34实现合并排序利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 35下列是动态规划算法基本要素的是（ D ）。 A、定义最优解 B、构造最优解 C、算出最优解 D、子问题重叠性质 36下列算法中通常以自底向下的方式求解最优解的是（ B ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 二、 填空题 1.算法的复杂性有 时间 复杂性和 空间 复杂性