1GB = 1024MB = 1024 × 1024KB = 1024 × 1024 × 1024Byte（字节） = 1024 × 1024 × 1024 × 8bit（比特）

1 英文字母（不分大小写）= 1Byte

1 汉字 = 2 byte = 16 bit （这里不是很准确，当编码不同的时候，1个汉字所占的字节数也会有所不同，有些编码是占 2个字节，有些则不是，可能是 3个或者 4个）

一、计算机组成与体系结构

1.1 数据的表示（☆☆☆☆）

1.1.1 不同进制转换

R进制转十进制【按权展开法】

• 二进制转十进制：10100.01 = 1✕2⁴ + 1✕2² + 1✕2^-2 = 16 + 4 + ¼ = 20.25
• 七进制转十进制：604.01 = 6✕7² + 4✕7⁰ + 1✕7^-2 = 282 + 4 + ¹⁄₄₉ ≈ 286.02

十进制转R进制【短除法】

R进制转R进制

• 二进制转八进制

• 八进制转二进制

• 二进制转十六进制

• 十六进制转二进制

• 其余二进制转七进制、七进制转二进制等需要十进制进行间接转换

1.1.2 原码、反码、补码、移码

由此可见，只有补码的【溢出数值】才是正确的加法运算，所以使用补码参与加减法运算。

1.1.3 速记

$\begin{cases} 正数的原码、反码、补码都相同 \\ 负数的反码除原码符号位外全部取反 \\ 负数的补码在反码的基础上+1 \\ 移码的正负数只对补码的符号位取反 \end{cases}$

1.2 数值表示范围

1.3 浮点数的运算

浮点数表示：N = 尾数 * 基数^阶码

特点：

1. 一般尾数用【补码】，阶码用【移码】
2. 対阶时，小数向大数看齐
3. 尾数越长，表示数的精度更高；阶码越长，表示数的范围越大

1.4 计算机结构

1.4.1 运算器与控制器（☆☆☆☆）

CPU = 运算器 + 控制器 + 寄存器组 + 内置总线

1.4.2 速记

$CPU \begin{cases} 运算器 \begin{cases} 算术逻辑单元ALU：数据的算术运算和逻辑运算 \\ 累加寄存器AC：通用寄存器，为 ALU 提供一个工作区，用在暂存数据 \\ 数据缓冲寄存器DR：写内存时，暂存指令或数据 \\ 状态条件寄存器PSW：存状态标志与控制标志（存在争议，也有将其归为控制器的） \end{cases}\\ 控制器 \begin{cases} 程序计数器PC：存储下一条要执行指令的地址 \\ 指令寄存器IR：存储从存储器中读取出来的，即将执行的指令 \\ 地址寄存器AR：存储 CPU 当前要访问的指令的地址 \\ 指令译码器IR：对指令中的操作码字段进行分析解释 \\ 时序部件：为每条指令按时间顺序提供时序控制信号 \end{cases}\\ 寄存器组 \\ 内置总线 \end{cases}$

1.4.3 存储器

• 主存储器：内存
• 辅助存储器：外存，硬盘属于外存

1.4.4 输入设备

1.4.5 输出设备

1.5 计算机体系结构分类

1.5.1 Flynn分类法（☆☆）

1.5.2 速记

1.6 指令的基本概念

一条指令就是机器语言的一个语句，它是一组有意义的二进制代码，指令的基本格式如下：

【操作码字段】指出了计算机要执行什么性质的操作，如加法、减法、取数、存数等。

【地址码字段】需要包含各操作数的地址及操作结果的存放地址等，从其地址结构的角度可以分为三地址指令、二地址指令、一地址指令和零地址指令。

1.7 寻址方式

1.7.1 速记

$寻址方式 \begin{cases} 立即寻址方式：【主存储器】→【指令】→【操作数】（速度快，但灵活性差） \\ 直接寻址方式：【主存储器】→【指令】→【操作数地址】 \\ 间接寻址方式：【主存储器】→【指令】→【地址】→【操作数地址】 \\ 寄存器寻址方式：【寄存器】→【指令】→【操作数地址】 \\ 寄存器间接寻址方式：【寄存器】→【指令】→【地址】→【操作数地址】 \end{cases}$

1.8 CISC与RISC（☆☆）【速记】

• CISC：复杂，指令数量多，指令种类多，频率差别大，指令寻址方式多，少量通用寄存器，使用微程序控制技术（微码），不支持流水线
• RISC：精简，指令数量少，指令种类少，频率差别小，指令寻址方式少，大量通用寄存器，单周期指令执行，采用流水线技术

1.9 流水线技术（☆☆☆☆）

流水线是指在程序执行时，多条指令重叠进行操作的一种标准并行处理实现技术。各种部件同时处理是针对不同指令而言的，它们可同时为多条指令的不同部分进行工作，以提高各部件的利用率和指令的平均执行速度。

1.9.1 流水线周期计算

t1：第一条指令的第一个步骤执行的时间

Δt：流水线周期

理论公式：(t1+t2+…+tk)+(n-1)*Δt

k*Δt：第一条指令的所有步骤都给一个宽裕的时间（即当中最长步骤的时间）来充分执行

实践公式：k*Δt+(n-1)*Δt

示例：一条指令的执行过程可以分解为取指、分析和执行三步，在取指时间 t=3Δt、分析时间 t=2Δt、执行时间 t=4Δt 的情况下，若按串行方式执行，则 10 条指令全部执行完需要（(3+2+4)Δt*10=90Δt）；若按流水线的方式执行，流水线周期为（4Δt），则 10 条指令全部执行完需要（(3+2+4)Δt+(10-1)*4Δt=45Δt）。

1.9.2 超标量流水线

超标量流水线就是 n 条流水线的组合，其中 n 称为：度。因此在计算所有指令全部执行完的时间时需要除以 n。

1.9.3 流水线吞吐率计算

流水线的吞吐率（Though Put rate, TP）是指在单位时间内流水线所完成的任务数量或输出的结果数量。计算流水线吞吐率的最基本的公式：TP = $\frac{指令条数}{流水线执行时间}$

流水线最大吞吐率：TP_max = $\lim\limits_{n\rightarrow\infty}\frac{n}{(k+n-1)Δt}$ = $\frac{1}{Δt}$

1.10 层次化存储结构

存储系统（☆☆☆☆）

1.10.1 Cache

在计算机的存储系统体系中，Cache 是访问速度最快的层次（若有寄存器，则寄存器最快）。

使用 Cache 改善系统性能的依据是程序的局部性原理。

• 时间局部性原理：一个变量可能被反复多次访问，则该变量不会被优先淘汰
• 空间局部性原理：一个被访问的变量，其附近的空间区域也有可能被访问到

1.10.2 Cache 命中率

如果以 h 代表对 Cache 的访问命中率，t₁ 表示 Cache 的周期时间，t₂ 表示主存储器周期时间，以读操作为例，则使用“Cache + 主存储器”的系统的平均周期：

t₃ = h*t₁+(1-h)*t₂

其中，( 1-h )又称为失效率（未命中率）

1.10.3 Cache 映像

【地址映像】是将主存与 Cache 的存储空间划分为若干大小相同的页（或称为块）。
示例：某机的主存容量为 1GB，划分为 2048 页，每页 512KB；Cache 容量为 8MB，划分为 16 页，每页 512KB。

直接相联映像

硬件电路较简单，但冲突率很高。

读取内存 16 页的内容时，会将 Cache 0页中已有的内容替换，因此这种方案速度最快，但冲突率最高

全相联映像

电路难于设计和实现，只适用于小容量的 cache，冲突率较低。

主存每一页的内容都可以放到 Cache 的任意一页中，冲突率是低了但是速度最慢，每次都要遍历 Cache 的页去找数据。

组相联映像

直接相联与全相联的折中。

先对主存的页进行分组（分区），只有同一组或者不同组但所对应 Cache 页一致的内容才会冲突。

1.11 主存

编址与计算

1 个字节（Byte） = 8 比特位（bit）

根据存储器所要求的的容量和选定的存储芯片的容量，就可以计算出所需芯片的总数，即：总片数 = $\frac{总容量}{每片的容量}$

示例：若内存地址区间为 4000H~43FFH，每个存储单元可存储 16 位二进制数，该内存区域用 4 片存储器芯片构成，则构成该内存所用的存储器芯片的容量是多少？

H 结尾表示 16 进制

总容量 = (43FFH-4000H+1)*16bit = 400H*16bit = 2¹⁰*16bit；总片数 = 4

每片的容量 = 2^10-2*16bit = 2⁸*16bit = 256*16bit

1.12 总线系统（☆）

一条总线同一时刻仅允许一个设备发送，但允许多个设备接收。

总线分类：

• 数据总线 ( Data Bus ) : 在 CPU 与 RAM 之间来回传送需要处理或是需要储存的数据。
• 地址总线 ( Address Bus ) : 用来指定在 RAM ( Random Access Memory )之中储存的数据的地址。
• 控制总线( Control Bus ) : 将微处理器控制单元 ( Control Unit ) 的信号专送到周边设备，一般常见的为 USB Bus 和 1394 Bus。

1.13 串联系统与并联系统

可靠性（☆）

• 串联系统可靠性 R = R₁×R₂×……×R_n
• 并联系统可靠性 R = 1-(1-R₁)×(1-R₂)×……×(1-R_n)

总结：串联是一个异常就全部异常；并联是一个正常就全部正常。

N 模混合系统

混合模型计算就划分块，总的是一个串联公式，括号分隔计算每个并联块的可靠性

1.14 校验码（☆☆☆）

码距：任何一种编码都由许多码字构成，任意两个码字之间最少变化的二进制位数就称为数据校验码的码距。

示例：二进制 0 到 1 的码距为 1；01 到 10 的码距为 2；因此可以用 4 位二进制表示 16 种状态，则有 16 个不同的码字，此时的码距为 1。如 0000 和 0001。

奇偶校验

奇偶校验只可【检错】，且只可检查 1 位的错误，不可【纠错】。

奇偶校验码的编码方法是：由若干位有效信息（如一个字节），再加上一个二进制位（校验位）组成校验码。

• 奇校验：整个校验码（有效信息位和校验位）中“1”的个数为奇数
• 偶校验：整个校验码（有效信息位和校验位）中“1”的个数为偶数

循环校验码CRC

循环校验码 CRC可【检错】，不可【纠错】。

CRC 的编码方法是：在 k 位信息码之后拼接 r 位校验码。应用 CRC 码的关键是如何从 k 位信息位简便地得到 r 位校验位（编码），以及如何从 k+r 位信息码判断是否出错

循环冗余校验码编码规律如下：

1. 把待编码的 N 位有效信息表示为多项式 M(X)；
2. 把 M(X) 左移 K 位，得到 M(X)×X^K，这样空出了 K 位，以便拼装 K 位余数（即校验位）；
3. 选取一个 K+1 位的产生多项式 G(X)，对 M(X)×X^K 做模 2 除；
4. 把左移 K 位以后的有效信息与余数 R(X) 做模 2 加减，拼接为 CRC 码，此时的 CRC 码共有 N+K 位。

把接收到的 CRC 码用约定的生成多项式 G(X) 去除，如果正确，则余数为 0；如果某一位出错，则余数不为0。不同的位数出错其余数不同，余数和出错位序号之间有惟一的对应关系。

示例：原始报文为“11001010101”，其生成多项式为：“x⁴+x³+x+1”。计算其进行 CRC 编码后的结果。

最后把余数【0011】拼接到原始报文后面【110010101010011】即可。

对方在接收到处理后的报文再进行一次【模 2 除】，余数为 0 即为正确。

海明校验码

海明校验码可【检错】，也可【纠错】。

原理可略，但是公式得掌握，知道怎么计算【校验位的个数】

海明校验码的原理是：在有效信息位中加入几个校验位形成海明码使码距比较均匀地拉大，并把海明码的每个二进制位分配到几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化这不但可以发现错误，还能指出错误的位置，为自动纠错提供了依据。

2^r≥m+r+1（r 为校验位的个数；m 为数据位的个数）

校验码为 3 位则固定放在：2⁰（1）、2¹（2）、2²（4）的位置

校验码为 4 位则固定放在：2⁰（1）、2¹（2）、2²（4）、2³（8）的位置

代入原始报文：

r₂ = I₄(1)、I₃(0)、I₂(1) 做偶校验【I₄(1)、I₃(0) → 10得1；1、I₂(1) → 11得0】= 0

r₁ = I₄(1)、I₃(0)、I₁(1) 做偶校验【I₄(1)、I₃(0) → 10得1；1、I₁(1) → 11得0】= 0

r₀ = I₄(1)、I₂(1)、I₁(1) 做偶校验【I₄(1)、I₂(1) → 11得0；0、I₁(1) → 01得1】= 1

所以可以得出海明码为：101 0101

若收到的信息被篡改为：101 1101

则如上图计算可知 r₂ 不为 0，由此满足检错的目的；同时根据对收到信息的做偶校验的计算公式中的元素取交集，可知是 r₂ 出了问题，由此完成纠错的目的。

二、操作系统

2.1 进程管理

进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。它由程序块、进程控制块（PCB）和数据块三部分组成。

2.1.1 进程 VS 程序

进程与程序的区别：

• 程序是完成某个特定功能的一系列程序的语句的集合，只要不被破坏，它就永远存在；进程是程序的一次执行过程，没有程序就没有进程。
• 程序是一个静态的概念，而进程是一个动态的概念，它由创建而产生，完成任务后因撤销而消亡。
• 进程是系统进行资源分配和调度的独立单位，而程序不是。

2.1.2 进程的状态（☆☆）

2.1.3 进程的同步与互斥

同步是合作进程间的直接制约问题，互斥是申请临界资源进程间的间接制约问题。

