软考中级-软件设计师

冯诺依曼

指令和数据在同一存储器

二进制数

浮点表示法

二进制数 $N = 2^E \times F$ ，其中

$E$ 为阶码（带符号的纯整数），决定 $N$ 的大小（位数更多，数值更大/表示范围越大）
$F$ 为尾数（带符号的纯小数），决定 $N$ 的精度（位数越多，精度越高）

[!tip]
这种方法称为浮点表示法

数符：尾数的符号，1 为正，0 为负
阶符：1 为负，0 为正

尾数 10 位 => $F = 2^{-10}$

小数点后面，从 1 次方开始算， $2^1, 2^2, ......$

阶码补码 (负数) = 0001 => 阶码原码 = 取反 (0001 - 1) = 1111
即 $E = - (1*2^0 + 1*2^1 + 1*2^2 + 1*2^3) = -15$

综上，浮点数为 $2^{-15} \times 2^{-10}$

浮点数对阶

浮点数加减运算时，首先要进行对阶，根据对阶的规则，阶码和尾数将进行相应的操作。

对阶的规则是，小阶向大阶对齐，即阶码小的尾数算数右移，每右移一位，阶码加1，直到对接的两个数的阶码相等为止。

浮点数加减法

零操作数检查
对阶操作
尾数加（减）运算
规格化及舍入处理

移位运算

左移 << 1 位：乘 $2^1$
带符号右移
无符号右移

校验码

奇偶校验码

只能检测代码中奇数个位出错的编码，但不能发现偶数个位出错的情况。

海明码

海明码利用奇偶性进行检错和纠错
码距最小为 2n+1
数据位 n，校验位 k，则

$2^k \geq n+k+1$

例：对于 32 位的数据，至少需要加（6）个校验位才能构成海明码。

循环冗余校验码

采用模 2 运算来构建校验位的，是 CRC 循环冗余校验码

哈夫曼树

左 0 右 1
节点的度要么为 0，要么为 2（用来判断一个编码方案是否构成哈夫曼树）
若有 n 个字符构造哈夫曼树，则会多出 n-1 个节点，也即一个 n+n-1 个节点的哈夫曼树，能够得到 n 个字符的编码

指令

CPU 依据指令周期的不同阶段来区分在内存中以二进制编码形式存放的指令和数据
VLIW (Very Long Instruction Word)：超长指令字
双核处理器的“双核”指的是在一个CPU中集成两个运算核心以提高运算能力

寄存器

PC（程序计数器）：存放下一条指令的地址
IR（指令寄存器）：存放从内存中读取的指令
AC（累加器）：通用寄存器，可用于传送和暂存数据，也可参与算术逻辑运算，保存运算结果

指令流水线

执行周期/流水线周期： $3\triangle t$ （最长的那个时间）
首条指令执行时间： $2\Delta t + 1\Delta t + 3\Delta t + 1\Delta t + 2\Delta t = 9\Delta t$
流水线执行时间：首条指令执行时间 + (指令数-1)*执行周期 = $9\triangle t + (n-1) 3\triangle t$ ，当 $n \rightarrow \infty$ 时，执行时间 = $3n\triangle t$
吞吐率： $\frac{1}{3\triangle t}$ （指令条数 $n$ / 流水线执行时间 $3n\triangle t$ ）
加速比：不采用流水线的时间 / 采用流水线的时间
- 不采用： $(2+1+3+1+2)\triangle t \times 10 = 90 \triangle t$
- 采用： $(2+1+3+1+2)\triangle t + (10-1) \times 3\triangle t = 36\triangle t$
- 加速比 = $90/36 = 5:2$

指令系统

RISC（精简）：Reduced

指令数量少、使用频率接近、定长格式
硬布线，硬件
优化编译
采用流水线
采用很多寄存器

CISC（复杂）：Complex

指令数量多、使用频率差别大、可变长格式
微程序控制技术（微码）
研制周期长
不采用流水线
采用很少寄存器

寻址方式

立即寻址：操作数就在指令里，获取操作数的速度最快
直接寻址：操作数的地址在指令里
寄存器寻址：存放操作数的寄存器名字在指令里，执行阶段不用访问主存，执行速度快

中断

中断方式下，IO 系统与外设交换数据时，CPU 可以并行处理其他任务。
采用中断方式和 DMA 方式控制技术时，CPU 可以与外设并行工作。
管理键盘最适合的 IO 方式是中断，不是DMA

中断流程

IO 准备好后，发出中断请求
CPU 收到信号后，保存现场，转入执行 IO，完成后返回被打断的程序继续执行

保存现场、中断处理、恢复现场

中断向量

系统中有多个中断源，用中断向量表保存各个中断服务程序的入口地址

DMA

