第一章

软件工程的特性

⚫ 软件工程关注于大型程序的构造

⚫ 软件工程的中心课题是控制复杂性

⚫ 软件经常变化

⚫ 开发软件的效率非常重要

⚫ 和谐地合作是开发软件的关键

⚫ 软件必须有效地支持它的用户

⚫ 在软件工程领域中是由具有一种文化背景的人替具有另一种文化背景的人创造产品

基本原理

⚫用分阶段的生命周期计划严格管理

⚫坚持进行阶段评审

⚫实行严格的产品控制

⚫采用现代程序设计技术

⚫结果应能清楚地审查

⚫开发小组的人员应该少而精

⚫承认不断改进软件工程实践的必要性

三要素

软件工程三个要素：方法、工具、过程

软件过程的定义

为了获得高质量软件所需要完成的一系列任务框架，它规定了完成各项任务的工作步骤

四种模型

瀑布模型，每个阶段都经过仔细验证，应付需求变化能力较弱

快速原型模型，不带反馈环，开发快，过多修改容易带来版本管理的问题

增量模型，把软件分成一系列增量构件，当新构件集成到现有软件时，所形成的产品必须可测试。要求软件结构必须是开放的

螺旋模型，每个阶段都增加了风险分析，风险更小

喷泉模型，迭代重复演进，各阶段无明显界限。

第二章，可行性分析

题型：画数据流图，数据字典，成本效益分析

可行性研究的目的和内容

可行性研究的目的是用最小的代价，在尽可能短的时间内确定问题是否可以解决，以及是否值得解决

可行性:技术可行性,经济可行性,操作可行性

数据流图的概念（必考画图）

数据流图(DFD)是一种图形化技术，它描绘信息流和数据从输入移动到输出的过程中所经受的变换

数据流图大题讲解

数据字典的概念，和数据流图的关系，表示方法

软件工程速成之数据字典例题讲解

概念：数据的信息的集合，也就是对数据流图中所包含的所有元素的定义的集合通常采用半形式化方法表达。

数据字典与数据流图配合，能清楚地表达数据处理的要求

成本/效益分析

第三章，需求分析

相关题型：简答题，画ER图，画状态转换图，其余简答题

需求分析是生命周期模型中定义阶段的最后一个步骤的工作

结构化分析方法SA：分析系统数据流

SA的描述工具：

1.分层的数据流图

2.数据词典

3.描述加工逻辑的结构化语言，判定图或判定树

需求分析阶段任务

确定对系统的综合要求

功能需求，性能需求，可靠性和可用性需求，出错处理需求，接口需求，约束（精度；工具和语言约束；设计约束；应该使用的标准；应该使用的硬件平台。），逆向需求，未来可能的扩充要求

分析系统的数据要求

建立概念性的数据模型（ER图），形象描绘数据结构（层次方框图，Warnier图，IPO图），数据结构规范化

导出系统的逻辑模型

导出系统的逻辑模型（DFD+DD+IPO）

修正系统开发计划

修正系统开发计划（重估成本，进度）

与用户沟通获取需求的方法

访谈，面向数据流自顶向下求精（沿数据流图（DFD）回溯，用户复查， 细化数据流图（DFD）），简易的应用规格说明技术，快速建立软件原型

面向过程的分析方法主要是建立三类模型

模型核心：数据字典

数据模型：E-R图表达

功能模型：DFD表达

行为模型：状态转换图

需求分析的产品是什么

编制需求分析阶段的文档

⚫ 需求规格说明书，作为分析阶段最终成果，是需求分析阶段得出的最主要的文档

⚫ 数据要求说明书

⚫ 初步的用户手册

⚫ 修改、完善与确定软件开发实施计划

软件需求规格说明书的内容

通常用自然语言完整、准确、具体地描述系统的数据要求、功能需求、性能需求、可靠性和可用性要求、出错处理需求、接口需求、约束、逆向需求以及将来可能提出的要求。

常使用的图形工具

实体-联系图（和数据库里的一样）

状态转换图

通过描绘系统的状态及引起系统状态转换的事件，来表示系统的行为

软件工程数据流图，状态转换图速通教程

第五章，总体设计

题型：给数据流图画结构图

总体设计的任务

将系统划分成模块结构形式，决定每个模块要完成的功能，每个模块之间的调用关系，决定模块接口。

1.设想供选择的方案

2.选取合理的方案

⚫ 数据流程图

⚫ 组成系统的物理元素清单

⚫ 成本/效益分析

⚫ 进度计划

3.确定最佳方案

4.功能分解

5.设计软件结构（模块化思想）

6.数据库设计

7.制定测试计划

8.书写文档

⚫ 系统说明

⚫ 用户手册

⚫ 测试计划

⚫ 详细的实施计划

⚫ 数据库设计结果

9.审查和复查

模块化思想

自顶向下，逐步细化，抽象，逐步求精，信息隐藏和局部化，模块独立

模块化就是把程序划分成独立命名且可独立访问的模块，每个模块完成一个子功能，把这些模块集成起来构成一个整体，可以完成指定的功能满足用户的需求。

衡量模块独立的标准（内聚和耦合的含义，种类）（问答，选择）

耦合

是模块之间的互相连接的紧密程度的度量。

种类：（从低到高）非直接耦合，数据耦合，标记耦合，控制耦合，外部耦合，公共耦合，内容耦合

原则：尽可能使用数据耦合，少用控制耦合和特征耦合，限制公共环境耦合的范围，完全不用内容耦合

内聚

是模块强度（一个模块内部各个元素彼此结合的紧密程度）的度量。

种类：（按紧密程度从高到底排列）功能内聚，顺序内聚，通信内聚，过程内聚，时间内聚，逻辑内聚，巧合内聚。

模块独立性比较强的模块应是高内聚低耦合的模块。

启发式规则

1.改进软件结构提高模块独立性

2.模块规模适中

3.适当控制深度，宽度，扇出（一个模块直接调用控制的模块数），扇入（直接调用该模块的模块数，不破坏独立性的前提下，越大越好）

4.模块的作用域应该在控制域之内

5.降低模块接口的复杂程度

6.单出单入，避免内容耦合

7.设计功能可预测的模块，但要避免过分受限制的模块

掌握面向数据流图的设计方法

解决的任务，就是将软件需求分析阶段生成的逻辑模型数据流图映射（Mapping）成表达软件系统结构的软件结构图

第六章，详细设计

考简答，画NS图，PAD图，判定树，判定表，计算复杂度，jackson方法

详细设计的基本任务

结构程序设计，人机界面程序设计

程序的五种控制结构

五种控制结构：顺序结构，选择结构，先判断循环结构，后判断循环结构，多选择结构

详细设计的工具，之间的转换

图形工具：程序流程图、盒图（N-S图）、PAD图

NS图例题

表格工具：判定表、判定树

Jackson方法

McCabe方法计算复杂度

程序环形复杂性计算方法（三种）：

(1)流图中区域的数量对应于环形复杂度

(2)给定流图G的环形复杂度V(G)，定义为V(G)=E-N+2，E是流图中边的数量，N是流图中结点的数量。

(3)V(G)=P+1，P是流图G中的判定结点数。

第七章，实现

题型：设计测试样例

选择程序设计语言应该考虑哪些因素

一般情况下高级语言优于汇编语言

• 系统用户的要求

• 可以使用的编译程序

• 可以得到的软件工具

• 工程规模

• 程序员的知识

• 软件可移植性要求

• 软件的应用领域

良好的编程风格应该包括哪些方面

程序实际上也是一种供人阅读的文章，有一个文章的风格问题。应该使程序具有良好的风格

⚫ 源程序文档化（标识符、注解、视觉效果等）

⚫ 数据说明

⚫ 语句结构（简单、直接）

⚫ 输入/输出方法

⚫ 效率（程序运行时间、存储器效率、输入/输出效率）

软件测试的目的

目标：以尽可能小的代价，发现尽可能多的错误

尽可能多地发现并排除软件中潜藏的错误，最终把一个高质量的软件系统交给用户使用

初步 测试计划是在哪个阶段制定的

一旦完成了需求模型就可以着手制定测试计划，在建立了设计模型之后就可以立即开始设计详细的测试方案

黑盒测试和白盒测试的概念（问答题必考设计测试样例）

黑盒测试是把程序看成一个黑盒子，完全不考虑程序内部结构和处理过程的测试——功能测试

白盒测试是对程序的执行细节进行测试，通过设计测试数据，验证程序模块的每个路径的执行情况——结构测试

测试步骤（5个）以及与之相关的文档

软件测试的步骤

⚫ 模块测试（单元测试）——程序设计&代码bugs

⚫ 子系统测试——测试模块的接口

⚫ 系统测试——需求确认&系统设计

⚫ 验收测试——用户加入

⚫ 平行运行——新旧系统比较运行结果

单元测试的方法

代码审查，计算机测试

测试重点

1.模块接口测试

2.局部数据结构测试

3.路径测试

4.错误处理测试

5.边界测试

渐增式与非渐增式的区别

模块组装成系统的两种方式

非渐增式测试：

首先对每个模块分别进行模块测试，然后再把所有模块组装在一起进行测试，最终得到要求的软件系统

