期中复习指南：密码学、操作系统与算法设计分析

This post is not yet available in English. Showing the original version.

November 5, 2026 Notes 学习 zh-CN

Table of Contents

本套复习指南面向计算机专业核心课程的期中考核，旨在帮助读者在具备编程与数据结构基础的前提下，建立对理论体系的系统性认知，理清底层机制推导，掌握典型习题的手算方法与规范解答流程。

复习材料按照“知识体系与机制推导”与“典型题型与代码/算例分析”两个层次进行组织，兼顾概念深度与应试规范。

一、各科复习范围与知识索引

科目	考察范围与重点	题型与考核侧重点	导航与解析入口
密码学	基础数论、古典密码、序列密码（LFSR）、分组密码（DES/AES/有限域）、公钥密码（RSA）	机制分析、代数证明、31 道指定典型习题手算	基础概念与序列密码对称密码与工作模式数论基础与 RSA 31 道重点课后题详解
操作系统	CPU 虚拟化与进程模型、CPU 调度策略、虚拟内存管理（分页、TLB、多级页表、缺页异常与页面置换）	理论机制简答（60 分）+ 并发与系统调用代码时序分析（40 分）	期中导引与核心机制 60+40 分全真模拟与代码分析外存与持久化存储基础（拓展）
算法设计与分析	渐近复杂度分析、主定理、递归分治策略、动态规划（状态设计与区间/背包模型）、贪心算法与正确性证明	概念辨析、时间/空间复杂度推导、算法建模与规范证明	算法复习导引计算复杂度与渐近分析递归分治与主定理动态规划设计与推导贪心算法与交换论证法期中典型题与模拟试卷

二、系统化复习与解题范式

在处理各科理论问题时，建议遵循统一的认知与解题闭环：

flowchart LR
    A["1. 问题背景与系统目标<br>（解决什么痛点？）"] --> B["2. 核心数学模型/系统原语<br>（代数结构 / 硬件抽象）"]
    B --> C["3. 机制推导与时序演算<br>（状态转移 / 执行通路）"]
    C --> D["4. 边界约束与反例分析<br>（适用条件 / 异常分支）"]

审视问题的代数结构与系统抽象：
- 明确输入数据的形式化定义（如有限域多项式、图的邻接关系、进程上下文、虚拟地址空间）；
- 区分理论上限（如信息论安全）与计算限制（如计算安全复杂度、多项式时间判定）。
抓住关键推导步骤：
- 密码学：优先确定运算所属的代数系（整数模 $n$ 还是多项式有限域 $\mathrm{GF}(2^8)$ ），注意区分指数模数 $\varphi(n)$ 与数据模数 $n$ ；
- 操作系统：构建精确的进程树拓扑，判定系统调用返回值，区分用户态缓冲区与内核文件表项；
- 算法设计：明确状态的无后效性，通过考察最后一步决策写出完整的转移方程，或采用交换论证法（Exchange Argument）严格证明贪心选择性质。
自检与结果回验：
- 模逆元求解后执行乘回验算： $(a \cdot a^{-1}) \bmod n \stackrel{?}{=} 1$ ；
- 动态规划检查基础边界与单元素输入；
- 进程并发分析明确等待依赖（wait）与调度器非确定性并发交错的边界。

三、各科核心考点提要

1. 密码学

古典密码与序列密码：掌握柯克霍夫原则与四大攻击模型；理解同余代数体系中乘法逆元存在的充要条件（ $\gcd(a, n) = 1$ ）；理解一次一密（OTP）的完美保密性与密钥复用漏洞（ $C_1 \oplus C_2 = M_1 \oplus M_2$ ）；推导 LFSR 状态递推与周期性质。
对称分组密码：证明 Feistel 网络无需轮函数 $f$ 可逆即可实现全局解密的代数原理；掌握 DES 首轮数据通路与 S 盒查表机制；掌握 $\mathrm{GF}(2^8)$ 有限域代数（异或加法、模不可约多项式乘法与求逆）；解析 ECB、CBC、OFB、CTR 模式的链式依赖与差错传播；掌握双重加密的中间相遇攻击（Meet-in-the-Middle）。
公钥密码与 RSA：熟练执行辗转相除法与扩展欧几里得算法（EEA）求模逆；掌握欧拉函数 $\varphi(n)$ 与欧拉定理；掌握平方-乘快速模幂算法；严格区分 RSA 密钥生成与加解密中的双模数规则；推导基于中国剩余定理（CRT）的 RSA 全域正确性。

