【数据结构】复习日：树 + 图 + 排序（整理对比表）-171主机测评

适合读者：软考中级备考同学
阅读时间：8分钟
内容：二叉树、图、排序三大模块核心对比表、易错点、记忆口诀汇总

一、二叉树部分

1.1 二叉树五大性质

性质编号内容公式应用场景

性质1	第 $i$ 层最多节点数	$2^{i-1}$	求某一层最多能放多少个节点
性质2	深度为 $k$ 的二叉树最多节点数	$2^k – 1$	求一棵树最多能有多少节点
性质3	叶子节点数与度为2的节点数关系	$n_0 = n_2 + 1$	选择题必考，已知叶子求二度节点
性质4	满二叉树高度 $h$ 的节点数	$n = 2^h – 1$ ，叶子 $2^{h-1}$	满二叉树计算
性质5	完全二叉树节点 $i$ 的左/右/父节点	左 $2 i$ ，右 $2 i + 1$ ，父 $⌊i/2⌋\\lfloor i/2 \\rfloor$	顺序存储的数组下标计算

1.2 满二叉树 vs 完全二叉树

对比项满二叉树完全二叉树

叶子节点位置	全部在最底层	只能在最后两层
非叶子节点	都有两个子节点	每个节点度 $≤2\\le 2$
节点数	恰好 $2^h – 1$	不一定
顺序存储	可以	可以（重点）
关系	满二叉树一定是完全二叉树	完全二叉树不一定是满二叉树

1.3 二叉树的遍历对比

遍历方式访问顺序根节点位置实现方式

前序	根 → 左 → 右	第一个	递归/栈
中序	左 → 根 → 右	中间	递归/栈
后序	左 → 右 → 根	最后一个	递归/栈
层次	上 → 下，左 → 右	第一个	队列

还原规律：前序/后序定根，中序分左右。前序+后序不能唯一确定二叉树。

1.4 二叉排序树（BST） vs 平衡二叉树（AVL）

对比项二叉排序树（BST）平衡二叉树（AVL）

定义	左小右大，递归定义	BST + 平衡因子 $≤1\\le 1$
中序遍历	递增有序	递增有序
查找效率	平均 $O(log⁡n)O(\\log n)$ ，最坏 $O (n)$	始终 $O(log⁡n)O(\\log n)$
插入/删除	直接插入或删除	可能需要旋转调整
适用场景	数据动态变化不剧烈	频繁查找、对效率要求高

二、图部分

2.1 图的基本术语速查

术语含义关键公式

无向图	边无方向	度之和 $\\times \|E\|$
有向图	边有方向	入度之和 $=$ 出度之和 $= ∣ E ∣$
连通图（无向）	任意两顶点有路径	至少 $n - 1$ 条边
强连通图（有向）	任意两顶点有双向路径	至少 $n$ 条边（环）
完全图（无向）	任意两顶点都有边	$n (n - 1) /2$ 条边
完全图（有向）	任意两顶点都有双向边	$n (n - 1)$ 条边
连通分量	无向图的极大连通子图	—

2.2 邻接矩阵 vs 邻接表

对比项邻接矩阵邻接表

空间复杂度	$O(n^2)$	$O (n + e)$
判断边是否存在	$O (1)$ （直接查）	$O (d e g r ee)$ （遍历链表）
求某顶点度（无向图）	$O (n)$ （统计一行）	$O (1)$ （链表长度）
适合图类型	稠密图	稀疏图
实现复杂度	简单	较复杂

无向图邻接表：所有链表的节点总数 $= 2 e$ （每条边存两次）

2.3 DFS vs BFS

对比项DFS（深度优先）BFS（广度优先）

核心数据结构	栈（递归）	队列
遍历策略	一条路走到黑，回溯	层层推进，先近后远
生成树形态	高瘦	矮胖
最短路径	❌ 不适合	✅ 适合（无权图）
空间复杂度	$O (n)$ （递归栈）	$O (n)$ （队列）
时间复杂度（邻接表）	$O (n + e)$	$O (n + e)$

