算法分析与设计习题集整理
第一章算法引论
一、填空题：
1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。
2、多项式A(n)?amnm???a1n?a0的上界为O(n)。
m
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；i { y=y+1; for（j＝0；j <=2n；j++ ） x＋＋； } 9、计算机求解问题的步骤：问题分析、数学模型建立、算法设计与选择、算法表示、算法分析、算法实现、程序调试、结果整理文档编制。 10、算法是指解决问题的 方法或过程 。 11、算法由操作、控制结构、数据结构三要素组成。 二、简答题： 2n2/3 1、按照时间复杂度从低到高排列：O( 4n)、O( logn)、O( 3)、O( 20n)、O( 2)、O( n), O( n!)应该排在哪一位？ 2/32n 答：O( 2)，O( logn)，O( n)，O( 20n)，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) {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 3）该算法的主要元操作是语句5，其执行次数是n次。 故该算法的时间复杂度记 3 为O(n). 4、算法A和算法B解同一问题，设算法A的时间复杂性满足递归方程 ?T(n)?1 , n?1 ，算法?T(n)?4T(n/2)?n , n?1?B的时间复杂性满足递归方程 ?T(n)?1 , n?1 ，若要使得算法A时间复杂性的阶高于算法B时间复杂性的阶，?T(n)?aT(n/4)?n , n?1?a的最大整数值可取多少？ 答：分别记算法A和算法B的时间复杂性为TA(n)和TB(n)，解相应的递归方程得： TA(n)?O(n2) ?O(n) , a?4? TB(n)??O(nlogn) , a?4 ?log4a) , a?4?O(n依题意，要求最大的整数a使得TB(n)〈TA(n)。显然，当a<=4时，TB(n)〈TA(n)； 当a>4时，TB(n)〈TA(n) ?log4a?2 ?a<4=16。 所以，所求的a的最大整数值为15。 5、算法分析的目的？ 答：1)为了对算法的某些特定输入，估算该算法所需的内存空间和运行时间； 2)是为了建立衡量算法优劣的标准，用以比较同一类问题的不同算法。 6、算法设计常用的技术？（写５种） 答： ①分治法; ②回溯法； ③贪心法； ④动态规划法 ⑤分治限界法 ； ⑥蛮力法； ⑦倒推法 三、算法设计题 1、蛮力法：百鸡百钱问题？ 2 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阶； 1 n=1 F(n) ＝ 2 n=2 F(n-1) + F(n-2) n>2 ②写出其相应的递归算法？ Int F(int n) { if(n=1) return 1; else if(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中任一塔座上。 ①写出该问题的解题步骤？ ②并写出其相应的递归算法？ 解： ①第一步：将n－1个盘子看成一个整体，从A移到C； 第二步：将第n个盘子移到B; 第三步：将n－1个盘子看成一个整体，从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)该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质； 3）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 4）利用该问题分解出子问题解可以合并为该问题解; 2、分治算法基本思想，解题步骤？ 三、算法设计题： 1、改写二分查找算法： 设a[1?n]是一个已经排好序的数组，改写二分查找算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i，和大于x的最小元素位置j；当搜索元素x在数组中时，i和j相同，均为x在数组中的位置。 并分析其时间复杂度？ 解：int binsearch( int a[n], int x ,) //x待查数据 {int mid, i , j; low=1; int high=n; while(low<=high) {mid=(low+high)/2; if(a[mid]=x) return i=j=mid; if(a[mid]>x) high=mid-1; //继续在左边查找 else // (a[mid] i=right; j=left; return 0；//low大于high查找区间为空，查找失败 } 计算时间复杂性为O(logn) kk 2、棋盘覆盖在一个2×2 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。