• 同步：进程 B 需要等待进程 A 把数据存入缓冲区，才可以取出数据进行处理
• 互斥：进程 A 和 B 使用同一张表格，不能同时编辑

2.1.4 信号量与PV操作（☆☆☆☆）

• 临界资源：各进程间需要互斥方式对其进行共享的资源，如：打印机、磁带机等

• 临界区：每个进程中访问临界资源的那段代码成为临界区

• 信号量（S）：是一个整型变量，根据控制对象的不同被赋予不同的值

  • 公用信号量：实现进程间的互斥，初值为 1 或资源的数目
  • 私用信号量：实现进程间的同步，初值为 0 或某个正整数

• PV：P 是荷兰语的 Passeren，V 是荷兰语的 Verhoog

利用 PV 操作实现进程的互斥

1. 理发店只有 1 位理发师为【临界资源 S】
2. 客户 1 进入理发店进行 P 操作，S=S-1=0≥0，进程继续进行理发
3. 客户 2 进入理发店进行 P 操作，S=S-1=-1<0，客户 2 进程进入阻塞队列
4. 客户 1 理完发进行 V 操作，S=S+1=0≤0，从阻塞队列唤醒一个进程进程，客户 1 进程继续，离开理发店；客户 2 进程被唤醒，进入操作 P，此时 S≥0，进行理发

P 操作（申请资源）的定义：S:=S-1，

1. 若 S < 0，则置该线程为阻塞状态（因为无可用资源），并将其加入阻塞队列；
2. 若 S ≥ 0，则执行 P 操作的进程继续执行。

V 操作（释放资源）的定义：S:=S+1，

1. 若 S ≤ 0，则从阻塞状态唤醒一个进程，并将其插入就绪队列，然后执行 V 操作的进程继续；
2. 若 S > 0，则执行 V 操作的进程继续执行。

利用 PV 操作实现进程的同步

单缓冲区生产者、消费者问题

案例分析A

某书店有一个收银员，该书店最多允许 n 个购书者进入。将收银员和购书者看作不同的进程，其工作流程如下图所示。利用 PV 操作实现该过程，设置信号量 S1、S2 和 Sn，初值分别为 0，0，n。则图中 a1 和 a2 应填入____，图中 b1 和 b2 应填入____。

分析过程：

• 收银员与购书者为一对多关系，所以先从【收银员进程】进行分析，b1 和 b2 应填入 C
• PV 操作成对出现，因此由 C 反推可得 a1 和 a2 应填入 A

案例分析B

分析过程：

• 题目以【前趋图】方式进行考察，其中 D 为切入口，执行进程 D 需要进程 A、B、C 都完成，即 P(Sa)、P(Sb)、P(Sc)
• PV 操作成对出现，由此定位 V(Sa)、V(Sb)、V(Sc)
• 进程 E 需要进程 D 完成，所以进程 E 为 P(Sd)，最后定位出 V(Sd)

2.1.5 死锁及银行家算法（☆☆☆☆）

死锁问题

进程管理是操作系统的核心，但如果设计不当，就会出现死锁的问题。如果一个进程在等待一件不可能发生的事，则进程就死锁了。而如果一个或多个进程产生死锁，就会造成系统死锁。

案例分析

系统有 5 个进程：A、B、C、D、E。这 5 个进程都需要 4 个系统资源。则系统至少需要多少个资源，才不可能发生死锁？

分析过程：

• 给所有进程提供（所需 -1）个系统资源，系统自己保留一个资源进行自由支配，此时不可能产生死锁
• 因此题目中至少需要：5 * (4 - 1) + 1 = 16 个资源才不可能发生死锁

形成死锁的四个必要条件

• 互斥：即资源的排他性使用，资源只能被一个进程占用
• 保持和等待：进程请求资源未果，进入阻塞，但仍占有资源
• 不剥夺：资源已被进程占用，未使用完前其资源不能被剥夺
• 环路等待：资源占用形成环路，P0 在等 P1 占用的资源，P1 在等 P0 占用的资源

有序资源分配法

给每个进程都提供充足的资源 —— 非常浪费

银行家算法：分配资源的原则

• 当一个进程对资源的最大需求量不超过系统中的资源数时，可以接纳该进程
• 进程可以分期请求资源，但请求的总数不能超过自身的最大需求量
• 当系统现有剩余的资源不能满足进程所需的资源数时，对进程的请求可以推迟分配，但总能使进程在有限的时间里得到资源（需要等待其他进程归还资源）

案例分析

假设系统中有三类互斥资源 R1、R2、R3，可用资源分别是 9、8、5。在 T0 时刻系统中有 P1、P2、P3、P4 和 P5 五个进程，这些进程对资源的最大需求量和已分配资源数如下所示，如果进程按序列执行，那么系统状态是安全的。

分析过程：

剩余资源数：（210）—— 满足 P2，释放资源 ——（210+211=421）—— 满足P4，释放资源 ——（421+120=541）……

因此选：B

2.2 存储管理

2.2.1 基本概念

逻辑地址 = 虚拟地址 = 相对地址 = 程序地址：一个连续的地址单元，方便表示进程数据的存放。在进程查找数据时，需要配合页表，定位到其物理地址。

物理地址 = 绝对地址：数据保存在内存中的真实地址

• 逻辑地址空间 = 地址空间：逻辑地址的集合
• 物理地址空间 = 存储空间：物理地址的集合

2.2.2 页式存储

基本原理

页式存储的前提是，逻辑地址空间和物理地址空间均分成同样大小的块，其中：

• 逻辑地址空间的每个块称为：逻辑页 = 虚页 = 页面 = 页（page）
• 物理地址空间的每个块称为：物理页 = 实页 = 页框 = 页帧（frame）= 块（block）

每个块的大小一般是 ½KB～4KB 之间的数值（太小寻址频繁，太大碎片问题严重浪费内存），而且必须是 2 的幂次方。

• 逻辑地址空间中逻辑页的编号称为：逻辑页号；其寻址地址为：（逻辑页号，页内地址）
• 物理地址空间中页框的编号称为：页框号；其寻址地址为：（页框号，页内地址）

在实际作业时，系统会对程序进行分页（分页在逻辑地址空间中是连续的，其最后一页大概率没有填满，其多余的空间即是空间碎片），然后一次性把程序的全部页面装入内存（每个页所占的内存块可以不连续，也没有先后顺序）。页与块因为大小一致，所以每个一一对应的页和块，其内部【页内地址 = 业内偏移量】所对应的数据都是一致的。

每个页和块的映射表称为页表。由于每个一一对应的页和块，其内部页内地址所存储的数据都是一致的，所以页表只有两列：页号、块号。

1. 一个进程对应一张页表
2. 进程的每一页对应一个页表项
3. 每个页表项由【页号】和【块号】组成
4. 页表用于记录【进程页面】和【实际存放的内存块】之间的对应关系
5. 每个页表项的长度是相同的，页号是“隐含”的（即逻辑页号是连续的）

进程的每次寻址都需要访问两次内存：

为了加快数据的寻址速度，可以将页表中常用以及正在使用的页表项放置在寄存器中形成【块表】。

多级页表

示例：一段长度为 16 的程序，划分为多级页表。此时需要获取物理地址为 10 的数据：

反置页表 Inverted page tables

反置页表可以优化页表的大小，节省内存空间

因为每个进程配置一张页表，也就是说，如果有 n 个进程，那么内存中就会有 n 张页表。页表的大小会随着进程的增加而增加。所以，如果有很多进程同时运行，那么内存中将会有很大一部分被页表占用。多级页表并不能解决这个问题，因为多级页表也是一个进程维护一张页表。反置页表可以解决这个问题。

• 页表中页框号的列省略了，是因为页框号是一个递增的编码，即【页表项的序号就是页框号】
• 进程号可以使用 Hash 编码，以加快数据的寻址速度
• 反置页表也可以将常用以及正在使用的页表项放到寄存器中，以加快寻址速度

优缺点分析

优点：内存利用率高，不会产生外部碎片，只会有少量的页内碎片；打破了存储分配的连续性要求。

缺点：可能产生抖动现象（属于同一个程序逻辑但是不同块号的数据之间相互调用），导致系统开销增加，同时也不方便按照逻辑模块实现信息的共享和保护。

2.2.3 段式存储

基本原理

• 逻辑地址空间分配规则：按照程序自身的逻辑关系划分为若干段，每个段都有一个段名（在低级语言中，程序员使用段名来编程），每段从0开始编址。
• 物理地址空间分配规则：以段为单位进行分配，每个段在内存中占连续空间，但各段之间不一定相邻。

在分段系统中，其寻址地址规则为：（【段号 = 段名】，【段内地址 = 段内偏移量】）

每一个程序都有一个对应的段表，段表保存在内存中，属于进程的现场信息。

段号列是从 0 开始递增的，因此可以省略。

段式存储完整寻址逻辑：

动态连接

在一个程序运行开始时，只将主程序段装配好并调入主存。其它被分成各段的函数装配是在主程序段运行过程中逐步进行的。每当需要调用一个新段时，才会将这个新段装配好，并与主程序段连接。

动态连接是页式存储难以做到的，因为页式存储的逻辑地址是一维的（通过一个页号就可以找出其对应的块号）。

信息的保护与共享

段式存储比页式存储更容易实现信息的共享与保护。页式存储按块的固定大小切分程序而不在乎其逻辑，抖动现象也由此产生。

段式存储 VS 页式存储

页是信息的【物理单位】；
段是信息的【逻辑单位】。

分页的主要目的是为了实现离散分配，提高内存利用率，会产生少量的页内碎片，不会产生外部碎片；
分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。没有页内碎片，但是会产生外部碎片。

分页对用户是不可见的，仅仅是系统管理上的需要，完全是系统行为；
分段对用户是可见的，用户编程时需要显式地给出段名。

页的大小固定且由系统决定；
段的长度不固定，决定于用户编写的程序。

分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址；
分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。

分段比分页更容易实现信息的共享和保护。不能被修改的代码称为纯代码或可重入代码（不属于临界资源），这样的代码是可以共享的。可修改的代码是不能共享的。

分页（单级页表）和分段访问数据都需要两次访问内存：1、查询内存中的页表；2、访问目标内存单元。
同样也都可以引入快表的方式，将近期访问过的页（段）表项放到快表中，减少一次对内存的访问，加快地址变换速度。

2.2.4 段页式存储（☆☆☆☆）

段页式存储：段式与页式的综合体。程序中的进程先按段式划分；然后对分段按页式划分。每个段大小不同，每个页的大小相同。

逻辑地址结构：（段号，页号，页内地址）

寻址过程

第一次访问内存：在根据【段号S】在寄存器中查询到分段的长度后，查询【段表】；由【页表长度】字段，进一步细分得到分段经过分页后的【页表】存放地址（即页表存放块号）

第二次访问内存：根据【页表存放块号】找到【页表】，代入【页号P】进行查询，得到逻辑空间中的分页在内存中的物理地址（内存块号）

第三次访问内存：根据分页在内存中的物理地址，代入【页内偏移量W】，定位到具体数据在内存中的真实地址

优缺点分析

优点：保留了分段和分页存储管理的全部优点；提供了虚存空间，能更有效利用主存。

缺点：增加了硬件成本；系统复杂度较大。

2.2.5 页面置换算法（☆）

• 最优（Optimal，OPT）算法：不常用的数据从页表或段表中删除，常用的数据保留（太理想）
• 随机（RAND）算法
• 先进先出（FIFO）算法：有可能产生“抖动”，需要经常使用的数据有可能在页表或段表中反复添加和删除
• 最近最少使用（LRU）算法：不会“抖动”，LRU 的理论依据是“局部性原理”（现今计算机所使用的方式）
  • 时间局部性：刚被访问的内容，立即又被访问
  • 空间局部性：刚被访问的内容，邻近的空间很快被访问

2.2.6 磁盘管理

2.2.7 磁盘调度算法

• 先来先服务（FCFS）
• 最短寻道时间优先（SSTF）：根据刷头所在的位置，先访问最近的数据 B，而不考虑最先请求的是数据 A
• 扫描算法（SCAN）：刷头在旋转的磁盘中碰到哪个数据就取哪个
• 循环扫描（CSCAN）算法：扫描算法对磁盘最内和最外磁道上的数据访问效果最差，所以加上一个循环，刷头从外向内，然后再跳到最外，反复扫描磁盘，不考虑数据的远近和时间上的先后顺序

2.2.8 读取磁盘数据时间计算

读取磁盘数据的时间应包括以下三个部分：

1. 找磁道的时间
2. 找块（扇区）的时间，即旋转延迟时间
3. 传输时间

某磁盘磁头从一个磁道移至另一个磁道需要 10ms。文件在磁盘上非连续存放，逻辑上相邻数据块的平均移动距离为 10 个磁道，每块的旋转延迟时间及传输时间分别为 100ms 和 2ms，则读取一个 100 块的文件需要 ( (10*10 ) +100+2 )*100 = 20200 ms 时间

A.10200 B.11000 C.11200 D.20200

2.3 作业管理

作业状态与作业管理

作业调度算法

• 先来先服务法
• 时间片轮转法：时间片到点了就切换作业，无论作业是否已经完成
• 短作业优先发
• 最高优先权优先法：按作业的优先级排序
• 高响应比优先法：按作业的响应比排序（响应比：作业等待时间 ÷ 作业执行时间）

2.4 文件管理

索引文件（☆☆）

绝对路径与相对路径（☆☆☆）

图中是 Linux 系统的文件目录结构，其中【/】是根节点。以 F2 为例：

• 绝对路径：/D1/W2/F2
• 相对路径：W2/F2

位示图（☆☆）

空闲存储空间的管理，一般出题是求存储容量

2.5 设备管理

