# 📚 数据结构知识点笔记 > 考研408 - 数据结构 ============================================================ 📅 学习时间：2026-05-04 11:55:08 🏷️ 知识点ID：ds_01 (MD5: b5c14b1f) ============================================================ ### 时间复杂度与空间复杂度分析 **核心概念** - 时间复杂度：算法执行次数与问题规模的渐近关系 - 空间复杂度：算法所需存储空间与问题规模的渐近关系 - 常用记号：O(1)、O(log n)、O(n)、O(n log n)、O(n2)、O(n3)、O(2n)、O(n!) **易错点** 1. 混淆O(n)和O(2n)：系数不重要，渐近上界只看最高次项 2. 递归算法空间复杂度：递归深度×每次递归的局部变量大小 3. 最好/最坏/平均复杂度：不要把三者混淆 **典型题目** for (i = 0; i < n; i++) for (j = i; j < n; j++): pass # O(1)操作 分析：外层n次，内层分别为n, n-1, n-2...1，总和 = n(n+1)/2 = O(n2) ============================================================ 📅 学习时间：2026-05-04 15:00:01 🏷️ 知识点ID：ds_03 (MD5: 08662c02) ============================================================ ### 二叉树遍历与线索二叉树 **核心概念** - 先序遍历（DLR）：根-左-右 - 中序遍历（LDR）：左-根-右 - 后序遍历（LRD）：左-右-根 - 层序遍历：利用队列，层内从左到右 **易错点** 1. 已知两种遍历序列（包含中序），可唯一确定二叉树 2. 仅有先序+后序无法唯一确定（可确定祖先关系但不能确定结构） 3. 递归遍历时间复杂度O(n)，空间复杂度O(h)，h为树高 **线索二叉树** - 目的：加快遍历速度，避免递归/栈 - 规定：若无左孩子，指向前驱；若无右孩子，指向后继 - 需要ltag/rtag标志位区分孩子指针和线索指针 **典型题目** 已知先序序列：ABDECF，中序序列：DBEAFC，构建二叉树 1. 先序根A → 中序分 DBE | A | CF 2. 左子树先序：BDE，中序：DBE → B为左子树根 3. 右子树先序：CF，中序：CF → C为右子树根 4. 结果：A左子B(B左D右E)，A右子C(C左F) ============================================================ 📅 学习时间：2026-05-04 20:00:01 🏷️ 知识点ID：ds_05 (MD5: 98057d4b) ============================================================ ### 查找算法：二分、平衡二叉树、散列表 **二分查找** - 条件：有序顺序表 - 时间复杂度：O(log n) - 易错：边界条件，mid = left + (right - left) // 2 **平衡二叉树（AVL）** - 定义：左右子树高度差绝对值小于等于1 - 旋转操作：LL（右单旋）、RR（左单旋）、LR（先左后右双旋）、RL（先右后左双旋） - 插入：先 BST 插入，再调整平衡因子 **B树与B+树** - B树：多路平衡查找树，节点包含数据 - B+树：非叶子节点只含索引，所有数据在叶子 - MySQL索引用B+树（叶子链表便于范围查询） **散列表** - 冲突处理：开放地址法（线性探测、二次探测）、链地址法 - 装填因子 = n/m，影响查找效率 - 开放地址法探测序列：h(key) = (h0 + f(i)) % m ============================================================ 📅 学习时间：2026-05-05 00:00:01 🏷️ 知识点ID：ds_04 (MD5: 0fd8e00c) ============================================================ ### 图遍历：DFS与BFS及其应用 **核心概念** - BFS（广度优先）：用队列，按层次遍历 - DFS（深度优先）：用栈（或递归），先深后广 - 时间复杂度：邻接表O(V+E)，邻接矩阵O(V2) **易错点** 1. BFS计算最短路径（无权图）：首次到达即为最短 2. DFS生成树/森林：同一强连通分量的顶点可通过DFS访问 3. 邻接矩阵空间复杂度O(V2)，适合稠密图 **应用** - BFS：最短路径（无权）、拓扑排序（Kahn算法） - DFS：拓扑排序（基于DFS的逆序）、强连通分量（Kosaraju） **典型题目** 拓扑排序算法（Kahn）： 1. 计算所有顶点入度 2. 将入度为0的顶点入队 3. 不断出队，删除边，更新入度 4. 若输出顶点数为V，则无环；否则有环 时间复杂度：O(V+E) ============================================================ 📅 学习时间：2026-05-05 02:00:01 🏷️ 知识点ID：ds_02 (MD5: 8ffc4851) ============================================================ ### 栈和队列的性质与扩展 **核心概念** - 栈：LIFO，先进后出；操作：push/pop/top - 队列：FIFO，先进先出；操作：enqueue/dequeue/front - 循环队列：避免假溢出，用(n+1)个空间区分满/空 **易错点** 1. 循环队列队空条件：front == rear 2. 循环队列队满条件：(rear + 1) % maxsize == front 3. 中缀表达式转后缀表达式时，栈中存放操作符，优先级低的运算符在前 **典型题目** 使用两个栈实现队列：stack_in用于入队，stack_out用于出队 - 入队：元素压入stack_in - 出队：如果stack_out不为空，弹出stack_out栈顶；否则把stack_in全部倒入stack_out 均摊时间复杂度：O(1) ============================================================ 📅 学习时间：2026-05-05 05:00:01 🏷️ 知识点ID：ds_02 (MD5: 8ffc4851) ============================================================ ### 栈和队列的性质与扩展 **核心概念** - 栈：LIFO，先进后出；操作：push/pop/top - 队列：FIFO，先进先出；操作：enqueue/dequeue/front - 循环队列：避免假溢出，用(n+1)个空间区分满/空 **易错点** 1. 循环队列队空条件：front == rear 2. 循环队列队满条件：(rear + 1) % maxsize == front 3. 中缀表达式转后缀表达式时，栈中存放操作符，优先级低的运算符在前 **典型题目** 使用两个栈实现队列：stack_in用于入队，stack_out用于出队 - 入队：元素压入stack_in - 出队：如果stack_out不为空，弹出stack_out栈顶；否则把stack_in全部倒入stack_out 均摊时间复杂度：O(1) ============================================================ 📅 学习时间：2026-05-05 08:00:01 🏷️ 知识点ID：ds_03 (MD5: 08662c02) ============================================================ ### 二叉树遍历与线索二叉树 **核心概念** - 先序遍历（DLR）：根-左-右 - 中序遍历（LDR）：左-根-右 - 后序遍历（LRD）：左-右-根 - 层序遍历：利用队列，层内从左到右 **易错点** 1. 已知两种遍历序列（包含中序），可唯一确定二叉树 2. 仅有先序+后序无法唯一确定（可确定祖先关系但不能确定结构） 3. 递归遍历时间复杂度O(n)，空间复杂度O(h)，h为树高 **线索二叉树** - 目的：加快遍历速度，避免递归/栈 - 规定：若无左孩子，指向前驱；若无右孩子，指向后继 - 需要ltag/rtag标志位区分孩子指针和线索指针 **典型题目** 已知先序序列：ABDECF，中序序列：DBEAFC，构建二叉树 1. 先序根A → 中序分 DBE | A | CF 2. 左子树先序：BDE，中序：DBE → B为左子树根 3. 右子树先序：CF，中序：CF → C为右子树根 4. 结果：A左子B(B左D右E)，A右子C(C左F) ============================================================ 📅 学习时间：2026-05-05 13:00:01 🏷️ 知识点ID：ds_05 (MD5: 98057d4b) ============================================================ ### 查找算法：二分、平衡二叉树、散列表 **二分查找** - 条件：有序顺序表 - 时间复杂度：O(log n) - 易错：边界条件，mid = left + (right - left) // 2 **平衡二叉树（AVL）** - 定义：左右子树高度差绝对值小于等于1 - 旋转操作：LL（右单旋）、RR（左单旋）、LR（先左后右双旋）、RL（先右后左双旋） - 插入：先 BST 插入，再调整平衡因子 **B树与B+树** - B树：多路平衡查找树，节点包含数据 - B+树：非叶子节点只含索引，所有数据在叶子 - MySQL索引用B+树（叶子链表便于范围查询） **散列表** - 冲突处理：开放地址法（线性探测、二次探测）、链地址法 - 装填因子 = n/m，影响查找效率 - 开放地址法探测序列：h(key) = (h0 + f(i)) % m ============================================================ 📅 学习时间：2026-05-05 20:00:01 🏷️ 知识点ID：ds_04 (MD5: 0fd8e00c) ============================================================ ### 图遍历：DFS与BFS及其应用 **核心概念** - BFS（广度优先）：用队列，按层次遍历 - DFS（深度优先）：用栈（或递归），先深后广 - 时间复杂度：邻接表O(V+E)，邻接矩阵O(V2) **易错点** 1. BFS计算最短路径（无权图）：首次到达即为最短 2. DFS生成树/森林：同一强连通分量的顶点可通过DFS访问 3. 邻接矩阵空间复杂度O(V2)，适合稠密图 **应用** - BFS：最短路径（无权）、拓扑排序（Kahn算法） - DFS：拓扑排序（基于DFS的逆序）、强连通分量（Kosaraju） **典型题目** 拓扑排序算法（Kahn）： 1. 计算所有顶点入度 2. 将入度为0的顶点入队 3. 不断出队，删除边，更新入度 4. 若输出顶点数为V，则无环；否则有环 时间复杂度：O(V+E) --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [408数据结构复习框架二（树与二叉树、图），含近十年考研真题] 8.4图的应用（最小生成树、最短路径、拓扑排序、拓扑排序）. （1）最小生成树. 性质：最小生成树的树形不唯一；其对应的边的权值之和总是唯一的，而且是 2. [考研408核心知识体系与备考策略深度解析] # 考研408核心知识体系与备考策略深度解析 简介：本文系统梳理计算机专业考研408科目（数据结构、计算机组成原理、操作系统、计算机网络）的核心知识框架，结合历年真题分析命题规律，提供分阶段备考方案及高效复习技巧，助力考生构建完整知识体系。 ### 一、考研408科目构成与命题特点 计算机专业基础综合（408）作为全国统考科目，涵盖数据结构（45分）、计算机组成原理（45分）、操作系统（35分）、计算机网络（25分）四大模块，总分150分。其命题呈现三大特征：知识点覆盖广、题型灵活多变、强调综合应用。 以2023年真题为例，数据结构部分通过”平衡二叉树构建与遍历”综合题，同时考察树结构 **典型真题摘录：** 1. [实用指南：数据结构——三十六、拓扑排序(王道408) - yangykaifa - 博客园] #### 2.例子 在这里插入图片描述 在这里插入图片描述 在这里插入图片描述 ### 3.代码实现 `bool ReverseTopologicalSort(Graph G){ int outdegree[MaxVertexNum];// 当前顶点出度 int print[MaxVertexNum];// 记录拓扑序列 InitStack(S); //初始化栈，存储出度为0的顶点 for(int i=0; i 加上线索的二叉树称为线索二叉树，其中指向结点前驱和后继的指针称为线索。 在后序线索二叉树中找结点的后继较为复杂，可分为三种情况： 1. 若结点x是二叉树的根，则其后继为空； 2. 若结点x是其双亲的右孩子，或其双亲的左孩子且其双亲没有右子树，则其后继即为双亲； 3. 若结点x是其双亲的左孩子，且其双亲有右子树，则其后继即为双亲的右子树上按后序遍历列出的第一个结点。 【树的存储结构】 1. 双亲表示法(用一组连续空间来存储每个结点) 2. 孩子表示法(将每个结点的孩子结点都用单链表链接起来形成一个线形结构，此时n个结点就有n个孩子链表，叶子结点的单链表为空表) 3. 孩子兄弟表示法( 3. [考研408核心知识体系与备考策略深度解析] # 考研408核心知识体系与备考策略深度解析 简介：本文系统梳理计算机专业考研408科目（数据结构、计算机组成原理、操作系统、计算机网络）的核心知识框架，结合历年真题分析命题规律，提供分阶段备考方案及高效复习技巧，助力考生构建完整知识体系。 ### 一、考研408科目构成与命题特点 计算机专业基础综合（408）作为全国统考科目，涵盖数据结构（45分）、计算机组成原理（45分）、操作系统（35分）、计算机网络（25分）四大模块，总分150分。其命题呈现三大特征：知识点覆盖广、题型灵活多变、强调综合应用。 以2023年真题为例，数据结构部分通过”平衡二叉树构建与遍历”综合题，同时考察树结构 **典型真题摘录：** 1. [实用指南：数据结构——三十六、拓扑排序(王道408) - yangykaifa - 博客园] #### 2.例子 在这里插入图片描述 在这里插入图片描述 在这里插入图片描述 ### 3.代码实现 `bool ReverseTopologicalSort(Graph G){ int outdegree[MaxVertexNum];// 当前顶点出度 int print[MaxVertexNum];// 记录拓扑序列 InitStack(S); //初始化栈，存储出度为0的顶点 for(int i=0; i=1) 高度为h，度为m的树【度为m的树指的是结点最多有m个孩子结点】至多有mh−1m−1\fr 2. [GitHub - ddy-ddy/cs-408: 计算机考研专业课程408相关的复习经验，资源和OneNote笔记 · GitHub] ## 二、数据结构 数据结构网上有很多质量很高的文章。有图解动画还有代码，这里推荐几个我看过的博客:Data-Structres | 算法大汇总 数据结构会画算法运行的流程图也就会做题了，笔记中记录了大多数算法的手绘流程图以及总结的算法常用结论和常考点。 👇下图是数据结构笔记中关于二叉树四种遍历方式的知识点：包括遍历过程，示例图，代码。[]( ## 三、计算机组成原理 计算机组成原理我是靠着王道视频和王道书过来的，如果实在有不理解的地方，我就会google，看各种博客。有些博客确实讲的很不错，精辟且易懂。计组难，但是还是有章可循的，主要以做题为导向！ 👇下图是计组笔记中一个关于控制 3. [(王道408考研数据结构)第五章树-第二节1：二叉树的定义 - CSDN博客] (王道408考研数据结构)第五章树-第二节1：二叉树的定义、特殊的二叉树及二叉树性质 原创 · 一：二叉树基本概念. （1）二叉树定义; （2）二叉树五种形态 · 二：特殊 **典型真题摘录：** 1. [王道计算机考研团队整理22考研408真题及答案| PDF - Scribd] Scribd # 王道计算机考研团队整理 22考研408真题及答案 王道计算机考研团队整理 22考研408真题及答案 ## Uploaded by AI-enhanced title and description # 王道计算机考研团队整理 22考研408真题及答案 这是一道判断二叉树是否为二叉搜索树的题目。题目要求使用C或C++语言描述一个高效算法。答案提供了算法的基本设计思想是利用中序遍历判断是否为升序序列,并使用递归方式实现中序遍历算法,关键步骤使用注释进行说明。 # 王道计算机考研团队整理 22考研408真题及答案 王道计算机考研团队整理 22考研408真题及答案 ## Uploaded by AI-enhanced title and description ## Share this document ## Footer menu ## About 2. [C 408—《数据结构》易错考点200题（含解析）] 博文中涉及的题目均来自《王道数据结构考研复习指导》，《竟成408考研复习全书》，以及《408统考历年真题》，其中真题部分包括09~22年的所有选择题真题。 3. [【已完结】2025考研数据结构全程班基础部分（适用于408与自命题）] 5-1 树与二叉树的定义; 5-2 二叉树的存储与遍历; 5-3 线索二叉树; 5-4 树、二叉树、森林的转换; 5-5 哈夫曼树; 5-6 习题解析; 6-1 图的定义和基本术语; 6-2 图的存储结构 --- ============================================================ 📅 学习时间：2026-05-07 02:00:01 🏷️ 知识点ID：ds_02 (MD5: 8ffc4851) ============================================================ ### 栈和队列的性质与扩展 **核心概念** - 栈：LIFO，先进后出；操作：push/pop/top - 队列：FIFO，先进先出；操作：enqueue/dequeue/front - 循环队列：避免假溢出，用(n+1)个空间区分满/空 **易错点** 1. 循环队列队空条件：front == rear 2. 循环队列队满条件：(rear + 1) % maxsize == front 3. 中缀表达式转后缀表达式时，栈中存放操作符，优先级低的运算符在前 **出栈序列判定定理** 对于入栈序列1,2,3...,n的输出序列：每个数字后面比它小的数字必须按**递减顺序**排列。例如：入栈1,2,3,4，若出栈序列为4,3,2,1，对于数字4后面比4小的{1,2,3}必须递减排列（3>2>1 ✓）。 **典型题目** 使用两个栈实现队列：stack_in用于入队，stack_out用于出队 - 入队：元素压入stack_in - 出队：如果stack_out不为空，弹出stack_out栈顶；否则把stack_in全部倒入stack_out 均摊时间复杂度：O(1) --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [王道计算机考研 数据结构_哔哩哔哩_bilibili] 12:39 3.1.3\_栈的链式存储实现 03:52 3.2.1\_队列的基本概念 04:09 3.2.2\_队列的顺序实现 16:46 3.2.3\_队列的链式实现 09:25 3.2.4\_双端队列 14:54 3.3.1\_栈在括号匹配中的应用 11:48 3.3.2\_1\_栈在表达式求值中的应用(上) 31:41 3.3.2\_2\_栈在表达式求值中的应用(下) 20:33 3.3.3\_栈在递归中的应用 13:01 3.3.4+3.3.5\_队列的应用 08:24 3.4.1-3.4.4\_特殊矩阵的压缩存储 27:41 4.1\_1 **典型真题摘录：** 1. [408历年真题解析数据结构篇 - 知乎专栏] 408历年真题有非常强的继承关系，例如. 2019年题10考察了2014年题11中的快速排序中每一趟排序后的序列；; 2021年题2考察了2010年题2中的输出受限的双端队列可能的出队序列； 2. [2020年408真题数据结构篇 - 知乎专栏] 设有一条u→v的有向边，递归需要用到递归栈，按照题意，先输出栈顶的，再输出栈底的，所以先输出v，再输出u，即先输出出度为0的结点v，此时让u的出度减一变为0，再输出u，正好和拓扑 3. [24考研计算机王道408网课分享（数据结构/组成原理/操作系统/计算机 ...] 数据结构10题分析题主要考察的是线性表和树中的算法设计和实现，基本上每年都会在这两个部分出题。在大家复习的过程中，要重点学习这两个部分。 线性表部分，建议大家优先学习 --- ============================================================ 📅 学习时间：2026-05-07 10:00:01 🏷️ 知识点ID：ds_01 (MD5: b5c14b1f) ============================================================ ### 时间复杂度与空间复杂度分析 **核心概念** - 时间复杂度：算法执行次数与问题规模的渐近关系 - 空间复杂度：算法所需存储空间与问题规模的渐近关系 - 常用记号：O(1)、O(log n)、O(n)、O(n log n)、O(n2)、O(n3)、O(2n)、O(n!) **易错点** 1. 混淆O(n)和O(2n)：系数不重要，渐近上界只看最高次项 2. 递归算法空间复杂度：递归深度×每次递归的局部变量大小 3. 最好/最坏/平均复杂度：不要把三者混淆 **典型题目** for (i = 0; i < n; i++) for (j = i; j < n; j++): pass # O(1)操作 分析：外层n次，内层分别为n, n-1, n-2...1，总和 = n(n+1)/2 = O(n2) --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [408考研数据结构复习-时间复杂度与空间复杂度-附统考真题-阿里云开发者社区] 5 【2012统考真题】求整数n的阶乘的算法如下，其时间复杂度是（O(n)） 解析：该递归相当于返回O(n)次。 6 【2013统考真题】已知两个长度分别为m和n的升序链表，若将它们合并为长度为m+n的一个降序链表，则最坏情况下的时间复杂度是（O(max(m,n))） 解析：两个升序链表合并，两两比较表中元素，每比较一次，确定一个元素的链接位置（取较小元素）。当一个链表比较结束后，将另一个链表的剩余元素插入即可。最坏的情况是两个链表中的元素依次进行比较，因为2max(m,n)>=m+n，所以时间复杂度为O(max(m,n))。 7 【2014统考真题】下列程序段的时间复杂度是（nlon **典型真题摘录：** 1. [计算机考研408真题解析（2023-01 深入解析顺序表操作的 ...] ... 数据结构真题中关于顺序表操作时间复杂度的考查，详细分析了顺序表在查找、插入、删除及获取元素等操作上的平均时间复杂度 ... 本文基于2023年408考研真题， 2. [计算机考研408真题解析（2025-01 嵌套循环时间复杂度深度 ...] 摘要：本文基于2025年408考研真题，深入分析嵌套循环时间复杂度的计算方法，提供完整的算法实现和性能优化方案。通过数学推导和代码验证，揭示了看似O(n²)的 3. [数据结构打卡表| PDF - Scribd] 【考点视频】1.2_3 算法的空间复杂度【王道书】 1.2.2_2 【习题】1.2.3 小题：全部【习题】1.2.3 大题：1 【考点视频】2.1 线性表的定义和基本操作【王道书】 2.1.1 --- ============================================================ 📅 学习时间：2026-05-07 18:00:01 🏷️ 知识点ID：ds_05 (MD5: 98057d4b) ============================================================ ### 查找算法：二分、平衡二叉树、散列表 **二分查找** - 条件：有序顺序表 - 时间复杂度：O(log n) - 易错：边界条件，mid = left + (right - left) // 2 **平衡二叉树（AVL）** - 定义：左右子树高度差绝对值小于等于1 - 旋转操作：LL（右单旋）、RR（左单旋）、LR（先左后右双旋）、RL（先右后左双旋） - 插入：先 BST 插入，再调整平衡因子 **B树与B+树** - B树：多路平衡查找树，节点包含数据 - B+树：非叶子节点只含索引，所有数据在叶子 - MySQL索引用B+树（叶子链表便于范围查询） **散列表** - 冲突处理：开放地址法（线性探测、二次探测）、链地址法 - 装填因子 = n/m，影响查找效率 - 开放地址法探测序列：h(key) = (h0 + f(i)) % m --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [《算法与数据结构考研试题精析》笔记(9) - 集合 | Lee's Blog] `O(logn)` `O(n)` 完全二叉树一定是AVL树。 这种命题，颇有争议。争议地纠结点在于“AVL树是否是BST”。如果AVL树的本质是BST，那么完全树不一定是AVL树；否则，完全二叉树一定是AVL树。 这里以Leetcode上的说法，认为AVL树仅与平衡因子BF有关。 （王道的数据结构中认为AVL树的本质是BST；清华的数据结构中没有明确表述，其将平衡的二叉搜索树称为BBST） 设高为h的m阶B树上共有k个关键字，则其叶子结点有k+1个。 具有n个关键字的B树的查找路径长度不会大于the max BST of B the max BST of B B树的高度包括叶子结点 **典型真题摘录：** 1. [数据结构：AVL树，B树，B+树，红黑树 - 小夏coding - 博客园] 规则 （1）排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则； （2）子节点数：非叶节点的子节点数>1，且<=M ，且M>=2，空树除外（注：M阶代表一个树节点最多有多少个查找路径，M=M路,当M=2则是2叉树,M=3则是3叉）； （3）关键字数：枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个（注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2); （4）所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子; 最后我们用一个图和一个实际的例子来理解B树（这里为了理解方便我就直接用实际字母的大小来排列C>B>A）在这里插入图片描述 在这里插入图片描述 B树查询流程 如上图我要从上图中找到E字母，查找流程如下 （1） 2. [2025 年 408 真题 | 计算机考研杂货铺] ##### 7 已知查找表中有 400 个元素，查找元素概率相同。采用分块查找法且均匀分块。若采用顺序查找法确定元素所在块，且块内也采用顺序查找法，为效率最高，每块包含元素应为（ ）。 数组查找 分块查找 正确答案：C 设块大小为 m ，块数为 mn​ 。查找复杂度为 O(n/m+m) 。 根据高中数学的知识可以得知， m=n​=20 时，查找复杂度最低，所以 m=20 。 ##### 8 给 7 个不同的关键字，能够构成不同 4 阶 B 树的个数为（ ）。 正确答案：C 树高为 3：每个节点内关键字个数最少取 1 时，B 树 高度为 3（类似满二叉树）——仅一种结构； 树高为 2: + 根节点关键字个数取 1，第二层两节点关键字个数均取 3——一种结构； + 根节点关键字个数取 2，则第二层内三个节点关键字个数分别可取 221、212、122、311 3. [2013年408真题数据结构篇 - 知乎专栏] 本题要求模拟平衡二叉树（AVL树）的插入过程。 将AVL树调整平衡的方法主要有旋转法和中序遍历法。 旋转法. 观察插入不平衡结点的在 --- ============================================================ 📅 学习时间：2026-05-07 22:00:01 🏷️ 知识点ID：ds_04 (MD5: 0fd8e00c) ============================================================ ### 图遍历：DFS与BFS及其应用 **核心概念** - BFS（广度优先）：用队列，按层次遍历 - DFS（深度优先）：用栈（或递归），先深后广 - 时间复杂度：邻接表O(V+E)，邻接矩阵O(V2) **易错点** 1. BFS计算最短路径（无权图）：首次到达即为最短 2. DFS生成树/森林：同一强连通分量的顶点可通过DFS访问 3. 邻接矩阵空间复杂度O(V2)，适合稠密图 **应用** - BFS：最短路径（无权）、拓扑排序（Kahn算法） - DFS：拓扑排序（基于DFS的逆序）、强连通分量（Kosaraju） **典型题目** 拓扑排序算法（Kahn）： 1. 计算所有顶点入度 2. 将入度为0的顶点入队 3. 不断出队，删除边，更新入度 4. 若输出顶点数为V，则无环；否则有环 时间复杂度：O(V+E) --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [408数据结构复习框架二（树与二叉树、图），含近十年考研真题] 8.4图的应用（最小生成树、最短路径、拓扑排序、拓扑排序）. （1）最小生成树. 性质：最小生成树的树形不唯一；其对应的边的权值之和总是唯一的，而且是 2. [考研408核心知识体系与备考策略深度解析] # 考研408核心知识体系与备考策略深度解析 简介：本文系统梳理计算机专业考研408科目（数据结构、计算机组成原理、操作系统、计算机网络）的核心知识框架，结合历年真题分析命题规律，提供分阶段备考方案及高效复习技巧，助力考生构建完整知识体系。 ### 一、考研408科目构成与命题特点 计算机专业基础综合（408）作为全国统考科目，涵盖数据结构（45分）、计算机组成原理（45分）、操作系统（35分）、计算机网络（25分）四大模块，总分150分。其命题呈现三大特征：知识点覆盖广、题型灵活多变、强调综合应用。 以2023年真题为例，数据结构部分通过”平衡二叉树构建与遍历”综合题，同时考察树结构 **典型真题摘录：** 1. [C 408—《数据结构》图、查找、排序专题考点（含解析）] 408考研——《数据结构》图，查找和排序专题考点选择题汇总（含解析） ... [2010真题] 对下图进行拓扑排序，可得不同拓扑序列的个数是(B)。 image 2. [王道408历年真题讲解] 【已完结】计算机408考研官方版09-25年真题全套逐. 290.1万 3.2万. 62:44:43. 百 ... 【2027王道计算机408】2027考研计算机王道408领学班数据结构. 3.6万 0. 142:45:38. 3. [考研408数据结构第六章——图（含应用）] （4）逆拓扑排序：和拓扑正好相反，先找出度为0的顶点，每次去掉该顶点已经射入该 ... 五、408真题. 2009年（选择1）. （2分）下列关于无向连通图特性的叙述中 --- ============================================================ 📅 学习时间：2026-05-08 06:00:01 🏷️ 知识点ID：ds_01 (MD5: b5c14b1f) ============================================================ ### 时间复杂度与空间复杂度分析 **核心概念** - 时间复杂度：算法执行次数与问题规模的渐近关系 - 空间复杂度：算法所需存储空间与问题规模的渐近关系 - 常用记号：O(1)、O(log n)、O(n)、O(n log n)、O(n2)、O(n3)、O(2n)、O(n!) **易错点** 1. 混淆O(n)和O(2n)：系数不重要，渐近上界只看最高次项 2. 递归算法空间复杂度：递归深度×每次递归的局部变量大小 3. 最好/最坏/平均复杂度：不要把三者混淆 **典型题目** for (i = 0; i < n; i++) for (j = i; j < n; j++): pass # O(1)操作 分析：外层n次，内层分别为n, n-1, n-2...1，总和 = n(n+1)/2 = O(n2) --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [408考研数据结构复习-时间复杂度与空间复杂度-附统考真题-阿里云开发者社区] 你好，我是AI助理，可以解答问题、推荐解决方案等 头像 菜单 热门 # 408考研数据结构复习-时间复杂度与空间复杂度-附统考真题 ## 文章目录 一、时间复杂度 二、空间复杂度 三、相关题目 ## 一、时间复杂度 一个语句的频度是指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记为T(n)，它是该算法问题规模n的函数，时间复杂度主要分析T(n)的数量级。算法中基本运算（最深层循环内的语句）的频度与T(n)同数量级，因此通常采用算法中基本运算的频度f(n)来分析算法的时间复杂度。因此，算法的时间复杂度记为T(n)=O(f(n))。 式中，O的含义是T(n)的数量级 **典型真题摘录：** 1. [2021-考研-数据结构考研真题及其答案一、选择题 1. 算法的计算量的大小称为计算的（ B ）。【北京邮电大学2000 - 掘金] 6．数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度【北京理工大学 2001 七、1（2分）】 7. 数据结构是研讨数据的\_逻辑结构和物理结构，以及它们之间的相互关系，并对与这种结构定义相应的操作（运算），设计出相应的算法。【西安电子科技大学 1998 二、2（3分）】 8． 一个算法具有5个特性: （1）有穷性 （2）确定性 （3）可行性，有零个或多个输入、有一个或多个输出。 【华中理工大学 2000 一、2（5分）】 【燕山大学 1998 一、2（5分）】 9．已知如下程序段 FOR i:= n DOWNTO 1 DO {语句1} BEGIN x:=x+1； {语句2} FOR j:=n DOWNTO i DO {语句3} y:=y+1; {语句4} END； 语句1执行的频度为 n+1 ；语句2执行的频度为n；语句3执行的频度为n(n+3)/2； 2. [时间复杂度练习题python 时间复杂度例题 - 51CTO博客] 时间复杂度练习题python 时间复杂度例题，前言题目主要是选取自408考研真题、《数据结构（C语言版）》严蔚敏编著的教材课后习题、王道习题等。 3. [王道408历年真题讲解] 【已完结】计算机408考研官方版09-25年真题全套逐. 290.1万 3.2万. 62:44:43. 百 ... 【2027王道计算机408】2027考研计算机王道408领学班数据结构. 3.6万 0. 142:45:38. --- ============================================================ 📅 学习时间：2026-05-08 14:00:01 🏷️ 知识点ID：ds_05 (MD5: 98057d4b) ============================================================ ### 查找算法：二分、平衡二叉树、散列表 **二分查找** - 条件：有序顺序表 - 时间复杂度：O(log n) - 易错：边界条件，mid = left + (right - left) // 2 **平衡二叉树（AVL）** - 定义：左右子树高度差绝对值小于等于1 - 旋转操作：LL（右单旋）、RR（左单旋）、LR（先左后右双旋）、RL（先右后左双旋） - 插入：先 BST 插入，再调整平衡因子 **B树与B+树** - B树：多路平衡查找树，节点包含数据 - B+树：非叶子节点只含索引，所有数据在叶子 - MySQL索引用B+树（叶子链表便于范围查询） **散列表** - 冲突处理：开放地址法（线性探测、二次探测）、链地址法 - 装填因子 = n/m，影响查找效率 - 开放地址法探测序列：h(key) = (h0 + f(i)) % m --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [Awesome-408/数据结构/王道笔记/search-algorithm.md at master · amatureemoprince/Awesome-408 · GitHub] 需要说明的是：m 阶 B 树表示所有结点子树高度相同的 m 路平衡查找树（说 B 树就是默认 m 阶 B 树，只是后者显示表示其最多有 m 颗子树）。 平衡查找树 是一种 自平衡的、有序的树形数据结构，用于高效存储和检索数据。它在动态插入、删除操作后能自动调整结构，确保最坏情况下的时间复杂度保持为 O(log n) 常见的平衡查找树有：AVL、RBT、B 树。对于不同的平衡查找树会有不同的约束条件！ 简单解释一下： 对于 AVL ，约束条件是任意一颗结点的左右子树高度差不能相差 1。 对于这里的 B 树，约束条件是每个结点的子树高度相同，结点关键字个数和子树个数限制。 B 树的定义 2. [数据结构——四十、折半查找(王道408) - 教程 - tlnshuju - 博客园] 博客园logo 搜索 搜索 搜索 搜索 写随笔 我的博客 短消息 简洁模式 用户头像 # tlnshuju ## 数据结构——四十、折半查找(王道408) - 教程 #### 文章目录 ## 前言 本文介绍了折半查找（二分查找）的基本思想、实现方法和查找效率分析。折半查找仅适用于有序顺序表，通过不断缩小查找区间来定位目标元素。文章通过示例演示了查找成功和失败的流程，并提供了升序和降序排列时的C语言实现代码。在效率分析部分，通过构建判定树计算了成功和失败情况下的平均查找长度（ASL），指出折半查找判定树具有右子树结点数-左子树结点数=0或1的特性，且一定是平衡二叉树和二叉排序树。最后说 **典型真题摘录：** 1. [2025 年 408 真题 | 计算机考研杂货铺] ##### 7 已知查找表中有 400 个元素，查找元素概率相同。采用分块查找法且均匀分块。若采用顺序查找法确定元素所在块，且块内也采用顺序查找法，为效率最高，每块包含元素应为（ ）。 数组查找 分块查找 正确答案：C 设块大小为 m ，块数为 mn​ 。查找复杂度为 O(n/m+m) 。 根据高中数学的知识可以得知， m=n​=20 时，查找复杂度最低，所以 m=20 。 ##### 8 给 7 个不同的关键字，能够构成不同 4 阶 B 树的个数为（ ）。 正确答案：C 树高为 3：每个节点内关键字个数最少取 1 时，B 树 高度为 3（类似满二叉树）——仅一种结构； 树高为 2: + 根节点关键字个数取 1，第二层两节点关键字个数均取 3——一种结构； + 根节点关键字个数取 2，则第二层内三个节点关键字个数分别可取 221、212、122、311 2. [【已完结】2025考研数据结构全程班基础部分（适用于408与自命题）] 【已完结】2025考研数据结构全程班基础部分（适用于408与自命题） ... 7-2 线性表的查找; 7-3 二叉排序树与平衡二叉树; 7-4 B树与B+树; 7-5 红黑树; 7-6 并查集; 7-7 散列表 3. [2013年408真题数据结构篇 - 知乎专栏] 本题要求模拟平衡二叉树（AVL树）的插入过程。 将AVL树调整平衡的方法主要有旋转法和中序遍历法。 旋转法. 观察插入不平衡结点的在 --- ============================================================ 📅 学习时间：2026-05-08 22:00:01 🏷️ 知识点ID：ds_02 (MD5: 8ffc4851) ============================================================ ### 栈和队列的性质与扩展 **核心概念** - 栈：LIFO，先进后出；操作：push/pop/top - 队列：FIFO，先进先出；操作：enqueue/dequeue/front - 循环队列：避免假溢出，用(n+1)个空间区分满/空 **易错点** 1. 循环队列队空条件：front == rear 2. 循环队列队满条件：(rear + 1) % maxsize == front 3. 中缀表达式转后缀表达式时，栈中存放操作符，优先级低的运算符在前 **出栈序列判定定理** 对于入栈序列1,2,3...,n的输出序列：每个数字后面比它小的数字必须按**递减顺序**排列。例如：入栈1,2,3,4，若出栈序列为4,3,2,1，对于数字4后面比4小的{1,2,3}必须递减排列（3>2>1 ✓）。 **典型题目** 使用两个栈实现队列：stack_in用于入队，stack_out用于出队 - 入队：元素压入stack_in - 出队：如果stack_out不为空，弹出stack_out栈顶；否则把stack_in全部倒入stack_out 均摊时间复杂度：O(1) --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [考研408总结【数据结构】---栈和队列这是我参与11月更文挑战的第28天，活动详情查看：2021最后一次更文挑战 本篇 - 掘金] 稀土掘金 稀土掘金 # 考研408总结【数据结构】---栈和队列 这是我参与11月更文挑战的第28天，活动详情查看：2021最后一次更文挑战 考研倒计时：27天 ## 栈和队列 掌握好栈和队列的特点，进行一些相关推导即可。 具体知识点就不赘述了，主要提一下需要记忆的点。 首先常见的题型： 给出入栈序列，推导出栈序列个数，或者与队列结合。 `- 一般考虑手工推导即可 - n个不同元素进栈，出栈序列的个数为(1/n+1)Cn 2n` 循环队列（重点） if rear指向队尾元素的下一个，front指向队首元素。 `队满条件：(Q.rear+1)%MaxSize == Q 2. [解2022年408考研真题第1题-腾讯云开发者社区-腾讯云] ## 解2022年408考研真题第1题 # 解2022年408考研真题第1题 作者头像 ## 解2022年408考研真题第1题 2022年408考研真题第1题，考察了时间复杂度的计算方法。题目内容如下： 下列程序段的时间复杂度是（ ）。 `sum = 0; for (i = 1; i < n; i = 2) for (j = 0; j < i; j++) sum++;` A. B. C. D. 对于这个题目，一种比较简单的解法是设 为 的倍数，即找一个特例，如令 ，则 。从而确定基本语句 `sum++` 的频度。 `sum++` 这种求解方法，能够得到正确答案 **典型真题摘录：** 1. [考研408之栈与队列学习。 原创 - CSDN博客] 2009年至2020年的408考研真题与答案解析，对于备考的考生来说，是一份非常宝贵的学习资料。 首先，我们来看数据结构部分。数据结构是计算机科学的核心课程，它 2. [2026考研王道计算机408 - 小猿资源站] ... 栈-出栈 ... | ├──408考研真题及答案解析.zip 21.48M | ├──code.zip 16.06M | └──C／C 函数大全.chm 121.95kb ├──03.26考研王道计算机【数据结构考点精讲】 3. [408历年真题解析数据结构篇 - 知乎专栏] 408历年真题有非常强的继承关系，例如. 2019年题10考察了2014年题11中的快速排序中每一趟排序后的序列；; 2021年题2考察了2010年题2中的输出受限的双端队列可能的出队序列； --- ============================================================ 📅 学习时间：2026-05-09 06:00:01 🏷️ 知识点ID：ds_03 (MD5: 08662c02) ============================================================ ### 二叉树遍历与线索二叉树 **核心概念** - 先序遍历（DLR）：根-左-右 - 中序遍历（LDR）：左-根-右 - 后序遍历（LRD）：左-右-根 - 层序遍历：利用队列，层内从左到右 **易错点** 1. 已知两种遍历序列（包含中序），可唯一确定二叉树 2. 仅有先序+后序无法唯一确定（可确定祖先关系但不能确定结构） 3. 递归遍历时间复杂度O(n)，空间复杂度O(h)，h为树高 **线索二叉树** - 目的：加快遍历速度，避免递归/栈 - 规定：若无左孩子，指向前驱；若无右孩子，指向后继 - 需要ltag/rtag标志位区分孩子指针和线索指针 **典型题目** 已知先序序列：ABDECF，中序序列：DBEAFC，构建二叉树 1. 先序根A → 中序分 DBE | A | CF 2. 左子树先序：BDE，中序：DBE → B为左子树根 3. 右子树先序：CF，中序：CF → C为右子树根 4. 结果：A左子B(B左D右E)，A右子C(C左F) --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [考研408总结【数据结构】---树与二叉树（上）这是我参与11月更文挑战的第2天，活动详情查看：2021最后一次更文挑战 - 掘金] 稀土掘金 稀土掘金 # 考研408总结【数据结构】---树与二叉树（上） 这是我参与11月更文挑战的第2天，活动详情查看：2021最后一次更文挑战 考研倒计时：53天 参考资料： 王道数据结构考研复习指导 天勤数据结构高分笔记 本篇先总结树的基本概念和计算、二叉树的遍历和线索二叉树的内容。 下篇总结树和森林、以及应用（二叉排序树、平衡二叉树、哈夫曼树）的内容。 ## 树的性质 树的结点数等于所有结点的度数加1. 度为m的树中第i层上至多有mi−1m^{i-1}mi−1个结点（i>=1) 高度为h，度为m的树【度为m的树指的是结点最多有m个孩子结点】至多有mh−1m−1\fr 2. [王道计算机考研 数据结构_哔哩哔哩_bilibili] 5.3.2\_2\_二叉树的线索化 19:25 5.3.2\_3\_在线索二叉树中找前驱后继 18:19 5.4.1 树的存储结构 19:29 5.4.2 树、森林与二叉树的转换 14:51 5.4.3 树和森林的遍历 11:09 5.5.1\_哈夫曼树 17:38 5.5.2\_1\_并查集 32:13 5.5.2\_2\_并查集的进一步优化 10:17 6.1.1\_图的基本概念 30:39 6.2.1\_邻接矩阵法 15:38 6.2.2\_邻接表法 06:53 6.2.3+6.2.4\_十字链表、邻接多重表 12:40 6.2.5\_图的 3. [25王dao408__数据结构Anki选择题【高效刷题版】Anki中文资源网] 1一、绪论 1.1.3数据结构的基本概念 5 1.2.3算法和算法评价 16 21 2二、线性表 2.1.3线性表的定义和基本操作 4 2.2.3线性表的顺序表示 15 2.3.7线性表的链式表示 35 54 3三、栈，队列和数组 3.1.4栈 31 3.2.5队列 24 3.3.6栈和队列的应用 18 3.4.5数组和特殊矩阵 16 89 4四、串 4.2.4串的模式匹配 11 11 5五、树与二叉树 5.1.4树的基本概念 10 5.2.3二叉树的概念 28 5.3.3二叉树的遍历和线索二叉树 43 5.4.4树、森林 **典型真题摘录：** 1. [王道计算机考研团队整理 22考研408真题及答案 | PDF] Scribd # 王道计算机考研团队整理 22考研408真题及答案 王道计算机考研团队整理 22考研408真题及答案 ## Uploaded by AI-enhanced title and description # 王道计算机考研团队整理 22考研408真题及答案 这是一道判断二叉树是否为二叉搜索树的题目。题目要求使用C或C++语言描述一个高效算法。答案提供了算法的基本设计思想是利用中序遍历判断是否为升序序列,并使用递归方式实现中序遍历算法,关键步骤使用注释进行说明。 # 王道计算机考研团队整理 22考研408真题及答案 王道计算机考研团队整理 22考研408真题及答案 ## Uploaded by AI-enhanced title and description ## Share this document ## Footer menu ## About 2. [分享｜在力扣备战考研数据结构 - 讨论 - 力扣（LeetCode）] # 分享｜在力扣备战考研数据结构 - 讨论 - 力扣（LeetCode） （by 天赐细莲） 408历年真题数据结构算法大题题源一览 - 知乎 107 14 481 评论 (14) 排序:最热 评论 1 2 探索 #技术交流 Image 36: jared-62 Image 37: loving-blackvvellbqn Image 38: zhong-mo-f1 准大一计算机工程新生求助 分享｜暂时退坑了，力扣 #学习分享 Image 39: jolly-hermanntth Image 40: you-min-k Image 41: aoyama_nanami 分享｜1000 题打卡 分享｜上瓜了😭😭😭 #求职面试 Image 42: adoring-visvesvarayaeop Image 43: xenodochial-ellis1pj I 3. [2025年王道计算机4082025年计算机408考研核心考点全梳理与备考策略 一、408考试科目与核心特点 计算机考研4 - 掘金] 稀土掘金 稀土掘金 # 2025年王道计算机408 ### 2025年计算机408考研核心考点全梳理与备考策略 #### 一、408考试科目与核心特点 计算机考研408涵盖四大核心科目：数据结构与算法（45分）、计算机组成原理（45分）、操作系统（35分）、计算机网络（25分）。其特点是： #### 二、各科目核心考点与复习重点 1. 数据结构与算法 2. 计算机组成原理 3. 操作系统 4. 计算机网络 #### 三、高效备考策略与资源推荐 分阶段复习 学习方法 必备资料 #### 四、常见误区与避坑指南 总结：408备考需系统规划、注重逻辑串联，建议以王道课程为核心，结合真题反复迭代。掌握高频考点（如线性表算法、补码运算）的同时，强化综合应用能力（如系统调用流程、Cache命中率计算）。 avatar 创作等级LV.2 --- ============================================================ 📅 学习时间：2026-05-09 10:00:01 🏷️ 知识点ID：ds_02 (MD5: 8ffc4851) ============================================================ ### 栈和队列的性质与扩展 **核心概念** - 栈：LIFO，先进后出；操作：push/pop/top - 队列：FIFO，先进先出；操作：enqueue/dequeue/front - 循环队列：避免假溢出，用(n+1)个空间区分满/空 **易错点** 1. 循环队列队空条件：front == rear 2. 循环队列队满条件：(rear + 1) % maxsize == front 3. 中缀表达式转后缀表达式时，栈中存放操作符，优先级低的运算符在前 **出栈序列判定定理** 对于入栈序列1,2,3...,n的输出序列：每个数字后面比它小的数字必须按**递减顺序**排列。例如：入栈1,2,3,4，若出栈序列为4,3,2,1，对于数字4后面比4小的{1,2,3}必须递减排列（3>2>1 ✓）。 **典型题目** 使用两个栈实现队列：stack_in用于入队，stack_out用于出队 - 入队：元素压入stack_in - 出队：如果stack_out不为空，弹出stack_out栈顶；否则把stack_in全部倒入stack_out 均摊时间复杂度：O(1) --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [考研408总结【数据结构】---栈和队列这是我参与11月更文挑战的第28天，活动详情查看：2021最后一次更文挑战 本篇 - 掘金] 稀土掘金 稀土掘金 # 考研408总结【数据结构】---栈和队列 这是我参与11月更文挑战的第28天，活动详情查看：2021最后一次更文挑战 考研倒计时：27天 ## 栈和队列 掌握好栈和队列的特点，进行一些相关推导即可。 具体知识点就不赘述了，主要提一下需要记忆的点。 首先常见的题型： 给出入栈序列，推导出栈序列个数，或者与队列结合。 `- 一般考虑手工推导即可 - n个不同元素进栈，出栈序列的个数为(1/n+1)Cn 2n` 循环队列（重点） if rear指向队尾元素的下一个，front指向队首元素。 `队满条件：(Q.rear+1)%MaxSize == Q 2. [GitHub - lanlankaoyanshan/408Bester: 这里有着计算机考研408的详细路线，每个月的学习规划和所有视频书籍资源，计算机考研必看仓库 · GitHub] 王道22年思维导图 ### 408 计算机考研书籍合集 下面有对应408书籍的详细说明，部分书籍主要针对非科班和高分的同学。PDF也整理好了，大家去下面加我wx即可。 | 书籍 | | --- | | 数据结构 | 大话数据结构 | | 操作系统 | 程序是怎么跑起来的 | | 计算机组成原理 | 计算机系统基础 计算机组成与系统结构呢 | | 计算机网络 | 网络是怎么连接的 | ### 408视频教程推荐 下面有对应视频的详细说明，部分视频主要针对非科班和高分的同学。 ### 408历年真题无水印清晰版 这里感谢几位同学的分享，之前忘记记录是哪位朋友圈的童鞋分享的，大家可 3. [408 复习路径（非科班必看） - 编程导航] 《操作系统》：王道计算机考研 操作系统\_哔哩哔哩\_bilibili 《计算机网络》：王道计算机考研 计算机网络\_哔哩哔哩\_bilibili ### 复习阶段安排 #### 第一轮 基础（3-7 月） 采用看一节王道视频，然后刷这一节王道书。教材作为辅助，当遇到不会的知识才去翻阅教材。王道书的选择题和大题都要做，重点和难点的地方要做标记，错题要标记好，更要思考为什么会出错。数据结构复习的时候建议记笔记，其他三科不要求，笔记可以作为以后查漏补缺之用。第一轮把每个知识点都要弄懂。 #### 第二轮 强化（8-9 月） 对王道书进行二刷。这一轮是熟能生巧的过程，重点和难点知识在这一 **典型真题摘录：** 1. [408历年真题解析数据结构篇 - 知乎专栏] 408历年真题有非常强的继承关系，例如. 2019年题10考察了2014年题11中的快速排序中每一趟排序后的序列；; 2021年题2考察了2010年题2中的输出受限的双端队列可能的出队序列； 2. [24考研计算机王道408网课分享（数据结构/组成原理/操作系统/计算机 ...] 数据结构10题分析题主要考察的是线性表和树中的算法设计和实现，基本上每年都会在这两个部分出题。在大家复习的过程中，要重点学习这两个部分。 线性表部分，建议大家优先学习 3. [深入解析：《考研408数据结构》第三章（3.1 栈）复习笔记 - wzzkaifa - 博客园] 博客园logo 搜索 搜索 搜索 搜索 写随笔 我的博客 短消息 简洁模式 用户头像 返回主页 # wzzkaifa ## # 深入解析：《考研408数据结构》第三章（3.1 栈）复习笔记 前提提要： 基于数据结构我个人大一学过，而且我也一直认为是408里最容易的，故而我一直拖到很晚才开，视频也没看，直接加速用【思维导图】+【例题】极限回顾复习，因此我也默认大部分人都是很早就学完了数据结构，所以该数据结构系列笔记只适用于非初学者的框架回顾复习，不再解释简单知识点概念。 ； 【另外关于：栈】 通过网上许多大佬、博主都总结了，【栈】和【队列】出的代码题本来就少能够说就没有，那么代码理解这块我将不再深究，反正知道逻辑会做【选择题】应该就够了 ## 一、栈的基本概念 ### 思维导图（放大保存可打印） ### 稍微讲解 大家都会我就不说什么了，如何定义说白了就是————【 --- ============================================================ 📅 学习时间：2026-05-09 18:00:01 🏷️ 知识点ID：ds_01 (MD5: b5c14b1f) ============================================================ ### 时间复杂度与空间复杂度分析 **核心概念** - 时间复杂度：算法执行次数与问题规模的渐近关系 - 空间复杂度：算法所需存储空间与问题规模的渐近关系 - 常用记号：O(1)、O(log n)、O(n)、O(n log n)、O(n2)、O(n3)、O(2n)、O(n!) **易错点** 1. 混淆O(n)和O(2n)：系数不重要，渐近上界只看最高次项 2. 递归算法空间复杂度：递归深度×每次递归的局部变量大小 3. 最好/最坏/平均复杂度：不要把三者混淆 **典型题目** for (i = 0; i < n; i++) for (j = i; j < n; j++): pass # O(1)操作 分析：外层n次，内层分别为n, n-1, n-2...1，总和 = n(n+1)/2 = O(n2) --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [GitHub - anbingxu666/WangDao-DataStructure: 《数据结构》经典算法代码 · GitHub] `.cpp` ### 使用方法1（推荐） 在线阅读，学习代码思想，手写 ### 使用方法2（推荐） ### 使用方法3 导入Clion工程，手动更改Makefile ### 使用方法4 大佬qing自行研究😊 ## 线性表 本章是考试重点容易出算法大题 2019 9 14 课后算法题更新到7道，对于2020王道数据结构第18页 链表的直接插入排序 2019 9 18 ## 栈 ## 队列 ## 树 🌲的考察在于各种树的特点，以及树的遍历算法 ### 平衡二叉树 ## 图 ### 遍历问题 ### 最小生成树问题 ### 最短路径问题 ### 拓扑排序 **典型真题摘录：** 1. [Awesome-408/数据结构/王道笔记/time-and-space-complexity.md at master · amatureemoprince/Awesome-408 · GitHub] 值得说明的是：在使用时间复杂度时总是使用最坏的或者平均的，而不会使用最好的，因为我们总要把最坏的情况考虑到而不会是最好的情况，这样才能知道自己是否能接受这个结果从而进行取舍。 ### 常见时间复杂度排序 我们来给常见的时间复杂度从小到大排个序： O(1) < O($\log\_2 n$) < O(n) < O(n \ $\log\_2 n$) < O($2^n$) < O(n!) :::tip 注意 O($2^n$) < O(n!)是n在大于4的情况下！ ::: ## 空间复杂度 空间复杂度，顾名思义是在程序运行时需要额外空间与输入规模之间的关系，这个概念是和时间复杂度非常类似。 可以看到这个使用的空间与n的输入大小无关，故空间复杂度为O(1)。 其余的就不在这里举例了。如果有想了解其他空间复杂度的同学可以访问hello算法 ## 总结 在计算时间复杂度时要紧紧抓住运算代码 2. [两种套路搞定所有时间复杂度408真题_哔哩哔哩_bilibili] 13-Ch3真题精讲2 23:31 14-Ch3存储管理-知识点3（一网打尽磁盘知识点） 46:26 15-Ch3真题精讲3（计组OS涉及到磁盘的所有真题） 26:04 32-计组终结（你我意念合一，多总结复盘） 19:13 （分割线）以下为操作系统试听课程 17:19 00-OS备考思路和学习方法 11:43 05-Ch2进程与线程（一节课搞定基础知识点） 53:45 07-Ch2进程与线程（进程调度算法大汇总） 29:46 25考研408操作系统终结课！恭喜你已建立好框架，拿捏408真题 19:31 25考研408数据结构刷题班规划课 10:08 408考研数据结构代码题的「舍与得」—如何备考算法题 13:49 两种套路搞定所有时间复杂度408真题 16:53 王道2027版数据结构习题讲解 王道计算机教育 579.7万 2.4万 3. [408考研数据结构复习-时间复杂度与空间复杂度-附统考真题-阿里云开发者社区] ### 探索云世界 #### 热门 #### 云计算 #### 大数据 #### 云原生 #### 人工智能 #### 数据库 #### 开发与运维 ### 活动广场 丰富的线上&线下活动，深入探索云世界 #### 任务中心 做任务，得社区积分和周边 #### 训练营 资深技术专家手把手带教 #### 直播 技术交流，直击现场 #### 乘风者计划 让创作激发创新 ### 下载 海量开发者使用工具、手册，免费下载 #### 镜像站 极速、全面、稳定、安全的开源镜像 #### 技术资料 开发手册、白皮书、案例集等实战精华 热门 # 408考研数据结构复习-时间复杂度与空间复杂度-附统考真题 ### 为什么选择阿里云 ### 大模型 ### 产品和定价 ### 技术内容 ### 权益 ### 服务 ### 关注阿里云 关注阿里云 --- ============================================================ 📅 学习时间：2026-05-10 02:00:02 🏷️ 知识点ID：ds_03 (MD5: 08662c02) ============================================================ ### 二叉树遍历与线索二叉树 **核心概念** - 先序遍历（DLR）：根-左-右 - 中序遍历（LDR）：左-根-右 - 后序遍历（LRD）：左-右-根 - 层序遍历：利用队列，层内从左到右 **易错点** 1. 已知两种遍历序列（包含中序），可唯一确定二叉树 2. 仅有先序+后序无法唯一确定（可确定祖先关系但不能确定结构） 3. 递归遍历时间复杂度O(n)，空间复杂度O(h)，h为树高 **线索二叉树** - 目的：加快遍历速度，避免递归/栈 - 规定：若无左孩子，指向前驱；若无右孩子，指向后继 - 需要ltag/rtag标志位区分孩子指针和线索指针 **典型题目** 已知先序序列：ABDECF，中序序列：DBEAFC，构建二叉树 1. 先序根A → 中序分 DBE | A | CF 2. 左子树先序：BDE，中序：DBE → B为左子树根 3. 右子树先序：CF，中序：CF → C为右子树根 4. 结果：A左子B(B左D右E)，A右子C(C左F) --- ### 🔍 考研真题相关定理与技巧 **典型真题摘录：** 1. [【王道数据结构】《王道数据结构》课后代码题汇总 - 梁君牧 - 博客园] #### 4.1.16 写出在中序线索二叉树里查找指定结点在后序的前驱结点的算法。 `/ 算法思想：在后序序列中，若结点p有右子女，则右子女是其前驱，若无右子女而有左子女，则左子女是其前驱。若结点p左、右子女均无，设其中序左线索指向某祖先结点f（p是f右子树中按中序遍历的第一个结点），若f有左子女，则其左子女是结点p在后序下的前驱;若f无左子女，则顺其前驱找双亲的双亲，一直找到双亲有左子女（这时左子女是p的前驱）。还有一种情况，若p是中序遍历的第一个结点，则结点p在中序和后序下均无前驱。 / BiThrTree InPostPre(BiThrTree t,BiThrTree p){ BiThrTree q; if(p->rtag == 0) //若p有右子女，则右子女是其后序前驱 q = p->rchild; else if(p->ltag ==0) //若p只有左子女，左子女是其后序前 2. [王道计算机考研团队整理 22考研408真题及答案 | PDF] Scribd # 王道计算机考研团队整理 22考研408真题及答案 王道计算机考研团队整理 22考研408真题及答案 ## Uploaded by AI-enhanced title and description # 王道计算机考研团队整理 22考研408真题及答案 这是一道判断二叉树是否为二叉搜索树的题目。题目要求使用C或C++语言描述一个高效算法。答案提供了算法的基本设计思想是利用中序遍历判断是否为升序序列,并使用递归方式实现中序遍历算法,关键步骤使用注释进行说明。 # 王道计算机考研团队整理 22考研408真题及答案 王道计算机考研团队整理 22考研408真题及答案 ## Uploaded by AI-enhanced title and description ## Share this document ## Footer menu ## About 3. [2020年计算机408统考真题] . 将 一 个 1 x1 对称 矩阵” 上 三 角 分的元素叫力 （ 1WZW/W1 按列优先存入 C 语 言 的 一维数组 N 中，元素加 7,2 在 N 中的 下 标是（）。 A. 1 5 B. 1 6 C. 22 D. 2 3 2. 对空栈 S 进 行 Push 和 Pop 操 作， 栈序列为 , b, c, d, e, 经 过 Push, Push, Pop, Push, Pop, Push,Pus h, P op 操作 后得 到的 出栈 序列 是（）。 A. b, , c B. b, , e C. b, c, D. b, c, e 3. 对于任意一棵高度为 5 且 有 1 个结点的二叉树，若采用顺序存储结构保存，每 个 结 点 占 1 个 存 储 单 元（仅存 --- ============================================================ 📅 学习时间：2026-05-10 10:00:01 🏷️ 知识点ID：ds_04 (MD5: 0fd8e00c) ============================================================ ### 图遍历：DFS与BFS及其应用 **核心概念** - BFS（广度优先）：用队列，按层次遍历 - DFS（深度优先）：用栈（或递归），先深后广 - 时间复杂度：邻接表O(V+E)，邻接矩阵O(V2) **易错点** 1. BFS计算最短路径（无权图）：首次到达即为最短 2. DFS生成树/森林：同一强连通分量的顶点可通过DFS访问 3. 邻接矩阵空间复杂度O(V2)，适合稠密图 **应用** - BFS：最短路径（无权）、拓扑排序（Kahn算法） - DFS：拓扑排序（基于DFS的逆序）、强连通分量（Kosaraju） **典型题目** 拓扑排序算法（Kahn）： 1. 计算所有顶点入度 2. 将入度为0的顶点入队 3. 不断出队，删除边，更新入度 4. 若输出顶点数为V，则无环；否则有环 时间复杂度：O(V+E) --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [408数据结构复习框架二（树与二叉树、图），含近十年考研真题] 8.4图的应用（最小生成树、最短路径、拓扑排序、拓扑排序）. （1）最小生成树. 性质：最小生成树的树形不唯一；其对应的边的权值之和总是唯一的，而且是 2. [考研408核心知识体系与备考策略深度解析] # 考研408核心知识体系与备考策略深度解析 简介：本文系统梳理计算机专业考研408科目（数据结构、计算机组成原理、操作系统、计算机网络）的核心知识框架，结合历年真题分析命题规律，提供分阶段备考方案及高效复习技巧，助力考生构建完整知识体系。 ### 一、考研408科目构成与命题特点 计算机专业基础综合（408）作为全国统考科目，涵盖数据结构（45分）、计算机组成原理（45分）、操作系统（35分）、计算机网络（25分）四大模块，总分150分。其命题呈现三大特征：知识点覆盖广、题型灵活多变、强调综合应用。 以2023年真题为例，数据结构部分通过”平衡二叉树构建与遍历”综合题，同时考察树结构 **典型真题摘录：** 1. [C 408—《数据结构》图、查找、排序专题考点（含解析）] 408考研——《数据结构》图，查找和排序专题考点选择题汇总（含解析） ... [2010真题] 对下图进行拓扑排序，可得不同拓扑序列的个数是(B)。 image 2. [考研408数据结构第六章——图（含应用）] （4）逆拓扑排序：和拓扑正好相反，先找出度为0的顶点，每次去掉该顶点已经射入该 ... 五、408真题. 2009年（选择1）. （2分）下列关于无向连通图特性的叙述中 3. [计算机考研408真题解析（2024-41 有向图拓扑序列唯一性判定算法 ...] 摘要：本文深入剖析2024年计算机考研408数据结构真题（题目ID：2024-DS-41），该题以载人航天工程为背景，要求设计算法判断有向图是否存在唯一的拓扑序列。我们 --- ============================================================ 📅 学习时间：2026-05-10 18:00:01 🏷️ 知识点ID：ds_05 (MD5: 98057d4b) ============================================================ ### 查找算法：二分、平衡二叉树、散列表 **二分查找** - 条件：有序顺序表 - 时间复杂度：O(log n) - 易错：边界条件，mid = left + (right - left) // 2 **平衡二叉树（AVL）** - 定义：左右子树高度差绝对值小于等于1 - 旋转操作：LL（右单旋）、RR（左单旋）、LR（先左后右双旋）、RL（先右后左双旋） - 插入：先 BST 插入，再调整平衡因子 **B树与B+树** - B树：多路平衡查找树，节点包含数据 - B+树：非叶子节点只含索引，所有数据在叶子 - MySQL索引用B+树（叶子链表便于范围查询） **散列表** - 冲突处理：开放地址法（线性探测、二次探测）、链地址法 - 装填因子 = n/m，影响查找效率 - 开放地址法探测序列：h(key) = (h0 + f(i)) % m --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [408考研之数据结构的查找——查找的概念&顺序查找_数据结构查找王道408-CSDN博客] 最新推荐文章于 2026-01-13 14:48:24 发布. 于 2023-05-22 09:42:20 发布. CC 4.0 BY-SA版权. 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。. 平均查找长度ASL(Average Search Length)——所有查找过程中，进行关键字比较次数的平均值（个人理解：一般是用查找到该关键字通过的次数除以表长）。. 一个不重要的王道上的知识点：ASL的数量级反应了查找算法时间复杂度。（了解即可，不了解也行，于考试无卵用）. 需要关注的是，顺序查找可从前往后，此为传统思想；也可使用哨兵，即 2. [【考研408数据结构-10】 查找算法（上）：线性查找与树形查找_408考二叉搜索树吗-CSDN博客] 最新推荐文章于 2026-01-12 17:53:06 发布. 于 2025-08-21 07:00:00 发布. CC 4.0 BY-SA版权. 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。. * **主关键字** vs **次关键字**：主关键字唯一标识一个记录，次关键字可能对应多个记录. * **内查找** vs **外查找**：内查找的数据全部在内存，外查找需要访问外存. 过程：3(×) → 5(×) → 2(×) → 8(✓) 找到！. int SeqSearch(int arr[], int n, int key) {. 3. [《算法与数据结构考研试题精析》笔记(9) - 集合 | Lee's Blog] 完全二叉树一定是AVL树。 > 这种命题，颇有争议。争议地纠结点在于“AVL树是否是BST”。如果AVL树的本质是BST，那么完全树不一定是AVL树；否则，完全二叉树一定是AVL树。 这里以Leetcode上的说法，认为AVL树仅与平衡因子BF有关。 （王道的数据结构中认为AVL树的本质是BST；清华的数据结构中没有明确表述，其将平衡的二叉搜索树称为BBST） 设高为h的m阶B树上共有k个关键字，则其叶子结点有k+1个。 具有n个关键字的B树的查找路径长度不会大于the max BST of B B树的高度包括叶子结点那一层。 > 清华教材上为此说法。也有不包含叶子层的说法。 【2 4. [第9章 检索 - B站-水论文的程序猿 - 博客园] 有数据 \({53，30，37，12，45，24，96}\) ，从空二叉树开始逐步插入数据形成二叉排序树，若希望高度最小，则应该选择下列的序列输入，答案 \(37,24,12,30,53,45,96\) 由于给定的是一个关键字有序序列 \(a[start\ldots{end}]\)，让其中间位置的关键字 \(a[mid]\) 作为根结点 左序列 \(a[start\dots{mid-1}]\) 构造左子树 右序列 \(a[mid+1\ldots{end}]\) 构造右子树 3. 若在 \(9\) 阶 B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为 \(8\ **典型真题摘录：** 1. [考研系列-408真题数据结构篇(10-17)_408数据结构真题-CSDN博客] ## # 2012年 ### 1.图的广度优先遍历 ### 2.邻接矩阵存储有向图，拓扑排序 不唯一的意思是这个图可能存在的拓扑序列是不唯一的。而不是说代码按照邻接矩阵找到的拓扑序列是唯一的，这个和图的不同结构(邻接矩阵、邻接表)遍历区分开。 注：有向无环图一定存在拓扑序列，题目中问的是存不存在拓扑序列，和拓扑序列是否唯一。 ### 3.B树的删除操作 ### 4.最小生成树 (1)Prim算法：从某一顶点开始构建生成树，每次将距离这棵树代价最小的新顶点纳入生成树 (2)Kruskal算法：每次选择一条权值最小的边使这条边的两头连通(原本连通的不选)，直到所有结点都连通；判断两个顶点是否属于一个集合，可以使用并查集来实现，并查集搜索时间复杂度:log_2E log_2E ## # 2013年 ### 1.时间复杂度计算 O(m+n)=O(max(m,n)) ### 2. [408数据结构考察范围 | 考研数据结构笔记] 📒 `⌘Ctrl``k` # 408数据结构考察范围 ## 考察目标 1. 掌握数据结构的基本概念、基本原理和基本方法 2. 掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析 3. 能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力 ## 一、线性表 ### （一）线性表的基本概念 ### （二）线性表的实现 1. 顺序存储 2. 链式存储 3. 线性表的应用 ## 二、栈、队列和数组 ### （一）栈和队列的基本概念 ### （二）栈和队列的顺序存储结构 ### （三）栈和队列的链式存储结构 ### （四）栈、队列和数组的应用 ### （五）特殊矩阵的压缩存储 ### （六）多维数组的存储 ## 三、树与二叉树 ### （一）树的基本概念 ### （二）二叉树 3. [数据结构练习题（灰灰考研）] 2014期末考试试题 (答案) B树Image 79 No ratings yet 2014期末考试试题 (答案) B树 10 pages 3900f945f4dec37e0c79dc79b61 7D420578 1F400Image 80 No ratings yet 3900f945f4dec37e0c79dc79b61 7D420578 1F400 5 pages Tango Etudes No 3, 4, 5, 1Image 81 No ratings yet Tango Etudes No 3, 4, 5, 1 6 pages 数据查找Image 82 No ratings yet 数据查找 16 pages 《计算机系统结构》2014年10月《计算机系统结构》真题Image 83 No rati --- ============================================================ 📅 学习时间：2026-05-10 22:00:01 🏷️ 知识点ID：ds_02 (MD5: 8ffc4851) ============================================================ ### 栈和队列的性质与扩展 **核心概念** - 栈：LIFO，先进后出；操作：push/pop/top - 队列：FIFO，先进先出；操作：enqueue/dequeue/front - 循环队列：避免假溢出，用(n+1)个空间区分满/空 **易错点** 1. 循环队列队空条件：front == rear 2. 循环队列队满条件：(rear + 1) % maxsize == front 3. 中缀表达式转后缀表达式时，栈中存放操作符，优先级低的运算符在前 **出栈序列判定定理** 对于入栈序列1,2,3...,n的输出序列：每个数字后面比它小的数字必须按**递减顺序**排列。例如：入栈1,2,3,4，若出栈序列为4,3,2,1，对于数字4后面比4小的{1,2,3}必须递减排列（3>2>1 ✓）。 **典型题目** 使用两个栈实现队列：stack_in用于入队，stack_out用于出队 - 入队：元素压入stack_in - 出队：如果stack_out不为空，弹出stack_out栈顶；否则把stack_in全部倒入stack_out 均摊时间复杂度：O(1) --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [考研408总结【数据结构】---栈和队列这是我参与11月更文挑战的第28天，活动详情查看：2021最后一次更文挑战 本篇 - 掘金] 稀土掘金 稀土掘金 # 考研408总结【数据结构】---栈和队列 这是我参与11月更文挑战的第28天，活动详情查看：2021最后一次更文挑战 考研倒计时：27天 ## 栈和队列 掌握好栈和队列的特点，进行一些相关推导即可。 具体知识点就不赘述了，主要提一下需要记忆的点。 首先常见的题型： 给出入栈序列，推导出栈序列个数，或者与队列结合。 `- 一般考虑手工推导即可 - n个不同元素进栈，出栈序列的个数为(1/n+1)Cn 2n` 循环队列（重点） if rear指向队尾元素的下一个，front指向队首元素。 `队满条件：(Q.rear+1)%MaxSize == Q **典型真题摘录：** 1. [[PDF] 2023 考研408 真题] 2023 考研408 真题 一、单项选择题：1～40 小题，每小题2 分，共80 分。下列每题给出的四个选项中，只有一 个选项是符合题目要求的。 1.下列对顺序存储的有序表(长度为n)实现给定操作的算法中， 平均时间复杂度为O(1)的是 （ ） 。 A.查找包含指定值元素的算法 B.插入包含指定值元素的算法 C.删除第i（1≤i≤n）个元素的算法 D.获取第i（1≤i≤n）个元素的算法 2.现有非空双向链表L，其结点结构为： ，prev 是指向直接前驱结点的指针，next I. M 的行数 II. M 中包含非零元素的行数 III. M 的列数 IV. M A. s–>next–>prev=p； s–>prev=p； B. p–>next–>prev=s； s–>prev=p； C. s–>prev=s–>next–>prev；s–>next–>prev=s； D. p–>next–>pr 2. [深入解析：《考研408数据结构》第三章（3.1 栈）复习笔记 - wzzkaifa - 博客园] 博客园logo 搜索 搜索 搜索 搜索 写随笔 我的博客 短消息 简洁模式 用户头像 返回主页 # wzzkaifa ## # 深入解析：《考研408数据结构》第三章（3.1 栈）复习笔记 前提提要： 基于数据结构我个人大一学过，而且我也一直认为是408里最容易的，故而我一直拖到很晚才开，视频也没看，直接加速用【思维导图】+【例题】极限回顾复习，因此我也默认大部分人都是很早就学完了数据结构，所以该数据结构系列笔记只适用于非初学者的框架回顾复习，不再解释简单知识点概念。 ； 【另外关于：栈】 通过网上许多大佬、博主都总结了，【栈】和【队列】出的代码题本来就少能够说就没有，那么代码理解这块我将不再深究，反正知道逻辑会做【选择题】应该就够了 ## 一、栈的基本概念 ### 思维导图（放大保存可打印） ### 稍微讲解 大家都会我就不说什么了，如何定义说白了就是————【 3. [408数据结构考察范围 | 考研数据结构笔记] ### ### ### ### ### ### ### 下一页1、基础知识 最后更新于 考察目标 一、线性表 （一）线性表的基本概念 （二）线性表的实现 二、栈、队列和数组 （一）栈和队列的基本概念 （二）栈和队列的顺序存储结构 （三）栈和队列的链式存储结构 （四）栈、队列和数组的应用 （五）特殊矩阵的压缩存储 （六）多维数组的存储 三、树与二叉树 （一）树的基本概念 （二）二叉树 （三）树、森林 （四）树与二叉树的应用 四、图 （一）图的基本概念 （二）图的存储及基本操作 （三）图的遍历 （四）图的基本应用 五、查找 （一）查找的基本概念 （二）顺序查找法 （三）分块查找法 （四）折半查找法 （五）树形查找结构 （六）B树及其基本操作、B+树的基本概念 （七）散列（Hash）表 （八）字符串模式匹配 --- ============================================================ 📅 学习时间：2026-05-11 06:00:01 🏷️ 知识点ID：ds_05 (MD5: 98057d4b) ============================================================ ### 查找算法：二分、平衡二叉树、散列表 **二分查找** - 条件：有序顺序表 - 时间复杂度：O(log n) - 易错：边界条件，mid = left + (right - left) // 2 **平衡二叉树（AVL）** - 定义：左右子树高度差绝对值小于等于1 - 旋转操作：LL（右单旋）、RR（左单旋）、LR（先左后右双旋）、RL（先右后左双旋） - 插入：先 BST 插入，再调整平衡因子 **B树与B+树** - B树：多路平衡查找树，节点包含数据 - B+树：非叶子节点只含索引，所有数据在叶子 - MySQL索引用B+树（叶子链表便于范围查询） **散列表** - 冲突处理：开放地址法（线性探测、二次探测）、链地址法 - 装填因子 = n/m，影响查找效率 - 开放地址法探测序列：h(key) = (h0 + f(i)) % m --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [《算法与数据结构考研试题精析》笔记(9) - 集合 | Lee's Blog] 完全二叉树一定是AVL树。 > 这种命题，颇有争议。争议地纠结点在于“AVL树是否是BST”。如果AVL树的本质是BST，那么完全树不一定是AVL树；否则，完全二叉树一定是AVL树。 这里以Leetcode上的说法，认为AVL树仅与平衡因子BF有关。 （王道的数据结构中认为AVL树的本质是BST；清华的数据结构中没有明确表述，其将平衡的二叉搜索树称为BBST） 设高为h的m阶B树上共有k个关键字，则其叶子结点有k+1个。 具有n个关键字的B树的查找路径长度不会大于the max BST of B B树的高度包括叶子结点那一层。 > 清华教材上为此说法。也有不包含叶子层的说法。 【2 2. [数据结构——四十、折半查找(王道408) - 教程 - tlnshuju - 博客园] 博客园logo 搜索 搜索 搜索 搜索 写随笔 我的博客 短消息 简洁模式 用户头像 # tlnshuju ## 数据结构——四十、折半查找(王道408) - 教程 #### 文章目录 ## 前言 本文介绍了折半查找（二分查找）的基本思想、实现方法和查找效率分析。折半查找仅适用于有序顺序表，通过不断缩小查找区间来定位目标元素。文章通过示例演示了查找成功和失败的流程，并提供了升序和降序排列时的C语言实现代码。在效率分析部分，通过构建判定树计算了成功和失败情况下的平均查找长度（ASL），指出折半查找判定树具有右子树结点数-左子树结点数=0或1的特性，且一定是平衡二叉树和二叉排序树。最后说 3. [[PDF] 上海科技大学2022 年攻读硕士学位研究生招生考试试题] Sort）、快速排序（Quick Sort）和堆排序（Heap Sort）；并请说明你得出相应结论的理由。 输入序列： 29，60，82，27，15，20，65，90，69，10，24 1) 29，60，82，15，27，20，65，90，69，10，24 29，60，15，27，82，20，65，90，10，24，69 15，27，29，60，82，10，20，24，65，69，90 2) 27，15，20，10，24，29，60，82，65，90，69 15，20，10，24，27，29，60，82，65，90，69 10，15，20，24，27，29，60，65，90，69，82 3) 4. [南昌大学2003年数据结构操作系统A专业课考研真题试卷(回忆版)_考研专业课 - 可可考研] ## 南昌大学 (单词翻译:单击) 一.单项选择题.(每题2分,共8分)1.对由n个记录组成的文件排序,如果n较小(n<50)且记录的规模较大,则采用()排序方法节省时间. A.直接插入 B.直接选择 C.快速 D.堆 2.假定有K个关键字互为同义词,若用线性探测法把这些同义词存入散列表中,至少要进行()次探测. A.K B.K2(K的平方) C.1/2K(K-1) D.1/2K(K+1) 3.二维数组a[0…8,1…10]按行存放时元素a[8,5]的起始地址与按列存放时元素()的起始地址相同. A.a[8,5] B.a[3,10] C. **典型真题摘录：** 1. [[PDF] 2023 考研408 真题] 5.已知一棵二叉树的树形如下图所示，若其后序遍历为f，d，b，e，c，a，则其先（前）序遍 历序列是（ ）。 A. a，e，d，f，b，c B. a，c，e，b，d，f 第 1 页，共 14 页 C. c，a，b，e，f，d D. d，f，e，b，a，c 6.已知无向连通图G 中各边的权值均为1，下列算法中，一定能够求出图G 中从某顶点到其余 各顶点最短路径的是（ ）。 I.普里姆（Prim）算法 II.克鲁斯卡尔（Kruskal）算法 III.图的广度优先搜索算法 A. 仅I B.仅III C. I、II D. I、II、III 7.下列关于非空B 树的叙述中，正确的是（ ）。 I.插入操作可能增加树的高度 II.删除操作一定会导致叶结点的变化 III.查找某关键字总是要查找到叶结点 IV.插入的新关键字最终位于叶结点中 A.仅I B. I、II C. III、IV D. I、II、IV 2. [2025 年 408 真题 | 计算机考研杂货铺] ##### 7 已知查找表中有 400 个元素，查找元素概率相同。采用分块查找法且均匀分块。若采用顺序查找法确定元素所在块，且块内也采用顺序查找法，为效率最高，每块包含元素应为（ ）。 数组查找 分块查找 正确答案：C 设块大小为 m ，块数为 mn​ 。查找复杂度为 O(n/m+m) 。 根据高中数学的知识可以得知， m=n​=20 时，查找复杂度最低，所以 m=20 。 ##### 8 给 7 个不同的关键字，能够构成不同 4 阶 B 树的个数为（ ）。 正确答案：C 树高为 3：每个节点内关键字个数最少取 1 时，B 树 高度为 3（类似满二叉树）——仅一种结构； 树高为 2: + 根节点关键字个数取 1，第二层两节点关键字个数均取 3——一种结构； + 根节点关键字个数取 2，则第二层内三个节点关键字个数分别可取 221、212、122、311 3. [408数据结构考察范围 | 考研数据结构笔记] ### （一）查找的基本概念 ### （二）顺序查找法 ### （三）分块查找法 ### （四）折半查找法 ### （五）树形查找结构 1. 二叉搜索树 2. 平衡二叉树 3. 红黑树 ### （六）B树及其基本操作、B+树的基本概念 ### （七）散列（Hash）表 ### （八）字符串模式匹配 ### （九）查找算法的分析及应用 ## 六、排序 ### （一）排序的基本概念 ### （二）直接插入排序 ### （三）折半插入排序 ### ### ### ### ### ### ### ### ### 下一页1、基础知识 最后更新于 [...] 📒 `⌘Ctrl``k` # 408数据结构考察范围 ## 考察目标 1. 掌握数据结构的基本概念、基本原理和基本方法 2. 掌握数据的逻辑结构、存储结构及基本操作的实现，能 --- ============================================================ 📅 学习时间：2026-05-11 14:00:01 🏷️ 知识点ID：ds_01 (MD5: b5c14b1f) ============================================================ ### 时间复杂度与空间复杂度分析 **核心概念** - 时间复杂度：算法执行次数与问题规模的渐近关系 - 空间复杂度：算法所需存储空间与问题规模的渐近关系 - 常用记号：O(1)、O(log n)、O(n)、O(n log n)、O(n2)、O(n3)、O(2n)、O(n!) **易错点** 1. 混淆O(n)和O(2n)：系数不重要，渐近上界只看最高次项 2. 递归算法空间复杂度：递归深度×每次递归的局部变量大小 3. 最好/最坏/平均复杂度：不要把三者混淆 **典型题目** for (i = 0; i < n; i++) for (j = i; j < n; j++): pass # O(1)操作 分析：外层n次，内层分别为n, n-1, n-2...1，总和 = n(n+1)/2 = O(n2) --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [《王道数据结构考研复习指导》笔记 | Lee's Blog] 时间复杂度的运算规则： 常见的时间复杂度： 算法的空间复杂度：若输入数据所占空间值取决于问题本身，和算法无关，则只需分析输入和程序之外的额外空间。 算法原地工作：算法所需的辅助空间为常量，即`O(1)`。 ## 二、线性表 【线性表的特点】 表中元素的个数有限； 表中元素具有逻辑上的顺序性，表中元素由其先后次序； 表中元素都是数据元素，每个元素都是单个元素； 表中元素的数据类型都相同，这意味着占有相同大小的存储空间； ### 顺序表 【顺序表的特点】表中元素的逻辑顺序与其物理顺序相同； > 称i为元素ai在线性表中的位序。 线性表中元素的位序是从1开始的，而数组中 2. [GitHub - anbingxu666/WangDao-DataStructure: 《数据结构》经典算法代码 · GitHub] `.cpp` ### 使用方法1（推荐） 在线阅读，学习代码思想，手写 ### 使用方法2（推荐） ### 使用方法3 导入Clion工程，手动更改Makefile ### 使用方法4 大佬qing自行研究😊 ## 线性表 本章是考试重点容易出算法大题 2019 9 14 课后算法题更新到7道，对于2020王道数据结构第18页 链表的直接插入排序 2019 9 18 ## 栈 ## 队列 ## 树 🌲的考察在于各种树的特点，以及树的遍历算法 ### 平衡二叉树 ## 图 ### 遍历问题 ### 最小生成树问题 ### 最短路径问题 ### 拓扑排序 3. [王道计算机考研 数据结构_哔哩哔哩_bilibili] 16:19 数据结构8.5选择16-20 16:15 数据结构8.6选择1-5 10:56 数据结构8.6选择6-10 18:33 数据结构8.6选择11-15 14:26 数据结构8.6选择16-20 17:06 数据结构8.6选择21-23 35:09 数据结构8.7选择1-5 14:10 数据结构8.7选择6-10 16:13 数据结构8.7选择11-15 12:13 数据结构8.7选择16 07:33 王道计算机考研 数据结构 0.0 课程白嫖指南 04:37 1.0\_开篇\_数据结构在学什么 07:59 1.1\_数据结构的基本概 4. [解2022年408考研真题第1题-腾讯云开发者社区-腾讯云] ## 解2022年408考研真题第1题 # 解2022年408考研真题第1题 作者头像 ## 解2022年408考研真题第1题 2022年408考研真题第1题，考察了时间复杂度的计算方法。题目内容如下： 下列程序段的时间复杂度是（ ）。 `sum = 0; for (i = 1; i < n; i = 2) for (j = 0; j < i; j++) sum++;` A. B. C. D. 对于这个题目，一种比较简单的解法是设 为 的倍数，即找一个特例，如令 ，则 。从而确定基本语句 `sum++` 的频度。 `sum++` 这种求解方法，能够得到正确答案 **典型真题摘录：** 1. [王道考研数据结构 - 京东] 【官方店 现货先发】王道408考研2027版计算机 408王道2027 计算机考研复习指导系列 王道数据结构 计算机考研教材真题机试指南 王道计算机 数据结构+组成原理 [...] 2027王道考研408全套4本数据结构操作系统计算机网络组成原理计算机专业基础综合历年真题预测冲刺卷考试辅导用书2027计算机官方 2026年计算机历年真题解析+模拟题 2027王道考研408全套4本数据结构操作系统计算机网络组成原理计算机专业基础综合历年真题预测冲刺卷考试辅导用书2027计算机官方 【2027现货】计算机网络+操作系统 【官方店 现货先发】王道408考研2027版计算机 408王道2027 计算机考研复习指导系列 王道数据结构 计算机考研教材真题机试指南 【现货先发】王道408计算机考研全套(共6册)") 2027王道408计算机考研复习指导系列 王道408计算机考研全套(共4册) 王道数据 2. [408历年真题解析数据结构篇 - 知乎专栏] 参考文献. 《2023年计算机专业基础综合考试历年真题解析》王道论坛; 《2024年全国硕士研究生招生考试计算机学科专业基础 3. [2021 王道考研 数据结构+习题讲解_王道课后题pdfP2【2021版】1.1.0 开篇_数据结构在学什么 P3【20 - 掘金] 稀土掘金 稀土掘金 # 2021 王道考研 数据结构+习题讲解\_王道课后题pdf P2【2021版】1.1.0 开篇\_数据结构在学什么 P3【2021版】1.1.1 数据结构的基本概念 P4【2021版】1.2.1 算法的基本概念 P5【2021版】1.2.2 算法的时间复杂度 P6【2021版】1.2.3 算法的空间复杂度 P7【2021版】2.1\_线性表的定义和基本操作 P8【2021版】2.2.1\_顺序表的定义 P9【2021版】2.2.2\_1\_顺序表的插入删除 P10【2021版】2.2.2\_2\_顺序表的查找 P11【2021版】2.3.1\_单链表的定义 P12【2021版】2.3.2\_1\_单链表的插入删除 P13【2021版】2.3.2\_2\_单链表的查找 P14【2021版】2.3.2\_3\_单链表的建立 P15【2021 --- ============================================================ 📅 学习时间：2026-05-11 22:00:01 🏷️ 知识点ID：ds_03 (MD5: 08662c02) ============================================================ ### 二叉树遍历与线索二叉树 **核心概念** - 先序遍历（DLR）：根-左-右 - 中序遍历（LDR）：左-根-右 - 后序遍历（LRD）：左-右-根 - 层序遍历：利用队列，层内从左到右 **易错点** 1. 已知两种遍历序列（包含中序），可唯一确定二叉树 2. 仅有先序+后序无法唯一确定（可确定祖先关系但不能确定结构） 3. 递归遍历时间复杂度O(n)，空间复杂度O(h)，h为树高 **线索二叉树** - 目的：加快遍历速度，避免递归/栈 - 规定：若无左孩子，指向前驱；若无右孩子，指向后继 - 需要ltag/rtag标志位区分孩子指针和线索指针 **典型题目** 已知先序序列：ABDECF，中序序列：DBEAFC，构建二叉树 1. 先序根A → 中序分 DBE | A | CF 2. 左子树先序：BDE，中序：DBE → B为左子树根 3. 右子树先序：CF，中序：CF → C为右子树根 4. 结果：A左子B(B左D右E)，A右子C(C左F) --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [《王道数据结构考研复习指导》笔记 | Lee's Blog] ## 五、树与二叉树 树适合于表示具有层次结构的数据. 结点的深度是从根结点开始自顶向下逐层增加；结点的高度从叶结点开始自底向上逐层增加。 度为m的树中第i层上至多有m^{i-1}个结点； 高度为h的m叉树至多有num个结点； 具有n个结点的m叉树最小高度为height。 二叉树的子树有左右之分，次序不能任意颠倒。 > 二叉树是有序树，即使树中结点只有一棵子树，也要区分它是左子树还是右子树。 平衡二叉树是二叉排序树。 依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映结点之间的逻辑关系。这样子既能最大可能地节省空间，又能利用数组元素的下 2. [考研408总结【数据结构】---树与二叉树（上）这是我参与11月更文挑战的第2天，活动详情查看：2021最后一次更文挑战 - 掘金] ## 二叉树的遍历 下面是三种遍历的递归代码，后续很多题型以此拓展得来。 `//二叉树的存储结构 typedef struct BTNode{ char data; struct BTNode lchild; struct BTNode rchild; } //先序遍历 根左右 void preorder(BTNode p){ if(p!=NULL){ Visit(p);//对p进行访问。比如打印p对应的数值 preorder(p->lchild); preorder(p->rchild); } } //中序遍历 左根右 void inorder(BTNode p){ if(p!=NULL **典型真题摘录：** 1. [王道数据结构第五章二叉树的遍历第6题原创 - CSDN博客] 题目描述. 设一棵二叉树各结点的值互不相同，其先序遍历和中序遍历分别存于两个一维数组A[1...n]和B[1...n]中，试编写算法建立该二叉树的二叉链表。 2. [【王道数据结构】《王道数据结构》课后代码题汇总 - 梁君牧 - 博客园] `/ 设置一个全局变量i记录已访问过的结点的序号，其初值是根结点在先序序列中的序号，即1.当二叉树b为空时返回特殊字符，，当i==k时，表示找到了满足条件的结点，返回b->data;当ik时，递归地在左子树中查找，若找到则返回该值，否则继续递归地在右子树中查找，并返回其结果。 本题实质上就是一个遍历算法的实现，只不过用一个全局变量来记录访问的序号，求其他遍历序列的第k个结点也采用相似的方法。二叉树的遍历算法可以引申出大量的算法题，因此考生务必要熟练掌握二又树的遍历算法。 / int i=1; //遍历序号的全局变量 int PreNode(BiTree b,int k) { if(b==NULL) //空结点，则返回特殊字符 return '#'; //相等，则当前结点即为第k个结点 if(i==k) return b->data; i++; //下一个结点 ch = PreNode(b- 3. [王道计算机考研团队整理-22考研408真题及答案] Full description ## Uploaded by Riet A AI-enhanced title and description Download Save Save 王道计算机考研团队整理-22考研408真题及答案 For Later Share 0%0% found this document useful, undefined 0%, undefined Print Embed Report 0 ratings 0% found this document useful (0 votes) 2K views 21 pages # 王道计算机考研团队整理 22考研408真题及答案 这是一道判断二叉树是否为二叉搜索树的题目。题目要求使用C或C++语言描述一个高效算法。答案提供了算法的基本设计思 --- ============================================================ 📅 学习时间：2026-05-12 06:00:01 🏷️ 知识点ID：ds_04 (MD5: 0fd8e00c) ============================================================ ### 图遍历：DFS与BFS及其应用 **核心概念** - BFS（广度优先）：用队列，按层次遍历 - DFS（深度优先）：用栈（或递归），先深后广 - 时间复杂度：邻接表O(V+E)，邻接矩阵O(V2) **易错点** 1. BFS计算最短路径（无权图）：首次到达即为最短 2. DFS生成树/森林：同一强连通分量的顶点可通过DFS访问 3. 邻接矩阵空间复杂度O(V2)，适合稠密图 **应用** - BFS：最短路径（无权）、拓扑排序（Kahn算法） - DFS：拓扑排序（基于DFS的逆序）、强连通分量（Kosaraju） **典型题目** 拓扑排序算法（Kahn）： 1. 计算所有顶点入度 2. 将入度为0的顶点入队 3. 不断出队，删除边，更新入度 4. 若输出顶点数为V，则无环；否则有环 时间复杂度：O(V+E) --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [408数据结构复习框架二（树与二叉树、图），含近十年考研真题] 8.4图的应用（最小生成树、最短路径、拓扑排序、拓扑排序）. （1）最小生成树. 性质：最小生成树的树形不唯一；其对应的边的权值之和总是唯一的，而且是 2. [计算机考研408真题解析（2024-41 有向图拓扑序列唯一性判定算法详解）_考研真题 拓扑排序 航天-CSDN博客] `int uniquely(MGraph G)` `G` 题目原文节选： 【2024-41】 2023年10月26日，神州十七号载人飞船发射取得圆满成功，再次彰显了中国航天事业的辉煌成就。载人航天工程是包含众多子工程的复杂系统工程，为了保证工程的有序开展，需要明确各子工程的前导子工程，以协调各子工程的实施。该问题可以简化、抽象为有向图的拓扑序列问题。已知有向图 G 采用邻接矩阵存储，类型定义如： `typedef struct { int numVertices, numEdges; //图的顶点数和有向边数 char VerticesList[MAXV]; //顶点表，MAXV 为已定 **典型真题摘录：** 1. [考研408数据结构第六章——图（含应用）] （4）逆拓扑排序：和拓扑正好相反，先找出度为0的顶点，每次去掉该顶点已经射入该 ... 五、408真题. 2009年（选择1）. （2分）下列关于无向连通图特性的叙述中 2. [C 408—《数据结构》图、查找、排序专题考点（含解析） - 华为云] 【摘要】 408考研——《数据结构》图，查找和排序专题考点选择题汇总（含解析）。 ​. 目录. Δ前言. 六、图. 6.1 图的基本概念. 6.2 图的存储及基本操作. 3. [数据结构408统考真题精讲：高频考点与复习策略_51CTO学堂_专业的IT技能学习平台] | 概念 | 二叉排序树 | 平衡二叉树 | --- | 定义 | 每个节点的左子树小于该节点，右子树大于该节点 | 在二叉排序树的基础上，保证左右子树的高度差不超过1 | | 特点 | 可能退化为链表 | 保证树的高度平衡，查找效率更高 | | 概念 | 拓扑排序 | 关键路径 | --- | 定义 | 对有向无环图（DAG）进行排序，使得每个节点的前驱节点都排在其前面 | 在拓扑排序的基础上，计算图中的最长路径 | | 应用场景 | 任务调度、依赖关系分析 | 项目管理、工期优化 | 通过本文的解析与示例，希望考生能够更好地掌握数据结构408统考中的高频考点，并结合配套视频课程进行复习。 上一篇：微软AI分层服务：快速集成机器学习能力 下一篇：深入理解数组：定义、赋值与操作 最新文章 FineBI模型关联与跨表计算实战避坑指南：5步搞定年月匹配、百分比显示与 --- ============================================================ 📅 学习时间：2026-05-12 10:00:01 🏷️ 知识点ID：ds_01 (MD5: b5c14b1f) ============================================================ ### 时间复杂度与空间复杂度分析 **核心概念** - 时间复杂度：算法执行次数与问题规模的渐近关系 - 空间复杂度：算法所需存储空间与问题规模的渐近关系 - 常用记号：O(1)、O(log n)、O(n)、O(n log n)、O(n2)、O(n3)、O(2n)、O(n!) **易错点** 1. 混淆O(n)和O(2n)：系数不重要，渐近上界只看最高次项 2. 递归算法空间复杂度：递归深度×每次递归的局部变量大小 3. 最好/最坏/平均复杂度：不要把三者混淆 **典型题目** for (i = 0; i < n; i++) for (j = i; j < n; j++): pass # O(1)操作 分析：外层n次，内层分别为n, n-1, n-2...1，总和 = n(n+1)/2 = O(n2) --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [计算机考研 408 数据结构 时间复杂度分析 计算题例题及解析_算法时间复杂度分析 考研题-CSDN博客] # 计算机考研 408 数据结构 时间复杂度分析 计算题例题及解析. 已于 2025-12-30 10:48:00 修改. CC 4.0 BY-SA版权. 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。. 于 2025-12-29 16:44:30 首次发布. ## 解题步骤. ## 例题. **例1** 以下 C 代码的时间复杂度是\_\_\_\_。. count = 0 for = 0*< + + for = 0< + + count + +. 1. i∈[0,√n−1],j∈[0,i−1]. 2. 0+1+2+...+√n−1=( 2. [《王道数据结构考研复习指导》笔记 | Lee's Blog] 时间复杂度的运算规则： 常见的时间复杂度： 算法的空间复杂度：若输入数据所占空间值取决于问题本身，和算法无关，则只需分析输入和程序之外的额外空间。 算法原地工作：算法所需的辅助空间为常量，即`O(1)`。 ## 二、线性表 【线性表的特点】 表中元素的个数有限； 表中元素具有逻辑上的顺序性，表中元素由其先后次序； 表中元素都是数据元素，每个元素都是单个元素； 表中元素的数据类型都相同，这意味着占有相同大小的存储空间； ### 顺序表 【顺序表的特点】表中元素的逻辑顺序与其物理顺序相同； > 称i为元素ai在线性表中的位序。 线性表中元素的位序是从1开始的，而数组中 3. [数据结构-考研时间复杂度的计算，408时间复杂度真题2011-2022分析_时间复杂度计算-CSDN博客] CC 4.0 BY-SA版权. 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。. for (int i = 0; i < N; ++i). for (int j = 0; j < N; ++j). for (int k = 0; k < 2 * N; ++k). printf("%d\n", count);//执行次数为1. N总=1+n^2+2*n+10+1=2*n+12+n\*n;. for (int k = 0; k < 2 * N; ++k) {. printf("%d\n", count);//执行一次. void Func3 4. [时间复杂度和空间复杂度 | Stay hungry, Stay foolish.] 主定理可以用来分析递归算法的时间复杂度（也叫渐进复杂度）。 ## 常见时间复杂度问题分析 看一段代码根据n的不同情况，运行多少次。 画出递归状态树，第一层1个节点，第二层2个节点，第三层2^2个节点，第四层2^3个节点，最终根据等比数列求和公式计算所有的节点数，就是它的时间复杂度。 ### 二叉树遍历，前序、中序、后序：时间复杂度是多少？ 遍历二叉树，每个节点都会访问一次，所以最终时间复杂度都为O(n)，n代表节点总数。 也可以通过主定理推算出来。 ### 图的遍历，时间复杂度是多少？ 遍历图的时候，每个节点都会访问一次，所以时间复杂度都是O(n)，n代表节点总数。 ## **典型真题摘录：** 1. [王道计算机考研团队整理-22考研408真题及答案] 二哥的并发编程进阶之路（暗黑版）Image 48 No ratings yet 二哥的并发编程进阶之路（暗黑版） 573 pages Linux是怎样工作的Image 49 No ratings yet Linux是怎样工作的 297 pages 嵌入式Linux应用开发完全手册V5.1 STM32MP157 Pro开发板Image 50 No ratings yet 嵌入式Linux应用开发完全手册V5.1 STM32MP157 Pro开发板 489 pages C#经典教程入门PPTImage 51 No ratings yet C#经典教程入门PPT 430 pages 计算机组成原理Image 52 No ratings yet 计算机组成原理 260 pages C++2 2. [2021 王道考研 数据结构+习题讲解_王道课后题pdfP2【2021版】1.1.0 开篇_数据结构在学什么 P3【20 - 掘金] 稀土掘金 稀土掘金 # 2021 王道考研 数据结构+习题讲解\_王道课后题pdf P2【2021版】1.1.0 开篇\_数据结构在学什么 P3【2021版】1.1.1 数据结构的基本概念 P4【2021版】1.2.1 算法的基本概念 P5【2021版】1.2.2 算法的时间复杂度 P6【2021版】1.2.3 算法的空间复杂度 P7【2021版】2.1\_线性表的定义和基本操作 P8【2021版】2.2.1\_顺序表的定义 P9【2021版】2.2.2\_1\_顺序表的插入删除 P10【2021版】2.2.2\_2\_顺序表的查找 P11【2021版】2.3.1\_单链表的定义 P12【2021版】2.3.2\_1\_单链表的插入删除 P13【2021版】2.3.2\_2\_单链表的查找 P14【2021版】2.3.2\_3\_单链表的建立 P15【2021 3. [数据结构408统考真题精讲：高频考点与复习策略_51CTO学堂_专业的IT技能学习平台] 感谢您的理解与支持！ 我知道了 # 数据结构408统考真题精讲：高频考点与复习策略 数据结构考研408统考_发布时间_2025-04-07 16:48:49 相关的教程以及配套的讲解 ，分享给大家 → ## : total = 0 for i in range(n): for j in range(n): total += 1 return total # 时间复杂度为 O(n^2) ``` 1. 2. 3. 4. 5. 6. 7. 8. 空间复杂度的计算相对较少，但同样需要掌握。以下是一个空间复杂度的示例： ```python def example_function(n): arr = n # 空间复杂度为 O(n) return a --- ============================================================ 📅 学习时间：2026-05-12 18:00:01 🏷️ 知识点ID：ds_05 (MD5: 98057d4b) ============================================================ ### 查找算法：二分、平衡二叉树、散列表 **二分查找** - 条件：有序顺序表 - 时间复杂度：O(log n) - 易错：边界条件，mid = left + (right - left) // 2 **平衡二叉树（AVL）** - 定义：左右子树高度差绝对值小于等于1 - 旋转操作：LL（右单旋）、RR（左单旋）、LR（先左后右双旋）、RL（先右后左双旋） - 插入：先 BST 插入，再调整平衡因子 **B树与B+树** - B树：多路平衡查找树，节点包含数据 - B+树：非叶子节点只含索引，所有数据在叶子 - MySQL索引用B+树（叶子链表便于范围查询） **散列表** - 冲突处理：开放地址法（线性探测、二次探测）、链地址法 - 装填因子 = n/m，影响查找效率 - 开放地址法探测序列：h(key) = (h0 + f(i)) % m --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [Awesome-408/数据结构/王道笔记/search-algorithm.md at master · amatureemoprince/Awesome-408 · GitHub] 需要说明的是：m 阶 B 树表示所有结点子树高度相同的 m 路平衡查找树（说 B 树就是默认 m 阶 B 树，只是后者显示表示其最多有 m 颗子树）。 平衡查找树 是一种 自平衡的、有序的树形数据结构，用于高效存储和检索数据。它在动态插入、删除操作后能自动调整结构，确保最坏情况下的时间复杂度保持为 O(log n) 常见的平衡查找树有：AVL、RBT、B 树。对于不同的平衡查找树会有不同的约束条件！ 简单解释一下： 对于 AVL ，约束条件是任意一颗结点的左右子树高度差不能相差 1。 对于这里的 B 树，约束条件是每个结点的子树高度相同，结点关键字个数和子树个数限制。 B 树的定义 2. [数据结构——四十、折半查找(王道408) - 教程 - tlnshuju - 博客园] 博客园logo 搜索 搜索 搜索 搜索 写随笔 我的博客 短消息 简洁模式 用户头像 # tlnshuju ## 数据结构——四十、折半查找(王道408) - 教程 #### 文章目录 ## 前言 本文介绍了折半查找（二分查找）的基本思想、实现方法和查找效率分析。折半查找仅适用于有序顺序表，通过不断缩小查找区间来定位目标元素。文章通过示例演示了查找成功和失败的流程，并提供了升序和降序排列时的C语言实现代码。在效率分析部分，通过构建判定树计算了成功和失败情况下的平均查找长度（ASL），指出折半查找判定树具有右子树结点数-左子树结点数=0或1的特性，且一定是平衡二叉树和二叉排序树。最后说 **典型真题摘录：** 1. [2013年408真题数据结构篇 - 知乎专栏] 本题要求模拟平衡二叉树（AVL树）的插入过程。 将AVL树调整平衡的方法主要有旋转法和中序遍历法。 旋转法. 观察插入不平衡结点的在 2. [数据结构408统考真题精讲：高频考点与复习策略_51CTO学堂_专业的IT技能学习平台] # 示例 hash_table = HashTable(10) hash_table.insert(5) hash_table.insert(15) print(hash_table.search(5)) # 输出：True print(hash_table.search(10)) # 输出：False ``` 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. #### []( 以下是一些常见问题及其解答： | 问题 | 答案 | --- | | 1. 时间复杂度的计算方法是什么？ | 时间复杂度的计算方法是分析算法中基本操作的执行次数，通 3. [分享｜在力扣备战考研数据结构 - 讨论 - 力扣（LeetCode）] # 分享｜在力扣备战考研数据结构 - 讨论 - 力扣（LeetCode） （by 天赐细莲） 408历年真题数据结构算法大题题源一览 - 知乎 108 14 482 评论 (14) 排序:最热 评论 1 2 探索 关于我们商务咨询使用条款隐私政策问题反馈 更多 沪ICP备18019787号-20沪ICP证B2-20180578 Image 3沪公网安备31010702007420号 下载 App ©2026 领扣网络（上海）有限公司 --- ============================================================ 📅 学习时间：2026-05-13 02:00:01 🏷️ 知识点ID：ds_03 (MD5: 08662c02) ============================================================ ### 二叉树遍历与线索二叉树 **核心概念** - 先序遍历（DLR）：根-左-右 - 中序遍历（LDR）：左-根-右 - 后序遍历（LRD）：左-右-根 - 层序遍历：利用队列，层内从左到右 **易错点** 1. 已知两种遍历序列（包含中序），可唯一确定二叉树 2. 仅有先序+后序无法唯一确定（可确定祖先关系但不能确定结构） 3. 递归遍历时间复杂度O(n)，空间复杂度O(h)，h为树高 **线索二叉树** - 目的：加快遍历速度，避免递归/栈 - 规定：若无左孩子，指向前驱；若无右孩子，指向后继 - 需要ltag/rtag标志位区分孩子指针和线索指针 **典型题目** 已知先序序列：ABDECF，中序序列：DBEAFC，构建二叉树 1. 先序根A → 中序分 DBE | A | CF 2. 左子树先序：BDE，中序：DBE → B为左子树根 3. 右子树先序：CF，中序：CF → C为右子树根 4. 结果：A左子B(B左D右E)，A右子C(C左F) --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [2025 年 408 真题 | 计算机考研杂货铺] 其他选项均满足每个非 -1 节点（除根节点）都有存在的父节点，是有效的二叉树顺序存储表示。 ##### 4 下列关于二叉树及森林的叙述中，正确的是？（ ）。 正确答案：B 完全二叉树中，度为 1 的结点可能存在。比如一颗完全二叉树只有两个结点，那么根结点的度就是 1。A 选项错误。 森林转二叉树 有固定的方法，B 选项正确。 ##### 5 设字符集 S 包含 7 个字符，各字符出现的频次分别是 2, 3, 4, 6, 8, 10, 11。 为 S 中的各字符构造哈夫曼编码，编码长度不小于 3 的字符个数是（ ）。 正确答案：D 按照 哈夫曼树 构造：频次为 2, 3 2. [GitHub - ddy-ddy/cs-408: 计算机考研专业课程408相关的复习经验，资源和OneNote笔记 · GitHub] ## 二、数据结构 数据结构网上有很多质量很高的文章。有图解动画还有代码，这里推荐几个我看过的博客:Data-Structres | 算法大汇总 数据结构会画算法运行的流程图也就会做题了，笔记中记录了大多数算法的手绘流程图以及总结的算法常用结论和常考点。 👇下图是数据结构笔记中关于二叉树四种遍历方式的知识点：包括遍历过程，示例图，代码。[]( ## 三、计算机组成原理 计算机组成原理我是靠着王道视频和王道书过来的，如果实在有不理解的地方，我就会google，看各种博客。有些博客确实讲的很不错，精辟且易懂。计组难，但是还是有章可循的，主要以做题为导向！ 👇下图是计组笔记中一个关于控制 3. [王道计算机考研 数据结构_哔哩哔哩_bilibili] 5.3.2\_2\_二叉树的线索化 19:25 5.3.2\_3\_在线索二叉树中找前驱后继 18:19 5.4.1 树的存储结构 19:29 5.4.2 树、森林与二叉树的转换 14:51 5.4.3 树和森林的遍历 11:09 5.5.1\_哈夫曼树 17:38 5.5.2\_1\_并查集 32:13 5.5.2\_2\_并查集的进一步优化 10:17 6.1.1\_图的基本概念 30:39 6.2.1\_邻接矩阵法 15:38 6.2.2\_邻接表法 06:53 6.2.3+6.2.4\_十字链表、邻接多重表 12:40 6.2.5\_图的 **典型真题摘录：** 1. [408历年真题解析数据结构篇 - 知乎专栏] 二叉树的遍历; 哈夫曼(Humffman) 树与哈夫曼编码; 图的基本概念; B树的定义及其基本 ... 王道版真题勘误. 王道408历年真题解析勘误数据结构篇. 注：由于编写这部分内容 2. [王道数据结构第五章二叉树的遍历第6题原创 - CSDN博客] 题目描述. 设一棵二叉树各结点的值互不相同，其先序遍历和中序遍历分别存于两个一维数组A[1...n]和B[1...n]中，试编写算法建立该二叉树的二叉链表。 3. [2024王道408数据结构P39 T22 原创 - CSDN博客] 首先我们还是先明白题目的意思，要用高效的算法找出链表中倒数第k个元素的值，那我们就尝试一次遍历就找出倒数第k个元素，我们还是先举个例子方便我们理解 --- ============================================================ 📅 学习时间：2026-05-13 10:00:01 🏷️ 知识点ID：ds_02 (MD5: 8ffc4851) ============================================================ ### 栈和队列的性质与扩展 **核心概念** - 栈：LIFO，先进后出；操作：push/pop/top - 队列：FIFO，先进先出；操作：enqueue/dequeue/front - 循环队列：避免假溢出，用(n+1)个空间区分满/空 **易错点** 1. 循环队列队空条件：front == rear 2. 循环队列队满条件：(rear + 1) % maxsize == front 3. 中缀表达式转后缀表达式时，栈中存放操作符，优先级低的运算符在前 **出栈序列判定定理** 对于入栈序列1,2,3...,n的输出序列：每个数字后面比它小的数字必须按**递减顺序**排列。例如：入栈1,2,3,4，若出栈序列为4,3,2,1，对于数字4后面比4小的{1,2,3}必须递减排列（3>2>1 ✓）。 **典型题目** 使用两个栈实现队列：stack_in用于入队，stack_out用于出队 - 入队：元素压入stack_in - 出队：如果stack_out不为空，弹出stack_out栈顶；否则把stack_in全部倒入stack_out 均摊时间复杂度：O(1) --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [王道计算机考研 数据结构_哔哩哔哩_bilibili] 12:39 3.1.3\_栈的链式存储实现 03:52 3.2.1\_队列的基本概念 04:09 3.2.2\_队列的顺序实现 16:46 3.2.3\_队列的链式实现 09:25 3.2.4\_双端队列 14:54 3.3.1\_栈在括号匹配中的应用 11:48 3.3.2\_1\_栈在表达式求值中的应用(上) 31:41 3.3.2\_2\_栈在表达式求值中的应用(下) 20:33 3.3.3\_栈在递归中的应用 13:01 3.3.4+3.3.5\_队列的应用 08:24 3.4.1-3.4.4\_特殊矩阵的压缩存储 27:41 4.1\_1 **典型真题摘录：** 1. [王道2024考研408计算机领学班-92资源站-IT学习网-每日更新] ├──2024王道计算机 计算机网络.pdf 31.61M ├──2024王道计算机 计算机组成原理.pdf 34.23M └──2024王道计算机 数据结构.pdf 61.03M ├──01.C语言督学训练营 ├──01.初级阶段（C语言入门） ├──01.课程导学，编程环境搭建 ├──02.数据的类型、数据的输入输出 ├──03.运算符与表达式 ├──04.选择、循环 ├──05.一维数组与字符数组 ├──06.指针 ├──07.函数 └──08.结构体与C++引用讲解 ├──02.中级阶段【数据结构算法题实战】 ├──01.数据结构概述 ├──02.线性表代码实战 ├──03.单链表的新建、查找 ├──04.单链表的删除u0026考研真题实战 ├──05.栈与队列u0026考研真题实战 ├──06.二叉树的建树和遍历u0026考研真题实战 ├──07.考研必会的查找算法u0026考研 2. [数据结构408统考真题精讲：高频考点与复习策略_51CTO学堂_专业的IT技能学习平台] 线性表的顺序存储结构与链式存储结构在考试中经常以选择题形式出现，有时也会在大题中涉及存储结构与算法实现。 #### { Stack stack = (Stack)malloc(sizeof(Stack)); stack->data = (int)malloc(sizeof(int) size); stack->top = -1; stack->size = size; return stack; } void push(Stack stack, int value) { if (stack->top == stack->size - 1) { printf("Stack Overflow\n"); return; } stack->data[++stack->top] = value; 3. [408 复习路径（非科班必看） - 编程导航 | 一线开发者编程经验和技术实战分享] 编程导航 编程导航会员 # 408 复习路径（非科班必看） 寅贝勒 最近和星球内部和外部咨询的同学聊，发现大家对于408的进度还是比较自信，觉得现在还不是时候，在这里统一回复下，大三下开学就要开始。对于非科班，需要提前了解408大体，尽早开始，同时也不要有太大的心理压力，科班的可能啥也不会。 来篇文章作为25考研408序幕：计狗上岸知识库原文链接：408修炼手册 ### 408总体介绍 计算机基础综合 408 满分 150 分，考试时间 3 个小时。其中数据结构占 45 分，计算机组成原理占 45 分，操作系统占 35 分，计算机网络占 25 分。题型为 40 道单选，每道2 分，单选共 80 分；7 道大题，大题共 70 分。选择题是专业课得高分的保证，但是选择题涉及的知识点范围很广，而且知识点容易出现复习完又忘记的现象，所以专业课复习的核心是多复习几轮。 ### 参考教材 --- ============================================================ 📅 学习时间：2026-05-13 18:00:01 🏷️ 知识点ID：ds_04 (MD5: 0fd8e00c) ============================================================ ### 图遍历：DFS与BFS及其应用 **核心概念** - BFS（广度优先）：用队列，按层次遍历 - DFS（深度优先）：用栈（或递归），先深后广 - 时间复杂度：邻接表O(V+E)，邻接矩阵O(V2) **易错点** 1. BFS计算最短路径（无权图）：首次到达即为最短 2. DFS生成树/森林：同一强连通分量的顶点可通过DFS访问 3. 邻接矩阵空间复杂度O(V2)，适合稠密图 **应用** - BFS：最短路径（无权）、拓扑排序（Kahn算法） - DFS：拓扑排序（基于DFS的逆序）、强连通分量（Kosaraju） **典型题目** 拓扑排序算法（Kahn）： 1. 计算所有顶点入度 2. 将入度为0的顶点入队 3. 不断出队，删除边，更新入度 4. 若输出顶点数为V，则无环；否则有环 时间复杂度：O(V+E) --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [考研408核心知识体系与备考策略深度解析] # 考研408核心知识体系与备考策略深度解析 简介：本文系统梳理计算机专业考研408科目（数据结构、计算机组成原理、操作系统、计算机网络）的核心知识框架，结合历年真题分析命题规律，提供分阶段备考方案及高效复习技巧，助力考生构建完整知识体系。 ### 一、考研408科目构成与命题特点 计算机专业基础综合（408）作为全国统考科目，涵盖数据结构（45分）、计算机组成原理（45分）、操作系统（35分）、计算机网络（25分）四大模块，总分150分。其命题呈现三大特征：知识点覆盖广、题型灵活多变、强调综合应用。 以2023年真题为例，数据结构部分通过”平衡二叉树构建与遍历”综合题，同时考察树结构 **典型真题摘录：** 1. [实用指南：数据结构——三十六、拓扑排序(王道408) - yangykaifa - 博客园] #### 2.例子 在这里插入图片描述 在这里插入图片描述 在这里插入图片描述 ### 3.代码实现 `bool ReverseTopologicalSort(Graph G){ int outdegree[MaxVertexNum];// 当前顶点出度 int print[MaxVertexNum];// 记录拓扑序列 InitStack(S); //初始化栈，存储出度为0的顶点 for(int i=0; i2>1 ✓）。 **典型题目** 使用两个栈实现队列：stack_in用于入队，stack_out用于出队 - 入队：元素压入stack_in - 出队：如果stack_out不为空，弹出stack_out栈顶；否则把stack_in全部倒入stack_out 均摊时间复杂度：O(1) --- ### 🔍 考研真题相关定理与技巧 **典型真题摘录：** 1. [王道408历年真题讲解] 【已完结】计算机408考研官方版09-25年真题全套逐题精讲. 王道2027版数据结构习题讲解. 591.7万 2.4万. 34:57:34. 百万播放. App. 王道2027版数据结构习题讲解. 王道2026版 2. [408历年真题解析数据结构篇 - 知乎专栏] 408历年真题有非常强的继承关系，例如. 2019年题10考察了2014年题11中的快速排序中每一趟排序后的序列；; 2021年题2考察了2010年题2中的输出受限的双端队列可能的出队序列； 3. [【强化】计算机408考研数据结构考点梳理+25王道课后习题归类精讲] 00-数据结构考点梳理及课后题带学导言; 01-第一章绪论; 02-第二章线性表-1; 03-第二章线性表-2; 04-第三章栈、队列和数组-1; 05-第三章栈、队列和数组-2 --- ============================================================ 📅 学习时间：2026-05-14 22:00:01 🏷️ 知识点ID：ds_03 (MD5: 08662c02) ============================================================ ### 二叉树遍历与线索二叉树 **核心概念** - 先序遍历（DLR）：根-左-右 - 中序遍历（LDR）：左-根-右 - 后序遍历（LRD）：左-右-根 - 层序遍历：利用队列，层内从左到右 **易错点** 1. 已知两种遍历序列（包含中序），可唯一确定二叉树 2. 仅有先序+后序无法唯一确定（可确定祖先关系但不能确定结构） 3. 递归遍历时间复杂度O(n)，空间复杂度O(h)，h为树高 **线索二叉树** - 目的：加快遍历速度，避免递归/栈 - 规定：若无左孩子，指向前驱；若无右孩子，指向后继 - 需要ltag/rtag标志位区分孩子指针和线索指针 **典型题目** 已知先序序列：ABDECF，中序序列：DBEAFC，构建二叉树 1. 先序根A → 中序分 DBE | A | CF 2. 左子树先序：BDE，中序：DBE → B为左子树根 3. 右子树先序：CF，中序：CF → C为右子树根 4. 结果：A左子B(B左D右E)，A右子C(C左F) --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [2025 年408 真题 - 计算机考研杂货铺] 其他选项均满足每个非 -1 节点（除根节点）都有存在的父节点，是有效的二叉树顺序存储表示。 ##### 4 下列关于二叉树及森林的叙述中，正确的是？（ ）。 正确答案：B 完全二叉树中，度为 1 的结点可能存在。比如一颗完全二叉树只有两个结点，那么根结点的度就是 1。A 选项错误。 森林转二叉树 有固定的方法，B 选项正确。 ##### 5 设字符集 S 包含 7 个字符，各字符出现的频次分别是 2, 3, 4, 6, 8, 10, 11。 为 S 中的各字符构造哈夫曼编码，编码长度不小于 3 的字符个数是（ ）。 正确答案：D 按照 哈夫曼树 构造：频次为 2, 3 2. [GitHub - ddy-ddy/cs-408: 计算机考研专业课程408相关的复习经验，资源和OneNote笔记 · GitHub] ## 二、数据结构 数据结构网上有很多质量很高的文章。有图解动画还有代码，这里推荐几个我看过的博客:Data-Structres | 算法大汇总 数据结构会画算法运行的流程图也就会做题了，笔记中记录了大多数算法的手绘流程图以及总结的算法常用结论和常考点。 👇下图是数据结构笔记中关于二叉树四种遍历方式的知识点：包括遍历过程，示例图，代码。[]( ## 三、计算机组成原理 计算机组成原理我是靠着王道视频和王道书过来的，如果实在有不理解的地方，我就会google，看各种博客。有些博客确实讲的很不错，精辟且易懂。计组难，但是还是有章可循的，主要以做题为导向！ 👇下图是计组笔记中一个关于控制 **典型真题摘录：** 1. [408历年真题解析数据结构篇 - 知乎专栏] 二叉树的遍历; 哈夫曼(Humffman) 树与哈夫曼编码; 图的基本概念; B树的定义及其基本 ... 王道版真题勘误. 王道408历年真题解析勘误数据结构篇. 注：由于编写这部分内容 2. [计算机考研408真题解析（2023-05 二叉树遍历序列推导） - CSDN博客] 摘要：本文针对2023年计算机考研408数据结构真题中的二叉树遍历序列推导问题，详细分析了后序遍历与先序遍历的特性，并结合树型图重建二叉树结构。通过C语言 3. [2024王道408数据结构P39 T22 原创 - CSDN博客] 题目说要找倒数第k个元素，那我们肯定要把链表都遍历一遍，设指针p用来遍历链表。 ... 不确定的话我们再多举两个例子。现在假设我们要找的是倒数第3个元素也 --- ============================================================ 📅 学习时间：2026-05-15 06:00:01 🏷️ 知识点ID：ds_05 (MD5: 98057d4b) ============================================================ ### 查找算法：二分、平衡二叉树、散列表 **二分查找** - 条件：有序顺序表 - 时间复杂度：O(log n) - 易错：边界条件，mid = left + (right - left) // 2 **平衡二叉树（AVL）** - 定义：左右子树高度差绝对值小于等于1 - 旋转操作：LL（右单旋）、RR（左单旋）、LR（先左后右双旋）、RL（先右后左双旋） - 插入：先 BST 插入，再调整平衡因子 **B树与B+树** - B树：多路平衡查找树，节点包含数据 - B+树：非叶子节点只含索引，所有数据在叶子 - MySQL索引用B+树（叶子链表便于范围查询） **散列表** - 冲突处理：开放地址法（线性探测、二次探测）、链地址法 - 装填因子 = n/m，影响查找效率 - 开放地址法探测序列：h(key) = (h0 + f(i)) % m --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [Awesome-408/数据结构/王道笔记/search-algorithm.md at master · amatureemoprince/Awesome-408 · GitHub] 前两种情况较为简单，则只举第三种情况的例子。 BST删除结点示意图 BST删除结点示意图 ::: ### 平衡二叉树（AVL） BST 在某些时候会退化为链表，故引入平衡二叉树，避免出现这种情况。 AVL：可以是一颗空树或者满足以下性质的二叉树： AVL示意图 AVL示意图 每个结点中的数值就为该结点的平衡因子（左右子树高度之差）。 AVL 的插入： AVL 的性质比 BST 的严格多了，所以在插入结点后被破坏了性质而进行的操作也比 BST 的操作复杂许多！ 会涉及到 RR、LL、RL、LR 这四种操作。下面一一来说明什么情况下使用什么操作。 AVL 插入的过程：先和 2. [数据结构——四十、折半查找(王道408) - 教程 - tlnshuju - 博客园] 博客园logo 搜索 搜索 搜索 搜索 写随笔 我的博客 短消息 简洁模式 用户头像 # tlnshuju ## 数据结构——四十、折半查找(王道408) - 教程 #### 文章目录 ## 前言 本文介绍了折半查找（二分查找）的基本思想、实现方法和查找效率分析。折半查找仅适用于有序顺序表，通过不断缩小查找区间来定位目标元素。文章通过示例演示了查找成功和失败的流程，并提供了升序和降序排列时的C语言实现代码。在效率分析部分，通过构建判定树计算了成功和失败情况下的平均查找长度（ASL），指出折半查找判定树具有右子树结点数-左子树结点数=0或1的特性，且一定是平衡二叉树和二叉排序树。最后说 3. [数据结构408统考真题精讲：高频考点与复习策略_51CTO学堂_专业的IT技能学习平台] 感谢您的理解与支持！ 我知道了 # 数据结构408统考真题精讲：高频考点与复习策略 数据结构考研408统考_发布时间_2025-04-07 16:48:49 相关的教程以及配套的讲解 ，分享给大家 → ## : total = 0 for i in range(n): for j in range(n): total += 1 return total # 时间复杂度为 O(n^2) ``` 1. 2. 3. 4. 5. 6. 7. 8. 空间复杂度的计算相对较少， **典型真题摘录：** 1. [2013年408真题数据结构篇 - 知乎专栏] 本题要求模拟平衡二叉树（AVL树）的插入过程。 将AVL树调整平衡的方法主要有旋转法和中序遍历法。 旋转法. 观察插入不平衡结点的在 2. [[PDF] 2023 考研408 真题答案解析 - 数据结构（Data Structure）] 2023 考研408 真题答案解析 一、单项选择题 1.【参考答案】D 【解析】 线性表的顺序存储结构采用一组地址连续的存储单元依次存储线性表的数据元素。 特 点是逻辑上相邻的数据元素在物理位置上相邻。 线性表顺序存储结构是一种随机存取的存储结 构，设线性表的每个元素占L 个存储单元，第一个元素a1 的存储地址是LOC(a1)，则任意元素 ai 的LOC(ai)=LOC(a1)+(i-1)L。因此获取第i 个值的算法为常量阶O(1)。 2.【参考答案】C 【解析】主要考察双链表的插入操作，解决这类问题可在纸上画出具体的双链表进行模拟。因 为 s->next 已经赋值为p 的后一个结点，同时p->next 指针已经赋值为s。所以只需要处理 s->next->prev 和 s->next->prev 的赋值，s->prev 需要指向p，s-next->prev 需要指向s。因为 p->next 3. [【已完结】2025考研数据结构全程班基础部分（适用于408与自命题）] 【已完结】2025考研数据结构全程班基础部分（适用于408与自命题） ... 7-2 线性表的查找; 7-3 二叉排序树与平衡二叉树; 7-4 B树与B+树; 7-5 红黑树; 7-6 并查集; 7-7 散列表 --- ============================================================ 📅 学习时间：2026-05-15 10:00:01 🏷️ 知识点ID：ds_03 (MD5: 08662c02) ============================================================ ### 二叉树遍历与线索二叉树 **核心概念** - 先序遍历（DLR）：根-左-右 - 中序遍历（LDR）：左-根-右 - 后序遍历（LRD）：左-右-根 - 层序遍历：利用队列，层内从左到右 **易错点** 1. 已知两种遍历序列（包含中序），可唯一确定二叉树 2. 仅有先序+后序无法唯一确定（可确定祖先关系但不能确定结构） 3. 递归遍历时间复杂度O(n)，空间复杂度O(h)，h为树高 **线索二叉树** - 目的：加快遍历速度，避免递归/栈 - 规定：若无左孩子，指向前驱；若无右孩子，指向后继 - 需要ltag/rtag标志位区分孩子指针和线索指针 **典型题目** 已知先序序列：ABDECF，中序序列：DBEAFC，构建二叉树 1. 先序根A → 中序分 DBE | A | CF 2. 左子树先序：BDE，中序：DBE → B为左子树根 3. 右子树先序：CF，中序：CF → C为右子树根 4. 结果：A左子B(B左D右E)，A右子C(C左F) --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [考研408总结【数据结构】---树与二叉树（上）这是我参与11月更文挑战的第2天，活动详情查看：2021最后一次更文挑战 - 掘金] 稀土掘金 稀土掘金 # 考研408总结【数据结构】---树与二叉树（上） 这是我参与11月更文挑战的第2天，活动详情查看：2021最后一次更文挑战 考研倒计时：53天 参考资料： 王道数据结构考研复习指导 天勤数据结构高分笔记 本篇先总结树的基本概念和计算、二叉树的遍历和线索二叉树的内容。 下篇总结树和森林、以及应用（二叉排序树、平衡二叉树、哈夫曼树）的内容。 ## 树的性质 树的结点数等于所有结点的度数加1. 度为m的树中第i层上至多有mi−1m^{i-1}mi−1个结点（i>=1) 高度为h，度为m的树【度为m的树指的是结点最多有m个孩子结点】至多有mh−1m−1\fr 2. [(王道408考研数据结构)第五章树-第二节1：二叉树的定义 - CSDN博客] (王道408考研数据结构)第五章树-第二节1：二叉树的定义、特殊的二叉树及二叉树性质 原创 · 一：二叉树基本概念. （1）二叉树定义; （2）二叉树五种形态 · 二：特殊 **典型真题摘录：** 1. [王道计算机考研团队整理-22考研408真题及答案] # 王道计算机考研团队整理 22考研408真题及答案 | PDF Opens in a new window Opens an external website Opens an external website in a new window This website utilizes technologies such as cookies to enable essential site functionality, as well as for performance cookies, personalization, and targeted advertising. To learn more, view the following link: Privacy Policy Skip to main content Open navigation menuImage 2. [数据结构树图算法题] 【已完结】计算机408考研官方版09-25年真题全套逐题精讲. 王道2027版数据结构 ... 使用动画讲解二叉树递归遍历的代码，数据结构与算法. 图的算法-DFS深度优先遍历 3. [王道数据结构第五章二叉树的遍历第6题原创 - CSDN博客] 题目描述. 设一棵二叉树各结点的值互不相同，其先序遍历和中序遍历分别存于两个一维数组A[1...n]和B[1...n]中，试编写算法建立该二叉树的二叉链表。 --- ============================================================ 📅 学习时间：2026-05-15 18:00:01 🏷️ 知识点ID：ds_02 (MD5: 8ffc4851) ============================================================ ### 栈和队列的性质与扩展 **核心概念** - 栈：LIFO，先进后出；操作：push/pop/top - 队列：FIFO，先进先出；操作：enqueue/dequeue/front - 循环队列：避免假溢出，用(n+1)个空间区分满/空 **易错点** 1. 循环队列队空条件：front == rear 2. 循环队列队满条件：(rear + 1) % maxsize == front 3. 中缀表达式转后缀表达式时，栈中存放操作符，优先级低的运算符在前 **出栈序列判定定理** 对于入栈序列1,2,3...,n的输出序列：每个数字后面比它小的数字必须按**递减顺序**排列。例如：入栈1,2,3,4，若出栈序列为4,3,2,1，对于数字4后面比4小的{1,2,3}必须递减排列（3>2>1 ✓）。 **典型题目** 使用两个栈实现队列：stack_in用于入队，stack_out用于出队 - 入队：元素压入stack_in - 出队：如果stack_out不为空，弹出stack_out栈顶；否则把stack_in全部倒入stack_out 均摊时间复杂度：O(1) --- ### 🔍 考研真题相关定理与技巧 **定理/技巧：** 1. [计算机考研 408 统考该如何准备？ | 二哥的Java进阶之路] 6.20—8.25 依照类似的步骤，完成计网，操作系统，计组的王道复习全书的二刷。 8.25—9.25 对照天勤408复习全书整理的知识点和教材，进行对4门课的知识点进行第三轮复习，查漏补缺。这里快速的把天勤复习全书上的题刷完。（整理出一份自己的重要知识点汇总，和易混知识点的对比，这一步很重要，是对前三轮复习的升华） 9.25—10.15 做完408计算机综合11年真题，可以不按照卷子刷，但真题里的每道题每一个知识点都要搞懂，尤其是大题。408的大题比较难，但是有套路，摸清套路以后，就会发现每年的大题是很类似的。（第一次做的时候，找不到套路很正常，后面还会做很多遍真题，慢慢就会有感觉的） **典型真题摘录：** 1. [数据结构408统考真题精讲：高频考点与复习策略_51CTO学堂_专业的IT技能学习平台] 线性表的顺序存储结构与链式存储结构在考试中经常以选择题形式出现，有时也会在大题中涉及存储结构与算法实现。 #### { Stack stack = (Stack)malloc(sizeof(Stack)); stack->data = (int)malloc(sizeof(int) size); stack->top = -1; stack->size = size; return stack; } void push(Stack stack, int value) { if (stack->top == stack->size - 1) { printf("Stack Overflow\n"); return; } stack->data[++stack->top] = value; 2. [408 复习路径（非科班必看） - 编程导航 | 一线开发者编程经验和技术实战分享] 编程导航 编程导航会员 # 408 复习路径（非科班必看） 寅贝勒 最近和星球内部和外部咨询的同学聊，发现大家对于408的进度还是比较自信，觉得现在还不是时候，在这里统一回复下，大三下开学就要开始。对于非科班，需要提前了解408大体，尽早开始，同时也不要有太大的心理压力，科班的可能啥也不会。 来篇文章作为25考研408序幕：计狗上岸知识库原文链接：408修炼手册 ### 408总体介绍 计算机基础综合 408 满分 150 分，考试时间 3 个小时。其中数据结构占 45 分，计算机组成原理占 45 分，操作系统占 35 分，计算机网络占 25 分。题型为 40 道单选，每道2 分，单选共 80 分；7 道大题，大题共 70 分。选择题是专业课得高分的保证，但是选择题涉及的知识点范围很广，而且知识点容易出现复习完又忘记的现象，所以专业课复习的核心是多复习几轮。 ### 参考教材 3. [2026考研王道计算机408] | | | ├──70-12.4 408考研真题2019年41题 题目解读与解题设计 .mp4 134.86M | | | ├──71-12.5 真题题目代码实战 .mp4 151.27M | | | ├──72-12.6 分析真题代码的时间复杂度 .mp4 12.87M | | | └──73-12.7 本节课OJ作业说明 .mp4 8.87M | | ├──13.栈与队列&考研真题实战 | | | ├──课件 | | | ├──74-13.1 上节课作业讲解 .mp4 128.92M | | | ├──75-13.2 与408关联解析及本节内容介绍 .mp4 8.83M | | | ├──76-13.3 栈的原理解析 .mp4 33.40M | | | ├──77-13.4 初始化栈-入栈-出栈实战 .mp4 60.38M | | | ├──78 --- ============================================================ 📅 学习时间：2026-05-16 02:00:01 🏷️ 知识点ID：ds_01 (MD5: b5c14b1f) ============================================================ ### 时间复杂度与空间复杂度分析 **核心概念** - 时间复杂度：算法执行次数与问题规模的渐近关系 - 空间复杂度：算法所需存储空间与问题规模的渐近关系 - 常用记号：O(1)、O(log n)、O(n)、O(n log n)、O(n2)、O(n3)、O(2n)、O(n!) **易错点** 1. 混淆O(n)和O(2n)：系数不重要，渐近上界只看最高次项 2. 递归算法空间复杂度：递归深度×每次递归的局部变量大小 3. 最好/最坏/平均复杂度：不要把三者混淆 **典型题目** for (i = 0; i < n; i++) for (j = i; j < n; j++): pass # O(1)操作 分析：外层n次，内层分别为n, n-1, n-2...1，总和 = n(n+1)/2 = O(n2) ============================================================ 📅 学习时间：2026-05-16 10:00:01 🏷️ 知识点ID：ds_05 (MD5: 98057d4b) ============================================================ ### 查找算法：二分、平衡二叉树、散列表 **二分查找** - 条件：有序顺序表 - 时间复杂度：O(log n) - 易错：边界条件，mid = left + (right - left) // 2 **平衡二叉树（AVL）** - 定义：左右子树高度差绝对值小于等于1 - 旋转操作：LL（右单旋）、RR（左单旋）、LR（先左后右双旋）、RL（先右后左双旋） - 插入：先 BST 插入，再调整平衡因子 **B树与B+树** - B树：多路平衡查找树，节点包含数据 - B+树：非叶子节点只含索引，所有数据在叶子 - MySQL索引用B+树（叶子链表便于范围查询） **散列表** - 冲突处理：开放地址法（线性探测、二次探测）、链地址法 - 装填因子 = n/m，影响查找效率 - 开放地址法探测序列：h(key) = (h0 + f(i)) % m ============================================================ 📅 学习时间：2026-05-16 18:00:01 🏷️ 知识点ID：ds_04 (MD5: 0fd8e00c) ============================================================ ### 图遍历：DFS与BFS及其应用 **核心概念** - BFS（广度优先）：用队列，按层次遍历 - DFS（深度优先）：用栈（或递归），先深后广 - 时间复杂度：邻接表O(V+E)，邻接矩阵O(V2) **易错点** 1. BFS计算最短路径（无权图）：首次到达即为最短 2. DFS生成树/森林：同一强连通分量的顶点可通过DFS访问 3. 邻接矩阵空间复杂度O(V2)，适合稠密图 **应用** - BFS：最短路径（无权）、拓扑排序（Kahn算法） - DFS：拓扑排序（基于DFS的逆序）、强连通分量（Kosaraju） **典型题目** 拓扑排序算法（Kahn）： 1. 计算所有顶点入度 2. 将入度为0的顶点入队 3. 不断出队，删除边，更新入度 4. 若输出顶点数为V，则无环；否则有环 时间复杂度：O(V+E) ============================================================ 📅 学习时间：2026-05-16 22:00:01 🏷️ 知识点ID：ds_04 (MD5: 0fd8e00c) ============================================================ ### 图遍历：DFS与BFS及其应用 **核心概念** - BFS（广度优先）：用队列，按层次遍历 - DFS（深度优先）：用栈（或递归），先深后广 - 时间复杂度：邻接表O(V+E)，邻接矩阵O(V2) **易错点** 1. BFS计算最短路径（无权图）：首次到达即为最短 2. DFS生成树/森林：同一强连通分量的顶点可通过DFS访问 3. 邻接矩阵空间复杂度O(V2)，适合稠密图 **应用** - BFS：最短路径（无权）、拓扑排序（Kahn算法） - DFS：拓扑排序（基于DFS的逆序）、强连通分量（Kosaraju） **典型题目** 拓扑排序算法（Kahn）： 1. 计算所有顶点入度 2. 将入度为0的顶点入队 3. 不断出队，删除边，更新入度 4. 若输出顶点数为V，则无环；否则有环 时间复杂度：O(V+E) ============================================================ 📅 学习时间：2026-05-17 06:00:01 🏷️ 知识点ID：ds_02 (MD5: 8ffc4851) ============================================================ ### 栈和队列的性质与扩展 **核心概念** - 栈：LIFO，先进后出；操作：push/pop/top - 队列：FIFO，先进先出；操作：enqueue/dequeue/front - 循环队列：避免假溢出，用(n+1)个空间区分满/空 **易错点** 1. 循环队列队空条件：front == rear 2. 循环队列队满条件：(rear + 1) % maxsize == front 3. 中缀表达式转后缀表达式时，栈中存放操作符，优先级低的运算符在前 **出栈序列判定定理** 对于入栈序列1,2,3...,n的输出序列：每个数字后面比它小的数字必须按**递减顺序**排列。例如：入栈1,2,3,4，若出栈序列为4,3,2,1，对于数字4后面比4小的{1,2,3}必须递减排列（3>2>1 ✓）。 **典型题目** 使用两个栈实现队列：stack_in用于入队，stack_out用于出队 - 入队：元素压入stack_in - 出队：如果stack_out不为空，弹出stack_out栈顶；否则把stack_in全部倒入stack_out 均摊时间复杂度：O(1) ============================================================ 📅 学习时间：2026-05-17 14:00:01 🏷️ 知识点ID：ds_03 (MD5: 08662c02) ============================================================ ### 二叉树遍历与线索二叉树 **核心概念** - 先序遍历（DLR）：根-左-右 - 中序遍历（LDR）：左-根-右 - 后序遍历（LRD）：左-右-根 - 层序遍历：利用队列，层内从左到右 **易错点** 1. 已知两种遍历序列（包含中序），可唯一确定二叉树 2. 仅有先序+后序无法唯一确定（可确定祖先关系但不能确定结构） 3. 递归遍历时间复杂度O(n)，空间复杂度O(h)，h为树高 **线索二叉树** - 目的：加快遍历速度，避免递归/栈 - 规定：若无左孩子，指向前驱；若无右孩子，指向后继 - 需要ltag/rtag标志位区分孩子指针和线索指针 **典型题目** 已知先序序列：ABDECF，中序序列：DBEAFC，构建二叉树 1. 先序根A → 中序分 DBE | A | CF 2. 左子树先序：BDE，中序：DBE → B为左子树根 3. 右子树先序：CF，中序：CF → C为右子树根 4. 结果：A左子B(B左D右E)，A右子C(C左F) ============================================================ 📅 学习时间：2026-05-17 22:00:01 🏷️ 知识点ID：ds_05 (MD5: 98057d4b) ============================================================ ### 查找算法：二分、平衡二叉树、散列表 **二分查找** - 条件：有序顺序表 - 时间复杂度：O(log n) - 易错：边界条件，mid = left + (right - left) // 2 **平衡二叉树（AVL）** - 定义：左右子树高度差绝对值小于等于1 - 旋转操作：LL（右单旋）、RR（左单旋）、LR（先左后右双旋）、RL（先右后左双旋） - 插入：先 BST 插入，再调整平衡因子 **B树与B+树** - B树：多路平衡查找树，节点包含数据 - B+树：非叶子节点只含索引，所有数据在叶子 - MySQL索引用B+树（叶子链表便于范围查询） **散列表** - 冲突处理：开放地址法（线性探测、二次探测）、链地址法 - 装填因子 = n/m，影响查找效率 - 开放地址法探测序列：h(key) = (h0 + f(i)) % m