# 软考软件设计师 · 每日一练 | 2026-04-21

软考软件设计师 · 每日一练 | 2026-04-21

距离2026上半年软考（5月23-26日）还有32天！
今日专题：图论算法（最短路径/最小生成树/拓扑排序/关键路径）/ 编译原理（编译vs解释/文法分类/有限自动机）

一、选择题精练（10题）

【1】图论·Dijkstra算法（数据结构）

关于Dijkstra算法，下列说法正确的是（ ）。

A. 可以处理带负权边的图
B. 适用于求解所有顶点对之间的最短路径
C. 使用贪心策略，每次选择当前距离源点最近的顶点
D. 时间复杂度为 O(V²)，无法优化

答案：C

解析：

Dijkstra算法核心特征：

• 贪心策略：每次从未访问顶点中选距离源点最近的，加入已确定最短路径集合
• 不能处理负权边（A错）：负权边可能导致已确定的最短路径被更新
• 单源最短路径（B错）：只求从一个源点到所有其他顶点的最短路径；求所有顶点对之间用Floyd算法
• 时间复杂度（D错）：邻接矩阵 O(V²)，邻接表+最小堆 O((V+E)logV)

Dijkstra手算步骤：

1. 初始化：dist[源点]=0，其余=∞；所有顶点标记为未访问 2. 从未访问顶点中选 dist 最小的顶点 u 3. 标记 u 为已访问（已确定最短路径） 4. 更新 u 的所有邻接顶点 v：dist[v] = min(dist[v], dist[u] + weight(u,v)) 5. 重复步骤2-4，直到所有顶点已访问或目标顶点已访问

注意：Dijkstra是贪心算法，但不保证全局最优（仅无负权时正确）。

【2】图论·最小生成树（数据结构）

使用Kruskal算法求解最小生成树，其核心思想是（ ）。

A. 每次选择与当前生成树相连的权值最小的边
B. 每次选择图中权值最小且不形成回路的边
C. 从一个顶点出发，每次扩展到最近的未访问顶点
D. 通过动态规划逐步求解最优解

答案：B

解析：

Kruskal算法：

• 策略：将所有边按权值从小到大排序，依次选取，若不形成回路则加入生成树
• 判回路方法：使用并查集（Union-Find）判断两个端点是否在同一连通分量
• 适用场景：稀疏图（边少的图）效率高
• 时间复杂度：O(E log E)（排序主导）

Prim算法对比：

• 策略：从一个起点开始，每次选择与当前生成树相连的最小权边（A选项描述的是Prim）
• 适用场景：稠密图（边多的图）效率高
• 时间复杂度：邻接矩阵 O(V²)，邻接表+最小堆 O((V+E)logV)

Kruskal vs Prim：

维度	Kruskal	Prim
核心策略	按边权排序，选最小不构成回路的边	从一个顶点扩展，选相连最小权边
数据结构	并查集	最小堆/优先队列
适用场景	稀疏图（边少）	稠密图（边多）
时间复杂度	O(E log E)	O(V²) 或 O((V+E)logV)
起点要求	任意（不需要起点）	需要指定起点

真题速记：Kruskal = “边排序 + 并查集”，Prim = “顶点扩展 + 最小堆”

【3】图论·拓扑排序（数据结构）

对一个有向图进行拓扑排序，下列说法正确的是（ ）。

A. 拓扑排序的结果是唯一的
B. 有回路的有向图也能进行拓扑排序
C. 拓扑排序通常使用深度优先搜索或不断删除入度为0的顶点来实现
D. AOV网的拓扑排序结果中，所有顶点的最早开始时间都相同

答案：C

解析：

拓扑排序（Topological Sort）：

• 适用：有向无环图（DAG，Directed Acyclic Graph）
• A错：拓扑排序结果不唯一（多个入度为0的顶点时可以任选）
• B错：有回路的图不能进行拓扑排序
• D错：拓扑排序只确定执行顺序，不涉及时间计算