2.5.1 数据传输控制方式

程序控制（查询）方式【效率最低】 ——> I/O 处理机【效率最高】

这里主要考察 DMA 方式

• 程序控制（查询）方式：分为无条件传送和程序查询方式两种。方法简单，硬件开销小，但 I/O 能力不高，严重影响 CPU 的利用率
• 程序中断方式：与程序控制方式相比，中断方式因为 CPU 无需等待而提高了传输请求的响应速度
• DMA 方式：DMA 方式是为了在主存与外设之间实现高速、批量数据交换而设置的。DMA 方式比程序控制方式与中断方式都高效（整个过程不需要 CPU 参与，CPU 只用发出控制指令，所有事情交给硬件完成，结束后把结果返回给 CPU 即可）
• 通道方式
• I/O 处理机
• 采用 DMA 方式传送数据时，每传送一个数据都需要占用一个存储周期【速记】

2.5.2 虚设备与 SPOOLING 技术（☆）

SPOOLING 技术是关于慢速字符设备如何与计算机主机交换信息的一种技术（打印技术），通常称为“假脱机技术”。SPOOLING 技术通过磁盘实现。

拿打印机举例：此时只有一台打印机，但计算机中有2个进程（word 进程和 pdf 进程）需要进行打印，这时两个进程都认为自己拥有一个打印机。但是不是就真的有 2 台打印机了呢？当然不是，明明是只有一台打印机。这就是通过虚拟化技术欺骗了 2 个无知的进程。进程需要打印的信息会缓存到一个队列中等待空闲的打印机调用。

三、数据系统

选择题（6~8）与简答题都有涉及

3.1 数据库模式（☆☆）

三级模式 - 两层映射

三级模式：

• 外模式 = 用户模式（视图级）：面向用户和应用程序打交道，暴露接口实现用户逻辑
• 概念模式 = 模式（表级）
• 内模式 = 存储模式（文件级）：数据结构的物理存储

两层映射：让数据与程序分离

• 外模式 - 概念模式映射：数据的逻辑独立性，【程序的逻辑结构】发生的变化不会影响到其他模式，只需要改变模式之间的映射关系
• 概念模式 - 内模式映射：数据的物理独立性，【数据在物理结构】发生的变化不会影响到其他模式，只需要改变模式之间的映射关系

3.2 数据库设计过程

四个阶段：

• 需求分析：该阶段产物为：数据流图（简答题15）、数据字典、需求说明书
• 概念结构设计：该阶段产物为：ER 模型（简答题15）
• 逻辑结构设计：该阶段产物为：关系模式（开始建表）
• 物理设计

3.3 ER 模式（☆☆☆☆☆）

一个实体转换为一个关系模式

联系转关系模式

总结：

• 1:1 联系时，联系的属性挂到哪个实体都可以
• 1:n 联系时，联系的属性要挂到多的一方实体
• m:n 联系时，联系的属性要抽出来，结合两边实体的主键形成一张中间表

三个以上实体间的多元联系

此时 ABC 三个实体三个关系模式，联系结合三方实体的主键，再加上自己的属性（如果有的话），单独形成一个关系模式，所以答案是：4。

3.4 关系代数（☆☆☆）

并：S1 ∪ S2（3 个属性）

交：S1 ∩ S2（3 个属性）

差：S1 - S2 或者 S2 - S1（3 个属性）

笛卡尔积：S1 × S2（3 + 3 = 6 个属性）

投影：π_Sno,Sname(S1) = π_1,2(S1)：按列投影

选择：δ_Sno=No0003(S1) = δ_1=No0003(S1)：按行选择

联接：S1 ⋈ S2 = π_{S1.Sno,S1.Sname,S1.Sdept,S2.Age}(δ_{S1.Sno=No0001,S2.Sno=No0001}(S1 × S2))，利用投影 + 选择在笛卡尔积中筛选出联接的结果。

3.5 规范化理论（☆☆☆☆☆）

关系模型 R（学生姓名，选修课程名，任课教师名，任课教师地址）

• 数据冗余：只要有数据冗余就会有下面的三种异常，因此要对数据进行规范化。像关系模型 R 中可以对关系模型进行拆分，去除冗余的数据。
• 修改异常
• 插入异常
• 删除异常

在依赖集 2 中，由 A → B，B → C，可得出 A → C，这就是：传递函数依赖。

3.5.1 键

• 候选键：可以唯一标识元组（元组可以理解为表里的一行记录），且无冗余。任选一个作为【主键】。
• 外键：其他关系的主键

3.5.2 求候选键

图示法求候选键（选择 + 简答）

1. 将关系到函数依赖关系，用“有向图”的方式表示。
2. 找出入度为 0 的属性，并以该属性集合为起点，尝试遍历有向图，若能正常遍历图中所有结点，则该属性集即为关系模式的候选键。（A → B，则 A 的入度为 0，B 的入度为 1）
3. 若入度为 0 的属性集不能遍历图中所有结点，则需要尝试性的将一些中间结点（既有入度，也有出度的结点）并入入度为 0 的属性集中，直至该集合能遍历所有结点，集合为候选键。

3.5.3 主属性与非主属性

组成【候选码】的属性就是主属性，其他的就是非主属性。

示例：关系模式 CSZ（CITY，ST，ZIP），其属性组上的函数依赖集为：F = {（CITY，ST）→ ZIP，ZIP → CITY}

其中 CITY 表示城市，ST 表示街道，ZIP 表示邮政编码。

则关系模式 CSZ 的主属性为：CITY，ST，ZIP（注意 ST 不能单独推导出 ZIP）

3.5.4 范式

第一范式（1NF）：在关系模式 R 中，当且仅当所有域只包含原子值，即每个属性都是不可再分的数据项，则称关系模式 R 是第一范式。

第二范式（2NF）：当且仅当关系模式 R 是第一范式（1NF），且**每一个非主属性完全依赖候选键（没有不完全依赖）**时，则称关系模式 R 是第二范式。

例如：AB → C，B → D。此时 D 对候选键 A 不完全依赖，该关系模式不满足第二范式。

第三范式（3NF）：当且仅当关系模式 R 是第二范式（2NF），且 R 中没有非主属性传递依赖于候选键时，则称关系模式 R 是第三范式。

BC 范式（BCNF）：设 R 是一个关系模式，F 是它的依赖集，当且仅当 F 中每个依赖的决定因素必定包含 R 的某个候选码时，则关系模式 R 属于 BCNF。

例如：AB → C，C → B。此时依赖 AB 和 AC 必定包含候选码 A，则该关系模式为 BCNF。

【速记】

$范式 \begin{cases} 第一范式（1NF）：属性值都是不可再分的原子值 \\ 第二范式（2NF）：消除非主属性对候选键（候选码）的部分依赖 \\ 第三范式（3NF）：消除非主属性对候选键（候选码）的传递依赖 \\ BC范式（BCNF）：所有属性都完全依赖于候选键（候选码），即在关键因素中一定包含候选键（候选码） \end{cases}$

示例A：R=(A, B, C)，F={A→B, B→A, C→A}

{C→A, A→B}；传递依赖，因此是 2NF

示例B：R=(A, B, C, D)，F={B→D, D→B, AB→C}

{B→D, D→B}；内部自己消化，都当作候选键处理。候选键为：(A, B, D)，但属性 C 不完全依赖于候选键，因此是 3NF

示例C：R=(A, B, C)，F={A→B, B→A, A→C}

{A→B, B→A}；内部自己消化，都当作候选键处理。所以消化处理后{B→A, A→C}的传递依赖就不存在了，3NF 满足。

因为 A=B，所以属性 C 完全依赖候选键(A, B)，满足 BCNF

3.5.5 模式分解

保持函数依赖分解：设数据库模式 ρ={R1，R2，……，Rk} 是关系模式 R 的一个分解，F 是 R 上的函数依赖集，ρ 中每个模式 Ri 上的 FD 集是 Fi。如果 {F1，F2，……，Fk} 与 F 是等价的（即相互逻辑蕴涵），那么称分解 ρ 保持 FD。

例：设关系模式 R(U, F)，其中U={A, B, C, D, E}，F={A → BC, C → D, BC → E, E → A}，则分解 ρ={R1(ABCE)，R2(CD)} 保持了函数依赖。而分解 ρ={R1(ABE)，R2(CD)} 没有保持函数依赖。

3.5.6 无损分解

指将一个关系模式分解成若干个关系模式后，通过自然联接和投影等运算仍能还原到原来的关系模式。

• 有损:不能还原
• 无损:可以还原

3.6 SQL 语言（☆☆☆☆）

选择题

增加主键约束【add constraint, primary key】

1
2
3
4
5
6
7
8
9
10

-- 建表时
CREATE TABLE user (
    id varchar(60) NOT NULL COMMENT '主键ID',
    username varchar(60) NOT NULL COMMENT '用户名',
    PRIMARY KEY (id)
);

-- 建表后
ALTER TABLE 表名 ADD CONSTRAINT 主键名称 PRIMARY KEY(设主键的列名);
ALTER TABLE emp ADD CONSTRAINT pk_eno PRIMARY KEY(eno);

增加外键约束【constraint, foreign key, references】

1
2
3
4
5
6

-- 建表时
FOREIGN KEY(从表字段名) REFERENCES 主表名(主表字段名);

-- 建表后
ALTER TABLE 从表名 CONSTRAINT 外键名 FOREIGN KEY(从表字段) REFERENCES 主表名(主表字段名);
ALTER TABLE dept CONSTRAINT fk_employee_dept FOREIGN KEY(dept_no) REFERENCES employee(dept_no);

增加条件约束【unique】

1
2
3
4
5
6
7
8
9
10

-- 建表时
CREATE TABLE user (
    id varchar(60) NOT NULL COMMENT '主键ID',
    username varchar(60) NOT NULL UNIQUE COMMENT '用户名',
    PRIMARY KEY (id)
);

-- 建表后
ALTER TABLE 表名 ADD UNIQUE (字段1, 字段2, ......); 
ALTER TABLE emp ADD UNIQUE (un_eno);

3.6.1 并发控制（☆☆）

事务的 ACID 属性【速记】

• 原子性【A】：一个事务中所包含的全部 SQL 语句是一个执行整体，不可分割，要么全执行，要么全取消。
• 一致性【C】：即数据库在事务操作前和事务处理后，其中的数据必须都要满足业务规范约束。如果在事务中出现错误，那么系统中的所有变化将自动地回滚，系统返回到原始状态。
• 隔离性【I】：指的是多个事务并发地独立运行，而不能互相干扰，事务提交时根据当前数据库状态进行操作。
• 持久性【D】：也称为永久性，指的是事务在处理结束后，对数据库的修改是永久性的，即使系统故障也不会丢失。

并发产生的问题【速记】

• 脏读：读到了其他事务未提交的脏数据。
  例如：事务 B 执行过程中修改了数据 X，在未提交前，事务 A 也读取了 X，但事务 B 却回滚了，这样事务 A 就形成了脏读。
• 不可重复读：在一个事务内，最开始读到的数据和事务结束前任意时刻读到的同一批数据出现不一致的情况。
  例如：事务 A 先读取了一条数据，然后再执行逻辑的时候，事务 B 将这条数据改变了，然后事务 A 再次读取该数据，发现数据不匹配，这就是所谓的不可重复读。
• 幻读：事务的某次 select 操作得到的结果所表示的数据状态无法支撑其后续的业务操作。
  例如：事务 A select 某条记录是否存在，不存在，准备插入此记录，但执行 insert 操作的时候发现此记录已存在，此时就产生了幻读。

封锁协议【速记】

• 共享锁【S锁】：事务对数据对象加 S 锁后，加锁事务对数据对象只能读而不能改，其他事务也一样，并且只能追加 S 锁而不能加 X 锁。
• 排他锁【X锁】：事务对数据对象加 X 锁后，加锁事务对数据对象可以读也可以改，但其他事务不能读也不能改，并且不能追加锁。

3.6.2 数据库完整性约束（☆）

• 实体完整性约束：主键 —— 非空且唯一
• 参照完整性约束：外键 —— 可以为空，但有值的话必须指向正确的记录
• 用户自定义完整性约束：UNIQUE 之类
• 触发器：……

四、计算机网络与信息安全（5+3）

4.1 计算机网络-开放系统互联参考模型（☆☆）

OSI/RM 七层模型

ARP：地址解析协议（IP 转成 MAC 地址）；RARP：地址反向解析协议（MAC 地址转成 IP）

4.2 计算机网络-TCP/IP 协议族（☆☆☆☆）【速记】

4.3 计算机网络-IP 地址与子网划分（☆☆☆☆☆）

IP 地址

A 类地址：0.0.0.0 ~ 127.255.255.255

• 网络位（8bit）：范围从 0000 0000 到 0111 1111（1000 0000 - 1），即 0 ~ 2⁸-1 = 0 ~ 128-1 = 0 ~ 127
• 地址位（24bit）：范围是：0 ~ 2²⁴-2（因为要去除全为 0 和全为 1 的两个掩码地址）

B 类地址：128.0.0.1 ~ 191.255.255.255

C 类地址：192.0.0.0 ~ 223.255.255.255

子网划分（选择题）

示例1：将 IP 地址 168.195.0.0 划分成 27 个子网，子网掩码为多少？

∵ 2⁴(16) < 27 < 2⁵(32)

∴ 主机位从左往右数 5 位置 1，即从：0000 0000 0000 0000 ~ 1111 1000 0000 0000

后 8 位 0 省略：1111 1000 = 2⁸-1-2²-2¹-2⁰ = 256-1-4-2-1 = 248，所以子网掩码为：168.195.248.0

示例2：将 IP 地址 168.195.0.0 划分成若干子网，每个子网内有主机 700 台，则子网掩码为多少？

