2021年辽宁石油化工大学计算机与通信工程学院数据结构考试大纲

　　►最新免费课程：

　　新传免费课：10.13务实写作题复习

　　教育免费课：10.13最后冲刺复习要点

　　一、 考试要求

　　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）内部排序算法的应用。