两种实现方法：

方法一：Kahn算法（BFS思想，入度表法） 1. 计算所有顶点入度 2. 将所有入度为0的顶点入队 3. 出队一个顶点，将其邻接顶点入度减1 4. 若邻接顶点入度变为0，入队 5. 重复直到队列为空 6. 若输出顶点数 < 总顶点数 → 有回路 方法二：DFS后序逆序法 1. 对图进行DFS遍历 2. 在顶点离开递归时记录（后序） 3. 将后序序列逆序 → 拓扑序列

AOV网 vs AOE网：

• AOV网：顶点表示活动，边表示先后关系 → 拓扑排序
• AOE网：边表示活动，顶点表示事件 → 关键路径

【4】图论·关键路径（数据结构）

在AOE网中，关键路径是指（ ）。

A. 从源点到汇点经过边数最多的路径
B. 从源点到汇点路径长度最短的路径
C. 从源点到汇点的最长路径，其上的活动为关键活动
D. 从源点到汇点的最短路径，其上的活动为关键活动

答案：C

解析：

关键路径（Critical Path）：

• 定义：AOE网中从源点到汇点的最长路径
• 含义：完成整个工程所需的最短时间（最长路径决定了工程最少需要的时间）
• 关键活动：关键路径上的活动（边），它们的延迟会直接导致整个工程延迟

四个核心时间参数：

事件（顶点）： VE(v) — 事件v的最早发生时间（从源点到v的最长路径） VL(v) — 事件v的最迟发生时间（不拖延总工期的最晚时间） 活动（边）： e(i) — 活动的最早开始时间 = 该边起点的VE l(i) — 活动的最迟开始时间 = 该边终点的VL - 该边的持续时间 关键活动：e(i) == l(i) 的活动（时间余量为0） 关键路径：由所有关键活动组成的路径

手算步骤：

1. 正向求VE：从源点开始，VE(v) = max{VE(u) + weight(u,v)} 2. 逆向求VL：从汇点开始，VL(v) = min{VL(w) - weight(v,w)} 3. 求各活动的 e 和 l 4. 找 e == l 的活动 → 关键活动 5. 关键活动串起来 → 关键路径

易错点：

• 关键路径可能不止一条
• 缩短关键活动不一定能缩短总工期（可能产生新的关键路径）
• 关键路径上所有活动的时间余量都为0

【5】图论·图的存储（数据结构）

对于有n个顶点、e条边的无向图，采用邻接矩阵存储，则该矩阵的大小为（ ）。

A. n × e
B. n × n
C. (n+1) × (n+1)
D. e × e

答案：B

解析：

图的存储结构对比：

维度	邻接矩阵	邻接表
空间复杂度	O(V²)	O(V + E)
适用场景	稠密图（边多）	稀疏图（边少）
判断两顶点是否相邻	O(1)	O(度数)
求顶点的度	无向图：行/列之和O(V)	无向图：链表长度O(1)
有向图入度/出度	行=出度，列=入度	出度查链表，入度需遍历
存储方式	二维数组	顶点数组 + 链表/指针

邻接矩阵特点：

• 无向图的邻接矩阵是对称矩阵
• 对角线元素表示自环（一般无向图无自环，为0）
• 空间 O(V²)，与边数无关

选择建议：

• 稠密图（E 接近 V²）→ 邻接矩阵
• 稀疏图（E 远小于 V²）→ 邻接表

【6】编译原理·编译vs解释（程序设计语言）

关于编译程序和解释程序，下列说法正确的是（ ）。

A. 编译程序不生成目标程序，边翻译边执行
B. 解释程序生成独立的目标程序文件
C. 编译程序的执行效率通常高于解释程序
D. 解释程序不需要词法分析和语法分析

答案：C

解析：

编译 vs 解释：