渐增式测试：

首先对一个个模块进行模块测试，然后将这些模块逐步组装成较大的系统。

在组装的过程中边连接边测试，以发现连接过程中产生的问题。通过渐增逐步组装成要求的软件系统。

分为自顶向下和自底向上两种方法

比较：

渐增式测试可以较早发现模块间的接口错误，非渐增式测试最后才组装，因此错误发现得晚。

非渐增式测试中发现错误后难以诊断定位，渐增式测试中，出现的错误往往跟最新加入的模块有关

渐增式测试在不断集成的过程中使模块不断在新的条件下受到新的检测，测试更彻底。

渐增式测试较非渐增式测试费时，非渐增式测试可以同时并行测试所有模块，能充分利用人力。

自顶向下，自下而上，以及混合策略的优缺点

1.自顶向下集成

优点：在早期即对主要控制及关键的抉择进行检验

问题：Stub只是对低层模块的模拟，测试时没有重要的数据自下往上流，许多重要的测试须推迟进行，而且在早期不能充分展开人力

2.自底向上集成（相反）

优点：模块自底向上组装，不需要桩模块，重要数据自下往上流动，可以提前完成重要测试，充分展开人力

缺点：不可以在早期就对主要控制进行检验

3.混合集成测试 兼具二者优点

改善的自顶向下测试，早期使用自底向上测试一些关键模块，其他一样

混合法：较下层采用自底向上，较上层采用自顶向下

确认测试

确认测试又称验收测试，任务是验证软件的功能和性能及其他特性是否与用户的要求一致。

对软件的功能和性能要求在软件需求规格说明。书中已经明确规定，它包含的信息就是软件确认测试的基础

确认测试应交付的文档有：

⚫ 确认测试分析报告⚫ 最终的用户手册和操作手册⚫ 项目开发总结报告

白盒测试技术（覆盖标准，基本路径）

每条路径对应表达式都写出来，表达式是给分关键

⚫语句覆盖（点覆盖）：每个语句至少执行一次

⚫ 判定覆盖（边界覆盖）：在语句覆盖的基础上，每个判定的每个分支至少执行一次

⚫ 条件覆盖：在语句覆盖的基础上，使每个判定表达式的每个条件都取到各种可能的结果

⚫ 判定/条件覆盖：即判定覆盖并条件覆盖

⚫ 条件组合覆盖：每个判定条件表达式中条件的各种可能组合都至少出现一次

⚫ 路径覆盖

黑盒测试技术（等级划分，边界值分析）

最好画个表

等价划分，错误推测

边界值分析，对等价类划分的补充

软件调试技术有哪些

蛮干法:强行排错

回溯法:一旦发现了错误，人们先分析错误征兆，确定最先发现“征兆”的位置

原因排除法：

1.归纳法

2.演绎法调试

3.对分查找法

软件可靠性（可靠性和可用性的含义）

可靠性（Reliability）

• 程序在给定的时间间隔内，按照说明书的规定，成
功地运行的概率

可用性（Usability）

• 程序在给定的时间点，按照说明书的规定，成功地
运行的概率

第八章，维护

什么是维护

软件维护就是在软件已经交付使用之后，为了改正错误或满足新的需要而修改软件的过程

维护的类型

⚫ 改正性维护（Corrective Maintenance）

⚫ 预防性维护（Preventive Maintenance）

⚫ 适应性维护（Adaptive Maintenance）

⚫ 完善性维护（Perfective Maintenance）

决定软件可维护性的因素

可理解性: 是指由文档代码理解功能运行的容易程度

可测试性:是指论证程序正确性的容易程度。

可修改性:是指程序容易修改的程度

可靠性

可移植性:表明程序转移到一个新的计算环境的可能性的大小

可使用性：定义为程序方便、实用、及易于使用的程度

效率:是指程序能执行预定义功能，而又不浪费机器
资源的程度

文档

⚫ 影响可维护性的决定因素，比代码更重要

⚫ 用户文档

• 功能描述——说明系统能做什么

• 安装文档——说明安装系统的方法及适应特定的硬件配置的方法

• 使用手册——说明使用方法以及错误挽救方法

• 参考手册——详尽描述用户可使用的所有系统设施以及他们的使用方法，给出错误信息注解表

• 操作员指南（如果需要有系统操作员的话）——说明操作员处理使用中出现的各种情况的方法

⚫ 系统文档

• 即软件生产过程中每一步产生的文档

维护是软件生命周期中所花费用最多的阶段

软件维护活动所花费的工作占整个生存期工作量的70%以上，维护成本约为开发成本的4倍（满足8-2原则）

第九~十二章 面向对象软件工程（考察较少）

几个概念：类，对象，继承，消息，属性，实例，多态性，重载

面向对象的方法(4个要素)

OOM=对象+类+继承+消息

对象(object)：客观世界由对象组成。

⚫ 类 (class) ：对象可划分为类；单个对象可视为某一类的实例 (instance)。

⚫ 继承(inheritance)：类可分层，下层子类与上层父类有相同特征，称为继承。

⚫ 消息(message)：对象间只能通过发送消息进行联系，外界不能处理对象的内部数据，只能通过消息请求它进行处理（如果它提供相应消息的话）。

面向对象方法的优点

① 与人类习惯的思维方式一致

②面向对象软件稳定性好

③ 面向对象软件可重用性好

④ 较易开发大型软件产品

⑤ 面向对象软件可维护性好

面向对象建模的三个模型，以及之间的关系

面向对象分析模型由3个独立模型组成：

⚫ 对象模型：最重要，开发任何系统都需要，

• 描述静态结构，定义做事情实体，用类图和对象图表示

⚫ 动态模型：对于开发交互式系统（interactive system）很重要

• 描述交互过程，由状态图和顺序图表示

⚫ 功能模型：对于开发大运算量问题（如科学计算、编译系统等）很重要

• 指明系统应“做什么”，由用例图表示

面向对象设计时要设计哪些子系统，及各个子系统的作用

问题域子系统，人机交互子系统，任务管理子系统，数据管理子系统

问题域：直接负责实现客户需求子系统

人机交互：实现用户界面子系统包括可复用的GUI子系统

任务管理：确定各类任务，把任务分配给适当的硬件或软件去执行

数据管理：负责对象的存储和检索的子系统

CMM等级划分（了解，选择题）

(1)初始级

(2)可重复级

(3)已定义级

(4)已管理级

(5)优化级

适用场景：复试上机时使用 Dev-C++ 编写和调试 C/C++ 程序。
目标：把最常用的环境配置、调试流程、代码片段和提交前检查集中到这一份。

1. 先把环境配对

1.1 常用界面操作

• Tools 下的环境设置可以切换界面语言。
• Ctrl + 鼠标滚轮 可以放大或缩小编辑器字体。

1.2 编译与调试选项

进入 Tools > Compiler Options，重点确认这几项：

• 编译参数建议包含：

1

-g -O0 -std=c++11 -Wall -Wextra -DLOCAL

• 关闭优化：调试阶段优先用 -O0。
• 打开调试信息：在代码生成或链接相关选项里，把 Generate debugging information / 产生调试信息 设为 Yes。
• 修改编译选项后，执行一次 Rebuild All，不要只点普通编译。

说明：

• -g：让断点、单步、变量查看生效。
• -O0：避免优化导致行号乱跳、变量被优化掉。
• -DLOCAL：方便在本地打开调试输出，提交前再关闭。

2. 上机时最实用的操作顺序

1. 先把题目输入格式确认清楚，写最小可运行版本。
2. 编译一次，先排掉语法错误和头文件问题。
3. 用最小样例跑通，再测边界样例。
4. 如果结果不对，优先用“断点 + Watch + 少量输出”定位。
5. 如果程序崩溃，先查数组越界、空指针、循环边界。
6. 提交前关闭调试开关，重新编译，再跑一遍样例。

3. Dev-C++ 里怎么调试最有效

3.1 断点打在哪里

• 循环问题：打在循环入口、循环体第一行、下标更新前。
• 分支问题：打在 if / else if 判断前。
• 指针问题：打在 *p、a[i]、node->next 这类访问前。
• 函数问题：打在调用前和函数入口处。

不要一开始满屏断点。先用 2 到 4 个关键断点缩小范围。

3.2 单步执行怎么选

• Step Over：执行当前行，不进入函数内部。默认优先用它。
• Step Into：进入函数内部。怀疑子函数有问题时再用。
• Step Out：从当前函数退回调用处。进太深时很有用。
• Continue：继续运行到下一个断点。

3.3 Watch 盯哪些变量

优先盯这些：

• 循环变量：i、j、k
• 边界变量：n、m、len
• 结果变量：ans、sum、cnt
• 指针或节点：p、head、tail
• 当前读入值：x、y、ch

建议一次只加 3 到 5 个最关键变量，避免界面太乱。

3.4 调试输出什么时候更快

当循环很多、断点停太频繁时，直接加少量输出更快：

1

cerr << "DEBUG i=" << i << " a[i]=" << a[i] << " sum=" << sum << '\n';

建议统一加 DEBUG 前缀，提交前一起删掉或通过宏关闭。

