数据结构期末复习要点(严蔚敏版)4

数据结构期末复习要点第一章绪论1、掌握基本概念和术语，看教材P4—P6部分内容；2、看P10—P11关于类C的语法描述，算法设计写代码时可用到；3、掌握算法的特征（5个）和要求（5个）（P13—P14），能够结合具体算法分析算法的时间复杂度和空间复杂度（比如线性表的插入、删除操作，查找、排序等操作），理解O(n)、O(1)等时间复杂度的具体含义（P14—P17）。第二章线性表1、看教材P21—P26，掌握有关线性表顺序存储的内容：（1）顺序表的随机存取（P21计算地址的公式）；（2）顺序表的表示（P22的Typedef）；（3）顺序表为空、为满的判定，插入和删除操作的特征以及时间复杂度的分析（P23—P25）；（4）有关顺序表的编程题。2、看教材P27—P30，掌握有关线性表链式存储的内容：（1）单链表的表示（P28的Typedef）；（2）单链表为空的判定（带头结点、不带头结点）；（3）单链表插入、删除操作的特征（操作点的确定以和指针的修改）以及时间复杂度分析（P29—P30）；（4）有关单链表的编程。3、为节约时间，循环链表、双向链表以及多项式加法可以不看；4、算法设计题要求写代码，在本章体现的可能性比较大。第三章栈和队列1、顺序栈的表示，栈操作的特点以及为空、为满的判定（P46—P47）；2、栈的应用举例看个标题就足够了；3、链队列的表示以及入队、出队操作（P61—P62）；4、循环队列为空、为满的判定（P65的代码中）；5、离散事件模拟这节不用看；6、第四章只需要看P70就够了，掌握串的特点（元素受限），串长度、空串、串的位置、串相等几个概念即可。第六章树和二叉树1、看教材P120，了解有关树的概念和术语；2、了解二叉树的链式存储结构（P127），掌握二叉树的性质（P123—P125），并会做题（参考课件或指导书相关内容）；3、掌握二叉树的各种遍历算法（P128—P129或课件）：（1）能够根据二叉树写出各种遍历序列；（2）能够由两种遍历序列（必须包含中序序列）恢复二叉树；（3）理解二叉树遍历算法的递归代码，能够读懂代码含义。4、线索二叉树、树和森林的遍历略看即可，涉及不多；树与等价问题没讲不用看；5、掌握Huffman树的相关内容（P144—P148）：（1）给定字符及频率构造Huffman树，设计Huffman编码；（2）掌握前缀编码的概念，能判定一组编码是否前缀编码。6、回溯法和树的计数这两节不用看；7、注意：要能够分析递归程序的执行结果（不局限于二叉树的递归算法）。第七章图1、看教材P157—P159，熟悉图的定义和术语；2、看教材P161—P164，掌握图的邻接矩阵和邻接表两种存储结构：（1）掌握存储结构的特点（是否对阵、求边数、求结点度等）；（2）能够画出给定图的存储结构，或者根据存储结构画出图的逻辑结构；（3）能够写出在两种存储结构上进行深度优先和广度优先遍历的序列；（4）十字链表和邻接多重表不用看了。3、看教材P173—P176，掌握构造最小生成树的Prim算法和Kruskal算法，能够按照考研指导书P199和P201所示的步骤构造最小生成树；4、对于拓扑排序算法和关键路径算法，前者可能要求写出拓扑排序序列，后者无法以大题考查，略看即可；5、知道求最短路径的两个算法的名称和能解决的问题即可，不必太费时间。第九章查找1、理解顺序查找的过程，分析索引顺序查找的性能，不用看静态树表查找；2、看教材P218—P221，掌握折半查找算法：（1）折半查找的前提；（2）折半查找的过程；（3）折半查找的判定树；（4）折半查找的ASL。3、掌握二叉排序树算法：（1）BST的定义和构造（P227—P229）；（2）BST的查找分析（P231）；（3）平衡二叉树（AVL）的定义和BBST的判定（P233）。4、了解B-树（P238—P239）和B+树（P246）的定义，不看键树；5、掌握哈希表的构造和哈希查找的过程：（1）哈希函数掌握“除留余数法”（P255）；（2）冲突处理函数掌握“开放定址法”中的线性探测再散列和二次探测再散列（P257），能够将给定的关键字填入哈希表的适当位置；（3）分析查找过程中关键字的比较次数。第十章内部排序1、看教材P263—P264，掌握学习排序算法的总体思路：（1）算法思想（排序原则和排序过程）；（2）算法性能（时间和空间复杂度）；（3）算法稳定性（取决于算法本身）；（4）算法的特殊性（适用前提、排序结果）；（5）注意横向分析比较各种排序算法。2、掌握直接插入排序的算法思想（读懂代码、模拟流程），能够进行性能分析（P265—P266）；3、折半插入排序、2-路插入排序、表插入排序和希尔排序略看即可；4、能够模拟起泡排序的执行过程，分析起泡排序的时间性能，把握起泡排序的结果特征（P273）；5、看教材P273—P276，掌握快速排序的基本思想（选取枢轴，逆序交换，递归完成），分析快速排序的时间性能（最好、最坏），把握快速排序的适用场合（何时最佳），调整快速排序的执行环境（三者取中法）；6、理解简单选择排序和树形选择排序的基本思想，重点掌握堆排序算法（P277——P282）：（1）堆的定义（小顶堆和大顶堆）和堆排序（初始建堆+重建堆）；（2）能够用完全二叉树的形式完成初始建堆和重建堆（筛选）；（3）明确何时创建什么样的堆（降序创建小顶堆，升序创建大顶堆）；（4）分析堆排序的特点和性能。7、理解归并排序的特点和性能（稳定的、先进的）（P283—P284）；8、了解基数排序的基本思想（以“分配”和“收集”代替关键字的比较），分析基数排序的性能（P286—P287）