Direct Memory Access，直接内存存取方式：数据在主存（内存）和 IO 设备（外设）间直接传送，不需要 CPU 干预
硬件电路实现
键盘适合 DMA
一个 DMA 传送只需要执行一个 DMA 周期，即一个总线读写周期

同类说法：
CPU 是在一个总线周期结束时响应 DMA 请求的
DMA 传送结束事件会触发 CPU 请求，是中断

[!tip] 总结
DMA 直接从内存读写数据，这个过程中 CPU 该干嘛干嘛，所以是并行的。但结束时，会通过中断的方式通知 CPU 活干完了，来查收。

总线

叙述

并行总线适合近距离高速数据传输
串行总线适合长距离数据传输
专用总线在设计上可以与连接设备实现最佳匹配
单总线结构的优点是控制简单方便，扩充方便，性能不高

单双工

单工：A 只能发信号，B 只能收信号（广播）
半双工：AB 都可发可收，但同一时间只能一个发一个收（对讲机）
全双工：AB 都可发可收，而且可以同时进行（电话）

PCI/SCSI

PCI 总线是并行内总线（PC 机）
SCSI 是并行外总线（软硬盘、扫描仪）

存储

Cache

Cache 不是主存，主存指的是内存条
Cache 是按照内容访问的存储器

主存与 Cache 的地址映射方式

Cache 与主存之间地址映射由硬件自动完成

全相联地址映射：主存的任意一块可以映象到 Cache 中的任意一块。
直接相联映射：主存中一块只能映象到 Cache 的一个特定的块中
组相联的映射：各区中的某一块只能存入缓存的同组号的空间内，但组内各块地址之间则可以任意存放。即从主存的组到 Cache 的组之间采用直接映象方式，在两个对应的组内部采用全相联映象方式。

RAM

[!tip]
RAM = 随机存储器
DRAM = 动态随机存储器 (Dynamic)
SRAM = 静态随机存储器（Static）

随机存储器可以按地址访问存储器的任一单元。

SRAM:

不刷新，速度快
断电就信息丢失，不断电就不会丢
集成度低，功耗、体积大，成本高

DRAM（内存条）：

存取速度慢
用电荷存信息（只能维持 1-2ms），周期性通电刷新
集成度高，功耗低
不刷新、关机，都会丢数据

FLASH可以不加电下长期保存数据（U 盘）

EEPROM电擦除可编程只读存储器：可以突出，也可以通过电擦除进行改写

磁盘

磁盘是一种直接存储器

调度算法

磁盘调度分为移臂调度（控制磁头的移动）和旋转调度（控制磁盘盘片的旋转）两类，并且是先进行移臂调度，然后进行旋转调度。

移臂调度

[!tip]
前两者会随时改变移动臂的运行方向

处理时间

一圈 30ms，一圈有 10 块，=> 读一块要 3ms
读出来的一块放入单缓冲区，处理要 6ms
读完并处理完第一块，一共 9ms，此时磁头已经过了 R2，到了 R4 的开始处，因此想读 R2 就得绕 8 块，8*3=24ms 到达 R2 的开头，然后读+处理 R2，一共 24+9=33ms
R2 到 R10 都是如此，因此一共 9*33=297ms
加上第一块的 9ms，一共 297+9=306ms（最长时间）

重新排布，让 R1 读完处理完后，磁头到达的地方改成 R2，以此类推，则最短时间= (3+6)*10=90ms

raid 阵列

raid5 有 N 块盘，只能用 N-1 块的容量，还有 1 块放校验信息

计算芯片数

内存按字节编址，利用 $8K \times 4bit$ 的存储器芯片构成 84000H 到 8FFFFH 的内存，需要（）片？

8FFFFH-84000H+1=C000H（地址数）
按字节编址 => 每个地址是 8bit
内存大小=C000H * 8bit = $(12 \times 16^3 \times 8) bit = 48K \times 8bit$
$\frac{48K \times 8bit}{8K \times 4bit} = 12$ ，即 12 片

地址变换

Screenshot_2023-05-23-20-46-38-391_tv.danmaku.bil.png

[!tip]
页面地址 = 页号 + 页内地址
物理地址 = 块号 + 页内地址

页面大小 $4K = 2^{12}$ ，所以逻辑地址为 12 位。一个 16 进制位是 4 个 2 进制位，所以逻辑地址 25EFH (H 是 16 进制的标志)的后三位 5EF (3x4=12)为页内地址，即 2 是页号。

从表里查，页号 2 对应的块号是 4 ，所以物理地址 45EF = 4 + 5EF

位示图

字长：一个字包含多少个物理块

计算机系统字长为 64 位，磁盘容量 512GB，物理块大小为 4MB，则位示图大小为 (2048) 个字

