教学大纲

考查目标

1. 掌握数据结构的基本概念、基本原理和基本方法。
2. 掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。
3. 能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用 C 或 C++语言设计与实现算法的能力。

1. 线性表

• (一) 线性表的基本概念
• (二) 线性表的实现
  1. 顺序存储
  2. 链式存储
• (三) 线性表的应用

2. 栈、队列和数组

• (一) 栈和队列的基本概念
• (二) 栈和队列的顺序存储结构
• (三) 栈和队列的链式存储结构
• (四) 多维数组的存储
• (五) 特殊矩阵的压缩存储
• (六) 栈、队列和数组的应用

3. 树与二叉树

• (一) 树的基本概念
• (二) 二叉树
  1. 二叉树的定义及其主要特征
  2. 二叉树的顺序存储结构和链式存储结构
  3. 二叉树的遍历
  4. 线索二叉树的基本概念和构造
• (三) 树、森林
  1. 树的存储结构
  2. 森林与二叉树的转换
  3. 树和森林的遍历
• (四) 树与二叉树的应用
  1. 二叉搜索树
  2. 平衡二叉树
  3. 哈夫曼(Huffman)树和哈夫曼编码

4. 图

• (一) 图的基本概念
• (二) 图的存储及基本操作
  1. 邻接矩阵法
  2. 邻接表法
  3. 邻接多重表、十字链表
• (三) 图的遍历
  1. 深度优先搜索
  2. 广度优先搜索
• (四) 图的基本应用
  1. 最小(代价)生成树
  2. 最短路径
  3. 拓扑排序
  4. 关键路径

5. 查找

• (一) 查找的基本概念
• (二) 顺序查找法
• (三) 分块查找法
• (四) 折半查找法
• (五) B 树及其基本操作、B+树的基本概念
• (六) 散列(Hash)表
• (七) 字符串模式匹配
• (八) 查找算法的分析及应用

6. 排序

• (一) 排序的基本概念
• (二) 插入排序
  1. 直接插入排序
  2. 折半插入排序
• (三) 起泡排序(bubble sort)
• (四) 简单选择排序
• (五) 希尔排序(shell sort)
• (六) 快速排序
• (七) 堆排序
• (八) 二路归并排序(mergesort)
• (九) 基数排序
• (十) 外部排序
• (十一) 各种排序算法的比较
• (十二) 排序算法的应用