数据结构期末复习要点

数据结构期末复习要点

第一章 绪论

1、掌握基本概念和术语:

(1)数据 (2)数据元素(3)数据对象 (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、掌握二叉排序树的定义和构造；掌握平衡二叉树（AVL）的定义。

5、掌握哈希表的构造和哈希查找的过程：

（1）哈希函数掌握“除留余数法”；

（2）冲突处理函数掌握“开放定址法”中的线性探测再散列和二次探测再散列，能够将给定的关键字填入哈希表的适当位置；Hi=(Hash(key)+di) mod m（m为哈希表的长度）

第十章 内部排序

掌握排序算法的总体思路，能够模拟排序的执行过程

1、掌握直接插入排序、折半插入排序和希尔排序（根据增量序列分段插入排序）的基本思想和排序过程；

2、理解起泡排序，掌握快速排序（选取枢轴，逆序交换，递归完成）；

3、理解简单选择排序，掌握堆排序：

（1）堆的定义（小顶堆和大顶堆）和堆排序（初始建堆+重建堆）；

（2）能够用完全二叉树的形式完成初始建堆和重建堆（筛选）；

3、理解归并排序

复习要求：

根据上述要点，以PPT为主，结合课本进行复习，对每章作业习题给与足够重视。

一、 选择题

二、 填空题

三、 应用题

四、 算法填空

五、 程序设计题

试卷类型分布：