算法设计与分析复习要点(DOC 9页).doc

1、算法设计与分析复习要点一、单项选择题（本大题共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

2、) (logn) (n) (nlogn) (n2) (n3)5、指数时间算法：计算时间用指数函数限界的算法6、常见的指数时间限界函数： (2n) (n！) (nn)7、什么是算法的复杂性：是该算法所需要的计算机资源的多少，它包括时间和空间资源。8、复习栈和队列、树、图的基本知识，了解二元树、完全二元树，满二元树、二分检索树、了解图的邻接矩阵和邻接表存储方法。9、能写出图的深度优先序列和广度优先序列。10、会求如下一些简单的函数的上界表达式：3n2+10n =O(n2)第3、4章 递归与分治算法1、理解递归算法的优缺点，深刻理解递归算法的执行过程。如能写出解决n阶汉诺塔问题的解，并能分析写出3阶

3、汉诺塔问题的递归执行轨迹。2、递归算法的优点：结构清晰，可读性强，容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。3、递归算法的缺点：运行效率较低，耗费的计算时间和占用的存储空间都多。为了达到此目的，根据具体程序的特点对递归调用工作栈进行简化，尽量减少栈操作，压缩栈存储空间以达到节省计算时间和存储空间的目的。4、能求解或证明常见递归关系式，如n阶汉诺塔问题的算法时间复杂度。5、分治法的基本思想：是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。6、掌握二分检索算法，如给一个实

4、例，可以模拟出low，hig，mid的运行轨迹。（74页）知道并能证明二分检索算法平均时间复杂度是Q( logn)7、掌握找最大和最小元素的递归分治算法。(79页)8、理解并掌握归并分类（归并排序）算法，能画出用二元树表示的归并分类调用过程及合并过程。理解并能证明归并分类算法的时间复杂度。9、合并排序的时间复杂度是：T(n)=O(nlogn)。利用该递归式求取合并排序算法时间复杂度的上界。10、理解并掌握快速分类（快速排序）算法，给定一个未排序数组，能分步写出快速分类中划分的执行过程。理解快速分类算法的时间复杂度。（87页）快速排序的时间复杂度是：T(n)=O(nlogn)本章作业：1、写出用

5、分治法求解循环赛日程表的完整程序。程序语言任意，但必须能上机运行。2、p99-4.22、P99-4.3根据4.2节开始所给出的二分检索策略，写一个二分检索的递归过程。3、P99-4.5作一个“三分”检索算法，它首先检查n/3处的元素是否等于某个x的值，然后检查2n/3处的元素。这样，或者找到x，或者把集合缩小到原来的1/3。分析此算法在各种情况下的计算复杂度。第5章 贪心方法1、贪心方法:是根据具体的问题, 选取一种量度标准,按此标准对n个输入进行排序, 然后按该顺序一次输入一个量. 如果这个输入量和当前的部分最优解加在一起不能产生一个可行解, 则不把此输入量加入到这个部分解中, 这种能够得到

6、某种量度意义下的最优解的分级处理方法就是贪心方法。2、贪心选择性质：指所求问题的整体最优解可以通过一系列局部最优的选择。3、贪心算法的基本要素：贪心选择性质和最优子结构性质。4、掌握背包问题的贪心解法，分别以重量、效益值，单位重量效益值为最优量度所得最优解的比较。5、三元归并模式的贪心解法和证明，能画出3元归并树（111）6、单源点最短路径的贪心解法，算法执行运行踪迹。(118)如：给出一个带权图，能将下表的运行踪迹图补充完整迭代S选取的结点udist2dist3dist4dist5置初值1-10maxint30100123作业：P121： 5.2、5.12第6章 动态规划1、将问题分解成多级

7、或许多子问题，然后顺序求解子问题，前一个子问题的解为后一个子问题的求解提供有用的信息。最优子结构性质：该问题的最优解包含着其子问题的最优解。2、动态规划算法的基本要素：最优子结构性质和子问题重叠性质。3、理解并掌握多段图的动态规划求解过程，包括递推步骤。如，下面是一个多段图问题，为了求出源点s到终点t的最短距离，假设用cost(i)表示节点i到终点t的距离(节点i是指下图中圆圈中的数字为i的结点)。试根据cost(i)的含义用动态规划的方法求出该多段图问题的解。（要求根据cost(i)的含义，用递推的方法写出求解步骤，得到结果）4、理解并掌握0/1背包问题的动态规划求解过程，会采用序偶直接解n

8、值不大的0/1背包问题。第8章 回溯法1、回溯法：是一个既带有系统性又带有跳跃性的搜索算法。这在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。2、理解回溯法的基本思想，掌握状态空间树的画法及各种含义。掌握n皇后问题的算法及执行踪迹。3、能画出0/背包问题的状态空间树及子集树。4、回溯法效率的因素：（1）产生xk的时间。（2）满足显约束的xk值的个数。（3）计算约束函数constraint的时间。（4）计算上

9、界函数bound的时间。（5）满足约束函数和上界函数约束的所有xk的个数第9章 分支限界法（了解）1、分支限界法的基本思想：(1)分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。(2)在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。(3)此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程，这个过程一直持续到找到所需的解或活结点表这空时为止。2、最常见的分支限界法有两种：队列式（FIFO）分支限界法和优先队列式分支限界法。3、上课反复讲、反复强调的几个问题，要求懂原理，会设计（关键是思路，表达方法可以是语言、伪代码、代码），会进行复杂度分析。建议：答题时不要把所有的东西写一大段，适当分步骤、分要点，如XXX算法原理做什么，怎么做做什么，怎么做等