维度	编译（Compiler）	解释（Interpreter）
工作方式	先翻译，后执行	边翻译，边执行
目标程序	生成独立目标程序	不生成独立目标程序
执行效率	高（已编译）	低（每次都要翻译）
调试便利	差（需重新编译）	好（逐行执行）
跨平台	差（目标代码绑定平台）	好（源代码级跨平台）
典型语言	C、C++、Go	Python、JavaScript、Ruby
混合模式	—	Java（先编译为字节码，再解释执行JIT）

A错：编译程序生成目标程序；B错：解释程序不生成独立目标程序；D错：解释程序同样需要词法分析和语法分析。

Java的特殊性：先编译成字节码（.class），再由JVM解释执行（或JIT编译为机器码），属于半编译半解释。

【7】编译原理·文法分类（程序设计语言）

Chomsky将文法分为四类，其中正规文法（正则文法）对应的是（ ）。

A. 0型文法
B. 1型文法
C. 2型文法
D. 3型文法

答案：D

解析：

Chomsky文法四类：

类型	名称	产生式限制	对应自动机	典型应用
0型	短语文法	α → β（α至少含1个非终结符）	图灵机	自然语言
1型	上下文有关文法	αAβ → αγβ（|γ| ≥ 1）	线性有界自动机	编程语言语义
2型	上下文无关文法	A → γ（A是非终结符）	下推自动机	语法分析（语法树）
3型	正规文法（正则文法）	A → aB 或 A → a（右线性）/ A → Ba 或 A → a（左线性）	有限自动机	词法分析（token识别）

软考核心考点：

3型文法（正规文法）= 有限自动机（FA）= 词法分析 2型文法（上下文无关文法）= 下推自动机（PDA）= 语法分析 词法分析器的理论基础：有限自动机 语法分析器的理论基础：上下文无关文法

记忆技巧：数字越大限制越多、能力越弱。3型最严格 → 只能用A→aB这种简单形式 → 用最简单的有限自动机就能处理。

【8】编译原理·有限自动机（程序设计语言）

关于DFA和NFA，下列说法正确的是（ ）。

A. DFA的状态转换函数对每个状态和输入符号有且仅有一个后继状态
B. NFA不能转换为DFA
C. DFA和NFA识别的语言不同
D. NFA比DFA的识别能力更强

答案：A

解析：

DFA vs NFA：

维度	DFA（确定性）	NFA（非确定性）
状态转换	每个状态+输入 →唯一后继	每个状态+输入 →多个后继或无
ε转移	不允许	允许（不加输入也可转移）
识别能力	与NFA等价	与DFA等价
空间效率	状态数可能更多	状态数通常更少
时间效率	更快（无需回溯）	更慢（可能需要回溯）

B错：NFA可以通过子集构造法转换为DFA
C错：DFA和NFA识别的语言完全相同（都是正规语言/正则语言）
D错：两者识别能力等价

关键转换链：

正规式 ↔ NFA ↔ DFA ↔ 最小化DFA（DFA Minimization） 正规式 → NFA：Thompson构造法 NFA → DFA：子集构造法（每个DFA状态 = NFA状态的一个子集） DFA → 最小化DFA：状态等价划分（ Hopcroft算法）

真题常考：给一个NFA状态图，求对应的DFA状态转换表。

【9】编译原理·编译过程（程序设计语言）

编译程序的工作过程通常不包括（ ）。

A. 词法分析
B. 语法分析
C. 需求分析
D. 目标代码生成

答案：C

解析：

编译过程五大阶段：

源程序 ↓ ① 词法分析（Lexical Analysis） → 输入：字符流 → 输出：Token序列（单词符号） → 任务：识别标识符、关键字、常数、运算符、界符 ② 语法分析（Syntax Analysis / Parsing） → 输入：Token序列 → 输出：语法树（AST） → 任务：根据文法规则检查语法是否正确 → 错误处理：括号不匹配、缺少分号等 ③ 语义分析（Semantic Analysis） → 输入：语法树 → 输出：带类型信息的语法树 → 任务：类型检查、作用域检查、语义一致性检查 → 例：int a = "hello" → 类型错误 ④ 中间代码生成 + 代码优化（可选） → 输入：带类型信息的语法树 → 输出：中间代码（如三地址码） → 优化：常量折叠、公共子表达式消除、循环优化等 ⑤ 目标代码生成 → 输入：中间代码 → 输出：目标机器代码（.o / .exe） → 任务：寄存器分配、指令选择、指令调度