∵ 2⁹(512) < 700 < 2¹⁰(1024)

∴ 主机位从右往左数 10 位置 0，即从：0000 0000 0000 0000 ~ 1111 1100 0000 0000

后 8 位 0 省略：1111 1100 = 2⁸-1-2¹-2⁰ = 256-1-2-1 = 252，所以子网掩码为：168.195.252.0

4.4 计算机网络-网络规划与设计（☆）

需求分析

• 网络功能要求
• 网络性能要求
• 网络运行环境要求
• 网络可扩充性和可维护性要求

网络规划原则

• 实用性原则
• 开放性原则
• 先进性原则

网络设计实施原则

• 可靠性原则
• 安全性原则
• 高效性原则
• 可扩展性原则

层次化网络设计

• 核心层
• 汇聚层
• 接入层

4.5 计算机网络-计算机网络分类

3G 与 4G 标准（☆☆）

4.6 计算机网络-网络接入技术

• 有线接入：公用交换电话网络（PSTN）、数字数据网（DDN）、综合业务数字网（ISDN）、非对称数字用户线路（ADSL）、同轴光纤技术（HFC）
• 无线接入：IEEE 802.11（WIFI）、IEEE 802.15（蓝牙 Bluetooth）、红外（IrDA）、WAPI

4.7 计算机网络-HTML 语言（☆☆）

4.8 信息安全-对称加密与非对称加密（☆☆☆）

4.8.1 对称加密

K_e = K_d

特点：加密强度不高，但效率高；密钥分发困难

常见对称密钥加密算法：DES、3DES（三重 DES）、RC-5、IDEA 算法

4.8.2 非对称加密

K_e ≠ K_d，密钥必须成对使用（公钥加密，对应的私钥解密）

特点：加密速度慢，但强度高

常见非对称密钥加密算法：RSA、ECC

1. 非对称加密可以反向加密和解密吗？
   非对称加密算法可以反向使用，也就是用私钥加密、公钥解密或者用公钥加密、私钥解密。但一般情况下，非对称加密算法都是采用“公钥加密、私钥解密”的方式，因为这种方式更安全。如果采用“私钥加密、公钥解密”的方式，则可能会导致私钥泄露而造成安全问题。
2. 只能单向加密和解密的非对称加密算法：只能单向加密的单向散列函数被称为哈希函数，常见的哈希函数包括 MD5、SHA-1 和 SHA-256 等。相较于非对称加密算法，哈希函数具有不可逆性，无法逆向还原出原始数据，因此适用于存储密码等敏感信息。另外，还有一种伪随机函数 HMAC，它是基于哈希函数构建的，可以提高哈希函数的安全性，通常用于计算消息认证码（MAC）。需要注意的是，哈希函数不具备加密和解密的概念，而是将数据映射成固定长度的摘要值，自然也不属于对称或非对称加密。
3. 可以双向加密和解密的非对称加密算法：在非对称加密算法中，常用的可以双向加密和解密的算法包括 RSA、ElGamal、ECC 等。这些算法都采用了公钥加密、私钥解密的方式，同时也能够采用私钥加密、公钥解密（但并不建议使用）。在这些算法中，RSA 是最为常见的算法之一，它基于大整数的因数分解难题，可用于数字签名、加密通信等场景。与哈希函数不同的是，RSA 等非对称加密算法具有加密和解密的过程，能够将明文转换为密文，并把密文还原为原始数据。

4.8.3 速记

对称加密简单速度快，所以常用于大量明文信息的加密传输。

$关于信息安全的加密方式 \begin{cases} 对称加密：DES、RC-5 \\ 非对称加密但可逆：RSA（X.509数字证书标准）、ECC（国密SM2数字证书） \\ 单向加密不可逆（单向散列函数，不属于非对称算法）：MD5、SHA-1、SHA-256 \end{cases}$

4.9 信息安全-信息摘要与数字签名（☆☆）

数字签名

基于非对称加密算法，但是反向：用私钥进行加密，公钥解密验证信息的正确性（包括 RSA、ECC 等非对称加密算法，可以反向加密和解密）

信息摘要

基于非对称加密算法，但是只能单向加密和解密，具有不可逆性。（包括 MD5、SHA-1 和 SHA-256 等非对称算法，只能单向加密和解密）

4.10 PKI 公钥体系

信息安全-数字证书（☆☆）

4.11 网络安全-各个网络层次的安全保障

信息安全-网络安全协议（☆☆☆）

4.12 网络安全-主动攻击与被动攻击【速记】

$网络攻击 \begin{cases} 主动攻击【认证阻止主动攻击】 \begin{cases} 拒绝服务攻击（DOS） \\ 会话拦截 \\ 修改数据命令 \end{cases}\\ 被动攻击【加密阻止被动攻击】 \begin{cases} 系统干涉 \end{cases} \end{cases}$

信息安全-防火墙技术与网络攻击（☆☆☆）

• 主动攻击：中断（可用性）；篡改（完整性）；伪造（真实性）
• 被动攻击：监听（保密性）：消息内容获取；业务流分析

DoS（拒绝服务）与DDoS

DOS 是指 Denial of Service（拒绝服务）攻击，DDOS 是指 Distributed Denial of Service（分布式拒绝服务）攻击。两者的基本概念是一致的：攻击者通过在网络中发送过多数据流量或请求，使目标系统无法正常处理、响应其他合法用户的请求，从而导致该系统的服务不能正常提供。

• DOS 攻击针对单个主机或服务器，攻击者向目标主机或服务器发送大量无效或欺骗性的请求或网络数据包，以耗尽目标主机或服务器的资源（如 CPU、内存、硬盘等），从而使其无法处理更多合法的请求
• DDOS 攻击则是操作多台“肉鸡”协同发起攻击，通常采用僵尸网络（Botnet）等手段将攻击流量分散到多个来源，以达到更强的攻击效果

DOS 和 DDOS 攻击都是网络安全领域的常见威胁，可以造成系统瘫痪、信息丢失、服务不可用等损失。为了防范这种攻击，需要采取各种技术措施，例如限制连接数、地址过滤、流量清洗、负载均衡等，同时也需要做好系统安全加固、漏洞修复等工作。

防火墙

网络级防火墙

• 包过滤：检查通过的 IP 数据封包（数据包的格式以及来源地址），并进一步处理。主要的处理方式有：放行、丢弃或拒绝，以达到保护自身网络的目的。（速度快但安全性低）
• 代理服务器：针对每一种应用服务程序进行代理服务的工作。一方面代替原来的客户建立连接，另一方面代替原来的客户程序，与服务器建立连接。它可确保数据的完整性，只有特定的服务才会被交换；还可进行高阶的存取控制，并可对其内容进行过滤。（检查包里的内容，速度慢但安全性高）
• 状态检测：采用了一种基于连接的状态检测机制，将属于同一连接的所有数据包作为一个整体的数据流来看待（TCP 的三次握手包），构成连接状态表，通过安全规则与状态表的共同配合来决定数据包的“去留”。综合了包过滤防火墙和代理服务器防火墙的优点，速度快且安全性高。

应用级防火墙：

• 双穴主机：内部网络 —— 双穴主机 —— 互联网环境（内网对外不可见）
• 屏蔽主机：内部网络 —— 堡垒主机 —— 屏蔽路由器 —— 互联网环境
• 屏蔽子网：内部网络 —— 路由器 —— 被屏蔽的子网（堡垒主机、Web 服务器）—— 路由器 —— 互联网环境

安全防范体系

1. 物理环境的安全性：包括通信线路、物理设备和机房的安全等。物理层的安全性主要体现在通信线路的可靠性（线路备份、网管软件和传输介质)、软硬件设备的安全性（替按设备、拆卸设备、增加设备）、设备的备份、防灾害能力、防干扰能力、设备的运行环境（温度、湿度、烟尘）和不间断电源保障等。
2. 操作系统的安全性：主要表现在三个方面，一是操作系统本身的缺陷带来的不安全因素，主要包括身份认证、访问控制和系统漏洞等；二是对操作系统的安全配置问题；三是病毒对操作系统的威胁。
3. 网络的安全性：网络层的安全问题主要体现在计算机网络方面的安全性，包括网络层身份认证、网络资源的访问控制、数据传输的保密与完整性、远程接入的安全、域名系统的安全、路由系统的安全、入侵检测的手段和网络设施防病毒等。
4. 应用的安全性：由提供服务所采用的应用软件和数据的安全性产生，包括 Web 服务、电子邮件系统和 DNS 等。此外，还包括病毒对系统的威胁。
5. 管理的安全性：包括安全技术和设备的管理、安全管理制度、部门与人员的组织规则等。管理的制度化极大程度地影响着整个计算机网络的安全，严格的安全管理制度、明确的部门安全职责划分与合理的人员角色配置，都可以在很大程度上降低其他层次的安全漏洞。

4.13 信息安全-计算机病毒与木马（☆☆☆）

• 病毒：编制或者在计算机程序中插入的破坏计算机功能或者破坏数据，影响计算机使用并且能够自我复制的一组计算机指令或者程序代码。
• 木马：计算机木马是一种后门程序，常被黑客用作控制远程计算机的工具。

五、系统开发基础（总11）

5.1 开发模型（☆☆☆☆☆）

瀑布模型

• 定义阶段：软件计划、需求分析

V 模型

喷泉模型

原型化模型

适合于开发高风险项目

演化模型

螺旋模型

螺旋模型 = 瀑布模型（各个阶段） + 原型模型（迭代一、迭代二、……），特别适用于大型复杂的系统。

统一过程

用例驱动、以架构为中心、迭代和增量

• 初始
  • 确定项目范围和边界
  • 识别系统的关键用例
  • 展示系统的候选架构
  • 估计项目费用和时间
  • 评估项目风险
• 细化
  • 分析系统问题领域
  • 建立软件架构基础
  • 淘汰最高风险元素
• 构建
  • 开发剩余的构件
  • 构件组装与测试
• 交付
  • 进行＆测试
  • 制作发布版本
  • 用户文档定稿
  • 确认新系统
  • 培训、调整产品

敏捷方法

1. XP（Extreme Programming，极限编程）在所有的敏捷型方法中，XP 是最引人瞩目的它源于 Smalltalk 圈子，特别是 Kent Beck 和 Ward Cunningham 在 20 世纪 80 年代末的密切合作。XP 在一些对费用控制严格的公司中的使用，已经被证明是非常有效的。
2. Cockburn 的水晶系列方法，水晶系列方法是由 Alistair Cockburn 提出的。它与 XP 方法一样，都有以人为中心的理念，但在实践上有所不同。Alistair 考虑到人们一般很难严格遵循一个纪律约束很强的过程，因此，与 XP 的高度纪律性不同，Alistair 探索了用最少纪律约束而仍能成功的方法，从而在产出效率与易于运作上达到一种平衡。也就是说，虽然水晶系列不如 XP 那样的产出效率，但会有更多的人能够接受并遵循它。
3. 开放式源码，这里提到的开放式源码指的是开放源码界所用的一种运作方式。开放式源码项目有一个特别之处，就是程序开发人员在地域上分布很广，这使得它和其他敏捷方法不同，因为一般的敏捷方法都强调项目组成员在同一地点工作。开放源码的一个突出特点就是查错排障（debug）的高度并行性，任何人发现了错误都可将改正源码的“补丁”文件发给维护者。然后由维护者将这些“补丁”或是新增的代码并入源码库。
4. SCRUM。SCRUM 已经出现很久了像前面所论及的方法一样，该方法强调这样一个事实，即明确定义了的可重复的方法过程只限于在明确定义了的可重复的环境中，为明确定义了的可重复的人员所用，去解决明确定义了的可重复的问题。
5. Coad 的功用驱动开发方法（FDD-Feature Driven Development）
   FDD 是由 Jeff De Luca 和大师 Peter Coad 提出来的。像其他方法一样，它致力于短时的选代阶段和可见可用的功能。在 FDD 中，一个选代周期一般是两周。
   在 FDD 中，编程开发人员分成两类：首席程序员和“类”程序员（class owner）。首席程序员是最富有经验的开发人员，他们是项目的协调者、设计者和指导者，而“类”程序员则主要做源码编写。
6. ASD 方法，ASD（Adaptive Software Development）方法由 Jim Hiqhsmith 提出，其核心是三个非线性的、重叠的开发阶段：猜测、合作与学习。

5.2 软件开发方法（☆）

结构化方法（面向数据流，不适用于大型复杂项目）

• 用户至上
• 严格区分工作阶段，每阶段有任务和结果
• 强调系统开发过程的整体性和全局性
• 系统开发过程工程化，文档资料标准化
• 自顶向下，逐步分解（求精）

原型法

面向对象方法（喷泉模型）

• 更好的复用性
• 关键在于建立一个全面、合理、统一的模型
• 分析、设计、实现三个阶段，界限不明确

面向服务的方法（SOA）

5.3 需求分析（☆）

需求的任务

需求的过程

• 问题识别
• 分析与综合
• 编制需求分析文档
• 需求分析与评审

需求的分类

• 功能需求
• 非功能需求
• 设计约束

应用的工具

• 数据流图（DFD）
• 数据字典（DD）
• 判定表
• 判定树

5.4 软件设计（☆☆）

软件设计的任务与活动

模块合计原则（高内聚低耦合）

可能考察【内聚度】或【耦合度】的顺序；或者类型与描述内容的对应（可能性略低）

应用的工具

• IPO 图：输入处理输出图
• PDL：程序描述语言
• PAD：问题分析图
• 程序流程图
• N/S 盒图

5.5 软件测试与维护

软件测试

• 动态测试
  • 黑盒测试法
  • 白盒测试法
  • 灰盒测试法
• 静态测试
  • 桌前检查
  • 代码审查
  • 代码走查

5.5.1 黑盒测试法

