# 软考软件设计师 · 每日一练 | 2026-04-20
软考软件设计师 · 每日一练 | 2026-04-20
距离2026上半年软考（5月23-26日）还有33天！
今日专题：排序算法 / 二叉树遍历与构造 / UML类图 / CMM与CMMI / 状态模式
一、选择题精练（10题）
【1】排序算法·时间复杂度（数据结构）
下列排序算法中，在最坏情况下时间复杂度为 O(n log n) 的是（ ）。
A. 快速排序
B. 堆排序
C. 冒泡排序
D. 插入排序
答案：B
解析：
- 堆排序在最好、最坏、平均情况下时间复杂度均为O(n log n)，是最稳定的 O(n log n) 排序算法。
- 快速排序平均 O(n log n)，最坏 O(n²)（已排序数组 + 固定选枢轴）
- 归并排序最好、最坏、平均均为 O(n log n)，但需要 O(n) 额外空间
- 冒泡/插入排序最坏 O(n²)
排序算法时间复杂度总览：
算法 最好 平均 最坏 空间 稳定 冒泡 O(n) O(n²) O(n²) O(1) ✅ 插入 O(n) O(n²) O(n²) O(1) ✅ 选择 O(n²) O(n²) O(n²) O(1) ❌ 快速 O(n log n) O(n log n) O(n²) O(log n) ❌ 归并 O(n log n) O(n log n) O(n log n) O(n) ✅ 堆排序 O(n log n) O(n log n) O(n log n) O(1) ❌ 希尔 O(n) O(n^1.3) O(n²) O(1) ❌ 基数 O(d(n+k)) O(d(n+k)) O(d(n+k)) O(n+k) ✅
【2】排序算法·稳定性（数据结构）
下列排序算法中，不稳定的是（ ）。
A. 冒泡排序
B. 归并排序
C. 堆排序
D. 插入排序
答案：C
解析：堆排序不稳定。例如序列 [3, 3, 1]：
- 建堆后 3 和 3 的相对位置可能被交换
- 排序完成后原来在前面的 3 可能跑到后面
稳定性含义：对于值相同的元素，排序后相对位置不变。
记忆口诀：
"不稳定的三剑客"：快排、堆排、选择排 其余常见排序（冒泡、插入、归并、基数）都是稳定的为什么不稳定？
- 快速排序：枢轴划分时可能跨越相同元素
- 堆排序：建堆/调整堆时可能改变同值元素顺序
- 选择排序：每次选最小值与前面交换时可能跨越同值元素
【3】排序算法·快速排序趟数（数据结构）
对序列 {49, 38, 65, 97, 76, 13, 27, 49} 进行快速排序（升序），以第一个元素为枢轴进行一趟排序后，序列变为（ ）。
A. {27, 38, 13, 49, 76, 97, 65, 49}
B. {13, 27, 38, 49, 65, 76, 97, 49}
C. {27, 38, 13, 49, 76, 97, 65, 49}
D. {38, 27, 13, 49, 65, 97, 76, 49}
答案：A
解析：以 49 为枢轴，使用双指针法：
初始: [49, 38, 65, 97, 76, 13, 27, 49] i→ ←j 步骤1: j从右向左找 < 49 的 → 49(停)，交换 → [27, 38, 65, 97, 76, 13, 49, 49] 步骤2: i从左向右找 > 49 的 → 65，交换 → [27, 38, 49, 97, 76, 13, 65, 49] 步骤3: j从右向左找 < 49 的 → 13，交换 → [27, 38, 13, 97, 76, 49, 65, 49] 步骤4: i从左向右找 > 49 的 → 97，交换 → [27, 38, 13, 49, 76, 97, 65, 49] 步骤5: i == j，一趟结束 最终: [27, 38, 13, 49, 76, 97, 65, 49] 枢轴49到达最终位置（第4个位置，下标3）注意：快速排序一趟排序的标志是——枢轴元素到达其最终排好序的位置。
【4】二叉树·遍历（数据结构）
某二叉树的前序遍历序列为 ABDFCE，中序遍历序列为 BFDACE，则该二叉树的后序遍历序列为（ ）。
A. FDBECA
B. FDBCEA
C. BFDCEA
D. BFDECA
答案：A
解析：已知前序+中序 → 确定二叉树 → 推后序
还原过程：
前序: A B D F C E → 根=A 中序: B F D A C E → A左边是左子树{B,F,D}，A右边是右子树{C,E} 左子树: 前序: B D F → 根=B 中序: B F D → B右边是{F,D}为右子树，无左子树 → B的右子树: 前序: D F → 根=D 中序: F D → D左边是{F}为左子树 右子树: 前序: C E → 根=C 中序: C E → C右边是{E}为右子树 还原出的二叉树: A / \ B C \ \ D E / F 后序遍历（左右根）: F → D → B → E → C → A = FDBECA ✅关键规则：
- 前序/后序定根，中序定左右子树
- 只有前序+中序或后序+中序才能唯一确定二叉树
- 前序+后序 不能唯一确定（无法区分单子树是左还是右）
【5】二叉树·节点计算（数据结构）
一棵完全二叉树有 700 个节点，则该二叉树有（ ）个叶子节点。
A. 349
B. 350
C. 351
D. 352
答案：B
解析：完全二叉树节点数 n = 700（偶数）。
完全二叉树叶子节点公式：
当 n 为偶数时：叶子节点数 = n / 2 = 350 当 n 为奇数时：叶子节点数 = (n + 1) / 2 或者统一公式： 设度为0的节点（叶子）为 n0，度为1的节点为 n1，度为2的节点为 n2 n = n0 + n1 + n2 完全二叉树中：n1 = 0 或 1 由二叉树性质 n0 = n2 + 1 n = n0 + n1 + (n0 - 1) = 2n0 + n1 - 1 → n0 = (n + 1 - n1) / 2 n=700(偶数) → n1=1 → n0 = (700 + 1 - 1) / 2 = 350 ✅ n=701(奇数) → n1=0 → n0 = (701 + 1 - 0) / 2 = 351速记：n 为偶数 → 叶子 = n/2；n 为奇数 → 叶子 = (n+1)/2
【6】二叉树·性质（数据结构）
一棵深度为 5 的满二叉树，其叶子节点数为（ ）。
A. 15
B. 16
C. 31
D. 32
答案：B
解析：满二叉树每一层都达到最大节点数。
深度为h的满二叉树: - 节点总数: 2^h - 1 = 2^5 - 1 = 31 - 叶子节点数: 2^(h-1) = 2^4 = 16 ✅ - 第k层节点数: 2^(k-1) 满二叉树 vs 完全二叉树: 满二叉树一定是完全二叉树 完全二叉树不一定是满二叉树（最后一层可能不满，但靠左连续）重要性质速记：
性质 公式 第k层最多节点 2^(k-1) 深度h最多节点 2^h - 1 n个节点完全二叉树深度 ⌊log₂n⌋ + 1 任意二叉树 n0 = n2 + 1
【7】UML·类图关系（软件工程）
在UML类图中，表示"组合（Composition）"关系的是（ ）。
A. 实线箭头 ———▶
B. 实线 + 空心菱形 ——◇
C. 实线 + 实心菱形 ——◆
D. 虚线箭头 - - -▶
答案：C
解析：
UML类图六种关系（从弱到强）：
关系 符号 含义 举例 依赖 - - -▶虚线箭头临时使用 方法参数类型 关联 ————实线长期引用 朋友关系 聚合 ——◇空心菱形整体-部分（弱） 部门和员工 组合 ——◆实心菱形整体-部分（强） 人和心脏 泛化 ——▷空心三角继承 猫是动物 实现 - - -▷虚线三角实现接口 鸟实现飞行接口 聚合 vs 组合（高频混淆点）：
- 聚合：部分可以独立于整体存在（空心菱形在整体端）
- 如：部门和员工（员工可以离开部门独立存在）
- 组合：部分的生命周期依赖于整体（实心菱形在整体端）
- 如：人和心脏（心脏不能脱离人独立存在）
【8】CMM·成熟度等级（软件工程）
CMM（能力成熟度模型）将软件过程的成熟度分为5个等级，其中"已管理级"是指（ ）。
A. 等级1
B. 等级2
C. 等级3
D. 等级4
答案：D
解析：
CMM五个等级：
等级 名称 核心特征 关键过程域（KPA）数 1级 初始级(Initial) 无序、混乱，成功靠个人英雄主义 无 2级 已管理级(Managed/Repeatable) 基本项目管理，有计划有跟踪 6个（需求管理、项目计划、项目跟踪等） 3级 已定义级(Defined) 过程标准化、制度化 7个（组织过程焦点、培训、集成软件管理等） 4级 定量管理级(Quantitatively Managed) 定量度量，可预测 2个（定量过程管理、软件质量管理） 5级 优化级(Optimizing) 持续改进，防止缺陷 3个（缺陷预防、技术变更管理、过程变更管理） 易混淆点：
- 2级"已管理"侧重项目管理（能跟踪成本进度）
- 3级"已定义"侧重过程标准化（组织级过程定义）
- 4级侧重定量控制（用数据说话）
- 5级侧重持续改进（主动预防缺陷）
速记口诀：初(1)乱、管(2)跟、定(3)标、量(4)数、优(5)改
【9】设计模式·状态模式（设计模式）
关于状态模式（State Pattern），下列说法错误的是（ ）。
A. 状态模式允许一个对象在其内部状态改变时改变它的行为
B. 状态模式将状态相关的行为局部化到不同状态类中
C. 状态模式和策略模式的结构相同，但意图不同
D. 状态模式中客户端需要直接切换具体的状态类
答案：D
解析：
状态模式核心：
- 意图：允许对象在内部状态改变时改变行为（对象看起来像是改变了类）
- 结构：Context 持有 State 接口引用，具体状态类实现 State 接口
- 关键：状态转换由具体状态类自己管理，客户端无需知道当前具体状态
D为什么错：状态模式中，状态转换通常在具体状态类内部完成（调用 context.setState()），客户端不需要直接操作具体状态类。这是状态模式的核心优势——对客户端透明。
状态模式 vs 策略模式（高频考点）：
维度 状态模式 策略模式 目的 状态决定行为 算法可替换 谁选策略/状态 对象自身根据状态切换 客户端主动选择 转换控制 状态类内部控制 客户端控制 数量关系 状态之间有转换关系 策略之间互相独立 类比 自动售货机（投币→选饮料→出饮料） 支付方式选择（微信/支付宝/现金） 代码模板：
// 状态接口interfaceState{voidhandle(Contextcontext);}// 具体状态AclassConcreteStateAimplementsState{voidhandle(Contextcontext){// 行为Acontext.setState(newConcreteStateB());// 状态转换}}// 上下文classContext{privateStatestate;voidrequest(){state.handle(this);}}
【10】CMMI·连续式 vs 阶段式（软件工程）
关于CMMI，下列说法正确的是（ ）。
A. CMMI只有阶段式表示方法
B. CMMI连续式中，能力等级最高为5级
C. CMMI阶段式中，成熟度等级4级是"已定义级"
D. CMMI连续式可以针对特定过程域进行能力评估
答案：D
解析：
CMMI两种表示法：
维度 阶段式 (Staged) 连续式 (Continuous) 评估对象 整个组织 特定过程域 度量单位 成熟度等级（1-5） 能力等级（0-3） 评估结果 一个等级（组织总体） 每个过程域一个等级 改进路径 固定顺序（由低到高） 灵活选择改进优先级 适用场景 组织整体评估 针对性改进特定过程 连续式能力等级（0-3级，注意与阶段式不同）：
- 0级：未完成（Incomplete）
- 1级：已执行（Performed）
- 2级：已管理（Managed）
- 3级：已定义（Defined）
C为什么错：阶段式4级是"定量管理级"，不是"已定义级"（3级才是已定义级）。
二、排序算法·核心知识体系
2.1 必考时间复杂度表
最好 平均 最坏 空间 稳定 冒泡排序 O(n) O(n²) O(n²) O(1) ✅ 插入排序 O(n) O(n²) O(n²) O(1) ✅ 选择排序 O(n²) O(n²) O(n²) O(1) ❌ 希尔排序 O(n) O(n^1.3) O(n²) O(1) ❌ 快速排序 O(n log n) O(n log n) O(n²) O(log n) ❌ 归并排序 O(n log n) O(n log n) O(n log n) O(n) ✅ 堆排序 O(n log n) O(n log n) O(n log n) O(1) ❌ 基数排序 O(d(n+k)) O(d(n+k)) O(d(n+k)) O(n+k) ✅2.2 快速排序核心思想
分治策略: 1. 选枢轴（pivot） 2. 划分（partition）：小于枢轴放左边，大于放右边 3. 递归排序左右子序列 关键点: - 一趟排序后，枢轴到达最终位置 - 最坏情况：已排序数组 + 固定选首元素 → O(n²) - 改进：随机选枢轴 / 三数取中法 - 不稳定排序（同值元素可能跨越）2.3 堆排序核心步骤
建堆（大顶堆）→ 逐步取堆顶 → 调整堆 1. 建堆：从最后一个非叶子节点开始，自下而上调整 - 最后一个非叶子节点下标: ⌊n/2⌋ - 1 2. 排序: - 交换堆顶（最大值）与末尾 - 堆大小减1 - 对新堆顶进行下沉调整 - 重复直到堆大小为1 时间复杂度: 建堆O(n) + n次调整O(log n) = O(n log n) 空间复杂度: O(1)（原地排序）2.4 软考排序真题套路
套路1: 给序列，问一趟快速排序后的结果 → 关键：记住枢轴到达最终位置 套路2: 问哪个排序在最坏/最好/平均情况下为O(n log n) → 归并和堆排永远是O(n log n) 套路3: 问排序稳定性 → "不稳定三剑客"：快排、堆排、选择排 套路4: 比较排序的最低时间复杂度 → O(n log n)，基于比较的排序不可能低于此（决策树下界）三、二叉树·核心知识体系
3.1 遍历顺序速记
先序遍历（根左右）: A → 左子树 → 右子树 中序遍历（左根右）: 左子树 → A → 右子树 后序遍历（左右根）: 左子树 → 右子树 → A 层次遍历: 一层一层从左到右（用队列实现） 记忆技巧: "先"记根先 → 根左右 "中"记根中 → 左根右 "后"记根后 → 左右根3.2 由遍历序列构造二叉树
✅ 前序 + 中序 → 唯一确定二叉树 ✅ 后序 + 中序 → 唯一确定二叉树 ✅ 层序 + 中序 → 唯一确定二叉树 ❌ 前序 + 后序 → 不能唯一确定（无法区分单子树方向） 构造步骤（以前序+中序为例）: 1. 前序第一个元素 = 根 2. 在中序中找到根，左边是左子树，右边是右子树 3. 递归处理左右子树3.3 二叉树关键性质
| 性质 | 公式/描述 |
|---|---|
| 二叉树第i层最多节点 | 2^(i-1) |
| 深度h最多节点 | 2^h - 1 |
| 叶子节点 n0 与 n2 | n0 = n2 + 1 |
| n个节点完全二叉树深度 | ⌊log₂n⌋ + 1 |
| 完全二叉树叶子节点 | n偶数: n/2; n奇数: (n+1)/2 |
| 满二叉树叶子节点 | 2^(h-1) |
3.4 线索二叉树
目的: 利用空指针存储遍历前驱/后继信息 n个节点的二叉树有 n+1 个空指针（n个节点有2n个指针域，n-1个非空指针） 线索化: 左指针为空 → 指向中序前驱（左线索） 右指针为空 → 指向中序后继（右线索） 附加标志位 ltag / rtag 区分是孩子指针还是线索 ltag = 0: lchild指向左孩子 ltag = 1: lchild指向前驱线索四、UML类图·关系强度排序
4.1 六种关系（从弱到强）
依赖 → 关联 → 聚合 → 组合 → 泛化(继承) → 实现 依赖(最弱): "临时用一下" 虚线箭头 - - -▶ 例: 方法参数引用其他类 关联: "长期有联系" 实线 ———— 例: 学生选课 聚合: "整体-部分(可分离)" 实线+空心菱形 ——◇ 菱形在整体端 例: 部门-员工（员工可独立存在） 组合: "整体-部分(不可分离)" 实线+实心菱形 ——◆ 菱形在整体端 例: 人-心脏（同生共死） 泛化/继承: "is-a" 实线+空心三角 ——▷ 例: 猫 → 动物 实现: "实现接口" 虚线+空心三角 - - -▷ 例: 鸟类 → 飞行接口4.2 多重性标记
1 → 恰好1个 0..1 → 0或1个 * → 0到多个 1..* → 1到多个（至少1个） 0..* → 等同于 * 例: 一个班级有1个班主任(1)，多个学生(1..*) 一个学生属于一个班级(1)五、CMM与CMMI·对比速记
5.1 CMM vs CMMI
| 维度 | CMM | CMMI |
|---|---|---|
| 全称 | 能力成熟度模型 | 能力成熟度模型集成 |
| 覆盖范围 | 仅软件工程 | 软件工程 + 系统工程 |
| 表示法 | 仅阶段式 | 阶段式 + 连续式 |
| 等级 | 1-5级 | 阶段式1-5级，连续式0-3级 |
5.2 CMM阶段式五级速记
1级-初始级: 乱! 个人英雄主义，成功靠运气 2级-已管理: 管项目! 有计划有跟踪，但组织无标准 3级-已定义: 定标准! 过程标准化，组织级过程资产 4级-定量管理: 用数据! 定量度量，可预测质量和进度 5级-优化级: 持续改! 预防缺陷，主动优化 口诀: 初乱-管跟-定标-量数-优改5.3 软考常考混淆
Q: CMM 2级的核心特征? A: 基本的项目管理（计划、跟踪、承诺） Q: CMM 3级和2级的区别? A: 2级是项目级过程，3级是组织级标准化过程 Q: CMMI连续式能力等级有几级? A: 0-3级（注意不是5级！） Q: "已定义级"是CMM几级? A: 3级! 不是4级六、设计模式·状态模式精讲
6.1 状态模式结构
┌──────────┐ ┌─────────────┐ │ Context │────→│ State │ │ (环境) │ │ (状态接口) │ │──────────│ │─────────────│ │ state │ │ handle() │ └──────────┘ └──────┬──────┘ │ ┌─────────┼─────────┐ ▼ ▼ ▼ ┌──────────┐┌──────────┐┌──────────┐ │ StateA ││ StateB ││ StateC │ │(具体状态) ││(具体状态) ││(具体状态) │ └──────────┘└──────────┘└──────────┘6.2 适用场景
✅ 一个对象的行为取决于它的状态，且必须在运行时根据状态改变行为 ✅ 代码中包含大量与状态相关的条件判断语句（if-else / switch） ✅ 状态转换规则复杂且状态较多 经典例子: - TCP连接状态管理（CLOSED → SYN_SENT → ESTABLISHED → ...） - 自动售货机（投币状态 → 选择状态 → 出货状态） - 文档编辑器（普通模式 → 编辑模式 → 预览模式）6.3 状态模式 vs 策略模式（真题必考）
| 维度 | 状态模式 | 策略模式 |
|---|---|---|
| 核心目的 | 状态决定行为 | 算法族可互换 |
| 切换者 | 状态对象自己切换 | 客户端主动切换 |
| 状态关系 | 状态之间有转换关系 | 策略之间互相独立 |
| 客户端感知 | 不知道当前状态 | 知道并选择策略 |
| 代码结构 | 相同（都是Context+接口+实现） | 相同 |
| 本质区别 | 意图不同！ | 意图不同！ |
七、今日记忆卡片
| 序号 | 知识点 | 关键记忆 |
|---|---|---|
| 1 | 不稳定三剑客 | 快排、堆排、选择排 |
| 2 | 堆排序复杂度 | 最好/最坏/平均都是O(n log n) |
| 3 | 快排最坏情况 | 已排序 + 固定枢轴 →O(n²) |
| 4 | 归并排序 | O(n log n) +稳定，但需O(n) 额外空间 |
| 5 | 构造二叉树 | 前序/后序 + 中序才能唯一确定 |
| 6 | 完全二叉树叶子 | n偶数:n/2; n奇数:(n+1)/2 |
| 7 | 满二叉树叶子 | 2^(h-1)，深度h的节点总数2^h - 1 |
| 8 | n0 与 n2 | 任意二叉树n0 = n2 + 1 |
| 9 | UML组合关系 | 实心菱形◆，部分不能独立于整体 |
| 10 | CMM等级 | 初乱(1)→管跟(2)→定标(3)→量数(4)→优改(5) |
| 11 | CMMI连续式 | 能力等级0-3级（不是5级！） |
| 12 | 状态模式 | 状态类自己管理状态转换，客户端不感知 |
八、倒计时提醒
📅 今天：2026-04-20（周一） 📋 距软考：33天 ⏰ 冲刺阶段建议： ✓ 上午刷排序算法题（手算快排一趟 + 堆排序建堆过程） ✓ 下午练习二叉树由遍历序列还原题目（前序+中序 → 后序） ✓ 晚上背诵UML六种关系符号 + CMM五级口诀 ✓ 整理设计模式状态模式 vs 策略模式的区别昨日回顾：页面置换算法三大对比（OPT/LRU/FIFO）、面向对象设计七大原则、DFD深化解题模板、风险管理四步走、知识产权高频考点、Scrum三角色五事件三工件
明日预告：图论算法（最短路径/最小生成树）、编译原理（正则表达式/有限自动机）、软件工程（需求工程/变更管理）