北京石油化工学院硕士研究生入学考试《数据结构与算法》考试大纲

一、课程名称及对象

     名称：数据结构与算法

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

二、理论部分

（一）绪论

数据结构、逻辑结构、存储结构和抽象数据类型的基本概念； 算法的五个特性；

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

（二）线性表

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

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

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

（三）栈和队列

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

（四）串

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

定长顺序存储表示；

串的模式匹配算法：求子串位置的定位函数，模式匹配的改进算法； 串操作应用实例：文本编辑。

（五）树和二叉树

树的基本概念；

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

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