线性结构：山大真题的“隐形重灾区”
山大数据结构真题中，线性结构占比超35%，但考生常因“看似简单”而失分。2023年真题显示：循环链表判断环入口题正确率仅58%，远低于预期。
高频考点与真题案例：
- 数组与链表的对比陷阱：2022年选择题要求判断“在已排序数组中插入元素，时间复杂度最低为O(1)”——错误！实际为O(n)（需移动元素），体现对“逻辑操作”与“物理操作”的混淆。
- 栈的“双栈共享”应用：2024年简答题要求设计双栈共享一维数组空间，写出入栈/出栈算法，并分析栈满条件。
- 队列的循环实现：2021–2024连续四年考查“用数组实现循环队列”，2024年升级为“支持动态扩容的循环队列”。
- 广义表递归遍历：2023年算法题要求实现广义表深度计算（如((a,b),(c,(d)))的深度为3），考察递归思维深度。
山大命题特色：不考定义复述，而考“边界条件处理”与“异常场景设计”，如“空链表反转”“单节点栈弹出”等。
树与图：山大真题的“高分 battleground”
树与图内容占总分35%，是区分高分与低分的关键。2025年真题中，树相关题平均得分率仅52%，图相关题为48%，凸显难点集中。
树结构考查重点：
- 二叉树的三种遍历重建：2024年算法题给出前序+中序序列，要求重建二叉树并输出后序序列（需处理重复值场景）。
- 堆的应用扩展：2023年考题要求用最小堆实现“ Top-K 大元素”，并分析 O(n log k) 复杂度。
- 线索二叉树的构造与遍历：2022年简答题要求说明线索化如何避免递归/栈，2025年新增“动态线索化”（边遍历边线索化）。
- B树/B+树的应用：2021–2025连续五年考查数据库索引场景，2025年要求计算“10^6节点B+树（m=10）的高度范围”。
图结构考查重点：
- 图的存储结构选择：2024年填空题给出“稀疏图（边数≈顶点数）”，要求选择邻接表（O(V+E)）而非邻接矩阵（O(V²)）。
- 关键路径与AOE网：2023年程序设计题要求实现“带时间窗的关键路径”，即路径中各活动存在时间窗口约束。
- 最短路径变形：2025年算法题要求“带障碍物的网格图最短路径”，需结合 BFS 与状态记录（位置+已绕过障碍数）。
- 网络流建模：2022年综合题要求将“任务分配问题”转化为最大流问题（源点→任务→工人→汇点）。
排序与查找：从“代码实现”到“系统优化”
排序与查找占20%，山大近年强调“工程思维”。2025年真题中，一道“外部排序”题（10GB文件排序，内存2GB）平均得分仅3.2/10分。
排序算法考查要点：
- 稳定性证明：2024年简答题要求证明“快速排序不稳定”，需构造反例（如序列[2,1,1]）。
- 复杂度分析陷阱：2023年选择题“归并排序空间复杂度为O(1)”——错误！实际为O(n)（需辅助数组）。
- 外部排序实现：2025年程序设计题要求实现“多路归并外部排序”，需处理“内存块划分”“归并树构建”“I/O优化”。
- 排序在特定场景的优化：2022年考题“对几乎有序数组排序”，正确答案为插入排序（O(n)），而非快排（O(n log n)）。
查找算法考查要点：
- 二分查找边界处理：2021–2025连续五年考查“查找第一个≥x的元素”，易错点在循环条件与mid更新逻辑。
- 哈希查找的冲突处理：2024年简答题要求比较线性探测与二次探测的聚集现象差异。
- B树查找的路径优化：2025年算法题要求实现“B树查找时缓存父节点指针”，避免重复遍历。
动态存储管理：被忽视的“得分盲区”
动态存储管理占10%，但山大近年加大考查深度。2025年真题中，一道“内存池设计”题（要求支持固定大小对象分配与回收）正确率仅41%。
核心考查方向：
- 内存池设计：2023年程序设计题要求实现“对象池”，支持“分配（allocate）”“回收（deallocate）”“重用（reuse）”，并分析时间复杂度。
- 引用计数与循环引用：2024年简答题要求说明“如何避免循环引用导致的内存泄漏”，需结合弱引用（weak_ptr）。
- 智能指针模拟：2025年算法题要求手写“shared_ptr”与“unique_ptr”的简化版，考察析构逻辑与引用计数管理。
- RAII思想实现：2022年综合题要求设计“文件资源管理类”，确保异常情况下文件句柄正确关闭。
山大命题趋势：从“内存分配”转向“资源生命周期管理”，强调“无泄漏”与“异常安全”。