等价类划分

等价类划分法是一种典型的，并且是最基础的黑盒测试用例设计方法。采用等价类划分法时，完全不用考虑程序内部结构，设计测试用例的唯一依据是软件需求规格说明书。

所谓等价类，是输入条件的一个子集合，该输入集合中的数据对于揭示程序中的错误是等价的。从每一个子集中选取少数具有代表性的数据，从而生成测试用例。

等价类又分为有效等价类和无效等价类。有效等价类代表对程序有效的输入，而无效等价类则是其他任何可能的输入（即不正确的输入值）。有效等价类和无效等价类都是使用等价类划分法设计用例时所必须的，因为被测程序若是正确的，就应该既能接受有效的输入，也能接受无效输入的考验。

• 确定无效等价类与有效等价类
• 设计用例尽可能多的覆盖有效类
• 设计用例只覆盖一个无效类

边界值分析

• 处理边界情况时最容易出错
• 选取的测试数据应该恰好等于、稍小于或稍大于边界值

等价类划分 VS 边界值分析 示例

小张帮朋友开发一个成绩分级程序，程序逻辑是：90-100分：优；80-89分：良；70-79分：中；60-69分：及格；0-59分：不及格。对此我们若采用等价类划分以及边界值分析，应该如何设计测试用例。

等价类划分：无效等价类：(-∞, 0) ∪ (100, +∞)；有效类：针对每个成绩的分级输入随机数值进行测试

边界值分析：针对成绩分级的各个临界值进行测试：-1、0、1；59、60、61；69、70、71；79、80、81；89、90、91；99、100、101

错误推测（略）

因果图（略）

5.5.2 V 模型的测试流程【速记】

一般考察的是：在题干中进行的是哪种测试

• 单元测试：测试：模块接口、局部数据结构（功能模块里面的东西）、边界条件、独立的路径、错误处理
• 集成测试：测试：模块间的接口和通信
• 系统测试：测试：设备的硬件环境是否能够支撑一个真实的环境（演示环境）
• 验收测试：以用户为主导的测试：有效性测试、软件配置审查、验收测试

5.5.3 白盒测试法（☆☆☆☆）【速记】

语句覆盖（错误发现能力最弱）＜判定覆盖＜条件覆盖＜路径覆盖（错误发现能力最强）

• 语句覆盖
• 判定覆盖
• 条件覆盖
• 条件判定覆盖
• 路径覆盖

5.5.4 McCabe 复杂度计算（☆☆☆）

V(G) = m-n+2（m：G 中的有效弧数；n：G 中的节点数）

m：10；n：8；V(G) = 10-8+2=4（至少需要 4 个测试用例才能覆盖环路）

也可以数被环路封闭的区域然后 +1，如图中的封闭区域为：3，所以其 McCabe 的复杂度为：3+1=4

5.5.5 软件维护【速记】

主要考察对可维护性因素和软件维护类型的区分

可维护性因素

• 可理解性（文档）
• 可测试性
• 可修改性（是否易于扩展）

软件维护类型（☆☆☆☆）【速记】

• 改正性维护：系统在发布的时候就有问题。
• 适应性维护：应用软件适应信息技术变化和管理需求变化而进行的修改。企业的外部市场环境和管理需求的不断变化也使得各级管理人员不断提出新的信息需求。
• 预防性维护：为了预防将来有可能发生的情况而准备的一系列事情。
• 完善性维护：扩充功能和改善性能而进行的修改。对已有的软件系统增加一些在系统分析和设计阶段中没有规定的功能与性能特征。

软件无故障时间（MTTF）；软件平均修复时间（MTTR）

软件可用性公式：$\frac{MTTF}{MTTF+MTTR}$；软件可维护性公式：$\frac{1}{1+MTTR}$

5.6 软件工程国家标准-软件文档管理指南

按阅读对象分类

主要考察哪些文档属于哪种类型

开发文档（面向技术人员）

• 可行性研究和项目说明书
• 需求规格说明
• 功能规格说明
• 设计规格说明（包括程序和数据规格说明）
• 开发计划
• 软件集成和测试计划
• 质量保证计划、标准、进度
• 安全和测试信息

产品文档（面向用户）

• 培训手册
• 参考手册和用户指南
• 软件支持手册
• 产品手册和信息广告

管理文档（其他）

• 开发过程中每个阶段的进度和进度变化的记录
• 软件变更情况的记录
• 相对于开发的判定记录
• 职责定义

5.7 软件质量保证（☆）

外部和内部质量

主要考察某种特征属于哪种软件质量保证类型

功能性

• 适合性
• 准确性
• 互操作性
• 安全保密性
• 功能性的依从性

可靠性

• 成熟性
• 容错性
• 易恢复性
• 可靠性的依从性

易用性

• 易理解性
• 易学性
• 易操作性
• 吸引性
• 易用性的依从性

效率

• 时间特征
• 资源利用性
• 效率依从性

维护性

• 易分析性
• 易改变性
• 稳定性
• 易测试性
• 维护性的依从性

可移植性

• 适应性
• 易安装性
• 共存性
• 易替换性
• 可移植性的依从性

5.8 软件过程改进（☆☆）

CMMI：软件成熟度模型，可以衡量一个企业达到哪一种资质

主要考察某特征属于哪一个级别

• 初始级：初创型公司，一个牛人支撑一个项目，乃至一家公司（混乱）
• 可管理级：对相同和相似的项目进行管控
• 已定义级：标准化、文档化
• 定量管理级：对软件的过程和质量可以进行度量
• 优化管理级：不断地持续优化改进

5.9 项目管理基础

十大知识领域

• 范围管理
• 时间管理
• 成本管理
• 质量管理
• 人力资源管理
• 沟通管理
• 风险管理（☆☆☆）
• 采购管理
• 整体管理
• 项目干系人管理

Gant 图（甘特图）（☆☆☆☆）

Pert 图（☆☆☆☆）

项目进度管理，找出关键路径，进行活动排序

• 前导图法（单代号网络图，PDM）
• 箭线图法（双代号网络图，ADM）

节点（活动）组成部分：

工作总时差 TF = LS - ES = LF - EF

工作自由时差 FF = ES(b) - EF(a)

5.10 项目管理

风险曝光度（Risk Exposure）：计算方法是：风险出现的概率 × 风险可能造成的损失。

示例：正在开发的软件项目可能存在一个未被发现的错误，而这个错误出现的概率是 0.5%，给公司造成的损失将是 1000000 元，那么这个错误的风险曝光度就应为：1000000 × 0.5% = 5000元。

六、面向对象技术（12）

选择（12）+简答（2道大题：面向对象的基本概念 + 设计模式）

6.1 面向对象的基本概念（☆☆☆☆☆）

• 对象：属性（数据）+ 方法（操作）+ 对象 ID
• 类（实体类/控制类/边界类）
• 继承与泛化：复用机制（让子类拥有父类的属性）
• 封装：隐藏对象的属性和实现细节，仅对外公开接口
• 多态：不同对象收到同样的消息产生不同的结果
• 接口：一种特殊的类，只有方法定义而没有实现
• 重载：一个类可以有多个同名而参数类型不同的方法
• 重写：子类对继承自父类的方法进行重构
• 模板类
• 消息和消息通信：消息是异步通信的

6.1.1 速记

$多态 \begin{cases} 通用多态 \begin{cases} 参数多态：最纯的多态 \\ 包含多态：子类型化，即一个类型是另一个类型的子类型 \end{cases}\\ 特定多态 \begin{cases} 过载多态：同一个名字在不同上下文中所代表的含义不同 \\ 强制多态： \end{cases}\\ \end{cases}$

6.1.2 面向对象设计的 7 大原则

• 单一职责原则：设计目的单一的类
• 开放-封闭原则：对扩展开放，对修改封闭
• 李氏（Liskov）替换原则：子类可以替换父类
• 依赖倒置原则：要依赖于抽象，而不是具体实现；针对接口编程，不要针对实现编程
• 接口隔离原则：使用多个专门的接口比使用单一的总接口要好
• 组合重用原则：要尽量使用组合，而不是继承关系达到重用目的（例如一个变化的行为，继承是通过继承后重写的方式实现，而组合是通过创建不同的行为实例实现）
• 迪米特（Demeter）原则（最少知识法则）：一个对象应当对其他对象尽可能少的了解

6.2 UML（通用建模语言）

区分哪些图属于结构图，哪些图属于行为图

UML活动图用于建模系统内从一个活动到另一个活动的流程

用例图（☆☆☆☆☆）（大题）

类图（☆☆☆☆☆）（选择+大题）【速记】

关联关系 = 聚合关系 + 组合关系

所以总体上是五种关系的类图

• 关联关系：描述了一组链，链是对象之间的连接
  • 聚合关系：整体与部分生命周期不同（部分离开整体后还能单独存活）
  • 组合关系：整体与部分生命周期相同（部分离开整体化不能单独存活）
• 依赖关系：一个事物发生变化影响另一个事物
• 泛化关系：特殊/一般关系（继承关系）
• 实现关系：接口与类之间的关系

顺序图（☆☆☆☆）

通信图（☆☆☆）

状态图（☆☆☆）

活动图（☆☆☆）

6.3 设计模式（☆☆☆☆☆）（选择x4）

主要考察某种模式属于哪一类型的模式

6.3.1 创建型模型【5】

工厂模式（Factory Method）

定义一个创建对象的接口，但由子类决定需要实例化哪一个类。工厂方法使得子类实例化的过程推迟。

• Product：产品角色定义产品的接口。
• ConcreteProduct：真实的产品，实现接口 Product 的类。
• Creator：工厂角色声明工厂方法（Factory Method），返回一个产品。
• ConcreteCreator：真实的工厂实现 Factory Method 工厂方法，由客户调用，返回一个产品的实例。

抽象工厂模式（Abstruct Factory）

提供一个接口，可以创建一系列相关或相互依赖的对象，而无需指定它们具体的类。

• AbstructFactory：抽象工厂，声明抽象产品的方法。
• ConcreteFactory：具体工厂，执行生成抽象产品的方法，生成一个具体的产品。
• AbstructProduct：抽象产品，为一种产品声明接口。
• Product：具体产品，定义具体工厂生成的具体产品的对象，实现产品接口。
• Client：客户，我们的应用程序使用抽象产品和抽象工厂生成对象。

原型模式（Prototype）

用原型实例指定创建对象的类型，并且通过拷贝这个原型来创建新的对象。

• Prototype：抽象原型类，定义具有克隆自己的方法的接口。
• ConcretePrototype：具体原型类实现具体的克隆方法。
• Client：客户。

单例模式（Singleton）

保证一个类只有一个实例，并提供一个访问它的全局访问点。

• Singleton：单例，提供一个 instance 的方法，让客户可以使用它的唯一实例。内部实现只生成一个实例。

构建器模式（Builder）

将一个复杂类的表示与其构造相分离，使得相同的构建过程能够得出不同的表示。

• Builder：抽象建造者，为创建一个 Product 对象各个部件指定抽象接口，把产品的生产过程分解为不同的步骤，从而使具体建造者在具体的建造步骤上具有更多弹性，从而创造出不同表示的产品。
• ConcreteBuilder：具体建造者，实现 Builder 接口，构造和装配产品的各个部件定义并明确它所创建的表示，提供一个返回这个产品的接口。
• Director：指挥者，构建一个是使用 Builder 接口的对象。
• Product：产品角色，被构建的复杂对象，具体产品建造者，创建该产品的内部表示并定义它的装配过程。

6.3.2 结构型模式【7】

适配器模式（Adapter）

将一个类的接口转换成用户希望得到的另一个接口。它使原本不相容的接口得以协同工作。

• Client：客户端，是包含当前程序业务逻辑的类。
• Client Interface：客户端接口，描述了其他类与客户端代码合作时必须遵守的协议。
• Service：服务，有一些功能类（通常来自第三方或遗留系统）。客户端（Client）与其接口不兼容，因此无法直接调用其功能。
• Adapter：适配器，一个可以同时与客户端和服务交互的类：它在实现客户端接口的同时封装了服务对象。适配器接受客户端通过适配器接口发起的调用，并将其转换为适用于被封装服务对象的调用。

桥接模式（Bridge）

将抽象部分与它的实现部分分离，使它们都可以独立地变化。

• Abstraction：抽象类定义抽象类的接口。维护一个 Implementation（实现抽象类）的对象。
• Refined Abstraction：扩充的抽象类，扩充由 Abstraction 定义的接口。
• Implementation：实现类接口，用于定义实现类，这个接口不一定要与 Abstraction 的接口完全一致，事实上这两个接口可以完全不同，一般的讲 Implementation 接口仅仅给出基本操作，而 Abstraction 接口则会给出很多更复杂的操作。
• Concrete Implementations：具体实现类，实现 Implementor 定义的接口并且具体实现它。

组合模式（Composite）

将对象组合成树型结构以表示“整体-部分”的层次结构，使得用户对单个对象和组合对象的使用具有一致性。

• Client：客户应虎程序，通过 Component 接口控制组合部件的对象。
• Leaf：叶部件，在组合中表示叶节点对象，叶节点没有子节点。定义组合中原有接口的行为。
• Composite：组合类，定义有子节点（子部件）的部件的行为。在 Component 接口中实现与子部件相关的操作。

装饰模式（Decorator）

动态地给一个对象添加一些额外的职责。它提供了用子类扩展功能的一个灵活的替代，比派生一个子类更加灵活。

• Component：部件，定义对象的接口，可以给这些对象动态的增加职责（方法）。
• Concrete Component：具体部件，定义具体的对象，Decorator 可以给他增加额外的职责（方法）。
• Base Decorator：装饰抽象类，维护一个内有的 Component，并且定义一个与 Component 接口一致的接口。
• Concrete Decorator：具体装饰对象，给内在的具体部件对象增加具体的职责（方法）。

