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

算法分析与设计习题集整理第一章算法引论一、填空题：1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。2、多项式10()mmAnanana的上界为O(nm)。3、算法的基本特征：输入、输出、确定性、有限性、可行性。4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。5、计算下面算法的时间复杂度记为：O(n3)。for(i=1;i=n;i++)for(j=1;j=n;j++){c[i][j]=0;for(k=1;k=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];}6、描述算法常用的方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD图。7、算法设计的基本要求：正确性和可读性。8、计算下面算法的时间复杂度记为：O(n2)。for（i＝1；in;i++）{y=y+1;for（j＝0；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(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){c[i][j]=0;(3)for(k=1;k=n;k++)(4)c[i][j]=c[i][j]+a[i][k]*b[k][j];}(5)答：1）定义：指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。2）算法的复杂性：指的是算法在运行过程中所需要的资源（时间、空间）多少。所需资源越多，表明算法的复杂性越高3）该算法的主要元操作是语句5，其执行次数是n3次。故该算法的时间复杂度记为O(n3).4、算法A和算法B解同一问题，设算法A的时间复杂性满足递归方程1n,n)2/n(T4)n(T1n,1)n(T，算法B的时间复杂性满足递归方程1n,n)4/n(aT)n(T1n,1)n(T，若要使得算法A时间复杂性的阶高于算法B时间复杂性的阶，a的最大整数值可取多少？答：分别记算法A和算法B的时间复杂性为)n(TA和)n(TB，解相应的递归方程得：)n(O)n(T2A4a,)n(O4a,)nlogn(O4a,)n(O)n(TalogB4依题意，要求最大的整数a使得)n(TB〈)n(TA。显然，当a=4时，)n(TB〈)n(TA；当a4时，)n(TB〈(n)TA2alog4a24=16。所以，所求的a的最大整数值为15。5、算法分析的目的？答：1)为了对算法的某些特定输入，估算该算法所需的内存空间和运行时间；2)是为了建立衡量算法优劣的标准，用以比较同一类问题的不同算法。6、算法设计常用的技术？（写５种）答：①分治法;②回溯法；③贪心法；④动态规划法⑤分治限界法；⑥蛮力法；⑦倒推法三、算法设计题1、蛮力法：百鸡百钱问题？2、倒推法：穿越沙漠问题？第二章分治算法（1）----递归循环一、填空题：1、直接或间接地调用自身的算法称为递归算法，用函数自身给出定义的函数称为递归函数。2、递归方程和约束函数（递归终止条件）是递归函数的两个要素。二、判断题：1、所有的递归函数都能找到对应的非递归定义。（√）2、定义递归函数时可以没有初始值。（X）三、简答题：1、什么是递归算法？递归算法的特点？答：1)递归算法:是一个模块（函数、过程）除了可调用其它模块（函数、过程）外，还可以直接或间接地调用自身的算法。2)递归算法特点：①每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算；（递归终止条件）②递归中用较小自变量函数值来表达较大自变量函数值；（递归方程式）2、比较循环与递归的异同？答：1)相同：递归与循环都是解决“重复操作”的机制。2)不同：就效率而言，递归算法的实现往往要比迭代算法耗费更多的时间（调用和返回均需要额外的时间）与存贮空间（用来保存不同次调用情况下变量的当前值的栈栈空间），也限制了递归的深度。每个迭代算法原则上总可以转换成与它等价的递归算法；反之不然。递归的层次是可以控制的，而循环嵌套的层次只能是固定的，因此递归是比循环更灵活的重复操作的机制。3、递归算法解题通常有三个步骤？答：1）分析问题、寻找递归：找出大规模问题与小规模问题的关系，这样通过递归使问题的规模逐渐变小。2）设置边界、控制递归：找出停止条件，即算法可解的最小规模问题。3）设计函数、确定参数：和其它算法模块一样设计函数体中的操作及相关参数。四、算法设计题：1、楼梯上有n个台阶，上楼时可以上1步，也可以上2步，设计一递归算法求出共有多少种上楼方法F(n)。①写出F(n)的递归表达式？②并写出其相应的递归算法？解：①写出F(n)的递归表达式分析：到n阶有两种走法：1）n-1阶到n阶；2）n-2阶到n阶；1n=1F(n)＝2n=2F(n-1)+F(n-2)n2②写出其相应的递归算法？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中任一塔座上。①写出该问题的解题步骤？②并写出其相应的递归算法？解：①第一步：将n－1个盘子看成一个整体，从A移到C；第二步：将第n个盘子移到B;第三步：将n－1个盘子看成一个整体，从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)该问题的规模缩小到一定的程度就可以容易解决;2)该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；3）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。4）利用该问题分解出子问题解可以合并为该问题解;2、分治算法基本思想，解题步骤？三、算法设计题：1、改写二分查找算法：设a[1…n]是一个已经排好序的数组，改写二分查找算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i，和大于x的最小元素位置j；当搜索元素x在数组中时，i和j相同，均为x在数组中的位置。并分析其时间复杂度？解：intbinsearch(inta[n],intx,)//x待查数据{intmid,i,j;low=1;inthigh=n;while(low=high){mid=(low+high)/2;if(a[mid]=x)returni=j=mid;if(a[mid]x)high=mid-1;//继续在左边查找else//(a[mid]x)low=mid+1;//继续在右边查找}i=right;j=left;return0；//low大于high查找区间为空，查找失败}计算时间复杂性为O(logn)2、棋盘覆盖在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。求：①简述分治算法的基本思想？②设计该棋盘覆盖问题的分治算法？③计算所设计算法的时间复杂度？（要求写出递推公式）解：①分解：将一个难以直接解决的大问题，分割成一些规模较小的相同子问题，以便各个击破，分而治之。对这k个子问题分别求解：如果子问题的规模仍然不不够够小小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止求小问题解、合并：将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。②、③3、金块问题（求最大最小元问题）老板有一袋金块(共n块)，最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。求：①简述分治算法的基本思想？②设计该金块问题的分治算法？③计算所设计算法的时间复杂度？（要求写出递推公式）答：①简述分治算法的基本思想：问题可以简化为：在含n（n是2的幂（n=2））个元素的集合中寻找极大元和极小元。用分治法（二分法）可以用较少比较次数地解决上述问题：1）将数据等分为两组（两组数据可能差1），目的是分别选取其中的最大（小）值。2)递归分解直到每组元素的个数≤2,可简单地找到最大(小)值.3）回溯时将分解的两组解大者取大，小者取小，合并为当前问题的解。②、③第三章动态规划算法一、填空题：1、动态规划算法中存储子问题的解是为了避免重复求解子问题。2、（最优子结构）是问题能用动态规划算法求解的前提。3、矩阵连乘问题的算法可由（动态规划）算法设计实现。二、判断题：1、动态规划算法基本要素的是最优子结构。（√）2、最优子结构性质是指原问题的最优解包含其子问题的最优解。（√）3、动态规划算法求解问题时，分解出来的子问题相互独立。（X）三、简答题：1、动态规划算法解题步骤？答：①找出最优解的性质，并刻划其结构特征;（即原问题的最优解，包含了子问题的最优解）②递归地定义最优值;（即子问题具有重叠性，由子问题定义原问题）③以自底向上的方式计算出最优值;④根据计算最优值时得到的信息，构造最优解;2、动态规划算法基本思想？答：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题；但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次；如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。3、动态规划与分治算法异同点？4、动态规划算法的基本要素？四、算法设计与计算题：1、12,,,mXxxxL和12,,,nYyyyL的最长公共子序列为12,,,kZzzzL。问：若用[][]cij记录序列12,,,iiXxxxL和12,,,jjYyyyL公共子序列长度。求：①用动态规划法求解时,计算最优值的递归公式？②设计计算最优值的算法？以及构造最优解的算法？2、长江游艇俱乐部在长江上设置了n个游艇出租站1,2…n.游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i，j)，其中1=ij=n；求：①用动态规划法求解时,计算最优值（最少租金）的递归公式？②设计计算最优值（最少租金）的算法？③并分析其时间复杂度？解：①②计算最优值算法p