2017年长沙理工大学850数据结构考研大纲

科目代码：850 科目名称：数据结构
一、考试内容
一、数据结构的有关概念
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．熟悉插入排序、选择排序及常用的几种排序方法。
能分析几种常用的排序算法的时间复杂度与空间复杂度。
二、参考书目
数据结构（C 语言版）严蔚敏、吴伟民，清华大学出版社，2007 年，第 1 版