外观模式（Facade）

定义一个高层接口，为子系统中的一组接口提供一个一致的外观，从而简化了该子系统的使用。

• Facade：外形类，知道哪些子系统负责处理哪些请求，将客户的请求传递给相应的子系统对象处理。
• Additional Facade：附加外观类，可以避免多种不相关的功能污染单一外观，使其变成又一个复杂结构。客户端和其他外观都可以使用附加外观。
• Subsystem class：子系统类，实现子系统的功能，处理由 Facade 传过来的任务。子系统不用知道 Facade，在任何地方也没有引用 Facade。

享元模式（Flyweight）

提供支持大量细粒度对象共享的有效方法。

• FlyweightFactory：轻量级类工厂，创建并且管理 flyweight 对象确保享用 flyweight。
• Flyweight：抽象轻量级类，声明一个接口，通过它可以接收外来的状态并作出处理。
• ConcreteFlyweight：具体轻量级类，实现 Flyweight 接口。
• UnsharedConcreteFlyweight：不共享的具体轻量级类，UnsharedFlyweight 对象常常将 ConcreteFlyweight 对象作为子节点。
• Client：客户应用程序。

代理模式（Proxy）

为其他对象提供一种代理以控制这个对象的访问。

• Subject：抽象实体接口，为 RealSubject 实体和 Proxy 代理定义相同的接口，使得 RealSubject 在任何地方都可以使用 Proxy 来访问。
• RealSubject：真实对象，定义 Proxy 代理的实体。
• Proxy：代理维护一个引用，使得代理可以访问实体，如果 RealSubject 和 Subject 的接口相同，则 Proxy 会引用 Subject。其他功能取决于 Proxy 的类型。
  • 远程代理：负责对请求及其参数编码，向不同地址空间中的实体发送已编码的请求。
  • 虚拟代理：可以缓存实体的其他信息，以便延迟对它的访问。
  • 保护代理：检查调用者的请求是不是有所需的权限。

6.3.3 行为模式【11】

职责链模式（Chain of Responsibility）

为解除请求的发送者和接收者之间的耦合，而使多个对象都有机会处理这个请求。将这些对象连成一条链，并沿着这条链传递该请求，直到有一个对象处理它。

• Handler：传递者接口，定义一个处理请求的接口。
• ConcreteHandle：具体传递者，处理它所负责的请求。可以访问链中下一个对象，如果可以处理请求，就处理它，否则将请求转发给后继者。
• Client：客户应用程序，向链中的对象提出最初的请求。

命令模式（Command）

将一个请求封装为一个对象，从而可用不同的请求对客户进行参数化，将请求排队或记录请求日志，支持可撤销的操作。

• Command：抽象命令类，盛名之下操作的一个接口。
• ConcreteCommand：具体命令类，将一个接收者对象绑定于一个动作。实现 execute() 方法，以调用接收者的相关操作（Action）。
• Invoke：调用者，要求一个命令对象执行一个请求。
• Receiver：接收者，知道如何执行关联请求的相关操作。
• Client：客户应用程序，创建一个具体命令类对象，并且设定它的接收者。

解释器模式（Interpreter）

给定一种语言，定义它的文法表示，并定义一个解释器，该解释器用来根据文法表示来解释语言中的句子。

• Client：客户程序，建造（或被给定）有这种语言表示的句子的抽象文法树，文法树有终结或非终结表达式的实例组成。
• Context：场景，包含解释器的所有全局信息。
• AbstractExpression：抽象表达式类，定义一个接口来执行解释操作，实现与文法中的元素相关联的解释操作。
• TerminalExpression：终结符表达式，实现文法中关联终结符的解释操作。文句中的每个终结符都需要一个实例。
• NonterminalExpression：非终结符表达式。

迭代器模式（Iterator）

提供一种方法顺序访问一个聚合对象中各个元素，而又不需要暴露该对象的内部表示。

• Aggregate：聚合，定义一个创建迭代器对象的接口。
• ConcreateAggregate：具体聚合，实现创建迭代器对象，返回一个具体迭代器的实例。
• Iterator：迭代器，迭代器定义访问和遍历元素的接口。
• ConcreateIterator：具体迭代器，实现迭代器的接口，在遍历时跟踪当前聚合对象中的位置。

中介者模式（Mediator）

用一个中介对象来封装一系列的对象交互。它使各对象不需要显式地相互调用，从而达到低耦合，还可以独立地改变对象间的交互。

• Mediator：抽象中介者角色定义统一的接口用于各同事角色之间的通信。
• ConcreteMediator：具体中介者，协调各个同事对象之间实现协作的行为，掌握并且维护它的各个同事对象引用。
• Colleage：同时类，每一个同事角色都知道对应的具体中介者角色，而且与其他的同事角色通信的时候，一定要通过中介者角色协作。

备忘录模式（Memento）

在不破坏封装性的前提下，捕获一个对象的内部状态，并在对象之外保存这个状态，从而可以在以后将该对象恢复到原先保存的状态。

• Originator：原发器，通常是需要备忘的对象自己，创建一个备忘录，记录它的当前内部状态。可以利用一个备忘录来恢复它的内部状态。
• Memento：备忘录对象，保持 Originator（原发器）的内部状态，根据原发器来决定保存哪些内部的状态。保存原发器之外的对象访问备忘录。备忘录可以有效地利用两个接口。看管者只能调用狭窄（功能有限）的接口 —— 它只能传递备忘录对象给其他对象。而原发器能调用一个宽接口（功能强大的接口），通过这个接口可以访问所有需要的数据，使原发器可以返回原先的状态。理想的情况是，只允许生成本备忘录那个原发器访问本备忘录的状态。
• CareTaker：备忘录管理者，只负责看管备忘录，不可以对备忘录的内容操作或者检查。

观察者模式（Observer）

定义对象间的一种一对多的依赖关系，当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并被自动更新。

• Subject：被观察对象，了解其多个观察者，任意数量的观察者可以观察一个对象，提供一个接口用来绑定以及分离观察者对象。
• ConcreteSubject：具体被观察对象，存储具体观察者，ConcreteObserver 有兴趣的状态。当其状态改变时，发送一个通知给其所有的观察者对象。
• Observer：观察者，定义一个更新接口，在一个被观察对象改变时应被通知。
• ConcreteObserver：具体观察者，维护一个对 ConcreteSubject 对象的引用。

状态模式（State）

允许一个对象在其内部状态改变时改变它的行为。

• Context：情景类，定义客户应用程序有兴趣的接口，维护一个 ConcreteState（具体状态）子类的实例对象。
• State：抽象状态类，定义一个接口用来封装与 Context 的一个特别状态（State）相关的行为。
• ConcreteState：具体状态类，每一个具体状态类（ConcreteState）实现了一个 Context 的状态（State）相关的行为。

策略模式（Strategy）

定义一系列算法，把它们一个个封装起来，并且使它们之间可相互替换，从而让算法可以独立于使用它的用户而变化。

• Strategy：抽象策略类，定义一个接口给所有支持的算法，Context 使用这个接口调用 ConcreteStrategy 定义的算法。
• ConcreteStrategy：具体策略类，用 ConcreteStrategy 对象配置其执行环境。

模板方法模式（Template Method）

定义一个操作中的算法骨架，而将一些步骤延迟到子类中，使得子类可以不改变一个算法的结构即可重新定义算法的某些特定步骤。

• AbstractClass：抽象类，定义一个抽象原始的操作，其子类可以重新定义它实现一个算法的各个步骤。实现一个模板方法定义一个算法的骨架，此模板方法不仅可以调用原始的操作，还可以调用定义于 AbstractClass 中的方法或者其他对象中的方法。
• ConcreteClass：具体子类，实现原始的操作以完成子类特定算法的步骤。

访问者模式（Visitor）

表示一个作用于某对象结构中的各元素的操作，使得在不改变各元素的类的前提下定义作用于这些元素的新操作。

• Visitor：抽象访问者，为对象结构中每一个具体元素类 ConcreteElement 声明一个访问操作，从这个操作的名称或参数类型可以清楚知道需要访问的具体元素的类型，具体访问者需要实现这些操作方法，定义对这些元素的访问操作。
• ConcreteVisitor：具体访问者，实现了每个由抽象访问者声明的操作，每一个操作用于访问对象结构中一种类型的元素。
• ObjectStructure：对象结构，是一个元素的集合，它用于存放元素对象，并且提供了遍历其内部元素的方法。它可以结合组合模式来实现，也可以是一个简单的集合对象，如一个 List 对象或一个 Set 对象。
• Element：抽象元素，一般是抽象类或者接口，它定义一个 Accept() 方法，该方法通常以一个抽象访问者作为参数。
• ConcreteElement：具体元素，实现了 Accept() 方法，在 Accept() 方法中调用访问者的访问方法以便完成对一个元素的操作。

6.3.4 速记

• 创建型模式：工抽单原构
• 结构型模式：代适桥组装享外
• 行为型模式

$设计模式 \begin{cases} 创建型模式 \begin{cases} 工厂方法模式 \\ 抽象工厂模式 \\ 单例模式 \\ 原型模式 \\ 构建器模式 \end{cases}\\ 结构型模式 \begin{cases} 代理模式 \\ 适配器模式 \\ 桥接模式 \\ 组合模式 \\ 装饰模式 \\ 享元模式 \\ 外观模式 \end{cases}\\ 行为型模式 \begin{cases} 职责链模式 \\ 命令模式 \\ 解释器模式 \\ 迭代器模式 \\ 中介者模式 \\ 备忘录模式 \\ 观察者模式 \\ 状态模式 \\ 策略模式 \\ 模板方法模式 \\ 访问者模式 \end{cases} \end{cases}$

七、数据结构与算法基础（10+1简答）

7.1 数组与矩阵（☆☆）

7.1.1 数组

示例：已知 5 行 5 列的二维数组 a 中的各元素占两个字节，则元素 a[2][3] 按行优先存储的存储地址为：a+(2×5+3)×2 = a+26。

7.1.2 稀疏矩阵

使用代入法，不必死记公式

稀疏矩阵	示意图	要点
上三角矩阵		在矩阵下标分别为 i 和 j 的元 素，对应的一维数组的下标计 算公式为：(2n-i+1)×i÷2+j
下三角矩阵		在矩阵中下标分别为 i 和 j 的元 素，对应的一维数组的下标计 算公式为：(i+1)×i÷2+j

7.1.3 速记

$对稀疏矩阵进行压缩存储的三种方法 \begin{cases} 三元组顺序链表 \\ 十字链表 \\ 行逻辑连接的顺序表 \end{cases}$

7.2 线性表（☆☆☆☆☆）

顺序表

链表

• 单链表
• 循环链表
• 双向链表

链表的基本操作

• 单链表删除节点
• 单链表插入节点
• 双向链表删除节点
• 双线链表插入节点

顺序存储 VS 链式存储

队列与栈

• 队列：先进先出
• 栈：先进后出

7.3 广义表（☆☆）

广义表是 n 个表元素组成的有限序列，是线性表的推广。通常用递归的形式进行定义，记作：LSn(a0, a1, ……, an)。

注：其中 LS 是表名，ai 是表元素，它可以是表（称作子表），也可以是数据元素（称为原子）。其中 n 是广义表的长度（也就是最外层包含的元素个数），n□ 0 的广义表为空表；而递归定义的重数就是广义表的深度，直观地说，就是定义中所含括号的重数（原子的深度为 0，空表的深度为 1）。

基本运算：取表头 head(Ls) 和取表尾 tail(Ls)。

示例：若有广义表 LS1 = (a, (b, c), (d, e))，head(LS1)=a，tail(LS1)=((b, c), (d, e))。

问1：其长度为 3，深度为 2。

问2：若要将其中的 b 字母取出，操作为：head(head(tail(LS1)))。（从尾部拿到 (b, c)，再从其头部拿到 b）

7.4 树与二叉树（☆☆☆☆☆）

• 结点的度（度就是分叉的意思，即一个节点有几个分叉）
• 树度（整棵树有几个分叉）
• 叶子节点
• 分支节点
• 内部节点
• 父节点
• 子节点
• 兄弟节点
• 层次

二叉树的重要特性

• 满二叉树：左右节点齐全
• 完全二叉树：有右子节点肯定有左子节点
• 非完全二叉树：有右子节点不一定有左子节点

1. 在二叉树的第 i 层最多有 2^i-1 个节点（i≥1）；
2. 深度为 k 的二叉树最多有 2^k-1 个节点（k≥1）；
3. 对任何一颗二叉树，如果其叶子结点数为 n₀，度为 2 的节点数为 n₂，则 n₀=n₂+1。
4. 如果对一棵有 n 个节点的完全二叉树的节点按层序编号（从第 1 层到 [log2n]+1 层，每层从左到右），则对任一节点 i(1≤i≤n)，有：
   1. 如果 i=1，则节点 i 无父节点，是二叉树的根；如果 i＞1，则父节点是 [i/2]；
   2. 如果 2i＞n，则节点 i 为叶子节点，无左子节点；否则，其左子节点是节点 2i；
   3. 如果 2i+1＞n，则节点 i 无右子节点；否则，其右子节点是节点 2i+1。

二叉树遍历

• 前序遍历：根左右（ABCDEFGHK）
• 中序遍历：左根右（BDCAEHGKF）
• 后序遍历：左右根（DCBHKGFEA）
• 层次遍历

反向构造二叉树

必须有中序遍历，才能知道根节点的左右节点有哪些

树转二叉树

• 孩子节点 —— 左子树节点
• 兄弟节点 —— 右孩子节点

查找二叉树

• 二叉排序树
• 左孩子小于根
• 右孩子大于根

插入节点：