2.4 最小生成树：Prim vs Kruskal

对比项Prim算法Kruskal算法

贪心对象	每次选连接已选/未选集合的最小边	每次选全局最小边，不形成环则加入
数据结构	邻接矩阵 / 优先队列	并查集
时间复杂度	$O(n^2)$ / $\\log n)$	$\\log e)$
适合图类型	稠密图	稀疏图
是否需要起点	需要指定起点	不需要

2.5 最短路径：Dijkstra vs Floyd

对比项Dijkstra算法Floyd算法

解决的问题	单源最短路径	多源最短路径
核心思想	贪心（每次选dist最小的顶点）	动态规划（三重循环）
核心循环顺序	选点 + 松弛	$k$ 在最外层（中转点）
时间复杂度	$O(n^2)$ / $\\log n)$	$O(n^3)$
是否支持负权边	❌ 不支持	✅ 支持（不能有负权环）
空间复杂度	$O (n)$	$O(n^2)$

三、排序部分

3.1 八大排序全景对比表

排序算法平均时间复杂度最好情况最坏情况空间复杂度稳定性

插入排序	$O(n^2)$	$O (n)$	$O(n^2)$	$O (1)$	✅ 稳定
希尔排序	$O(n^{1.3})$	$O (n)$	$O(n^2)$	$O (1)$	❌ 不稳定
冒泡排序	$O(n^2)$	$O (n)$	$O(n^2)$	$O (1)$	✅ 稳定
快速排序	$\\log n)$	$\\log n)$	$O(n^2)$	$O(log⁡n)O(\\log n)$	❌ 不稳定
简单选择	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O (1)$	❌ 不稳定
堆排序	$\\log n)$	$\\log n)$	$\\log n)$	$O (1)$	❌ 不稳定
归并排序	$\\log n)$	$\\log n)$	$\\log n)$	$O (n)$	✅ 稳定
基数排序	$O (d (n + r))$	$O (d (n + r))$	$O (d (n + r))$	$O (n + r)$	✅ 稳定

3.2 稳定性记忆

稳定（4个）不稳定（4个）

插入排序	希尔排序
冒泡排序	简单选择排序
归并排序	堆排序
基数排序	快速排序

记忆口诀：插冒归基（稳定），快选堆希（不稳定）

3.3 与初始顺序无关的算法

算法说明

简单选择排序	比较次数始终为 $n (n - 1) /2$
归并排序	始终对半分割
堆排序	复杂度稳定
基数排序	只按位分配，不依赖顺序

3.4 场景选型速查

应用场景推荐算法理由

数据基本有序	插入排序	接近 $O (n)$
数据量大、要求稳定	归并排序	$\\log n)$ 且稳定
数据量大、内存紧张	堆排序	$O (1)$ 空间
平均性能要求最高	快速排序	平均最快
固定位数数据（学号/身份证）	基数排序	不依赖比较，效率极高

四、易错点汇总

易错点正确理解

满二叉树一定是完全二叉树	✅ 正确
完全二叉树一定是满二叉树	❌ 错误（完全二叉树不一定是满二叉树）
二叉排序树的中序遍历是递减有序	❌ 是递增有序
折半查找要求数据按升序排列	❌ 升序或降序均可，但必须有序
平衡二叉树的平衡因子只能是 $- 1$ 或 $1$	❌ 可以是 $- 1, 0, 1$
有向图中所有顶点的入度之和等于边数	✅ 正确
强连通图至少需要 $n - 1$ 条边	❌ 至少需要 $n$ 条边（构成环）
连通图至少需要 $n$ 条边	❌ 至少需要 $n - 1$ 条边
无向图邻接表中所有链表节点总数为 $e$	❌ 是 $2 e$
DFS使用队列，BFS使用栈	❌ DFS用栈，BFS用队列
Prim算法适合稀疏图	❌ Prim适合稠密图，Kruskal适合稀疏图
Dijkstra可以处理负权边	❌ 不能处理负权边
Floyd算法中转点应放在最内层	❌ 中转点 $k$ 应放在最外层
堆排序是稳定排序	❌ 堆排序不稳定
快速排序在所有情况下都很快	❌ 最坏情况 $O(n^2)$ （已有序且基准选第一个时）

