数据结构期末总览(线性表、栈与队列、树与二叉树、图、查找、排序):核心概念、对照表和易错点

作者:SeekFlaw 求瑕 内容组 · 发布于 2026-11-19 · 更新于 2026-11-19

先说结论

这是数据结构的期末总览,主线是「抓结构定义与基本运算 → 存储方式与复杂度 → 典型算法的执行过程」:线性表、栈队列、树与二叉树、图、查找、排序六块各自回答三个问题——怎么存、怎么操作、代价多大。用法:先看导图文字版,再默写排序对照表和图算法对照表,然后手工模拟样题的执行过程。

适用范围

按《数据结构》(C 语言 / 通用描述)通行教材整理,只写教材通行、可以逐条验证的结论;红黑树、AVL 的完整删除过程、外部排序、KMP 的细节这页只点到或没有展开。伪代码风格、章节顺序和考核方式各校不同,以你所用教材和老师的大纲为准。

用这张图开始复习

导图文字版

以下是这张导图的文字大纲,可以按层级直接复制。

  • 数据结构
    • 复杂度
      • 时间复杂度看基本操作执行次数随问题规模 n 增长的数量级,常见阶:O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
      • 双重循环 for i in 1..n、内层 for j in 1..i 的基本语句执行 n(n + 1)/2 次,是 O(n²)
    • 线性表
      • 顺序表:随机访问 O(1),在第 i 个位置插入或删除要移动其后的元素,平均约移动 n/2 个,是 O(n)
      • 单链表:头插 O(1),按位置查找要从头遍历,是 O(n);插入删除不用移动元素,但要先找到前驱
      • 循环链表、双向链表是对单链表的改进:前者首尾相连,后者能直接找到前驱
    • 栈与队列
      • 栈后进先出,队列先进先出;栈用于括号匹配、表达式求值、递归的实现
      • 循环队列(队满时留一个空位):队空 front = rear,队满 (rear + 1) mod m = front,元素个数 (rear − front + m) mod m
      • 入栈顺序为 1、2、3 时,合法的出栈序列共 5 种(卡特兰数 C(2n, n)/(n + 1),n = 3 时为 5)
    • 树与二叉树
      • 性质:n = n₀ + n₁ + n₂,n₀ = n₂ + 1(n₀ 为叶子数,n₂ 为度为 2 的结点数);第 i 层最多 2^(i−1) 个结点,高度为 h 的二叉树最多 2^h − 1 个结点
      • 完全二叉树有 n 个结点时高度为 ⌊log₂n⌋ + 1
      • 遍历:前序、中序、后序、层序;前序 + 中序或后序 + 中序能确定一棵二叉树,前序 + 后序不能
      • 二叉排序树的中序遍历是递增序列;平衡二叉树任一结点左右子树高度差不超过 1,失衡时通过 LL、RR、LR、RL 四种旋转调整
      • 哈夫曼树:带权路径长度 WPL 最小的二叉树;每次取权最小的两棵合并,WPL 等于所有合并出的内部结点的权之和;哈夫曼编码是前缀码
    • 图
      • 无向图所有顶点度数之和 = 2e;n 个顶点的无向完全图有 n(n − 1)/2 条边
      • 存储:邻接矩阵空间 O(n²),邻接表空间 O(n + e)
      • 遍历:广度优先用队列,深度优先用递归或栈;用邻接表存储时时间都是 O(n + e)
      • 最小生成树:Prim 从顶点出发扩展,适合稠密图;Kruskal 按边权从小到大选边并避免成环,适合稀疏图
      • 最短路径:Dijkstra 求单源最短路径,要求边权非负;Floyd 求任意两点间最短路径,时间 O(n³)
      • 拓扑排序针对有向无环图(DAG);图中有环时排序不能完成
    • 查找
      • 顺序查找:等概率时查找成功的平均查找长度 ASL = (n + 1)/2
      • 折半查找要求线性表有序且是顺序存储;n 个元素的判定树高度 ⌊log₂n⌋ + 1,也是最坏比较次数
      • B 树是平衡的多路查找树,m 阶 B 树每个结点最多 m 个孩子(最多 m − 1 个关键字)
      • 哈希表:装填因子 α = n/m;冲突处理有线性探测(可能堆积)和链地址法
    • 排序
      • 稳定性:相等关键字排序后相对次序不变;插入、冒泡、归并、基数排序稳定,简单选择、希尔、快速、堆排序不稳定
      • 基于比较的排序,最坏情况下的比较次数下界是 Ω(n log n)
      • 直接插入排序的移动次数等于序列的逆序对数

翻几张试试

点一下问题看答案,先自己想一想再翻。

