考研408计算机学科专业基础综合 数据结构复习

考研408计算机学科专业基础综合 数据结构复习第一页数据结构一——基础线性表高频一、数据结构核心基础必背1. 数据结构定义相互之间存在一种或多种特定关系的数据元素的集合包括逻辑结构集合、线性、树形、图状和物理结构顺序存储、链式存储核心是“结构与操作的匹配”。2. 算法定义与特性解决特定问题的有限步骤集合特性必背有穷性、确定性、可行性、输入≥0、输出≥1。3. 算法复杂度高频考点重点掌握计算方法① 时间复杂度算法执行语句的频度只保留最高阶项如O(n²)、O(nlog₂n)忽略常数和低阶项② 空间复杂度算法执行所需额外存储空间不包括输入输出数据分为原地工作O(1)和需要额外空间如O(n)③ 高频复杂度场景冒泡排序O(n²)、快速排序O(nlog₂n)、二分查找O(log₂n)。二、线性表高频考点每年必考1. 线性表定义n个数据元素的有限序列特点元素有序、每个元素有唯一前驱和后继除首尾。2. 顺序表顺序存储① 存储方式用连续的存储空间存储元素下标从0开始② 核心操作必背实现思路插入平均O(n)需移动元素、删除平均O(n)、查找按值O(n)按位O(1)③ 优点随机访问快、存储密度高缺点插入删除效率低、扩容麻烦。3. 链表链式存储① 分类单链表只有后继指针、双链表有前驱后继指针、循环链表首尾相连② 核心操作必背单链表插入找到前驱节点修改指针、删除找到前驱节点断开指针、遍历O(n)③ 优点插入删除效率高O(1)找到节点后、无需扩容缺点随机访问慢O(n)、存储密度低需存指针。4. 高频考点单链表逆置、双链表插入删除、循环链表判空/判满、顺序表与链表的对比选择题必考。第二页数据结构二——栈、队列、串高频三、栈高频选择大题必考1. 栈的定义先进后出LIFO的线性表只允许在栈顶进行插入push和删除pop操作。2. 存储方式① 顺序栈用数组实现栈顶指针top初始-1栈满topmaxsize-1② 链栈用单链表实现栈顶为表头无需考虑栈满除非内存不足。3. 核心应用必背① 表达式求值后缀表达式大题高频② 括号匹配选择题高频③ 递归调用栈保存递归上下文④ 进制转换。4. 易错点顺序栈的栈满/栈空判断、链栈的插入删除方向栈顶为表头插入在表头。四、队列高频选择题为主1. 队列的定义先进先出FIFO的线性表只允许在队尾插入enqueue、队头删除dequeue。2. 存储方式① 顺序队列用数组实现队头front、队尾rear初始0存在“假溢出”问题② 循环队列重点解决假溢出队满条件rear1%maxsize front队空条件front rear③ 链队列用单链表实现队头为表头队尾为表尾无需考虑队满。3. 核心应用进程调度操作系统联动、缓冲队列、广度优先搜索BFS与图联动。五、串低频但必背选择题为主1. 串的定义由零个或多个字符组成的有限序列区别于线性表元素是字符。2. 串的存储定长顺序存储、堆分配存储、块链存储了解即可。3. 高频考点串的模式匹配算法必背——① 暴力匹配BF算法时间复杂度O(mn)简单但低效② KMP算法重点时间复杂度O(mn)核心是求next数组避免回溯主串无需背代码掌握next数组求解方法和匹配过程。第三页数据结构三——数组、矩阵、广义表低频抓重点六、数组低频选择题为主1. 数组的存储行优先C语言、列优先Fortran语言重点掌握二维数组地址计算必背。① 二维数组a[m][n]行优先存储a[i][j]的地址 基地址 (i*n j)*每个元素所占字节数② 列优先存储a[i][j]的地址 基地址 (j*m i)*每个元素所占字节数。七、矩阵高频考点选择题大题1. 特殊矩阵存储重点① 对称矩阵只存储上三角或下三角元素节省空间地址计算如下三角矩阵k i*(i1)/2 j② 三角矩阵上三角下三角全为0或下三角上三角全为0存储方式同对称矩阵额外存储一个常数0的区域③ 稀疏矩阵非零元素极少存储方式必背三元组表行、列、值、十字链表了解即可。八、广义表低频了解核心1. 广义表定义线性表的推广元素可以是原子单个元素或子表另一个广义表如LS (a, (b,c), d)。2. 核心考点广义表的深度嵌套层数、长度最外层元素个数如上述LS长度为3深度为2。第四页数据结构四——树与二叉树高频必考九、树的基本概念必背1. 树的定义n≥0个节点的有限集合n0为空树n≥1时存在一个根节点其余节点分为若干个互不相交的子树。2. 核心术语必背① 节点的度节点拥有的子树个数叶子节点度为0根节点度为子树个数② 树的度树中所有节点的最大度③ 深度高度根节点深度为1叶子节点深度为树的高度④ 层次根节点为第1层依次向下递增。3. 树的性质必背选择题高频① 树中节点总数 所有节点的度之和 1② 度为k的树第i层最多有k^(i-1)个节点③ 高度为h的k叉树最多有(k^h - 1)/(k-1)个节点。十、二叉树核心每年必考1. 二叉树定义每个节点最多有2个子树左子树、右子树有序左、右子树不能交换。2. 二叉树的性质必背① 第i层最多有2^(i-1)个节点② 高度为h的二叉树最多有2^h - 1个节点满二叉树③ 任意二叉树叶子节点数 度为2的节点数 1n0 n2 1④ 完全二叉树除最后一层外每一层节点数都满最后一层节点从左到右连续重点地址计算。3. 二叉树的存储① 顺序存储适用于完全二叉树节点i的左孩子2i右孩子2i1父节点i/2向下取整② 链式存储二叉链表每个节点有数据域、左指针lchild、右指针rchild重点掌握结构定义和遍历。4. 二叉树的遍历必背大题高频① 前序遍历根→左→右② 中序遍历左→根→右③ 后序遍历左→右→根④ 层序遍历按层次从上到下、从左到右用队列实现⑤ 高频考点根据两种遍历序列如前序中序还原二叉树大题必考。第五页数据结构五——树的应用图高频必考十一、树的应用高频1. 哈夫曼树最优二叉树必背① 定义带权路径长度WPL最小的二叉树权值越大的节点离根越近② 构造方法哈夫曼算法每次选两个权值最小的节点合并为一个新节点新节点权值为两者之和重复直到只剩一个节点③ 应用哈夫曼编码前缀编码无歧义用于数据压缩。2. 二叉排序树BST高频① 定义左子树所有节点值 根节点值右子树所有节点值 根节点值左右子树也为二叉排序树② 核心操作插入按大小插入保持排序特性、删除分叶子节点、度为1、度为2节点重点、查找平均O(log₂n)③ 易错点二叉排序树的查找效率与树的高度相关最坏情况单支树O(n)。3. 平衡二叉树AVL树高频① 定义左右子树高度差平衡因子的绝对值 ≤ 1平衡因子左子树高度-右子树高度② 失衡调整必背LL型、RR型、LR型、RL型掌握旋转方法无需背代码掌握旋转逻辑。十二、图核心每年必考选择大题1. 图的基本概念必背① 定义由顶点集V和边集E组成G(V,E)分为无向图边无方向、有向图边有方向② 核心术语顶点的度无向图边数有向图入度出度、路径顶点序列、环起点终点的路径、连通图任意两顶点可达、强连通图有向图任意两顶点相互可达。2. 图的存储必背大题高频① 邻接矩阵n×n矩阵a[i][j]1表示顶点i和j有边0表示无边优点查询快O(1)缺点空间复杂度O(n²)适合稠密图② 邻接表每个顶点对应一个链表存储其邻接顶点优点空间复杂度O(ne)适合稀疏图缺点查询慢O(n)。3. 图的遍历必背大题高频① 深度优先搜索DFS用栈实现优先访问当前顶点的邻接顶点再回溯类似树的前序遍历② 广度优先搜索BFS用队列实现按层次访问先访问当前顶点的所有邻接顶点再依次访问它们的邻接顶点类似树的层序遍历。第六页数据结构六——图的应用排序高频必考十三、图的应用必背大题高频1. 最小生成树MST必考① 定义连通图中权值和最小的生成树无环包含所有顶点② 算法必背Prim算法从一个顶点出发逐步添加权值最小的边适合稠密图时间复杂度O(n²)Kruskal算法按边的权值从小到大排序依次添加不形成环的边适合稀疏图时间复杂度O(eloge)。2. 最短路径必考① Dijkstra算法求单源最短路径从一个顶点到其他所有顶点不能处理负权边时间复杂度O(n²)② Floyd算法求所有顶点之间的最短路径可处理负权边不能有负权环时间复杂度O(n³)③ 高频考点两种算法的实现思路、步骤能手动计算最短路径。3. 拓扑排序高频有向图① 定义对有向无环图DAG的顶点进行排序使得对于每一条有向边(u→v)u在排序中位于v之前② 算法 Kahn算法用队列删除入度为0的顶点更新邻接顶点入度、DFS拓扑排序后序遍历逆序③ 应用任务调度、课程安排避免循环依赖。十四、排序必考选择大题重点掌握1. 排序分类① 稳定排序冒泡、插入、归并、基数排序② 不稳定排序选择、快速、希尔、堆排序③ 内部排序所有数据在内存中排序④ 外部排序数据量大需借助外存了解即可。2. 高频排序算法必背实现思路、复杂度、稳定性① 冒泡排序相邻元素比较逆序则交换O(n²)稳定② 插入排序将元素插入已排序序列O(n²)稳定③ 快速排序重点选基准元素分区小于基准放左大于放右递归排序O(nlog₂n)不稳定最坏O(n²)④ 归并排序重点分治思想将序列分成两半分别排序再合并O(nlog₂n)稳定⑤ 堆排序重点构建大根堆/小根堆每次取出堆顶元素调整堆O(nlog₂n)不稳定⑥ 希尔排序插入排序的改进按步长分组排序O(n^1.3)不稳定。3. 高频考点排序算法的时间/空间复杂度、稳定性对比选择题必考、快速排序的分区过程、归并排序的合并过程大题必考。