需求分析（C选项）是软件工程的阶段，不是编译过程的阶段！

【10】图论·DFS遍历（数据结构）

对无向图进行深度优先搜索（DFS），使用邻接表存储，其时间复杂度为（ ）。

A. O(V)
B. O(E)
C. O(V + E)
D. O(V × E)

答案：C

解析：

图的遍历时间复杂度：

遍历方式	邻接矩阵	邻接表
DFS	O(V²)	O(V + E)
BFS	O(V²)	O(V + E)

邻接表存储：

• 访问每个顶点：O(V)
• 遍历每个顶点的邻接链表：所有链表总长为 2E（无向图）或 E（有向图）
• 总计：O(V + E)

邻接矩阵存储：

• 访问每个顶点：O(V)
• 对每个顶点扫描整行/列找邻接顶点：O(V)
• 总计：O(V²)

DFS vs BFS本质区别：

DFS（深度优先）：栈（递归调用栈）→ 一条路走到黑 → 回溯 BFS（广度优先）：队列 → 一层一层扩展 → 最短路径（无权图）

二、图论算法·核心知识体系

2.1 最短路径算法对比

单源最短路径 所有顶点对最短路径 无负权边 Dijkstra O(V²)/O((V+E)logV) Floyd O(V³) 允许负权边 Bellman-Ford O(V×E) Floyd O(V³) 允许负权回路 不可能求出最短路径 不可能求出最短路径 Dijkstra: 贪心，单源，无负权 Bellman-Ford: 动态规划，单源，可检测负权回路（V-1轮松弛后还能松弛 → 有负权回路） Floyd: 动态规划，三重循环，所有顶点对 状态转移: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

2.2 最小生成树算法对比

Kruskal: 1. 所有边按权值排序 2. 依次取最小边，不构成回路则加入（并查集判断） 3. 选够 V-1 条边停止 时间: O(E log E) 适合: 稀疏图 Prim: 1. 任选起点加入集合 2. 找到与集合相连的最小权边，将新顶点加入集合 3. 重复直到所有顶点加入 时间: O(V²) 或 O((V+E)logV) 适合: 稠密图 MST性质: - 最小生成树可能不唯一（有等权边时） - 但MST的总权值唯一 - n个顶点的连通图，MST恰好有 n-1 条边

2.3 拓扑排序速记

适用: 有向无环图（DAG） 方法: 入度表法（BFS思想） 步骤: 1. 统计所有顶点入度 2. 入度为0的顶点入队 3. 出队 → 输出 → 邻接顶点入度-1 4. 新的入度为0的顶点入队 5. 重复直到队空 判断有环: 输出顶点数 < 总顶点数 → 有回路 应用: 任务调度、课程先修关系、Make工具

2.4 关键路径·计算模板

AOE网: 边=活动（有权值），顶点=事件 正向求VE（最早发生时间）: VE(源点) = 0 VE(v) = max{VE(前驱u) + weight(u,v)} 逆向求VL（最迟发生时间）: VL(汇点) = VE(汇点) VL(v) = min{VL(后继w) - weight(v,w)} 活动时间: 最早开始 e(i) = VE(活动起点) 最迟开始 l(i) = VL(活动终点) - weight 关键活动: e(i) == l(i)（时间余量 = 0） 关键路径: 关键活动组成的路径 注意: - 关键路径可能不止一条 - 缩短关键活动不一定缩短总工期 - 所有事件VE == VL 的都在关键路径上

三、编译原理·核心知识体系

