软件设计师上午题知识点

约 51837 字大约 173 分钟

软件设计师

2025-03-18

上午题知识点

计算机组成原理

计算机基本工作原理

冯诺依曼体系结构

一、核心思想

存储程序 + 程序控制 计算机的 程序和数据统一存储在内存中，CPU 按顺序读取指令并执行。

二、五大组成部分

部件	功能	类比
运算器	算术运算（如加减乘除）和逻辑运算（如与或非）	计算器
控制器	指挥各部件协调工作（取指令、译码、执行）	指挥官
存储器	存放程序和数据（内存、硬盘等）	仓库
输入设备	将外部信息（如键盘、鼠标）输入到计算机	眼睛 / 耳朵
输出设备	将处理结果输出（如显示器、打印机）	嘴巴 / 手

三、工作流程

输入：用户通过输入设备（如键盘）输入程序或数据。
存储：程序和数据存入存储器（如内存）。
执行
- 取指令：控制器从内存读取指令到 CPU。
- 译码：分析指令功能（如加法、跳转）。
- 执行：运算器完成操作，结果存入内存或寄存器。
输出：结果通过输出设备（如屏幕）显示。

计算机工作基本原理

寄存器

寄存器是什么？

定义：寄存器是 CPU 内部的 高速存储单元，用于 临时存放数据、指令或地址。特点：

访问速度极快（纳秒级，比内存快 100 倍以上）。
容量极小（通常每个 CPU 有几十个寄存器）。比喻：类似你办公桌上的 临时小抽屉，存放你正在处理的文件（数据 / 指令），伸手就能拿到。

寄存器的分类与作用

寄存器类型	作用	典型例子
通用寄存器	存放临时数据、运算结果	AX（累加器）、BX（基址寄存器）
程序计数器（PC）	存储下一条要执行的指令地址	PC
指令寄存器（IR）	存放当前正在执行的指令	IR
地址寄存器（MAR）	存放内存访问的地址（如读取数据或指令）	MAR
状态寄存器（FLAGS）	记录运算状态（如进位、溢出、零标志）	CF（进位标志）、ZF（零标志）

校验码

CRC：模 2 运算 生成校验码，检错不纠错。
海明码：校验位定位错误，纠错能力强。
奇数校验：简单检错，但 可靠性低。

循环冗余校验（CRC）

循环冗余校验（CRC）

核心原理：通过 多项式除法（模 2 运算）生成校验码，用于检错。
常考点：
- 生成多项式选择（如 CRC-16、CRC-32）。
- 计算步骤：在数据后补 0，与生成多项式进行模 2 除法，余数即为校验码。
- 检错能力：可检测 所有奇数位错误 和 突发错误（长度 ≤ 生成多项式位数）。

海明码

核心原理：通过插入 校验位（r 位），利用 奇偶校验 实现纠错。
常考点：
- 校验位位置：满足 2^r ≥ k + r + 1（k 为数据位，r 为校验位）。
- 校验位计算：按位异或对应数据位。
- 纠错过程：通过校验位组合定位错误位置。
- 能力：可纠正 1 位错误，检测 2 位错误。

奇数校验

核心原理：使 数据位 + 校验位 的 1 的总数为奇数。
常考点：
- 校验位生成：根据数据位中 1 的个数确定（奇校验补 1，偶校验补 0）。
- 局限性：仅能检测 奇数位错误，无法纠错。
- 应用场景：简单通信（如串口传输）。

原码补码反码移码

之间的相互转换

原码
- 定义：符号位（0 正 1 负）+ 数值绝对值的二进制表示。
- 示例（8 位）：
  - +6 → 0000 0110
  - -6 → 1000 0110
- 转换规则：直接按符号位 + 数值转换。
反码
- 定义：正数与原码相同；负数符号位不变，其余位取反。
- 示例（8 位）：
  - +6 → 0000 0110
  - -6 → 1111 1001
- 转换规则：原码 → 反码（负数取反）。
补码
- 定义：正数与原码相同；负数为反码末位加 1。
- 示例（8 位）：
  - +6 → 0000 0110
  - -6 → 1111 1010
- 转换规则：反码 → 补码（末位 + 1）。
移码
- 定义：补码符号位取反（常用于浮点数阶码）。
- 示例（8 位）：
  - +6 → 1000 0110
  - -6 → 0111 1010
- 转换规则：补码 → 移码（符号位取反）。

表示范围

码制	整数范围	特殊值说明
原码	-127 ~ +127	±0 表示不同（`0000 0000` 和 `1000 0000`）
反码	-127 ~ +127	±0 表示不同（`0000 0000` 和 `1111 1111`）
补码	-128 ~ +127	唯一 0（`0000 0000`），-128 表示为 `1000 0000`
移码	-128 ~ +127	符号位取反，便于比较大小唯一 0

真值计算

原码转真值
- 1001 0101 → 符号位 1（负），数值 001 0101 → -37。
补码转真值
- 1111 0101 → 符号位 1（负），取反得 0000 1010，加 1 得 0000 1011 → -11。
移码转真值
- 0111 0101 → 符号位取反得补码 1111 0101 → 真值 - 11。

浮点数

浮点数在计算机中用以近似表示任意某个实数，一个浮点数 a 可如下表示: a = M*bE。

尾数部分 M 的位数越多，数的精度越高。

指数部分 E 的位数越多，能表示的数值越大。

因此在总长度固定的情况下，增加 E 的位数、减少 M 的位数可以扩大可表示的数的范围同时降低精度。

定点表示和浮点表示

类型	定义	特点
定点表示	小数点位置固定（如整数、纯小数），直接存储数值。	- 精度固定，范围小。 - 适合处理整数或固定精度小数。
浮点表示	采用科学计数法形式：尾数 × 基数 ^ 阶码（如 `±1.xxxxx×2^±yyy`）。	- 动态范围大，精度可变。 - 适合处理大范围数值（如科学计算）。

规格化

目的：使浮点数的表示唯一且有效位数最大化。条件：

原码规格化：尾数最高位必须为 1（避免前导零）。
- 例：1.0101×2^3（有效），0.1010×2^4（无效，需调整为 1.010×2^3）。
补码规格化：
- 正数：最高位为 1。
- 负数：最高位为 0（补码负数的绝对值最大，如 1.0101 表示 - 0.9375）。

意义：消除冗余表示，提高精度。

如何计算浮点数的表示范围

与或异或同或

输入 A	输入 B	与（AND）	或（OR）	异或（XOR）	同或（XNOR）
0	0	0	0	0	1
0	1	0	1	1	0
1	0	0	1	1	0
1	1	1	1	0	1

关键规则说明

与（AND）：只有 两个都为 1 时，结果才为 1。 → 口诀：“有 0 则 0，全 1 才 1”。
或（OR）：只要 有一个为 1，结果就为 1。 → 口诀：“有 1 则 1，全 0 才 0”。
异或（XOR）：两个值不同时结果为 1，相同则为 0。 → 口诀：“不同为 1，相同为 0”。
同或（XNOR）：两个值相同时结果为 1，不同则为 0。 → 口诀：“相同为 1，不同为 0”（等同于异或结果取反）。

冗余技术

冗余是指对于实现系统规定功能是多余的那部分资源，包括硬件、软件、信息和时间。通常冗余技术分为 4 类:

1.结构冗余，按其工作方法可以分为静态、动态和混合冗余;

2.信息冗余，指的是为了检测或纠正信息在运算或传输中的错误另外加的一部分信息;

3.时间冗余，是指以重复执行指令或程序来消除瞬时错误带来的影响;

4.冗余附件技术，是指为实现上述冗余技术所需的资源和技术。

存储系统

主存、辅存、cache

存储类型	全称	速度	容量	作用	典型设备
Cache	高速缓存	极快（纳秒级）	极小（MB 级）	缓解 CPU 与主存的速度差异	CPU 内置缓存
主存	主存储器	快（微秒级）	中等（GB 级）	CPU 直接访问的临时存储	内存条
辅存	辅助存储器	慢（毫秒级）	大（TB 级）	长期存储程序和数据	硬盘、SSD

主存主要采用动态随机存储器 DRAM

Cache 采用静态随机存储器 SRAM

EEPROM 是电擦除可编程的只读存储器

Cache 与主存之间的映射由硬件实现，主存与辅存之间的交互是硬件与软件结合起来实现的。

存储层次结构
- 常考：Cache - 主存 - 辅存构成三级存储体系，速度递减、容量递增。
命中率优化
- 示例：Cache 命中率越高，CPU 等待时间越少，性能越好。
虚拟内存技术
- 常考：主存不足时，部分数据暂存到辅存（虚拟内存），但会导致速度下降。

全相联、直接相连、组相连映射对比详解

一、核心概念**

直接相连映射（Direct Mapping）
- 主存块只能映射到 Cache 的唯一固定位置。
- 例如：主存块 0 → Cache 块 0，主存块 1 → Cache 块 1，依此类推。
组相连映射（Set Associative Mapping）
- 主存块映射到 Cache 的 某个组（如每组 4 块），组内块可自由选择。
- 例如：主存块 0 → Cache 组 0 的任意块（块 0-3）。

全相联映射（Fully Associative Mapping）

主存块可映射到 Cache 的 任意位置，无固定限制。

二、工作原理对比

映射方式	地址划分	查找逻辑	替换策略
直接相连	主存地址 = 块号 + 块内偏移	根据块号直接定位 Cache 块	固定替换（如覆盖）
组相连	主存地址 = 组号 + 块号 + 块内偏移	先定位组，再查找组内块	LRU、FIFO 等
全相联	主存地址 = 标签 + 块内偏移	遍历所有 Cache 块，对比标签	LRU、FIFO 等

三、特点对比表

对比项	直接相连	组相连	全相联
映射规则	固定位置	组内自由	完全自由
冲突率	高（易地址冲突）	中	低
查找速度	快（直接计算地址）	中（组内搜索）	慢（全 Cache 搜索）
硬件复杂度	低	中	高（需全比较电路）
典型应用	片外 Cache、简单系统	一级 Cache、通用系统	小容量 Cache、高性能场景

存储容量、存储块的计算方式

存储容量计算

存储容量 指存储器能存储的二进制信息总量，公式为： 存储容量 = 存储单元数 × 每个单元的位数

若某存储器有 1024 个存储单元，每个单元 8 位，则总容量为： 1024 × 8 = 8192位 = 1024字节（1KB）
单位换算： 1KB=1024B，1MB=1024KB，1GB=1024MB，依此类推。

存储块计算方式

存储块 是主存与 Cache 之间数据交换的最小单位，计算需明确：

主存总容量
块大小（主存与 Cache 的块大小必须一致）
公式： 主存块数量 = 主存总容量 ÷ 块大小Cache 块数量 = Cache 总容量 ÷ 块大小

示例：

主存容量 1MB，块大小 16 字节： 1MB ÷ 16B = 65536块
Cache 容量 64KB，块大小 16 字节： 64KB ÷ 16B = 4096块

计算机的存储体系

计算机中不同容量、不同速度、不同访问形式、不同用途的各种存储器形成的是一种层次结构的存储系统。所有的存储器设备按照一定的层次逻辑关系通过软硬件连接起来，并进行有效的管理，就形成了存储体系。不同层次上的存储器发挥着不同的作用。

一般计算机系统中主要有两种存储体系:

Cache 存储体系由 Cache 和主存储器构成，主要目的是提高存储器速度，对系统程序员以上均透明; 虚拟存储体系由主存储器和在线磁盘存储器等辅存构成，主要目的是扩大存储器容量，对应用程序员透明。

存储体系中的存储器

按访问方式可分为按 地址访问的存储器 和 按内容访问的存储器;

按寻址方式分类可分为 随机存储器、顺序存储器 和 直接存储器。

随机存储器(Random AccessMemory，RAM)指可对任何存储单元存入或读取数据，访问任何一个存储单元所需的时间是相同的。
顺序存储器(Sequentially AddressedMemory，SAM)指访问数据所需要的时间与数据所在的存储位置相关，磁带是典型的顺序存储器。
直接存储器(Direct AddressedMemory，DAM)是介于随机存取和顺序存取之间的一种寻址方式。磁盘是一种直接存取存储器，它对磁道的寻址是随机的，而在一个磁道内，则是顺序寻址。

按照内容访问可分为相联存储器

相联存储器是一种按内容访问的存储器。其工作原理就是把数据或数据的某一部分作为关键字，将该关键字与存储器中的每一单元进行比较，从而找出存储器中所有与关键字相同的数据字。

总线系统

概念

总线（Bus）是一组信号线组成的传输线束，它作为计算机各种功能部件之间传送信息的公共通信干线。根据计算机所传输的信息种类，总线可以分为数据总线、地址总线和控制总线。

数据总线（Data Bus）：用于在 CPU 与 RAM 之间来回传送需要处理或是需要储存的数据。它是双向的，意味着数据可以在两个方向上传输。
地址总线（Address Bus）：用来指定在 RAM 之中储存的数据的地址。它是单向的，从 CPU 发出到内存或其他设备。
控制总线（Control Bus）：将微处理器控制单元的信号传送到周边设备，如 USB Bus 和 1394 Bus 等。

总线的分类

总线可以根据其所在位置、传输方式和工作模式进行分类：

按位置分：
- 内部总线（片内总线）：存在于 CPU 芯片内部，用于寄存器之间和算术逻辑部件 ALU 与控制部件之间的数据传输。
- 系统总线（板级总线）：连接微机各插件板与系统板之间的总线，实现插件板一级的互联。
- 外部总线（通信总线）：连接计算机与其他外部设备或系统之间的总线。
按传输方式分：
- 并行总线：多位数据同时通过多条线路传输，适合短距离高速数据传输。
- 串行总线：数据一位接一位地顺序传输，适用于长距离传输，成本较低且抗干扰能力强。
按工作模式分：
- 单工：数据只能在一个方向上传输。
- 半双工：允许数据双向传输，但同一时间只能在一个方向上进行。
- 全双工：支持数据同时双向传输。

总线性能指标

了解总线的性能指标对于评估系统的效率至关重要。主要的性能指标包括：

带宽（Bandwidth）：指总线每秒可以传输的最大数据量，通常以位/秒（bps）或字节/秒（Bps）表示。
总线速度（Bus Speed）：即总线的时钟频率，决定了每秒能进行多少次数据传输周期。
总线协议（Bus Protocol）：定义了总线上的设备如何进行通信的具体规则。
总线仲裁（Bus Arbitration）：当多个设备尝试同时访问总线时，决定哪个设备获得优先权的机制。

总线设计考虑因素

在选择或设计总线时，需要综合考虑以下因素：

数据传输速率的需求。
可靠性和稳定性，尤其是在高负载情况下。
成本效益分析，包括硬件成本和维护成本。
电磁兼容性（EMC），特别是在并行总线设计中尤为重要。

总线结构

单总线结构（Single Bus Architecture）

结构
所有设备共享一条单一总线（数据、地址、控制信号复用）。
特点
- 优点：简单、成本低、易于扩展。
- 缺点：带宽瓶颈（多设备竞争）、延迟高。
应用场景：早期微型计算机（如 8 位 / 16 位系统）、嵌入式系统。

2. 双总线结构（Dual Bus Architecture）

结构分为
系统总线（连接 CPU、内存）和 I/O 总线（连接外设）。
特点
- 优点：分离高速与低速设备，减少冲突。
- 缺点：需通过桥接器（如北桥芯片）中转，增加延迟。
应用场景：传统 x86 架构计算机（如 PCI 总线与 ISA 总线并存）。

3. 多总线结构（Multi-Bus Architecture）

结构
多级总线分层连接，如高速总线（如 PCIe）连接 CPU 与显卡，低速总线（如 USB）连接外设。
特点
- 优点：优化带宽分配，支持高速设备（如 GPU、SSD）。
- 缺点：复杂度高，需总线控制器协调。
应用场景：现代服务器、高性能计算机。

4. 层次化总线结构（Hierarchical Bus Architecture）

结构
总线按层次划分，如：
1. 片内总线（SoC 内部，如 AMBA AHB/AXI）；
2. 系统总线（主板级，如 PCIe）；
3. 外部总线（外设级，如 USB）。
特点
- 优点：分层管理，提升整体性能。
- 缺点：依赖协议兼容性（如 PCIe 与 USB 的转换）。
应用场景：智能手机 SoC（如骁龙芯片）、个人计算机。

5. 专用总线结构

示例
- 内存总线：专用连接 CPU 与内存（如 DDR4/DDR5）；
- 存储总线：连接存储控制器与硬盘（如 SATA、NVMe）。

特点

优点：针对特定设备优化，高带宽、低延迟。
缺点：通用性差。

总线结构的性能对比

结构类型	带宽	延迟	扩展性	典型应用
单总线	低	高	有限	嵌入式系统、早期微机
双总线	中	中	中等	传统 PC（已淘汰）
多总线	高	低	强	服务器、游戏 PC
层次化总线	极高	极低	极强	智能手机 SoC、高性能计算

总线带宽计算

总线带宽 = 总线宽度 × 时钟频率

假设我们有一个 32 位宽的总线，并且它的时钟频率是 200MHz，那么根据上述公式，我们可以这样计算总线带宽：

总线带宽 = 32 bits×200 MHz = 6400 Mbits/s

但是，因为数据传输率通常以字节（Byte）而非比特（bit）来表示，我们需要将结果转换成字节形式。由于 1 字节等于 8 比特，所以：

总线带宽 = 64008 MB/s = 800 MB/s

或者，如果我们想要将其转换为 GB/s，则需要进一步除以 1024：

总线带宽 = 8001024 GB/s≈0.78 GB/s

输入输出系统

概念

输入输出定义
- 输入：数据从外部设备传入计算机（如键盘、扫描仪）。
- 输出：数据从计算机传出到外部设备（如显示器、打印机）。
输入输出系统组成
- 外设：输入 / 输出设备（如磁盘、网卡）。
- I/O 接口：连接 CPU 与外设的桥梁，含数据、状态、控制寄存器。
- 总线：系统总线（地址、数据、控制）用于传输信号。

数据传送方式

无条件传送
- CPU 直接读写外设，无需状态查询。
- 适用场景：简单外设（如开关、LED）。
查询传送
- CPU 循环检测外设状态，就绪后传输数据。
- 优点：实现简单；缺点：CPU 利用率低。
中断方式
- 外设主动向 CPU 发送中断请求，CPU 暂停当前任务处理中断。
- 优点：CPU 利用率高；缺点：需处理中断上下文切换。
DMA（直接内存访问）
- 外设直接访问内存，无需 CPU 干预。
- 优点：高速传输，适合大块数据（如磁盘读写）；缺点：硬件成本高。
- 常考对比：DMA 与中断的区别（CPU 是否参与数据传输）。

中断嵌套

当系统中有多个中断请求时，中断系统按优先级进行排队。若在处理低级中断过程中又有高级中断申请中断，则高级中断可以打断低级中断处理，转去处理高级中断，等处理完高级中断后再返回去处理原来的低级中断，称为中断嵌套。

实现中断嵌套用后进先出的栈来保护断点和现场最有效。

指令系统和计算机体系结构

程序的局部性

一、核心概念

程序的局部性原理是指 程序在执行时倾向于访问 **** 近期使用过的数据或指令，以及 邻近的数据或指令。这一特性是计算机系统设计（如缓存、虚拟内存）的基础，也是程序优化的重要依据。

二、局部性分类

时间局部性（Temporal Locality）
- 定义：如果一个数据或指令被访问，那么在 不久的将来 很可能再次被访问。
- 示例
  - 循环中的变量（如 for (int i=0; i<1000; i++) 中的 i）。
  - 函数调用中的局部变量（多次被使用）。
空间局部性（Spatial Locality）
- 定义：如果一个数据或指令被访问，那么与其 相邻的内存区域 的数据或指令也可能很快被访问。
- 示例
  - 连续存储的数组元素（如 arr[0], arr[1], arr[2]）。
  - 代码中的顺序执行（如连续的指令块）。

精简指令系统和复杂指令系统

RISC（精简指令系统）
- 设计理念：简化指令集，通过减少指令种类和复杂度提升执行效率。
- 典型代表：ARM、MIPS、RISC-V。
CISC（复杂指令系统）
- 设计理念：提供丰富复杂的指令，通过单条指令完成复杂操作以减少代码量。
- 典型代表：x86（如 Intel/AMD 处理器）。

对比项	RISC	CISC
指令数量	少（约 100 条以内）	多（可达数百条）
指令长度	固定（便于流水线处理）	可变（复杂指令长度不同）
执行周期	单周期执行	多周期执行
内存访问	仅 LOAD/STORE 指令访问内存	指令可直接操作内存
流水线效率	高（指令简单，并行性强）	低（指令复杂，易阻塞流水线）
硬件复杂度	低（无需微程序控制）	高（需微程序解析复杂指令）
编译器依赖	高（依赖编译器优化）	低（指令功能强，编程灵活）

流水线概念以及常见计算

一、吞吐率定义

概念：单位时间内完成的指令数量（或任务数），衡量流水线的处理效率。
公式： 吞吐率（TP）= 指令数（n） / 总执行时间（T） 单位：指令数 / 时间单位（如条 / 秒、条 /ns）。

二、流水线吞吐率计算

最大吞吐率（理想情况）
- 当流水线完全填满后，每周期完成一条指令。最长执行时间的倒数
- 公式： 最大吞吐率（TP_max）= 1 / 最长阶段时间（Δt_max）
- 示例：最长阶段时间为 3ns → TP_max ≈ 0.33 条 /ns。
实际吞吐率（考虑指令数）
- 公式： TP = n / [ (k + n -1) × Δt_max ] （k 为阶段数，n 为指令数）
- 示例：k = 5，n = 100，Δt_max = 3ns → TP = 100 / 312 ≈ 0.32 条 /ns。

VLIW（超长指令字）

一种非常长的指令组合，把许多条指令连在一起增加运算速度。

寻址方式

采用不同寻址方式的目的是为了扩大寻址空间提高编程灵活性

类型	定义	示例	特点
立即寻址	操作数直接包含在指令中	`ADD R0, #5`（R0 += 5）	无需内存访问，速度快，但操作数范围受限（受指令长度限制）。
直接寻址	指令中包含内存地址	`LOAD R1, [0x1000]`（R1 = 内存 0x1000）	地址固定，适合访问静态数据，但地址空间有限（需完整地址位）。
寄存器寻址	操作数存于寄存器中	`ADD R0, R1`（R0 += R1）	速度最快，RISC 架构核心方式（如 ARM、RISC-V）。
寄存器间接寻址	寄存器存储内存地址	`LOAD R2, [R3]`（R2 = 内存 [R3]）	灵活访问动态数据，适合数组、指针操作。
基址寻址	基址寄存器 + 偏移量确定地址	`LOAD R4, [R5+0x20]`（R4 = 内存 [R5+32]）	简化数组、结构体访问，支持内存分段管理。
变址寻址	变址寄存器 + 偏移量确定地址	`LOAD R6, [0x1000+R7]`（R6 = 内存 [2560 + R7]）	适合循环遍历数组，偏移量固定，寄存器动态调整。
相对寻址	当前指令地址 + 偏移量确定地址	`JMP 0x10`（跳转到当前地址 + 16）	常用于分支指令，节省地址空间（只需偏移量）。

典型应用场景

立即寻址：初始化常量、简单运算。
寄存器间接寻址：动态数据访问（如链表、堆内存）。
基址 + 变址寻址：二维数组、结构体成员访问。
相对寻址：程序跳转（如函数调用、条件分支）。

寻址范围计算

范围 = 内存容量/字节长度

flynn 分类法

Flynn 分类法定义

提出背景：由 Michael J. Flynn 于 1966 年提出，用于 根据指令流（Instruction Stream）和数据流（Data Stream）的并行性 对计算机体系结构进行分类。

核心维度：

指令流并行性：是否同时执行多条指令。
数据流并行性：是否同时处理多个数据项。

Flynn 分类法四大类型

