《算法设计与分析考试重点归纳》由会员分享，可在线阅读，更多相关《算法设计与分析考试重点归纳（7页珍藏版）》请在金锄头文库上搜索。
1、算法设计考试重点整理题型：一选择题（10*2=20分）二简答题（4*5二20分）三应用题（3*10=30分）四算法题（3*10=30分）第一、二章算法的定义：解某一特定问题的一组有穷规则的集合（对特定问题求解步骤的一种描述， 是指令的有限序列）算法的特征：1）有限性2）确定性3）输入4）输出5）能行性算法分析的目的：基本数据结构：线性结构（元素之间是一对一的关系）用顺序存储结构存储的线性表称为顺序表用链式存储结构存储的线性表称为链表。树形结构（元素之间是一对多的关系）图（网）状结构（元素之间是多对多的关系）栈：是一种只允许在表的一端进行插入或删除操作的线性表。允许进行插入、删除操作的一 端称为
2、栈顶，另一端称为栈底。当栈中没有数据元素时，称之为空栈。栈的插入操作称为进 压栈，删除操作称为出栈。队列：只允许在一端进行插入操作，在另一端进行删除操作的线性表。允许进行插入操作的 一端称为队尾。允许进行删除操作的一端称为队头。当队列中没有数据元素时，称之为空队 列。队列的插入操作称为进队或入队。队列的删除操作称为退队或出队。树：树型结构是一种非线性结构，它用于描述数据元素之间的层次关系图图：G=（V, E）是一个二元组其中：V是图G中数据元素（顶点）的非空有限集集合E是图G中关系的有限集合由表达式求渐进表达式：例：（n2+n）/4n2/4 （增长速率最快的那一项）时间复杂度的计算：（P23）
3、性能的比较：0（1） 0（log2n） O（n） 0（nlog2n） =0（nlogn） 0（”）0（m） O（nk） O（2n）第三章算法思想、稳定性、时间复杂度、应用、排序的移动次数：希尔排序（数据结构P265）：先将待排序列分割为若干个子序列分别进行直接插入排序；待 整个序列基本有序时，再对全体记录进行一次直接插入排序。也称缩小增量的直接插入排 序。希尔排序的时间复杂度在0（nlog2n）和0（n2）之间，大致为0 （n13）合并排序（P59）:设初始序列含有n个记录，则可看成n个表长为1的有序表将这n个有序 表两两合并，则可得n/2个表长为2的有序表再将这n/2个有序表两两合并，则可得
4、n/4 个长为4的有序表依次重复，直到对2个表长为n/2的有序表两两合并得1个表长为n的有序表为止。堆排序、堆调整(P62)：初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树(一维数组存储二叉树，调 整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n个元素中最小(或最大)的元 素，这时堆的根节点的数最小(或者最大)。然后对前面(n-1 )个元素重新调整使之成为堆, 输出堆顶元素，得到n个元素中次小(或次大)的元素。依此类推，直到只有两个节点的堆， 并对它们作交换，最后得到有n个节点的有序序列。基数排序(P71)：不进行记录关键字的比较，借助多关键字排序的思想对单逻辑关键字进行 排序。
5、算法时间复杂度稳定性希尔排序0帥.3)不稳定快速排序O(nlogn)不稳定堆排序O(nlogn)不稳定宁归(合)并排序O(nlogn)稳定基数排序O(n)稳定第四章(考一个算法题，课后，不在书上)算法思想：基于归纳的递归算法解规模为n的问题P(n),归纳法的思想如下：1. 基础步：a是问题P(1)的解12. 归纳步：对所有的k (1 k lchild)+1;h2=Height(t-rchild)+1;return h1h2?h1:h2;*2假定用面值为2角5分、1角、5分、1分的硬币，来支付n分钱。设计一个算法，使付 出的枚数最少(n由键盘输入)void solve(int p,int x,int n)int i;for(i=0;i4;i+)xi=n/pi;n=n%pi;*3对于给定的邮箱网G,求网中指定的顶点v到其余各顶点的最短路径。P147*4 n后问题(P210)5图的着色问题(P214)6哈密尔顿回路问题(P217)友情提示：本资料代表个人观点，如有帮助请下载，谢谢您的浏览！
