第一部分1. 一句话核心总结针对数据结构考试以“优先级”为线索梳理了二叉树、图、排序、查找等核心模块的高频考点与解题技巧强调理解逻辑如指针操作、遍历过程而非死记硬背公式。2. 核心概念定义数据结构三要素数据项最小单位如学号、数据元素基本单位完整信息、数据对象同类元素的集合如整个班级的信息。逻辑结构四大类集合无任何关系、线性结构一对一、树形结构一对多、图形结构多对多。存储结构两种类型顺序存储物理空间连续如数组访问任意元素快O(1)但插入删除需移动大量元素O(n)适合静态查询。链式存储物理空间不连续通过指针连接插入删除仅需修改指针O(1)但访问需按顺序遍历O(n)且因存储指针而空间开销更大。时间复杂度仅关注最高次项常见排序O(1) O(log n) O(n) O(n log n) O(n²) O(n³) O(2^n)。3. 分类/类型/步骤1考试优先级约90%学校优先级章节预估分值占比最高二叉树、图、排序超过60%高查找含哈希表、二分查找约15%中绪论、线性表、栈与队列约20%低数组与广义表、递归5%以下2链表插入与删除核心操作操作核心原则关键步骤插入先改新节点指针再改前驱指针“先盖指针后赋值”新节点.next 前驱.next前驱.next 新节点删除修改前驱指针跳过目标节点释放目标节点前驱.next 目标.nextfree(目标)3二叉树的遍历遍历方式访问顺序示例以根A、左B、右C的树为例先序前序根→左→右A B D E C F中序左→根→右D B E A C F后序左→右→根D E B F C A层序逐层从左到右A B C D E F注图中的树结构为A为根B为A的左孩子B的左孩子为D右孩子为EC为A的右孩子C的左孩子为空右孩子为F。4哈夫曼树构建与WPL计算构建每次取权值最小的两个节点合并左小右大重复直至单根。WPL带权路径长度每个叶子节点的权值 × 路径长度之和。示例中9×1 7×1 5×2 3×2 33。5图的关键算法算法类型核心思想适用场景克鲁斯卡尔Kruskal最小生成树按边权升序不形成环则加入边稀疏图普里姆Prim最小生成树从起点开始每次加入与已选集合距离最近的顶点边稠密图迪杰斯特拉Dijkstra单源最短路径逐步确定从源点到各顶点的最短距离贪心非负权图弗洛伊德Floyd多源最短路径动态规划逐步允许中间点求解所有点对间最短路径6常见排序的稳定性口诀稳定排序插冒归基插入、冒泡、归并、基数排序不稳定排序选择、希尔、快速、堆排序4. 排序或对比关系顺序表 vs 链表顺序表查询快(O(1))增删慢(O(n))链表增删快(O(1))查询慢(O(n))。邻接矩阵 vs 邻接表矩阵适合边稠密图存储方便查边快O(1)表适合边稀疏图节省空间求度高。DFS深度优先 vs BFS广度优先DFS“一条路走到黑”再回溯BFS“层层扩散”遍历邻居。开放定址法 vs 链地址法处理哈希冲突定址法将冲突元素放到下一个空位链地址法在同一位置用链表存储多个元素。5. 具体建议与注意事项建议不要死记硬背插入删除的移动次数公式动手画12345的数组模拟操作。学习二叉树的三种遍历用带字母的简单树如A/B/C/D/E/F反复练习。最小生成树与最短路径算法是必考需要亲自走一遍流程。排序题会考察“某算法第一趟/第二趟后的序列”要动手模拟。注意最小生成树中“千万不能成环”成环则算法失效。迪杰斯特拉算法中选中的中继点已确定最短路径的点后续不再更新。哈希表查找失败次数计算中开放定址法需按探测序列找到空位为止链地址法需遍历链表直到空指针。不同学校的考纲可能有差异建议配合学校题库或模拟题练习。6. 补充说明误区认为“时间复杂度只看for循环层数”——实际上需要分析循环内部操作和递归深度。建议查看的资料老师给的题库、网上模拟题。第二部分常见知识点与需了解的概念基础概念类抽象数据类型ADT数据对象、数据关系、基本操作三者集合是“逻辑结构操作”的数学抽象。栈与队列的实现视频只讲概念未涉及顺序栈数组、链栈链表、循环队列数组实现及“假溢出”处理。树与二叉树的转换任意树可通过“左孩子右兄弟”表示法转换为二叉树算法题可能要求画出转换结果。二叉排序树BST左子树根右子树插入和删除操作是查找章节核心考点。平衡二叉树AVL树左右子树高度差不超过1其旋转调整LL/RR/LR/RL是常见选择题考点。风险类概念混淆风险考试中常出现“数据项”“数据元素”“数据对象”的选择题需注意数据项是最小单位数据元素是基本单位。指针操作中的“野指针”链表删除后必须free节点否则会造成内存泄漏但考试更关注指针修改逻辑。动态规划与贪心混淆迪杰斯特拉贪心与弗洛伊德动态规划的原理不同。排序稳定性的实际意义稳定性指“相同关键字的相对顺序在排序后是否改变”在笔试中容易被忽略。实操类如何手写快速排序过程快速排序的“挖坑法”或“指针交换法”的具体步骤这是常考大题。哈希表装填因子αα 表中记录数 / 哈希表长度影响查找效率常出现在选择题中。算法复杂度分析技巧递归算法如归并排序的空间复杂度O(n)与时间复杂度O(n log n)的推导逻辑。模拟图的连通性判断最小生成树前提是图连通。对比类递推 vs 递归递归可能导致栈溢出递推迭代效率更高。内部排序 vs 外部排序内部排序数据在内存中外部排序如多路归并用于处理大规模数据。深度优先生成树 vs 广度优先生成树两者生成树形态不同视频未展示从遍历过程到生成树的转换。常见误区误区1认为“树的高度 深度”。→ 高度从叶子节点算起深度从根节点算起但通常可混用考试若不区分则一致。误区2认为“最小生成树唯一”。→ 当存在相同权值的边时生成树可能不唯一。误区3认为“快速排序一定最快”。→ 最坏情况有序序列时间复杂度退化为O(n²)而堆排序可保证O(n log n)。误区4认为“哈希表查找时间复杂度一定是O(1)”。→ 实际受冲突影响最好O(1)最坏O(n)。进阶知识点B树与B树数据库索引常用结构平衡多路搜索树可在考研复试或后续课程中出现。字符串匹配算法KMP算法Knuth-Morris-Pratt是数据结构中经典算法其next数组计算是常见考点。图的拓扑排序与关键路径有向无环图DAG的应用在项目管理和工程规划中重要。并查集Union-Find高效处理集合合并与查询常用于Kruskal算法中检测环。第三部分全面内容总结合并第一、二部分1. 主题概述数据结构课程的核心在于逻辑结构与存储结构的映射关系线性表、树、图分别对应一对一、一对多、多对多的数据关系而顺序存储与链式存储则决定了插入/删除/访问的代价。考试高频集中在二叉树遍历、哈夫曼树、图的最小生成树与最短路径、排序算法的手动模拟与复杂度分析、哈希表冲突处理五大板块。视频以“会画图、能模拟”为核心方法强调通过动手操作替代机械记忆公式。2. 分类与对比模块关键概念常考形式典型分值线性表顺序表、单链表、双链表插入删除指针修改、头节点作用5-10分栈与队列LIFO、FIFO、循环队列判空判满出栈序列合法性、循环队列公式5-10分二叉树5种遍历、性质N0N21、哈夫曼树遍历序列推导、WPL计算、树转二叉树15-20分图邻接矩阵/表、DFS/BFS、最小生成树、最短路径画图模拟算法过程、求路径与代价15-20分查找二分查找、二叉排序树、哈希表开放/链地址查找次数计算、ASL平均查找长度10-15分排序6-8种内排序的趟次模拟、稳定性、复杂度给定序列手写某算法第一/第二趟结果15-20分3. 风险与注意事项注意最小生成树“成环即无效”迪杰斯特拉选中的中继点不再更新哈希表查找次数需区分成功与失败。补充风险快速排序最坏情况有序时间复杂度退化为O(n²)需警惕。哈希表装填因子过大时冲突加剧查找效率下降。递归算法空间复杂度常被低估可能引发栈溢出。4. 实操建议线性表画图模拟指针修改先改新节点再改原链。口头禅“先盖指针后赋值”。二叉树背诵三种遍历顺序根左右、左根右、左右根用简单树反复验证。哈夫曼树每次取最小两个权值合并左小右大编码左0右1。图算法Kruskal排序所有边从小到大加边成环则跳过。Prim从起点出发每次选与当前集合最短连接的非集顶点。Dijkstra迭代更新最短距离表每次选未处理的最小值作为中继点。排序重点练习冒泡、插入、选择、快速的手写过程。记住稳定排序口诀“插冒归基”。哈希表明确除留余数法、开放定址线性探测与链地址法的冲突解决步骤能计算成功/失败的平均查找长度。5. 常见误区辨析误区1数据元素和数据项混淆。→ 数据项是最小单元如姓名数据元素是完整记录。误区2二叉树遍历结果死记硬背。→ 应理解递归过程先序根先序左先序右。误区3认为最小生成树唯一。→ 权重相等边存在时可能不唯一。误区4哈希表查找总是O(1)。→ 冲突严重时效率急剧下降。误区5链表删除节点就是修改指针忘了释放内存。→ 考试中须写free语句。通过本篇内容你将掌握理解数据结构三要素数据项/数据元素/数据对象和四种逻辑结构集合/线性/树/图区分顺序存储与链式存储的性能差异及其适用场景掌握二叉树的三种深度遍历先/中/后序和哈夫曼树的构建与WPL计算学会手动模拟图的最小生成树Prim/Kruskal和最短路径Dijkstra算法过程判断常见排序算法的稳定性与时间复杂度能写出某趟排序后的序列计算哈希表在开放定址法和链地址法下的平均查找长度ASL
笔记：数据结构与算法（School examination）
第一部分1. 一句话核心总结针对数据结构考试以“优先级”为线索梳理了二叉树、图、排序、查找等核心模块的高频考点与解题技巧强调理解逻辑如指针操作、遍历过程而非死记硬背公式。2. 核心概念定义数据结构三要素数据项最小单位如学号、数据元素基本单位完整信息、数据对象同类元素的集合如整个班级的信息。逻辑结构四大类集合无任何关系、线性结构一对一、树形结构一对多、图形结构多对多。存储结构两种类型顺序存储物理空间连续如数组访问任意元素快O(1)但插入删除需移动大量元素O(n)适合静态查询。链式存储物理空间不连续通过指针连接插入删除仅需修改指针O(1)但访问需按顺序遍历O(n)且因存储指针而空间开销更大。时间复杂度仅关注最高次项常见排序O(1) O(log n) O(n) O(n log n) O(n²) O(n³) O(2^n)。3. 分类/类型/步骤1考试优先级约90%学校优先级章节预估分值占比最高二叉树、图、排序超过60%高查找含哈希表、二分查找约15%中绪论、线性表、栈与队列约20%低数组与广义表、递归5%以下2链表插入与删除核心操作操作核心原则关键步骤插入先改新节点指针再改前驱指针“先盖指针后赋值”新节点.next 前驱.next前驱.next 新节点删除修改前驱指针跳过目标节点释放目标节点前驱.next 目标.nextfree(目标)3二叉树的遍历遍历方式访问顺序示例以根A、左B、右C的树为例先序前序根→左→右A B D E C F中序左→根→右D B E A C F后序左→右→根D E B F C A层序逐层从左到右A B C D E F注图中的树结构为A为根B为A的左孩子B的左孩子为D右孩子为EC为A的右孩子C的左孩子为空右孩子为F。4哈夫曼树构建与WPL计算构建每次取权值最小的两个节点合并左小右大重复直至单根。WPL带权路径长度每个叶子节点的权值 × 路径长度之和。示例中9×1 7×1 5×2 3×2 33。5图的关键算法算法类型核心思想适用场景克鲁斯卡尔Kruskal最小生成树按边权升序不形成环则加入边稀疏图普里姆Prim最小生成树从起点开始每次加入与已选集合距离最近的顶点边稠密图迪杰斯特拉Dijkstra单源最短路径逐步确定从源点到各顶点的最短距离贪心非负权图弗洛伊德Floyd多源最短路径动态规划逐步允许中间点求解所有点对间最短路径6常见排序的稳定性口诀稳定排序插冒归基插入、冒泡、归并、基数排序不稳定排序选择、希尔、快速、堆排序4. 排序或对比关系顺序表 vs 链表顺序表查询快(O(1))增删慢(O(n))链表增删快(O(1))查询慢(O(n))。邻接矩阵 vs 邻接表矩阵适合边稠密图存储方便查边快O(1)表适合边稀疏图节省空间求度高。DFS深度优先 vs BFS广度优先DFS“一条路走到黑”再回溯BFS“层层扩散”遍历邻居。开放定址法 vs 链地址法处理哈希冲突定址法将冲突元素放到下一个空位链地址法在同一位置用链表存储多个元素。5. 具体建议与注意事项建议不要死记硬背插入删除的移动次数公式动手画12345的数组模拟操作。学习二叉树的三种遍历用带字母的简单树如A/B/C/D/E/F反复练习。最小生成树与最短路径算法是必考需要亲自走一遍流程。排序题会考察“某算法第一趟/第二趟后的序列”要动手模拟。注意最小生成树中“千万不能成环”成环则算法失效。迪杰斯特拉算法中选中的中继点已确定最短路径的点后续不再更新。哈希表查找失败次数计算中开放定址法需按探测序列找到空位为止链地址法需遍历链表直到空指针。不同学校的考纲可能有差异建议配合学校题库或模拟题练习。6. 补充说明误区认为“时间复杂度只看for循环层数”——实际上需要分析循环内部操作和递归深度。建议查看的资料老师给的题库、网上模拟题。第二部分常见知识点与需了解的概念基础概念类抽象数据类型ADT数据对象、数据关系、基本操作三者集合是“逻辑结构操作”的数学抽象。栈与队列的实现视频只讲概念未涉及顺序栈数组、链栈链表、循环队列数组实现及“假溢出”处理。树与二叉树的转换任意树可通过“左孩子右兄弟”表示法转换为二叉树算法题可能要求画出转换结果。二叉排序树BST左子树根右子树插入和删除操作是查找章节核心考点。平衡二叉树AVL树左右子树高度差不超过1其旋转调整LL/RR/LR/RL是常见选择题考点。风险类概念混淆风险考试中常出现“数据项”“数据元素”“数据对象”的选择题需注意数据项是最小单位数据元素是基本单位。指针操作中的“野指针”链表删除后必须free节点否则会造成内存泄漏但考试更关注指针修改逻辑。动态规划与贪心混淆迪杰斯特拉贪心与弗洛伊德动态规划的原理不同。排序稳定性的实际意义稳定性指“相同关键字的相对顺序在排序后是否改变”在笔试中容易被忽略。实操类如何手写快速排序过程快速排序的“挖坑法”或“指针交换法”的具体步骤这是常考大题。哈希表装填因子αα 表中记录数 / 哈希表长度影响查找效率常出现在选择题中。算法复杂度分析技巧递归算法如归并排序的空间复杂度O(n)与时间复杂度O(n log n)的推导逻辑。模拟图的连通性判断最小生成树前提是图连通。对比类递推 vs 递归递归可能导致栈溢出递推迭代效率更高。内部排序 vs 外部排序内部排序数据在内存中外部排序如多路归并用于处理大规模数据。深度优先生成树 vs 广度优先生成树两者生成树形态不同视频未展示从遍历过程到生成树的转换。常见误区误区1认为“树的高度 深度”。→ 高度从叶子节点算起深度从根节点算起但通常可混用考试若不区分则一致。误区2认为“最小生成树唯一”。→ 当存在相同权值的边时生成树可能不唯一。误区3认为“快速排序一定最快”。→ 最坏情况有序序列时间复杂度退化为O(n²)而堆排序可保证O(n log n)。误区4认为“哈希表查找时间复杂度一定是O(1)”。→ 实际受冲突影响最好O(1)最坏O(n)。进阶知识点B树与B树数据库索引常用结构平衡多路搜索树可在考研复试或后续课程中出现。字符串匹配算法KMP算法Knuth-Morris-Pratt是数据结构中经典算法其next数组计算是常见考点。图的拓扑排序与关键路径有向无环图DAG的应用在项目管理和工程规划中重要。并查集Union-Find高效处理集合合并与查询常用于Kruskal算法中检测环。第三部分全面内容总结合并第一、二部分1. 主题概述数据结构课程的核心在于逻辑结构与存储结构的映射关系线性表、树、图分别对应一对一、一对多、多对多的数据关系而顺序存储与链式存储则决定了插入/删除/访问的代价。考试高频集中在二叉树遍历、哈夫曼树、图的最小生成树与最短路径、排序算法的手动模拟与复杂度分析、哈希表冲突处理五大板块。视频以“会画图、能模拟”为核心方法强调通过动手操作替代机械记忆公式。2. 分类与对比模块关键概念常考形式典型分值线性表顺序表、单链表、双链表插入删除指针修改、头节点作用5-10分栈与队列LIFO、FIFO、循环队列判空判满出栈序列合法性、循环队列公式5-10分二叉树5种遍历、性质N0N21、哈夫曼树遍历序列推导、WPL计算、树转二叉树15-20分图邻接矩阵/表、DFS/BFS、最小生成树、最短路径画图模拟算法过程、求路径与代价15-20分查找二分查找、二叉排序树、哈希表开放/链地址查找次数计算、ASL平均查找长度10-15分排序6-8种内排序的趟次模拟、稳定性、复杂度给定序列手写某算法第一/第二趟结果15-20分3. 风险与注意事项注意最小生成树“成环即无效”迪杰斯特拉选中的中继点不再更新哈希表查找次数需区分成功与失败。补充风险快速排序最坏情况有序时间复杂度退化为O(n²)需警惕。哈希表装填因子过大时冲突加剧查找效率下降。递归算法空间复杂度常被低估可能引发栈溢出。4. 实操建议线性表画图模拟指针修改先改新节点再改原链。口头禅“先盖指针后赋值”。二叉树背诵三种遍历顺序根左右、左根右、左右根用简单树反复验证。哈夫曼树每次取最小两个权值合并左小右大编码左0右1。图算法Kruskal排序所有边从小到大加边成环则跳过。Prim从起点出发每次选与当前集合最短连接的非集顶点。Dijkstra迭代更新最短距离表每次选未处理的最小值作为中继点。排序重点练习冒泡、插入、选择、快速的手写过程。记住稳定排序口诀“插冒归基”。哈希表明确除留余数法、开放定址线性探测与链地址法的冲突解决步骤能计算成功/失败的平均查找长度。5. 常见误区辨析误区1数据元素和数据项混淆。→ 数据项是最小单元如姓名数据元素是完整记录。误区2二叉树遍历结果死记硬背。→ 应理解递归过程先序根先序左先序右。误区3认为最小生成树唯一。→ 权重相等边存在时可能不唯一。误区4哈希表查找总是O(1)。→ 冲突严重时效率急剧下降。误区5链表删除节点就是修改指针忘了释放内存。→ 考试中须写free语句。通过本篇内容你将掌握理解数据结构三要素数据项/数据元素/数据对象和四种逻辑结构集合/线性/树/图区分顺序存储与链式存储的性能差异及其适用场景掌握二叉树的三种深度遍历先/中/后序和哈夫曼树的构建与WPL计算学会手动模拟图的最小生成树Prim/Kruskal和最短路径Dijkstra算法过程判断常见排序算法的稳定性与时间复杂度能写出某趟排序后的序列计算哈希表在开放定址法和链地址法下的平均查找长度ASL