512G/4MB = $2^{17}$ 个物理块
$2^{17}$ / 64 = 2048 个字

2053 号块 = 第 2054 个块，字长 32 位 = 一个字 32 个物理块
=> 2054/32 = 64 余 6，即占满了 0-63 号字，从 64 号字开始
=> 余下 6 个物理块，即 64 号字中的 0-5 号位，该块占用
=> 64 号字的位号 5 的位置”1“

段页式存储

31-22+1=10，21-12+1=10， $2^{10}=1024$

最多可有 1024 个段，每个段最大允许有 1024 个页，页的大小为 4K

文件系统

[!question] 某文件系统文件存储采用文件索引|节点法。每个文件索引|节点中有8个地址项，每个地址项大小为4字节，其中5个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引。磁盘索引块和磁盘数据块大小均为1KB。若要访问iclsClient.d文件的逻辑块号分别为1、518，则系统应分别采用（）。

A：直接地址索引和直接地址索引
B：直接地址索引和一级间接地址索引
C：直接地址索引引和二级间接地址索引
D：一级间接地址索引和二级间接地址索引

直接地址索引|有5个地址项，对应逻辑块号0-4。
一级间接索引|有2个地址项，每个地址项对应1Kb/4B=256个物理块，对应逻辑块号范围是5-516。
二级间接索引|有一个地址项，对应256×256=65536个物理块，对应逻辑块号范围是517以上。

三种存储器

随机存储器：任何存储单元读写，访问时间相同
顺序存储器：访问数据所需时间与数据存储位置相关
直接存储器：介于上述两者之间，磁道寻址随机，磁道内寻址顺序

多线程

进程创建了若干线程，则它们的栈指针不能共享

PV 操作

安全

加密

浏览器和服务器之间用于加密 HTTP 消息的方式：会话秘钥+公钥加密

服务器证书被撤销：客户端无法再信任服务器

目前加密技术主要两类：

基于对称密钥的加密算法（私钥加密算法）
- DES AES IDEA RC4
- 分组加密： AES
- 流加密：用伪随机数序列作为密钥
基于非对称密钥的加密算法（公钥算法）
- RSA ECC

[!tip] MD5 SHA 属于消息摘要算法

数字证书

证书	密码算法
X.509	RSA
国密 SM2	ECC

安防

入侵防御系统包括入侵检测系统。所以直接可以阻断网络攻击行为，不需要联动入侵检测
配置 ACL 可以阻止外部未授权用户访问内部网络
凡是带 NAT 字眼的，就是做地址转换的（Network Address Translation）
SQL 注入确实属于 web 攻击，但是不会被视为入侵，因为它本质上是正常的用户交互行为，只不过因为系统存在漏洞，所以会变成攻击
防火墙类型：
- 包过滤防火墙：网络层
- 应用代理网关防火墙：应用层
- 状态检测防火墙：网络层
防火墙受保护程度：外网 < DMZ < 内网

密码法

《中华人民共和国密码法》规定国家对密码实行分类管理：核心密码、普通密码和商用密码

知识产权

产权	期限
著作权	终生+死后 50 年
署名权	无限
修改权	无限
保护作品完整权	无限

软件著作权自软件开发完成之日起自动产生，不存在生效一说
国际上保护计算机软件知识产权不受侵犯的主要方式：版权法
著作权人死亡后，继承人可以按规定继承除了署名权以外的其他权利 (财产权利)
受委托的作品，著作权归属由双方通过合同约定。没得合同，或者合同没有明确规定，著作权归受托人

说人话就是你委托外包干活，你不要著作权那就归外包所有

专利申请，
- 不是同一天申请的，先来先得
- 同一天申请，自行协商
软件著作权的两个基本法律文件：
- 《中华人民共和国著作权法》
- 《计算机软件保护条例》

软件许可

许可类型	范围
独占许可	被授权方用，著作权人和第三方均不可用
独家许可	被授权方和著作权人能用，第三方不可用
普通许可	著作权人和任意多的被授权方都可用

数据流图

顶层数据流图，只包含一个表示整个系统的“加工”，即输入与输出

要注意的问题

图中每个数据流、加工、数据存储和外部实体都要命名
一个加工不适合有过多的数据流
分解尽可能均匀

[!warning] 图中不一定要表示出控制流

平衡原则

父图与子图的平衡
- 输入和输出的条数一致
- 方向也要一致
子图内部的平衡：对于每一个加工，要有输入和输出
- 黑洞：只有输入，没有输出（只进不出）
- 奇迹：只有输出，没有输入（无中生有）

活动图

最早、最晚时间计算

也叫PERT图
可以描述任务间的以来关系，但不能清晰描述各任务之间的并行情况

