计科八股20260605——软件生命周期、文档、死锁、地址转换、I/O控制方式、堆、无向图、连通图、最小支配集、逆关系、永真式

Q：软件的生命周期和软件文档怎么理解

一、软件生命周期（6个阶段）

软件生命周期 = 一个软件从“出生”到“死亡”的全过程

注意：很多面试官会把运维和废弃/下线也算进去，所以有时会说是7个阶段。

二、每种开发模型对应的生命周期特点

面试时可以说的：

“现代开发大多用敏捷，但文档在不同公司要求不同。有的用敏捷说‘不写文档’，但核心文档（需求、接口、部署）还是要有的，只不过写得更轻量。”

三、软件文档分类（三/四大类）

四、你至少要记住的6个核心文档

面试时不要背全量，关键是要说出这些文档解决了什么问题（沟通、边界、交接、运维）。

拷问1：敏捷开发说“不写文档”，那文档重要吗？

答：文档不是为“写”而存在，是为沟通、交接、维护服务。敏捷追求“可工作的软件胜过详尽的文档”，但完全没文档的问题很早就暴露了——比如核心人员离职后，新来的根本看不懂系统。

结论：文档要简但关键，接口文档、部署文档、核心业务逻辑必须留下来。

A：“软件生命周期一般分为可行性分析、需求分析、设计、编码、测试、运维六个阶段。不同的开发模型会调整迭代方式，比如瀑布是线性推进，敏捷是迭代式。

文档大体分三类：开发文档（给开发看）、管理文档（给项目负责人看）、用户文档（给用户看）。其中最核心的文档包括：需求规格说明书、概要设计、详细设计、测试报告、用户手册、运维手册。

我理解文档的价值不是‘写得多’，而是降低沟通成本和维护成本。尤其是在团队协作或交接时，关键信息如果只靠口头或代码注释，很容易丢失。”

以下为笔试内容：

Q：操作系统

1.死锁进程数

典型题目：

5 个进程，每个最多需要 3 个资源，系统最少需要多少个资源才一定不会死锁？

答案：5 × (3-1) + 1 = 11 个

2.逻辑地址转物理地址

典型题目：

已知页式存储系统中，页面大小为 4KB，逻辑地址为 12000。页表内容：页号0→块号2，页号1→块号5，页号2→块号3，页号3→块号7。求物理地址。

解题步骤：

1. 页面大小 4KB = 4096 字节

2. 逻辑地址 12000 ÷ 4096 = 2 余 3808（商=页号，余数=页内偏移）

3. 查页表：页号 2 → 块号 3

4. 物理地址 = 块号 × 页大小 + 偏移 = 3 × 4096 + 3808 = 12288 + 3808 =16096

Q：计算机组成原理

一、程序查询方式

程序查询方式是指CPU通过执行I/O指令，主动、定期地检查外部设备的状态寄存器，判断设备是否准备好传送数据。只有当设备就绪时，CPU才执行数据传送指令；否则CPU循环等待，直至设备就绪。

二、程序中断方式

程序中断方式是当外部设备准备好传送数据或发生异常情况时，设备主动向CPU发送中断请求信号。CPU在每条指令执行完毕后检测中断请求，若收到请求且允许中断，则暂停当前正在执行的程序，保存现场，转去执行相应的中断服务程序完成数据传送，传送完成后恢复现场，返回原程序继续执行。

三、DMA（直接内存存取）方式

DMA方式是指利用专门的DMA控制器硬件，在不经过CPU的情况下，直接控制外部设备与主存之间进行批量数据传送。CPU只需在传送开始时对DMA控制器进行初始化（设置传送数据块的起始地址、数据长度和传送方向），之后由DMA控制器接管总线完成数据传送，传送结束后DMA控制器向CPU发出中断信号通知传送完成。

四、通道方式

通道方式是一种更高级的I/O控制方式。通道是一个专门的I/O处理器，拥有自己的指令系统，能够独立执行通道程序。CPU只需执行一条I/O指令启动通道，通道便可根据预先存放在主存中的通道程序，自主地控制多个I/O设备与主存之间的数据传送，传送期间CPU与通道并行工作。传送完成后，通道向CPU发出中断请求。

二、核心区别（面试/笔试答题要点）

三、一句话总结

• 程序查询：CPU又当爹又当妈，一直盯着设备看

• 程序中断：CPU当妈，设备哭一声才过去喂一口

• DMA：CPU请了个保姆搬东西，搬完喊一声

