2021辽宁石油化工大学数据结构专业研究生考试大纲

一、 考试要求

1、理解数据结构的基本概念；把握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现；

2、把握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析；

3、能够选择合适的数据结构和方法进行问题求解。

二、 考试内容

1、线性表

（1）线性表的定义和基本操作。

（2）线性表的实现：①顺序存储结构；②链式存储结构；③线性表的应用。

2、栈、队列和数组

（1）栈和队列的基本概念。

（2）栈和队列的顺序存储结构。

（3）栈和队列的链式存储结构。

（4）栈和队列的应用。

（5）非凡矩阵的压缩存储。

3、树与二叉树

（1）树的概念。

（2）二叉树：①二叉树的定义及其主要特征；②二叉树的顺序存储结构和链式存储结构；③二叉树的遍历；④线索二叉树的基本概念和构造；⑤二叉排序树；⑥平衡二叉树。

（3）树、森林：①树的存储结构；②森林与二叉树的转换；③树和森林的遍历。

（4）树的应用：①等价类问题；②哈夫曼（Huffman）树和哈夫曼编码。

4、图

（1）图的概念。

（2）图的存储及基本操作：①邻接矩阵法；②邻接表法；

（3）图的遍历：①深度优先搜索；②广度优先搜索。

（4）图的基本应用及其复杂度分析：①最小（代价）生成树；②最短路径；③拓扑排序；③关键路径。

5、查找

（1）查找的基本概念。

（2）顺序查找法。

（3）折半查找法。

（4）B-树。

（5）散列（Hash）表及其查找。

（6）查找算法的分析及应用。

5、内部排序

（1）排序的基本概念。

（2）插入排序：①直接插入排序；②折半插入排序；

（3）气泡排序。

（4）简单选择排序。

（5）希尔排序（shell sort）。

（6）快速排序。

（7）堆排序。

（8）二路归并排序（merge sort）。

（9）基数排序。

（10）各种内部排序算法的比较。

（11）内部排序算法的应用。