一棵二叉树有 5 个度为 2 的结点、3 个度为 1 的结点,一共有多少个结点?

n₀ = n₂ + 1 = 6,总数 6 + 3 + 5 = 14。

前序 ABDECF,中序 DBEAFC,后序是什么?

DEBFCA。

权值 5、9、12、13、16、45 的哈夫曼树,WPL 是多少?

各次合并的和 14 + 25 + 30 + 55 + 100 = 224。

序列 49、38、65、97、76、13、27、49 的逆序对数是多少?它和直接插入排序的移动次数有什么关系?

逆序对数 15,直接插入排序移动次数等于它,也是 15。

11 个元素的有序表做折半查找,成功时的 ASL 和最坏比较次数各是多少?

ASL = 33/11 = 3,最坏比较次数 ⌊log₂11⌋ + 1 = 4。

对照表:排序算法,图的四个常考算法

排序算法平均时间最坏时间空间稳定性
直接插入O(n²)O(n²)O(1)稳定
冒泡O(n²)O(n²)O(1)稳定
简单选择O(n²)O(n²)O(1)不稳定
希尔取决于增量序列取决于增量序列O(1)不稳定
快速O(n log n)O(n²)平均 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)稳定
图算法解决什么关键条件典型复杂度
Prim最小生成树连通无向带权图邻接矩阵 O(n²),适合稠密图
Kruskal最小生成树连通无向带权图,用并查集判环O(e log e),适合稀疏图
Dijkstra单源最短路径边权非负朴素实现 O(n²)
Floyd任意两点最短路径无负权回路O(n³)

用法:先默写表,再用具体序列和具体图手算一遍(见例 4、例 5),算完核对稳定性、比较次数这些容易错的项。

带演算的例题

  • 例 1(二叉树结点数):一棵二叉树中度为 2 的结点有 5 个,度为 1 的结点有 3 个,则 n₀ = n₂ + 1 = 6,总结点数 6 + 3 + 5 = 14。完全二叉树有 12 个结点时,高度 ⌊log₂12⌋ + 1 = 3 + 1 = 4。检验:高度为 3 的二叉树最多 2³ − 1 = 7 个结点,12 > 7,高度为 4 的二叉树最多 15 个结点,12 ≤ 15,所以高度是 4。
  • 例 2(由遍历序列还原二叉树):前序序列 ABDECF,中序序列 DBEAFC。前序首个结点 A 是根,在中序中 A 左边的 DBE 是左子树、右边的 FC 是右子树。左子树前序 BDE,根 B,中序 D B E,所以 D 是左孩子、E 是右孩子;右子树前序 CF,根 C,中序 F C,所以 F 是 C 的左孩子。后序序列:DEBFCA。检验:用后序的最后一个结点 A 是根,与前序首个结点一致。
  • 例 3(哈夫曼树):权值 5、9、12、13、16、45。合并 5 + 9 = 14;12 + 13 = 25;14 + 16 = 30;25 + 30 = 55;45 + 55 = 100。WPL = 14 + 25 + 30 + 55 + 100 = 224。检验:45 在深度 1,12、13、16 在深度 3,5、9 在深度 4,WPL = 45 × 1 + (12 + 13 + 16) × 3 + (5 + 9) × 4 = 45 + 123 + 56 = 224。
  • 例 4(最小生成树与最短路径):6 个顶点 A–F,边 AB = 4、AC = 1、BC = 2、BD = 5、CD = 8、CE = 10、DE = 3、DF = 6、EF = 7。Kruskal 按权从小到大选:AC(1)、BC(2)、DE(3) 选中,AB(4) 与 AC、BC 成环舍去,BD(5)、DF(6) 选中,此时已有 5 条边,EF(7)、CD(8)、CE(10) 都会成环,舍去。MST 权值 1 + 2 + 3 + 5 + 6 = 17。Dijkstra 从 A 出发:C = 1,B = 1 + 2 = 3,D = 3 + 5 = 8,E = 8 + 3 = 11,F = 8 + 6 = 14。检验:MST 边数 = 顶点数 − 1 = 5;Dijkstra 中 E 经 C 直达 1 + 10 = 11,与经 D 的 8 + 3 = 11 相等,路径不唯一,距离是 11。
  • 例 5(排序):序列 49、38、65、97、76、13、27、49。直接插入排序(从后向前比较、不设哨兵的写法):逆序对数 15,元素后移 15 次,比较 20 次(比较次数随写法略有不同),结果 13、27、38、49、49、65、76、97。冒泡排序(一趟没有交换就结束):比较 27 次,交换 15 次(交换次数等于逆序对数)。快速排序以首元素 49 为枢轴,一趟划分后得到 27、38、13、49、76、97、65、49,枢轴落在下标 3(从 0 起算),左边都小于等于 49,右边都大于等于 49。
  • 例 6(折半查找与哈希):(a) 有序表 11 个元素做折半查找,判定树各层元素个数 1、2、4、4,等概率成功时 ASL = (1 × 1 + 2 × 2 + 4 × 3 + 4 × 4)/11 = 33/11 = 3,最坏比较 4 次。(b) 哈希函数 H(k) = k mod 13,表长 13,线性探测,依次插入 19、14、23、1、68、20、84、27、55、11:19 → 6,14 → 1,23 → 10,1 先落在 1 号已占用、探到 2,68 → 3,20 → 7,84 先落在 6、7 已占用、探到 8,27 先落在 1、2、3 已占用、探到 4,55 先落在 3、4 已占用、探到 5,11 → 11。比较次数依次 1、1、1、2、1、1、3、4、3、1,成功查找 ASL = 18/10 = 1.8。