• 通道：CPU请了个管家，给张任务清单，管家自己安排人干完

Q：数据结构

1. 堆排序

题目：

对序列 [49, 38, 65, 97, 76, 13, 27, 49] 进行堆排序（建大根堆），写出初始堆和每一趟排序后的结果。

步骤：

• 建堆（从最后一个非叶子节点开始向下调整）

• 交换堆顶和堆尾，堆长度减1，再调整堆顶

• 重复直到堆长度为1

初始堆：从位置(n/2-1)开始调整

常见考点：

• 堆排序时间复杂度：O(n log n)

• 空间复杂度：O(1)（原地排序）

• 不稳定排序

ps：我今天才知道堆排序是找子节点的最大/最小节点。

2. 无向图求环（伪代码 + 时间复杂度）

题目：

给定一个无向图 G(V,E)，判断图中是否存在环。请写出伪代码并分析时间复杂度。

思路：用并查集（Union-Find）

def has_cycle(V, edges): parent = [i for i in range(V)] def find(x): if parent[x] != x: parent[x] = find(parent[x]) return parent[x] def union(x, y): parent[find(x)] = find(y) for u, v in edges: if find(u) == find(v): return True # u和v已经连通，再加这条边就形成环 union(u, v) return False

时间复杂度：O(E × α(V))，其中 α(V) 是阿克曼函数的反函数，近似常数。几乎就是 O(E)

也可以用 DFS：访问过程中遇到已访问且不是父节点的点，则有环。复杂度 O(V+E)

3. 强连通图

题目：

什么是有向图的强连通分量？如何求？时间复杂度是多少？

定义：有向图中，任意两个顶点之间互相可达，则称该图为强连通图。极大强连通子图称为强连通分量。

算法：Kosaraju 或 Tarjan

Kosaraju 思路：

1. 对原图做一次 DFS，记录完成时间（压栈）

2. 构建反图（所有边反向）

3. 按栈顺序（完成时间逆序）在反图上做 DFS，每次 DFS 访问到的节点属于同一个强连通分量

时间复杂度：O(V+E)

Q：离散数学

1. 最小支配集

题目：

什么是图的最小支配集？给定一个图，求它的一个最小支配集。

定义：支配集 D 是顶点集的一个子集，使得图中每个顶点要么在 D 中，要么与 D 中某个顶点相邻。最小支配集是顶点数最少的支配集（NP-难问题，通常用近似算法或暴力搜索）

小图求最小支配集的思路：从所有顶点开始，尝试删掉某些点，检查剩余集合是否仍能支配全图。

例题：一个三角形（3 个顶点两两相连）

• 任选一个顶点，它可以支配自己+相邻两个顶点，所以一个顶点就够

• 最小支配集大小 = 1

2. R^-1（逆关系）与关系的性质

题目：

设 R 是集合 A 上的关系。R^-1 表示 R 的逆关系。证明：若 R 是自反的，则 R^-1 也是自反的。

定义回顾：

• 自反：对所有 a∈A，有 (a,a)∈R

• 对称：若 (a,b)∈R，则 (b,a)∈R

• 传递：若 (a,b)∈R 且 (b,c)∈R，则 (a,c)∈R

• 逆关系：R^-1 = {(b,a) | (a,b)∈R}

证明：

• 若 R 自反，则对任意 a∈A，(a,a)∈R

• 由逆关系定义，(a,a)∈R ⇒ (a,a)∈R^-1

• 所以 R^-1 也自反

对称性：若 R 对称，则 R = R^-1
传递性：逆关系不一定保持传递性，需要额外条件

3. 任意和存在结合表达式判断永真式

题目：

判断以下公式是否为永真式（永真式在所有解释下都为真）：
(∀x∃y P(x,y)) → (∃y∀x P(x,y))

思路：

• 这个公式不是永真式

• 左边 ∀x∃y P(x,y)：对每个 x，存在一个 y（可能依赖 x）使 P(x,y) 成立

• 右边 ∃y∀x P(x,y)：存在一个 y，对所有 x 都有 P(x,y) 成立

• 左边推不出右边：例如 P(x,y) 表示 "x = y"

  • ∀x∃y (x=y)：对每个 x，取 y=x 即可，成立

  • ∃y∀x (x=y)：存在一个 y 等于所有 x？不可能（除非只有一个元素）

  • 所以左边真，右边假，蕴含式为假

常见陷阱：∀x∃y 和 ∃y∀x 不能交换顺序，前者弱于后者。