408 统考数据结构 (Data Structure) —— 知识库总览

本资料库汇集了 408 考研《数据结构》科目的全部核心大纲知识点，涵盖绪论、线性表、栈队列、串、树与二叉树、图、查找、排序八大章节。

---

📂 理论模块

• 01 绪论：时空复杂度计算法则及数据结构三要素。
• 02 线性表：顺序表与链表的实现及对比。
• 03 栈、队列和数组：特殊线性表的应用（括号匹配、表达式求值等）。
• 04 串：字符串模式匹配，主攻 KMP 算法及 next 数组推导。
• 05 树与二叉树：二叉树遍历、线索二叉树、哈夫曼树等极高频考点。
• 06 图：DFS/BFS 遍历、最短路径（Dijkstra/Floyd）、最小生成树（Prim/Kruskal）及拓扑排序。
• 07 查找：折半查找、B/B+ 树特性、散列表（Hash）及冲突解决。
• 08 排序：各类排序算法原理及对口应用场景对比分析。

🎯 提分与回顾

分值分布（数据结构约 45 分）：树与二叉树、图、查找、排序四章占绝大多数，且代码大题基本出自线性表 / 树 / 图。

必背速查

主题	一句话结论
完全二叉树结点 $i$	双亲 $\lfloor i/2\rfloor$，左孩子 $2i$，右孩子 $2i+1$
二叉树叶子数	$n_0=n_2+1$
平衡二叉树最少结点	$N(h)=N(h-1)+N(h-2)+1$
稳定排序	直接插入、冒泡、归并、基数
一趟后必有元素归位	冒泡、快排、简单选择、堆排
最短路径	Dijkstra 不能有负权；Floyd 可以
拓扑排序	出队数 $<n$ 即存在环

高频易错

1. 高度与深度、层次从 1 还是 0 开始，审题时先确认。
2. KMP 的 next 数组是否整体 +1，不同教材定义不同，按题目给出的为准。
3. 折半查找判定树必为平衡二叉树，$ASL$ 按判定树层数算。
4. 快排的最坏情况出现在基本有序时，不是随机时。
5. B 树的阶 $m$ 指最多孩子数；关键字数为 $m-1$。

💻 代码实现库

• 代码实现：针对 408 代码大题的全套框架（C / C++ 双轨，伪代码版与可运行版），并附代码题解题套路。