4. 常见问题排查顺序

4.1 数组越界

• 检查下标是否可能 < 0 或 >= n
• 重点盯 i、j、n
• 在 a[i] 访问前打断点

4.2 死循环

• 看循环变量是否真的在变化
• 看退出条件是否有机会满足
• 打印每轮的 i/j/cnt/sum

4.3 指针异常

• 解引用前先判断是否为 nullptr
• 检查是否访问了失效对象
• 链表重点看 next，树结构重点看左右孩子

4.4 输入输出异常

• 检查读入格式是否和题目一致
• 不要混用 cin/cout 和 scanf/printf
• 对关键读入值做短输出确认

4.5 断点失效

• 通常是没开 -g
• 或者改完编译选项后没 Rebuild All
• 或者优化没有关掉

5. 机试时可直接复制的代码片段

5.1 快速输入输出

1
2
3

ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

5.2 本地调试开关

1
2
3
4
5
6
7

#ifdef LOCAL
#define DBG(x) cerr << #x << " = " << (x) << '\n'
#define LOG(msg) cerr << msg << '\n'
#else
#define DBG(x)
#define LOG(msg)
#endif

5.3 打印 vector

1
2
3
4
5
6
7
8
9
10
11

#ifdef LOCAL
template <class T>
void print_vec(const vector<T>& v) {
    cerr << "[";
    for (size_t i = 0; i < v.size(); ++i) {
        if (i) cerr << ", ";
        cerr << v[i];
    }
    cerr << "]\n";
}
#endif

经典基础

一、核心易错点

1. 数组与越界

• 循环变量和分类下标分离：不要用外层 i 直接访问固定小数组。
• 容器访问前先判空或判长度：

1
2

if (!v.empty()) use(v[0]);
if (v.size() > 1) use(v[1]);

2. 输入输出

• cin >> n 后接 getline，必须先吃掉换行符：

1
2

cin >> n;
cin.ignore();

• 大数据 I/O 优化：

1
2

ios::sync_with_stdio(0);
cin.tie(0);

• 固定宽度补零：printf("%05d\n", num)。
• 输出优先 \n，避免频繁 endl。

3. 数据结构选择

• 键可能重复时，不用 map 存主体数据（会覆盖），用 struct + vector + sort。
• 不要求有序时优先 unordered_map/unordered_set。
• 小范围计数（如 26 字母）优先数组。

4. 边界条件

• 重点检查：0、空输入、区间端点、整除（余数为 0）。
• 转换类题目做“正向 + 逆向”自检。

5. 算法策略

• 能数组模拟就别硬改指针（如链表题可先按地址收集再处理）。
• 位数少可枚举，位数大用 DFS + 剪枝。

二、字符串输入与分词

1. 按空白读取到 EOF

1
2
3
4

string word;
while (cin >> word) {
    words.push_back(word);
}

2. 读取整行后按空格切词

1
2
3
4
5
6
7

string line;
getline(cin, line);
istringstream iss(line);
string word;
while (iss >> word) {
    words.push_back(word);
}

3. cin >> n 与 getline 混用模板

输入流缓冲区陷阱：

先 cin >> 读数字，后用 getline() 读字符串，cin 残留的回车符会直接被 getline 吞掉导致读到空串。必须在两者之间加 cin.ignore(); 清理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int n;
cin >> n;
cin.ignore();

for (int i = 0; i < n; i++) {
    string line;
    if (!getline(cin, line)) break;
    istringstream iss(line);
    string word;
    while (iss >> word) {
        cout << word << ' ';
    }
    cout << '\n';
}

三、排序与比较器

1. sort + Lambda

1
2
3

sort(a.begin(), a.end(), [](const Node& x, const Node& y) {
    return x.key < y.key;
});

2. 结构体内重载 <

1
2
3
4
5
6
7
8
9
10

struct Student {
    int num, de, cai;
    bool operator<(const Student& b) const {
        if (de + cai == b.de + b.cai) {
            if (de == b.de) return num < b.num;
            return de > b.de;
        }
        return de + cai > b.de + b.cai;
    }
};

• 成员版 operator< 只写一个参数（右操作数）。
• 建议加 const，保证比较不改对象。

四、map<int, bool> 常用写法

1. 插入/修改

1
2
3

mp[10] = true;
mp.insert({30, true});
mp.emplace(50, false);

2. 遍历（推荐写法）

1
2
3

for (const auto& [key, val] : mp) {
    cout << key << ' ' << boolalpha << val << '\n';
}

五、区间与迭代器

1. begin() 与 end()

• begin() 指向第一个元素。
• end() 指向末尾后一个位置，不可解引用。

2. reverse 左闭右开

• reverse(first, last) 作用区间是 $[first, last)$。
• 示例：

1
2

reverse(v.begin(), v.begin() + 3); // 前 3 个
reverse(v.begin() + 1, v.end());   // 从第 2 个到末尾

六、格式化输出

1

cout << fixed << setprecision(n) << x << '\n';

• fixed：固定小数格式。
• setprecision(n)：配合 fixed 时表示小数位数。

七、sort() 越界保护

1. 推荐：min 限制右边界

1
2

int end_idx = min(i + step, (int)a.size());
sort(a.begin() + i, a.begin() + end_idx);

2. 与 end() 比较

1
2

auto it_end = (a.begin() + i + step > a.end()) ? a.end() : a.begin() + i + step;
sort(a.begin() + i, it_end);

八、工程化小习惯

• 比较前先判长度，不等直接返回。
• vector 返回值可直接 return {a, b};。
• 累加场景优先检查是否误写 =（应为 +=）。

这是一个为你整理的 C++ STL 关联容器与哈希表核心用法总结表。在刷题和面试时，你可以直接在脑海中调出这张表格，快速决定使用哪种数据结构。

九、C++ STL 核心容器对比与速查表

核心操作速记 (适用于以上所有 STL 容器)

• 查找是否存在： 首选：if (container.find(key) != container.end())
  • 次选（仅限 set/map）：if (container.count(key) > 0)
• 插入元素：
  • set / unordered_set: insert(key)
  • map / unordered_map: container[key] = value (最方便) 或 insert({key, value})
• 删除元素：
  • 按值删除：erase(key)
• 遍历容器：
  • C++11 写法：for (auto it : container)
  • C++17 结构化绑定 (针对 map)：for (auto [key, value] : my_map)

十、算法题型强化（从 N 数之和开始）

这一部分按“题型框架 -> 高频坑点 -> 可复用模板思维”整理，便于刷题时快速调用。

1. N 数之和家族（3Sum / 4Sum）

题型总框架

• 先排序，再做枚举 + 双指针。
• 去重必须发生在遍历过程中，而不是预处理阶段。
• 4Sum 及以上场景优先考虑剪枝，否则容易超时。

四个高频坑点

1. 不能提前去重

• 不要先用 set 对原数组去重。
• 原数组中的重复值可能是合法答案的一部分，例如 [0, 0, 0]。

2. 去重边界要写准

• 外层去重：if (k > 0 && nums[k] == nums[k - 1]) continue;
• 内层去重：if (i > k + 1 && nums[i] == nums[i - 1]) continue;
• 关键点：内层必须和当前层起点比较，不能写成 i > 0。

3. 警惕整型溢出

• 多个 int 累加时可能溢出。
• 计算和时先提升类型：(long long)nums[k] + nums[i] + ...。

4. 剪枝时分清 break 与 continue

• 最小和已经大于 target：后续只会更大，直接 break。
• 最大和仍小于 target：当前值太小，应该 continue。

2. 回溯算法（Backtracking）

统一骨架

终止条件 -> 做选择 -> 递归 -> 撤销选择。

两种写法对比

1. 值传递写法（易写易懂）

• 形式：void backtrack(int n, string path)
• 递归：backtrack(n, path + ch)
• 特点：天然不需要手动撤销，代码直观。
• 代价：频繁拷贝字符串，适合 $n$ 很小（如 $n \le 10$）。

2. 引用传递写法（面试主流）

• 形式：void backtrack(int n, string& path)
• 必须严格遵循：加入字符 -> 递归 -> pop_back()。
• 特点：性能更好，适合规模更大的搜索。

3. 哈希表优化思路

思路一：分组哈希（降维）

• 典型题：四数相加 II（四个独立数组）。
• 做法：前两数组求和计数，后两数组查补数 0 - c - d。
• 复杂度从 $O(n^4)$ 降为 $O(n^2)$。

思路二：能用定长数组就别用哈希

• 当键空间很小且固定（如 26 个小写字母）时，优先 int hash[26] = {0};。
• 数组访问常数更小、内存连续、实现也更稳定。

4. 一页速记（实战决策）

• N 数之和：排序 + 双指针 + 分层去重 + 剪枝。
• 回溯：小规模可值传递，大规模用引用传递并手动撤销。
• 哈希优化：先看能否分组降维，再看能否降到定长数组。

十一、二叉树与 C++ 核心机制

1. 二叉树的遍历框架（基础必须如肌肉记忆般熟练）

1. DFS 迭代法（前、中、后序）