类型	全称	指令流	数据流	特点	典型应用
SISD	单指令流单数据流	单指令	单数据	传统串行计算机，无并行处理能力。	早期个人计算机（如 8086）
SIMD	单指令流多数据流	单指令	多数据	一条指令操作多个数据（数据级并行）。	GPU、向量处理器（如 Intel AVX）
MISD	多指令流单数据流	多指令	单数据	理论上存在，实际应用极少（可能用于容错处理）。	研究原型（如某些纠错系统）
MIMD	多指令流多数据流	多指令	多数据	多条指令独立操作多个数据（任务级并行）。	多核 CPU、分布式计算集群

系统性能评测和可靠性基础

系统可靠度计算

可靠度表示为 R

串联: R 相乘

示例：R1 = 0.9, R 2 = 0.95, R 3 = 0.98。

R 串联 = 0.9×0.95×0.98 = 0.8379(83.79%)

并联:

两个并联为 1-(1-R)²

R = 0.9

R 并联 = 1−(0.1×0.1)= 0.99(99%)

可靠度为（1-（1-R）³）（1-（1-R）²）

程序语言

程序设计语言基础概念

核心概念

低级语言 vs 高级语言
- 低级语言：机器语言（二进制指令）、汇编语言（符号指令），执行效率高但开发效率低。
- 高级语言：Java、C、Python 等，接近自然语言，开发效率高但需翻译（编译 / 解释）。
编译程序 vs 解释程序
- 编译程序：一次性生成目标程序（如.exe 文件），执行效率高，不可调试。
- 解释程序：边翻译边执行，开发灵活但效率低（如 Python、JavaScript）。
语言三要素
- 语法：结构规则（如括号匹配、分号结尾）。
- 语义：逻辑含义（如变量类型是否匹配）。
- 语用：符号与使用者的关系（如注释、代码规范）。

语言处理程序基础

词法分析：识别单词符号（如关键字、标识符）。
语法分析：检查语法结构（如表达式是否合法）。
语义分析：类型检查（如整数与字符串相加错误）。
中间代码生成：转换为与机器无关的代码（如逆波兰式、四元式）。
代码优化：提升执行效率（如循环展开、冗余删除）。
目标代码生成：输出机器语言或汇编代码。

程序设计语言基本成分

数据成分
- 常量 / 变量：全局量（静态存储） vs 局部量（动态存储）。
- 数据类型：基本类型（int、char）、构造类型（数组、结构体）、抽象类型（类）。
控制成分
- 条件语句：if-else、switch-case。
- 循环语句：for、while、do-while。
- 函数调用:
  - 值调用：形参修改不影响实参。
  - 引用调用：形参修改直接影响实参（如 C++ 的指针）。
运算成分
- 运算符优先级：如 * 高于 +。
- 逻辑运算：&&（短路与）、||（短路或）、!。

核心传递方式对比（软考高频）

方式	定义	语言示例	是否修改实参	常考陷阱
值调用	传递参数副本，函数内修改不影响实参。	C 的普通参数、Java 基本类型	❌ 否	交换函数无效（如 `swap(int a, int b)` 无法交换实参）。
引用调用	传递实参地址（或别名），函数内修改直接影响实参。	C++ 引用（`&`）、C# `ref`/`out`	✅ 是	Java 对象引用是 “值传递的引用”：可修改对象属性，但无法改变引用指向（如无法交换两个对象）。
指针传递	传递指针变量（地址的副本），通过解引用修改实参。	C 的指针（`int*`）	✅ 是	区分 “传递指针” 与 “传递指针指向的值”：`func(int* p)` 可改 `*p`，但无法改 `p` 本身（如交换指针无效）。
传名调用	参数在调用处替换为表达式，可能多次求值（已过时，软考仅考概念）。	Algol、早期 Pascal	✅ 可能	副作用：表达式含自增（如 `a++`）时，多次求值导致结果不可控。

典型语言实现与常考细节

C 语言
- 值调用：默认方式，如 void f(int x) { x=5; }，调用后实参不变。
- 指针传递：需显式传递地址，如 void f(int* x) { *x=5; }，调用 f(&a) 修改 a。
- 常考题：交换函数必须用指针，否则无效。
C++
- 引用调用：void f(int& x) { x=5; }，实参直接被修改。
- 区别指针：引用必须初始化，且语法更简洁（无需 *）。
Java
- 基本类型：值调用，如 void f(int x) 无法修改实参。
- 对象类型：传递对象引用的副本（值调用的引用），可修改对象属性（如 obj.name="new"），但无法改变引用指向（如无法通过函数让 obj 指向新对象）。
- 常考题：判断 “Java 的对象传递是引用调用” 是否正确（错误，本质是值传递的引用）。
C#
- ref：引用调用，实参需初始化，如 void f(ref int x) { x=5; }。
- out：强制函数内赋值，用于 “输出参数”，如 void f(out int x) { x=5; }。
Python
- 可变对象（列表、字典）：值调用传递对象引用，可修改内容（如 lst.append(3)），但无法重新赋值（如 lst = [1,2] 不影响实参）。
- 不可变对象（整数、字符串）：值调用，修改无效。

语言分类以及特点

分类	代表语言	核心特点	典型用途
命令式语言	C、Java、C#、C++	强调算法步骤，支持变量和控制流（顺序、分支、循环），分面向过程和面向对象。	C：系统开发、嵌入式；Java/C#：企业级应用、Android 开发；C++：游戏引擎、桌面软件。
函数式语言	Haskell、Lisp、Scala	纯函数、不可变性、惰性求值，强调数学计算逻辑。	Haskell：金融计算；Lisp：早期 AI；Scala：大数据处理（Spark）。
逻辑式语言	Prolog	基于一阶逻辑，声明性编程，自动推理。	专家系统、自然语言处理、数据库查询优化。
脚本语言	Python、JavaScript、PHP	动态类型、语法简洁、解释执行，开发效率高。	Python：数据分析、AI；JavaScript：Web 全栈；PHP：中小型 Web 应用。
科学计算语言	Fortran、MATLAB	高效数值计算，支持矩阵运算和可视化。	Fortran：工程模拟；MATLAB：信号处理、控制系统设计。
现代语言	Go、Swift、Rust	高性能、安全性、简洁语法，支持并发或特定场景优化。	Go：云服务（Docker）；Swift：iOS 开发；Rust：区块链、内存安全服务端。
其他重要语言	SQL	非过程化，面向数据操作，声明式查询。	数据库管理、数据检索与分析。

错误类型分类

错误类型	定义	典型示例	语言示例	软考常考陷阱
语法错误	违反编程语言的语法规则，无法通过编译。	缺少分号、括号不匹配、关键字拼写错误	C、Java、Python 编译阶段报错	注意中文符号（如 “；” 代替 “;”）导致的隐藏错误。
类型错误	操作符与操作数类型不匹配，编译阶段检查。	字符串与整数相加、数组越界	C 的 `int + char`、Java 的 `String s = 123`	注意自动类型转换（如 C 的 `char` 转 `int`）可能掩盖类型错误。
语义错误	语法正确但逻辑含义错误，导致程序行为不符合预期。	条件判断错误、算法逻辑错误	错误的循环终止条件、错误的公式计算	软考常考 “逻辑错误” 与 “运行时错误” 的区分：逻辑错误可能在运行时才暴露。
运行时错误	程序运行期间发生的错误，通常导致程序崩溃或异常。	除零错误、空指针解引用、数组越界	C 的 `NULL指针解引用`、Java 的 `NullPointerException`	注意 Java 的 “受检异常” 与 “非受检异常” 区别（如 `IOException` 需显式处理）。
链接错误	编译通过但链接阶段找不到符号（如未定义的函数或变量）。	函数声明与实现不匹配、库文件缺失	C 的 `undefined reference to 'func'`	软考可能结合编译流程考查链接错误的原因（如函数名大小写不一致）。
逻辑错误	算法设计错误，导致结果不正确但程序不崩溃。	排序算法错误、错误的业务逻辑	冒泡排序中的循环次数错误	逻辑错误是软考重点考查对象，需通过测试用例发现（如错误的闰年判断条件）。

典型错误类型解析与常考细节

语法错误
- 特点：编译阶段直接报错，必须修复才能运行。
- 示例
```
int a = 5; // 正确
int a = 5  // 缺少分号（语法错误）
```
- 软考陷阱：混淆 “语法错误” 与 “语义错误”，例如 if (a = 0) 是语法正确但语义错误（应为 a == 0）。
运行时错误
- 分类
  - 异常：可捕获处理（如 Java 的 try-catch）。
  - 崩溃：不可恢复（如 C 的除零错误直接终止程序）。
- 示例
```
int[] arr = new int[5];
System.out.println(arr[10]); // 数组越界（运行时错误）
```
- 软考常考：Java 的 ArrayIndexOutOfBoundsException 属于运行时错误，而 C 的数组越界可能导致未定义行为。
逻辑错误
- 隐蔽性：程序正常运行但结果错误，需通过测试发现。
- 示例
```
def is_leap(year):
    return year % 4 == 0  # 错误，未处理整百年（软考经典逻辑错误）
```
- 软考重点：算法设计题中常见，如错误的循环条件导致结果偏差。
类型错误
- 静态类型语言（如 C、Java）：编译阶段检查。
- 动态类型语言（如 Python）：运行时检查。
- 示例
```
a = "hello" + 5  # 运行时类型错误（Python）
```
- 软考陷阱：Java 的自动拆箱 / 装箱可能掩盖类型错误（如 Integer i = null; int j = i; 导致 NullPointerException）。

编译、解释系统

编译

编译是将高级程序设计语言编写的源程序转化为目标机器可执行的机器语言程序的过程。

词法分析：编译的第一个阶段，使用有限自动机实现。从左到右扫描源程序字符流，依据词法规则将其识别为一个个单词，如关键字、标识符、常量、运算符等。
语法分析：基于词法分析得到的单词序列，依据语法规则，使用多种方法如 自顶向下（递归下降分析法和预测分析法）和自底向上 等（移进-归约分析法），构建语法树，检查源程序的语法结构是否正确。
语义分析：在语法分析基础上，对语法树进行遍历，依据语义规则检查源程序语义的正确性，如类型检查、变量声明与使用一致性检查等，并进行必要的语义处理，如生成中间代码。
中间代码生成：是编译程序的重要阶段，将源程序转换为一种中间表示形式，方便进行与目标机器无关的优化和生成目标代码，常采用规定的表示形式有 三地址码、四元式、后缀式、语法树 等。
代码优化：对中间代码进行等价变换，依据优化原则和技术，如常量折叠、公共子表达式删除等，提高目标代码的执行效率。
目标代码生成：根据目标机器的指令集和体系结构，将优化后的中间代码转换为目标机器可执行的机器语言代码，涉及寄存器分配、指令选择等工作。

常见的中间代码形式。

编译语言和解释语言

编译语言

简介：编写的源代码通过编译器一次性翻译成目标机器的机器码，生成可执行文件，执行时直接运行可执行文件。
举例：C、C++、Java（Java 有编译过程，生成字节码，在虚拟机上运行，也可看作特殊的编译语言）等。

解释语言

简介：源代码由解释器逐行解释并执行，不生成目标机器码，边解释边执行。

举例：Python、JavaScript、Ruby 等。

对比

对比项	解释型语言	编译型语言	软考常考点
翻译方式	逐行翻译并立即执行	一次性整体翻译为目标代码	翻译方式的差异（逐行 vs 整体）
运行过程	源代码 → 解释器 → 执行	源代码 → 编译器 → 可执行文件 → 执行	运行阶段的步骤（是否生成中间文件）
语法检查	运行时检查（错误即时反馈）	编译时检查（生成错误报告）	错误检测的时机（运行时 vs 编译时）
开发效率	高（修改后立即生效）	低（需重新编译）	开发效率与调试便利性
执行速度	慢（逐行解释）	快（直接执行机器码）	执行效率对比（软考高频考点）
跨平台性	好（只需解释器）	差（需编译不同平台版本）	跨平台能力的优劣
典型语言	Python、PHP、JavaScript、BASIC	C、C++、Java（编译为字节码后由 JVM 解释）	语言分类（如 Java 的特殊性：编译 + 解释）
代码安全性	伪码易被反编译	机器码难逆向	安全性对比（需注意 Java 的字节码也可能被反编译）
中间代码	可能生成中间码（如字节码）但不保存	生成目标代码（如机器码、汇编）并保存	是否生成独立的中间文件

文法分析

1. 文法的定义与分类

文法：形式化描述语言的规则集合，由四元组 G =(V N, V T, P, S) 表示：
- V N：非终结符集（如 S, A, B）。
- V T：终结符集（如 a, b,+）。
- P：产生式规则（如 S → a S b）。
- S：开始符号。
文法类型（乔姆斯基分类）：
- 0 型（无限制文法）：无约束条件，等价于图灵机。
- 1 型（上下文有关文法）：产生式形如 α → β，其中 ∣ α ∣≤∣ β ∣。
- 2 型（上下文无关文法）：产生式形如 A → β，非终结符可替换为任意符号串。
- 3 型（正规文法）：产生式形如 A → a B 或 A → a，对应有限自动机。

2. 推导与归约

推导：从开始符号出发，通过产生式规则生成句子的过程（如 S ⇒ a S b ⇒ aa S bb ⇒ aabb）。
最左（右）推导：每次替换最左（右）非终结符。
归约：推导的逆过程，从句子反向构造语法树。

3. 语法树与短语

语法树：可视化推导过程的树形结构。
短语：某个非终结符可推导出的符号串（如在 S ⇒ a S b ⇒ aa S bb 中，a S 是相对于 S 的短语）。
句柄：最左直接短语，用于自底向上分析（如 LR 分析）。

4. 语法分析方法

自顶向下分析：LL (1)、递归下降分析。
- LL(1)：第一个 L 表示从左到右扫描，第二个 L 表示最左推导，1 表示向前看一个符号。
- 条件：无左递归、无回溯、First 和 Follow 集不相交。
自底向上分析：LR(0)、SLR(1)、LR(1)、LALR(1)。
- LR 分析：L 表示从左到右扫描，R 表示最右推导的逆过程。

软考常考题目解析

1. 文法分类题

题目：判断以下文法类型：S → a S b ∣ ab分析：

产生式形式为 A → β，符合上下文无关文法（2 型）。
无法转换为正规文法（3 型），因存在递归嵌套。答案：上下文无关文法。

2. First 和 Follow 集计算

题目：文法 G =(S, A, a, b, P, S)，其中 P 为：S → a A A → b S ∣ ϵ 求 First (S)、First (A)、Follow (S)、Follow (A)。解答：

