【数据结构】期末考试复习重点

考试题型：

选择题（15个30分）、填空题（8空16分）、综合题（6个54分）

第1章绪论：

1. 存储结构和逻辑结构的理解
2. 算法的定义与评价
3. 时间复杂度的计算

第2章线性表：

1. 顺序表的基本操作（包括初始化、插入、删除、取值等）
2. 单链表的基本操作（包括插入、删除、判空、取元素等）
3. 循环链表的基本操作（包括插入、删除、判空条件等）

第3章栈和队列：

1. 栈和队列的运算规则
2. 栈的基本操作（包括进栈、出栈、取栈顶元素等）
3. 队列的基本操作（包括入队、出队、队空/队满的判定、队中元素个数等）

第4章串、数组和广义表：

1. 计算数组中元素地址
2. BF模式匹配算法
3. 广义表计算表头、表尾、长度、深度

第5章树和二叉树：

1. 二叉树的性质
2. 二叉树的存储结构
3. 二叉树的三种遍历
4. 线索化二叉树
5. 哈夫曼树（包括构造过程、哈夫曼编码、计算WPL）

第6章图：

1. 图的存储结构（邻接矩阵、邻接表）
2. 图的两种遍历
3. 最小生成树
4. 最短路径

第7章查找：

1. 折半查找的思想及过程
2. 散列表的构造、元素的查找、线性探测/二次探测解决冲突、计算ASL

第8章排序：

1. 直接插入排序的思想及过程
2. 快速排序的思想及过程
3. 简单选择排序的思想及过程

视频附录