• 核心数据结构：栈 (stack)。注意栈是后进先出 (LIFO)。
• 易错点：写前序遍历时，压栈顺序必须是先压右孩子，再压左孩子，这样出栈时才是“先左后右”。

2. BFS 层序遍历

• 核心数据结构：队列 (queue)。
• 黄金模板：每次 while 循环开头，一定要先定格 int size = q.size();，然后用 for(int i=0; i<size; i++) 处理当前层，千万别和刚加进来的下一层节点混淆。

2. 树的属性与形态判定（思维陷阱高发区）

1. 最小深度 (Min Depth) 的“单身狗”陷阱

• 教训：遇到空节点不能直接算作叶子返回 0。如果一个节点只有左孩子没有右孩子，你必须顺着左边往下走，不能抄右边的空指针近道。

2. 对称二叉树 (Symmetric Tree)

• 教训：队列不支持下标访问（q[i] 报错）。正确的迭代法是成对入队，每次弹出两个节点对比，然后按 [左的左, 右的右] 和 [左的右, 右的左] 的顺序压入。

3. 平衡二叉树 (Balanced Tree) 的 $O(N)$ 优化

• 教训：自顶向下的递归会导致 $O(N^2)$ 的重复计算。
• 神仙操作：利用自底向上，在求深度的同时判断高度差。一旦发现不平衡，直接返回 -1 作为报错信号，一路剪枝到顶。

4. 左叶子之和 (Sum of Left Leaves)

• 教训：当前节点无法判断自己是不是“左叶子”。必须站在父节点去判断：root->left && !root->left->left && !root->left->right。

3. 高阶算法思想的应用

1. 完全二叉树的节点数（二分搜索思想）

• 核心公式：满二叉树节点数 = (1 << height) - 1 （注意防溢出，必要时用 1LL）。
• 神级优化：一直向左走测出左右子树的高度。如果 leftH == rightH，说明左子树是满的；如果 leftH > rightH，说明右子树是满的。每次直接抛弃一半，复杂度降为 $O(\log^2 N)$。

2. 回溯算法初步（Binary Tree Paths & Path Sum）

• 传值 vs 传引用：传 string path (传值) 会自动拷贝，不需要你手动清理；传 vector<int>& path (传引用) 必须成对出现 push_back 和 pop_back（做选择与撤销选择）。
• 做减法：路径总和问题，最好带着 targetSum - root->val 往下传，到叶子节点看是否刚好归零。

4. 二叉树的重构（纯靠索引操作）

1. 从中序与后序遍历构造二叉树

• 教训 1：建好的子树一定要挂载到父节点上（node->left = ...）。
• 教训 2：切分数组时，不要用绝对下标相加！唯一可靠的指标是算出一个 leftSize（左子树长度）。
• 切分公式：leftSize = index - inBegin。然后顺着后序数组的开头数 leftSize 个人，硬切开左右子树。

5. C++ 语言与语法避坑指南

1. 变量遮蔽 (Variable Shadowing)

• 惨痛教训：在 while 循环外定义了 TreeNode* cur，如果在循环里又写了 TreeNode* cur = q.front()，外部的 cur 就废了！更新外部变量时千万别加类型。

2. STL 队列操作

• C++ 的 q.pop() 返回值是 void！必须先 q.front() 拿到值，再去 q.pop() 弹出。

3. 防呆设计 (Null Pointer Check)

• 任何递归或循环的第一步，永远是 if (!root) return ...;，直接拦截空指针，防止 Segfault。

十三、转义字符

反斜杠必须转义：

题目要求的错误提示包含 \，在 C++ 字符串中必须写成双反斜杠 **\\**，即 cout << "Are you kidding me? @\\/@";。

死循环与段错误：

找右括号 ] 时，循环条件必须加上 j < line.size() 保护。如果输入数据残缺（只有 [ 没有 ]），不加保护直接内存越界。

十四、整除

在中文语境和数学严谨表达中，“A 可以整除 B” 的含义是：B 是被除数，A 是除数。

• A 整除 B（记作 $A | B$）：意味着 $B \div A$ 的结果是一个整数。
• A 被 B 整除：意味着 $A \div B$ 的结果是一个整数。

所以，题目中“正整数 N 可以整除它的 4 个不同正因数之和”对应的数学表达式是：

$$\frac{\text{因数1} + \text{因数2} + \text{因数3} + \text{因数4}}{N} = \text{整数}$$

也就是说，这 4 个因数的“和”，必须是 $N$ 的倍数。

十五、螺旋矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

void solve() {
    int N;
    cin >> N;
    vector<int> vec(N);
    for (int i = 0; i < N; i++) {
        cin >> vec[i];
    }

    // TODO 1: 对 vec 进行降序排序
    sort(vec.begin(),vec.end(),[](int a,int b){
        return a > b;
    });
    int m = 0, n = 0;
    // TODO 2: 计算行数 m 和列数 n 
    // 提示: 令 n = sqrt(N)，循环递减 n 直到 N % n == 0，求出 m
    for(n = sqrt(N);n >= 1;n--){
        if(N % n == 0){
            m = N / n;
            break;
        }
    }
   // cout  << m << " " << n << endl;
    // 初始化二维矩阵 (注意一定要等 m 和 n 算出来后再初始化)
    vector<vector<int>> matrix(m, vector<int>(n));

    // 定义四个边界
    int top = 0, bottom = m - 1;
    int left = 0, right = n - 1;
    int index = 0; // 记录当前填到了 vec 中的第几个数

    // TODO 3: 螺旋填充核心逻辑
    while (index < N) {
        // 1. 从左到右填充上边界，填完后上边界下移
        // 提示: for (int j = left; j <= right && index < N; j++) ...
        //00 -> 0n
        for(int j = left; j <= right && index < N;j++){
            matrix[top][j] = vec[index++];
        }
        top ++;
        // 2. 从上到下填充右边界，填完后右边界左移
        //1n -> mn
        for(int j = top;j <= bottom && index < N;j++){
            matrix[j][right] = vec[index++];
        }
        right--;
        // 3. 从右到左填充下边界，填完后下边界上移
        //mn -> m0
        for(int j = right;j >= left && index < N;j--){
            matrix[bottom][j] = vec[index++];
        }
        bottom--;
        // 4. 从下到上填充左边界，填完后左边界右移
        //m0 -> 10
        for(int j = bottom;j >= top && index < N;j--){
            matrix[j][left] = vec[index++];
        }
        left++;
    }
    
}

操作系统

填空题（1*20=20分）简单看看概念

选择题（1*20+ 2 * 5=30分）

简答题（4*5=20分）5道题目，辅修考了：进程的概念，基本特征，中断处理过程

综合题（5*6=30分）6道题目，

考：银行家算法，作业调度算法，PV原语，管程，页面替换算法，存储空间管理，文件索引

[TOC]

绪论

操作系统的定义

操作系统是计算机系统中的一个系统软件，是一些程序模块的集合，它们管理和控制计算机系统中的硬件及软件资源，合理地组织计算机工作流程。以便有效地利用这些资源为用户提供一个具有最够的功能、使用方便、可扩展、安全和可管理的工作环境，从而在计算机与用户之间起到接口的作用。

操作系统的基本类型和特点

批处理操作系统

操作员把用户提交的作业分类，把一批作业编成一个作业执行序列，由专门编制的监督程序自动依次处理

特点：用户脱机使用计算机、成批处理、多道程序运行

分时操作系统

把处理机的运行时间分成很短的时间片，按时间片轮转的方式，把处理机分配给各个进程使用

特点：交互性、多用户同时性、独立性

实时操作系统

在被控对象允许时间范围内做出响应

特征：对实时信息分析处理速度要比进入系统快、要求安全可靠

微机操作系统

单用户单任务OS

只允许一个用户上机，且只允许用户程序作为一个任务运行

最具代表性的是CP/M和MS-DOS

单用户多任务OS

只允许一个用户上机，但允许将一个用户程序分为若干个任务，使他们并发执行

最具代表性的是os/2和MS-WINDOWS

多用户多任务OS

允许多个用户通过各自的终端使用同一台主机，共享主机的各类资源，同时用户程序又可以分成几个任务使它们并发执行

最具代表性的是UNIX OS

操作系统的功能

处理机管理

存储管理

设备管理

文件系统管理（信息管理）

用户接口

程序一级接口

作业一级接口

思考题

问题：鼠标点击“绪论.ppt”图标到屏幕上显示该文件内容

这个过程中，按照先后顺序描述操作系统完成了哪些功能？（尽可能描述细节）

鼠标点击—设备管理，用户接口

启动powerpoint程序—-存储管理，处理器管理

打开绪论.ppt文件—-文件管理，设备管理，存储管理

在屏幕上显示—-设备管理，用户接口

操作系统的特点

并发是两或多个事件在同一时间间隔内发生。

共享性：系统中的所有资源不再为一个程序所独占，而是供同时存在于系统中的多道程序所共同使用

虚拟是指通过某种技术把一个物理实体变为若干个逻辑上的对应物

异步性和不确定性：程序的执行并非“一气呵成”，而是以“走走停停”的方式运行，即程序是以异步方式运行的

作业

是指在一次应用业务处理过程中，从输入开始到输出结束，用户要求计算机所做的有关该次业务处理的全部工作

