数据结构与算法

快拿分：复杂度阶的比较、排序稳定性与一趟排序结果、哈夫曼 WPL、图的拓扑/关键路径、哈希冲突处理——上午极高频；下午算法题则抓 循环边界与变量初值。

一、知识与应试（考点·难点·知识点合一）

1.1 复杂度与线性结构

• 渐近：(O,\Omega,\Theta)；递归式常见用展开法或主定理。
• 栈队列：表达式、括号；循环队列判满（牺牲单元或 size）。
• 〔真题〕：问「平均/最坏」须看清题干限定。

1.1.1 复杂度阶速记

[ O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) ]

数据结构三要素：逻辑结构、存储结构、数据运算。题目若问“数据结构包括什么”，不要只答线性表、树、图这些逻辑结构。

1.2 树与堆

• 二叉树性质：(n_0=n_2+1)；深度与结点数关系。
• BST：中序有序；退化链最坏 (O(n))。
• 堆：建堆 (O(n))；堆排序不稳定。
• 哈夫曼：(n) 叶子 → (2n-1) 个结点；WPL 最小。

1.3 图

• 存储：邻接矩阵稠密、邻接表稀疏。
• 遍历：BFS/DFS；拓扑排序（无环 DAG）；关键路径（AOE 最早/最迟时间）。
• 〔易错〕：Dijkstra 不适用负权边（除非题改）。

1.4 排序与查找

排序	平均时间	最坏时间	空间	稳定？
直接插入	(O(n^2))	(O(n^2))	(O(1))	稳
冒泡	(O(n^2))	(O(n^2))	(O(1))	稳
简单选择	(O(n^2))	(O(n^2))	(O(1))	不稳
希尔	与增量有关	与增量有关	(O(1))	不稳
快排	(O(n\log n))	(O(n^2))	(O(\log n))	不稳
堆排	(O(n\log n))	(O(n\log n))	(O(1))	不稳
归并	(O(n\log n))	(O(n\log n))	(O(n))	稳
基数	(O(d(n+r)))	(O(d(n+r)))	(O(r))	稳

• B+ 树：叶子链、适合 DB 索引（与 B 树对比为常考点）。

1.4.1 查找高频

查找	前提	平均/典型复杂度	考点
顺序查找	无序/有序均可	(O(n))	监视哨可减少判断
折半查找	有序顺序表	(O(\log n))	不能用于链表
分块查找	块间有序、块内可无序	索引查找 + 块内查找	常考“块间有序，块内无序”
哈希查找	哈希函数与冲突处理	接近 (O(1))	装填因子影响冲突

1.5 算法思想（DP / 分治 / 贪心）

范式	识别关键词	典型复杂度（记阶）
动态规划	重叠子问题、最优子结构；背包/切割/LCS	常 (O(n^2))、(O(nW))、(O(mn))
分治	独立子问题 + 合并；假币/归并/快排/二分	常 (O(n\log n))、(O(\log n))
贪心	局部最优；活动安排、分数背包、霍夫曼	常 (O(n\log n))（含排序）

• 分治 vs DP：子问题 是否重叠——重叠用 记表（DP），不重叠 分治+合并。
• 贪心 vs DP：0-1 背包用 DP；分数背包可 贪心（按单位价值）。
• 回溯：解空间搜索 + 剪枝（n 皇后、Hamilton），与上三者不同。

举例、决策流程图、经典题复杂度全表 → 算法设计填空 §〇。

二、速记与背诵

• 不稳记三堆希快选（堆、希尔、快排、选择排序——按常见考法）。
• 稳定记直冒归基（直接插入、冒泡、归并、基数）。
• KMP：next[j] = 前缀后缀最长公共长度相关（按教材定义填）。
• 完全二叉树高度：(\lfloor\log_2 n\rfloor+1) 与 (\lceil\log_2(n+1)\rceil) 等价类表述看清选项。

三、考场检查

• 排序题：问「某一趟之后序列」必须 按该算法真实执行，不可凭感觉。
• 图题：拓扑有序序列可能不唯一，选项中合法即可。