易错点

  • 错法:认为前序 + 后序也能确定二叉树。正确:只有前序 + 中序或后序 + 中序能确定;前序 + 后序无法区分单个孩子是左孩子还是右孩子。
  • 错法:把完全二叉树和满二叉树混为一谈。正确:满二叉树每层都是满的;完全二叉树只要求按层序编号后与同高满二叉树的前 n 个位置一一对应,最后一层靠左排列。
  • 错法:对有负权边的图用 Dijkstra。正确:Dijkstra 要求边权非负;有负权边时用其他算法,Floyd 还要求没有负权回路。
  • 错法:背稳定性时把简单选择排序当作稳定。正确:稳定的是插入、冒泡、归并、基数;简单选择、希尔、快速、堆排序都不稳定。
  • 错法:以为快速排序任何时候都是 O(n log n)。正确:平均 O(n log n),最坏 O(n²),例如序列已有序而枢轴取首元素时。
  • 错法:对链式存储的线性表做折半查找。正确:折半查找需要按下标随机访问,只适用于有序的顺序存储表;链表只能顺序查找。
  • 错法:循环队列判空判满条件都写成 front = rear。正确:留一个空位时队空是 front = rear,队满是 (rear + 1) mod m = front,不留空位则要另设计数器或标志。
  • 错法:认为 Kruskal 每次选的边只要最小就行,不判断是否成环。正确:每选一条边要先判断两端点是否已在同一连通分量,是则舍去(例 4 中的 AB、EF、CD)。

常见问题

数据结构期末先复习哪几块?
一般按线性表、栈和队列、树与二叉树、图、查找、排序六块复习,范围以老师的大纲为准。先默写排序算法对照表和图算法对照表,再用具体数据手工模拟遍历、建哈夫曼树、最小生成树、排序、哈希插入的过程。
排序算法的稳定性怎么记?
稳定的是直接插入、冒泡、归并、基数排序;不稳定的是简单选择、希尔、快速、堆排序。可以拿两个相等的元素手工排一遍序,看它们的先后顺序有没有变。
已知前序和中序遍历怎么还原二叉树?
前序的首个结点是根,在中序中找到它,左边是左子树、右边是右子树,再对两棵子树递归处理。例 2 中前序 ABDECF、中序 DBEAFC,得到后序 DEBFCA。
Prim 和 Kruskal 有什么区别?
都求最小生成树。Prim 从一个顶点出发每次加入连接已选顶点集与未选顶点集的权最小的边,邻接矩阵实现是 O(n²),适合稠密图;Kruskal 对所有边按权排序、依次选边并避免成环,适合稀疏图。
折半查找的最坏比较次数怎么算?
对 n 个元素的有序顺序表,最坏比较次数等于判定树的高度 ⌊log₂n⌋ + 1。n = 11 时为 4。成功查找的平均查找长度要按判定树每层的元素个数加权。

用这张图开始复习

用我的资料做一张

相关页面

依据与局限

依据:《数据结构》通行教材线性表、栈队列、树与二叉树、图、查找、排序各章的定义、性质与算法表述;公式已逐条核对,例题已逐步演算并用程序重新计算验证(树还原、哈夫曼 WPL、最小生成树与最短路径、排序比较次数和移动次数、折半查找 ASL、哈希探测次数)。局限:不含红黑树、AVL 删除的完整过程、外部排序和 KMP 的细节;各校教材、伪代码风格和考试范围不同,以教材和老师为准;不预测考什么,不承诺提分。

标签:数据结构期末复习数据结构总结二叉树遍历还原哈夫曼树WPL最小生成树Kruskal排序算法稳定性折半查找ASL哈希线性探测