系统调用

作用：系统调用是系统向编程人员（应用程序，用户程序）提供的唯一接口

实现过程：

（1）用户在源程序中使用系统调用，并给出系统调用名和参数，即产生一条相应的陷阱指令

（2）处理机在执行到这条指令后，引起处理机中断，并发出有关信号给陷阱处理机构

（3）该处理机构收到信号后，启动相关程序保护处理机现场，取系统调用功能号并寻找子程序入口，通过入口地址表找到该系统子程序并执行

（4）执行完毕后，退出中断，返回到用户程序的断点，恢复现场，继续执行用户程序

进程管理

程序顺序执行的特征

顺序性，一个程序开始执行必须要等到前一个程序已执行完成。

封闭性，程序一旦开始执行，其计算结果不受外界因素影响。

可再现性，程序的结果与它的执行速度无关（即与时间无关），只要给定相同的输入，一定会得到相同的结果

程序并发执行的特征

间断性，“走走停停”，一个程序可能走到中途停下来，失去原有的时序关系

失去封闭性，程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性

不可再现性，程序在并发执行时，由于失去了封闭性，也导致失去了可再现性

并发

概念，一组在逻辑上相互独立的程序或程序段在执行过程中，其执行时间在客观上相互重叠

并发带来的效率提升

进程

概念：在操作系统中进程是一个拥有资源的基本单位，也是一个调度和执行的基本单位

特征：动态性（最基本），并发性，独立性，异步性，结构特性

进程的静态结构

PCB :OS感知进程的存在的唯一标识

PCB，由进程创建原语创建

程序段

数据结构集

进程状态转换

执行，等待，就绪

思考题

如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个，最少几个；等待进程最多几个，最少几个？

答：最多有1个进程运行，最少是0个，就绪进程最多N-1个，最少0个

等待进程最多N个，最少0个（死锁）

原语

概念：是指系统态下执行的某些具有特定功能的程序段

原语又称为“原子操作(Atomic Operation)”过程，作为一个整体而不可分割——要么全都完成，要么全都不做

机器指令级的:执行期间不允许中断

功能级的:作为原语的程序段不允许并发执行

临界区

概念：一个进程访问临界资源的那段程序代码称为临界部分或者称为临界区.即访问公用数据的那段程序

使用准则：

（1）不能假设各并发进程的相对执行速度。即各并发进程享有平等的、独立的竞争共有资源的权利，且在不采取任何措施的条件下，在临界区内任一指令结束时，其他并发进程可以进入临界区

（2）并发进程中的某个进程不在临界区时，它不阻止其他进程进入临界区；放弃处理机

（3）并发进程中的若干个进程申请进入临界区时，只能允许一个进程进入。

（4）从并发进程中的某个进程申请进入临界区时开始，应在有限时间内能够进入其临界区

即：空则让进，等则让权（让权等待），忙则等待，等则有限

信号量

信号量的本质是计数器，一个口袋，P是申请拿球，V是放球

sem>0表示有sem个资源可用

sem=0表示无资源可用

sem<0则| sem |表示sem等待队列中的进程个数

sem的应该初值大于等于零

P(S):表示申请一个资源

V(S):表示释放一个资源

进程互斥的实现

软件法：通过平等协商方式实现进程互斥

单标志算法，双标志、先检查算法，双标志、先修改后检查算法，先修改、后检查、后修改者等待算法

硬件法：关中断，专用指令（testset, swap）

信号量

单个临界资源：整型信号量，记录型信号量

多个临界资源:AND型信号量

管程

条件变量：cwait,csignal

局部变量,操作

实现进程的同步和互斥

进程的互斥：由于共享资源而引起的在临界区内不允许并发进程交叉执行的现象称为由共享公有资源而造成的对并发进程执行速度的间接制约

进程的同步：由于并发进程互相共享对方的私有资源所引起的直接制约

进程的前驱关系（时间同步）

一组有关的并发进程在执行时间上有严格的先后顺序时，就会出现时间上的进程同步问题，或者称为进程的前驱关系

进程通信

低级通信：进程之间控制信息的交换。一般只传送一个和几个字节的信息，达到控制进程执行速度的作用。（进程的同步和互斥）

高级通信：用户可以直接利用操作系统所提供的一组通信命令，高效地传送大量数据的一种通信方式。

方式：主从式 (master-servant system) 　，会话式(dialogue system)，

