一、适用专业

计算机技术

二、题目类型

计算分析题

算法设计题

画图题

三、参考书目

1. 《数据结构》（ C 语言版） 严蔚敏、吴伟民编著 清华大学出版社

2. 《数据结构题集》（ C 语言版）严蔚敏、吴伟民编著 清华大学出版社

四、基本内容

（一）绪论

1 掌握数据、数据元素、数据对象和数据类型、抽象数据类型的概念和术语的含义；理解数据结构的逻辑结构、存储结构的联系与区别以及对算法设计的作用。

2 理解算法的定义、性质、设计算法的要求；

3 掌握算法设计的基本要求以及计算语句频度和估算算法时间复杂度的方法。

（二）线性表

1 掌握线性表的逻辑结构特性是数据元素之间存在着的线性关系；

2 熟练掌握线性表的顺序存储结构和链式存储结构的描述方法及循环链表 , 双向链表的特点；

3 熟练掌握线性表在顺序存储结构和各种链表结构上的查找、插入和删除的算法；

4 能够从时间和空间复杂度的角度综合比较两种存储结构的不同特点及其适用的场合。

（三）栈和队列

1 熟练掌握栈和队列的结构特性 ---- 操作受限的线性表；

2 熟练掌握栈类型在两种存储结构表示时的基本操作实现方法；

3 熟练掌握循环队列和链队列的基本操作实现算法；

4 熟练掌握栈和队列的满和空的条件和它们的描述方法；

5 掌握 栈和队列在程序设计中的应用 。

（四）串

1 掌握串的结构特性 ---- 数据元素为字符的线性表；

2 串的三种存储表示以及各种基本操作的实现及其应用

3 掌握串匹配的 KMP 算法 , 熟悉 next 函数的定义 , 学会手工计算 next 函数值。

（五）数组

1 掌握高维数组存在一维数组中的两种存储表示方法及以行为主 ( 低下标优先 ) 的存储结构中的地址计算 , 特别注意下标是从 0 开始或从 1 开始；

2 掌握对特殊矩阵 ( 对称矩阵 , 下三角矩阵等 ) 进行压缩存储时的下标变换公式；

3 领会稀疏矩阵的压缩方式和简单运算；

4 了解广义表的定义和基本运算。

（六） 树和二叉树

1 熟悉树的基本定义及其相关的术语的含义（如孩子、兄弟 , 深度、度等概念）；

2 熟练掌握二叉树的结构特性，了解相应的证明方法 , 理解常见的二叉树（如满二叉树，完全二叉树， Huffman 树，平衡二叉树，排序二叉树和判定树）有关理论结论；

3 熟悉二叉树的二叉链和线索二叉树存储结构特点及适用范围；

4 熟悉三种遍历二叉树的递归算法（先序 , 中序和后序）；

5 掌握二叉树线索化的实质及线索化的过程；

6 领会并掌握树的各种存储结构。

7 掌握树和森林与二叉树的转换 , 及其各自遍历的对应关系；了解树的简单应用。

了解实现树的各种操作的算法；

8 掌握最优树的特性，掌握 Huffman 树及其应用。

（七） 图

1 掌握图的定义和术语（如顶点，边，度及其相互之间的数量关系 , 连通性与生成树等）；

2 掌握图的两种存储结构：数组表示法（邻接矩阵）、邻接表，了解实际问题的求解效率与采取何种存储结构和算法有密切关系；

3 掌握图的两种遍历策略：深度优先搜索和广度优先搜索；图的遍历和树的遍历之间的类似与差异；

4 熟悉图的最小生成树的生成方法（ Prim 方法和 Kruskal 方法）；

5 理解拓扑排序、关键路径、最短路径的算法思想。

（八）查找

1 熟练掌握顺序表和有序表的查找方法（顺序查找和二分查找）；

2 掌握查找效率的计算方法 ----- 平均查找长度；

3 熟练掌握二叉排序树的构造和查找方法；

4 掌握平衡二叉树的构造方法；

（九）内部排序

1 掌握排序的定义和各种排序方法的基本思想及其特点；

2 了解各种排序方法的排序过程及其依据的原则，基于“关键字间的比较”进行排序的方法可以分为插入排序、交换排序、选择排序、归并排序和基数排序；

3 熟练掌握快速排序和堆排序等方法的实例排序过程；

4 能够进行各种排序方法的时间复杂性 ( 平均情况与最坏情况 ) 估计或分析；

5 一般了解排序方法“稳定”的含义。