本文仅对全国硕士研究生招生考试计算机科学与技术联考计算机学科专业基础综合数据结构考试大纲（也就是计算机考研408）进行简单的解读，专业课大纲每年的变化很小，本文以2021年的考研大纲为基础（新大纲尚未发布，待发布后会调整内容，请持续关注）。
后续的博文也会按照本大纲进行展开，感兴趣的同学可以持续关注！
☆的数量标示知识点的重要程度。
考察目标
1.掌握数据结构的基本概念、基本原理和基本方法。
2.掌握数据结构的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。
3.能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。
1.线性表
- (☆☆)线性表的基本概念
- (☆☆☆)线性表的实现(存储结构)：顺序存储、链式存储
- (☆)线性表的应用
线性表是考研命题中的重中之重。基本上每年的算法设计题都是基于线性表的（顺序表或单链表），这类算法题实现起来代码量不大，但却要求具有最优的性能（时间复杂度和空间复杂度），才能获得满分。因此，应当牢固掌握线性表的各种基本操作（基于顺序、链式存储结构），我们在平时的学习中应多注重积累和培养动手能力。另外，需要提醒的是，算法最重要的是思想，在考场上的时间有限，在试卷上不一样要求代码具有实际的可执行性，因此应当尽力表达出算法的思想和步骤，不必过于拘泥于每一个细节。（对于C语言的编程建议，大家可以参考这篇文章）
2.栈、队列和数组
- (☆☆☆)栈和队列的基本概念
- (☆☆)栈和队列的顺序存储结构
- (☆☆☆)栈和队列的链式存储结构
- (☆)多维数组的存储
- (☆)特殊矩阵的压缩存储
- (☆☆)栈、队列、数组的应用
复习提示：本章内容通常以选择题的形式考察，题目不难，单命题的形式比较灵活。其中栈（出入栈的过程、出栈序列的合法性）和队列的操作及其特征是重中之重，属于每年必考的内容。由于它们均属于是线性表的应用和推广，很容易出现在算法设计题中。此外，栈和队列的顺序存储结构、链式存储结构及其特点、双端队列的特点、栈和队列的常见应用，以及数组和特殊矩阵的压缩存储都是必须要掌握的内容。
3.树和二叉树
- (☆)树的基本概念
- (☆☆☆☆)二叉树
- (☆☆☆)二叉树的定义及其主要特征（尤其要注意完全二叉树）
- (☆☆)二叉树的顺序存储结构和链式存储结构
- (☆☆)二叉树的遍历（递归与非递归）
- (☆☆)线索二叉树的基本概念和构造
- (☆☆)树和森林
- (☆)树的存储结构
- (☆☆)森林和二叉树的转换
- (☆)树和森林的遍历
- (☆☆)树和二叉树的应用
- (☆☆)二叉搜索树（二叉排序树）
- (☆☆)平衡二叉树
- (☆☆)哈夫曼树(Huffman)和哈夫曼编码
复习提示：本章内容通常以选择题的形式考察，但不排除会有算法题涉及树的遍历。树和二叉树的性质、遍历操作、转换、存储结构和操作特性等，满二叉树、完全二叉树、线索二叉树、哈夫曼树的定义和性质，二叉排序树和二叉平衡树的性质和操作等都是选择题必然会涉及的内容。
4.图
- (☆☆☆)图的基本概念
- (☆☆)图的存储及基本操作
- (☆☆)邻接矩阵法
- (☆)邻接表法
- (☆)邻接多重表、十字链表
- (☆☆)图的遍历
- (☆☆)深度优先搜索
- (☆☆)广度优先搜索
- (☆☆)图的基本应用
- (☆☆)最小（代价）生成树
- (☆)最短路径
- (☆)拓扑排序
- (☆)关键路径
复习提示：图算法的难度较大，因此主要掌握深度优先搜索与广度优先搜索的程序设计，其他内容以算法设计题形式出现的概率不大，通常会以选择题和综合题的形式考察。应掌握图的基本概念及基本性质（度、路径长度、回路、路径等）、图的存储结构（邻接矩阵、邻接表、邻接多重表和十字链表）及其特性、存储结构之间的转化、基于存储结构上的遍历操作和各种应用（拓扑排序、最小生成树、最短路径和关键路径）等。图的相关算法较多易混，但通常只需要掌握基本思想和实现步骤（能手动模拟、学而有余的同学可以通过编程实现一到两遍），而算法的具体实现则不是重点。读者应将这些算法按不同的方式分类，对比记忆，并用一定量的实例练习。
5.查找
- (☆)查找的基本概念
- (☆)顺序查找法
- (☆)分块查找法
- (☆)折半查找法
- (☆☆)二叉排序树、平衡二叉树
- (☆)B树及其基本操作、B+树的基本概念
- (☆☆☆)散列（hash）表
- (☆)字符串模式匹配（KMP）
- (☆☆☆)查找算法的分析及应用
复习提示：本章是考研命题的重点，特别是散列查找和折半查找，容易考计算题。对于散列查找，应掌握散列表的构造，冲突的处理方法（各种方法的处理过程）、查找成功和查找失败的平均查找长度、散列查找的特征和性能分析。对于折半查找，应掌握折半查找的过程，构造判定树、分析查找成功和查找失败的平均查找长度等；另外折半查找只能基于顺序表，因此也比较容易结合顺序表出算法设计题。B树和B+树是本章的难点，考纲仅要求了解B+树的基本概念和性质，而B树则要求掌握插入、删除和查找的操作过程，不要求掌握算法（学而有余的同学可以编程实现，掌握算法）。字符串模式匹配，需要重点掌握next数组的构造方法。
6排序
- (☆)排序的基本概念
- (☆)插入排序
- (☆)直接插入排序
- (☆)折半插入排序
- (☆)起泡排序
- (☆)简单选择排序
- (☆)希尔排序
- (☆☆)快速排序
- (☆☆)堆排序
- (☆☆)二路归并排序
- (☆)基数排序
- (☆)外部排序
- (☆☆)各种排序算法的比较
- (☆☆☆)排序算法的应用
复习提示：堆排序（建堆、插入和调整）、快速排序（划分、过程特性）和归并排序（归并路数、归并过程）是本章重点。我们应深入的理解掌握各种排序算法的思想、排序过程（能手动模拟、最好编程实现）和特征（初态的影响、时空复杂度、稳定性、适用性等），通常以选择题的形式考察不同算法之间的对比。此外，对于一些常用的排序算法的关键代码，要达到熟练编写的程度；看到某特定序列，应具有选择最优排序算法（根据排序算法特征）的能力。
又到了分隔线以下，本文到此就结束了，本文内容全部都是由博主根据自身理解与对考研资料进行的整理，仅作为参考，大佬有什么问题、或发现有什么错误，还请批评指正。
本专栏为数据结构知识，喜欢的话可以持续关注，如果本文对你有所帮助，还请还请点赞、评论加关注。