重庆师范大学2027年硕士研究生招生考试自命题科目考试大纲：819数据结构与算法

重庆师范大学2027年硕士研究生招生考试自命题科目考试大纲：819数据结构与算法

  一、考试范围

  数据结构与算法考试范围为数据结构及相关算法。涉及结构有线性结构（线性表、栈与队列、串、数组与广义表）、树与二叉树结构、图结构及相关算法；不同结构下的查找算法、排序算法及其对比与应用。

  二、考试要求

  要求考生理解数据结构的基本概念；掌握数据的逻辑结构和存储结构，以及各种结构的基本操作算法的实现。能对算法的时间复杂度与空间复杂度进行分析。具备采用C/C++语言设计与实现算法的能力。对实际问题的求解能选择合适的数据结构和方法来完成。

  三、主要内容

  第1章 绪论

  数据结构基本概念及术语；

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

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

  第2章 线性表

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

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

  线性表链式结构及基本操作和特征，典型的单链表、循环链表、双向链表、双向循环链表的存储结构及其各种基本操作算法；

  在顺序表和链表存储结构上的典型算法的设计与实现，提高算法性能的优化算法设计方法。

  第3章 栈和队列

  栈的特征、顺序栈和链栈的定义和操作算法实现，栈与递归算法的实现；

  队列的特征、循环队列和链队列的定义和操作算法实现；

  栈和队列的结构特性和典型操作算法设计。

  第4章 串、数组和广义表

  串类型的定义，串的表示和实现；定长顺序存储表示，堆分配存储表示；

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

  串操作应用实例算法设计；

  数组的定义，数组的顺序表示和实现；

  矩阵的压缩存储，特殊矩阵，稀疏矩阵；

  广义表的定义，广义表的存储结构，建立广义表的存储结构；广义表的相关操作算法。

  第5章 树和二叉树

  树的基本概念和特征；

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

  树的存储结构、树和森林与二叉树间的转换，掌握树和森林的遍历；了解并查集及其应用。

  哈夫曼树的概念、哈夫曼树的构造过程算法及哈夫曼编码输出算法设计与实现；了解译码的方法；利用二叉树求解表达式的值。

  第6章 图

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

  图的邻接矩阵和邻接表的存储结构，十字链表，邻接多重表；

  图的深度优先和广度优先遍历算法及其应用；

  最小生成树（Prim算法和Kruskal算法）的求解过程；

  有向无环图的概念，拓扑排序和关键路径的求解过程；

  带权最短路径的概念，最短路径的求解过程。

  第7章 查找

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

  静态查找表的概念，熟练顺序、折半查找算法、分块查找方法；

  动态查找表和二叉排序树的概念、查找及相关操作；

  理解平衡二叉树的概念与操作；B+、B-树的概念与操作；

  哈希表的概念，熟练掌握哈希函数的构造和处理冲突的基本方法，哈希表的构造，查找成功和失败的平均查找长度的计算；

  第8章 排序

  理解排序概念；各类排序的过程、特征及算法。

  插入类排序的排序算法、排序特点和排序过程，如直接插入排序、希尔排序；

  交换类排序的排序算法、排序特点和排序过程，如冒泡排序、快速排序；

  选择类排序的排序算法、排序特点和排序过程，如简单选择排序、堆排序；

  归并排序的排序算法、排序特点和排序过程；

  以上各种排序算法的稳定性，各种排序方法时间复杂度和空间复杂度分析。

  基数排序的排序算法、排序特点和排序过程。如多关键字排序、链基数排序。

  外部排序的外存信息的存取、排序的基本方法和排序过程。如多路平衡归并的实现；置换-选择排序；最佳归并树。