First(S)：由 S → a A，First(S) = {a}。
First(A)：由 A → b S ∣ ϵ，First(A) = {b, ε}。
Follow(S)
：
- S 是开始符号，初始 Follow (S) = {#}。
- 由 A → b S，S 后可能有 Follow (A) 中的符号。
- 由 S → a A，A 后可能有 Follow (S) 中的符号，而 A 可推导出 ε，因此 Follow (S) = Follow (S) ∪ Follow (A)。
- 最终 Follow (S) = {#, b}。
Follow(A)
：
- 由 S → a A，A 后可能有 Follow (S) 中的符号（即 {#, b}）。
- 由 A → b S，S 后可能有 Follow (A) 中的符号，但 S 的 Follow 集包含 {#, b}，因此 Follow (A) = {#, b}。

3. LL (1) 文法判定

题目：判断文法 S → a S b ∣ ab 是否为 LL (1)。分析：

First(S)：{a}（两个产生式的 First 集相同，无冲突）。
Follow(S)：{b, #}（由推导 S ⇒ a S b，S 后可能有 b 或结束符 #）。
条件
：所有产生式的 First 集不相交，且 First 集与 Follow 集无交集。
- 此处两个产生式的 First 集均为 {a}，无冲突，且 First (S) 与 Follow (S) 无交集。结论：是 LL (1) 文法。

4. LR 分析表构造

题目：对文法 S → a A, A → b S ∣ ϵ，构造 LR (0) 分析表。步骤：

拓广文法：添加 S′→ S。
构造项目集
：
- I 0: S′→⋅ S, S →⋅ a A
- I 1: S′→ S ⋅（接受状态）
- I 2: S → a ⋅ A, A →⋅ b S ∣⋅ ϵ
- I 3: A → b ⋅ S, S →⋅ a A
- I 4: A → ϵ ⋅（归约状态）
转移函数：根据符号跳转（如 I 0 输入 a 转移到 I 2）。
分析表
：
- I 0：action [a] = s2（移进）。
- I 2：action [b] = s3（移进），action [ε] = r2（归约）。
- I 4：goto [A] = I_1（归约后转到 S 的状态）。答案：分析表需完整列出所有状态和符号的 action/goto 项。

有限自动机

核心知识点

定义与五元组 有限自动机是一个五元组：M = (Q, Σ, δ, q₀, F)，其中：
- Q：有限状态集；
- Σ：输入字母表；
- δ：转移函数（DFA 为单值映射，NFA 为多值映射或含 ε 转移）；
- q₀：初始状态；
- F：终止状态集。
类型
- 确定有限自动机（DFA）：每个状态对每个输入有唯一转移。
- 非确定有限自动机（NFA）：允许 ε 转移和多值转移，可通过 ε- 闭包简化为 DFA。
语言识别 输入字符串被接受的条件是：从初始状态出发，按转移规则遍历字符后到达终止状态。
正则表达式与自动机的转换
- 正则式 →NFA：通过 Thompson 算法构造。
- NFA→DFA：通过子集构造法（如 ε- 闭包计算）。
- DFA 最小化：通过等价类划分（如 Hopcroft 算法）。

软考常考点

DFA 与 NFA 的区别
- 重点：DFA 转移唯一，NFA 允许多转移和 ε 动作。
- 题型示例：判断给定自动机是 DFA 还是 NFA。
状态转移图分析
- 常考：根据状态转移图，选择自动机接受的字符串（如以特定模式结尾）。
- 解题技巧：模拟路径，关注终止状态条件。
正则式与自动机的转换
- 软考高频考点：将正则式转换为 NFA，或根据自动机图写出对应的正则式。
ε- 闭包与子集构造法
- 常考步骤：计算 NFA 的 ε- 闭包，将其转换为等价 DFA。
DFA 最小化
- 步骤：划分状态等价类，合并不可区分状态。

操作系统

进程管理

进程与线程基础

1. 进程定义

进程是程序的一次执行过程，是操作系统资源分配的基本单位。
包含：程序段、数据段、进程控制块（PCB，记录进程状态和资源信息）。

2. 进程特征

动态性：进程有生命周期（创建、运行、终止）。
并发性：多个进程可同时执行（宏观并行，微观交替）。
独立性：进程独立获得资源和调度。
异步性：进程按不可预知的速度推进。

3. 线程（轻量级进程）

线程是CPU 调度的基本单位，共享进程资源（如内存、文件句柄）。
分类：
- 用户线程：由用户空间库管理，操作系统不可见（优点：切换快，缺点：一个线程阻塞可能导致进程阻塞）。
- 内核线程：由操作系统内核管理，线程调度由内核完成（优点：支持多处理器并发，缺点：切换开销略高）。

进程 vs 线程：

对比项	进程	线程
资源分配单位	是	否（共享进程资源）
调度单位	是（旧系统）	是（现代系统）
上下文切换开销	高（需切换内存空间等资源）	低（仅切换寄存器、栈等）

进程状态与转换

1. 三态模型（基础状态）

状态	说明	转换条件
运行态	进程正在 CPU 上执行（单 CPU 下同一时刻仅一个进程处于此状态）。	从就绪态被调度选中。
就绪态	进程具备执行条件，等待 CPU 调度。	进程创建后；运行态进程因时间片用完或被更高优先级进程抢占。
阻塞态	进程因等待某事件（如 I/O 完成、资源获取）暂时无法执行。	等待的事件发生（如 I/O 完成），重新回到就绪态。

2. 五态模型（扩展状态）

新建态：进程正在被创建，尚未加入就绪队列。
终止态：进程执行结束或异常终止，等待操作系统回收资源。

3. 状态转换核心逻辑

阻塞 → 就绪：等待的事件完成（如 I/O 操作结束）。
运行 → 阻塞：进程主动请求等待事件（如调用 I/O 函数）。
运行 → 就绪：时间片耗尽（抢占式调度）或主动让出 CPU（非抢占式）。

进程调度算法

1. 调度目标

公平性：各进程获得合理的 CPU 时间。
效率：减少上下文切换开销，提高 CPU 利用率。
响应时间：交互式任务需快速响应（如时间片轮转算法）。

2. 常见算法分类

算法类型	算法名称	核心思想	优点	缺点	适用场景
先来先服务（FCFS）	非抢占式	按进程到达顺序调度，先就绪先执行。	实现简单，公平。	长任务可能导致短任务等待（“饥饿”）。	批处理系统
短作业优先（SJF）	非抢占式 / 抢占式（短剩余时间优先）	优先调度预计运行时间最短的进程。	平均等待时间最短。	需预知作业运行时间（实际难实现）。	批处理系统
时间片轮转（RR）	抢占式	将 CPU 时间划分为固定时间片，进程轮流执行，时间片用完则切换。	响应时间均衡，适合交互式任务。	时间片过短会增加切换开销。	分时系统（如 Linux）
优先级调度	抢占式 / 非抢占式	为进程分配优先级，优先调度高优先级进程（可解决 “饥饿”，如动态调整优先级）。	灵活控制任务优先级。	低优先级进程可能长期等待（需避免饥饿）。	实时系统、多任务系统
高响应比优先（HRRN）	非抢占式	响应比 =（等待时间 + 运行时间）/ 运行时间，优先选择响应比高的进程。	兼顾公平性与效率。	每次调度需计算响应比，开销略高。	批处理系统

进程同步与互斥

1. 核心问题

临界资源：一次仅允许一个进程访问的资源（如打印机、共享变量）。
临界区：访问临界资源的代码段。
目标：确保多个进程互斥访问临界区，避免数据不一致（如银行账户余额同时读写）。

2. 解决方法

信号量机制（PV 操作）：
- 信号量 S：一个整数变量，代表可用资源数（S≥0 时表示可用资源数，S<0 时绝对值表示等待队列中的进程数）。
- P 操作（申请资源）：S 减 1，若 S<0 则进程阻塞，加入等待队列。
- V 操作（释放资源）：S 加 1，若 S≤0 则唤醒等待队列中的一个进程。
- 例子：互斥访问临界区（初始 S=1，P/V 操作包裹临界区）。
经典问题：
- 生产者 - 消费者问题：通过信号量实现缓冲区的互斥与同步（空缓冲区数、满缓冲区数、互斥信号量）。
- 读者 - 写者问题：允许多个读者同时读，但写者需互斥（区分 “读者优先” 和 “写者优先” 策略）。

3. 进程通信（IPC）方式

共享内存：多个进程直接访问同一块内存区域（最快，但需手动同步）。
消息传递：通过消息队列或管道（如无名管道、命名管道）交换数据（安全，无需手动同步）。
信号量与信号：信号量用于同步，信号（如 Ctrl+C）用于通知进程事件（如终止、暂停）。

死锁问题

1. 死锁定义

多个进程因竞争资源或相互等待对方释放资源，导致所有进程无法继续执行的状态。

2. 死锁必要条件（四缺一则无死锁）

互斥条件：资源一次只能被一个进程占用。
请求与保持条件：进程已持有资源，同时请求其他资源（且不释放已持有资源）。
不可剥夺条件：资源只能被进程主动释放，不能被强制剥夺。
循环等待条件：进程间形成资源等待环（A 等 B 的资源，B 等 A 的资源）。

3. 死锁处理策略

策略	核心思想	典型方法	优缺点
死锁预防	破坏死锁必要条件（至少破坏一个）。	如禁止 “请求与保持”（进程启动时申请所有资源）、资源按序分配（破坏循环等待）。	简单，但可能浪费资源（如提前申请未使用的资源）。
死锁避免	在资源分配前预判是否可能导致死锁，避免进入不安全状态。	银行家算法：计算进程的最大需求、已分配资源、剩余资源，判断分配是否安全（存在安全序列则分配）。	效率较高，但需知道进程的最大资源需求（实际难满足）。
死锁检测与解除	定期检测是否存在死锁，若存在则通过剥夺资源或终止进程解除。	构建资源分配图，检测环是否存在；解除时优先终止优先级低或消耗资源少的进程。	允许死锁发生，适用于死锁不频繁的场景，但解除代价高（可能丢失进程数据）。

4. 银行家算法示例

数据结构：最大需求矩阵 Max、已分配矩阵 Allocation、需求矩阵 Need（Need=Max-Allocation）、可用资源向量 Available。
安全检查：尝试为每个进程分配其所需资源，若能找到一个安全序列（所有进程均可执行完毕），则当前状态安全，否则不安全（拒绝分配）。

文件管理

文件系统的作用

实现按名存取：用户通过文件名访问文件，无需关心物理存储位置。
管理磁盘空间：分配 / 回收空闲块，记录文件的物理位置（如 FAT 表、inode）。
提供安全与共享机制：权限控制（如 UNIX 的 rwx）、文件共享（硬链接 / 软链接）。
支持数据持久化：将数据长期存储在磁盘等非易失性介质中。

文件的逻辑结构

1. 记录式文件

定长记录文件：所有记录长度相同，支持随机访问（如数据库表）。
变长记录文件：记录长度可变，需索引表辅助定位（如日志文件）。

2. 流式文件

无结构的字节流，按顺序访问（如文本文件、视频文件）。
优点：简单灵活，适用于连续读写场景。

类型	特点	典型场景
定长记录文件	记录长度固定，随机访问高效	数据库、学生信息表
变长记录文件	记录长度可变，需索引表定位	日志、邮件系统
流式文件	无结构字节流，顺序访问为主	文本、多媒体文件

文件的物理结构

1. 连续分配

原理：文件数据存放在连续的磁盘块中。
优点：顺序访问速度快，支持随机访问。
缺点：易产生外部碎片，文件扩展困难。

2. 链式分配

隐式链接：每个块包含指向下一块的指针，仅支持顺序访问（如 FAT32 早期版本）。
显式链接：指针集中存储在 FAT 表中，支持随机访问（如 FAT32）。
优点：无外部碎片，动态扩展方便。
缺点：随机访问需遍历指针，FAT 表占用内存。

3. 索引分配

原理：文件数据块地址存放在索引块中，支持随机访问。
多层索引：通过多级索引块管理大文件（如 EXT4 的 extent 结构）。
混合索引：小文件直接存储地址，大文件使用索引（如 UNIX 的 inode）。
优点：高效随机访问，支持大文件。
缺点：索引块占用额外空间。

类型	访问方式	碎片问题	扩展性	典型系统
连续分配	随机 / 顺序	外部碎片	差	早期 DOS
链式分配	顺序为主	无	好	FAT32、早期 Linux
索引分配	随机 / 顺序	无	好	NTFS、EXT4

目录结构与路径

1. 目录结构类型

单级目录：所有文件存放在同一目录，不支持重名（仅适用于简单系统）。
树形目录：分层结构（根目录 → 子目录 → 文件），支持重名文件（如 Linux、Windows）。
非循环图目录：允许文件或目录被多个父目录引用（如硬链接 / 软链接）。

2. 文件路径

绝对路径：从根目录开始（如/home/user/file.txt）。
相对路径：从当前目录开始（如./doc/report.pdf）。

3. 硬链接与软链接

类型	原理	特点
硬链接	多个文件名指向同一 inode，共享数据块	不可跨分区，删除原文件不影响链接，链接计数需减至 0 才真正删除。
软链接	类似快捷方式，存储原文件路径	可跨分区，原文件删除后链接失效，访问需解析路径（可能增加 I/O 开销）。

文件系统类型与核心机制

1. 常见文件系统

文件系统	特点	适用场景
FAT32	简单、兼容性强，单个文件 ≤4GB	U 盘、嵌入式设备
NTFS	支持大文件、加密、压缩、权限控制	Windows 系统盘
EXT4	高性能、日志功能、支持 extent 结构	Linux 系统盘
exFAT	跨平台、支持大文件（>4GB）	移动硬盘、闪存设备

2. 索引节点（inode）

作用：存储文件元数据（大小、权限、数据块地址等），不包含文件名。
特点：每个文件唯一对应一个 inode，文件名存放在目录项中。

3. 空闲块管理

位示图：用二进制位表示磁盘块是否空闲（如 1 表示占用，0 表示空闲）。
成组链接法：将空闲块分组管理，兼顾效率与可靠性（如 Linux 的 ext 系列）。

文件权限与安全

1. UNIX 权限模型（rwx）

权限类型：读（r）、写（w）、执行（x）。
用户分类：所有者（u）、所属组（g）、其他用户（o）。
示例：rwxr-xr-x 表示所有者可读写执行，组和其他用户可读执行。

2. 权限设置命令

chmod：修改文件权限（如chmod 755 file.txt）。
umask：设置新建文件 / 目录的默认权限（如默认umask 022，目录权限 755，文件权限 644）。

3. 目录权限

执行权限（x）：访问目录下的文件或子目录的前提。
写权限（w）：允许在目录中创建、删除文件（需同时具备 x 权限）。

磁盘调度与访问优化

1. 磁盘访问时间

寻道时间：磁头移动到目标磁道的时间（占主导）。
旋转延迟：目标扇区旋转到磁头下方的时间。
传输时间：数据读写时间。

2. 调度算法

算法	策略	特点
FCFS	按请求顺序处理	公平但延迟高
SSTF	优先处理最近磁道请求	减少寻道时间，可能饥饿
SCAN（电梯调度）	磁头单向移动，依次处理请求	均衡性能，避免饥饿
CSCAN	磁头单向移动，到达尽头后跳转至起点继续	消除 SCAN 的反向延迟

文件操作与系统调用

1. 核心操作流程

打开文件（open）：
1. 检查权限，读取目录项获取 inode。
2. 将 inode 信息存入内存打开文件表，返回文件描述符。
读取文件（read）：
1. 根据文件描述符找到 inode，定位数据块地址。
2. 从磁盘读取数据到内存缓冲区。
写入文件（write）：
1. 分配空闲块，更新 inode 数据块地址。
2. 将内存数据写入磁盘。
关闭文件（close）：
1. 同步缓存数据到磁盘。
2. 释放内存中的打开文件表项。

2. 系统调用示例

调用	功能	参数说明
`open()`	创建或打开文件	路径、打开模式（如只读、读写）
`read()`	从文件读取数据	文件描述符、缓冲区、读取长度
`write()`	向文件写入数据	文件描述符、缓冲区、写入长度
`lseek()`	设置文件偏移量	文件描述符、偏移量、起始位置（如开头、当前位置）

存储管理

存储管理基础

1. 内存管理目标

高效利用内存：减少碎片（内部 / 外部），提升资源利用率。
进程隔离：确保进程只能访问自己的内存空间（如基址寄存器 + 界限寄存器保护）。
虚拟内存扩展：通过硬盘模拟更大内存空间，支持大程序运行。
快速访问：通过 TLB（快表）加速地址转换。

2. 地址重定位

静态重定位：程序装入时一次性完成逻辑地址到物理地址的转换（无需硬件支持）。
动态重定位：程序运行时由 MMU（内存管理单元）动态转换地址（需基址寄存器支持）。

3. 内存保护机制

基址寄存器 + 界限寄存器：
- 基址寄存器存储进程起始物理地址，界限寄存器存储最大逻辑地址。
- 访问地址需满足：基址 ≤ 物理地址 < 基址 + 界限，否则触发越界中断。

内存分配方式

1. 连续分配

单一连续分配：内存分为系统区和用户区，仅支持单进程（如早期 DOS）。
- 优点：实现简单，无外部碎片。
- 缺点：内存利用率低，多进程支持差。
固定分区分配：将内存划分为大小固定的分区，每个分区装入一个进程。
- 优点：支持多进程，无外部碎片。
- 缺点：内部碎片严重（分区大小与进程不匹配）。
动态分区分配：根据进程需求动态划分内存（如首次适应、最佳适应算法）。
- 优点：按需分配，减少内部碎片。
- 缺点：易产生外部碎片，需合并空闲块。

算法	核心思想	优缺点
首次适应	从低地址开始查找第一个足够大的空闲块	简单，保留高地址大空闲块；低地址碎片多，查找时间长。
最佳适应	选择与需求最接近的空闲块	减少大材小用；产生大量难以利用的微小碎片。
最坏适应	选择最大的空闲块分配	减少碎片，但大内存块快速被分割。

虚拟内存技术

1. 分页存储管理

原理：将程序与内存划分为固定大小的页（如 4KB），页表记录页号与物理页框的映射关系。
逻辑地址：页号 + 页内偏移（如 32 位地址：10 位页号 + 22 位页内偏移）。
物理地址：页框号 + 页内偏移。
优点：无外部碎片，支持离散存储。
缺点：页表占用内存（多级页表可解决），可能产生抖动。

2. 分段存储管理

原理：按程序逻辑分段（如代码段、数据段），段表记录段基址与段长。
逻辑地址：段号 + 段内偏移。
优点：支持逻辑模块化，方便共享与保护。
缺点：易产生外部碎片，内存利用率低。

3. 段页式存储管理

原理：先分段，再分页（如 Linux 内核）。
逻辑地址：段号 + 段内页号 + 页内偏移。
优点：结合分段与分页的优势，空间浪费小。
缺点：地址转换需三次内存访问（段表 → 页表 → 物理地址），开销较大。

类型	地址结构	碎片问题	共享支持	典型场景
分页	页号 + 页内偏移	无外部碎片	差	通用操作系统（如 Windows）
分段	段号 + 段内偏移	外部碎片	好	模块化程序设计
段页式	段号 + 段内页号 + 页内偏移	无外部碎片	好	大型系统（如 UNIX）

页面置换算法

1. 算法目标

减少缺页中断次数，提升内存访问效率。
依据程序局部性原理（时间局部性、空间局部性）预测未来访问模式。

2. 常见算法对比

算法	核心思想	优点	缺点	缺页率
FIFO	淘汰最早进入内存的页面	实现简单	可能产生 “抖动”（Belady 现象）	高
LRU	淘汰最近最久未使用的页面	缺页率低，接近 OPT	需维护访问时间戳，硬件开销大	低
OPT	淘汰未来最长时间不访问的页面（理论最优）	缺页率最低	无法实现（需预知未来访问序列）	最低
Clock	维护环形链表，淘汰未被访问的页面（二次机会算法优化）	开销低，接近 LRU	性能略逊于 LRU	中

3. 示例：页面访问序列 1→2→3→4→1→2→5→1→2→3→4→5（内存容量 3 页）

FIFO：缺页 9 次（1→2→3→4→1→2→5→3→4→5）。
LRU：缺页 7 次（1→2→3→4→1→2→5→1→2→3→4→5）。

内存优化与扩展

1. 多级页表

原理：将页表分页存储（如二级页表），仅加载当前需要的页表项到内存。
优点：减少页表占用内存（如 32 位系统单级页表需 4MB，二级页表仅需 KB 级）。
缺点：地址转换需多次内存访问（通过 TLB 缓解）。

2. 快表（TLB）

作用：缓存最近使用的页表项，加速地址转换（命中率高达 90% 以上）。
机制：CPU 先查 TLB，未命中则查内存页表，并将结果存入 TLB。

3. 内存抖动（颠簸）

定义：频繁的页面换入换出导致系统性能急剧下降。
原因：内存分配不足或置换算法不当（如 FIFO 未考虑局部性）。
解决：增加物理内存、优化置换算法（如使用 LRU）、调整进程优先级。

内存分配策略与安全

1. 空闲块管理

位示图：用二进制位表示磁盘块是否空闲（如 1 表示占用，0 表示空闲）。
成组链接法：将空闲块分组管理，兼顾效率与可靠性（如 Linux 的 ext 系列）。

2. 内存安全机制

访问权限控制：通过页表项或段表项标记读写、执行权限（如 X86 的 PTE 标志位）。
地址空间随机化：随机化进程内存布局，防止缓冲区溢出攻击。

设备管理

设备管理基础

1. 设备分类

分类标准	类型	特点	示例
传输速率	低速设备	每秒传输字节数 ≤1KB（需 CPU 频繁干预）	键盘、鼠标
	中速设备	每秒传输 KB~MB 级（中断驱动为主）	打印机、扫描仪
	高速设备	每秒传输 MB 级以上（DMA / 通道控制）	磁盘、网卡
功能	存储设备	存储数据（非易失性）	硬盘、U 盘
	输入 / 输出设备	实现人机交互或数据传输	显示器、声卡
共享属性	独占设备	同一时刻仅允许一个进程使用（需互斥）	打印机、磁带机
	共享设备	多个进程可交替使用（分时复用）	磁盘、网卡
	虚拟设备	通过 SPOOLing 技术将独占设备虚拟为共享设备（如虚拟打印机）	虚拟串口、虚拟光驱

2. 设备管理目标

高效利用：减少 CPU 等待时间（如 DMA 技术），提升 I/O 吞吐量。
透明访问：实现设备独立性（用户通过逻辑设备名访问，屏蔽物理差异）。
安全可靠：控制设备访问权限，处理设备故障（如错误重试、设备切换）。

I/O 控制方式

1. 程序查询方式

原理：CPU 不断轮询设备状态寄存器，直到设备准备好数据。
流程：
1. 发送 I/O 请求，CPU 进入循环查询状态。
2. 设备完成操作后设置状态为 “就绪”，CPU 读取数据。
优点：实现简单，无需硬件支持。
缺点：CPU 利用率极低（忙等），仅适用于低速设备。

2. 中断驱动方式

原理：设备完成操作后主动向 CPU 发送中断信号，CPU 暂停当前任务处理 I/O。
流程：
1. 发送 I/O 请求，CPU 继续执行其他任务。
2. 设备完成后触发中断，CPU 执行中断处理程序（如读取数据）。
优点：CPU 无需忙等，利用率提升。
缺点：一次中断处理一次数据（如单个字节），高频中断增加 CPU 开销（适用于中速设备）。

3. DMA（直接内存访问）方式

原理：通过 DMA 控制器（DMAC）直接控制内存与设备的数据传输，无需 CPU 干预。
流程
：
1. CPU 发送 DMA 请求，配置传输参数（地址、长度）。
2. DMAC 负责数据读写，完成后触发中断通知 CPU。
优点：支持批量数据传输（如磁盘块），大幅减少 CPU 干预。
缺点：需专用硬件（DMAC），适用于高速设备（如硬盘、网卡）。

4. 通道方式（高级 DMA）

原理：独立的通道处理器（CHP）控制多台设备的 I/O，支持复杂 I/O 逻辑（如协议转换）。
优点：CPU 仅需发送通道程序指令，通道自行管理多设备并发。
适用场景：大型主机系统（如 IBM 大型机），处理高速、多设备并发 I/O。

控制方式	CPU 干预程度	数据传输单位	中断频率	典型设备
程序查询	高（忙等）	单个字节 / 字符	无	键盘、传感器
中断驱动	中（响应中断）	单个字节 / 字符	高	打印机、扫描仪
DMA	低（初始化后释放）	数据块（如扇区）	低（一次传输一整块）	磁盘、U 盘
通道	极低（仅发指令）	多数据块 / 流	极低	高速外设集群

设备驱动程序与中断处理

1. 设备驱动程序（Driver）

作用：屏蔽硬件细节，为操作系统和应用程序提供统一接口（如read()/write()）。
功能：
- 初始化设备（如显卡自检）。
- 处理设备打开 / 关闭请求（如挂载 U 盘）。
- 数据传输（将用户数据转换为设备特定格式）。
- 错误处理（如磁盘扇区坏块重试）。

2. 中断处理流程

中断响应：CPU 检测到中断信号，暂停当前程序，保存现场（寄存器值、程序计数器）。
中断识别：通过中断向量表（IVT）找到对应中断处理程序（如键盘中断号 0x09）。
中断处理：执行驱动程序的中断服务例程（ISR），如读取设备数据到缓冲区。
中断返回：恢复现场，继续执行被中断的程序。

3. 中断类型

硬件中断：由设备触发（如 I/O 完成、时钟中断），分为可屏蔽中断（如打印机中断）和不可屏蔽中断（如电源故障）。
软件中断：由程序指令触发（如系统调用int 80h），用于请求操作系统服务。

四、磁盘调度算法（核心考点）

1. 磁盘结构与访问时间

寻道时间：磁头移动到目标磁道的时间（占总时间 60%~80%）。
旋转延迟：目标扇区旋转到磁头下方的时间（平均为磁盘转速的 1/2，如 5400 转 / 分硬盘平均旋转延迟 ≈5.56ms）。
传输时间：数据读写时间（与转速和扇区大小相关）。

2. 调度算法对比

算法	核心策略	优点	缺点	平均寻道时间	是否饥饿
FCFS（先来先服务）	按请求顺序处理磁道访问（如 100→10→22→…）	公平，实现简单	寻道时间波动大（如从 100 到 10 再到 22）	高	否
SSTF（最短寻道时间优先）	优先处理与当前磁头位置最近的磁道（如当前 100，选 102 而非 10）	大幅减少寻道时间	可能导致某些磁道长期无法访问（饥饿）	中	是（可能）
SCAN（电梯调度）	磁头单向移动（如从内到外），处理所有请求后反向，重复（类似电梯运行）	均衡内外磁道访问，避免饥饿	边缘磁道访问频率低（如最内 / 外磁道）	低	否
CSCAN（循环扫描）	磁头单向移动，到达终点后立即跳转至起点，不处理反向请求（仅正向扫描）	确保各磁道访问频率均衡	寻道时间略高于 SCAN	低	否
N-Step SCAN	将请求队列分为多个子队列，每个子队列执行 SCAN（避免 SSTF 的 “粘着” 现象）	减少磁头频繁切换方向	实现稍复杂	中	否

示例：

磁头初始位置 100，请求序列：10, 22, 20, 2, 40, 6, 38
FCFS 寻道顺序：100→10→22→20→2→40→6→38，总寻道长度 = (90)+(12)+(2)+(18)+(38)+(34)+(32) = 226
SSTF 寻道顺序：100→102（假设附近有请求）→ 实际应为最近的 102？更正：示例中最近为 22（100→22→20→10→6→2→38→40），总寻道长度 = 78+2+10+4+4+36+2 = 136

五、缓冲区管理与 SPOOLing 技术

1. 缓冲区类型

单缓冲：CPU 与设备共享一个缓冲区（如打印机缓冲区），轮流使用，效率低。
双缓冲：两个缓冲区交替使用（如 A 区写入时 B 区读取），提升 CPU 与设备并行度。
循环缓冲：多个缓冲区组成环形队列，适用于连续数据传输（如视频流）。
缓冲池：共享多个缓冲区，动态分配给不同设备（如 Linux 的页缓存），提高利用率。

2. SPOOLing（假脱机技术）

作用：将独占设备（如打印机）虚拟为共享设备，实现多进程并发使用。
核心原理：
1. 输入井 / 输出井：用磁盘空间模拟设备缓冲区（如打印队列）。
2. 输入进程 / 输出进程：分别负责将数据从输入设备写入输入井，或将输出井数据发送到输出设备。
优点：
- 减少进程等待时间（数据先存入磁盘，再由 SPOOLing 进程处理）。
- 实现设备无关性（用户程序只访问逻辑设备名）。

六、设备分配与独立性

1. 设备分配策略

静态分配：进程启动时一次性分配所需所有设备，运行结束后释放（适用于独占设备，如磁带机）。
- 优点：无死锁风险。
- 缺点：设备利用率低（进程可能长期占用设备但不使用）。
动态分配：进程需要时申请设备，使用完毕后立即释放（适用于共享设备，如磁盘）。
- 优点：利用率高。
- 缺点：需处理竞争条件（如死锁，需结合银行家算法）。

2. 设备独立性（逻辑设备 vs 物理设备）

逻辑设备：用户程序使用的抽象设备名（如 “打印机 01”）。
物理设备：实际硬件设备（如 “HP LaserJet P1108”）。
映射过程：操作系统通过设备驱动表将逻辑设备名映射到物理设备的驱动程序入口。
优点：
- 用户无需关心硬件细节（如更换打印机无需修改程序）。
- 方便设备热插拔（如 U 盘插入后自动映射为逻辑设备）。

作业管理

作业管理基础

1. 作业定义

作业：用户提交给操作系统执行的一个独立任务，包含 程序、数据、作业说明书（描述运行条件，如资源需求、优先级）。
组成部分：
- 作业控制块（JCB）：记录作业信息（作业名、状态、资源需求、调度参数等），是作业调度的依据。
- 程序段：执行具体功能的代码（如 C 语言编译程序）。
- 数据段：程序运行所需的输入数据或输出结果。

2. 作业与进程的区别

对比项	作业	进程
视角	用户角度（任务整体）	操作系统角度（程序执行实例）
生命周期	从提交到完成（包含等待、执行阶段）	从创建到终止（动态执行过程）
包含关系	一个作业可对应多个进程（如编译作业 → 编译进程 + 链接进程）	进程是作业的执行单元

作业状态与处理流程

1. 作业四状态模型

状态	说明	转换条件
提交态	作业通过输入设备（如键盘、网络）提交给系统，等待进入后备队列。	作业提交成功，尚未被调度程序处理。
后备态	作业已存入外存（如磁盘）的作业队列，等待调度到内存执行（又称 “收容态”）。	调度程序将作业从外存读入内存，分配资源，创建进程。
执行态	作业被调度到内存，进程正在 CPU 上执行（可能交替运行 / 阻塞）。	作业获得 CPU 资源，进程处于运行态或就绪态。
完成态	作业执行结束，系统回收资源，等待输出结果或用户查看。	作业的最后一个进程终止，结果写入外存，JCB 被删除。

2. 批处理系统作业处理流程

提交：用户通过 JCL（作业控制语言）或图形界面提交作业（如submit job.prg）。
调度：作业调度程序按算法选择后备作业，分配内存和外设（如打印机、磁盘空间）。
执行：作业转换为进程集合，进程调度程序负责 CPU 分配（如时间片轮转）。
终止：作业执行完毕，输出结果（如打印报表），释放所有资源。

作业调度算法（核心考点）

1. 调度目标

公平性：各作业获得合理的资源分配（如避免短作业长期等待）。
效率：提高系统吞吐量（单位时间完成的作业数），减少作业平均等待时间。
响应时间：交互式作业需快速响应（但批处理系统更关注吞吐量）。

2. 常见算法对比

算法	核心思想	优点	缺点	关键公式 / 指标
FCFS（先来先服务）	按作业提交顺序调度，先进入后备队列的先执行。	实现简单，公平性好。	长作业导致短作业等待（如 “饥饿”）。	平均周转时间 = 总等待时间 / 作业数
SJF（短作业优先）	优先调度预计运行时间最短的作业（可抢占 / 非抢占，批处理常用非抢占）。	平均周转时间最小。	需预知作业运行时间（实际难实现）。	带权周转时间 = 周转时间 / 运行时间
HRRN（高响应比优先）	响应比 =（等待时间 + 运行时间）/ 运行时间，优先选择响应比高的作业。	兼顾公平与效率，避免饥饿。	每次调度需计算响应比，开销略高。	响应比 = (等待时间 + 运行时间) / 运行时间
优先级调度	按作业优先级（用户指定或系统动态计算）调度，高优先级先执行。	灵活控制任务优先级（如系统作业优先）。	低优先级作业可能长期等待（需动态调整优先级）。	优先级可基于资源需求、提交时间等因素

3. 示例计算（3 个作业）

作业	提交时间	运行时间	FCFS 周转时间	SJF 周转时间	HRRN 响应比（调度时）
A	0	10	10	10	(0+10)/10 = 1（首次调度）
B	1	1	10+1-1=10（等待 9 单位）	10+1=11（A 执行完才开始）	(9+1)/1=10（调度时等待 9 单位）
C	2	2	10+1+2-2=11	10+1+2=13	(8+2)/2=5（调度时等待 8 单位，B 执行完后）

FCFS 平均周转时间：(10+10+11)/3 = 10.33
SJF 平均周转时间：(10+11+13)/3 = 11.33（注：此处示例 SJF 应为非抢占，若抢占则结果不同）
HRRN 选择顺序：A（响应比 1）→ B（响应比 10）→ C（响应比 5，B 执行完后 C 的等待时间为 8）

作业控制与用户接口

1. 作业控制方式

脱机控制
：通过 作业控制语言（JCL） 提前编写作业执行步骤（如 IBM JCL、UNIX shell 脚本），适用于批处理系统。
- 示例：//COMPILE JOB CLASS=A, USER=ADMIN（定义编译作业）。
联机控制
：通过交互式命令实时控制作业（如 Windows 命令提示符、Linux 终端）。
- 常用命令：start（启动作业）、pause（暂停）、kill（终止）。

2. 用户接口类型

类型	特点	示例
CLI（命令行接口）	文本交互，需记忆命令语法（如`dir`查看文件、`rm`删除文件）。	DOS 命令行、Linux Shell
GUI（图形用户界面）	可视化操作，通过鼠标点击菜单、图标完成任务（如打开文件、创建文件夹）。	Windows Explorer、macOS Finder
作业控制语言（JCL）	批处理专用，定义作业执行流程和资源需求（如分配内存、指定输入文件）。	IBM OS/360 JCL、批处理脚本

3. 脱机输入输出（SPOOLing 技术前身）

原理：通过外围计算机预先将作业输入到磁盘（输入井），执行时直接从磁盘读取，输出结果暂存磁盘（输出井）后统一打印。
优点：减少 CPU 等待输入输出时间，提升批处理效率（早期大型机常用）。

五、作业调度与进程调度的关系

调度层次	作用	调度时机	调度算法
作业调度	从后备队列选择作业进入内存，分配资源（如内存空间、外设）。	作业提交后或执行完毕时	FCFS、SJF、HRRN 等
进程调度	从就绪队列选择进程占用 CPU，控制 CPU 时间分配。	时间片用完或进程阻塞时	时间片轮转、优先级调度等

核心关联：作业调度是高级调度，决定哪些作业进入内存；进程调度是低级调度，决定内存中的进程如何使用 CPU。
资源分配：作业调度分配内存和外设等资源，进程调度不分配资源（仅分配 CPU 时间）。

软件工程基础知识

软件工程概述

软件工程基本要素：方法，工具，过程

软件生存周期

可行性分析与项目开发计划

这个阶段主要确定软件的开发目标及其可行性参加人员有用户，项目负责人和系统分析师该阶段产生的主要文档有可行性分析报告和项目开发计划，从而确定系统的逻辑模型

需求分析

这个阶段确定软件的系统的功能，性能，数据和界面等要求参加人员有用户，项目负责人和系统分析师。该阶段产生的主要文档软件需求说明书

概要设计

在概要设计阶段，开发人员要把确定的各项功能需求转换需要的体系结构。概要设计就是设计软件的结构概要设计概要的参加人员有系统分析师和软件设计师该阶段主要产生文档有概要设计说明书

详细设计

详细设计阶段的主要任务是对每个模块完成的功能进行具体描述，要把功能描述转变为精确的，结构化的过程描述。详细设计阶段的参加人员有软件设计师和程序员。该阶段主要产生文档有详细设计文档。

编码

编码阶段就是把每个模块的控制结构转换成计算机课接受的程序代码。即写成某种特定程序设计语言表示的源程序清单

测试

测试是保证软件质量的重要手段，其主要方式是在设计测试用例的基础上检查软件的各个组成部分。测试阶段的参加人员通常是另一部门的软件设计师或系统分析师。该阶段主要产生文档有软件测试计划，测试用例和软件测试报告。

软件工具与开发环境

有效的项目管理集中在 4P 上：人员，产品，过程，项目。

软件项目估算方法：成本估算方法

自顶向下估算：又称类比估算法，先确定一个总金额，再向下分摊到每一个功能点。
自底向上估算：从底层功能点开始估算成本，然后向上累加。
差别估算法：与以前的项目相比，找出不同点重新估算，相同点则直接估算。
专家估算：聘请专家，凭借其经验对项目整体费用进行估算。

COCOMO 模型：常见的软件规模估算方法。常用代码行分析方法作为一种度量估计单位，以代码行数估算每个程序员工作量，再累加得到软件成本。

模型按详细程度分为三级：
- 基本 COCOMO 模型：是一个静态单变量模型，它用一个以估算出来的原代码行数为自变量的经验函数计算软件开发工作量。
- 中间 COCOMO 模型：在基本 COCOMO 模型的基础上，再用涉及产品、硬件、人员、项目等方面影响因素调整工作量的估算。
- 详细 COCOMO 模型：包括中间 COCOMO 模型所有特性，但更进一步考虑了软件工程的每一个步骤的影响。

COCOMO II 模型：COCOMO 模型的升级，也是以软件规模作为成本的主要因素，考虑多个成本驱动因子。该方法包括三个阶段性模型，即应用组装模型，早期设计阶段模型，体系结构阶段模型。

Putnam 估算模型：一种动态多变量模型，假设在软件开发的整个生存周期中工作量有特定的分布。

进度管理

基本原则：划分，相互依赖，时间分配，工作量确认，确认责任，明确输出结果，确定里程碑。

Gantt 图：又称横道图，横轴表示时间，纵轴表示活动，以时间顺序表示活动，能反应活动间的并行关系，但无法反应活动间的依赖关系，因此也难以清晰的确定关键任务和关键路径。

PERT 图：类似前趋图，是有向图，反应活动间的依赖关系，有向边上标注活动的运行时间，但无法反应活动间的并行关系。

PERT 图关键路径：

最早开始时间 ES：取所有前驱活动最早完成时间 EF 的最大值。
最早完成时间 EF：ES + DU（活动本身时间）。
关键路径（项目总工期）：项目中耗时最长的线路。
最晚完成时间 LF：取后续活动最晚开始时间的最小值。
最晚开始时间 LS：LF - DU。
松弛时间：LS - ES 或者 LF - EF （即活动最多可以晚几天开始）。

例：关键路径为图中最长的路径即 D-F-H 权值为 48 所以第一空选 C。 FG 的松弛时间为关键路径 - 包含 FG 的最长路径（DFH）-（DFG）=48-28=20 所以第二空为 B。

软件项目的组织

程序设计小组的组织方式：

主程序员制小组：主程序员全权负责，后援工程师有必要时能替代主程序员，适合大规模项目。
民主制小组：也即无主程序员小组，成员之间地位平等，任何决策都是全员参与投票，适合于项目规模小，开发人员少，采用新技术和确定性较小的项目。
层次式小组：两个层次，一名组长领导若干个高级程序员，每个高级程序员领导若干个程序员。

软件开发项目管理

软件质量管理

通常将质量理解为用户满意程度，为了使用户满意，有两个必要条件：设计的规格说明书符合用户标准，称为设计质量。程序按照设计规模书所规定的情况正确执行，称为程序质量。设计质量评审，程序质量评审。

质量特性	质量子特性
功能性	适合性准确性互用性依从性安全性
可靠性	成熟性容错性易恢复性
易使用性	易理解性易学性易操作性
效率	时间特性资源特性
可维护性	易分析性易改变性稳定性易测试性
可移植性	适应性易安装性一致性易替换性

易分析性：与为诊断缺陷或失效原因，或为判定待修改部分所需那里有关的软件属性。
易改变性：与进行修改、排错、或适应环境变换所需努力有关的软件属性。
稳定性：与修改造成未预料效果风险有关的软件属性。
易测试性：为确认经修改软件所需努力有关的软件属性。

软件容错技术

容错就是软件遇到错误的处理能力，实现容错的手段主要是冗余，包括下面四种冗余技术：

结构冗余：分为静态（通过表决和比较，少数服从多数）、动态（多重模块待机备份，故障是切换备份机）、混合冗余（二者综合）。
信息冗余：为检错和纠错在数据中加上一段额外的信息，例如检验码原理。
时间冗余：遇到错误是重复执行，例如回滚，重复执行还有错，则转入错误处理逻辑。
冗余附加技术：冗余附加技术是指为实现数据结构，信息和时间冗余技术所需的资源和技术，包括程序，指令，数据，存放和调动它们的空间和通道等

风险管理

风险管理两个特性：不确定性（可能发生也可能不发生）、损失（发生会产生恶性后果）。

项目风险威胁到项目计划，如果项目风险发生，有可能拖延项目的进度和增加项目的成本，指预算。进度、人员、资源。利益相关者、需求等方面的潜在问题以及它们对软件项目的影响。项目复杂度、规模及结构不确定性也属于项目风险因素。
技术风险威胁到要开发软件的质量和交付时间，如果技术风险发生，开发工作就变得很困难或者不可能，只设计、实现、接口、验证和维护等方面的潜在问题。此外，规格说明的歧义性，技术的不确定性，技术陈旧以及“前沿”技术也是技术风险因数。

商业风险威胁到要开发软件的生存能力，包括下面五种：

市场风险：开发了一个没有人真正需要的优良产品或系统。
策略风险：开发的产品不在符合公司的整体商业策略。
销售风险：开发了一个销售部门不知道该如何销售的产品。
管理风险：由于重点的转移或人员变动而失去了高级管理层的支持。
预算风险：没有得到预算或人员的保证。

风险管理过程如下：

风险识别：识别出项目中已知和可预测的风险，确定风险的来源，产生的条件，描述风险的特征以及哪些项目可以产生风险。形成一个风险列表。
风险预测：又称为风险估计，从两个方面预测风险，即风险可能发生的概率和风险产生的后果，因此有风险曝光度=风险发生的可能性*风险发生带来的损失。
风险评估：定义风险参照水准，将识别出来的风险评估分类。
风险控制：辅助项目组建立处理风险的策略，包括风险避免，风险监控，RMMM 计划（风险缓解，监控和管理计划）

软件度量

软件的两种属性：外部属性指面向管理者和用户的属性，可直接测量，一般为性能指标。内部属性指软件产品本身的属性，如可靠度等，只能间接测量。 McCabe 算法：又称为环路复杂度，假设有向图中有向边数为 M，节点数为 N，则此有向图的环路复杂度为 M-N+2。

软件过程管理

能力成熟度模型 CMM

能力成熟度模型 CMM：对软件组织化阶段的描述，随着软件组织地定义、实施，测量、控制和改进其软件过程，软件组织地能力经过这些阶段逐步提高。

初始级（Initial）：软件过程的特点是杂乱无章，又是甚至很混乱，几乎没有明确定义的步骤，项目的完成全依赖个人的努力和英雄式核心人物的作用。
可重复级（Repeatable）：建立了基本的项目管理过程和实践来跟踪项目费用、进度和功能特性，有必要的过程准则来重复以前在同类项目中的成功。
已定义级（Defined）：管理和工程两方面的软件过程已经文档化、标准化，并综合成整个软件来发组织地标准软件过程，所有项目都采用根据实际情况修改后得到的标准软件过程来开发和维护软件。
已管理级（Managed）：制定了软件过程和产品质量的详细度量标准。软件过程的产品质量都被开发组织地成员所理解和控制。
优化级（Optimized）：加强了定量分析，通过来之过程质量反馈和来自新观念、新技术的反馈使过程能不断持续地改进。

能力成熟度模型 CMMI

能力成熟度模型 CMMI：将已有的几个 CMM 模型结合在一起，使之构造成为“集成模型”。支持多个工程学科和领域的、系统的、一致的过程改进框架，能适应现代工程的特点和需求，能提高过程的质量和工作效率。阶段式模型：类似于 CMM，它关注组织地成熟度，五个成熟度模型如下：

初始的：过程不可预测且缺乏控制。
已管理的：过程为项目服务。
已定义的：过程为组织服务。
定量管理的：过程为以度量和控制。
优化的：集中于过程改进。

维护

软件维护是软件设计生存周期中时间最长的阶段。已交付的软件投入正式使用后，便进入软件维护阶段，它可以持续几年甚至十几年。

软件过程模型

统一过程模型（UP）

统一过程模型：是一种“用例和风险驱动，以架构为中心，迭代并且增量”的开发过程。开发的四个阶段

起始阶段：项目的初始活动，如确认需求和风险评估等。
精化阶段：需求分析和架构设计等。
构建阶段：系统的构建，产生实现模型等。
移交阶段：软件提交方面的工作，产生软件增量，进行 β 测试，交付系统等。 UP 的每一次迭代都是一次完整的软件开发过程，包括整个软件开发生命周期，有五个核心工作流（需求-分析-设计-实现-测试）。

瀑布模型

结构化方法中的模型，是结构化的开发，开发流程如瀑布一样，一步一步走下去，直到项目完成开发只适用于需求明确或者二次开发（需求稳定）的项目。

V 模型

是瀑布模型的一个变种。特点是增加了多轮测试，并且这些测试贯穿于软件开发的各个阶段。

原型

快速原型开发，与瀑布模型相反，原型针对需求不明确的情况。

螺旋模型

是多种模型的混合，针对需求不明确的项目，与原型相似，但增加了风险分析（制定计划—风险分析—实施工程—用户评估）。

增量模型

首先开发核心功能模块，而后与用户确认，之后再开发次核心功能，即每次开发一部分功能，并与用户需求确认，最终完成项目开发，优先级高的服务最先交付。增量模型的每一次增量版本都可作为独立操作的作品。

喷泉模型

是一种以用户需求为动力，以对象作为驱动的模型。适用于面向对象的开发方法是开发过程具有迭代性和无间隙性

基于构建的开发模型

利于预先包装的构件来构造应用系统，构件是可以组织内部开发的构件，也可以是商品化成品软件构件。提点是增强了复用性，在系统开发过程中，会构建一个构件库，供其他系统复用，因此可以提高复用性，节省时间和成本。

敏捷开发

敏捷开发的总体目标是通过“尽可能早，持续地对有价值的软件的交付”使客户满意。通过在软件开发过程中加入灵活性，敏捷开发使用户能够在开发周期的后期增加或者改变需求。

自适应开发（ASD）

强调开发方法的适应性。

水晶方法（Crystal）

水晶法认为每一个不同项目都需要一套不同的策略，约定和方法论。

特性驱动开发

是一套针对中小型软件开发项目的开发模式，是一个模型驱动的快速迭代开发过程，它强调的是简化，使用，易被开发团队接受，适用于需求经常变动的项目。

并列争求法（Scrum）

并列争求法是一种迭代的增量化过程，其中，把每 30 天一次的迭代称为一个“冲刺”，并按需求的优先级来实现产品。

极限编程（XP）

XP 是一种轻量级（敏捷），高效，低风险，柔性，可预测，科学的软件开发方式。 四大价值观：沟通，简单性，反馈和勇气。 五个原则：快速反馈，简单性假设，逐步修改，提倡更改和优质工作。 12 个最佳实践：计划游戏，小型发布，隐喻，简单设计，测试先行，重构，结队编程，集体代码所有制，持续集成，每周工作 40 小时，现场客户和编码标准

结对编程

一个程序员开发，另一个审查代码，能够有效的提高代码的质量。

系统开发与运行

系统分析概述

系统分析是一种问题的求解技术，它将一个系统分解成各个组成部分，目的是研究各个部分如何工作，交互，以实现其系统目标。目的和任务：系统分析的主要任务是对现行系统进一步详细调查，将调查中所得到的文档资料集中，对组织内部整体管理状况和信息处理过程进行分析，为系统开发提供所需资料，并提交系统方案说明书。系统分析的主要步骤:

认识、理解当前的现实环境，获得当前系统的“物理模型”。
从当前系统的“物理模型”抽象出当前系统的“逻辑模型”。
对当前系统的“逻辑模型”进行分析和优化，建立目标系统的“逻辑模型”。
对目标系统的逻辑模型具体化（物理化），建立目标系统的物理模型。

系统开发的目的是将现有系统的物理模型转换为目标系统的物理模型。

系统设计

抽象

本质：聚焦问题核心本质，忽略非本质细节（如具体实现、技术差异），提炼关键特征形成通用模型。作用：简化复杂系统，让设计者专注于 “做什么” 而非 “如何做”（例如将磁盘抽象为文件系统，屏蔽物理存储细节）。

模块化

定义：将系统拆解为可独立设计、组合、替换的单元（模块），每个模块完成特定功能（如用户模块、支付模块）。特性：

可分解：按功能 / 逻辑拆分（如 MVC 模式分为模型、视图、控制器）。
可组合：通过标准接口灵活组装（如插件式架构新增功能）。
可替换：模块实现可独立升级（如更换数据库驱动不影响上层逻辑）。

信息隐蔽

核心：将模块内部细节（算法、数据结构等）封装隐藏，仅通过公开接口（如函数、API）对外提供服务（形成 “黑盒”）。目的：减少模块间依赖，修改内部实现不影响外部调用（如文件系统仅暴露read/write接口，隐藏磁盘块分配逻辑）。

模块独立

设计目标：追求高内聚、低耦合，是衡量模块质量的核心标准：

高内聚：模块内部功能高度相关（一个模块仅完成单一明确任务，如 “用户登录验证” 模块）。
低耦合：模块间联系简单（仅通过数据交互，无复杂逻辑依赖，如模块 A 调用模块 B 时仅传递参数，不操作其内部数据）。

关键：内聚体现模块 “内部紧密性”，耦合体现模块 “外部依赖性”——内聚越高越好，耦合越低越好。

内聚

内聚程度从低到高如下表所示：

内聚分类	定义	记忆关键字
偶然内聚	一个模块内各处理元素之间没有任何联系	无直接关系
逻辑内聚	模块内执行若干个逻辑上相似的功能，通过参数确定改模块完成哪一个功能	逻辑相似，参数决定
时间内聚	把需要同时执行的动作组合在一起形成模块	同时执行
过程内聚	一个模块完成多个任务，这些任务必须按指定的过程执行	指定的过程顺序
通信内聚	模块内所有处理元素都在同一个数据结构上操作，或者各处理使用相同的输入数据或产生相同的输出数据	相同的数据结构、形同的输入输出
顺序内聚	一个模块中各个处理元素都密切相关于同一功能且必须顺序执行，前一个功能元素的输出就是后一个功能元素的输入	顺序执行、输入为输出
功能内聚	最强的内聚，模块内所有元素共同作用完成一个功能，缺一不可	共同作用，缺一不可

耦合

耦合程度从低到高如下表所示：

耦合分类	定义	记忆关键字
无直接耦合	两个模块之间没有直接的关系，它们分别从属于不同模块的控制与调用，不传递任何信息	无直接关系
数据耦合	两个模块之间有调用关系，传递的是简单的数据值，相当于高级语言中的值传递	传递数据值调用
标记耦合	两个模块之间传递的是数据结构	传递数据结构
控制耦合	一个模块调用另一个模块时，传递的是控制变量，被调用模块通过该控制变量的值，有选择的执行模块内的某一功能	控制变量，选择执行某一功能
外部耦合	模块间通过软件之外的环境联合（如 I/O 将模块耦合到特定的设备，格式，通信协议）时	软件外部环境
公共耦合	通过一个公共数据环境相互作用的那些模块间的耦合	公共数据结构
内容耦合	当一个模块直接使用另一个模块的内部数据，或通过非正常入口转入另一个内部模块时	模块内部关联

系统设计

系统设计的主要目的是为系统制定蓝图，在各种技术和实施方法中权衡利弊，精心设计，合理地使用各种资源，得出新系统的详细设计方案。

步骤：概要设计和详细设计

概要设计基本任务：

设计软件系统总体结构
数据结构及数据库设计
编写概要设计文档
评审

详细设计基本任务：

模块内详细算法设计
模块内数据结构设计
数据库物理设计
其他设计（代码、输入输出格式、用户界面）
编写详细设计文档
评审

软件需求

按需求内容分类：

业务需求：由客户提出的宏观功能需求。
用户需求：设计员通过调查，获取每个用户的具体需求。
系统需求：整合后的最终需求，包含功能、性能、设计约束三个方面。

从客户角度分类：

基本需求：需求中明确规定的功能。
期望需求：除基本需求外，客户认为应包含的其他功能。
兴奋需求：客户未要求的功能需求，可能增加项目开发时间和成本。

软件需求分类：

功能需求：软件必须完成的基本动作。
性能需求：软件或人机交互的静态 / 动态数值需求，如系统响应速度、处理速度等。
设计约束：受硬件标准等外部因素的限制。
属性：可用性、安全性、可维护性、可移植性。
外部接口需求：用户接口、硬件接口、软件接口、通信接口。

测试基础知识

系统测试是为了发现错误而执行程序的过程，成功的测试是发现了至今尚未发现的错误的测试。

测试原则：

应尽早并持续进行测试。
测试工作避免由开发软件的人员或小组承担。
设计测试方案时，需确定输入数据及预期输出结果。
测试用例包含有效、合理及不合理、失效的情况。
检验程序是否完成应做之事，且未做不应做之事。
严格按测试计划执行。
妥善保存测试用例和测试计划。
测试用例可重复使用或追加测试。

测试阶段

单元测试：对单个模块进行测试，由程序员依据软件详细说明书，测试模块内部接口、信息和功能。单元测试中，驱动模块（上层）用于调用被测模块（自顶向下测试无需额外编写），桩模块（底层）模拟被测模块调用的子模块。
集成测试：将模块组合测试，分为一次性组装（简单、省时、发现错误少，适用于小项目）和增量式组装（能发现更多错误，耗时，可分为自顶向下、自底向上、混合式）。
确认测试：对完成的软件进行功能测试，包括内部确认测试（无用户参与）、Alpha 测试（用户在开发环境测试）、Beta 测试（用户在实际使用中测试）、验收测试（用户依据 SRS 验收项目）。
系统测试：对软件进行性能测试，主要包括负载测试（极限情况下的性能指标）、强度测试（低资源情况下）、容量测试（并发测试，最大在线用户数），还涉及可靠性等测试，一般采用黑盒测试方法。
回归测试：软件修改或变更后，验证修改是否引入新错误。
动态测试：程序运行时测试，分为：
- 黑盒测试法：功能性测试，基于功能设计用例，不关注代码结构。
- 白盒测试法：结构性测试，依据代码逻辑设计用例，实现代码覆盖。
- 灰盒测试法：结合黑盒与白盒测试。
静态测试：程序静止时进行，即人工审查代码，分为：
- 桌前检查：程序员在程序编译后、单元测试前，检查自己编写的程序。
- 代码审查：由程序员和测试人员组成评审小组，通过会议评审程序。
- 代码走查：通过会议审查代码，测试人员提供用例，程序员模拟计算机手动运行用例，检查代码逻辑。

测试策略

自底向上：从底层模块开始测试，需编写驱动程序，逐步合并模块完成系统测试，优点是可较早验证底层模块。
自顶向下：先测试整个系统，需编写桩程序，逐步向下测试底层模块，优点是可较早验证系统主要控制和判断点。
三明治：结合自底向上和自顶向下测试方法，兼具两者优点，但测试工作量大。

测试用例设计

黑盒测试用例：将程序视为黑盒，仅关注输入输出，设计用例分类如下：

等价类划分：将数据按特性归类，从每类中选取数据。设计原则为：先设计用例覆盖未覆盖的有效等价类，直至全部覆盖；再设计用例覆盖未覆盖的无效等价类，直至全部覆盖。
边界值划分：选取每类数据的边界值作为测试用例，边界值通常为范围两端值及范围外与之间隔最小的两个值，如年龄范围 0 - 150，边界值为 0、150、1、151。

白盒测试用例：依据代码逻辑，设计覆盖代码分支的用例，覆盖级别从低到高分为六种：

语句覆盖：执行逻辑代码中的所有语句，覆盖层级最低，执行所有语句不代表覆盖所有条件判断。
判定覆盖：覆盖逻辑代码中所有判断语句条件的真假分支。
条件覆盖：对代码中每个独立条件的真假分支都进行覆盖，例如对于条件 a>0&&b<0，条件覆盖需对 a>0 和 b<0 各自的真假分支设计测试用例，共 4 个，比判定覆盖层级更高。
判定 / 条件覆盖：使判定中每个条件的所有可能取值（真 / 假）至少出现一次，且每个判定本身的结果（真 / 假）也至少出现一次，综合了判定覆盖和条件覆盖。
条件组合覆盖：覆盖每个判定条件中所有条件的可能值组合。
路径覆盖：覆盖逻辑代码中所有可行路径，覆盖层级最高。

面向对象技术

面向对象基本概念

面向对象分析：是为了确定问题域，理解问题。包含五个活动：认定对象(按自然存在的实体确定对象)、组织对象(分析对象关系,抽象成类)、对象间的互相作用(描述各对象在应用系统中的关系)、确定对象的操作(操作,如创建增加删除等)、定义对象的内部信息(属性)

面向对象设计：是设计分析模型和实现相应源代码，在目标代码环境中这种源代码可被执行。设计问题域的解决方案。面向对象程序设计：用面向对象程序设计语言实现设计方案。详见案例分析。面向对象测试：与普通测试步骤并无不同。可分为四个层次：

算法层(测试类中定义的每个方法，类似单元测试)
类层(测试同一个类中所有方法与属性的互相作用，特有的模块测试)
模板层(测试一组协同工作的类之间的互相作用，类似集成测试)
系统层(类似系统测试)

UML 图

UML 是统一建模语言，和程序设计语言并无关系。 UML 三个要素：UML 的基本构造快、支配这些构造块如何放置在一起的规则和运用与整个语言的一些公共机制。 UML 的基本构造快包括：事务（对模型中最具有代表性的成分的抽象）、关系（把事务结合在一起）、图（聚集了相关的事务）。 UML 中有四种事务：结构事务、行为事务、分组事务、注释事务。

结构事务：模型的静态部分，如类、接口、用例、构件等如下图示例：

事务

关系

依赖：一个事务的语义依赖于另一个事务的语义变化而变化
关联：是一种结构关系，描述一组链，链是对象之间的连接。分为组合（强关联）和聚合（弱关联）
泛化：一般/特殊的关系，子类和父类之间的关系。
实现：一个类元指定了另一个类元保证执行的契约。

类图

类图：静态图，为系统的静态设计视图，展现一组对象、接口、协作和他们之间的关系。

对象图

对象图：静态图，展现某一时刻一组对象及他们之间的关系，为类图的某一快照。在没有类图的前提下，对象图就是静态设计图。

用例图

用例图：静态图，展现了一组用例、参与者以及他们之间的关系。 用例图中的参与者是人、硬件或其它系统可以扮演的角色；用例是参与者完成的一系列操作。用力之间的关系包括：

包含(include)
扩展(extend)
泛化

序列图

序列图：即顺序图，动态图，是场景的图形化表示，描述了以时间顺序组织的对象之间的交互活动。有同步消息（进行阻塞调用，调用者中止执行，等待控制权返回，需要等待返回消息，用实心三角箭头表示）、 异步消息（发出消息后继续执行，不引起调用者阻塞，也不等待返回消息，由空心箭头表示）、 返回消息（由从右到左的虚线箭头表示）三种。

通信图

通信图：动态图，即协作图，是顺序图的另一种表示方法，也是由对象和消息组成的图，只不过 不强调时间顺序，只强调事件之间的通信，而且也没有固定的画法规则，和顺序图统称为交互图。

状态图

状态图：动态图，展现了一个状态机，描述单个对象在多个用例中的行为，包括单状态和组合状态。转换可以通过事件触发器出发，事件触发后相应的监护条件会进行检查。

状态图中转换和状态是两个独立的概念，如下：图中方框代表状态，箭头上的代表触发事件，实心圆点为起点和终点。下图描述的就是一个图书的状态变化：

活动图

活动图：动态图，是一种特殊的状态图，展现了在系统内从一个活动到另二个活动的流程。 活动的分叉和汇合线是一条水平粗线。 每个分岔的分支数代表了可同时运行的线程数。活动图中能够并行执行的是在一个分岔粗线下的分支上的活动。

UML 图总结

图名称	用途	类型
类图	静态图，为系统的静态设计视图，展现一组对象、接口、协作和他们之间的关系。	静态图
对象图	静态图，展现某一时刻一组对象及他们之间的关系，为类图的某一快照。在没有类图的前提下，对象图就是静态设计图。	静态图
用例图	静态图，展现了一组用例、参与者以及他们之间的关系。	静态图
序列图	即顺序图，动态图，是场景的图形化表示，描述了以时间顺序组织的对象之间的交互活动。	动态图
通信图	不强调时间顺序，只强调事件之间的通信，而且也没有固定的画法规则，和顺序图统称为交互图	动态图
状态图	动态图，展现了一个状态机，描述单个对象在多个用例中的行为，包括单状态和组合状态。	动态图
活动图	展现了在系统内从一个活动到另二个活动的流程。	动态图

设计模式

创建型设计模式

速记口诀：单抽元件厂

模式名称	定义	记忆关键字
Singleton 单例模式	确保一个类仅有一个实例，并提供全局访问点	唯一实例
Abstract Factory 抽象工厂模式	提供一个接口来创建相关或依赖对象的家族，而不需要指定具体类	抽象接口
Prototype 原型模式	通过复制现有原型对象来创建新对象，避免重复初始化操作	原型实例化，拷贝
Builder 构建器模式	将复杂对象的构造与其表示分离，使同样的构建过程可以创建不同对象	类和构造分离
Factory Method 工厂方法模式	定义一个创建对象的接口，但让子类决定实例化哪个类	子类决定实例化

结构型设计模式

速记口诀：外侨组员带配饰

模式名称	定义	记忆关键字
Facade 外观模式	为复杂子系统提供一个统一的高层接口，简化调用过程	对外统一接口
Bridge 桥接模式	将抽象部分与其实现部分分离，使它们可以独立变化	抽象和实现分离
Composite 组合模式	将对象组合成树形结构以表示”整体-部分”的层次关系	整体-部分，树形结构
Flyweight 享元模式	通过共享技术来高效地支持大量细粒度对象的重用	细粒度，共享
Proxy 代理模式	为其他对象提供一种代理以控制对这个对象的访问	代理控制
Adapter 适配器模式	将一个类的接口转换为另一个接口，使原本不兼容的类可以协同工作	转换，兼容接口
Decorator 装饰模式	动态地给对象添加额外的职责，相比继承更加灵活	附加职责

行为型设计模式

速记口诀：观摩对(迭)策，责令解放，戒忘台

模式名称	定义	记忆关键字
Observer 观察者模式	定义对象间的一对多依赖关系，当一个对象状态改变时自动通知所有依赖对象	通知、自动更新
Template Method 模板方法模式	定义算法框架，允许子类在不改变结构的情况下重写特定步骤	子类可重写算法步骤
Iterator 迭代器模式	提供一种方法顺序访问聚合对象的元素，而不暴露其内部表示	顺序访问，不暴露内部
Strategy 策略模式	定义一系列算法，将每个算法封装在独立的类中，并使它们可以相互替换	算法替换
Chain of Responsibility 责任链模式	将请求沿着处理链传递，直到有对象处理它	传递请求、职责链接
Command 命令模式	将请求封装为对象，支持可撤销操作和请求队列	日志记录、可撤销
Interpreter 解释器模式	定义语言的文法表示，并提供解释器来处理该语法	解释器，虚拟机
Visitor 访问者模式	将作用于对象结构的操作与对象本身分离，便于新增操作	数据和操作分离
Mediator 中介者模式	定义一个中介对象来封装一组对象间的交互，降低耦合度	不直接引用
Memento 备忘录模式	在不破坏封装性的前提下，捕获并保存对象的内部状态以便恢复	保存，恢复
State 状态模式	允许对象在其内部状态改变时改变它的行为	状态变成类

面向对象设计原则

单一职责原则：一个对象应该只包含单一的职责，并且该职责被完整的封装在一个类中
开闭原则：软件实体应当对扩展开放，对修改关闭
里氏替换原则：所有引用基类的地方必须能透明的使用其子类的对象
依赖倒转原则：高层模块不应该依赖低层模块，他们都应该依赖抽象。抽象不应该依赖于细节，细节应该依赖于抽象
接口隔离原则：客户端不应该依赖那些它不需要的接口
合成复用原则：优先使用对象组合，而不是继承来达到复用的目的
迪米特法则：每一个软件单位对其他的单位都只有最少的知识，而且局限于那些与本单位密切相关的软件单位

网络与信息安全和病毒防护

ISO/OSI 网络体系结构

层次	功能描述	典型协议 / 技术	数据单元	对应设备
7. 应用层	直接为用户应用程序提供服务（如文件传输、电子邮件、远程登录等）。	HTTP、FTP、SMTP、POP3、DNS、Telnet、SSH	消息（Message）	主机（终端设备）
6. 表示层	负责数据格式转换（如加密、压缩、解码），确保不同系统间数据格式兼容。	SSL/TLS、JPEG、MPEG、ASCII、UTF-8	数据（Data）	无特定硬件设备（软件实现）
5. 会话层	管理主机间的通信会话（建立、维护、终止），如会话同步和错误恢复。	NFS、RPC、ZIP（会话管理）	会话数据单元	无特定硬件设备（软件实现）
4. 传输层	实现端到端的可靠（TCP）或不可靠（UDP）数据传输，处理流量控制和错误恢复。	TCP、UDP、SPX（Novell）	段（Segment）	无特定硬件设备（软件实现）
3. 网络层	负责网络间的逻辑寻址和路由选择，将数据从一个网络传输到另一个网络。	IP、ICMP、IGMP、OSPF、BGP	数据包（Packet）	路由器（Router）
2. 数据链路层	将物理层的比特流封装为帧，实现相邻节点间的可靠传输（错误检测、流量控制）。	Ethernet、PPP、HDLC、VLAN、802.11（Wi-Fi）	帧（Frame）	交换机（Switch）、网桥（Bridge）、网卡（NIC）
1. 物理层	定义物理设备的电气、机械特性，传输原始比特流（0/1 信号）。	IEEE 802.3（以太网）、RJ-45、光纤、同轴电缆	比特（Bit）	集线器（Hub）、中继器（Repeater）、网卡（NIC）

以下是对网络协议、网络安全、加密技术及常见网络诊断命令的优化整理，采用清晰的结构化格式：

网络协议

1. 局域网协议

协议标准	速率	传输介质	描述
IEEE 802.3	10Mbps	同轴电缆	标准以太网协议，基础局域网通信。
IEEE 802.3u	100Mbps	双绞线	快速以太网协议，支持更高带宽。
IEEE 802.3z	1Gbps	光纤/双绞线	千兆以太网协议，支持光纤或超五类双绞线。

2. 网络层协议

协议	功能	关键特性
IP 协议	负责寻址和路由，将数据包从源传到目标。	无连接、不可靠，仅保证尽力传输。
ICMP 协议	网络诊断与错误报告（如 ping 命令）。	属于 IP 协议的补充，用于检测网络连通性。
ARP 协议	将 IP 地址映射为物理地址（MAC）。	IP → MAC，用于本地网络通信。
RARP 协议	将物理地址（MAC）映射为 IP 地址。	MAC → IP，常用于无盘工作站启动。

3. 传输层协议

协议	可靠性	特点	典型应用
TCP 协议	可靠	面向连接，三次握手建立连接，保证数据有序、无错传输。	文件传输（FTP）、网页浏览（HTTP）
UDP 协议	不可靠	无连接，低延迟，适用于实时性要求高的场景。	视频通话、在线游戏、DNS 查询

4. 应用层协议

协议	传输协议	端口	功能	可靠性
HTTP	TCP	80	超文本传输协议，用于网页浏览。	可靠
HTTPS	TCP	443	HTTP + SSL/TLS 加密，安全传输。	可靠
FTP	TCP	21 (控制) 20 (数据)	文件传输，支持文件上传/下载。	可靠
DNS	UDP	53	域名解析，将域名转换为 IP 地址。	不可靠
DHCP	UDP	67/68	动态分配 IP 地址，客户端/服务器模式，默认租期 8 天。	不可靠
SMTP	TCP	25	邮件发送协议，使用 ASCII 格式。	可靠
POP3	TCP	110	邮件接收协议，从服务器下载邮件。	可靠
Telnet	TCP	23	远程登录，明文传输（不安全）。	可靠

网络安全

1. 核心要素

保密性：数据仅对授权用户可见。
完整性：数据未被篡改。
可用性：系统资源可被授权用户随时访问。
可控性：对网络行为和资源有控制权。
不可抵赖性：操作行为可追溯，不可否认。

2. 防火墙

类型	层级	特点	优缺点
网络级防火墙	网络层	基于包过滤，检查 IP、端口、协议等。	优点：速度快，透明性高；缺点：无法检测内部伪装数据。
应用级防火墙	应用层	深度检测数据内容，如代理服务器。	优点：安全性高；缺点：效率低，资源消耗大。

DMZ（非军事区）：

位于内外网之间，存放 Web 服务器、邮件服务器等对外服务，增强内网安全。

3. 病毒与木马

类型	描述	示例
病毒	自我复制，破坏数据或系统功能。	CIH（破坏硬件）、宏病毒（如“美丽沙”）
木马	隐藏的后门程序，窃取数据或控制权。	冰河、特洛伊木马
蠕虫	通过网络自主传播，无需用户干预。	熊猫烧香、冲击波

4. 网络攻击类型

攻击类型	描述	示例
拒绝服务（DoS）	洪泛网络资源，导致合法用户无法访问。	SYN Flood、CC 攻击
中间人（MITM）	窃听或篡改通信数据。	ARP 欺骗、DNS 劫持
重放攻击	重复发送合法数据包以达到恶意目的。	窃取认证信息
SQL 注入	通过输入恶意 SQL 代码攻击数据库。	篡改或窃取数据
XSS	在网页中注入恶意脚本，攻击用户浏览器。	盗取 Cookie、会话令牌

加密技术

1. 基本概念

明文：原始数据。
密文：加密后的数据。
加密/解密：通过算法和密钥转换数据。
对称加密：加密/解密使用同一密钥。
非对称加密：加密/解密使用公钥和私钥。

2. 对称加密算法

算法	特点	适用场景
DES	56 位密钥，速度快，但安全性低。	历史遗留系统
3DES	三重 DES，安全性增强，但效率低。	金融、支付系统
AES	128/192/256 位密钥，安全性高，效率适中。	现代加密标准（如 SSL/TLS）
RC-5/IDEA	可变参数，灵活性高。	专用加密场景

3. 非对称加密算法

算法	特点	典型应用
RSA	基于大整数分解，密钥长度长（1024/2048 位）。	数字签名、SSL/TLS 握手
ECC	基于椭圆曲线数学，密钥长度短，安全性高。	移动设备、物联网
ElGamal	基于 Diffie-Hellman 密钥交换，支持加密和数字签名。	安全通信协议

常见网络诊断命令

命令	功能	常用参数/示例
ping	检测网络连通性，发送 ICMP 回显请求。	`ping 8.8.8.8`
tracert	跟踪数据包路径，定位网络故障点。	`tracert www.google.com`
ipconfig	显示/修改 TCP/IP 配置（Windows）。	`ipconfig /release`（释放 IP） `ipconfig /flushdns`（清除 DNS 缓存）
nslookup	查询 DNS 记录，验证域名解析。	`nslookup baidu.com`
netstat	显示网络连接、端口状态及路由表。	`netstat -ano`（查看所有连接）

数据库技术

数据库基础知识

数据库：是指按照一定的结构来存储和管理数据的仓库。
数据库管理系统（DBMS）：是用于创建和管理数据库的软件系统。它允许用户定义、创建、维护和控制对数据库的访问。
数据库系统（DBS）：由数据库、数据库管理系统（及其开发工具）、应用系统、数据库管理员（DBA）和用户构成的整体。

数据库类型

关系型数据库（RDBMS）
- 使用表格形式存储数据，其中行代表记录，列表示字段。
- 支持 SQL 作为查询语言。
- 常见的关系型数据库有 MySQL、PostgreSQL、Oracle、Microsoft SQL Server 等。
非关系型数据库（NoSQL）
- 不使用传统的表格形式存储数据，而是采用键值对、文档、列族或图形存储方式。
- 更加灵活，适用于大规模分布式系统。
- 常见的 NoSQL 数据库有 MongoDB（文档型）、Cassandra（列族型）、Redis（键值对型）、Neo4j（图数据库）等。

数据模型

层次模型：早期的数据组织形式，以树状结构表示数据之间的关系。
网状模型：比层次模型更复杂，允许一个子节点拥有多个父节点。
关系模型：现代最常用的模型，基于数学理论，通过表格的形式展示数据间的联系。
面向对象模型：将数据和方法封装在一起，支持复杂的对象结构。

SQL 基础

数据定义语言（DDL）：用于定义数据库结构，如CREATE, ALTER, DROP等命令。
数据操作语言（DML）：用于添加、更新、删除数据，如INSERT INTO, UPDATE, DELETE FROM等。
数据查询语言（DQL）：用于检索数据，主要命令为SELECT。
数据控制语言（DCL）：用于权限管理，如GRANT, REVOKE等命令。

事务管理

事务：指作为一个逻辑单元执行的一系列操作，要么全部成功，要么全部失败回滚。
ACID 属性：
- 原子性（Atomicity）：事务是不可分割的工作单位，要么都做，要么都不做。
- 一致性（Consistency）：事务必须使数据库从一个一致性状态变换到另一个一致性状态。
- 隔离性（Isolation）：并发事务之间相互不影响。
- 持久性（Durability）：一旦事务提交，它对数据库的影响就是永久性的。

E-R 模型

E-R 模型（实体-联系模型）

1. 基本概念

定义：E-R 模型是用户视角的数据建模工具，通过实体、属性和联系描述现实世界的信息结构。
- 实体（Entity）：现实世界可区分的对象，用矩形表示（如学生、课程）。
  - 软考重点：需明确实体的业务含义，避免遗漏关键实体（如“订单”与“订单详情”）。
- 属性（Attribute）：实体的特征，用椭圆表示，分为：
  - 主属性（主键）：唯一标识实体（如学号），需用下划线或加粗标注。
  - 次属性：非唯一属性（如姓名、年龄）。
  - 软考重点：主键选择需唯一且最小化，避免多值属性（如“电话”可能为多值需单独表）。
- 联系（Relationship）：实体间的关联，用菱形表示，分为：
  - 一对一（1:1）：如“身份证号”与“个人”的关系。
  - 一对多（1:N）：如“部门”与“员工”的关系。
  - 多对多（M:N）：如“学生”与“课程”的选课关系。
  - 软考重点：联系类型判断是考试高频考点，需结合业务场景（如“教师授课”是 1:N 还是 N:M）。

2. E-R 图设计步骤

确定实体：明确系统涉及的对象（如学生、教师、课程）。
定义属性：为每个实体列出属性，并标记主属性。
- 软考重点：主键需唯一且不可为空，避免冗余属性。
分析联系：确定实体间的关联类型（1:1、1:N、M:N）。
转换为关系模式：
- 一对一（1:1）：合并到任意一端实体的表中，或单独建表。
  - 软考重点：若合并需考虑业务需求，考试中常考“如何选择更优方案”。
- 一对多（1:N）：在“多”端实体表中添加“一”端的主键作为外键。
  - 软考重点：外键命名需规范（如DepartmentID作为员工表的外键）。
- 多对多（M:N）：创建中间表，包含双方主键作为联合主键（如学生选课表包含学生学号和课程号）。
  - 软考重点：多对多联系必须转为中间表，否则视为错误设计。

3. 转换规则与常见错误

多对多联系：必须转为中间表，联合主键需包含双方主键。
三个实体的联系：需拆分为两个二元联系，分别建表。
软考重点：考试中常出现“三元联系”转换错误，需拆分后设计中间表。

综合示例与考点解析

题目：
设计学生选课系统的 E-R 图，并转换为关系模式。
解答步骤：

E-R 图设计：
- 实体：学生（学号（主键），姓名，年龄）、课程（课程号（主键），课程名，学分）。
- 联系：选课（学号，课程号，成绩）。
- 考点：需正确标注主键（学号、课程号），联系类型为 M:N。
关系模式转换：
- 学生表：Student(Sno, Sname, Sage)（主键：Sno）。
- 课程表：Course(Cno, Cname, Credit)（主键：Cno）。
- 选课表：SC(Sno, Cno, Grade)（主键：(Sno, Cno)，外键：Sno→Student.Sno，Cno→Course.Cno）。
- 考点：中间表需包含双方主键作为联合主键，外键命名规范。

关键考点总结

E-R 模型：

E-R 图绘制：实体、属性、联系的正确标注及类型判断。
多对多联系转中间表，避免遗漏。
主键与外键的规范设置。

SQL 语言

基础查询（SELECT）

作用：从数据库中检索数据。 基本语法：

SELECT 列名1, 列名2, ...
FROM 表名
[WHERE 条件]
[GROUP BY 分组列]
[HAVING 分组条件]
[ORDER BY 排序列 ASC/DESC]
[LIMIT 分页参数];

1. 基础用法

查询所有列：
```
SELECT * FROM 表名;  -- 返回表中所有行和列
```
示例：SELECT * FROM 学生;考点：* 表示所有列，但实际应用中需避免滥用以减少数据量。
查询指定列：
```
SELECT 列1, 列2 FROM 表名;
```
示例：SELECT 学号, 姓名 FROM 学生;考点：明确指定列可提高查询效率，避免冗余数据。
别名（AS）：
```
SELECT 列 AS 新列名 FROM 表名;
```
示例：SELECT 姓名 AS 学生姓名 FROM 学生;考点：AS 可省略，但增强可读性（如 SELECT 姓名学生姓名）。
去重（DISTINCT）：
```
SELECT DISTINCT 列 FROM 表名;
```
示例：SELECT DISTINCT 部门 FROM 员工;考点：DISTINCT 仅对指定列去重，需与聚合函数区分。

条件查询（WHERE）

作用：筛选满足条件的记录。 常用运算符：

比较运算符：=、!=、<>、>、<、>=、<=。
逻辑运算符：AND、OR、NOT。
范围查询：BETWEEN ... AND ...。
模糊匹配：LIKE（结合通配符 % 和 _）。

1. 单条件与多条件

-- 单条件
SELECT * FROM 表名 WHERE 列 = 值;

-- 多条件
SELECT * FROM 表名
WHERE 列1 = 值1 AND 列2 > 值2
OR 列3 IS NULL;

示例：

SELECT * FROM 学生 WHERE 年龄 = 20;
SELECT * FROM 员工 WHERE 工资 > 10000 AND 部门 = '技术部';

2. 范围查询（BETWEEN）

SELECT * FROM 表名
WHERE 列 BETWEEN 值1 AND 值2;  -- 包含边界值

示例：SELECT * FROM 学生 WHERE 年龄 BETWEEN 18 AND 22;

3. 模糊查询（LIKE）

SELECT * FROM 表名
WHERE 列 LIKE '模式';

%：匹配任意字符（0 个或多个）。
_：匹配单个字符。示例：
SELECT * FROM 学生 WHERE 姓名 LIKE '张%'; -- 查询姓“张”的学生。
SELECT * FROM 商品 WHERE 名称 LIKE 'A__'; -- 查询以“A”开头且长度为 3 的名称。

聚合函数与分组（GROUP BY/HAVING）

作用：对数据进行分组统计。 常用聚合函数：

函数	作用	示例
`COUNT(*)`	统计总行数	`SELECT COUNT(*) FROM 学生`
`SUM(列)`	求和	`SELECT SUM(销售额) FROM 销售`
`AVG(列)`	计算平均值	`SELECT AVG(年龄) FROM 学生`
`MAX(列)`	取最大值	`SELECT MAX(成绩) FROM 考试`
`MIN(列)`	取最小值	`SELECT MIN(价格) FROM 商品`

1. 分组查询（GROUP BY）

SELECT 分组列, 聚合函数(列)
FROM 表名
GROUP BY 分组列
[HAVING 条件];

示例：

统计各部门平均工资

SELECT 部门, AVG(工资) AS 平均工资
FROM 员工
GROUP BY 部门;

过滤分组结果（HAVING）

SELECT 部门, COUNT(*) AS 人数
FROM 员工
GROUP BY 部门
HAVING 人数 > 5;  -- 过滤员工数超过5人的部门

连接查询（JOIN）

作用：合并多表数据。 常见连接类型：

连接类型	语法	说明
内连接（INNER JOIN）	`ON 条件`	返回两个表中满足条件的匹配行。
左连接（LEFT JOIN）	`LEFT JOIN ... ON 条件`	返回左表所有行，右表匹配则返回，否则为 NULL。
右连接（RIGHT JOIN）	`RIGHT JOIN ... ON 条件`	返回右表所有行，左表匹配则返回，否则为 NULL。
全连接（FULL JOIN）	`FULL JOIN ... ON 条件`	返回两个表所有行，不匹配则对应列为 NULL（部分数据库不支持）。

1. 内连接（INNER JOIN）

SELECT 学生.学号, 课程.课程名, 成绩
FROM 学生
INNER JOIN 选课 ON 学生.学号 = 选课.学号
INNER JOIN 课程 ON 选课.课程号 = 课程.课程号;

2. 左连接（LEFT JOIN）

SELECT 表1.列, 表2.列
FROM 表1
LEFT JOIN 表2
ON 表1.关联列 = 表2.关联列;

SELECT 学生.学号, 学生.姓名, 选课.课程号
FROM 学生
LEFT JOIN 选课 ON 学生.学号 = 选课.学号;  -- 包含未选课的学生

子查询（Subquery）

作用：嵌套查询实现复杂条件。

-- 查询选修过课程ID为 'C001' 的学生
SELECT 姓名
FROM 学生
WHERE 学号 IN (SELECT 学号 FROM 选课 WHERE 课程ID = 'C001');

-- 查询比平均工资高的员工
SELECT *
FROM 员工
WHERE 工资 > (SELECT AVG(工资) FROM 员工);

排序与分页（ORDER BY/LIMIT）

1. 排序（ORDER BY）

SELECT * FROM 表名
ORDER BY 列 ASC/DESC;  -- ASC升序（默认），DESC降序

SELECT * FROM 学生
ORDER BY 年龄 DESC, 姓名 ASC;  -- 先按年龄降序，再按姓名升序

2. 分页（LIMIT/OFFSET）

MySQL/PostgreSQL

SELECT * FROM 表名
LIMIT 偏移量, 行数;  -- 如 LIMIT 0, 10 表示第1页，每页10条

SQL Server

SELECT TOP 行数 * FROM 表名
WHERE 条件 NOT IN (SELECT TOP 偏移量 * FROM 表名);

高级查询技巧

1. 常见表表达式（CTE）

WITH 临时表名 AS (子查询)
SELECT * FROM 临时表名;

WITH 高薪员工 AS (
  SELECT * FROM 员工 WHERE 工资 > 20000
)
SELECT 部门, COUNT(*) AS 高薪人数
FROM 高薪员工
GROUP BY 部门;

2. 窗口函数（Window Functions）

SELECT 列,
       SUM(列) OVER (PARTITION BY 分组列) AS 累计值
FROM 表名;

SELECT 学号, 课程号, 成绩,
       AVG(成绩) OVER (PARTITION BY 学号) AS 学生平均分
FROM 选课;

3. 联合查询（UNION/UNION ALL）

SELECT 列 FROM 表1
UNION [ALL]
SELECT 列 FROM 表2;  -- 去重，UNION ALL保留所有行

INSERT（插入数据）

基础语法

INSERT INTO 表名 (列1, 列2, ...)
VALUES (值1, 值2, ...);

常考考点：
- 默认值/NULL：未指定列时需允许 NULL 或设置默认值。
- 批量插入：INSERT INTO 表A SELECT * FROM 表B。

UPDATE（更新数据）

基础语法

UPDATE 表名
SET 列1 = 新值, 列2 = 新值
WHERE 条件;

常考考点：
- WHERE 条件：必须明确条件，否则会更新全表。
- 自增字段：若表有自增主键，需谨慎更新以避免冲突。

DELETE（删除数据）

基础语法：
```
DELETE FROM 表名
WHERE 条件;
```
常考考点：
- 外键约束：删除主表数据前需先删除从表关联数据，或设置 ON DELETE CASCADE。
- 全表删除：DELETE FROM 表名 删除所有数据，但保留表结构。

字符串与日期函数

字符串函数

函数	作用	示例
`CONCAT(列1, 列2)`	字符串拼接	`SELECT CONCAT(姓, 名) AS 全名 FROM 员工`
`SUBSTRING(列, 起始, 长度)`	截取子字符串	`SELECT SUBSTRING(电话, 4, 4) FROM 客户`
`UPPER(列)`	转大写	`SELECT UPPER(城市) FROM 订单`
`LOWER(列)`	转小写	`SELECT LOWER(邮箱) FROM 用户`

日期函数

函数	作用	示例
`CURRENT_DATE()`	获取当前日期	`SELECT CURRENT_DATE()`
`DATE_FORMAT(日期, 格式)`	格式化日期	`SELECT DATE_FORMAT(出生日期, '%Y-%m-%d') FROM 学生`
`DATEDIFF(日期1, 日期2)`	计算日期差	`SELECT DATEDIFF('2023-01-01', '2022-01-01')`

四、授权与收回（DCL 核心考点）

1. GRANT（授权）

基础语法

GRANT 权限1, 权限2
ON 对象类型.对象名
TO 用户/角色
[WITH GRANT OPTION];

常考权限类型
- 数据操作权限：SELECT, INSERT, UPDATE, DELETE。
- 数据定义权限：CREATE, DROP, ALTER。
- 全部权限：ALL PRIVILEGES。

常考考点

列级权限：GRANT UPDATE(列名) ON 表名 TO 用户。
转授权：WITH GRANT OPTION 允许被授权用户再次授权。
对象范围
- ON 表名：对指定表授权。
- ON *.*：对数据库所有对象授权。

示例

-- 授予用户UserA对表employees的查询权限
GRANT SELECT ON employees TO UserA;

-- 授予角色Analyst对所有表的全部权限
GRANT ALL PRIVILEGES ON *.* TO Analyst;

-- 列级权限：仅允许更新price列
GRANT UPDATE(price) ON sales TO UserB;

2. REVOKE（收回权限）

基础语法

REVOKE 权限1, 权限2
ON 对象类型.对象名
FROM 用户/角色;

常考考点

收回转授权权限：

需明确指定GRANT OPTION

REVOKE GRANT OPTION FOR INSERT ON projects FROM UserB;

对象范围：需与 GRANT 时指定的范围一致。

示例：

-- 撤销UserA对表employees的查询权限
REVOKE SELECT ON employees FROM UserA;

-- 撤销UserB对列price的更新权限
REVOKE UPDATE(price) ON sales FROM UserB;

关系代数

运算分类

类型	运算符	描述	核心操作对象
传统集合运算	∪（并）、∩（交）、−（差）、×（笛卡尔积）	基于元组集合的行操作，要求参与运算的关系并相容（列数相同且对应属性域一致）	行（元组）
专门关系运算	σ（选择）、π（投影）、∞（连接）、÷（除）	结合行列操作，支持复杂查询逻辑	行和列（属性）

运算符速查表

运算符	名称	SQL 对应	功能描述
∪	并	UNION	合并元组，去重
−	差	EXCEPT	排除另一关系的元组
∩	交	INTERSECT	取共同元组
×	笛卡尔积	CROSS JOIN	所有元组组合
σ	选择	WHERE	筛选行
π	投影	SELECT	选择列
∞	连接	JOIN ... ON	关联表
÷	除	NOT EXISTS	包含全部匹配

传统集合运算（行操作）

2.1 并（∪）

定义：合并两个关系的元组，去除重复行。
表达式：R ∪ S = {所有属于 R 或 S 的元组}。
示例：
- 关系 R：
  A B
  1 2
  3 4
- 关系 S：
  A B
  3 4
  5 6
- R ∪ S：
  A B
  1 2
  3 4
  5 6

2.2 差（−）

定义：保留属于 R 但不属于 S 的元组。
表达式：R − S = {属于 R 但不在 S 中的元组}。
示例：
- R − S：
  A B
  1 2

2.3 交（∩）

定义：保留同时属于 R 和 S 的元组。
表达式：R ∩ S = {同时属于 R 和 S 的元组}。
示例：
- R ∩ S：
  A B
  3 4

2.4 笛卡尔积（×）

定义：生成两个关系所有元组的组合，属性数为 R+S，元组数为 R×S。
表达式：R × S = {所有 r∈R，s∈S 的组合}。
示例：
- R × S：
  A B A B
  1 2 3 4
  1 2 5 6
  3 4 3 4
  3 4 5 6

专门关系运算（行列结合）

3.1 选择（σ）

定义：从关系中筛选满足条件的元组。
表达式：σ_条件(关系)
示例：查询年龄 ≥20 的学生：σ_{年龄 ≥20}(学生表)。

3.2 投影（π）

定义：从关系中选择指定列，去重。
表达式：π_{属性 1, 属性 2}(关系)
示例：查询学生姓名和年龄：π_{姓名，年龄}(学生表)。

3.3 连接（∞）

类型	符号	描述	示例（关系 R 和 S）
等值连接	⋈_A=B	选择 R 和 S 中指定属性值相等的元组	R ⋈_R.A=S.A S
自然连接	⋈	等值连接后去掉重复属性	R ⋈ S（隐含相同属性名的等值连接）
左外连接	⟕	保留 R 所有元组，S 中无匹配的元组补 NULL	R ⟕ S
右外连接	⟖	保留 S 所有元组，R 中无匹配的元组补 NULL	R ⟖ S
全外连接	⟗	保留 R 和 S 所有元组，无匹配的元组补 NULL	R ⟗ S

自然连接与等值连接对比

对比项	自然连接	等值连接
条件	基于相同属性名的等值连接	任意属性的等值条件
结果列	去除重复属性	保留重复属性
符号	⋈	⋈_A=B

3.4 除（÷）

定义：R÷S 返回 R 中包含 S 所有属性值的元组。
表达式：R÷S = {r[X] | r∈R ∧ π_Y(S)⊆Y_x}，其中 Y 是 S 的属性，Y_x是 R 中 X 值对应的 Y 值集合。
示例：查询选修了所有课程的学生：π_{学号，课程号}(选课表) ÷ π_课程号(课程表)。
除运算步骤

投影 S 的属性：提取 S 中与 R 相同的属性列。
分组 R 的属性：按 R 中与 S 不同的属性分组。
检查包含关系：每组的象集是否包含 S 的投影。

典型题型与解题技巧

关系代数表达式书写

例题：查询年龄 ≥20 且性别为男的学生姓名和年龄。

步骤：
1. 选择条件：σ_{年龄 ≥20 ∧ 性别 =‘男’}(学生表)
2. 投影属性：π_{姓名，年龄}(步骤 1 结果)
表达式：π_{姓名，年龄}(σ_{年龄 ≥20 ∧ 性别 =‘男’}(学生表))

除运算应用

例题：查询选修了所有课程的学生学号。

步骤：
1. 提取选课表的学号和课程号：π_{学号，课程号}(选课表)
2. 提取课程表的课程号：π_课程号(课程表)
3. 执行除运算：步骤 1 ÷ 步骤 2
表达式：π_{学号，课程号}(选课表) ÷ π_课程号(课程表)

连接类型判断

例题：判断以下连接类型：

R ⟕ S：左外连接，保留 R 所有元组。
R ⟖ S：右外连接，保留 S 所有元组。
R ⋈ S：自然连接，隐含相同属性的等值连接。

关系代数与 SQL 对应

关系代数运算	SQL 语句示例
选择	SELECT * FROM 表 WHERE 条件；
投影	SELECT 属性 1, 属性 2 FROM 表；
自然连接	SELECT * FROM R JOIN S USING (公共属性);
除	SELECT 学号 FROM 选课表 AS A WHERE NOT EXISTS (SELECT _ FROM 课程表 AS B WHERE NOT EXISTS (SELECT _ FROM 选课表 AS C WHERE C. 学号 = A. 学号 AND C. 课程号 = B. 课程号));

关系数据库的规范化

核心概念

规范化的核心目标是通过分解关系模式，消除数据冗余和操作异常（如插入、删除、更新异常），提高数据一致性。核心工具包括函数依赖和范式：

函数依赖：属性间的决定关系，如学号→姓名。分为完全依赖、部分依赖和传递依赖。
范式：关系模式的规范化等级，包括 1NF、2NF、3NF、BCNF 等，等级越高约束越严格。

函数依赖基础

基本定义

函数依赖（FD）：若属性 X 的值确定时，属性 Y 的值唯一确定，记为X→Y。
候选键：能唯一标识元组的最小属性集，如学生表中的学号。
主属性：包含在任一候选键中的属性；非主属性：不包含在任何候选键中的属性。

依赖类型对比

类型	定义	示例
完全函数依赖	Y 依赖于 X 的全部属性，且 X 的任何真子集都不能决定 Y	`(学号,课程号)→成绩`（成绩完全依赖于组合键）
部分函数依赖	Y 依赖于 X 的部分属性	`(学号,课程号)→姓名`（姓名仅依赖学号）
传递函数依赖	X→Y 且 Y→Z（Y 不决定 X），则 Z 传递依赖于 X	`学号→系名，系名→系主任` → `学号→系主任`

各级范式详解

第一范式（1NF）

定义：所有属性不可再分，确保每个单元格为原子值。
条件：
- 关系模式中的每个属性均为原子类型。
- 无重复组或多值属性。
示例：
- 不符合 1NF：关系学生(学号,姓名,联系方式(电话,邮箱))（联系方式可拆分）。
- 符合 1NF：关系学生(学号,姓名,电话,邮箱)。

第二范式（2NF）

定义：在 1NF 基础上，消除非主属性对主码的部分函数依赖。
条件：
- 关系模式满足 1NF。
- 所有非主属性完全依赖于主码。
示例：
- 不符合 2NF：关系选课(学号,课程号,课程名,成绩)，因课程号→课程名存在部分依赖。
- 分解后：
  - 选课(学号,课程号,成绩)（完全依赖）。
  - 课程(课程号,课程名)（消除部分依赖）。

第三范式（3NF）

定义：在 2NF 基础上，消除非主属性对主码的传递函数依赖。
条件：
- 关系模式满足 2NF。
- 所有非主属性不传递依赖于主码。
示例：
- 不符合 3NF：关系学生(学号,姓名,系名,系主任)，因学号→系名→系主任存在传递依赖。
- 分解后：
  - 学生(学号,姓名,系名)。
  - 系(系名,系主任)（消除传递依赖）。

BCNF（Boyce-Codd 范式）

定义：在 3NF 基础上，消除主属性对候选键的部分和传递依赖。
条件：
- 关系模式满足 3NF。
- 所有决定因素（X）均为候选键。
示例：
- 不符合 BCNF：关系教师(教师编号,课程号,学生)，若(教师编号,课程号)→学生且学生→课程号，则学生非候选键，存在主属性依赖。
- 分解后：
  - 授课(教师编号,课程号)。
  - 学生(学生,课程号)（确保所有决定因素为候选键）。

范式层次关系

范式等级从低到高依次为：1NF ⊂ 2NF ⊂ 3NF ⊂ BCNF。每一级范式均需满足前一级的所有条件。

范式转换流程

转换步骤

1NF→2NF：拆分部分依赖的非主属性至新表。
2NF→3NF：拆分传递依赖的非主属性至新表。
3NF→BCNF：拆分主属性依赖的决定因素至新表。

分解原则

无损连接：分解后的关系通过自然连接可恢复原关系。
保持依赖：分解后的关系保留原函数依赖。
示例：
- 原关系：S-L-C(Sno, Sdept, SLOC, Cno, Grade)（SLOC 为学生宿舍楼）。
- 问题：存在部分依赖Sno→Sdept和传递依赖Sdept→SLOC。
- 分解步骤：
  1. 拆分为S-C(Sno, Cno, Grade)和S-L(Sno, Sdept, SLOC)（消除部分依赖）。
  2. 进一步拆分为S-D(Sno, Sdept)和D-L(Sdept, SLOC)（消除传递依赖）。

典型题型

范式判断

例题：判断关系R(A,B,C,D,E)，函数依赖F={A→B, B→C, C→D, D→E}满足几范式？解析：

1NF：属性原子化，满足。
2NF：候选键为A，非主属性B、C、D、E均完全依赖A，满足。
3NF：存在传递依赖A→B→C→D→E，不满足。结论：关系R满足 2NF，不满足 3NF。

模式分解

例题：分解关系S(PNO, PNAME, QTY, PRICE, DATE, CUST_NAME, CUST_ADDR)至 3NF。步骤：

确定函数依赖：(PNO, DATE)→QTY, PRICE；PNO→PNAME；CUST_NAME→CUST_ADDR。
消除部分依赖：
- 产品(PNO, PNAME, PRICE)。
- 销售(PNO, DATE, QTY)。
- 顾客(CUST_NAME, CUST_ADDR)。
消除传递依赖：已满足 3NF。 分解结果：产品、销售、顾客三张表。

依赖保持与无损连接

例题：关系R(A,B,C,D)，函数依赖F={A→B, B→C, C→D}，分解为R1(A,B)、R2(B,C)、R3(C,D)是否保持依赖？解析：

依赖保持：A→B在R1，B→C在R2，C→D在R3，所有依赖均保留，保持依赖。
无损连接：通过自然连接可恢复原关系，满足无损连接。结论：分解保持依赖且无损。

题型类型	例题描述	解析要点
范式判断	判断关系`R(A,B,C,D,E)`，函数依赖`F={A→B, B→C, C→D, D→E}`满足几范式？	逐层检查 1NF、2NF、3NF 条件，重点分析部分依赖和传递依赖。
模式分解	分解关系`S(PNO, PNAME, QTY, PRICE, DATE, CUST_NAME, CUST_ADDR)`至 3NF。	识别函数依赖，拆分部分依赖和传递依赖的属性至新表，确保无损连接和保持依赖。
依赖保持与无损连接	关系`R(A,B,C,D)`分解为`R1(A,B)`、`R2(B,C)`、`R3(C,D)`是否保持依赖？	检查所有函数依赖是否保留在分解后的关系中，并验证自然连接能否恢复原关系。

控制功能

事务管理

ACID 特性

原子性（Atomicity）：事务中的操作要么全部执行，要么全部不执行。例如，转账操作中扣款和入账必须同时成功或失败。
一致性（Consistency）：事务执行前后，数据库从一个合法状态转换到另一个合法状态。例如，转账前后账户总金额不变。
隔离性（Isolation）：并发执行的事务之间互不干扰。例如，多个用户同时修改同一数据时，通过锁机制保证数据一致性。
持久性（Durability）：事务提交后，数据修改永久生效。例如，断电后已提交的转账记录不会丢失。

事务状态转换

活动状态 → 部分提交状态 → 提交状态（成功）
活动状态 → 失败状态 → 中止状态（回滚）

活动状态：事务开始后的初始状态。
部分提交状态：最后一条操作执行完毕，但未提交。
提交状态：事务成功完成，数据持久化。
失败状态：事务执行中出现错误。
中止状态：事务回滚，数据恢复到初始状态。

事务调度

串行调度：事务依次执行，结果唯一。
并发调度：事务交替执行，需保证可串行化（结果与某一串行调度一致）。
可恢复调度：事务读取的数据必须来自已提交的事务，避免脏读。

并发控制

并发问题

问题类型	描述	示例
丢失修改	两个事务同时修改同一数据，后提交的覆盖先提交的结果	事务 A 和 B 同时修改库存，最终库存值错误
脏读	事务读取到未提交的中间数据	事务 A 修改数据后未提交，事务 B 读取到该数据，随后 A 回滚，B 读取的数据无效
不可重复读	同一事务内多次读取同一数据，结果不一致	事务 A 读取数据后，事务 B 修改并提交，A 再次读取时结果不同
幻读	事务读取符合条件的记录数变化	事务 A 查询得到 10 条记录，事务 B 插入新记录后，A 再次查询得到 12 条记录

封锁协议

协议等级	加锁规则	解决的问题
一级协议	修改数据前加 X 锁，事务结束释放	丢失修改
二级协议	一级协议 + 读取数据前加 S 锁，读完释放	丢失修改、脏读
三级协议	一级协议 + 读取数据前加 S 锁，事务结束释放	丢失修改、脏读、不可重复读

两阶段锁协议（2PL）

扩展阶段：事务可申请锁，但不能释放锁。
收缩阶段：事务只能释放锁，不能申请新锁。
特点：确保可串行化调度，但可能导致死锁。

隔离级别

隔离级别	描述	解决的问题
READ UNCOMMITTED	允许读取未提交数据	仅避免丢失修改
READ COMMITTED	只能读取已提交数据	丢失修改、脏读
REPEATABLE READ	事务内多次读取结果一致	丢失修改、脏读、不可重复读
SERIALIZABLE	最高级别，强制事务串行执行	所有并发问题

数据库恢复

恢复技术

数据转储：
- 静态转储：转储期间不允许读写操作。
- 动态转储：转储期间允许读写，需结合日志文件。
- 海量转储：备份全部数据。
- 增量转储：备份自上次转储后更新的数据。
日志文件：记录事务操作，用于恢复时的 UNDO 和 REDO。

检查点机制

设置检查点：定期将内存数据刷新到磁盘，记录活动事务。
恢复步骤：
- 反向扫描日志，找到最后一个检查点。
- 对检查点后提交的事务执行 REDO（重做）。
- 对检查点后未提交的事务执行 UNDO（回滚）。

故障恢复

故障类型	恢复方法
事务故障	反向扫描日志，对未提交事务执行 UNDO
系统故障	对未提交事务执行 UNDO，对已提交但未写入磁盘的事务执行 REDO
介质故障	重装数据库备份，结合日志文件执行 REDO

完整性约束

约束类型

实体完整性：主键不能为空或重复。
- 示例：CREATE TABLE 学生 (学号 INT PRIMARY KEY, 姓名 VARCHAR(50));
参照完整性：外键值必须存在于被参照表的主键中。
- 示例：CREATE TABLE 选课 (学号 INT, 课程号 INT, FOREIGN KEY (学号) REFERENCES 学生(学号));
用户定义完整性：自定义约束条件。
- 示例：ALTER TABLE 学生 ADD CONSTRAINT 年龄 CHECK (年龄 BETWEEN 18 AND 30);

触发器

作用：自动执行特定操作，确保复杂业务规则。

示例：

CREATE TRIGGER 库存检查 AFTER INSERT ON 订单
FOR EACH ROW
BEGIN
  UPDATE 商品 SET 库存 = 库存 - NEW.数量 WHERE 商品ID = NEW.商品ID;
END;

安全性控制

访问控制

用户认证：通过用户名 / 密码验证身份。
授权管理：
- 授予权限：GRANT SELECT, INSERT ON 学生 TO 'user1'@'localhost';
- 回收权限：REVOKE INSERT ON 学生 FROM 'user1'@'localhost';
角色管理：将权限赋予角色，用户通过角色获取权限。

视图与审计

视图：限制用户访问特定数据。
- 示例：CREATE VIEW 学生信息 AS SELECT 学号, 姓名 FROM 学生;
审计：记录用户操作，用于追踪和安全分析。

数据加密

静态加密：对存储的数据加密（如透明数据加密 TDE）。
动态加密：对传输中的数据加密（如 SSL/TLS）。

典型题型

事务调度判断例题：事务 T1 和 T2 的操作序列如下，是否为可串行化调度？ T1: R(A), W(A), R(B), W(B) T2: R(B), W(B), R(A), W(A) 解析：冲突操作顺序不一致（T1 的 W (B) 与 T2 的 R (B) 冲突），不可串行化。

封锁协议应用例题：若事务需要读取数据 A 并修改数据 B，应采用几级封锁协议？解析：三级封锁协议，对 A 加 S 锁（事务结束释放），对 B 加 X 锁（事务结束释放），防止不可重复读和丢失修改。

恢复步骤计算例题：日志文件如下，检查点后发生故障，需恢复哪些事务？

T1 START
T1 W(A)
T2 START
T2 W(B)
CHECKPOINT (T1, T2)
T3 START
T3 W(C)
T1 COMMIT
T3 COMMIT 解析：T1 已提交（REDO），T2 未提交（UNDO），T3 已提交（REDO）。

知识点	内容概述
时间复杂度定义	衡量算法运行时间随输入规模增长的趋势，用大 O 符号表示。通常关注最坏情况下的复杂度。
空间复杂度定义	衡量算法运行所需额外存储空间随输入规模的增长趋势，同样用大 O 符号表示。
计算规则	1. 加法规则：总复杂度取最大项（如 T(n)=O(f(n))+O(g(n)) → O(max(f(n),g(n)))）。 2. 乘法规则：嵌套操作复杂度相乘（如 T(n)=O(f(n))×O(g(n)) → O(f(n)*g(n))）。
渐进符号（大 O）	忽略低阶项和系数，保留最高阶项。例如：T(n)=2n²+3n+5 → O(n²)。
主定理（Master Theorem）	用于求解递归式的时间复杂度，适用于形如 T(n)=aT(n/b)+f(n) 的递归方程。

考点归纳

考点	核心内容
常见时间复杂度等级	O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
时间复杂度计算步骤	1. 确定基本操作（如循环内耗时最多的语句）。 2. 计算基本操作的执行次数。 3. 用大 O 表示法简化。
空间复杂度计算重点	区分算法所需额外空间（如递归栈、辅助数组）与输入数据本身的存储空间。
递归算法复杂度分析	时间复杂度：递归次数 × 每次递归的操作次数。空间复杂度：递归深度 × 每次递归的辅助空间。

常见算法复杂度表

算法名称	时间复杂度（最坏情况）	空间复杂度	说明
直接访问数组元素	O(1)	O(1)	常数时间，无需额外空间。
顺序查找（线性查找）	O(n)	O(1)	遍历数组查找元素。
二分查找	O(log n)	O(1)	有序数组的对数时间查找。
冒泡排序	O(n²)	O(1)	简单排序，原地操作。
快速排序	O(n²)	O(log n)	平均 O(n log n)，最坏 O(n²)（递归栈）。
归并排序	O(n log n)	O(n)	需额外空间合并子数组。
堆排序	O(n log n)	O(1)	原地排序，基于堆结构。
插入排序	O(n²)	O(1)	适合小规模或部分有序数据。
斐波那契数列（递归）	O(2ⁿ)	O(n)	指数时间，递归栈深度为 n。
矩阵乘法（三重循环）	O(n³)	O(1)	逐元素计算的朴素方法。
Dijkstra 算法（邻接表）	O((V+E) log V)	O(V+E)	优先队列实现，V 为顶点数，E 为边数。

复杂度等级对比

复杂度等级	示例算法/操作	输入规模 n 的适用范围
O(1)	数组访问、哈希表查询	任何规模，时间恒定。
O(log n)	二分查找、堆操作	n=1e9 时，log2(n)≈30，效率极高。
O(n)	线性查找、单层循环	n=1e6 时，可处理秒级。
O(n log n)	快速排序、归并排序	n=1e7 时，仍可接受。
O(n²)	冒泡排序、简单矩阵乘法	n≤1e4 时，可能超时。
O(n³)	三重循环、朴素矩阵乘法	n≤1e3 时，可能超时。
O(2ⁿ)	子集枚举、斐波那契递归	n≤20 时，可能超时；n=30 时，不可行。
O(n!)	全排列生成	n≤12 时，可能超时；n=20 时，不可行。

关键注意事项

时间复杂度优先级：在算法选择中，优先考虑低阶复杂度（如 O(n log n)优于 O(n²)）。
空间与时间的权衡：例如，哈希表（空间换时间）或分治算法（可能增加空间需求）。
递归的隐式成本：递归可能导致额外空间开销（如栈深度）。
实际优化：常数系数和低阶项在小规模数据中可能影响性能，但复杂度分析关注趋势。

线性结构

线性结构的核心概念

1. 定义与特点

定义：数据元素之间存在一对一的线性关系，元素按顺序排列，每个元素有唯一前驱和后继（首尾元素除外）。
核心特点：
- 有序性：元素按逻辑顺序排列。
- 唯一性：首元素无前驱，尾元素无后继。
- 直接关系：相邻元素直接关联。

2. 常见线性结构类型

线性表：最基础的线性结构，包含顺序表和链表。
栈（Stack）：后进先出（LIFO），仅允许在栈顶操作（如递归、表达式求值）。
队列（Queue）：先进先出（FIFO），队尾入队、队头出队（如任务调度、BFS）。
数组：固定大小的线性结构，支持随机访问。
字符串：字符序列，属于线性表的特殊形式。

存储方式对比与关键考点

1. 存储方式选择

存储方式	特点	适用场景	常考对比
顺序存储	内存连续，支持随机访问（`data[i]`），插入/删除需移动元素，动态扩容可能耗时	数据量固定或较少插入/删除操作	与链式存储对比：插入/删除效率低，但访问快
链式存储	动态分配内存，插入/删除快（改指针即可），但访问需遍历，空间利用率较低	频繁插入/删除操作，数据量动态变化	与顺序存储对比：访问慢，但插入/删除快

2. 线性表操作复杂度

操作类型	顺序表	单链表	考点关联
插入/删除	平均 `O(n)`	平均 `O(1)`（需找到位置）	考察存储方式选择：频繁操作选链表，静态数据选顺序表
查找	`O(1)`（直接索引）	`O(n)`（需遍历）	考察时间复杂度分析：顺序表随机访问快，链表需遍历

栈与队列的核心对比与应用

1. 栈（Stack）与队列（Queue）的区别

对比维度	栈（Stack）	队列（Queue）	常考题型
操作原则	后进先出（LIFO）	先进先出（FIFO）	概念对比题：区分 LIFO 与 FIFO 的应用场景
典型应用	递归、表达式求值、函数调用栈、括号匹配	任务调度、BFS、消息队列、缓存管理	应用实例题：DFS 用栈，BFS 用队列
存储实现	数组或链表实现，需维护栈顶指针	数组或链表实现，需维护队头/队尾指针	循环队列的溢出条件（`front = (rear + 1) % maxSize`）

2. 栈与队列的实现细节

栈：通常用数组或链表实现，需注意栈满/栈空的判断。
队列：循环队列需处理“假溢出”，需掌握其溢出条件（如 front = (rear + 1) % maxSize）。

线性结构的典型应用与复杂度分析

1. 线性结构在算法中的应用

栈：
- 递归：函数调用栈的底层实现。
- 表达式求值：用栈匹配括号或计算逆波兰表达式。
队列：
- BFS：通过队列按层次遍历图或树。
- 任务调度：操作系统中任务队列的管理。

2. 常考复杂度分析题

题目：顺序表和链表在插入操作上的时间复杂度有何差异？
- 答案：顺序表需移动元素，复杂度 O(n)；链表仅改指针，复杂度 O(1)。
题目：深度优先搜索（DFS）和广度优先搜索（BFS）分别使用什么结构？
- 答案：DFS 用栈（LIFO），BFS 用队列（FIFO）。

关键注意事项与易错点

线性结构与非线性结构的区别：
- 线性结构：元素间一对一（如线性表、栈、队列）。
- 非线性结构：元素间多对多（如树、图）。
- 易错点：将树或图误认为线性结构。
存储方式的权衡：
- 顺序表：适合静态数据或需频繁访问的场景（如数据库索引）。
- 链表：适合动态数据或频繁插入/删除的场景（如链表实现 LRU 缓存）。
栈与队列的隐含要求：
- 栈的操作仅限栈顶，队列的操作仅限队头/队尾。
- 循环队列的溢出条件需特别注意（避免“假溢出”）。

总结：线性结构对比表

结构类型	特点	存储方式	典型应用	时间复杂度（平均）
线性表	有序、一对一关系	顺序/链式	数据存储、排序算法	查找 `O(1)/O(n)`，插入/删除 `O(n)/O(1)`
栈	LIFO	数组/链表	递归、表达式求值	入栈/出栈 `O(1)`
队列	FIFO	数组/链表/循环队列	任务调度、BFS	入队/出队 `O(1)`
顺序表	连续内存，支持随机访问	顺序存储	静态数据存储	插入/删除 `O(n)`
链表	动态分配，插入/删除高效	链式存储	动态操作场景	查找 `O(n)`

数组，矩阵，广义表

数组（Array）

1. 核心概念

定义：多个相同类型的元素按有序方式排列的集合，元素通过下标访问。
特点：
- 固定长度：定义后不可动态扩展或缩小（需重新分配内存）。
- 连续存储：内存中连续存放，支持随机访问（通过下标直接定位）。
- 多维特性：可以是高维结构（如二维数组、三维数组），但底层存储为一维线性结构。

2. 存储方式

行优先（Row-major Order）：
- 多维数组按行展开为一维数组。例如，二维数组 A[m][n] 中，A[i][j] 的地址计算公式为： LOC(A[i][j]) = LOC(A[0][0]) + (i * n + j) * L（L 为元素大小）。
- C/C++/Java 等语言默认按行优先存储。
列优先（Column-major Order）：
- 多维数组按列展开，如 A[i][j] 的地址为 LOC(A[i][j]) = LOC(A[0][0]) + (j * m + i) * L。

3. 考点与应用

多维数组地址计算：如二维数组 A[3][4] 中，A[1][2] 的地址为 base + (1×4 + 2) × L。
特殊矩阵的压缩存储：
- 对称矩阵：只存储下三角（含对角线）元素，空间复杂度降为 n(n+1)/2。
- 三角矩阵：上/下三角全为常数，存储非常数区域。
- 对角矩阵：非零元素集中在主对角线附近，按行或列压缩存储。

矩阵（Matrix）

1. 分类与存储

特殊矩阵：
- 对称矩阵：满足 A[i][j] = A[j][i]，存储下三角部分即可。
- 三角矩阵：
  - 上三角矩阵：下三角（不含对角线）全为常数。
  - 下三角矩阵：上三角（不含对角线）全为常数。
- 对角矩阵：非零元素集中在主对角线附近（如三对角矩阵）。
稀疏矩阵：
- 定义：非零元素远少于零元素，且分布无规律。
- 压缩存储方法：
  - 三元组顺序表：存储(行, 列, 值)，如 trimat[k][0] 表示第 k 个非零元素的值。
  - 行逻辑链接表：增加行索引数组，快速定位某行的非零元素。
  - 十字链表：每个非零元素用节点表示，包含行、列、值，以及行指针和列指针。

2. 考点与应用

特殊矩阵的地址计算：
如三对角矩阵第 i 行的带状区域首元素下标为：
- i=1 时为 0；
- i>1 时为 2 + (i-2)*3。
稀疏矩阵的三元组操作：如稀疏矩阵的转置、加法等需基于三元组顺序表实现。

广义表（Generalized List）

1. 核心概念

定义：线性表的扩展，元素可以是原子（不可分数据）或子表（另一个广义表）。
关键术语：
- 长度：表中最外层元素的个数（如 (a, (b, c)) 的长度为 2）。
- 深度：括号嵌套的最大层数（如 (a, (b, (c))) 的深度为 3）。

2. 存储方式

链式存储：

节点类型：
- 原子节点：包含 tag=0 和原子值。
- 表节点：包含 tag=1、hp（指向表头）和 tp（指向表尾）。

C 语言实现：

typedef struct GLNode {
    int tag;          // 0:原子，1:子表
    union {
        char atom;    // 原子值
        struct {
            struct GLNode *hp, *tp; // 表头、表尾指针
        } ptr;
    } un;
} GLNode, *GList;

存储特点：
- 无法用顺序存储（因嵌套结构复杂）。
- 链式结构灵活，适合动态嵌套。

3. 考点与应用

深度与长度计算：如广义表 (a, (b, (c))) 的长度为 2，深度为 3。
广义表操作：
- 取表头：GetHead(L) 返回第一个元素（原子或子表）。
- 取表尾：GetTail(L) 返回剩余元素组成的表。
区别于线性表：线性表元素只能是原子，广义表允许嵌套子表。

对比总结

结构	元素类型	存储方式	特点	典型应用
数组	同类型、固定长度	顺序存储（行/列优先）	随机访问高效，插入/删除低效	多维数据存储、矩阵运算
矩阵	数值型	特殊矩阵压缩存储，稀疏矩阵三元组/链表	节省内存空间，支持高效运算	科学计算、图像处理
广义表	原子或子表	链式存储（带 tag 节点）	支持嵌套结构，灵活但操作复杂	人工智能、符号计算

高频考题示例

数组地址计算：题目：二维数组 A[5][6] 按行优先存储，首地址为 100，每个元素占 4B，求 A[3][4] 的地址。答案：100 + (3×6 + 4)×4 = 100 + 88×4 = 452。
广义表深度计算：题目：广义表 (a, (b, (c, d))) 的深度是多少？答案：3（括号嵌套层数为 3）。
稀疏矩阵三元组操作：题目：稀疏矩阵的三元组顺序表中，第 k 个元素的行标如何表示？答案：trimat[k][1]（假设三元组结构为 [值, 行, 列]）。

关键注意事项

数组与广义表的区别：数组元素类型固定且无嵌套；广义表允许嵌套子表，结构灵活。
特殊矩阵压缩的适用场景：对称、三角、对角矩阵适合压缩，而稀疏矩阵需用三元组或链表。
广义表的链式存储实现：必须区分原子节点和表节点，通过 tag 标志域控制。

树

以下是关于数据结构中树的核心知识点总结，结合知识库内容，以清晰的结构化形式呈现，突出重点、对比和高频考点：

树的基本概念

定义

树（Tree）：
由n 个节点组成的有限集合，满足以下条件：
- 有且仅有一个根节点（Root），无父节点。
- 其余节点分为互不相交的子树，每个子树本身也是一棵树。
特点：
- 非线性结构，层次分明。
- 节点间存在一对一或多对多的层次关系。

核心术语

术语	定义	示例
节点（Node）	树的基本单位，包含数据元素和指向子节点的指针。	A、B、C 等节点构成树的结构。
根节点（Root）	树的顶层节点，无父节点。	树结构中的 A 节点。
叶子节点（Leaf）	度为 0 的节点，无子节点。	B、C 等末端节点。
父节点（Parent）	有子节点的节点。	A 是 B 的父节点。
子节点（Child）	直接连接到父节点的节点。	B 是 A 的子节点。
度（Degree）	节点的子节点数目；树的度是所有节点度的最大值。	A 的度为 3，树的度为 3。
层次（Level）	根为第 1 层，子节点逐层递增。	A 为 1 层，B 为 2 层。
高度（Height）	根节点到最远叶子节点的路径长度（边数+1）。	树的高度为 4 层。

树的分类

按节点分支数量分类

类型	特点	应用场景
二叉树	每个节点最多 2 个子节点（左、右）。	表达式求值、搜索、编译器语法分析
多叉树	节点可有任意子节点数。	文件系统、组织架构表示
满二叉树	所有非叶子节点都有 2 个子节点，且叶子节点在同一层。	完全对称的树结构
完全二叉树	除最后一层外，其他层满；最后一层从左到右填充。	堆结构实现
平衡二叉树	任意节点的左右子树高度差 ≤1（如 AVL 树、红黑树）。	动态数据高效查询
B/B+树	多路平衡树，每个节点存储多个键，适合磁盘存储。	数据库索引（如 MySQL）

按结构特性分类

类型	特点	示例
二叉搜索树（BST）	左子树值 < 根值 < 右子树值，中序遍历有序。	快速查找、插入、删除操作
哈夫曼树	权值大的节点离根近，用于最优编码（如数据压缩）。	Huffman 编码算法
线索二叉树	在空闲指针域存储前驱/后继节点，支持非递归遍历。	遍历优化

树的存储结构

常见存储方式

类型	结构	适用场景
双亲表示法	每个节点存储父节点索引，便于查找父节点。	父节点访问频繁的场景
孩子表示法	每个节点的孩子构成链表，便于遍历子树。	子树操作频繁的场景
孩子兄弟表示法	每个节点保存第一个孩子和下一个兄弟的指针，支持多叉树转换为二叉树。	多叉树的二叉化存储
顺序存储（数组）	仅适用于完全二叉树，通过下标计算父子关系（父节点`i`，左子`2i+1`，右子`2i+2`）。	完全二叉树的高效索引访问
链式存储	每个节点包含数据和子节点指针，灵活支持任意树结构。	动态树结构（如 AVL 树）

树的遍历方法

1. 遍历类型与实现

遍历方式	规则	示例（根 A，左 B 右 C）
前序遍历（根 → 左 → 右）	访问根，遍历左子树，遍历右子树。	A → B → C
中序遍历（左 → 根 → 右）	遍历左子树，访问根，遍历右子树。	B → A → C
后序遍历（左 → 右 → 根）	遍历左子树，遍历右子树，访问根。	B → C → A
层次遍历（广度优先）	按层次从上到下、从左到右访问。	A → B → C → D → E → F → G

2. 遍历应用

前序：复制树结构、表达式生成。
中序：二叉搜索树的有序输出。
后序：释放树资源、表达式求值。
层次遍历：文件系统目录遍历。

关键性质与公式

节点数与边数：
- 树有 N 个节点，则边数为 N-1。
完全二叉树性质：
- 若高度为 h，则节点数范围：2^(h-1) ≤ N ≤ 2^h -1。
二叉树遍历唯一性：
- 前序+中序可唯一确定树结构；
- 后序+中序可唯一确定树结构；
- 前序+后序无法唯一确定（除非是满二叉树）。

高频考点与典型题型

1. 树的度与高度计算

例题：某树的度为 3，有 9 个叶子节点，5 个度为 2 的节点，求度为 3 的节点数。
答案：
设度为 3 的节点数为 x，根据公式：
叶子 = 1 + 2×度2节点 + 3×度3节点 → 9 = 1 + 2×5 + 3x → x=2。

2. 二叉树性质应用

例题：一棵完全二叉树有 100 个节点，求其高度。
答案：
完全二叉树高度 h 满足：2^(h-1) ≤ 100 ≤ 2^h -1 → h=7（2^6=64，27-1=127）。

3. 遍历序列还原树结构

例题：已知前序序列A B D E C F，中序序列D B E A F C，画出二叉树。
步骤：
1. 前序首节点 A 为根；
2. 中序中 A 左边为左子树（D B E），右边为右子树（F C）；
3. 递归构造左右子树。

常见易错点与陷阱

树与森林的区别：
- 森林：m 棵互不相交的树的集合。
完全二叉树与满二叉树混淆：
- 满二叉树一定是完全二叉树，但反之不成立。
树的存储结构选择：
- 顺序存储仅适用于完全二叉树，动态结构优先链式存储。
遍历顺序混淆：
- 中序遍历需先访问左子树，再根，再右子树（易与前序混淆）。

总结对比表

概念	树	二叉树	完全二叉树
节点限制	无限制	≤2 个子节点	必须完全填充除最后一层外的层
存储方式	链式/孩子兄弟表示法	链式/顺序存储（完全二叉树适用）	顺序存储最优
遍历方法	前序、中序、后序、层次	前序、中序、后序、层次	层次遍历最常用
典型应用	文件系统、组织架构	表达式求值、编译器语法分析	堆结构、优先队列

图

以下是关于**图（Graph Theory）**的核心知识点整理，结合知识库内容，以清晰的结构化形式呈现，涵盖定义、分类、术语、性质、算法及应用：

图的基本定义

1. 定义

图（Graph）：
由**顶点集合（V）和边集合（E）**组成，记为 ( G = (V, E) )。
- 顶点（Vertex/Node）：图的基本单元，表示实体或对象。
- 边（Edge）：连接两个顶点的线段，表示顶点之间的关系。
- 有向边（Arc）：具有方向的边（如 ( u \rightarrow v )）。
- 无向边（Edge）：无方向的边（如 ( (u, v) )）。

图的分类

1. 按边的方向分类

类型	定义	示例
无向图	边无方向，边是顶点的无序对（如 ( (u, v) = (v, u) )）。	社交网络中的朋友关系
有向图（DAG）	边有方向，边是顶点的有序对（如 ( u \rightarrow v )）。	交通网络中的单向道路

2. 按边的特性分类

类型	定义	示例
简单图	无自环（顶点到自身的边）和多重边（连接同一对顶点的多条边）。	无向图中的完全图
多重图	允许自环或多重边。	交通网络中的多条并行道路
有向无环图（DAG）	有向且无环的图。	任务调度中的依赖关系

核心术语与性质

1. 度（Degree）

无向图：
- 顶点的度：与顶点关联的边的数量。
- 握手定理：所有顶点的度数之和等于边数的2 倍。
有向图：
- 入度（In-degree）：指向顶点的边数。
- 出度（Out-degree）：从顶点出发的边数。
- 度数关系：所有顶点的入度之和等于出度之和，且等于边数。

2. 连通性

概念	定义	示例
连通图（无向）	图中任意两顶点间存在路径。	互联网中的节点连接
连通分量	无向图的极大连通子图（最大可能的连通子图）。	非连通图中的独立子图
强连通图（有向）	图中任意两顶点间存在双向路径。	环形交通网络
强连通分量	有向图的极大强连通子图。	社交网络中的紧密社群

3. 其他关键术语

术语	定义	示例
路径（Path）	顶点序列 ( v_1, v_2, ..., v_n )，使得每对相邻顶点间有边。	从 A 到 B 的路线
环（Cycle）	起点和终点相同的路径，且除起点外无重复顶点。	三角形结构中的闭合路径
自环（Loop）	顶点到自身的边。	顶点 A 到自身的边
子图（Subgraph）	顶点集和边集均为原图子集的图。	删除部分边后的简化图
生成子图	包含原图所有顶点的子图。	连通图的生成树

图的存储结构

常见存储方式

类型	结构	适用场景
邻接矩阵	二维数组 ( G[n][n] )，( G[i][j] = 1 ) 表示边 ( i \rightarrow j )。	小规模图、稠密图（边数多）
邻接表	每个顶点对应一个链表，存储其邻接顶点。	大规模图、稀疏图（边数少）
邻接表（带权）	链表节点存储邻接顶点及边权值。	赋权图（如最短路径问题）
边集数组	保存所有边的列表，按顶点或边权排序。	简单图操作（如最小生成树）

图的遍历算法

常见遍历方法

算法	规则	时间复杂度
深度优先搜索（DFS）	沿路径尽可能深访问，直到无法继续，再回溯。	( O(V + E) )
广度优先搜索（BFS）	逐层扩展访问，按距离起点的远近顺序探索。	( O(V + E) )

2. 遍历应用

DFS：检测图的连通性、寻找路径、拓扑排序（DAG）。
BFS：求最短路径（无权图）、层次遍历、二分图检测。

关键性质与公式

完全图的边数：

无向完全图：( \frac{n(n-1)}{2} ) 条边。
有向完全图：( n(n-1) ) 条边。

连通分量数量：

无向图至多有 ( n ) 个连通分量（每个顶点独立）。

欧拉定理：
- 无向图存在欧拉回路的充要条件：所有顶点度数为偶数。

高频考点与典型题型

1. 度数计算

例题：一个有向图有 5 个顶点，入度之和为 8，求边数。
答案：边数等于入度之和，即 8 条。

2. 连通性判断

例题：判断下图是否为强连通图。
步骤：
1. 检查每对顶点是否存在双向路径；
2. 若存在，则为强连通图。

3. 最小生成树（MST）

算法：
- Kruskal 算法：按边权从小到大选择，避免形成环。
- Prim 算法：从单个顶点出发，逐步扩展最小边。

经典问题与应用

1. 典型问题

问题	描述	算法
最短路径	求两点间权值最小的路径。	Dijkstra、Floyd、Bellman-Ford
拓扑排序	对 DAG 进行线性排序，确保所有前驱在后继之前。	Kahn 算法（BFS）、DFS
旅行商问题（TSP）	寻找访问所有顶点并返回起点的最短回路。	动态规划（NP 难，近似算法）

2. 实际应用

社交网络分析：通过图模型分析用户关系、社区发现。
物流路径规划：利用最短路径算法优化运输路线。
网页排名（PageRank）：基于有向图的节点重要性计算。

常见易错点与陷阱

连通分量与强连通分量混淆：
- 连通分量针对无向图，强连通分量针对有向图。
度数计算错误：
- 有向图中，顶点的度数是入度与出度之和。
生成树误解：
- 连通图的生成树必须包含所有顶点且无环。
欧拉回路条件误判：
- 必须所有顶点度数为偶数，且图连通。

总结对比表

概念	无向图	有向图
边	无方向	有方向
连通性	连通图/连通分量	强连通图/强连通分量
度数	顶点关联边的数量	入度（in-degree）和出度（out-degree）
完全图边数	( \frac{n(n-1)}{2} )	( n(n-1) )
典型应用	社交网络、电路设计	任务调度、网页链接分析

算法

贪心算法（Greedy Algorithm）

核心思想：在每一步决策中选择当前最优（局部最优），从而希望导致全局最优解。不考虑后续可能的影响，依赖问题的贪心选择性质（局部最优可推导全局最优）。

工作流程：

确定贪心策略（如按权重、时间、代价排序）；
按策略依次选择当前最优选项，确保不违反约束条件；
直至问题求解完成。

优点：

实现简单，效率较高（常结合排序，复杂度多为 O(nlogn)）；
适用于具备贪心选择性质的问题（如活动选择、最小生成树）。

缺点：

无法保证所有问题的全局最优（如 0-1 背包问题，贪心可能失效）；
需严格证明策略的正确性。

经典案例：

活动选择问题（选择不冲突的最多活动，按结束时间排序）；
Dijkstra 最短路径算法（非负权图，每次选当前最短距离节点）；
Kruskal/Prim 最小生成树算法（贪心选最小边或最近顶点）。

动态规划（Dynamic Programming, DP）

核心思想：将复杂问题分解为重叠子问题，用表格（DP 表）存储子问题的解，避免重复计算，通过状态转移方程推导最终解。

工作流程：

定义状态（如 d**p[i] 表示前 i 个物品的最优解）；
推导状态转移方程（如 d**p[i]=max(d**p[i−1],d**p[i−w]+v)）；
填充 DP 表，处理边界条件。

优点：

高效解决指数级复杂度问题（如 0-1 背包，暴力枚举为 O(2n)，DP 为 O(nV)）；
适用于具备最优子结构和重叠子问题的场景。

缺点：

状态定义和转移方程推导较难（需抽象问题模型）；
空间复杂度可能较高（可通过滚动数组优化，如二维转一维）。

经典案例：

0-1 背包问题（最大化价值，重量不超过容量）；
最长公共子序列（LCS，字符串相似度分析）；
斐波那契数列（递归优化，避免重复计算）。

回溯算法（Backtracking）

核心思想：通过深度优先搜索（DFS）遍历解空间树，逐步构建候选解，若发现当前路径无效（违反约束）则回溯，尝试其他分支。

工作流程：

定义解空间（如排列、子集、路径的可能形式）；
递归遍历解空间，每一步选择合法选项，记录路径；
若达到目标解则保存，否则回溯（剪枝）到上一层。

优点：

适合求解组合型问题（排列、子集、路径搜索），可枚举所有合法解；
剪枝优化可大幅减少搜索空间。

缺点：

最坏时间复杂度高（指数级 O(2n) 或阶乘级 O(n!)）；
需设计高效的剪枝条件（否则性能低下）。

经典案例：

八皇后问题（在棋盘上放置 8 个皇后，互不攻击）；
子集和问题（判断是否存在子集和为目标值）；
迷宫寻路（寻找从起点到终点的所有路径）。

分治算法（Divide and Conquer）

核心思想：将问题分解为若干规模更小、结构相同的子问题，递归求解子问题，再合并子解得到原问题的解。

工作流程：

分解：将原问题分成多个子问题；
求解：递归求解每个子问题（直至子问题足够小可直接求解）；
合并：将子问题的解合并为原问题的解。

优点：

适合处理可分解为相似子问题的场景（如排序、搜索）；
可利用递归和并行计算优化效率（如归并排序的 O (n log n) 复杂度）。

缺点：

子问题需独立（无重叠，否则动态规划更优）；
合并子解可能增加实现复杂度（如归并排序的合并步骤）。

经典案例：

归并排序（分解数组，递归排序后合并）；
快速排序（选择基准值，分治处理左右子数组）；
二分查找（在有序数组中递归缩小区间）。

深度优先搜索（DFS）与广度优先搜索（BFS）

算法	核心思想	特点	应用场景
DFS	从起点出发，沿一条路径深入探索，直到无法继续则回溯，访问所有可达节点。	用栈（或递归）实现，优先访问深层节点，适合找单一路径或检测连通性。	图的连通性判断、强连通分量检测、回溯算法的基础。
BFS	从起点出发，按层遍历，优先访问距离起点近的节点（队列实现）。	用队列实现，适合求无权图的最短路径（层序遍历保证最短距离）。	无权图最短路径、层序遍历、社交网络最短距离计算。

KMP 算法

核心思想：在字符串匹配中，利用预处理得到的部分匹配表（最长前缀后缀匹配长度），避免匹配失败时重复移动模式串，优化匹配效率。

工作流程：

预处理模式串，生成 next 数组（记录每个位置的最长前缀后缀长度）；
用 next 数组指导主串与模式串的匹配，失败时按 next 值跳转模式串指针。

优点：

时间复杂度低（O(n+m)，n 为主串长度，m 为模式串长度）；
高效处理长文本匹配（如文本编辑器 “查找” 功能）。

缺点：

仅适用于单模式串匹配（多模式串需 AC 自动机等算法）。

经典案例：在 DNA 序列中查找特定子串、日志文件中的关键词匹配。

最小生成树算法（Prim/Kruskal）

算法	核心思想	数据结构	适用场景
Prim	从顶点出发，每次选择离当前生成树最近的顶点（贪心），逐步扩展生成树。	邻接矩阵（稠密图，O(V2)）或优先队列（稀疏图，O(ElogV)）。	稠密图（边数多）的最小生成树。
Kruskal	按边权从小到大排序，依次选择不构成环的边（并查集判环），直到生成树形成。	并查集（判环）+ 排序（O(ElogE)）。	稀疏图（边数少）的最小生成树。

算法优缺点及实用案例对比表

算法	核心思想	优点	缺点	实用案例（软考高频）
贪心算法	局部最优推导全局最优	实现简单、效率高（常结合排序）	不保证全局最优（依赖问题性质）、需证明策略正确性	活动选择、Dijkstra 最短路径、Prim/Kruskal 生成树
动态规划	存储子问题解，避免重复计算	解决指数级复杂度问题、适用于重叠子问题和最优子结构	状态定义难、空间复杂度可能高（需优化）	0-1 背包、LCS、斐波那契数列优化
回溯算法	深度优先搜索解空间树，剪枝无效路径	适合组合问题、枚举所有合法解	最坏复杂度高（指数级）、依赖剪枝效率	八皇后、子集和、迷宫寻路
分治算法	分解子问题，递归求解后合并	高效处理可分解的相似子问题（如排序、搜索）	子问题需独立（无重叠）、合并步骤可能复杂	归并排序、快速排序、二分查找
DFS	深度优先遍历图或解空间	找单一路径、检测连通性	无法保证最短路径（适用于无权图）	图的连通性检测、回溯算法基础
BFS	广度优先按层遍历图	求无权图最短路径、层序遍历	空间复杂度高（需维护队列）	无权图最短路径、二叉树层序遍历
KMP 算法	利用部分匹配表优化字符串匹配	线性时间复杂度（O (n+m)）、高效长文本匹配	仅适用于单模式串匹配	DNA 序列子串查找、日志关键词匹配
Prim 算法	贪心选择最近顶点构建最小生成树	适合稠密图（邻接矩阵实现高效）	需维护顶点距离数组	电网布线（最小权重生成树）
Kruskal 算法	贪心选择最小边，并查集判环	适合稀疏图（排序和并查集高效）	需排序边集	通信网络最小成本架构设计

核心对比总结

贪心 vs 动态规划：
- 贪心：局部最优，无后效性（不考虑后续状态），依赖问题的贪心选择性质。
- 动态规划：全局最优，需考虑状态转移，处理重叠子问题和后效性（如 0-1 背包的 “选或不选” 影响后续容量）。
DFS vs BFS：
- DFS 适合找单一路径或检测连通性，用递归 / 栈实现；
- BFS 适合求无权图最短路径，用队列实现，按层扩展。
Prim vs Kruskal：
- Prim 以顶点为中心，适合稠密图（邻接矩阵）；
- Kruskal 以边为中心，适合稀疏图（排序 + 并查集）。

标准化和知识产权

标准化组织对比表

组织名称	性质	代表标准 / 领域	备注
ISO	国际标准化组织	ISO 9000（质量）、ISO 27001（信息安全）	全球通用，促进国际间技术协调
IEEE	美国电气电子工程师协会	IEEE 802（局域网）、IEEE 754（浮点数）	侧重电气、电子及计算机工程领域标准
CMMI	过程改进模型	CMMI-DEV（软件开发成熟度）	评估企业软件开发过程成熟度
GB	中国国家标准	GB（强制性）、GB/T（推荐性）	国内通用，如 GB 18030（汉字编码）
行业标准	特定行业规范	YD（通信）、GA（公安）、SJ（电子）	在行业内强制或推荐使用

标准分类表

按适用范围分类

分类	定义	示例
国际标准	国际组织发布，全球适用	ISO、IEC 标准
国家标准	国家主管机构发布，全国适用	GB（中国）、ANSI（美国）
行业标准	行业协会发布，特定行业内适用	YD（通信）、IEEE 标准
企业标准	企业自行制定，内部适用	某公司技术规范

按性质分类

分类	特点	示例
强制性标准	法律强制遵守，违规禁止生产 / 销售	GB（不带 / T 后缀）
推荐性标准	自愿采用，以 “/T” 标识	GB/T、ISO/IEC 指南

知识产权核心考点

知识产权保护期限表

客体类型	权利类型	保护期限	特殊说明
软件著作权	署名权、修改权	永久	公民作品归个人，职务作品归单位
	发表权、使用权	公民：终生 + 死后 50 年；单位：首次发表后 50 年	合作开发以最后死亡作者为准
专利权	发明专利权	20 年（自申请日起）	需每年缴纳年费
	实用新型 / 外观设计	10 年（自申请日起）
商标权	注册商标权	10 年（可无限续展，续展期 6 个月）	未续展则注销
商业秘密	技术 / 经营信息	未公开则永久有效	公开后丧失保护

知识产权归属判定表

场景	归属原则	示例说明
职务作品	单位享有著作权（除署名权）	员工在本职工作中开发的软件
委托开发	有合同按合同，无合同归受托人	甲委托乙开发软件，未约定则乙拥有
合作开发	共同享有，可分割成果可单独申请	甲乙合作开发，成果可拆分则各自申请
商标 / 专利申请	先申请原则，同时申请协商或抽签	甲乙同日申请，协商不成则抽签

常考例题汇总

标准化知识例题

题目：以下属于推荐性国家标准的是（） A. GB 18030 B. YD/T 1234 C. GB/T 2312 D. ISO 9001 答案：C 解析：GB/T 是推荐性国家标准标识，GB 为强制性，YD/T 是通信行业推荐标准，ISO 是国际标准。
题目：IEEE 802.11 属于（） A. 国际标准 B. 行业标准 C. 企业标准 D. 地方标准答案：B 解析：IEEE 是美国电气电子工程师协会制定的行业标准，专注于局域网技术。

知识产权知识例题

题目：某公司员工在业余时间开发的软件，著作权归（） A. 公司 B. 员工个人 C. 公司与员工共有 D. 无归属答案：B 解析：非职务作品（业余时间、未用公司资源）著作权归个人所有。
题目：发明专利的保护期限是（） A. 10 年 B. 15 年 C. 20 年 D. 50 年答案：C 解析：发明专利权保护期自申请日起 20 年，实用新型和外观设计为 10 年。
题目：甲委托乙开发软件，未约定著作权归属，该软件著作权归（） A. 甲 B. 乙 C. 甲乙共有 D. 国家所有答案：B 解析：委托开发未约定时，著作权归受托人（乙）所有。
题目：以下属于侵犯软件著作权的行为是（） A. 购买正版后安装到公司 3 台电脑 B. 修改正版软件后自用 C. 备份正版软件到硬盘 D. 转让正版软件许可给他人答案：D 解析：转让软件许可需著作权人授权，个人安装、备份属于合理使用，修改后自用若未传播不侵权（具体视软件许可协议）。

专业英语

英文	中文
Abstract	摘要；抽象的
Abstraction	抽象
Access	访问
Accessibility	无障碍；辅助功能 (win/mac)
Activate, Activation	激活
Active	使用中的；现用的；有效的；激活的
Adapter, Adaptor	适配卡，适配器
Add	添加
Address	位址，地址
Advanced	高级的
Aggregation	聚合
AI (Artificial intelligence)	人工智能
Algorithm	算法
Allocate	分配
Allocator	分配器
Annotation	注释 (win)；注解 (mac)
App bundle	应用程序包 (win)；App 捆绑包 (mac)
Application	应用；应用程序
Apply	应用
Architecture	架构；结构
Argument	参数（也称为实际参数，实参）
Arity	参数数量
Artifact	项目 (win)；成品 (mac)
Array	数组
Assembly language	汇编语言
Assert, Assertion	断言 (win)；声明 (win/mac)；论断 (mac)
Assign, Assignment	分配；（编程）赋值
Assignment operator	赋值运算符
Asynchronize	异步
Asynchronous	异步的
Atomic	原子的
Attribute	属性
Audio	音频
Authenticate, Authentication	验证，认证
Authorize, Authorization	授权
Autoboxing	自动装箱
Background processes	后台进程
Bandwidth	带宽
Base class	基类
Batch	批（处理）
Binary function	二元函数
Binary operator	二元运算符
Binary search	二分查找
Binary tree	二叉树
Bind	绑定
Bit	位
Bitrate	码率
Block	屏蔽；阻止
Block	（代码）块
Blocker	阻止程序 (win)；拦截器 (mac)
Boolean	布尔
Bounce	退回；弹跳
Breakpoint	断点
Build (verb)	构建
Build (noun)	构件；版本（号）
Build-in	内置 (win)；内建 (mac)
Bundle (noun)	捆绑包
Bundle (verb)	整合
Bus	总线
Burn	刻录
Byte	字节
Cache	高速缓存，缓存
Call	调用
Callback	回调
Certificate	证书
Character	字符
Check	查看
Check box, Checkbox	复选框
Class	类
Point & Click (noun)	点按
Click (vs. Tap)	点击 (win)；点按 (mac)
Tap (vs. Click)	触碰 (win)；轻点 (mac)
Client-side	客户端
Clipboard	剪贴板
Clone	克隆
Cloud computing	云计算
Cohesion	内聚
Collaborate, Collaboration	协作
Combo box	组合框
Come with	随附
Command	命令
Command line	命令行
Comment	评论
注解，注释
Commit	提交
Communication	通信
Community	社区
Compatibility	兼容性
Compatible	兼容的
Compile, Compilation	编译
Compile time, Compile-time	编译期，编译时
Compiler	编译器
Component	组件
Composition	组合
Compress	压缩
Concurrency	并发性，并发
Concurrent	并发的；同时的
Configuration	配置
Connect, Connection	连接
Constant	常量
Constraint	约束；限制
Constructor	构造函数
Container	容器
Context	背景（关系）；环境；上下文；内容
Continuous delivery	持续交付
Continuous deployment	持续部署
Continuous integration	持续集成
Control	控件
Copy	复制 (win)；拷贝 (mac)
Coroutine	协程，协同程序
Coupling	耦合
Crash	崩溃 (win/mac)；故障 (win)
Create	创建
Cursor	光标
Custom	自定义
Data	数据
Data link layer	数据链路层
Data structure	数据结构
Database	数据库
Database schema	数据库架构，数据库模式
Deadlock	死锁
Debug	调试
Debugger	调试器
Declare, Declaration	声明
Default	默认
Definition	定义；清晰度
Delegate, Delegation	委托
Dependency	依赖
Derived class	派生类
Design pattern	设计模式
Destructor	析构函数
Detect, Detection	检测
Device	设备
Dialog	对话框
Digital	数字的；数字化
Digital signature	数字签名
Digital certificate	数字证书
Directory	目录
Disk	盘
Disk image	磁盘映像
Dispatch	分派；调度
Distributed	分布式
Distribute, Distribution	分发；分配；分布
Distribution	发行（版本）
Document	文档；文稿
Domain	域
Driver	驱动程序
Drop-down, Dropdown (noun)	下拉菜单
Drop-down, Dropdown (verb)	下拉
Drop-down menu	下拉菜单 (win/mac)
Drop-down list	下拉列表
Dynamic binding	动态绑定
Element	元素；元件
Email, E-mail	电子邮件
Enable	启用
Encapsulation	封装
Entity	实体
Enumeration	枚举
Equal	相等的
Equality	相等性，相等
Escape code	转义码
Event	事件
Exception	异常
Explicit	显式
Export	导出
Expression	表达式
Extension	扩展（程序、功能）
Extension	扩展名
Feature	特色，特点
Feature (vs. Function)	（特殊的）功能
Feedback	反馈
Field	字段，栏位；域
File	文件
Filter	过滤器
Find	查找
Firmware	固件
Flag	标记
Flash memory	闪存
Flush	刷新
对齐，齐平
Folder	文件夹
Font	字体
Form	表单
Format (noun)	格式
Format (verb)	格式化
Forward	转发，转送，转寄
Fragment	片段
Frame	帧；框架
Frame rate FPS (frames per second)	帧率
Framework	框架
Frozen	冻结，锁定
Full screen, Fullscreen	全屏
Function	函数
Function (vs. Feature)	（一般的）功能
Functionality	功能
Game	游戏
Gateway	网关
General	通用的
Generate	生成
Generic	通用的
Generics	泛型
Global	全局的
Group box	分组框，群组框
Graph	图
Handle	句柄
Handler	处理程序，处理器
Hardware	硬件
Hash	哈希
Header file	头文件
Heap	堆
Help	帮助
Hierarchy	层次结构
High Definition	高清晰度，高清
Host file	主机文件
Home folder	主文件夹 (win)；个人文件夹 (mac)
Home page	主页
Icon	图标
IDE	集成开发环境
Identifier	标识符
Idle	闲置
Image	影像；图像，图片；映像
Immutable	不可变的；不可更改的
Implement	实现
Implementation	实现
Implicit	隐式
Import	导入
Indent	缩进
Info	简介
Information	信息
Inheritance	继承
Initialization	初始化
Inline	内联
Instance	实例
Integrate	集成
Integrated	集成的
Integrity	完整性
Interact, Interaction	交互
Interface	接口
Internal Storage	内存 (仅手机等便携装置，民间称谓)
Internationalization (I18N)	国际化
Internet	互联网
Interpreter	解释器
Invoke	调用
Iterate	迭代；重复、循环（访问）
Iteration	迭代
Iterator	迭代器
Kernel	内核
Key	密钥
Keybind	快捷键
Lag	延迟
Layout	布局，配置
Lazy loading	延迟加载；懒加载
Library	程序库，函数库
Link	链接
Link time	链接期
Linked list	链表
Linker	链接器
List	列表
Listener	监听器
Literals	字面值，字面量
Literal constant	字面常量
Load	加载
Load time	加载期
Loader	加载器
Local	局部的，本地的；本地（主机）
Localization (L10N)	本地化
Local variable	局部变量
Lock	锁定
Log	日志
Log in, Login	登录
Log out, Logout	退出；注销
Loop	循环
Map, Mapping	映射
Match	匹配
Memory	内存
Menu	菜单
Message	消息；信息
Metadata	元数据
Middleware	中间件，中间软件
Mobile	移动
Moderate, Moderation	审核
Modifier	修饰符
Module	模块
Monomorphism	单态
Motherboard	主板
Mouse	鼠标
Mouse pointer	鼠标指针
Multitasking	多任务（处理）
Mutable	可变的
Mutex	互斥
Native	原生
Navigate, Navigation	导航
Navigator	导航器
Nested	嵌套的
Network	网络
New	新建
Notarization	公证
Object	对象
Object code	目标代码
Object file	目标文件
Object-oriented	面向对象
Online	在线
Operand	操作数，运算元
Operating system	操作系统
Operator	操作符，运算符
Optimize, Optimization	优化
Overflow	溢出（上溢出）
Overlay	叠加面板
Overload	重载
Override	覆盖，重写
Pack	打包，压缩
Package (noun)	（程序、软件）包
Package (verb)	打包，封装
Pane	窗格 (win) 面板 (mac)
Parallelism	并行性，并行
Parameter	参数（也称为形式参数，形参）
Parse	解析
Partition	分割；（硬盘）分区
Paste	粘贴
Patch	补丁 (win) 修补程序 (mac)
Pattern	模式；样式
Performance	性能
Persistence	持久性
Photo	照片
Physical layer	物理层
Picklist	选择列表
Placeholder	占位符
Pluggability	可插入性
Plugin	插件
Pointer	指针
Polymorphism	多态
Port	端口
Power bank	移动电源，充电宝
Presentation layer	表示层
Preset	预设
Print	打印
Printer	打印机
Procedure	过程
Process	进程
Profile	配置文件 (win) 描述文件 (mac)
Profile	评测
Profile (or Personal profile)	个人资料
Profiler	（性能）分析器
Program	程序
Project	项目
Protocol	协议
Provision, Provisioning	预配
Proxy (or Proxy server)	代理服务器
Pseudo code	伪代码
Pull-down list	下拉列表
Quality	质量
Queue	队列
Quit unexpectedly	意外退出
Radian	弧度
Radio button	单选按钮
RAM (Random Access Memory)	随机存取存储器
Read	读
Read-only	只读
Recovery	还原 (win)，恢复 (mac)
Recursion	递归
Redirect, Redirection	重定向
Reference	参考
Register	寄存器；注册
Release	（发行、发布）版本
Remote	远程
Render	渲染
Resolution	分辨率
Response	响应
Response body	响应正文
Response header	响应头
Restore	还原 (win)，恢复 (mac)
Return	返回；恢复
Revoke, Revocation	撤销
Rollback	回滚，回退
Routine	程序
Run	运行
Runtime, Run-time	运行期，运行时；运行环境
Runtime environment (RTE), Runtime system	运行环境；运行系统
Save	保存
Sampling	取样
Scalar	标量
Schedule	调度
Scheduler	调度器，调度程序
Scope	（作用、有效）范围，域
Scroll bar	滚动条
Script	脚本
SDK (Software Development Kit)	软件开发工具包 (win) 软件开发套件 (mac)
Search engine	搜索引擎
Security	安全性
Segment	段
Server	服务器
Server-side	服务器端
Session	会话
Session	会话
Session layer	会话层
Set up	设置
Settings	设置
Shortcut	快捷
Shortcut key	快捷键
Sign in, sign-in	登录
Sign out, sign-out	退出，注销
Silicon	硅
Simulation	模拟
Signature	签名
Slider	滑块
Smart	智能
Smartphone	智能手机
SMS (Short Message Service)	短信
Snip	截图
Source code	源代码，源码
Stack	栈
Star rating	星级评分
Statement	语句
Status bar	状态栏
Stepper	步进器
Stream	（数据）流
String	字符串
String interpolation	字符串插值
Stuttering	-
Subclass	子类
Subroutine	子例程
Superclass	超类
Support	支持
Suspend	暂停（权限）
Synchronize	同步
Synchronous	同步的
Tab	标签（页）
Tag	标签
Task	任务
Template	模板
Text	文本
Text box	文本框
Thread	线程
Top-up	充值
Token	标记 (win) 令牌 (mac)
权杖；代币
Traverse	遍历
Tray (or System tray)	系统托盘
Tree	树
Tuple	元组
Tutorial	教程
Type	类型
Universal	通用的
Variable	变量
Video	视频
View	查看；显示；视图
Voice	语音
Volume	卷 (win)；宗卷 (mac)
Window	窗口
Widget	窗口部件；小部件
Wildcard	通配符
Workspaces	工作区
Write	写

版权所有

许可证：署名 4.0 国际 (CC-BY-4.0)