879 字
2 分钟
考研专业课学习记录2026-06-26
考研专业课学习记录 | 2026-06-26
今日学习内容
两个半小时，完成并查集和霍夫曼编码的学习
AI知识点带复盘
并查集考点复盘
- 核心概念：并查集是用于管理元素分组、查询连通性的经典数据结构，考研408中核心考察
查找(Find)和合并(Union)两种基础操作，以及其优化版本的实现与应用场景。 - 优化技巧：
- 路径压缩：查找根节点时，将当前节点直接指向根节点，扁平化树结构，降低后续查找的时间复杂度
- 按秩合并：按树的深度或节点数量合并，将浅树挂载到深树上，避免树高过度增长 两种优化结合后，单次操作时间复杂度近似为，为阿克曼函数反函数，增长极慢可视为常数。
- 考研常见考察形式：
- 选择题：连通性判断、优化方式的时间复杂度分析、实际场景应用（如Kruskal最小生成树、朋友圈分组问题）
- 编程题：实现带优化的并查集、解决网格连通块、动态分组统计等题型
霍夫曼编码考点复盘
- 核心概念：霍夫曼编码基于霍夫曼树（最优二叉树）实现，属于变长前缀编码，可使给定权值的编码总长度最短，是数据压缩领域的经典应用。
- 标准构造步骤：
- 将所有给定权值作为叶子节点构建独立二叉树森林
- 每次选取两个权值最小的节点，合并为新的父节点，父节点权值为两节点权值之和
- 重复步骤2直至森林仅剩一棵二叉树，即得到目标霍夫曼树
- 关键指标：带权路径长度WPL = 所有叶子节点权值 × 其到根节点的路径长度之和，即为编码总长度。
- 考研常见考察形式：
- 选择题：前缀编码的判断、WPL计算、霍夫曼编码的优劣对比
- 计算题：给定权值集合构造霍夫曼树、计算WPL、生成对应编码表
问题与反思
- 对并查集路径压缩与按秩合并的底层代码实现细节理解不够透彻，容易混淆两种优化的触发条件
- 构造霍夫曼树时，偶尔会在选取最小权值节点时出现失误，需要加强构造练习
- 未结合408真题对应题型进行练习，后续需要补充针对性刷题巩固
收获与总结
- 掌握了并查集的基本操作与两种优化方式，明确了其在连通性问题中的核心应用场景
- 理解了霍夫曼树与霍夫曼编码的原理，能够独立完成简单的霍夫曼树构造与WPL计算
- 明确了408考试中这两个知识点的考察形式与重点方向，为后续刷题奠定了基础
- 今日学习节奏合理，两个半小时的专注学习完成了既定目标，后续可保持该学习强度 💡 碎碎念：踏实吃透每一个知识点！
文档内容由 AI 辅助生成
分享
如果这篇文章对你有帮助，欢迎分享给更多人！
考研专业课学习记录2026-06-26
https://elysiaweb.vercel.app/posts/408/6-26/ 部分信息可能已经过时
相关文章 智能推荐