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

Q软件的生命周期和软件文档怎么理解一、软件生命周期6个阶段软件生命周期 一个软件从“出生”到“死亡”的全过程阶段做什么产出物1. 可行性分析判断值不值得做技术、经济、法律可行性报告2. 需求分析搞清楚用户要什么需求规格说明书3. 设计架构设计、详细设计概要设计文档、详细设计文档4. 编码实现写代码代码、注释5. 测试找Bug、验证功能测试用例、测试报告6. 运维与维护上线、修Bug、迭代更新运维手册、变更记录注意很多面试官会把运维和废弃/下线也算进去所以有时会说是7个阶段。二、每种开发模型对应的生命周期特点模型特点适用场景瀑布模型一个阶段做完才进下一个不回头需求明确、不常变的项目敏捷开发迭代开发每个迭代都走一遍完整流程需求常变、快速交付V模型瀑布的变种测试和开发一一对应对质量要求高的项目螺旋模型每轮都做风险分析大型、高风险项目面试时可以说的“现代开发大多用敏捷但文档在不同公司要求不同。有的用敏捷说‘不写文档’但核心文档需求、接口、部署还是要有的只不过写得更轻量。”三、软件文档分类三/四大类分类文档作用开发文档需求规格说明书、概要设计、详细设计、数据库设计、接口文档让开发人员知道怎么干管理文档项目计划、风险评估、进度报告让项目经理掌控进度用户文档用户手册、操作指南、在线帮助让用户会用运维文档有时归入用户文档部署手册、运维手册、API文档让运维能部署和排查四、你至少要记住的6个核心文档文档一句话作用需求规格说明书用户到底要什么概要设计系统分几个模块、模块之间怎么通信详细设计每个模块具体怎么写接口怎么调用测试用例测试报告测了什么、结果如何用户手册用户怎么用运维手册怎么部署、怎么重启、怎么排查面试时不要背全量关键是要说出这些文档解决了什么问题沟通、边界、交接、运维。拷问1敏捷开发说“不写文档”那文档重要吗答文档不是为“写”而存在是为沟通、交接、维护服务。敏捷追求“可工作的软件胜过详尽的文档”但完全没文档的问题很早就暴露了——比如核心人员离职后新来的根本看不懂系统。结论文档要简但关键接口文档、部署文档、核心业务逻辑必须留下来。A“软件生命周期一般分为可行性分析、需求分析、设计、编码、测试、运维六个阶段。不同的开发模型会调整迭代方式比如瀑布是线性推进敏捷是迭代式。文档大体分三类开发文档给开发看、管理文档给项目负责人看、用户文档给用户看。其中最核心的文档包括需求规格说明书、概要设计、详细设计、测试报告、用户手册、运维手册。我理解文档的价值不是‘写得多’而是降低沟通成本和维护成本。尤其是在团队协作或交接时关键信息如果只靠口头或代码注释很容易丢失。”以下为笔试内容Q操作系统1.死锁进程数典型题目5 个进程每个最多需要 3 个资源系统最少需要多少个资源才一定不会死锁答案5 × (3-1) 1 11 个2.逻辑地址转物理地址典型题目已知页式存储系统中页面大小为 4KB逻辑地址为 12000。页表内容页号0→块号2页号1→块号5页号2→块号3页号3→块号7。求物理地址。解题步骤页面大小 4KB 4096 字节逻辑地址 12000 ÷ 4096 2 余 3808商页号余数页内偏移查页表页号 2 → 块号 3物理地址 块号 × 页大小 偏移 3 × 4096 3808 12288 3808 16096Q计算机组成原理一、程序查询方式程序查询方式是指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发出中断请求。二、核心区别面试/笔试答题要点对比维度程序查询程序中断DMA通道谁发起传输CPU主动问设备主动通知CPU初始化DMA控制器执行CPU发启动命令通道执行CPU是否参与数据传输是CPU直接搬数据是CPU直接搬数据否DMA控制器搬否通道搬CPU参与程度全程占用忙等每次传输都中断仅开始和结束时仅开始时数据传输单位字节/字字节/字数据块一组数据块硬件复杂度最低低中最高CPU效率极低中等高最高三、一句话总结程序查询CPU又当爹又当妈一直盯着设备看程序中断CPU当妈设备哭一声才过去喂一口DMACPU请了个保姆搬东西搬完喊一声通道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-Finddef 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(VE)3. 强连通图题目什么是有向图的强连通分量如何求时间复杂度是多少定义有向图中任意两个顶点之间互相可达则称该图为强连通图。极大强连通子图称为强连通分量。算法Kosaraju 或 TarjanKosaraju 思路对原图做一次 DFS记录完成时间压栈构建反图所有边反向按栈顺序完成时间逆序在反图上做 DFS每次 DFS 访问到的节点属于同一个强连通分量时间复杂度O(VE)Q离散数学1. 最小支配集题目什么是图的最小支配集给定一个图求它的一个最小支配集。定义支配集 D 是顶点集的一个子集使得图中每个顶点要么在 D 中要么与 D 中某个顶点相邻。最小支配集是顶点数最少的支配集NP-难问题通常用近似算法或暴力搜索小图求最小支配集的思路从所有顶点开始尝试删掉某些点检查剩余集合是否仍能支配全图。例题一个三角形3 个顶点两两相连任选一个顶点它可以支配自己相邻两个顶点所以一个顶点就够最小支配集大小 12. 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 (xy)对每个 x取 yx 即可成立∃y∀x (xy)存在一个 y 等于所有 x不可能除非只有一个元素所以左边真右边假蕴含式为假常见陷阱∀x∃y 和 ∃y∀x 不能交换顺序前者弱于后者。