北京石油化工学院硕士研究生入学考试

《数据结构与算法》考试大纲

一、课程名称及对象

名称：数据结构与算法

对象：硕士研究生入学考试用

二、理论部分

（一）　绪论

数据结构、逻辑结构、存储结构和抽象数据类型的基本概念；

算法的五个特性；

算法时间和空间复杂度的含义及表示法。

（二）　线性表

线性表的概念、逻辑结构；

线性表的顺序存储结构及其基本操作和特征；

单链表、循环链表存储结构及其基本操作。

（三）　栈和队列

栈的特征、顺序栈和链栈的设置和操作实现，栈与递归的实现；

队列的特征、循环队列和链队列的设置和操作实现。

（四）　串

串类型的定义，串的表示和实现；

定长顺序存储表示；

串的模式匹配算法，求子串位置的定位函数，模式匹配的改进算法；

串操作应用实例：文本编辑。

（五）　树和二叉树

树的基本概念；

二叉树的概念和性质、二叉树的顺序存储结构和链式存储结构、二叉树的遍历和应用，二叉树非递归算法的实现；

树的存储结构、森林与二叉树间的转换。

（六）　图

无向图、有向图的相关概念及术语；

图的存储结构：数组表示法，邻接表；

图的深度优先和广度优先遍历算法。

（七）　查找

查找的概念及查找效率的评价方法；

静态查找表：顺序查找、折半查找算法；

动态查找表：二叉排序树和平衡二叉树；

哈希表的概念，哈希函数的构造方法和处理冲突的基本方法。

（八）　内部排序

插入类排序的排序算法、排序特点和排序过程；

交换类排序的排序算法、排序特点和排序过程：起泡排序、快速排序；

选择类排序的排序算法、排序特点和排序过程：简单选择排序。

三、参考书目

《数据结构》（C语言版），清华大学出版社，2007，严蔚敏，吴伟民编著， ISBN：978-7-302-14751-0。