作者：edelweiss 日期：2020年2月23日
参考书目：ISBN 978-7-5135-1724-9 数据结构
1. 概论
学习目的与要求
本章的学习目的是要求考试了解数据结构在计算机软件和计算机应用中的作用；熟悉常见的名词和术语的含义；掌握逻辑结构、存储结构的基本概念；熟悉数据结构的两大类型和四种基本的存储方法；了解算法的五个要素（准则）以及算法与程序的区别；熟悉使用类 C 语言函数对算法的描述；掌握对算法的分析和时间复杂的估算。
本章的重点是了解数据结构的逻辑结构、存储结构和数据运算三方面的概念及相互关系，难点是算符复杂度的分析方法。
考核内容与考核要求
- 数据结构的作用、意义、基本概念和术语、要求达到 “识记” 层次、
1.1 数据结构所研究的内容；在计算机学科中的作用和意义；Wirth 关于程序的定义公式。
1.2 数据、数据元素、数据对象、数据项、数据结构等概念的定义。
1.3 数据的逻辑结构、存储结构及数据运算的含义及其相互关系。
1.4 数据结构的两大类逻辑结构和四种常用的存储表示方法。
- 算法的描述和分析，要求达到领会层次。
2.1 算法、算法的时间复杂度和空间复杂度等概念。
2.2 一个完整的算法需要满足的五个准则; 算法与程序的关系。
2.3 算法的分析方法；对于一般算法能分析其时间复杂度。
1.1 引言
1.2 基本概念和常用术语
1.3 算法的描述和分析
1.3.1 算法描述
1.3.2 算法分析
小结
思考与练习
2. 线性表
2.1 线性表的定义和基本运算
2.1.1 线性表的逻辑定义
2.1.2 线性表的基本运算
2.2 线性表的顺序存储和基本运算的实现
2.2.1 线性表的顺序存储
2.2.2 顺序表上基本运算的实现
2.3 线性表的链式存储结构
2.3.1 单链表 （线性链表）
2.3.2 单链表上的基本运算
2.3.3 循环链表
2.3.4 双向链表
2.4 顺序表和链表的比较
小结
思考与练习
3. 栈和队列
3.1 栈
3.1.1 栈的定义及其运算
3.1.2 栈的存储表示和实现
3.2 栈的应用举例
3.2.1 圆括号匹配的检查
3.2.2 字符串回文的判断
3.2.3 数制转换
3.2.4 栈与递归
3.3 队列
3.3.1 队列的定义及其运算
3.3.2 顺序循环队列
3.3.3 链队列
3.4 栈和队列的应用实例
3.4.1 中缀表达式到后缀表达式的转换
3.4.2 后缀表达式的计算
小结
思考与练习
4.多维数组和广义表
4.1 多维数组和运算
4.1.1 数组的顺序存储
4.1.2 数组的运算举例
4.2 矩阵的压缩存储
4.2.1 特殊矩阵
4.2.2 稀疏举止
4.3 广义表基础
4.3.1 广义表的定义
4.3.2 广义表的基本运算
4.3.3 广义表的存储结构
4.3.4 广义表基本运算的实现
小结
思考与练习
5. 树和二叉树
5.1 树的基本概念和术语
5.2 二叉树
5.2.1 二叉树的定义和性质
5.2.2 二叉树的存储结构
5.3 二叉树的运算
5.3.1 二叉树的生成
5.3.2 二叉树的遍历
5.3.3 二叉树的应用举例
5.4 搜索二叉树
5.4.1 二叉树的线索化
5.4.2 二叉线索链表上的运算
5.5 数和森林
5.5.1 树的存储结构
5.5.2 树、森林与二叉树的转换
5.5.3 树和森林的遍历
5.6 哈夫曼树及其应用
5.6.1 最优二叉树(哈夫曼树）
5.6.2 哈夫曼编码
小结
思考与练习
6. 图
6.1 图的定义和基本术语
6.2 图的存储结构
6.2.1 邻接矩阵表示法
6.2.2 临接表表示法
6.3 图的遍历
6.3.1 深度优先搜索遍历
6.3.2 广度优先搜索遍历
6.4 图的生成树和最小生成树
6.4.1 图的生成树
6.4.2 最小生成树
6.5 最短路径
6.6 拓扑排序
小结
思考与练习
