[算法设计.docxVIP

算法设计考试重点整理题型：一 选择题 （10*2=20 分）二 简答题 （4*5=20 分）三 应用题 （3*10=30 分）四 算法题 （3*10=30 分）第一、二章算法的定义：解某一特定问题的一组有穷规则的集合 （对特定问题求解步骤的一种描述，是指令的有限序列）算法的特征：1）有限性 2）确定性 3）输入 4）输出 5）能行性算法分析的目的：基本数据结构：线性结构(元素之间是一对一的关系)用顺序存储结构存储的线性表称为顺序表用链式存储结构存储的线性表称为链表。树形结构(元素之间是一对多的关系)图(网)状结构(元素之间是多对多的关系)栈：是一种只允许在表的一端进行插入或删除操作的线性表。允许进行插入、删除操作的一端称为栈顶，另一端称为栈底。当栈中没有数据元素时，称之为空栈。栈的插入操作称为进压栈，删除操作称为出栈。队列：只允许在一端进行插入操作，在另一端进行删除操作的线性表。允许进行插入操作的一端称为队尾。允许进行删除操作的一端称为队头。当队列中没有数据元素时，称之为空队列。队列的插入操作称为进队或入队。队列的删除操作称为退队或出队。树：树型结构是一种非线性结构，它用于描述数据元素之间的层次关系图图：G＝(V，E)是一个二元组 其中：V是图G中数据元素（顶点）的非空有限集集合 E是图G中关系的有限集合 由表达式求渐进表达式：例：(n2+n)/4 n2/4 （增长速率最快的那一项）时间复杂度的计算：（P23）性能的比较：O(1) O(log2n) O(n) O(nlog2n) =O(nlogn) O(n2) O(n3) O(nk) O(2n)第三章算法思想、稳定性、时间复杂度、应用、排序的移动次数：希尔排序（数据结构P265）：先将待排序列分割为若干个子序列分别进行直接插入排序；待整个序列基本有序时，再对全体记录进行一次直接插入排序 。也称缩小增量的直接插入排序。希尔排序的时间复杂度在O(nlog2n)和 O(n2)之间，大致为O(n1.3) 合并排序（P59）：设初始序列含有n个记录，则可看成n个表长为1的有序表将这n个有序表两两合并，则可得n/2个表长为2的有序表再将这n/2个有序表两两合并，则可得n/4个长为4的有序表依次重复，直到对2个表长为n/2的有序表两两合并得1个表长为n的有序表为止。 堆排序、堆调整（P62）：初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大)的元素。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。基数排序（P71）：不进行记录关键字的比较，借助多关键字排序的思想对单逻辑关键字进行排序。 算法 时间复杂度 稳定性希尔排序 O(n1.3) 不稳定快速排序 O(nlogn) 不稳定堆排序 O(nlogn) 不稳定宁归(合)并排序 O(nlogn) 稳定基数排序 O(n) 稳定第四章（考一个算法题，课后，不在书上）算法思想：基于归纳的递归算法解规模为 n 的问题 P(n),归纳法的思想如下：1. 基础步：a1 是问题 P(1) 的解2. 归纳步：对所有的 k (1 k n)，若ak 是问题 P(k) 的解， 则p(ak)是问题 P(k+1) 的解， 其中p(ak)是对ak 的某种运算或处理为求问题 P(n) 的解an，先求问题 P(n – 1) 的解an-1再对an-1进行p(an-1)运算或处理，得到an为求问题 P(n – 1) 的解an-1，先求问题 P(n – 2) 的解an-2再进行p(an-2)运算或处理，得到an-1如此等等，不断地进行递归求解，直到 P(1) 的解a1为止当得到 P(1) 的解之后，再回过头来，不断地把所得到的解进行 p 运算或处理，直到得到 P(n) 的解为止 分治法：对于一个规模为n的问题p(n)，可以把它分解为k个规模较小的子问题，这些子问题相互独立，且结构与原来问题的结构相同。在解这些子问题时，又对每一个问题进一步的分解，直到某个阀值n0 为止。递归地解决这些子问题，再把各个子问题的解合并起来，就得到原来问题的解。分治法设计的3个步骤：1）划分步：把输入的问题实例划分为 k 个子问题。尽量使 k 个子问题的规模大致相同。例如，k = 2，如最大最小问题取其中的一部分，而丢弃另一部分，如二叉检索问题用分治法处理的情况2）治理步：由 k 个递归调用组成3）组合步：把 k 个子问题的解组合起来 算法思想、应用：快速排序（数据结构P269）：把序列就地划分为两个子序列，使第一个子序列