（二） 插入排序
1. 直接插入排序
2. 折半插入排序
（三） 气泡排序（ bubble sort）
（四） 简单选择排序
（五） 希尔排序（ shell sort）
（六） 快速排序
（七） 堆排序
（八） 二路归并排序（ merge sort）
（九） 基数排序
（十） 各种内部排序算法的比较
（十一） 内部排序算法的应用
【知识点解析】
1. 线性表
线性表是一种最简单的数据结构，在线性表方面，主要考查线性表的定义和基本操作、线性表的
实现。在线性表实现方面，要掌握的是线性表的存储结构，包括顺序存储结构和链式存储结构，特
别是链式存储结构，是考查的重点。另外，还要掌握线性表的基本应用。
2. 栈、队列和数组
栈和队列是两种特殊的线性表，在这方面，要求我们掌握栈和队列的基本概念，以及他们之间的
区别。对于栈和队列的存储结构 ( 包括顺序存储结构、链式存储结构 ) 要有较深的理解，对于栈和队
列的应用，例如，排队问题、子程序调用问题、表达式问题等，要搞清楚。
一维数组属于线性表范畴，但多维数组不属于线性表。在这方面，主要掌握数组的存储结构，例
如按行优先、按列优先等，某个元素存在的地址是什么。对于特殊矩阵 ( 二维数组 ) 的压缩存储原理
也要搞清楚。
3 、树与二叉树
二叉树和树是两种不同的概念，这一点是必须要搞清楚的。在这个部分，我们要掌握树的定义、
二叉树的定义及主要特征 ( 特殊的二叉树、二叉树的性质 ) 。在二叉树的顺序存储结构和链式存储结
构方面， 特别是链式存储结构， 因为很多应用都是建立在链式存储基础上， 例如， 二叉树的遍历 ( 前
序遍历、中序遍历、后序遍历 ) 就是一种典型的应用。
在特殊的二叉树中， 完全二叉树的概念是必须要搞清楚的， 其次，线索二叉树的基本概念和构造、
二叉排序树、 平衡二叉树的基本概念和应用， 特别是二叉排序树的基本性质和特点要能很好地理解。
多棵独立的树就组成了森林，树的存储结构和遍历、森林的遍历、树和二叉树的转换、森林和二
叉树的转换等知识，也要有了了解。
最后就是树的应用，通常会作为综合应用类试题出现，包括等价类问题、哈夫曼 (Huffman) 树和
哈夫曼编码等。
4 、图
在数据结构中，图的结构是最复杂的，这里的概念也是最多的。我们要掌握图的基本概念 ( 有向
图、无向图、连通、路径、子图、出度、入度、生成树、最短路径、关键路径等 ) 。
图的存储及基本操作主要有邻接矩阵法和邻接表法，我们要掌握这有向图和无向图的这 2 种存储
方法，要清楚图的连通和存储方法之间的关系。例如，一个顶点的出度和临界矩阵中 1 的个数有什
么关系，等等。
图的遍历方法有深度优先搜索和广度优先搜索，我们要掌握这 2 种遍历方法的算法实现。给出一
个具体的图，要能知道它的遍历次序。
在数据结构课程中， 图的基本应用是最多的， 也是最复杂的， 我们要掌握这些应用的复杂度分析。
要掌握的具体应用主要包括最小 ( 代价 ) 生成树、最短路径、拓扑排序、关键路径。在给出的一个具
体的图中，我们要会利用已知条件，求出上述应用的结果。