1. 若该键值节点已存在，则不再插入；
2. 若查找二叉树为空树，则以新节点为查找二叉树；
3. 将要插入节点键值与插入后父节点键值比较，就能确定新节点是父节点的左子节点，还是右子节点。

删除节点：

1. 若待删除节点时叶子节点，则直接删除；
2. 若待删除节点只有一个子节点，则将这个子节点与待删除节点的父节点直接连接；
3. 若待删除的节点 p 有两个子节点，则在其左子树上，用中序遍历寻找关键值最大的节点 s，用节点 s 的值代替节点 p 的值，然后删除节点 s，节点 s 必属于上述 1、2 情况之一。

最优二叉树（哈夫曼树）

• 树的路径长度
• 权（访问次数，权值越高，访问越频繁）
• 带权路径长度
• 树的带权路径长度（树的代价）

例：假设有一组权值：5, 29, 7, 8, 14, 23, 3, 11，请尝试构造哈夫曼树。

• 先从权值最低的值（5, 3）入手，5+3=8 构成树，放左侧；
• 再取权值最小的（8, 7），7+8=15 构成树，放左侧；
• 再取权值最小的（8, 11），8+11=19 构成树，放右侧；
• 再取权值最小的（15, 14），15+14=29 构成树，放左侧；
• 再取权值最小的（19, 23），19+23=42 构成树，放右侧；
• 再取权值最小的（29, 29），29+29=58 构成树，放左侧；
• 此时原始权值已计算完，将最后两个权值（58, 42）构成哈夫曼树。

线索二叉树（了解）

平衡二叉树

平衡二叉树的定义：

• 任意节点的左右子树深度相差不超过1
• 每个节点的平衡度只能为-1、0 或 1

7.5 图（☆☆）

完全图

• 在无向图中，若每对顶点之间都有一条边相连，则称该图为完全图（complete graph）。
• 在有向图中，若每对顶点之间都有两条有向边相互连接，则称该图为完全图。

邻接矩阵

用一个 n 阶方阵 R 来存放图中各级诶单的关联信息，其矩阵元素 Rij 定义为：