关键路径：开始节点到结束节点之间，持续时间最长的路径 ACEHJK 。其长度就是把路径边值加起来的和 23
里程碑：就是图里的节点
关键路径上的任何活动逾期，都会影响关键路径的长度 (项目的进度)

[!tip] 所以如果有一个活动在关键路径上，问你：它晚开始几天不会影响项目进度，那答案不就是 0 天吗

[!warning]

切记是总时间最长的路径，而不是每一步都选择最长的路径，这玩意不是按照贪心算法得到的！

关键路径不一定只有一条！

[!question] 关键路径上的活动发生变化了，如何计算总时间？

根据题意得到新的活动天数

根据新的活动天数，重新审视活动图，得到新的关键路径，以此计算新的时间

项目管理

n 位成员的开发团队，一共有 $\frac {n (n-1)} 2$ 条沟通路径
概要设计：划分模块，确定功能与接口
详细设计：算法、数据结构、代码、输入/输出格式、用户界面、数据库的物理设计等
原型模型适用于“需求不明确、经常变化”的情况。
结构化分析方法是分析对象的数据流。
软件评审是软件质量保证的主要活动之一。

瀑布模型

不适合开发初期对软件需求缺乏准确全面认知的情况。
容易理解，管理成本低、需求明确、文档齐全、风险控制弱。

增量模型

开发过程划分为若干增量。第一个增量为核心功能。所以：

快速提交可用产品/快速构造核心产品
让用户尽早熟悉系统
高优先级功能先交付

[!tip]
没有又快又稳的方法。你想稳就得慢，你想快，管理成本就会高

敏捷方法

敏捷统一过程 AUP

在大型任务上连续，在小型任务上迭代

注意跟并列征求法区分
采用经典的 UP 阶段性活动，即初始、精化、构建和转换
1. 起始阶段：起始阶段专注于项目的初创活动。
2. 精化阶段：精化阶段在理解了最初的领域范围之后进行需求分析和架构演进。
3. 构建阶段：构建阶段关注系统的构建，产生实现模型。
4. 移交阶段：移交阶段关注于软件提交方面的工作，产生软件增量。

[!tip] 怎么记？

xp极限：极限操作，所以先测试

水晶方法：水晶是个多面体，不同面就是不同的项目，策略也不同

并列争求：都并列了，这么多一起来，那得分一个先后顺序（优先级）

风险管理

回避风险
转移风险
减轻风险
接受风险并控制损失

[!bug] 风险不可消除（避免）。即使预测到风险，也只能提前做好预案，不一定能避免其发生。

ISO/IEC 软件质量模型

CMM

