今日学习内容#

今日累计学习2小时，完整完成2020年全国硕士研究生招生考试计算机学科专业基础综合（408）真题中的数据结构模块两道综合应用题，同步整理错题思路与核心考点笔记。

AI知识点带复盘#

本次刷题覆盖了408数据结构两道高频核心大题考点，具体复盘如下：

1. 二叉树遍历与路径计算考点 2020年第41题结合中序+后序遍历序列构造二叉树，并求解根到叶子节点的最大路径和，属于数据结构常考综合题型。核心考点包括：
   • 二叉树遍历序列的还原逻辑：后序遍历序列的最后一个元素为根节点，通过中序遍历序列可将序列划分为根节点的左、右子树区间，递归完成整棵二叉树的构造；
   • 根到叶子路径和的求解思路：采用深度优先搜索（DFS）递归遍历每个节点，累加路径上的节点值，当遍历到叶子节点时记录当前路径和的最大值；
   • 延伸考点：该题型可变形为求解最小路径和、判断是否存在路径和等于给定值、输出所有符合条件的路径等，核心逻辑均基于递归遍历的路径累加。
2. 哈希表开放定址法的平均查找长度考点 2020年第42题考查线性探测再散列的哈希表查找成功与不成功的平均查找长度（ASL）计算，是哈希表模块的核心考点：
   • 线性探测再散列的冲突处理规则：H_i = (H(key) + d_i) % m，其中d_i = 1,2,...,m-1，发生冲突时依次向后探查直到找到空位置；
   • 查找成功的ASL计算：统计每个关键字在插入时的探查次数，求和后除以关键字总数；
   • 查找不成功的ASL计算：针对每个散列地址0~m-1，统计从该地址开始首次遇到空位置的探查次数，求和后除以散列表长度m； 结合本题给定的关键字序列{10,24,31,4,6,19,21,27,13,16}、散列函数H(key)=key%7与表长11，可完整推导两次ASL的计算结果，巩固了哈希表性能分析的实操方法。

问题与反思#

1. 二叉树构造环节中，对中序序列的左右子树区间划分边界偶尔出现失误，导致后续路径计算出错；
2. 哈希表查找不成功的ASL计算时，容易混淆探查次数的统计起点，曾误将空位置的位置计入而非探查次数；
3. 本次刷题总时长2小时，超出了考场单道大题建议20分钟的时间上限，解题速度有待提升，后续需加强限时刷题训练。

收获与总结#

1. 熟练掌握了二叉树遍历还原与路径类题型的标准化解题步骤，理清了递归遍历的核心逻辑；
2. 彻底厘清了线性探测哈希表的两种平均查找长度的计算规则，能够独立完成真题场景下的ASL推导；
3. 明确了408数据结构真题的命题风格与高频考点分布，后续刷题可针对性聚焦常考模块；
4. 意识到了考场时间把控的重要性，后续刷题将严格按照考试时长要求进行模拟训练。

💡 碎碎念：踏实吃透每一个知识点！

文档内容由 AI 辅助生成