每日选做题单汇总

本页整理课程提供的两份 OpenJudge / LeetCode 每日选做题单：

• pre_problem_list_2025spring.md：寒假预习题单
• problem_list_2025spring.md：学期内每日练习题单

为便于复习，下面按主题聚合代表性题目。若需要查看完整题单，可前往本地文件：

• D:\Frank\Academic\大四上\data_structure\pre_problem_list_2025spring.md
• D:\Frank\Academic\大四上\data_structure\problem_list_2025spring.md

复习建议

• 优先刷标注为"必须会"和 Medium 难度的题目。
• 同一类题集中练习，掌握模板后再跨主题混合。
• 上机考试重点考察"识别算法框架"，所以每道题做完后要能说出用了什么数据结构/算法。

1. 链表与指针

核心技巧

• 反转链表：三指针迭代或递归。
• 倒数第 N 个：快慢指针。
• 回文链表：快慢指针找中点 + 反转后半部分 + 比较。

2. 栈与队列

核心技巧

• 出栈序列合法性：用栈模拟。
• 中缀转后缀 / 后缀求值：栈的经典应用。
• 单调栈：维护递增/递减序列，处理"下一个更大/更小元素"类问题。

3. 字符串与 KMP

核心技巧

• KMP：手写 next 数组是笔试重点。
• Trie：前缀匹配、字符串集合查询。

4. 二叉树

核心技巧

• 遍历：前序、中序、后序、层序。
• 重建：前序 + 中序、中序 + 后序。
• BST 性质：中序有序，用于验证和搜索。

5. 图论基础

核心技巧

• 图存储：邻接矩阵 vs 邻接表。
• 遍历：BFS、DFS。
• 最短路：Dijkstra（非负权）、Floyd（多源）、Bellman-Ford（负权）。
• 最小生成树：Prim、Kruskal。
• 拓扑排序：Kahn 算法 / DFS 后序逆序。

6. 并查集

核心技巧

• 路径压缩 + 按秩合并保证近似 $O(\alpha(n))$。
• 带权并查集（食物链类问题）。

7. 堆与 Trie

核心技巧

• 堆：向下调整、向上调整、建堆 $O(n)$、堆排序。
• Trie：节点按字符分叉，适合前缀查询。

8. 排序与二分

核心技巧

• 归并排序：逆序对计数常用。
• 二分：明确边界、循环不变量。
• 快速选择 / 第 K 大元素。

9. 动态规划

核心技巧

• 状态定义、状态转移、初始化、遍历顺序。
• 树形 DP：后序遍历收集子树信息。

10. 回溯与搜索

核心技巧

• 回溯 = 深度优先搜索 + 状态恢复。
• 剪枝：提前终止不可能的分支。

11. 贪心与滑动窗口

核心技巧

• 贪心：证明最优性通常是难点，考试中多为直观贪心。
• 滑动窗口：维护窗口内统计信息，根据条件收缩左边界。

完整题单位置

如需按日期顺序查看全部题目，请参考本地文件：

• D:\Frank\Academic\大四上\data_structure\pre_problem_list_2025spring.md
• D:\Frank\Academic\大四上\data_structure\problem_list_2025spring.md