909 字
3 分钟
软考中级软件设计师 · 知识点速查表
软考中级软件设计师 · 知识点速查表
整理时间：2026-04-22 来源：错题本精选
第一部分：数据结构
1.1 图
有向完全图 vs 无向完全图
| 类型 | 边数公式 | 说明 |
|---|---|---|
| 无向完全图 | n(n-1)/2 | 每对顶点之间1条边 |
| 有向完全图 | n(n-1) | 每对顶点之间2条边（双向） |
记忆口诀： 有向翻一番
邻接矩阵
| 图类型 | 非零元素个数 | 空间复杂度 |
|---|---|---|
| 有向图 | E | O(n²) |
| 无向图 | 2E（对称） | O(n²) |
最小生成树算法对比
| Prim | Kruskal | |
|---|---|---|
| 算法类型 | 贪心 | 贪心 |
| 思想 | 选最近顶点 | 选最短边 |
| 适合图类型 | 稠密图 | 稀疏图 |
| 时间复杂度 | O(n²) | O(eloge) |
| 实现方式 | 顶点集合 | 边集合 |
记忆口诀：
Prim：选点（就近）→ 适合密图Kruskal：选边（最短）→ 适合疏图判断环：并查集，同集合则环1.2 树
树中结点关系公式
n（总结点数）= 分支数 + 1分支数 = Σ 各结点度数之和树的总结点数 = 1 + Σ(各度级结点 × 该结点度数)解题步骤：
- 设叶子结点（度为0）个数为 n₀
- 结点总数 n = n₀ + 各度级结点之和
- 分支数 = Σ(各度级结点 × 该结点度数)
- 利用 n = 分支数 + 1 求解
1.3 数组
二维数组地址计算
行优先： LOC(i,j) = LOC(0,0) + (i×m + j) × L
列优先： LOC(i,j) = LOC(0,0) + (j×n + i) × L
| 符号 | 含义 |
|---|---|
| LOC(0,0) | 基地址 |
| i, j | 行、列下标（从0开始） |
| m | 列数（行优先时） |
| n | 行数（列优先时） |
| L | 每个元素占用的存储单元数 |
记忆口诀： 行优先：行×列数 + 列；列优先：列×行数 + 行
1.4 栈
表达式求值栈深度
核心方法： 中缀表达式 → 后缀表达式 → 模拟求值
后缀表达式求值步骤：
- 操作数入栈
- 遇到运算符弹出两个操作数，计算结果后入栈
- 栈的最大深度即为所需容量
快速判断技巧： 第一个运算符前有多少个操作数，栈容量至少就是多少
第二部分：算法
2.1 查找算法
折半查找（二分查找）ASL
判定树构造：
- 根节点 = 第1次比较的元素
- 左右子树 = 左右半部分，第2次比较的元素
- 以此类推…
ASL 计算公式：
成功查找 ASL = (各层结点数 × 该层层数) / 元素个数失败查找 ASL = (各外部结点比较次数之和) / 失败位置数 （失败位置数 = n + 1）分块查找 ASL
步骤：
- 在索引表中查找，确定元素在哪一块
- 在块内查找，找到目标元素
ASL 公式：
| 索引表查找 | 块内查找 | ASL |
|---|---|---|
| 顺序查找 | 顺序查找 | (m+1)/2 + (n/m+1)/2 |
| 折半查找 | 折半查找 | log₂(m+1) + log₂(n/m+1) |
n = 总元素数，m = 块数
记忆口诀： 分块查找 ASL = 索引表查找 + 块内查找
2.2 排序算法
时间复杂度对比
| 排序算法 | 最好 | 平均 | 最坏 | 空间 | 稳定性 |
|---|---|---|---|---|---|
| 直接插入 | O(n) | O(n²) | O(n²) | O(1) | ✅ 稳定 |
| 希尔排序 | O(n) | O(n^1.3) | O(n²) | O(1) | ❌ 不稳定 |
| 简单选择 | O(n²) | O(n²) | O(n²) | O(1) | ❌ 不稳定 |
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | ✅ 稳定 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n²) | O(logn) | ❌ 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | ❌ 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | ✅ 稳定 |
记忆要点
- 稳定排序： 直接插入、冒泡、归并
- 平均时间最优： 快速排序 O(nlogn)
- 空间复杂度最优： 堆排序 O(1)
- 最坏情况最优： 堆排序、归并排序 O(nlogn)
2.3 算法设计策略
分治法
三步骤： 分 → 治 → 合
分 → 划分问题为子问题治 → 递归求解子问题合 → 合并子问题的解典型应用： 最近点对问题、归并排序、快速排序
注意： 分治法在合并阶段只需检查有限范围，不是全部枚举
第三部分：高频考点速记
必背公式汇总
无向完全图边数：n(n-1)/2有向完全图边数：n(n-1)
树总结点数：分支数 + 1二叉树性质：n₀ = n₂ + 1（度为0的结点数 = 度为2的结点数 + 1）
数组行优先：LOC(i,j) = LOC(0,0) + (i×m + j) × L数组列优先：LOC(i,j) = LOC(0,0) + (j×n + i) × L
折半查找 ASL（成功）：(各层结点数 × 层数) / 元素个数折半查找 ASL（失败）：外部结点比较次数之和 / (n+1)
分块查找 ASL：(m+1)/2 + (n/m+1)/2（持续更新中）
分享
如果这篇文章对你有帮助，欢迎分享给更多人！
软考中级软件设计师 · 知识点速查表
https://www.rumin.top/posts/知识点速查表_软考软件设计师/ 部分信息可能已经过时