考试科目: 数据结构与程序设计 适用专业:系统分析与集成
一.复习要求:
掌握线性表、栈、队列、串、数组、广义表、树、图、文件等常用的数据结构，掌握常用数据结构的排序、查找运算及算法复杂度，能应用合适的数据结构及设计有效的算法。
二.主要复习内容
1. 数据结构的概念
数据类型和数据结构，基本数据结构，算法描述及算法分析。
2. 线性表
线性表逻辑结构与存储结构, 表的实现（数组, 单链表）, 其它表结构（循环链表, 双向链表），矩阵的表示（矩阵, 特殊矩阵, 稀疏矩阵），表的动态存储。
重点：链表的表示和操作。
3. 栈和队列
栈 （栈的定义及基本操作）, 栈的实现（ 数组, 链表）, 队列（队列的定义及基本操作），队列的实现（数组, 链表）, 栈队应用（表达式求值, 递归模拟, 广义表）。
重点： 栈和队列操作、应用。
4. 串
抽象数据类型串, 串的实现（数组, 链表），串的模式匹配。
重点： 串实现、应用。
5. 树
树的基本概念, 二叉树, 二叉树实现（链接, 数组），二叉树的遍历，线索树, 树和森林（森林的二叉树表示, 树和森林的遍历, 树和森林的数组表示（先根次序表示, 后根次序表示, 中根层次次序表示）），树的应用（抽象数据类型UFSET的实现, 哈夫曼算法和哈夫曼编码, 优先队列的实现）。
重点：树的存储结构、遍历和线性表示；二叉树、线索树、哈夫曼树算法。
6. 图
图的概念, 图的存储表示（邻接矩阵, 邻接表, 邻接多重表）, 图的遍历（深度优先搜索, 广度优先搜索），最小生或树 （Prim算法, Kruskal算法），最短路径, 拓扑排序, 关键路径。
重点：图存储结构，图的表示、遍历及图的应用算法。
7. 排序
插入排序（数组直接插入排序,链表直接插入排序）, 二分法排序, 希尔排序，选择排序（选择排序, 堆排序），交换排序（冒泡排序, 快速排序），基数排序, 归并排序。
重点：各种排序及其算法。
8. 查找
表的查找（顺序查找, 二分法查找, 分块查找, 散列（散列函数, 解决冲突）），树目录的查找（二叉查找树, 平衡二叉树, Tries），外查找（B树, B+树）。
重点：各种查找算法、散列。
9. 外排序
外存储器（磁带, 磁盘）, 初始归并段的生成, 磁带归并模式, 磁盘归并技术。
三.参考书目
1严蔚敏、吴伟民编《数据结构》，清华大学出版社，1997。
2施振夏 等译《程序设计》，上海交通大学出版社，1999。
一.复习要求:
掌握线性表、栈、队列、串、数组、广义表、树、图、文件等常用的数据结构，掌握常用数据结构的排序、查找运算及算法复杂度，能应用合适的数据结构及设计有效的算法。
二.主要复习内容
1. 数据结构的概念
数据类型和数据结构，基本数据结构，算法描述及算法分析。
2. 线性表
线性表逻辑结构与存储结构, 表的实现（数组, 单链表）, 其它表结构（循环链表, 双向链表），矩阵的表示（矩阵, 特殊矩阵, 稀疏矩阵），表的动态存储。
重点：链表的表示和操作。
3. 栈和队列
栈 （栈的定义及基本操作）, 栈的实现（ 数组, 链表）, 队列（队列的定义及基本操作），队列的实现（数组, 链表）, 栈队应用（表达式求值, 递归模拟, 广义表）。
重点： 栈和队列操作、应用。
4. 串
抽象数据类型串, 串的实现（数组, 链表），串的模式匹配。
重点： 串实现、应用。
5. 树
树的基本概念, 二叉树, 二叉树实现（链接, 数组），二叉树的遍历，线索树, 树和森林（森林的二叉树表示, 树和森林的遍历, 树和森林的数组表示（先根次序表示, 后根次序表示, 中根层次次序表示）），树的应用（抽象数据类型UFSET的实现, 哈夫曼算法和哈夫曼编码, 优先队列的实现）。
重点：树的存储结构、遍历和线性表示；二叉树、线索树、哈夫曼树算法。
6. 图
图的概念, 图的存储表示（邻接矩阵, 邻接表, 邻接多重表）, 图的遍历（深度优先搜索, 广度优先搜索），最小生或树 （Prim算法, Kruskal算法），最短路径, 拓扑排序, 关键路径。
重点：图存储结构，图的表示、遍历及图的应用算法。
7. 排序
插入排序（数组直接插入排序,链表直接插入排序）, 二分法排序, 希尔排序，选择排序（选择排序, 堆排序），交换排序（冒泡排序, 快速排序），基数排序, 归并排序。
重点：各种排序及其算法。
8. 查找
表的查找（顺序查找, 二分法查找, 分块查找, 散列（散列函数, 解决冲突）），树目录的查找（二叉查找树, 平衡二叉树, Tries），外查找（B树, B+树）。
重点：各种查找算法、散列。
9. 外排序
外存储器（磁带, 磁盘）, 初始归并段的生成, 磁带归并模式, 磁盘归并技术。
三.参考书目
1严蔚敏、吴伟民编《数据结构》，清华大学出版社，1997。
2施振夏 等译《程序设计》，上海交通大学出版社，1999。