数据结构
课程编码：B0911002Y 英文名称：Data Structures 课时：60 学分：3.00 课程属性：专业必修课 主讲教师：沈海华
本课程按章节包含如下主要内容：
第1章绪论，数据结构的基本概念，算法的基本特征，算法分析的基本概念。
第2章线性表，线性表的定义、基本操作、线性表的若干应用。要求掌握线性表的存储结构(包括顺序存储结构、链式存储结构)及操作实现。
第3章栈和队列，栈与队列的基本概念、基本操作以及栈与队列的若干应用。要求掌握栈与队列的存储结构(包括顺序存储结构、链式存储结构)及操作实现。
第4章串，串的基本概念和基本操作。要求掌握串的存储结构及操作实现。要求掌握串的模式匹配算法。
第5章数组和广义表，数组、广义表的基本概念和基本操作。要求掌握多维数组的实现。理解特殊矩阵(包括对称矩阵、稀疏矩阵)的压缩存储。了解广义表的存储结构和遍历。
第6章树和二叉树，树、二叉树、森林的基本概念和性质。树、二叉树、森林的存储结构、遍历。线索二叉树的基本概念和构造。二叉树和森林/树的相互转换。Huffman树和Huffman编码。并查集(Union-Find Set)。
第7章图，图的存储。图的遍历(DFS/BFS)。拓扑排序。图的连通分支。最小生成树。最短路径。关键路径。
第8章动态存储管理，边界标识法，伙伴系统。
第9章查找，查找的基本概念。顺序查找，分块查找，折半查找，Fibonacci查找，次优查找树查找。二叉排序树/二叉检索树，平衡二叉树，B树(含2-3树)。键树/数字查找树，散列表。各种查找算法的分析、比较及应用。
第10章内部排序，插入排序(直接插入排序，折半插入排序，Shell排序)、快速排序、选择排序(简单选择排序，树形选择排序，堆排序)、归并排序、基数排序。各种排序算法的分析、比较及应用。
第11章外部排序，K-路平衡归并，置换-选择排序，最佳归并树。
学时分配：
规定出本课程的各种教学环节（习题课、实验、上机、讨论等）恰当学时。
| 章节/学时分配 | 讲课 | 习题课 | 实验课 | 上机课 | 讨论课 | 其它 |
| 1 | 2 | |||||
| 2 | 4 | |||||
| 3 | 4 | |||||
| 4 | 4 | 2 | ||||
| 5 | 4 | |||||
| 6 | 6 |
|
|
|
|
|
| 7 | 9 |
|
|
|
| 期中考试 |
| 8 | 1 | 2 |
|
|
|
|
| 9 | 8 |
|
|
|
|
|
| 10 | 4 |
|
|
|
|
|
| 11 | 2 | 2 |
|
|
|
|