数据结构期末复习要点
第一章绪论
1、掌握基本概念和术语:
(1)数据(2)数据元素数据对象(4)数据结构及其形式化描述(5)数据类型
2、熟悉算法的特征和要求，理解算法的时间复杂度和空间复杂度。
第二章线性表
1、掌握有关线性表顺序存储的内容：
（1）顺序表的随机存取；
（2）顺序表为空、为满的判定；
（3）顺序表的插入和删除操作（算法）；
2、掌握有关线性表链式存储的内容：
（1）单链表为空的判定（带头结点、不带头结点）；
（2）单链表的查找（算法）；
（3）单链表的插入、删除操作（算法）。
第三章栈和队列
1、顺序栈的表示，栈操作的特点以及为空、为满的判定；
2、栈的入栈和出栈操作(算法)；
3、队列的表示以及循环队列为空、为满判定。
第四章串
掌握串的特点（元素受限），串长度、空串、串的位置、串相等、空串、空格串几个概念即可。
第六章树和二叉树
1、了解有关树的概念和术语；
2、了解二叉树的链式存储结构，
3、掌握完全二叉树的基本概念；
4、重点掌握二叉树的六大性质，并会灵活运用；
5、掌握二叉树的各种遍历方法：
（1）能够根据二叉树写出各种遍历序列；
（2）能够由两种遍历序列（必须包含中序序列）恢复二叉树；
6、掌握Huffman树的相关内容：给定字符及频率构造Huffman树，设计Huffman 编码；
第七章图
1、熟悉图的定义和术语（有向图、无向图、完全图）；
2、掌握图的邻接矩阵和邻接表两种存储结构：
（1）掌握存储结构的特点（是否对阵、求边数、求结点度等）；
（2）能够画出给定图的存储结构，或者根据存储结构画出图的逻辑结构；（3）能够写出在两种存储结构上进行深度优先和广度优先遍历的序列；
3、掌握构造最小生成树的Prim算法（归并顶点）和Kruskal算法（归并边），能够按照步骤构造最小生成树；
4、对于拓扑排序算法和关键路径算法，前者要求会写拓扑排序序列，后者略看即可；
第九章查找
1、理解顺序查找的过程，掌握折半查找和索引顺序查找的过程。
2、掌握二叉排序树的定义和构造；掌握平衡二叉树（A VL）的定义。
5、掌握哈希表的构造和哈希查找的过程：
（1）哈希函数掌握“除留余数法”；
（2）冲突处理函数掌握“开放定址法”中的线性探测再散列和二次探测再散列，能够将给定的关键字填入哈希表的适当位置；H i=(Hash(key)+d i) mod m（m为哈希表的长度）
第十章内部排序
掌握排序算法的总体思路，能够模拟排序的执行过程
1、掌握直接插入排序、折半插入排序和希尔排序（根据增量序列分段插入排序）的基本思想和排序过程；
2、理解起泡排序，掌握快速排序（选取枢轴，逆序交换，递归完成）；
3、理解简单选择排序，掌握堆排序：
（1）堆的定义（小顶堆和大顶堆）和堆排序（初始建堆+重建堆）；
（2）能够用完全二叉树的形式完成初始建堆和重建堆（筛选）；
3、理解归并排序
复习要求：
根据上述要点，以PPT为主，结合课本进行复习，对每章作业习题给与足够重视。
试卷类型分布：
一、选择题
二、填空题
三、应用题
四、算法填空
五、程序设计题