3.1 编译过程全景图

源程序 → [词法分析] → [语法分析] → [语义分析] → [中间代码生成] → [代码优化] → [目标代码生成] → 目标程序 ↓ ↓ ↓ Token序列 语法树(AST) 带类型信息的AST 符号表管理 + 错误处理 贯穿全过程

3.2 文法四类速记

限制越来越强 能力越来越弱 自动机越来越简单 0型 短语文法 ←————————————→ 图灵机 1型 上下文有关 ←————————————→ 线性有界自动机 2型 上下文无关 ←————————————→ 下推自动机（栈） 3型 正规文法 ←————————————→ 有限自动机 关联记忆: 3型 → 有限自动机 → 词法分析（识别token） 2型 → 下推自动机 → 语法分析（构造语法树） 正规文法产生式形式: 右线性: A → aB 或 A → a （a是终结符，B是非终结符） 左线性: A → Ba 或 A → a

3.3 有限自动机转换链

正规式 ——Thompson——→ NFA ——子集构造——→ DFA ——最小化——→ 最小DFA 子集构造法（NFA→DFA）: - 每个DFA状态 = NFA状态的一个子集 - 需要计算ε-closure（ε闭包） - 新状态名称用花括号表示，如 {q0,q1,q2} DFA最小化: - 将状态分为终态组和非终态组 - 检查每个组内的状态是否对每个输入符号都转到同一组 - 不满足则拆分，直到不能再拆分为止 - 最终每个组 = 最小DFA的一个状态

3.4 编译vs解释·核心区别

编译: 先翻译成目标代码 → 保存为文件 → 执行目标代码 优点: 执行效率高 缺点: 开发调试慢、跨平台差 代表: C/C++/Go/Rust 解释: 逐行读取源代码 → 翻译 → 立即执行 优点: 调试方便、跨平台好 缺点: 执行效率低 代表: Python/JavaScript/Ruby/PHP 混合模式: Java/C# 先编译为中间代码（字节码）→ 运行时由虚拟机解释/JIT编译执行

四、图的存储与遍历·速记

4.1 邻接矩阵 vs 邻接表

邻接矩阵（二维数组）: - 无向图: 对称矩阵 - 空间: O(V²) - 查邻接: O(1) - 适合稠密图 邻接表（数组+链表）: - 空间: O(V + E) - 查邻接: O(度数) - 适合稀疏图 - 无向图: 每条边存两次 - 有向图: 方便查出度，查入度需遍历（或建逆邻接表）

4.2 DFS vs BFS

DFS（深度优先）: 数据结构: 栈（递归） 特点: 一条路走到黑，然后回溯 应用: 拓扑排序、连通分量、回溯法 适用: 寻找所有解、检测连通性 BFS（广度优先）: 数据结构: 队列 特点: 一层一层扩展 应用: 最短路径（无权图）、层次遍历 适用: 寻找最近/最短解

五、今日记忆卡片

六、倒计时提醒

📅 今天：2026-04-21（周二） 📋 距软考：32天 ⏰ 冲刺阶段建议： ✓ 上午手算Dijkstra最短路径 + Kruskal最小生成树（给图手算！） ✓ 下午练习关键路径计算（VE/VL/关键活动判断） ✓ 晚上背诵文法四类 + 编译过程六阶段 ✓ 整理正规式↔NFA↔DFA转换链的解题模板

昨日回顾：排序算法完整时间复杂度表（8种算法对比/稳定与不稳定/快排最坏O(n²)）、快速排序一趟模拟与堆排序步骤、二叉树遍历速记与由前序中序构造二叉树、完全二叉树叶子节点公式、UML类图六种关系从弱到强、CMM五级口诀与CMMI连续式0-3级、状态模式核心与vs策略模式对比
明日预告：操作系统（进程调度算法/内存管理/文件系统）、数据库（SQL高级查询/事务隔离级别）、软件工程（软件测试策略/质量保证）