2014年数据结构考研大纲——陕西科技大学电气与信息工程学院

2014年数据结构考研大纲——陕西科技大学电气与信息工程学院

　　1. 基本概念：理解什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、抽象数据类型、算法及算法时间复杂度。

　　2. 线性表的基本概念：线性表的顺序表示和实现、线性表的链表表示和实现、链表运算(线性链表、循环链表、双向链表)。

　　3. 栈的特性、栈的基本运算、栈满及栈空条件、栈的应用(表达式计算、递归与栈);队列的特性、队列的基本运算(循环队列中队头与队尾指针的表示，队满及队空条件，队列的链表实现，链式队列中的队头与队尾指针的表示、双向队列的插入与删除算法)、队列的应用。

　　4. 串的特点、串的基本运算、串的模式匹配算法(简单算法及改进算法)。

　　5. 数组的定义、数组的按行顺序存储与按列顺序存储地址计算、矩阵的压缩存储;广义表定义、长度、深度、表头、表尾，用图形表示广义表的存储结构，广义表的递归算法(包括复制、求深度、求长度等算法)。

　　6. 树的定义、树的基本运算，二叉树定义、二叉树的性质及基本运算，完全二叉树的顺序存储、完全二叉树的双亲、子女和兄弟的位置，二叉树的前序、中序、后序遍历的递归算法及层序遍历算法，哈夫曼树的构造方法、哈夫曼编码、带权路径长度的计算。

　　7. 图的定义与图的存储表示(邻接矩阵表示、邻接表与逆邻接表表示，邻接多重表表示);深度优先遍历与广度优先遍历;会画出用Prim算法构造最小生成树的过程;最短路径(单源最短路径、任意顶点间的最短路径);关键路径。

　　8. 静态查找表的基本概念、静态查找的基本方法(顺序表、有序表、静态树表、索引顺序表的查找);动态查找表的基本概念、二叉查找树概念及查找算法、二叉排序树的基本概念及查找算法、B-树和B+树的基本概念、哈希表的基本概念、哈希函数的构造方法、冲突处理的方法、哈希表的查找算法及分析。

　　9. 排序的基本概念：关键码、初始关键码排列、关键码比较次数、数据移动次数、稳定性、附加存储、内部排序、外部排序;熟悉以下常用排序算法及稳定性、算法的复杂度：插入排序、选择排序、快速排序、二路归并排序、堆排序。

　　参考书目： 《数据结构》(C语言版)严蔚敏，清华大学出版社

相关推荐