算法设计与分析复习要点.doc

算法设计与分析复习要点一、单项选择题（本大题共15小题，每小题2分，共30分）二、填空题（本大题共15空，每空1分，共15分）三、分析题（本大题共5小题，每小题5分，共25分）四、综合题（本大题共4小题，1、2题每题6分，3题8分，4题10分，共30分）第2章，导引与基本数据结构：1、什么是算法, 算法的5个特性；对一个算法作出全面分析的两个阶段。P245个特性：确定性、能行性、输入、输出、有穷性两个阶段：事前分析、事后测试2、 O(g(n)，(g(n)，Q(g(n)的含义。3、多项式时间算法：可用多项式（函数）对其计算时间限界的算法。4、常见的多项式限界函数所表示算法时间复杂度的排序： (1) <(logn) < (n) < (nlogn) < (n2) < (n3)5、指数时间算法：计算时间用指数函数限界的算法6、常见的指数时间限界函数： (2n) < (n！) < (nn)7、什么是算法的复杂性：是该算法所需要的计算机资源的多少，它包括时间和空间资源。8、复习栈和队列、树、图的基本知识，了解二元树、完全二元树，满二元树、二分检索树、了解图的邻接矩阵和邻接表存储方法。9、能写出图的深度优先序列和广度优先序列。10、会求如下一些简单的函数的上界表达式：3n2+10n =O(n2)第3、4章 递归与分治算法1、理解递归算法的优缺点，深刻理解递归算法的执行过程。如能写出解决n阶汉诺塔问题的解，并能分析写出3阶汉诺塔问题的递归执行轨迹。2、递归算法的优点：结构清晰，可读性强，容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。3、递归算法的缺点：运行效率较低，耗费的计算时间和占用的存储空间都多。为了达到此目的，根据具体程序的特点对递归调用工作栈进行简化，尽量减少栈操作，压缩栈存储空间以达到节省计算时间和存储空间的目的。4、能求解或证明常见递归关系式，如n阶汉诺塔问题的算法时间复杂度。5、分治法的基本思想：是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。6、掌握二分检索算法，如给一个实例，可以模拟出low，hig，mid的运行轨迹。（74页）知道并能证明二分检索算法平均时间复杂度是Q( logn)7、掌握找最大和最小元素的递归分治算法。(79页)8、理解并掌握归并分类（归并排序）算法，能画出用二元树表示的归并分类调用过程及合并过程。理解并能证明归并分类算法的时间复杂度。9、合并排序的时间复杂度是：T(n)=O(nlogn)。利用该递归式求取合并排序算法时间复杂度的上界。10、理解并掌握快速分类（快速排序）算法，给定一个未排序数组，能分步写出快速分类中划分的执行过程。理解快速分类算法的时间复杂度。（87页）快速排序的时间复杂度是：T(n)=O(nlogn)本章作业：1、写出用分治法求解循环赛日程表的完整程序。程序语言任意，但必须能上机运行。2、p99-4.22、P99-4.3根据4.2节开始所给出的二分检索策略，写一个二分检索的递归过程。3、P99-4.5作一个“三分”检索算法，它首先检查n/3处的元素是否等于某个x的值，然后检查2n/3处的元素。这样，或者找到x，或者把集合缩小到原来的1/3。分析此算法在各种情况下的计算复杂度。第5章 贪心方法1、贪心方法:是根据具体的问题, 选取一种量度标准,按此标准对n个输入进行排序, 然后按该顺序一次输入一个量. 如果这个输入量和当前的部分最优解加在一起不能产生一个可行解, 则不把此输入量加入到这个部分解中, 这种能够得到某种量度意义下的最优解的分级处理方法就是贪心方法。2、贪心选择性质：指所求问题的整体最优解可以通过一系列局部最优的选择。3、贪心算法的基本要素：贪心选择性质和最优子结构性质。4、掌握背包问题的贪心解法，分别以重量、效益值，单位重量效益值为最优量度所得最优解的比较。5、三元归并模式的贪心解法和证明，能画出3元归并树（111）6、单源点最短路径的贪心解法，算法执行运行踪迹。(118)如：给出一个带权图，能将下表的运行踪迹图补充完整迭代S选取的结点udist2dist3dist4dist5置初值1-10maxint30100123作业：P121： 5.2、5.12第6章 动态规划1、将问题分解成多级或许多子问题，然后顺序求解子问题，前一个子问题的解为后一个子问题的求解提供有用的信息。最优子结构性质：该问题的最优解包含着其子问题的最优解。2、动态规划算法的基本要素：最优子结构性质和子问题重叠性质。3、理解并掌握多段图的动态规划求解过程，包括递推步骤。如，下面是一个多段图问题，为了求出源点s到终点t的最短距离，假设用cost(i)表示节点i到终点t的距离(节点i是指下图中圆圈中的数字为i的结点)。试根据cost(i)的含义用动态规划的方法求出该多段图问题的解。（要求根据cost(i)的含义，用递推的方法写出求解步骤，得到结果）4、理解并掌握0/1背包问题的动态规划求解过程，会采用序偶直接解n值不大的0/1背包问题。第8章 回溯法1、回溯法：是一个既带有系统性又带有跳跃性的搜索算法。这在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。2、理解回溯法的基本思想，掌握状态空间树的画法及各种含义。掌握n皇后问题的算法及执行踪迹。3、能画出0/背包问题的状态空间树及子集树。4、回溯法效率的因素：（1）产生xk的时间。（2）满足显约束的xk值的个数。（3）计算约束函数constraint的时间。（4）计算上界函数bound的时间。（5）满足约束函数和上界函数约束的所有xk的个数第9章 分支限界法（了解）1、分支限界法的基本思想：(1)分支限界法常以广度优先或以最小耗费(最大效益)优先的方式 搜索问题的解空间树。(2)在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。(3)此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程，这个过程一直持续到找到所需的解或活结点表这空时为止。2、最常见的分支限界法有两种：队列式（FIFO）分支限界法和优先队列式分支限界法。3、上课反复讲、反复强调的几个问题，要求懂原理，会设计（关键是思路，表达方法可以是语言、伪代码、代码），会进行复杂度分析。建议：答题时不要把所有的东西写一大段，适当分步骤、分要点，如XXX算法原理做什么，怎么做做什么，怎么做等