2015算法复习提纲(改).doc

2015年第一学期《算法设计与分析》复习提纲 题型： 一、选择（2*8=16分） 二、填空（2*10=20分） 三、程序设计与分析题（2*9=18分） 四、简答（4小题，共17分） 五、综合题（4小题，共29分） 范围: 第一章 算法设计的步骤 理解问题，精确解或近似解选择数据结构算法设计策略，设计算法，证明正确性，分析算法，设计程序。 算法时间复杂度的分类 掌握O O(1) O(logn) O(n) O(n*logn)O(n2)O(n3)… O(2n)O(3n)…O(n!) 。 3．算法的性质 输入，输出，确定性，有限性，可行性。 第二章 递归与分治的基本思想 递归：直接或间接的调用自己的算法； 分治：将一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同。递归的解这些子问题，然后将各个子问题的解合并为更大规模的解自底向上逐步求出原问题的解。 分治法解题的基本步骤及特征 基本步骤：解决小规模的问题，分解问题，递归的解各子问题，将子问题得解合并为原问题的解 特征：问题规模缩小到一定的程度就可以容易的解决； 问题可分解为若干个规模较小的相同的子问题，即有最优子结构； 问题分解出的子问题的解可以合并为原问题的解； 问题分解出的各个子问题是相互独立的。 二分有哪些信誉好的足球投注网站、快速排序、大整数乘法 第三章 贪心法的定义 指的是从对问题的某一初始解出发,一步一步的攀登给定的目标,尽可能快地去逼近更好的解。当达到某一步,不能再攀登时,算法便终止 （2）有哪些信誉好的足球投注网站方式的不同：回溯法以深度优先的方式有哪些信誉好的足球投注网站解空间树，而分支限界法则以广度优先或以最小耗费优先的方式有哪些信誉好的足球投注网站解空间树。 常见的两种分支限界法（以0-1背包问题为例） 队列式(FIFO)分支限界法 按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。