五、记忆口诀

二叉树性质：

第 $i$ 层最多 $2^{i-1}$ ，深度 $k$ 满 $2^k – 1$ ， $n_0 = n_2 + 1$ ，完全二叉树编号灵：左 $2 i$ 右 $2 i + 1$ 。

遍历：

前序根左右，中序左根右，后序左右根，层次用队列。

图术语：

连通图 $n - 1$ ，强连通图 $n$ ，完全图 $n (n - 1) /2$ （无向）或 $n (n - 1)$ （有向）。

图存储：

邻接矩阵 $O(n^2)$ 适稠密，邻接表 $O (n + e)$ 适稀疏。

最小生成树：

Prim从顶点长，稠密图它最强；Kruskal从边合，稀疏图它最妥。

最短路径：

Dijkstra贪心单源，负权边不能沾；Floyd动态多源， $k$ 最外层是关键。

排序稳定性：

插冒归基（稳定），快选堆希（不稳定）。

六、进度回顾

板块完成篇数状态

1. 计算机系统知识	28篇	✅ 已完成
2. 程序语言与编译	16篇	✅ 已完成
3. 操作系统	28篇	✅ 已完成
4. 软件工程	24篇	✅ 已完成
5. 面向对象技术	16篇	✅ 已完成
6. 数据结构与算法	30篇	✅ 已完成
7. 数据库技术	20篇	即将开始

七、下期预告：板块7 – 数据库技术

预计更新 20篇，主要内容：

数据库系统概述与三级模式
数据模型（层次/网状/关系）
关系代数与SQL
规范化理论（1NF/2NF/3NF/BCNF）
事务管理与并发控制
数据库设计（ER图）

请持续关注本专栏，每日更新，陪你一起拿下软考中级！

🔔 本专栏日更，点击头像 → 专栏《软考中级高频考点》订阅，第一时间接收新内容

【数据结构】复习日：树 + 图 + 排序（整理对比表）

一、二叉树部分

1.1 二叉树五大性质

1.2 满二叉树 vs 完全二叉树

1.3 二叉树的遍历对比

1.4 二叉排序树（BST） vs 平衡二叉树（AVL）

二、图部分

2.1 图的基本术语速查

2.2 邻接矩阵 vs 邻接表

2.3 DFS vs BFS

2.4 最小生成树：Prim vs Kruskal

2.5 最短路径：Dijkstra vs Floyd

三、排序部分

3.1 八大排序全景对比表

3.2 稳定性记忆

3.3 与初始顺序无关的算法

3.4 场景选型速查

四、易错点汇总

五、记忆口诀

六、进度回顾

七、下期预告：板块7 – 数据库技术

相关推荐

评论抢沙发

热门标签

热门文章

最新文章

归档

分类

一、二叉树部分

1.1 二叉树五大性质

1.2 满二叉树 vs 完全二叉树

1.3 二叉树的遍历对比

1.4 二叉排序树（BST） vs 平衡二叉树（AVL）

二、图部分

2.1 图的基本术语速查

2.2 邻接矩阵 vs 邻接表

2.3 DFS vs BFS

2.4 最小生成树：Prim vs Kruskal

2.5 最短路径：Dijkstra vs Floyd

三、排序部分

3.1 八大排序全景对比表

3.2 稳定性记忆

3.3 与初始顺序无关的算法

3.4 场景选型速查

四、易错点汇总

五、记忆口诀

六、进度回顾

七、下期预告：板块7 – 数据库技术

相关推荐

评论 抢沙发

热门标签

热门文章

最新文章

归档

分类

评论抢沙发