# 408数据结构考察范围

## 考察目标

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

## 一、线性表

### （一）线性表的基本概念

### （二）线性表的实现

1. 顺序存储
2. 链式存储
3. 线性表的应用

## 二、栈、队列和数组

### （一）栈和队列的基本概念

### （二）栈和队列的顺序存储结构

### （三）栈和队列的链式存储结构

### （四）栈、队列和数组的应用

### （五）特殊矩阵的压缩存储

### （六）多维数组的存储

## 三、树与二叉树

### （一）树的基本概念

### （二）二叉树

1. 二叉树的定义及其主要特征
2. 二叉树的顺序存储结构和链式存储结构
3. 二叉树的遍历
4. 线索二叉树的基本概念和构造

### （三）树、森林

1. 树的存储结构
2. 森林与二叉树的转换
3. 树和森林的遍历

### （四）树与二叉树的应用

1. 哈夫曼（Huffman）树和哈夫曼编码
2. 并查集及其应用

## 四、图

### （一）图的基本概念

### （二）图的存储及基本操作

1. 邻接矩阵法
2. 邻接表法
3. 邻接多重表、十字链表

### （三）图的遍历

1. 深度优先搜索
2. 广度优先搜索

### （四）图的基本应用

1. 最小（代价）生成树
2. 最短路径
3. 拓扑排序
4. 关键路径

## 五、查找

### （一）查找的基本概念

### （二）顺序查找法

### （三）分块查找法

### （四）折半查找法

### （五）树形查找结构

1. 二叉搜索树
2. 平衡二叉树
3. 红黑树

### （六）B树及其基本操作、B+树的基本概念

### （七）散列（Hash）表

### （八）字符串模式匹配

### （九）查找算法的分析及应用

## 六、排序

### （一）排序的基本概念

### （二）直接插入排序

### （三）折半插入排序

### （四）起泡排序（BubbleSort）

### （五）简单选择排序

### （六）希尔排序（ShellSort）

### （七）快速排序

### （八）堆排序

### （九）二路归并排序（MergeSort）

### （十）基数排序

### （十一）外部排序

### （十二）排序算法的分析与应用