$Rij=\left\{ \begin{matrix} 1：若顶点 i 到顶点 j 有邻接边 \\ 0：若顶点 i 到顶点 j 无邻接边 \end{matrix} \right.$

邻接表

首先把每个顶点的邻接顶点用链表表示出来，然后用一个一维数组来顺序存储上面每个链表的头指针。

图的遍历

遍历方法	说明	示例	图例
深度优先	1、首先访问出发顶点V； 2、依次从V触发搜索V的任意一个邻 接点W； 3、若W未访问过，则从该点出发继 续深度优先遍历。 它类似于树的前序遍历	V1,V2, V4,V8, V5,V3, V6,V7
广度优先	1、首先访问出发顶点V； 2、然后访问与顶点V邻接的全部未 访问顶点W、X、Y……； 3、然后再依次访问W、X、Y……邻接 的未访问的顶点。	V1,V2, V3,V4, V5,V6, V7,V8

拓扑排序（了解）

用有向边表示活动之间开始的先后关系。这种有向图称为用顶点表示活动网络，简称 AOV 网络。

图的最小生成树

保留图顶点之间最小权值的连线，并且保证最后所有顶点都能连接在一起。

7.6 排序与查找（☆☆☆☆☆）

7.7 时间复杂度与空间复杂度（☆☆☆☆☆）

7.8 算法基础及常见的算法（☆☆☆☆☆）（缺）

算法的特性

• 有穷性：执行有穷步之后结束。
• 确定性：算法中每一条指令都必须有确切的含义，不能含糊不清。
• 输入（>=0）
• 输出（>=1）
• 有效性（可行性）：算法的每个步骤都能有效执行并能得到确定的结果。例如：a=0，b/a 就无效

算法的复杂度

八、程序设计语言与语言处理程序基础（3~5）

8.1 编译与解释（☆☆☆）

源程序 ——> 词法分析 ——> 语法分析 ——> 语义分析 ——> 中间代码生成 ——> 代码优化 ——> 目标代码生成 ——> 目标程序

8.2 文法（☆☆）

一个形式文法是一个有序四元组 G=(V, T, S, P)，其中：

• V：非终结符。不是语言组成部分，不是最终结果，可理解为占位符。
• T：终结符。是语言的组成部分，是最终结果。V∩T=∅
• S：起始符。是语言的开始符号。
• P：产生式。用终结符替代非终结符的规则。形如 α→β

正则闭包：A⁺=A¹∪A²∪A³∪……∪Aⁿ∪……（也就是所有幂的组合）。

闭包：A^*=A⁰∪A⁺（在正则闭包的基础上，加上 A⁰={ε}）。

示例：a^*={a, aa, aaa, ……, ε}；(ab)^*={ab, abab, ababab, ……, ε}。

8.3 语法推导数

一棵语法树应具有以下特征：

1. 每个节点都有一个标记，此标记是 V 的一个符号；
2. 根的标记是 S；
3. 若一节点 n 至少有一个它自己除外的子孙，并且有标记 A，则 A 肯定在 V_N 中；
4. 如果节点 n 的直接子孙，从左到右的次序是节点 n₁, n₂, ……, n_k，其标记分别是：A₁, A₂, ……, A_k，那么 A→A₁, A₂, ……, A_k，一定是 P 中的一个产生式。

示例：文法 G=({a, b}, {S, A}, S, P)，其中：S→aAS|a（S 可以推导出：aAS；S 可以推导出：a）；A→SbA|SS|ba（A 可以推导出 SbA；A 可以推导出 SS；A 可以推导出 ba），请构造句型 aabAa 的推导树。

aabAa → aSbAa → aAa → aAS → S

8.4 有限自动机（☆）

M=(S, Σ, δ, S0, Z)

1. S 是一个有线集，每个元素为一个状态
2. Σ 是一个有穷字母表，每个元素为一个输入字符
3. δ 是转换函数：是一个单值对照
4. S0 属于 S，是其唯一的初态
5. Z 是一个终态集（可空）

有限状态自动机可以形象地用状态转换图表示，设有限状态自动机：

DFA=({S, A, B, C, f}, {1, 0}, δ, S, {f})，

其中：δ(S, 0)=B，δ(S, 1)=A，δ(A, 0)=f，δ(A, 1)=C，δ(B, 0)=C，δ(B, 1)=f，δ(C, 0)=f，δ(C, 1)=f。

8.5 正规式（☆☆☆☆）

正规式是描述程序语言单词的表达式，对于字母 Σ，其上的正规式及其表示的正规集可以递归定义如下：

1. ε 是一个正规式，它表示集合 L(ε)={ε}。
2. 若 a 是 Σ 上的字符，则 a 是一个正则式，它所表示的正规 L(a)={a}。
3. 若正规式 r 和 s 分别表示正规集 L®=L(s)，则：
   1. r|s 是正规式，表示集合 L®∪L(s)；
   2. r·s 是正规式，表示集合 L®L(s)；
   3. r* 是正规式，表示集合 (L®)*（闭包，表示循环）；
   4. ® 是正规式，表示集合 L®。

仅由有限次地使用上述三个步骤定义的表达式才是 Σ 上的正规式。由此可见，正规式要么为空，要么由字母、或、连接、闭包运算符组成。其中闭包运算符“*”具有最高的优先级，连接运算具有次高优先级，或运算符“|”具有最低优先级。

C 是终态，执行最终应停在 C 节点，只有 C 符合。

写为正规式：(1*00*(10)*1)*

8.6 数据类型与程序控制结构

常见数据类型：

• 数字数据类型：int，float，double，short，long
• 布尔类型：boolean
• 字符类型：char，byte
• 枚举类型
• 指针类型

程序控制结构主要有：顺序结构、选择结构（if-else等）和循环结构（for，do-while等）

8.7 程序语言基础-表达式

后缀表达式（☆☆☆）

有点像二叉树的前中后序遍历

前缀表达式很少使用，一般考察中缀表达式与后缀表达式的转化

• 前缀表达式（+ab）
• 中缀表达式（a+b）
• 后缀表达式（ab-）

示例：表达式 (a-b)*(c+5) 的后缀表达式是：ab-c5+*

8.8 函数调用-传值与传址（☆☆☆☆）（每年考）

• 左侧代码为：传值调用，只传输实参的值
• 右侧代码为：引用调用，传输实参的地址，在方法中被修改的值会反向影响到实参（注意符号）

8.9 多种程序语言特点（☆☆☆）

1. Fortran 语言（科学计算，执行效率高）
2. Pascal 语言（为教学而开发的，表达能力强，Delphi）
3. C 语言（指针操作能力强，高效）
4. Lisp 语言（函数式程序语言，符号处理，人工智能）
5. C++ 语言（面向对象，高效）
6. Java 语言（面向对象，中间代码，跨平台）
7. C# 语言（面向对象，中间代码，.Net）
8. Prolog 语言（逻辑推理，间接性，表达能力，数据库和专家系统）
9. Python 语言（解释型，面向对象，胶水语言）

九、多媒体基础知识（3选）

9.1 多媒体技术基本概念（☆☆）

9.2 多媒体相关计算问题（☆☆☆）

音频相关概念

声音的带宽：

• 说话：300-3400Hz
• 人耳：20Hz-20kHz
• 乐器：20Hz-20kHz

采样

• 采样频率
• 采样精度
• 采样频率应为声音最高评率 2 倍

A/D 转换（模拟信号A转数字信号D）：采样→量化→编码

常见音频格式：WAVE、MP3、MIDI（乐器的标准）

每秒容量 = 采样频率（Hz）× 量化/采样位数（位）× 声道数 ÷ 8（压缩后的公式）

示例：CD 上声音的采样频率为 44.1kHz，样本精度为 16bit，双声道立体声，那么其未经压缩的数据传输率为：44.1k×16bit×2=1411.2kb（未经压缩，因此不用÷8）

图像相关概念

图片注意未压缩计算需要【÷8】

• 亮度：画面的明亮程度。
• 色调（红，绿）：颜色的种类，如红色、绿色、蓝色等不同颜色就是指色调。同时画面整体颜色倾向，也是色调。
• 饱和度：色彩的纯洁性，即颜色的艳丽程度。

示例：某数码相机内置 128MB 的存储空间，拍摄分辨率设定为 1600×1200 像素，颜色深度为 24 位，若不采用压缩存储技术，使用内部存储器最多可以存储128÷(1600×1200×24÷8÷1024÷1024)=128÷5.5=23.3张照片。（B→KB→MB）

9.3 媒体的种类（显示媒体）（☆☆☆）

• 感觉媒体：指直接作用于人的感觉器官，使人产生直接感觉的媒体。如：声音、图形、图像、动画等。
• 表示媒体：指为了加工、处理和传输感觉媒体而人为研究、构造出来的一种媒体，常见的有各种编码方式，如文本编码、图像编码和声音编码等。
• 显示媒体（表现媒体）：表现和获取信息的物理设备。如：输入显示媒体：键盘、鼠标和麦克风等；输出显示媒体：显示器、打印机和音箱等。（输入输出设备，一般考察这里）
• 交换媒体（转换媒体）
  • 存储媒体：存储数据的物理设备。如：磁盘、光盘和内存等。
  • 传输媒体：传输数据的物理载体（介质）。如：电缆、光缆和交换设备等。

9.4 常见多媒体标准数据压缩技术（☆☆）

正是因为数据有冗余，所以需要压缩技术

• 空间冗余（几何冗余）
• 时间冗余
• 视觉冗余
• 信息熵冗余
• 结构冗余
• 知识冗余

有损压缩与无损压缩

• 无损压缩编码法（Lossless compression coding），也称冗余压缩法或熵编码法。
• 有损压缩编码法（Loss compression coding），也称为熵压缩法。

常见多媒体标准

MP3 表示的是 MPEG-1 的第三层，而不是 MPEG-3

十、知识产权与标准化（1~2选）

构成我国保护计算机软件著作权的两个基本法律：《中华人民共和国著作权法》、《计算机软件保护条例》【速记】

10.1 保护范围与对象

10.2 保护期限（☆☆）

翻译权：将原软件从一种自然语言文字转换成另一种自然语言文字的权利。【速记】

10.3 知识产权人确定（☆☆☆）

10.4 侵权判断（☆☆☆☆）（1~2）

中国公民、法人或者其他组织的作品，不论是否发表，都享有著作权。

开发软件所用的思想、处理过程、操作方法或者数学概念不受保护。

著作权法不适用于下列情形：

• 法律、法规，国家机关的决议、决定、命令和其他具有立法、行政、司法性质的文件，及其官方正式译文；
• 时事新闻；
• 历法、通用数表、通用表格和公式。

10.5 标准的分类（☆）

• 国际标准：ISO、IEC 等国际标准化组织
• 国家标准：GB —— 中国、ANSI —— 美国；BS —— 英国；JIS —— 日本
• 区域标准：又称为地区标准，如 PASC —— 太平洋地区标准会议；CEN —— 欧洲标准委员会；ASAC —— 亚洲标准咨询委员会；ARSO —— 非洲地区标准化组织
• 行业标准：GJB —— 中国军用标准；MIT-S —— 美国军用标准；IEEE —— 美国电气电子工程师协会
• 地方标准：国家的地方一级行政机构制定的标准
• 企业标准
• 项目规范

10.6 标准代码的识别（☆）

• 国际、国外标准代号：标准代号+专业类号+顺序号+年代号
• 我国国家标准代号：强制性标准代号为 GB；推荐性标准代号为 GB/T；指导下标准代号为：GB/Z；实物标准代号为：GSB
• 行业标准代号：由汉语拼音大写字母组成（如：电子行业为：SJ）
• 地方标准代号：由 DB 加上省级行政区代码的前两位
• 企业标准代号：由 Q 加上企业代号组成

十一、数据流图（DFD）（简答No1）

15分需要至少拿到12分以上

11.1 数据流图基本概念（主）

11.2 数据字典（次）

11.3 数据平衡原则（主）

11.3.1 父图与子图之间的平衡

一旦顶层图（父图）确定好了，0 层图（子图）要进行平衡（外部实体与数据流要和父图统一）

11.3.2 子图内平衡

数据流的输入输出要匹配：

• 数据流要有流进流出
• 数据的流入成分要充足（例如：查询销售额，则至少要输入员工信息和销售记录）

十二、数据库设计（简答题No2）

15分需要至少拿到13分以上

12.1 数据库设计过程

12.2 ER 模型

12.3 考点

1. 找联系
2. ER 图转成关系模式
3. 找主键、外键
4. 大综合

十三、UML建模

15分需要至少拿到12分以上

13.1 用例图（必考）【速记】

用例图描述一组用例、参与者及他们之间的关系

13.1.1 包含关系

其中这个提取出来的公共用例称为抽象用例，而把原始用例称为基本用例或基础用例；当可以从两个或两个以上的用例中提取公共行为时，应该使用包含关系来表示它们。（include）

13.1.2 扩展关系

如果一个用例明显地混合了两种或两种以上的不同场景，即根据情况可能发生多种分支，则可以将这个用例分为一个基本用例和一个或多个扩展用例，这样使描述可能更加清晰。(extend)

13.1.3 泛化关系

当多个用例共同拥有一种类似的结构和行为的时候，可以将它们的共性抽象成为父用例，其他的用例作为泛化关系中的子用例。在用例的泛化关系中，子用例是父用例的一种特殊形式，子用例继承了父用例所有的结构、行为和关系。

13.1.4 用例建模的流程

• 识别参与者（必须）
• 合并需求获得用例（必须）
• 细化用例描述（必须）
• 调整用例模型（可选）

13.2 类图与对象图（必考）

13.2.1 类图（class diagram）【速记】

类图描述一组类、接口、协作和它们之间的关系。在 OO 系统的建模中，最常见的图就是类图。类图给出了系统的静态设计视图，活动类的类图给出了系统的静态进程视图。

类图有四种关系（因为关联关系 = 聚合关系 + 组合关系，所以总体上是五种关系的类图）

• 关联关系：描述了一组链，链是对象之间的连接
  • 聚合关系：整体与部分生命周期不同（部分离开整体后还能单独存活）
  • 组合关系：整体与部分生命周期相同（部分离开整体化不能单独存活）
• 依赖关系：一个事物发生变化影响另一个事物
• 泛化关系：特殊/一般关系（继承关系）
• 实现关系：接口与类之间的关系

聚合 VS 组合示例

一个商城系统，有商品、网店、购物车等内容

• 商品 VS 购物车，购物车包含一部分商品，与商品是整体和部分的关系，且没有购物车了，商品依旧可以单独存在，因此两者是聚合关系
• 商品 VS 网店，网店里包含一部分商品，与商品是整体和部分的关系，但是没有网店了，商品也就没了，商品不可以脱离网店单独存在，因此两者是组合关系

13.2.2 对象图（object diagram）

对象图描述了一组对象及它们之间的关系。对象图描述了在类图中所建立的事物实例的静态快照。和类图一样，这些图给出了系统的静态设计视图或静态进程视图，但它们是从真实案例或原型案例的角度建立的。

• 填类名，方法名，属性名
• 填多重度
• 填关系

13.3 顺序图（掌握）

顺序图（sequence diagram，序列图）。顺序图是一种交互图（interaction diagram），交互图展现了一种交互，它由一组对象或参与者以及它们之间可能发送的消息构成。交互图专注于系统的动态视图。顺序图是强调消息的时间次序的交互图。

13.4 活动图（掌握）

活动图（activity diagram）。活动图将其进程或其他计算结构展示为计算内部一步步的控制流和数据流。活动图专注于系统的动态视图。它对系统的功能建模和业务流程建模特别重要，并强调对象间的控制流程。

13.5 状态图（掌握）

状态图（state diagram）。状态图描述一个状态机，它由状态、转移、事件和活动组成。状态图给出了对象的动态视图。它对于接口、类或协作的行为建模尤为重要，而且它强调时间导致的对象行为，这非常有助于对反应式系统建模。

13.6 通信图（了解）

通信图（communication diagram）。通信图也是一种交互图，它强调收发消息的对象或参与者的结构组织。顺序图和通信图表达了类似的基本概念，但它们所强调的概念不同，顺序图强调的是时序，通信图强调的是对象之间的组织结构（关系）。

13.7 构件图（了解）

构件图（component diagram）。构件图描述了一个封装的类和它的接口、端口以及由内嵌的构件和连接件构成的内部结构。构件图用于表示系统的静态设计实现视图。对于由小的部件构建大的系统来说，构件图是很重要的。构件图是类图的变体。

13.8 部署图（了解）

部署图（deployment diagram）。部署图描述对运行时的处理节点及在其中生存的构件的配置。部署图给出了架构的静态部署视图，通常一个节点包含一个或多个部署图。

十四、数据结构与算法应用（15）（难点）

争取3~9分

14.1 判断程序属于哪一种方法（3）

分治法；回溯法；贪心法；动态规则法

14.1.1 分治法

对于一个规模为 n 的问题，若该问题可以容易地解决（比如说规模 n 较小）则直接解决；否则将其**【分解】为 k 个规模较小的子问题，这些子问题相互独立且与原问题形式相同，递归地【解决】这些子问题，然后将各子问题的解【合并】**得到原问题的解。

• 该问题的规模缩小到一定的程度就可以容易地解决
• 该问题可以分解为若干个规模较小的相同问题
• 利用该问题分解出的子问题的解可以合并为该问题的解
• 该问题所分解出的各个子问题是相互独立的

特征：把一个问题拆分成多个小规模的相同子问题，一般可用递归解决。（局部和整体解唯一，不用判断最优）

经典问题：斐波那契数列、归并排序、快速排序、矩阵乘法、二分搜索、大整数乘法、汉诺塔

14.1.2 动态规划法（用于求最优解）

在求解问题中，对于每一步决策，列出各种可能的局部解，再依据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解。

特征：划分子问题，并把子问题结果用数组存储，利用查询子问题结果构造最终问题。（整体最优但不一定是局部最优）

经典问题：斐波那契数列、矩阵乘法、背包问题、LCS 最长公共子序列

14.1.3 回溯法

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。这种走不通就退回再走的技术就是回溯法。

• 试探部分：满足除规模之外的所有条件，则扩大规模。（扩大规模）
• 回溯部分：（缩小规模）
  • 当前规模解不是合法解时回溯（不满足约束条件 D）
  • 求完一个解，要求下一个解时，也要回溯

特征：系统的搜索一个问题的所有解或任一解。

经典问题：N 皇后问题、迷宫（走不通时就返回最近的一个分叉口继续探索）、背包问题

14.1.4 贪心法

总是做出在当前来说是最好的选择，而并不从整体上加以考虑，它所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不必为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解，但得不到最优解。

特征：局部最优，但整体不见得最优。每步有明确的、既定的策略。（局部最优但不一定是整体最优）

京东问题：背包问题（如装箱）、多机调度、找零钱问题

14.1.5 速记

$算法 \begin{cases} 分治法：所求解的问题比较简单，不用区分甚至没有最优解，只有唯一解 \\ 动态规划法：在问题求解时，列出所有可能的解，并选取最优方案 \\ 回溯法：在问题求解时，先做出最优的选择，但发现原先选择并不优或达不到目标，则回退重新选择 \\ 贪心法：在问题求解时，总是做出在当前看来是最好的选择 \end{cases}$

动态规划法 VS 贪心法

• 动态规划法的每次决策都依赖当前的状态，但子问题选择最优解后，又会引起现有状态的转移，具有重叠子问题性。一个决策序列就是在变化的状态中产生的中，因此叫动态规划。
• 贪心法在求解问题时，也是做出当前看来最好的选择。但不同的是，选择的贪心策略必须具备无后效性（即某个子问题解决后，不会影响到之后的状态，而只与当前状态有关）。

14.2 求程序的时间复杂度（3）【速记】

O(1) ＜ O(log₂n) ＜ O(n) ＜ O(nlog₂n) ＜ O(n²) ＜ O(n³) ＜ O(2ⁿ)

14.2.1 常数级时间复杂度 O(1)

• 单个语句（如：k=0;）
• 整个程序都没有循环语句，或复杂函数的调用

1
2
3
4
5

void main() {
    char*x = "ABCDEFG";
    int m = strlen(x);
    printf("len:%d\n", m);
}

14.2.2 时间复杂度 O(n)

单层循环

1
2
3
4
5
6
7

void main() {
    int i,j;
    k=0;
    for(i=0;i＜n; i++) {
        b[i]=0;
    }
}

14.2.3 时间复杂度 O(n²)

双层循环

1
2
3
4
5
6
7
8
9

void main() {
    int i, s=0, n=1000;
    for(i=1; i<n; i++) {
        for(j=1; j<n; j++) {
            s+=j;
        }
    }
    printf("结果为：%d", s);
}

14.2.4 时间复杂度 O(log₂n)

求一棵树的深度，因为：二叉树叶子节点数 = 2ⁿ（n 为二叉树的深度-1）

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

int search(int array[], int n, int v) {
    int left, right, middle;
    left=0, right=n-1;
    while(left<=right) {
        middle=(left+right)/2;
        if(array[middle]>v) {
            right=middle;
        } else if(array[middle]<v) {
            left=middle;
        } else {
            return middle;
        }
    }
    return -1;
}

14.2.5 时间复杂度 O(nlog₂n)

典型代表：堆排序，每次重建栈的时间复杂度是 log₂n，n 个元素基本上就是 nlog₂n。

14.3 程序填空题

一般第一个空是填写程序初始化（3），争取争取

十五、面向对象程序设计

争取 >=3

汇编语言就是低级语言，可以直接描述/控制 CPU 的运行。

15.1 C++ 语法要点【速记】

编译型编程语言

编译器的工作方式及特点：先翻译后执行，用户程序运行效率高但可移植性差。

• 词法分析：分析词性（这个词属于名词？形容词？动词？）
• 语法分析：分析各种介词短语、名词短语、动词短语……
• 语义分析：分析词语串起来后，整个句子的意思是什么（类型检查）

15.2 Java 语法要点

解释型编程语言

解释器的工作方式及特点：边翻译边执行，用户程序运行效率低但可移植性好。

Java 语言的特征

1. 即时编译
2. 对象在堆空间分配
3. 自动的垃圾回收处理

15.3 Python 语法要点

解释型编程语言

Python 语言特点

1. 动态编程
2. 跨平台、开源
3. 支持面向对象程序设计

15.3.1 元组（tuple）

与列表（list）类似，是一个有序的数据集合，但是其中的元素不能像列表那样允许添加和删除。

15.4 设计模式程序实现

15.5 结构化语言

15.5.1 顺序语句

15.5.2 选择语句

1
2
3
4
5
6
7

IF 条件 THEN
    分支内容
ELSE IF 条件 THEN
    分支内容
ELSE
    分支内容
ENDIF

15.5.3 循环语句

1
2
3
4
5
6
7
8

WHILE 下雨 
DO{
    在家
    IF 不下雨 THEN
        出门
    ENDIF
}
ENDDO

十六、选择题速记

流水线完成 n 个任务的吞吐率

流水线分段中的最大耗时为 T_max，其他分段的耗时为 T_sum，则流水线完成 n 个任务的吞吐率为 n÷(T_max×n+T_sum)。

SRAM、DRAM

• SRAM：是一种具有静止存取功能的内存。不需要刷新电路即能保存它内部的数据。
• DRAM：即动态随机存取存储器，最为常见的系统内存。只能将数据保存很短的时间。为保持数据，DRAM 使用电容存储，所以必须隔一段时间刷新一次，如果存储单元没有被刷新，存储的信息就会丢失。

ISO/IEC 软件质量模型

面向对象的主要活动

$面向对象分析时的五个活动 \begin{cases} 1、认定对象 \\ 2、组织对象 \\ 3、描述对象间的相互作用 \\ 4、确定对象的操作 \\ 5、定义对象的内部信息 \end{cases}$

$面向对象设计时的五个活动 \begin{cases} 1、识别类及对象 \\ 2、定义属性 \\ 3、定义服务 \\ 4、识别关系 \\ 5、识别包 \end{cases}$

面向对象的设计原则

• 接口分离原则：不应该强迫客户依赖于他们不用的方法。
• 开放封闭原则：软件实体（类、模块、函数等）应该是可以扩展的，即开放的；但是不可修改的，即封闭的。
• 共同封闭原则：包中的所有类对于同一性质的变化应该是共同封闭的。一个变化若对一个包产生影响，则将对该包中的所有类产生影响，而对于其他包则不造成任何影响。
• 共同重用原则：一个包中的所有类应该是共同重用的。如果重用了包中的一个类，那么就要重用包中的所有类。

单播、组播、广播

• 单播：向特定的一台主机进行信息的发送
• 组播 = 多播：向特定的一组主机进行信息的发送
• 广播：向同一广播域的所有主机进行信息的发送

名词区分

$名词区分 \begin{cases} UML用例之间的关系：包含关系、扩展关系、泛化关系 \\ 数据库实体间的联系类型：一对一、一对多、多对多 \\ UML类图之间的关系：关联关系（聚合关系、组合关系）、依赖关系、泛化关系、实现关系 \\ 关系模式：对象名称（对象属性1，对象属性2，……） \\ 设计模式：创建型模型（工抽单原构）、结构型模型（代适桥组装享外）、行为型模型 \end{cases}$