考试科目：850数据结构

参考书目：

数据结构（C语言版）严蔚敏、吴伟民，清华大学出版社，2007年，第1版

专业课考试大纲：

一、考试内容

一、数据结构的有关概念

1．掌握数据结构的有关概念，理解逻辑结构与物理结构之间的关系。

2．掌握数据结构的几种基本结构。

3．掌握抽象数据类型的表示与实现方法。

4．熟悉算法分析的分析方法。

二、线性表

1．掌握线性表的顺序存储方法及链式存储方法。

2．熟悉线性表的建立、插入、删除、搜索与归并算法。

3．了解一元多项式的表示方法及其应用。

三、栈和队列

1．掌握栈和队列的顺序存储方法及链式存储方法。

2．熟悉进栈、出栈、进队、出队的实现方法。

3．栈和对列的简单应用。

4．递归的实现。

四、串

1．掌握串的有关概念，了解顺序存储方法及链式存储方法。

2．了解串的有关操作的实现方法。

3．了解串的模式匹配算法。

4．串的简单应用。

五、数组与广义表

1． 掌握数组的顺序存储方法及矩阵的压缩存储方法。

2． 掌握矩阵的转置算法和矩阵的相加算法的实现。

3． 了解广义表在m元多项式中的简单应用。

六、树和二叉树

1． 熟悉树和二叉树的有关定义，掌握二叉树的顺序存储结构和链式存储结构的实现方法。

2．掌握二叉树的建立及二叉树的几种遍历算法，了解树和森林的遍历方法。3．了解最优二叉树和哈夫曼树的应用。

4．其他简单应用。

七、图

1． 熟悉图的有关定义，掌握图的数组存储结构和邻接表存储结构的实现方法。

2．了解图的深度优先遍历算法和广度优先算法。

3．了解最小生成树、拓扑排序、关键路径的有关算法。

4．其他简单应用。

八、查找

1． 掌握静态查找表的几种查找方法。

2．掌握哈希表的构造方法及其冲突处理方法。

九、内部排序和外部排序

1． 掌握内部排序和外部排序的概念。

2． 熟悉插入排序、选择排序及常用的几种排序方法。

能分析几种常用的排序算法的时间复杂度与空间复杂度。