2. 操作系统

进程管理与并发控制：理解进程上下文、状态转移（就绪、运行、阻塞）与上下文切换开销；深入掌握核心系统调用 fork()（地址空间逻辑复制与 COW 写时复制）、exec()（进程映像替换与 PID 继承）、wait()/waitpid()（子进程资源回收与状态宏解析）；分析标准 I/O 缓冲区与内核打开文件表项（Open File Table）的文件偏移量共享。
CPU 调度：定量推导周转时间与响应时间；对比 FIFO、SJF、STCF、RR 的性能权衡与护航效应（Convoy Effect）；掌握多级反馈队列（MLFQ）的历史动态调整机制与防饥饿规则。
虚拟内存与地址翻译：掌握分页机制的地址切分（虚拟页号 VPN 与页内偏移 Offset）；计算线性页表与多级页表的空间开销与有效访存时间（EAT）；理解 TLB 硬件缓存的角色与未命中处理；推演缺页异常的处理全流程（从硬件陷阱、分配物理页框、磁盘调页到指令重新执行）；对比 FIFO、LRU、Clock、OPT 页面置换策略的时序轨迹。

3. 算法设计与分析

复杂度与理论基础：严格运用极限与不等式定义渐近符号 $O, \Omega, \Theta$ ；推导循环结构的算术/几何级数；应用主定理（Master Theorem）三类分支判定分治递推复杂度；准确理解 P 类、NP 类、NP-Hard 与 NP-Complete 的严格数学关系，掌握多项式时间归约的方向性（ $A \le_p B$ 表示 $B$ 的计算难度不低于 $A$ ）。
递归分治：掌握二分查找循环不变量与边界收敛证明；推导归并排序与利用归并过程统计逆序对的 $O(n\log n)$ 算法；理解快速选择（Quick Select）期望线性时间 $O(n)$ 的数学推导；掌握 Karatsuba 大整数乘法与 Strassen 矩阵乘法的代数降维思想；掌握残缺棋盘覆盖与平面最近点对的分治构造。
动态规划：掌握最优子结构与无后效性的形式化检验；通过“考察最后一步决策”建立状态转移方程；掌握 0-1 背包、最长公共子序列（LCS）、最大子段和、矩阵连乘积与最优二叉搜索树（Optimal BST）的模型推导；掌握空间压缩中一维数组逆序更新的数学原因；掌握六大经典实验题的状态设计。
贪心算法：理解贪心选择性质与最优子结构的充要关系；规范运用交换论证法（Exchange Argument）证明贪心策略的全局最优性；推导活动安排问题、分数背包、哈夫曼编码、Dijkstra 单源最短路径（非负权先决条件）与最小生成树（Prim/Kruskal 割性质）；分析多机调度 LPT 近似算法的近似比保证与反例。

四、复习建议与自测路径

建议先研读各模块理论篇章，明确核心机制的形式化推导与算法步骤，随后通过典型题进行闭卷手算演练：

密码学重点落实 31 道课后题的手算全流程；
操作系统重点落实 60 分论述题的四步因果阐述法 与 40 分代码分析题的进程拓扑树绘制；
算法设计重点落实 规范化六步答题范式（建模 $\to$ 状态 $\to$ 转移 $\to$ 证明 $\to$ 复杂度 $\to$ 边界）。

Loading comments...