教学大纲
这份大纲是本课程与 408 考试大纲的对齐说明:它先把课程要掌握的三层目标摊开,再逐章列出考查范围,从线性表一直排到排序与查找。开始学习前先通读一遍,可以据此判断每一章的轻重;如果是为了备考,就把它当成「哪些内容必考、哪些只需了解」的清单。
- 掌握数据结构的基本概念、基本原理和基本方法。
- 掌握数据的逻辑结构、存储结构及基本操作的实现,能够对算法进行基本的时间复杂度与空间复杂度的分析。
- 能够运用数据结构基本原理和方法进行问题的分析与求解,具备采用 C 或 C++语言设计与实现算法的能力。
- (一) 线性表的基本概念
- (二) 线性表的实现
- 顺序存储
- 链式存储
- (三) 线性表的应用
- (一) 栈和队列的基本概念
- (二) 栈和队列的顺序存储结构
- (三) 栈和队列的链式存储结构
- (四) 多维数组的存储
- (五) 特殊矩阵的压缩存储
- (六) 栈、队列和数组的应用
- (一) 树的基本概念
- (二) 二叉树
- 二叉树的定义及其主要特征
- 二叉树的顺序存储结构和链式存储结构
- 二叉树的遍历
- 线索二叉树的基本概念和构造
- (三) 树、森林
- 树的存储结构
- 森林与二叉树的转换
- 树和森林的遍历
- (四) 树与二叉树的应用
- 二叉搜索树
- 平衡二叉树
- 哈夫曼(Huffman)树和哈夫曼编码
- (一) 图的基本概念
- (二) 图的存储及基本操作
- 邻接矩阵法
- 邻接表法
- 邻接多重表、十字链表
- (三) 图的遍历
- 深度优先搜索
- 广度优先搜索
- (四) 图的基本应用
- 最小(代价)生成树
- 最短路径
- 拓扑排序
- 关键路径
- (一) 查找的基本概念
- (二) 顺序查找法
- (三) 分块查找法
- (四) 折半查找法
- (五) B 树及其基本操作、B+树的基本概念
- (六) 散列(Hash)表
- (七) 字符串模式匹配
- (八) 查找算法的分析及应用
- (一) 排序的基本概念
- (二) 插入排序
- 直接插入排序
- 折半插入排序
- (三) 起泡排序(bubble sort)
- (四) 简单选择排序
- (五) 希尔排序(shell sort)
- (六) 快速排序
- (七) 堆排序
- (八) 二路归并排序(mergesort)
- (九) 基数排序
- (十) 外部排序
- (十一) 各种排序算法的比较
- (十二) 排序算法的应用