CMM模型指“能力成熟度模型”(Capability Maturity Model for Software）。它是对于软件组织在定义、实施、度量、控制和改善其软件过程的实践中各个发展阶段的描述。CMM的核心是把软件开发视为一个过程，并根据这一原则对软件开发和维护进行过程监控和研究，以使其更加科学化、标准化，使企业能够更好地实现商业目标。CMM模型分为5个等级：①初始级，②可重复级，③已定义级，④定量管理级，⑤优化级。（按成熟度划分，1级最低，5级最高）

基于构建的开发模型

指利用预先打包的构件来构造应用系统
构件可以是组织内部开发的构件，也可以是商品化成品软件构件
本质上是演化模型，需要以迭代方式构建软件

编码设计

绑定方式

静态绑定：编译器
动态绑定：运行时

面相对象设计

识别类及对象、定义属性、定义服务、识别关系、识别包
特殊多态：分为过载多态和强制多态两种
- 过载：同一个名字在不同上下文可代表不同的含义
- 强制：一种类型变量作为参数传递时，隐式转换为另一种类型

耦合

内容耦合（危险的）：一个模块直接使用另一个模块的数据，或通过非正常入口转入另一个模块内部
外部耦合：模块间没有直接关联，通过外部数据环境中的简单全局变量产生关联

[!tip] 公共耦合是通过复杂全局变量

内聚

7种内聚性由高到低：

功能内聚：模块内所有元素完成一个单一功能，各个部分协同工作，缺一不可。
顺序内聚：处理元素相关，而且必须顺序执行。
通信内聚：模块内所有处理元素都在同一个数据结构上操作，或者各处理使用相同的输入数据或产生相同的输出数据。
过程内聚：一个模块完成多个任务，而且这些任务必须按特定的次序执行。
瞬时内聚(时间内聚)：所包含的任务必须在同一时间间隔内执行。
逻辑内聚：模块内执行若干个逻辑上相似的功能，通过参数确定该模块完成哪一个功能。
偶然内聚(巧合内聚)：完成一组没有关系或松散关系的任务。

设计模式

创建型模式，共五种：工厂方法模式、抽象工厂模式、单例模式、建造者模式、原型模式。
结构型模式，共七种：适配器模式、装饰器模式、代理模式、外观模式、桥接模式、组合模式、享元模式。
行为型模式，共十一种：策略模式、模板方法模式、观察者模式、迭代子模式、责任链模式、命令模式、备忘录模式、状态模式、访问者模式、中介者模式、解释器模式。

责任链模式 Responsibility chain

使多个对象都有机会处理请求，从而避免请求的发送者和接收者之间的耦合关系。责任链模式将这些对象连成一条链，沿着该链传递请求，直到有一个对象处理它为止。

属于行为型对象模式。适用于：

有多个对象可以处理一个请求，具体由哪个处理，在运行时自动确定
想在不明确接收者的情况下，向多个对象中的某一个提交请求
可处理一个请求的对象集合应该被动态指定

中介者模式 Mediator

使用一个中介对象封装一系列的对象交互，使各对象不需要显示的相互引用，从而使其耦合松散，可以独立地改变它们之间的交互，类似于“电话接线员”。

属于行为型对象模式。适用于：

一组对象以定义良好但复杂的方式进行通信，产生的依赖关系结构混乱且难以理解
一个对象引用其他很多对象并且直接与这些对象通信，导致难以复用该对象
想定制一个分布在多个类中的行为，而又不想生成太多的子类

观察者模式 Observer

定义对象之间的一种一对多依赖关系，使得每当一个对象改变状态，则其相关依赖对象皆得到通知并被自动更新。

观察者（Observer）至少维护一个被观察对象（Subject）
一个被观察对象需要维护多个观察者
被观察对象需要通知观察者其自身的状态变化

策略模式 Strategy

针对一组算法，将每一个算法封装到具有共同接口的独立的类中，从而使得它们可以相互替换。策略模式使得算法可以在不影响到客户端的情况下发生变化。

装饰模式 Decorator

装饰模式就是把要添加的附加功能分别放在单独的类中，并让这个类包含它要装饰的对象，当需要执行时，客户端就可以有选择地、按顺序地使用装饰功能包装对象。可以给对象动态地添加一些额外的职责，而不改变该对象的结构。

适配器模式 Adaptor

将一个类的接口转换成客户希望的另外一个接口。Adapter模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。

享元模式 Flyweight

通过运用共享技术，有效地支持大量细粒度的对象。系统只使用少量的对象，而这些对象都很相似，状态变化很小，对象使用次数增多。

访问者模式 Visitor

用于表示一个作用于某对象结构中的各元素的操作，它使得用户可以在不改变各元素的类的前提下，定义作用于这些元素的新操作。访问者模式使得新的操作变得很容易，但在一定程度上破坏了封装性。

设计原则

类的设计原则主要有七个，包括：开闭原则、里氏代换原则、迪米特原则（最少知道原则）
单一职责原则、接口分隔原则、依赖倒置原则、组合聚合复用原则。

共同重用原则是指一个包中的所有类应该是共同重用的。如果重用了包中的一个类，那么就要重用包中的所有类。
开放封闭原则，即软件实体（类、模块、函数等）应该是可以扩展的，即开放的。但是不可修改的，即封闭的。
接口分离原则，是指不应该强迫客户依赖于他们不用的方法，接口属于客户，不属于它所在的类层次结构。即依赖于抽象，不依赖于具体，同时，在抽象级别，不应该有对于细节的依赖。
共同封闭原则，是指包中的所有类对于同一类性质的变化应该是共同封闭的。一个变化若对包产生影响，则将对该包中的所有类产生影响，而对于其他的包不造成任何影响。
开闭原则：一个软件实体应当对扩展开放，对修改关闭。
里氏替换原则：子类型必须能够替换它们的基类型，即任何基类对象可以出现的地方，子类对象一定可以出现。
依赖倒转原则：要依赖于抽象，不要依赖于具体。

系统架构

三层 C/S 架构

将软件在逻辑上分成表示层、功能层、数据层

合理划分三层结构的功能，逻辑上保持相对独立，提高系统可维护、可扩展性
更灵活有效地选用软硬件平台和系统
各层可以并行开发，也可以选择各自最合适的开发语言

UML 建模

构件图：系统静态实现
活动图：将进程或其他计算的结构展示为计算内部一步步的控制流和数据流。
包图：模型本身分解而成的组织单元，以及它们之间的依赖关系
静态结构：用例图、类图和包图
动态视图：活动图、状态图、序列图和协作图
- 交互视图：序列图、协作图

用例图

[!question]
include 和 extend 有什么区别？

include 表示的是包含关系。其含义为：当一个用例中所使用的某种功能，而该功能已经被另外的用例所定义，则这两个用例就是包含与被包含的关系，由包含用例 a 指向被包含用例 b ： a ---<<include>>---> b

extend 表示的是扩展关系。其含义为：如果一个用例明显混合了两种及以上的不同场景，即根据实际情况可能发生多种分支，则可以将这个用例分为一个基本用例和一个/多个扩展用例，由扩展用例 b 指向基本用例 a ： a <---<<extend>>--- b

用例执行有先后顺序：依赖关系
多个用例的重复功能抽取出来行成抽象用例。抽象用例与使用它的用例称为使用关系。
泛化关系：表示一个用例是另一个用例的特殊情况。（容易和包含关系混淆，主要关注“特殊”这个关键词）

类图

要求说明类图中的属性和方法时，简要列出名称即可，不需要加上数据类型。例如：

属性：
- 部门编号、姓名、住址、…
- 方法：添加、创建、打开、…

组合与聚合

都是整体与部分的关系，都是关联关系的特殊种类，区别在于：

组合：B 是 A 的一部分，但 A 消失后 B 也不存在，即强聚合
聚合：B 是 A 的一部分，但没有 A，B 也可以独立存在

[!tip]
“碰巧聚在一起，分开也能各自安好”
“我们组成了一个团队，分开了，团队就没了”

序列图

序列图的基本元素：对象、生命线和消息

算法

n 个顶点，e 条弧
- 邻接表，广度优先，时间复杂度为 $O(n+e)$
- 邻接矩阵，广度优先， $O(n^2)$
递归子程序分析属于自上而下的分析法

复杂度分析

算法 A： $T(n)=8T(\frac n 2)+n^2$ ，算法 B： $T(n)=XT(\frac n 4)+n^2$
问：对充分大的 $n$ ，若要算法 B 比 A 快， $X$ 的最大值为多少？

对 A 分析如下：

$T(n)=8T(\frac n 2)+n^2 \implies T(\frac n 2) = 8T(\frac n 4) + \frac {n^2} {4}$

将 $T(\frac n 2)$ 带入左式得：

$T(n)=8(8T(\frac n 4) + \frac{n^2}{4}) + n^2= 64T(\frac n 4) + 3n^2$

当 $n$ 充分大时， $n^2$ 忽略不计，因此 $X \leq 63$ 即可 B 比 A 快。

排序总结

排序方法	时间复杂度 (平均)	时间复杂度 (最坏)	时间复杂度 (最好)	空间复杂度	稳定性
插入排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定
希尔排序	$O(n^{1.3})$	$O(n^2)$	$O(n)$	$O(1)$	不稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
堆排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	$O(1)$	不稳定
冒泡排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定
快速排序	$O(nlog_2n)$	$O(n^2)$	$O(nlog_2n)$	$O(nlog_2n)$	不稳定
归并排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(nlog_2n)$	$O(n)$	稳定
计数排序	$O(n+k)$	$O(n+k)$	$O(n+k)$	$O(n+k)$	稳定
桶排序	$O(n+k)$	$O(n^2)$	$O(n)$	$O(n+k)$	稳定
基数排序	$O(n*k)$	$O(n*k)$	$O(n*k)$	$O(n+k)$	稳定

不稳定：快些选一堆好友来聊天（快速、希尔、选择、堆）

因为情绪不稳定，所以才要“快些选一堆好友来聊天”

时间快：快些归队（快速、希尔、归并、堆）
- 除了希尔，快、归、堆的时间复杂度都是 $O(nlog_2n)$
- 归并的空间复杂度是最高的

折半查找

折半查找是一个分治算法
只能用于有序表
若表长为n，则时间复杂度为 $O(log_n)$

先构造二叉查找树
ASL 成功：比 1 次找到的几个，比 2 次找到的几个，…，除以总共的点数
ASL 失败：比 1 次找不到的几个，比 2 次找不到的几个，…，除以总共找不到的个数

[!warning]
查找长度就是从根结点开始的比较次数，不要去数树的深度！

问题求解

贪心算法：活动安排、01背包、分数背包（部分背包）
分治法：二分搜索、棋盘覆盖
动态规划：矩阵连乘、最长公共子序列
回溯算法：n 后问题、01背包
分支限界：布线问题

软件测试

软件测试的目标来自于需求分析阶段

白盒测试

流程图有 n 个判断节点，就需要 2n 个测试用例才能覆盖所有路径

当然，也可以手动数

各种覆盖方法中，语句覆盖是最弱的
测试原则：
- 程序模块中的所有独立路径至少执行一次
- 在所有的逻辑判断中，取“真”和取“假”的两种情况至少都能执行一次
- 每个循环都应在边界条件和一般条件下各执行一次
- 测试程序内部数据结构的有效性等

McCabe 计算程序复杂度

数流程图中的闭环数
闭环数+1 即为复杂度

面向对象软件的测试

算法层：测试类中定义的每个方法。
类层：测试封装在同一个类中的所有方法与属性之间的相互作用。
模板层：测试一组协同工作的类之间的相互作用。
系统层：把各个子系统组装成完整的面向对象软件系统，在组装过程中同时进行测试。

软件设计

体系结构设计、接口设计、数据设计、过程设计。

四种类型的软件维护

完善性 == 改善性

Linux

用 Apache 作为服务器时，默认的 Web 站目录为 /var/log/httpd

计算机网络

协议

SNMP：简单网络管理协议，使用 UDP，没有安全设计
ICMP：控制报文协议
电子邮件
- 安全的协议：PGP
- 发送：SMTP（端口25）
- 接受：POP3（端口110）
- 交互式邮件存取协议：IMAP（端口143）
CSMA/CD 协议：基带冲突检测的载波监听多路访问技术
Telnet：登录协议，基于 TCP，未加密
IPSec：IP 安全协议，对 IP 数据报进行加密
PPTP：点对点隧道协议，用于封装点对点协议（PPP）的数据包
ARP：将IP解析成MAC，反之则为RARP
DHCP：动态IP分配

端口

应用	协议	端口	功能
FTP	TCP	20(数据),21(控制)
TFTP	UDP	69	简单文件传输
SMTP	TCP	25	邮件发送
POP3	TCP	110	邮件收取
Telnet	TCP	23
DNS	UDP	53
DHCP	UDP	67	动态 IP 配置
SNMP	UDP	161	网络管理

IP 地址

某公司网络的地址是 192.168.192.0/20，要分成 32 个子网，则子网掩码为( )？每个子网可分配的主机地址数是( )？

192.168.192.0/20 为 IP-CIDR 格式，/20 表示前 20 位不变，即网络号。
$32 = 2^5$ ，因此需要 5 位表示子网号。
综上，子网掩码一共占据 20+5=25 位，为 255.255.255.128。

32-25=7 位，因此主机号为 7 位。
0.0.0.0（本地地址）和 255.255.255.255（广播地址）不可作为主机号，因此每个子网可分配的主机地址数为 $2^7-2=126$ 个。

报文

报文交换不能用于语音数据传输

OSI 参考模型

VLAN tag 在数据链路层实现
数据链路层可保障物理线路提供可靠的数据传输
表示层对数据表示进行处理，如数据压缩、加密解密等。

osi

设备

集线器（Hub）在物理层，交换机在数据链路层，路由器在网络层
网络层设备（路由器）既可以隔离冲突域，又可以隔离广播域；
数据链路层设备（交换机、网桥）可以隔离冲突域，不能隔离广播域；
物理层设备（中继器、集线器）无法隔离冲突域和广播域。
特性：
- 电气特性：规定传输二进制位时，线路上信号的电压高低、阻抗匹配、传输速率和距离限制等
- 功能特性：指明某条线路上出现的某一电平表示的意义，以及接口部件的信号线的用途

计算机可靠性

平均时间

MTTF ：Mean Time to Failure，平均无故障时间
MTTR ：Mean Time to Repair，平均修复时间
MTBF ：Mean Time Between Failure，平均故障间隔时间

MTBF = MTTF + MTTR
可靠性 = MTTF / (1 + MTTF)
可用性 = MTBF / (1 + MTBF)
可维护性 = 1 / (1 + MTTR)

计算可靠性

串联系统： $R = R_1 \times R_2 \times ... \times R_n$
并联系统： $R = 1-(1-R_1) \times (1-R_2) \times ...\times (1-R_n)$

数据库相关

设计

ER图用于数据建模
概念结构设计阶段的工作步骤：抽象数据 -> 设计局部视图 -> 合并取消冲突 -> 修改重构消除冗余

三级模式

数据库系统中的视图、存储文件和基本表分别对应数据库系统结构中的外模式、内模式、模式，或者说对应用户视图、内部视图、概念视图
创建聚簇索引，属于物理数据修改，所以改变的是数据库的内模式

范式

[!tip]
数据库最高范式就是为了消除冗余和更新异常，换言之，只要你没到最高，就是有冗余和更新异常的

SQL

视图在数据字典中保存的是视图定义

事物

COMMIT：事务提交。该操作表示事务成功的结束，它将通知事务管理器将该事务的所有更新操作现在可以被提交或永久保留
ROLLBACK：事务回滚。该操作表示事务非成功地结束，它将通知事务管理器出故障了，数据库可能处于不一致状态，该事务的所有更新操作必须回滚或撤销。
COMMIT 产生的影响无法用 ROLLBACK 撤销

编程相关

源码执行流程

词法分析：识别出一个个的单词，删掉无用的信息，报告分析时的错误。
语法分析：将单词划分为语法单位（如表达式、赋值、循环等），确定其语法的正确性（同义说法：正确的逻辑结构）
语义分析：检查是否存在语义错误，例如类型信息、表达式的除数是否为零等。
优化：对前阶段的中间代码进行变换或改造
目标代码生成：优化后的中间代码变换成指令代码或汇编代码

编译器会生成用户源程序的目标代码，而解释器则不产生目标代码。
目标代码经链接后产生可执行代码，可执行代码可独立加载运行，与源程序和编译程序都不再相关。
而在解释方式下，在解释器的控制下执行源程序或其中间代码，因此相对而言，用户程序执行的速度更慢。
中间代码生成和优化不是编译过程中必需的阶段。
对用户源程序依次进行了词法分析、语法分析和语义分析后，原则上就可以产生目标代码了，只是目标代码的质量和效率可能不够高。
词法分析时编译或解释用户源程序过程中唯一与源程序打交道的阶段，其主要功能是按顺序分析出源程序的记号。

语义

程序设计语言的语义分为静态语义和动态语义。

静态语义分析方法是语法制导翻译，其基本思想是将语言结构的语义以属性的形式赋予代表此结构的文法符号，而属性的计算以语义规则的形式赋予文法的产生式。

编译错误

中间代码

中间代码的作用是可使程序的结构在逻辑上更为简单明确，特别是可使目标代码的优化比较容易实现。
中间代码有多种形式，常见的有逆波兰记号(后缀式)、四元式和三元式(三地址码)
与具体的机器无关，不依赖于具体的计算机。

汇编语言

汇编程序的功能是将汇编语言源程序翻译为相应的目标程序
用汇编语言编写的程序必须经过汇编程序翻译成计算机所能识别的机器语言程序(即目标程序)后，才能被计算机执行。
汇编语言是低级程序设计语言
汇编语言与计算机硬件体系结构密切相关

命名对象

需要用户定义的标识符为程序中的对象命名，这个叫命名对象。所以常见的命名对象包括：变量、函数、数据类型。关键字（或保留字）不属于命名对象。

多态

多态分为两种：通用的多态和特定的多态。两者的区别是：

前者对工作的类型不加限制，允许对不同类型的值执行相同的代码；
后者只对有限数量的类型有效，而对不同类型的值可能要执行不同的代码。

通用的多态：

参数多态（Parametric）：采用参数化模板，通过给出不同的类型参数，使得一个结构有多种类型。
包含多态（lnclusion）：同样的操作可用于一个类型及其子类型（注意是子类型，不是子类）。包含多态一般需要进行运行时的类型检查。

特定的多态：

过载多态（Overloading）：同一个名（操作符、函数名）在不同的上下文中有不同的类型，程序设计语言中基本类型的大多数操作符都是过载多态的。
强制多态（Coercion）：编译程序通过语义操作，把操作对象的类型强行加以变换，以符合函数成操作符的要求。程序设计语言中基本类型的大多数操作符，在发生不同类型的数据进行混合运算时，编译程序一般都进行强制多态。

多态（Polymorphism）是指同一个方法调用可以根据对象的不同而表现出不同的行为，包括编译时多态和运行时多态。在编译时多态中，主要体现为方法重载；在运行时多态中，主要体现为方法覆盖。

方法重载（Overload）是指在一个类中定义多个名称相同而参数表不同的方法。在编译时确定调用哪个方法。重载属于编译时多态，是静态多态性的一种体现。
方法覆盖（Override）是指子类重新定义父类中已定义的方法，子类可以在覆盖的方法中实现自己的逻辑。覆盖通过动态绑定机制实现多态，是运行时多态性的一种体现。

Java

即时编译
变量在栈空间分配
对象在堆空间分配

接口

接口中每一个方法都是隐式抽象的，会被隐式的指定为 public abstract（只能是 public abstract，其他修饰符都会报错）。
abstract 不是返回值，接口中的方法返回值该怎么定义还是怎么定义。
接口中可以含有变量，但是接口中的变量会被隐式的指定为 public static final 变量（并且只能是 public，用 private 修饰会报编译错误）。
接口中的方法是不能在接口中实现的，只能由实现接口的类来实现接口中的方法。
A implements B，注意看后续方法中所需的参数到底是 A 还是 B（抽象还是具体），如果需要的是B（抽象），那么声明参数对象时为 B b = new A()

C

无返回值的函数，必须声明 void：void func();
无参数，参数列表可以为空，也可以声明 void：int func(void); // int func();
在C/C++中，非静态局部变量分配在栈区