消息或信箱机制(message)，共享存储区方式(shared memory）

死锁

**概念：**指多个进程因竞争资源而造成的一种僵局，若无外力的作用，这些进程将永远不能再向前推进

产生死锁的必要条件：互斥，部分分配，不剥夺条件，环路等待

1. Mutual-exclusion - 一个口袋一个球，得到球才能继续
2. Wait-for - 得到球的人想要更多的球
3. No-preemption - 不能抢别人的持有的球
4. Circular-chain - 形成循环等待球的关系

预防死锁

**预防死锁设计思路：**设置某些限制条件，去破坏死锁四个必要条件中的一个或多个，来防止死锁。

防止“互斥条件”：使用Spooling技术来管理设备

防止“不剥夺”条件的出现：一个已经保持了某些资源的进程，当它再提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源，待以后需要时再重新申请

防止部分分配（摒弃请求和保持条件）：系统要求任一进程必须预先申请它所需的全部资源，而且仅当该进程的全部资源要求能得到满足时，系统才能给予一次性分配，然后启动该进程运行

防止“环路等待”条件的出现：把系统中所有资源类型线性排队，并按递增规则赋予每类资源以唯一的编号，进程申请资源时，必须严格按资源编号的递增顺序进行，否则系统不予分配

死锁避免：

安全状态：存在某种资源调度顺序，来为每个进程分配其所需资源，直至最大需求,保证所有进程正常运行完成，则称该状态为安全状态。

不安全状态：不存在可满足所有进程正常运行的资源调度顺序，则称该状态为不安全状态

避免死锁的实质是如何使系统不进入不安全状态

银行家算法

判断是否为安全状态，对于进程的资源请求，判断是否能够进行分配

银行家算法_Banker’s_Algorithm_哔哩哔哩_bilibili

死锁的检测和恢复

死锁的检测：实质是确定是否存在环路等待现象

死锁的恢复：立即结束所有进程的执行,并重新启动操作系统；撤销进程；剥夺资源

线程

线程是调度和执行的基本单位，不作为独立分配资源的单位

引入线程则是为了减少程序并发执行时的所付出的时空开销

线程本身拥有少数资源，多个线程共享所属进程的资源

线程分类：用户级线程，系统级线程

适用范围：多处理机系统，网络与分布式系统

处理器调度

调度的分级

作业调度（宏观调度，高级调度），交换调度（中级调度），内外存的进程交换，进程调度，分配处理机

作业调度的衡量

周转时间：从提交到完成的时间

带权周转时间：周转时间除运行时间

调度算法（考）

先来先服务（FCFS）：将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理，它优先考虑在系统中等待时间最长的作业，而不管要求运行时间的长短

轮转法:

把CPU划分成若干时间片。将系统中所有的就绪进程按照FCFS原则，排成一个队列每次调度时将CPU分派给队首进程，让其执行一个时间片

时间片的选择：

时间片长度S＝R/Nmax

R：响应时间;

Nmax：最大进程数

多级反馈轮转法:

系统中设置多个就绪队列

每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大

优先级法:静态优先级,动态优先级

最短作业优先法

对预计执行时间短的作业（进程）优先分派处理机

比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；

提高系统的吞吐量

最高响应比优先法:响应比R = 1 +（作业等待时间/ 作业执行时间）

实时系统中的任务分类

按照时限严格程度类型分类

硬实时任务：要求系统必须完全满足任务的时间要求

软实时任务：允许系统对任务的时限要求有一定的延迟，时限要求是一个相对条件

按照时限是周期or时刻分类

周期性任务：要求在周期T内完成或开始进行处理

非周期性任务：存在一个完成或开始进行处理的时间

存储管理

概念

**逻辑地址:**程序经编译或汇编以后形成目标程序，其指令的顺序都是以零作为参考地址，这些地址称为 逻辑地址

虚拟地址空间:

虚存容量的扩大是以牺牲CPU工作时间以及内、外存交换时间为代价的 （时间换空间）

虚拟存储器的最大容量（用户编程空间）由计算机的地址结构和寻址方式决定

如直接寻址时，若CPU的有效长度为16位，则其地址范围是0～～64K-1(216-1)，最大容量为64K**(确认地址位数)**

静态重定位

在装入一个作业时，把作业中的指令地址和数据地址全部转换为物理地址（地址转换工作是在作业执行前集中一次完成的）在作业执行过程中就无须再进行地址转换工作

动态重定位:地址转换是在作业执行时动态完成

内存保护

上下界保护法

在CPU中设置一对上界寄存器和下界寄存器存放用户作业在内存中的起始地址和终止地址；每当CPU要访问内存时，硬件自动将被访问的内存地址与界限寄存器的内容进行比较，以判断是否越界

保护键法

为每一个被保护存储块分配一个单独的保护键。保护键可设置成对读写同时保护的或只对读、写进行单项保护的；在程序状态字中则设置相应的保护键开关字段, 不同的进程赋予不同的开关代码；

界限寄存器与CPU的用户态或核心态工作方式相结合的保护方式

在这种保护模式下，用户态进程只能访问那些在界限寄存器所规定范围内的内存部分，而核心态进程则可以访问整个内存地址空间

内存扩充

覆盖方式：

一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间

交换方式：

由操作系统把那些在内存中处于等待状态的进程换出内存，以及把那些等待事件已经发生，处于就绪态的进程换入内存，以及那些即将执行的程序数据调入内存

调入方式：

请求调入方式, 预调入方式

内存管理

常用方法:

分区存储管理,页式管理,段式管理,段页式管理

动态分区分配

最先适应法:要求空闲分区按首址递增的次序组织可用表或自由链

最佳适应法:空闲分区链按照分区容量递增的方式形成

最坏适应法:要求空闲区按大小递减的顺序组织可用表(或自由链)

动态分区回收:

a,与空闲区合并。b,与上空闲区合并。c,与下空闲区合并。d,不合并

缺点：

所谓“碎片”(fragmentation)：就是指不能分配给作业使用的一段无效存贮空间。

固定分区管理存在内碎片，可变分区管理存在外碎片

碎片使得内存的空闲空间得不到充分利用，并且存储每个用户作业都要受到实际存储容量的限制。

页式管理（考计算）

页式管理中给定逻辑地址的组成，页表，将逻辑地址转换为物理地址

计算过程：程序地址/页长

页式管理的问题：CPU要存取一个数据，需访问主存两次

解决：快表

请求（动态）页式管理的实现：

与每个虚页号相对应，除了页面号之外，再增设该页是否在内存的中断位以及该页在外存中的副本起始地址，还应增加一项以记录该页是否曾被改变

段式存储管理（考计算）

给定段表，计算逻辑地址对应的物理地址

页面置换算法（考）

注意刚开是空页放入也计入表格

FIFO算法：淘汰最早建立的页面，Belady现象

LRU:最近最久没有使用,当需要淘汰时，应淘汰当前时间最近的一段时间内最久没有使用过的页

LFU:最不经常使用,淘汰被访问次数最少的页

NUR：当需要淘汰某一页时，从那些最近一个时期内未被访问的页中任选一页淘汰

理想型页面置换法（OPT）：选择“未来不再使用的”或“在离当前最远位 置上出现的”页面被置换

缺页率的计算：缺页次数/访问页面次数

Belady现象

采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，缺页率反而提高的异常现象。

原因：

FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的

局部性原理

指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域

还可以表现为：

时间局部性，即一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内；

空间局部性，即当前指令和邻近的几条指令，当前访问的数据和邻近的数据都集中在一个较小区域内

内存抖动问题

定义：

在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖动

产生的原因

分配给进程的物理页面数太少

页面淘汰算法不合理

避免的方法

扩大工作集

选择不同的淘汰算法

文件系统

文件的逻辑结构与存取方法

逻辑结构

字符流式的无结构文件：源程序、可执行文件、库函数等

记录式的有结构文件：数据库

存取方法

(1)顺序存取法

⑵ 随机（直接）存取法

⑶ 按关键字存取法

文件的物理结构与存储设备

物理结构

为了有效地管理文件存储器，通常把文件存储空间划分成若干个大小相等的物理块，物理块是分配及传输信息的基本单位

常用的物理结构：连续文件，串联文件，索引文件；

存储设备

顺序存储设备：磁带

直接存储设备：磁盘

磁盘臂调度算法

先来先服务(FCFS):

磁盘驱动程序每次接收一个请求并按照接收顺序完成请求

最短寻道时间优先（shortest seek time first，SSTF）:

下一次总是处理与磁头距离最近的请求以使寻道时间最小化

文件空间管理

空闲文件目录

空闲块链

UNIX中使用成组链法

位视图

文件接口

OPEN, close, create,delete

目录结构

单级目录

结构简单，实现容易

搜索速度较慢，不允许文件重名

二级目录

解决了文件的重名问题和文件共享问题

提高搜索速度，查找时间降低

多级目录

层次结构清晰，便于管理和保护；有利于文件分类；解决重名问题；

查找一个文件按路径名逐层检查，由于每个文件都放在外存，多次访盘影响速度

文件的共享

绕道法

使用绕道法进行文件共享时，用户从当前目录出发向上返回到与所要共享文件所在路径的交叉点再顺序下访到共享文件

链接法

在相应目录表之间进行链接。即将一个目录中的链指针直接指向被共享文件所在的目录

基本文件目录表BFD

把所有文件目录的内容分成两部分：

基本文件目录表BFD：存放除了文件名之外的文件说明信息和文件内部标识符；

符号文件目录表SDF：存放文件名和文件内部标识符

存取权限控制

（1）文件的共享：指不同的用户共同使用一个文件

（2）文件的保护：指文件本身需要防止文件的拥有者或其他用户破坏文件内容。

（3）文件的保密：指未经拥有者许可，任何用户不得访问该文件。（防止窃取）

设备管理

SPOOLNG系统

假脱机真联机技术：设备管理的虚拟技术

它使用直接存取的大容量磁盘作为缓冲，将一个可共享的磁盘空间改造成若干个输入设备和输出设备，并使得I/O设备和CPU并行操作。（在联机情况下实现的同时外围操作）

SPOOLING 系统的组成

（1）输入井和输出井（2）输入缓冲区和输出缓冲区

（3）输入进程和输出进程（输入管理模块、输出管理模块）

特点：

1. 提高了I/O速度

   从对低速I/O设备进行的I/O操作变为对输入井或输出井的操作,如同脱机操作一样,提高了I/O速度,缓和了CPU与低速I/O设备速度不匹配的矛盾

2. 设备并没有分配给任何进程

   在输入井或输出井中,分配给进程的是一存储区和建立一张I/O请求表.

3. 实现了虚拟设备功能

   多个进程同时使用一独享设备,而对每一进程而言,都认为自己独占这一设备,不过,该设备是逻辑上的设备

数据传输控制方式

程序直接控制：由用户进程来直接控制内存或CPU和外设间的信息传送。

中断方式：进程通过CPU发出指令启动外设，该进程阻塞。当输入完成时，I/O控制器通过中断请求线向CPU发出中断信号，CPU进行中断处理。

DMA方式：在外设和内存之间开辟直接的数据交换通路。（成块）

通道控制方式：CPU发出启动指令，指出通道相应的操作和I/O 设备，该指令就可启动通道并使该通道从内存中调出相应的通道指令执行。（成组）

中断技术

中断的概念

指CPU对系统发生的某个事件作出的一种反应：

CPU暂停正在执行的程序，

保留现场后自动转去执行相应的处理程序，

处理完该事件后再返回断点继续执行被“打断”的程序。

中断的处理过程

1、保存被中断程序的现场，其目的是为了在中断处理完之后，可以返回到原来被中断的地方继续执行；

2、分析中断源，判断中断原因；

3、转去执行相应的处理程序；

4、恢复被中断程序现场，继续执行被中断程序。

分类

根据中断源的产生的条件，可把中断分为外中断和内中断

中断和陷阱的主要区别

将中断源按照外界因素的作用程度进行划分，常可分为自愿型中断与强迫型中断两大类

	区别
中断	强迫型中断
陷阱	自愿型中断

缓冲技术

引入缓冲技术的原因

1、改善CPU与I/O设备间速度不匹配的矛盾

2、可以减少对 CPU的中断频率，放宽对中断响应时间的限制

3、提高 CPU和 I／O设备之间的并行性

缓冲的设置

根据位置：专用硬件缓冲器，软件缓冲

根据个数：单缓冲、双缓冲和缓冲池

设备分配数据结构

设备无关性

为了提高系统的可适应性和可扩展性，我们希望所编制的用户程序与实际使用的物理设备无关，这就是所谓与设备无关性。

为此，我们将逻辑设备与物理设备区分，并引入逻辑设备名称和物理设备名称的概念

为了实现与设备的无关性，系统中必须有一张联系逻辑设备名称和物理设备名称的映射表，（ＬＵＴ表）

用户I/O：用户程序通过内核提供的系统调用接口与逻辑I/O层交互

设备无关程序

对设备驱动程序的统一接口——向用户层软件提供一个一致接口

设备命名——设备无关软件负责将设备名映射到相应驱动程序

设备保护——检查是否有权访问申请的设备（个人计算机不提供任何保护）

提供独立于设备块大小——逻辑记录到物理记录的转换

缓冲区管理与块设备的存储分配

独占性外围设备的分配和释放——通过 OPEN 打开相应的设备文件进行申请；关闭独占设备同时将释放该设备

错误报告——关键系统数据结构出错（如读磁盘使用状况位图），操作系统打印出错信息，并终止运行

设备驱动程序的功能

(1) 接收由I/O进程发来的命令和参数，并将命令中的抽象要求转换为具体要求，例如，将磁盘块号转换为磁盘的盘面、磁道号及扇区号。　

(2) 检查用户I/O请求的合法性，了解I/O设备的状态，传递有关参数，设置设备的工作方式。

(3) 发出I/O命令，如果设备空闲，便立即启动I/O设备去完成指定的I/O操作；如果设备处于忙碌状态，则将请求者的请求块挂在设备队列上等待。　

(4) 及时响应由控制器或通道发来的中断请求，并根据其中断类型调用相应的中断处理程序进行处理。

(5) 对于设置有通道的计算机系统，驱动程序还应能够根据用户的I/O请求，自动地构成通道程序。

I/O中断处理程序

通知用户程序输入输出操作推进的程度

通知用户程序输入输出操作正常结束（设备通知通道/控制器→CPU）

通知用户程序发现的输入输出操作异常，及提前中止操作的原因

通知程序外围设备上有重要的异步信号，如设备报到、设备结束等

LINUX操作系统

Linux进程调度原则：

按照进程优先级，调度最高优先级进程

进程优先级随时间动态变化

Linux的进程分为普通进程和实时进程

对于普通进程采用可抢占式动态优先级调度：SCHED_OTHER

对于实时进程，采用两种调度策略：

基于优先级(rt-priority)的先进先出调度：SCHED_FIFO，

基于优先级(rt-priority)的时间片轮转调度：SCHED_RR

Linux系统采用段页式存储管理技术，提供虚拟存储功能

补充

管程

是一种共享的数据结构，内部资源只能由内部函数访问，

基本特征：

各外部进程/线程只能通过管程提供的特定入口才能访问共享数据，

每次仅允许一个进程在管程内执行某个内部进程

新增 SSH 密钥到 GitHub 帐户 - GitHub 文档

第一步

1
2
3

cd ~/.ssh
ls
//看是否存在 id_rsa 和 id_rsa.pub文件，如果存在，说明已经有SSH Key

第二步：生成ssh key

如果不存在ssh key，使用如下命令生成

1
2

ssh-keygen -t rsa -C "xxx@xxx.com"
//执行后一直回车即可

第三步：获取ssh key公钥内容（id_rsa.pub）

1
2

cd ~/.ssh
cat id_rsa.pub

复制该内容

第四步：Github账号上添加公钥

进入Settings设置
添加ssh key，把刚才复制的内容粘贴上去保存即

第五步：验证是否设置成功

1

ssh -T git@github.com

注意之后在clone仓库的时候要使用ssh的url，而不是https！

Mysql问题

说一说事物隔离级别

SQL标准的事务隔离级别包括：

读未提交，读提交，可重复读，串行化

事务的四大特性有哪些？

原子性，一致性，隔离性，持久性

Linux系统目录

C++11新特性总结

final关键字

使派生类不可覆盖它所修饰的虚函数

override描述符

如果派生类在虚函数声明时使用了override描述符，那么该函数必须重载其基类中的同名函数

关于左值，右值

C++中所有的值都必然属于左值、右值二者之一。左值是指表达式结束后依然存在的持久化对象，右值是指表达式结束时就不再存在的临时对象。所有的具名变量或者对象都是左值，而右值不具名。很难得到左值和右值的真正定义，但是有一个可以区分左值和右值的便捷方法：看能不能对表达式取地址，如果能，则为左值，否则为右值。

右值引用

左值是指可以出现在=左侧者，

右值是指只能出现在=右侧者

临时对象是个右值

右值引用与move语义的关系

• 关联性: 右值引用是实现move语义的基础
• 作用: 允许”偷取”临时对象的资源而非复制
• 应用场景: 容器操作中大量临时对象的处理

移动语义

右值则临时对象

1

c.insert(ite,Vtype(buf));

左值则使用move关键字

1
2

M c1(c);
M c2(std::move(c1));

• 核心机制
  • 当赋值右侧是右值时，左侧对象可直接”偷取”资源
  • 避免不必要的资源分配和拷贝
• 实现要点
  • 类需要同时实现拷贝和移动语义版本
  • 移动操作后原对象应处于有效但未定义状态
  • 容器需要支持右值版本的插入操作
• 注意事项
  • 被移动后的对象不应再使用
  • 移动构造函数应标记为noexcept
  • 临时对象自动被视为右值
• 典型应用
  • 容器扩容时的元素迁移
  • 返回临时对象的优化
  • 明确不再使用的左值资源转移

应用

1. 函数返回值优化。
2. STL 容器的高效插入与操作。
3. 动态资源管理（如智能指针）。

完美转发

1. 底层数据结构

• 动态数组：元素连续存放且可动态扩展的数组。
• 链表：使用指针将元素链接而成的结构，可分为单向链表与双向链表。
• 平衡二叉树：自平衡的二叉搜索树，常用的是红黑树（Red-Black Tree）。
• 哈希表：以哈希函数作为索引，通过哈希冲突解决机制（如拉链法）高效存储数据。
• 堆：通常是二叉堆，支持动态调整以保证堆顶始终是最大值或最小值。

2. 元素存储特点

• 连续存储：vector 和 array 采用连续存储，内存紧凑，随机访问快。
• 分段连续存储：deque 分段实现，以保证在头尾添加数据的高效性。
• 不连续存储：list、forward_list、set 等采用链表或树结构，插入/删除效率高，但随机访问速度较慢。

3. 访问方式

• 下标访问 ([])：vector、array 支持随机访问，可迅速获取指定位置的元素。
• 头尾访问：stack 和 queue 限制为某些特定操作。
• 优先访问：priority_queue 只能访问堆顶元素（最大值/最小值）。
• 基于 key 访问：map、unordered_map 以键值对方式支持查找。

4. 是否支持随机访问

• 支持随机访问的容器（如 vector、array、deque 等）提供 O(1) 复杂度的下标访问，操作简单。
• 不支持随机访问的容器（如 list、set 等）需要遍历或依赖搜索结构，访问效率较低。

5. 动态大小调整

• 动态容器（如 vector、deque、list）可以根据元素数目动态分配或收缩内存。
• 静态容器（如 array）在定义时需指定固定大小。

6. 应用场景

每种容器都有其典型应用场景，选择合适的容器取决于业务需求（如性能、顺序性、查找效率）。

根据需求选择不同容器：

1. 需要快速随机访问：使用 vector、array。
2. 需要频繁插入和删除：使用 list、deque（插入和删除表现良好）。
3. 需要数据自动排序：使用 set、multiset（有序集合）或 map、multimap（有序键值对）。
4. 需要快速查找，不关心顺序：优先选择哈希容器，比如 unordered_set 和 unordered_map。
5. 使用栈或队列模型：考虑 stack、queue 或 priority_queue。

项目背景： 设计并实现了一个基于 Linux 平台的轻量级 HTTP 服务器，采用多 Reactor 多线程高并发模型，通过 epoll 提供高效的 I/O 复用。结合自动增长缓冲区、定时器和异步日志等技术，实现了高性能和稳定运行的目标。

主要工作

内存优化：设计了内存池和 LFU 缓存，减少内存碎片，提升内存使用效率。

高效事件处理：利用 epoll 多路复用机制，高效监听和处理客户端连接及数据传输事件。

高并发模型：基于 Reactor 模型，实现 One Loop per Thread，支持多客户端并发连接。

动态缓冲区：实现自动增长缓冲区，动态调整大小以适配不同请求，优化内存分配。

连接管理：使用小根堆实现高效定时器，管理连接超时时间，防止长期空闲连接浪费资源。

异步日志：设计异步日志模块，基于单例模式和阻塞队列，实现高效日志写入，避免同步写入的性能开销。

关于项目

介绍一下

本项目是一个高性能的WEB服务器，使用C++实现，项目底层采用了多线程多Reactor的网络模型，并且在这基础上增加了内存池，高效的双缓冲异步日志系统，以及LFU的缓存。

服务器的网络模型是主从reactor加线程池的模式，IO处理使用了非阻塞IO和IO多路复用技术，具备处理多个客户端的http请求和ftp请求，以及对外提供轻量级储存的能力。

项目中的工作可以分为两部分，

一部分是服务器网络框架、日志系统、存储引擎等一些基本系统的搭建，

另一部分 是为了提高服务器性能所做的一些优化，比如缓存机制、内存池等一些额外系统的搭建。

最后还对系统中的部分功能进行了功能和压力测试。对于存储引擎的压力测试，

在本地测试下，存储引擎读操作的QPS可以达到36万，写操作的QPS可以达到30万。对于网络框架的测试，使用webbench创建1000个进程对服务器进行60s并发请求，测试结果表明，对于短连接的QPS为1.8万，对于长连接的QPS为5.2万。

项目难点

根据工作分为两部分

一部分是服务器网络框架，日志系统，存储引擎等一些基本系统的搭建，这部分的难点主要就是技术理解和选型，以及将一些开源的框架调整后应用到我的项目中去。

另一部分就是性能优化方面，比如缓存机制，内存池等一些额外系统的搭建。这部分的难点在于找出服务器的性能瓶颈所在，然后结合自己的想法突破瓶颈，提高服务器性能。

遇到的困难，怎么解决

一方面是对技术理解不够深刻，难以选出合适的技术框架，这部分主要是阅读作者的技术文档，找相关的解析文章看

另一部分是编程遇到的困难，由于工程能力不足出现bug，这部分主要是通过日志定位bug，推断bug出现的原因并尝试修复，如果以自己能力无法修复，先问问ai能提供什么思路，或者搜索相关的博客。

内存优化

设计了内存池和 LFU 缓存

缓存机制

为什么选择LFU

因为最近加入的数据因为起始的频率很低，容易被淘汰，而早期的热点数据会一直占据缓存。

高效事件处理：

epoll 多路复用机制

采用非阻塞I/O模型，执行系统调用就立即返回，不检查事件是否发生，没有立即发生返回-1，errno设置为在处理中。所以要采用I/O通知机制（I/O复用和SIGIO信号）来得知就绪事件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

I/O多路复用技术
I/O 多路复用允许一个线程同时监视多个 I/O 文件描述符（如网络 socket），并在其中一个或多个文件描述符变为"可操作"时返回。应用程序可以据此进行相应的 I/O 操作（如读、写）。

1.1 select
简介
select 是一种最早的 I/O 多路复用接口，几乎所有主流平台都支持。

它允许程序监视多个文件描述符，查询它们是否可读、可写或出现错误。
select 的接口会使用三个位图（readset、writeset 和 exceptset）指定文件描述符的状态。
工作原理
调用 select 时，程序将文件描述符集（一个位图）传递给内核。
内核在超时时间内扫描这些文件描述符并返回那些状态发生变化的描述符（如变为可读或可写）。
用户态程序可根据返回结果进行相应的 I/O 操作。
缺点
支持的文件描述符数量有限（通常受 FD_SETSIZE 限制，默认 1024）。
每次调用时都需要将文件描述符的状态从用户态复制到内核态，这带来一定的性能开销。
内核需要线性遍历所有文件描述符（效率低），尤其在大并发连接时性能较差。
1.2 poll
简介
poll 是 select 的改进版本，克服了文件描述符数量限制的问题。

它使用一个数组结构而不是位图来描述文件描述符及其事件。
工作原理
用户定义一个 pollfd 数组，该数组中每一个元素保存一个文件描述符及其相关事件。
调用 poll 时，内核会遍历这个数组，检查哪些文件描述符有事件发生，并返回结果。
优点
支持任意数量的文件描述符，突破了 select 的 FD_SETSIZE 限制。
缺点
和 select 类似，每次调用都需要将监控的文件描述符数组从用户态复制到内核态，开销较大。
和 select 一样，内核需要线性遍历文件描述符，在高并发场景下效率仍然较低。
1.3 epoll
简介
epoll 是 Linux 平台下提供的高性能 I/O 多路复用接口，它是 select 和 poll 的替代品。

epoll 被设计用于解决 select 和 poll 的性能问题，是一种效率更高的方式处理大量并发连接的技术。
工作原理
epoll 的核心思想是使用事件驱动机制（Event-Driven）替代轮询机制。

创建一个 epoll 实例（epoll_create），用作事件管理器。
使用 epoll_ctl 向内核注册需要监听的具体文件描述符及其事件类型（关注可读、可写或异常事件）。
调用 epoll_wait，等待事件发生。
发生事件的文件描述符被加入到一个内核维护的就绪列表，并从中直接返回。
这避免了不必要的遍历额外文件描述符的开销。
优点
事件驱动模型：文件描述符有变化时通过回调机制加入就绪列表，只需处理活跃文件描述符。
无大小限制：最大受限于系统的内存资源，而非固定限制。
高性能：避免了线性遍历，即使监视十万连接，只需处理少量已就绪的描述符。
缺点
仅支持 Linux 系统，不跨平台。
epoll 的两种触发模式
LT（Level Trigger，水平触发）： 默认模式，文件描述符只要处于就绪状态，就会不断返回。
ET（Edge Trigger，边缘触发）： 更高效，只在文件描述符状态从未就绪到就绪时触发（适用于非阻塞 I/O）

IO多路复用

LT与ET

LT:水平触发模式，只要内核缓冲区有数据就一直通知，只要socket处于可读状态就一直返回sockfd；是默认的工作模式，支持阻塞IO和非阻塞IO

ET：边沿触发模式，只有状态发生变化才通知并且这个状态只会通知一次，只有当socket由不可写到可写或由不可读到可读，才会返回sockfd：只支持非阻塞IO

为什么用epoll，其他多路复用方式以及区别

高并发模型

基于 Reactor 模型，实现 One Loop per Thread

Reactor模式通常用同步I/O模型实现

Proactor模式通常用异步I/O模型实现

1. 主线程往epoll内核事件表注册socket读就绪事件
2. 主线程调用epoll_wait等待socket上有数据可读
3. 当socket上有数据可读时，epoll_wait通知主线程，主线程将socket可读事件放入请求队列
4. 工作线程被唤醒，读数据处理请求，然后往epoll内核事件表注测socket写就绪事件
5. 主线程调用epoll_wait等待socket可写
6. 当socket可写，epoll_wait通知主线程，主线程将socket可写事件放入请求队列
7. 睡眠在请求队列的工作线程被唤醒，往socket上写入服务器处理客户请求的结果

动态缓冲区

实现自动增长缓冲区

1. 核心数据结构

1
2
3
4
5
6

class Buffer {
private:
    std::vector<char> buffer_;  // 主缓冲区（使用vector自动管理内存）
    size_t readerIndex_;         // 读指针（数据起始位置）
    size_t writerIndex_;         // 写指针（数据结束位置）
};

采用vector作为底层容器，自动处理内存分配/释放

读写指针分离设计，支持零拷贝操作

零拷贝是指计算机执行IO操作时，CPU不需要将数据从一个存储区域复制到另一个存储区域，从而可以减少上下文切换以及CPU的拷贝时间。它是一种I/O操作优化技术。

2. 自动增长机制

(1) 扩容触发条件

当writableBytes() < 待写入数据量时自动扩容

通过vector的resize实现：

1
2
3
4
5
6
7

void append(const char* data, size_t len) {
    if (writableBytes() < len) {
        makeSpace(len);  // 扩容操作
    }
    std::copy(data, data+len, beginWrite());
    writerIndex_ += len;
}

(2) 智能扩容策略

1
2
3
4
5
6
7
8
9
10
11
12

void makeSpace(size_t len) {
    if (writableBytes() + prependableBytes() < len) {
        // 需要真正扩容：vector.resize(writerIndex_ + len)
        buffer_.resize(writerIndex_ + len);
    } else {
        // 通过移动数据复用空间
        size_t readable = readableBytes();
        std::copy(begin()+readerIndex_, begin()+writerIndex_, begin());
        readerIndex_ = 0;
        writerIndex_ = readable;
    }
}

3. 高性能IO优化

(1) 双缓冲区读操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

ssize_t readFd(int fd, int* saveErrno) {
    char extrabuf[65536]; // 64KB栈缓冲区
    iovec vec[2];
    
    vec[0].iov_base = begin() + writerIndex_;
    vec[0].iov_len = writableBytes();
    vec[1].iov_base = extrabuf;
    vec[1].iov_len = sizeof(extrabuf);
    
    // 根据剩余空间决定使用1个还是2个缓冲区
    const int iovcnt = (writableBytes() < sizeof(extrabuf)) ? 2 : 1;
    ssize_t n = readv(fd, vec, iovcnt);
    
    // 处理读入的数据...
}

使用readv系统调用实现分散读

优先使用主缓冲区空间，不足时使用栈缓冲区过渡

避免频繁扩容带来的性能损耗

(2) 写操作优化

1
2
3

ssize_t writeFd(int fd, int* saveErrno) {
    return ::write(fd, peek(), readableBytes());
}

直接使用write系统调用

peek()返回有效数据起始指针，避免内存拷贝

4. 关键特性总结

1. 智能扩容：按需自动增长，兼顾内存使用效率

2. 零拷贝设计：读写指针分离，减少内存拷贝

3. 双缓冲策略：栈空间+主缓冲区组合优化IO性能

4. 线程安全：单次IO操作原子性保证

5. 内存高效：自动回收已读区域空间

典型工作流程：

1. 读取数据时优先使用主缓冲区空间

2. 空间不足时暂存到栈缓冲区

3. 触发自动扩容后合并数据

4. 写入数据时直接操作有效数据区域

连接管理

使用小根堆实现高效定时器，管理连接超时时间

1
2

using Entry = std::pair<Timestamp, Timer*>; // 以时间戳作为键值获取定时器
using TimerList = std::set<Entry>;          // 底层使用红黑树管理，自动按照时间戳进行排序

1
2

// 定时器管理红黑树插入此新定时器
timers_.insert(Entry(when, timer));

异步日志

设计异步日志模块，基于单例模式和阻塞队列

日志系统是多生产者，单消费者的任务场景

多生产者负责把日志写入缓冲区，单消费者负责把缓冲区数据写入文件

前端往后端写，后端往硬盘写

双缓冲技术 ，写满就交换，相当于将多条日志拼接成一个大buffer传送到后端然后写入文件，减少了线程开销

Mysql问题

说一说事物隔离级别

SQL标准的事务隔离级别包括：

读未提交，读提交，可重复读，串行化

事务的四大特性有哪些？

原子性，一致性，隔离性，持久性

Linux系统目录