数据结构与算法

一、绪论

1.1 数据结构的概念；1.2 抽象数据类型；1.3 算法与算法分析

二、栈、队列和线性表及其应用

2.1 栈的ADT定义，栈的连续实现和链表实现，栈的应用举例；2.2 队列的ADT定义，队列的连续实现和链表实现，队列应用举例；2.3 线性表的ADT定义，线性表的连续实现和链表实现，连续实现与链表实现特点之比较

三、递归

3.1递归原理与递归算法的设计；3.2 递归的机器实现，递归与栈的关系；3.3 递归树的概念，递归算法的时间和空间复杂度估算；3.4 递归与非递归的比较

四、串、数组和广义表

4.1 串的ADT定义，串的存储结构；4.2串的匹配算法；4.3串的应用举例；4.4 数组的存储；4.5 特殊矩阵的存储，稀疏矩阵的压缩存储；4.6 广义表的概念

五、二叉树

5.1 二叉树的概念及性质；5.2 二叉树的抽象数据类型；5.3 遍历二叉树；5.4 二叉树的实现；5.5 线索二叉树的概念，线索二叉树的实现和遍历；5.6 二叉树的应用

六、树与森林

6.1树的概念，树的递归定义；6.2 森林与二叉树的等价转换；6.3 树的遍历，包括先根序遍历和中根序遍历；6.4 树的存储，包括树的双亲表示法，孩子表示法和孩子兄弟表示法

七、图

7.1 图的基本概念和术语，包括结点的度数，邻接点，路径，连通等；7.2 图的存储结构，包括邻接矩阵法，邻接表，邻接多重表和十字链表等；7.3 图的遍历，包括深度优先和广度优先方法的实现；7.4 拓扑排序的概念及其实现方法；7.5关键路径与AOE网（边表示活动的有向网）；7.6 最短路径问题，使用贪婪法求解的Dijkstra算法，算法的时间复杂度分析；7.7 最小生成树，Prim算法的实现

八、内排序

8.1 排序问题的基本概念，稳定排序的概念；8.2 简单插入排序及其复杂度分析，Shell排序；8.3 简单选择排序，堆排序，复杂度分析；8.4 快速排序，归并排序，基数排序及其复杂度；8.5 各种排序方法特点（如稳定性，复杂度等）和比较

九、查找

9.1 查找的基本概念；9.2 顺序查找，有序表的二分查找（折半查找），查找效率的估算，平均查找长度的概念；9.3 二叉查找树的概念，二叉查找树的查找、插入和删除的实现；9.4平衡二叉树的概念，平衡二叉树的插入和删除方法；9.5 散列方法：散列的概念，常用构造散列函数方法，解决冲突的开地址法和拉链法，查找的分析；9.6 Trie结构的概念，Trie的查找、插入和删除；9.7 B-树的概念，B-树的查找、插入和删除；9.8 B+树的概念

十、文件与外排序

10.1文件概念；10.2 外排序概念和多路归并法