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