一. 计算机基础

1.海明码

特点：

• 能检测出2位错，纠出1位错
• 默认进行偶校验

校验位数计算：2^k^ >= k + 位数 + 1

2. 系统可靠度计算

A B两个部件串联，可靠度为 A*B

A B 两个部件并联，可靠度为 1-(1-A)*(1-B)

术语：MTBF(平均故障间隔时间)，是衡量可靠性的指标

3. 存储结构

基本的存储技术包括

• 静态存储器(SRAM)：比DRAM快，但是贵—用作高速缓存Cache，是主存内容的拷贝，Cache与主存的地址映射是由硬件自动完成的
• 动态存储器(DRAM)：主存/图形系统的缓冲区，需要定时对其进行刷新来维持信息不丢失
• ROM存储器：断电信息不丢失
• 固态硬盘

主存与Cache的地址映射方式：

• 全相联：主存中任意一块都可以映射到Cache中的任一块。命中率高，实现复杂且功耗高。
• 直接映射：主存中每个地址块只能映射到Cache的一个固定位置。命中率低，实现简单。
• 组相联：将Cache划分为多个组，每个组内全相联，不同组之间直接映射。常见的包括2路相联，4路相联。

4. 浮点数

如果浮点数的阶码(包括1位阶符)用R位的移码表示，尾数(包括1位数符)用M位的补码表示，则浮点数的表示范围为：

$+(1-2^{-M+1})2^{2^{R-1}-1}$ 到 $-12^{2^{R-1}-1}$​

浮点数能表示的数的范围由阶码的位数决定，精度由尾数的位数决定

浮点数加（减）法操作流程： 零操作数检查、对阶操作、尾 数 加 ( 减 ) 运 算、规格化及舍入处理。

5. 指令的执行时间

第一条指令执行时间+(指令数-1)*各指令段执行时间中最大的执行时间

6. 码

• 补码：正数的补码就是原码。负数的补码是原码（不包括符号位）取反后加1
• 反码：正数的反码和原码一样，负数的反码就是在原码的基础上符号位保持不变，其他位取反
• 移码：正数的移码就是原码。负数的移码是将其原码取反后加上一个偏移值(bias)。移码最常见于表示浮点数的指数部分
• 真值：正数的真值就是原码。负数的真值是用第一位(最高位)表示符号(0正1负)，其余位表示绝对值

7. 存储容量的计算

例. 内存按字节编址，从A1000H到B13FFH的区域的存储容量为（）KB

存储容量 =(B13FFH - A1000H + 1) / 1024 KB = 65KB

8. 总线结构

参考： 计算机体系结构 ｜计算机总线接口技术

总线的本质作用是完成数据交换。总线用于将两个或两个以上的部件连接起来，使得它们之间可以进行数据交换，或者说通信。

按照数据传递方向分类：

• 单向总线：数据只能从一端传递到另一端，而不能反向传递
• 双向总线：也称为双工总线。又可分为半双工总线和全双工总线

按照总线使用的信号类型分类：

• 并行总线：包含多位传输线，在同一时刻可以传输多位数据。优点在于相同频率下总线的带宽更大，适合近距离高速数据传输 。
• 串行总线：只使用一位传输线，同一时刻只传输一位数据。串行总线的传输频率可以大大提升，适合长距离数据传输。

三总线结构的计算机总线系统由数据总线、地址总线和控制总线组成

• 系统总线通常用来连接计算机中的各个部件(如CPU.内存和I/O设备)
• 寄存器和运算器部件主要用片内总线连接
• 接口和外设、DMA控制器和中断控制器由外部总线进行连接

9. 寻址方式

• 直接寻址：给出操作数的有效地址
• 立即寻址：给出可以立即使用的操作数
• 寄存器寻址：给出一个寄存器的编号，如 MOV AX， BX

10. 一些术语英文简称

• CISC: 复杂指令系统计算机
• RISC: 精简指令系统计算机
• VILW: 超长指令字

11. OSI七层网络模型

• 应用层：实现具体的应用功能。
• 表示层：数据的格式与表达、加密、压缩。
• 会话层：建立、管理和终止会话。
• 传输层：端到端的连接。
• 网络层：分组传输和路由选择。
• 数据链路层：传送以帧为单位的信息。
• 物理层：二进制传输。

12. 哈夫曼编码

构造最优二叉树的哈夫曼算法如下：

①根据给定的n个权值｛w1, w2, …, wn｝构成n棵二叉树的集合F={T1, T2, …, Tn}，其中每棵树Ti中只有一个带权为Wi的根结点，其左右子树均空。

②在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，置新构造二叉树的根结点的权值为其左、右子树根结点的权值之和。

③从F中删除这两棵树，同时将新得到的二叉树加入到F中。

重复②、③，直到F中只含一棵树时为止。这棵树便是最优二叉树（哈夫曼树）。

从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称为路径长度。树的路径长度是从树根到每一个结点的路径长度之和。树的带权路径长度为树中所有叶子结点的带权路径长度之和。

例题：一棵哈夫曼树共有127个结点，对其进行哈夫曼编码，共能得到(64 ) 个字符的编码。

当两个字符构造哈夫曼树，就会多出一个节点，若是三个字符则多出两个节点，若是四个字符则多出三个节点，以此类推，若是有n个字符构造哈夫曼数，则会多出n-1个节点。因此哈夫曼树的节点数就是n+n-1个,由此计算出字符数为64

13. IP地址

CIDR表示法：{<网络前缀>，<主机号>} / 网络前缀所占位数

例如：IP地址块222.125.80.128/26包含了（ ）个可用主机地址，其中最小地址是（ ），最大地址是（）

222.125.80.128/26——主机号占6位，222.125.80.10000000

主机号全0的IP地址代表仅网络号指向的那个网段，该IP代表一个网段；主机号全1，IP地址代表网络号指向的全部主机，IP地址代表广播地址 。这两个地址是不可用的主机地址。

最小地址：222.125.80.10000001 = 222.125.80.129

最大地址：222.125.80.10111110 = 222.125.80.128.190

二、设计模式

参考资料：https://refactoringguru.cn/design-patterns/catalog

口诀：类模式——公司模姐，结构型模式——四桥组装外箱带

1.创建型模式

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

• 工厂模式：定义一个创建对象的接口，但由子类决定需要实例化那一个类

• 原型模式：用原型实例指定创建对象的类型，并且通过拷贝原型来创建新对象【实现cloneable接口，实现clone方法，从外部复制对象不一定可行，因为可能有私有变量】

• 单例模式：保证一个类只有一个实例对象，并提供一个全局访问点

• 构建/生成器模式：将一个复杂类的表示与其构造相分离，使得相同的构建过程能够得出不同的表示。这种模式建议将对象构造代码从产品类中抽取出来， 并将其放在一个名为生成器的独立对象中。

  

  这种模式可以避免“重叠构造函数”的出现，可以分步骤生成对象

2.结构型模式

• 适配器模式：将一个接口转换成用户希望得到的另一种接口。使得原本不相容的接口得以协同工作

• 桥接模式：将抽象部分与它的实现部分分离，使他们都可以独立地变化。桥接模式将继承改为组合的方式来解决问题。

  

• 组合模式：将有层级关系的多个对象组合成树形结构以表示“整体-部分”的层次结构

• 装饰模式：动态地给对象添加一些额外的职责、功能。

三、信息安全

1. 五个基本要素

• 机密性：确保信息不暴露给未授权的实体/进程
• 完整性：只有得到允许才能修改数据，并且可以判断数据是否已被篡改
• 可用性：攻击者不能占用所有资源而阻碍授权者的工作
• 可控性：可以控制授权范围内的信息流向及行为方式
• 可审查性：对出现的信息安全文日提供调查的依据和手段

2. 对称与非对称加密

• 对称加密：非公开加密，双方加/解密使用的是同一个密钥。加密强度不高，效率较高，密钥分发困难。

  常见算法：DES AES RC-5 IDEA

• 非对称加密：公开密钥加密，公钥是公开的用于加密，私钥解密，密钥需要成对使用。加密强度较大，效率较低。

  常见算法：RSA DSA ECC

3. 数字签名与信息摘要

参考：https://abcdxyzk.github.io/blog/2022/09/20/tools-https/

数字签名技术是将摘要信息用发送者的私钥加密，与原文一起传送给接收者。接收者只有用发送者的公钥才能解密被加密的摘要信息，然后用HASH函数对收到的原文产生一个摘要信息，与解密的摘要信息对比。如果相同，则说明收到的信息是完整的，在传输过程中没有被修改，否则说明信息被修改过，因此数字签名能够验证信息的完整性。

数字签名是个加密的过程，数字签名验证是个解密的过程。

数字签名作用：

• 接收者可验证消息来源的真实性
• 发送者无法否认发送过该消息
• 接收者无法伪造或者篡改消息

信息摘要：由单向散列函数加密成固定长度的散列值

常见算法：MD5(128位) SHA(160位)

4.一些常见的病毒/木马

• 欢乐时光

  是一个VB源程序病毒，专门感染.htm、.html、.vbs、.asp和.htt文件。它作为电子邮件的附件，并利用Outlook Express的性能缺陷把自己传播出去，利用一个被人们所知的Microsoft Outlook Express的安全漏洞，可以在你没有运行任何附件时就运行自己。还利用Outlook Express的信纸功能，使自己复制在信纸的Html模板上，以便传播。

• 熊猫烧香

  其实是一种蠕虫病毒的变种，而且是经过多次变种而来的，由于中毒电脑的可执行文件会出现“熊猫烧香”图案，所以也被称为“熊猫烧香”病毒。但原病毒只会对EXE图标进行替换，并不会对系统本身进行破坏。

• X卧底软件

  是一种安装在手机里的监控软件，在手机里安装了这种软件，该手机的所有短信，通话记录都将自动上传到后台服务器，安装者在登录后台便可看见目标手机所收发的信息及通话内容，因此X卧底病毒通过木马形式感染智能机。

• CIH病毒

  一种能够破坏计算机系统硬件的恶性病毒。

四、数据库

1.一些基本概念

• 数据库的基本表对应概念视图，存储文件对应内部视图，视图对应用户视图。

2.模式

• 外模式/模式映象：定义在外模式描述中，把描述局部逻辑结构的外模式与描述全局逻辑结构的模式联系起来。

• 保证逻辑独立性：当模式改变时，只要对外模式/模式映象做相应的改变，使外模式保持不变，则以外模式为依据的应用程序不受影响，从而保证了数据与程序之间的逻辑独立性，也就是数据的逻辑独立性。

• 模式/内模式映象：定义在模式描述中，把描述全局逻辑结构的模式与描述物理结构的内模式联系起来。

• 保证物理独立性：当内模式改变时，比如存储设备或存储方式有所改变，只要模式/内模式映象做相应的改变，使模式保持不变，则应用程序保持不变。

五、UML

1.组件图

展现了一组构件之间的组织和依赖，专注于系统的静态（实现）视图，图中通常包括构件、接口以及各种关系

2.通信图

通信图强调收发消息的对象或参与者的结构组织。强调的是对象之间的组织结构（关系）

3.顺序图

顺序图由一组对象或参与者以及它们之间可能发送的消息构成。强调消息的时间次序的交互图。

4.组合结构图

组合结构图用于画出结构化类的内部内容

六、数据流图DFD

参考：

https://blog.csdn.net/qq_29385297/article/details/124460539

https://cloud.tencent.com/developer/article/1781315

例题：https://blog.csdn.net/Catherinemin/article/details/130548751

1. 数据流图组成

2. 数据流图的平衡原则：

（1）父图 ( 上层数据流图 ) 与 子图 ( 下层数据流图 ) 平衡

• 个数一致：两层数据流图中的数据流个数一致
• 方向一致：两层数据流图中的数据流方向一致

（2）守恒加工原则

• 黑洞：加工只有输入没有输出
• 奇迹：加工只有输出没有输入
• 灰洞：加工中输入不足以产生输出

（3）数据守恒原则

• 外部实体与外部实体之间不存在数据流
• 外部实体与数据存储之间不存在数据流
• 数据存储与数据存储之间不存在数据流

七、其他

1. McCabe度量法

McCabe度量法是一种基于程序控制流的复杂性度量方法。

McCabe复杂性度量又称环路度量，其计算公式为: V(g)=m-n+2，其中m和n分别代表图中的边数和顶点数。

2. 面向对象设计

面向对象设计有7个主要原则：

• 里式替换原则：子类可以替换父类
• 迪米特原则：一个对象应当对其他对象有尽可能少的了解
• 接口分离原则：要依赖于抽象，不是具体实践
• 开闭原则：在设计一个对象时，应遵循对扩展开放、对修改关闭
• 依赖倒转原则：指程序中要依赖抽象而不是具体的实现进行编程
• 单一职责原则：设计一个类应只实现单一或独立的职责即业务功能
• 组合/聚合复用原则：尽量使用组合/聚合而不要使用继承

3. 统一过程UP模型

UP(统一过程)模型是一种以用例和风险为驱动、以架构为中心、选代并且增量的开发过程，由UML方法和工具支持。

UP过程定义了五个阶段：

• 起始阶段：专注于项目的初创活动

• 精化阶段：在理解了最初的领域范围之后进行需求分析和架构演进

• 构建阶段：关注系统的构建，产生实现模型

• 移交阶段：关注于软件提交方面的工作，产生软件增量

• 产生阶段

开发过程中有多次选代，每次选代都包含计划，分析、设计、构造、集成和测试，以及内部和外部发布。

每个选代有五个核心工作流，捕获系统应该做什么的需求工作流、精化和结构化需求的分析工作流、在系统结构内实现需求的设计工作流、构造软件的实现工作流和验证是否如期望那样工作的测试工作流。

4. 软著

软件著作权人可以许可他人行使其软件著作权，并有权获得报酬。

软件著作权人可以全部或者部分转让其软件著作权，并有权获得报酬。

为了学习和研究软件内含的设计思想和原理，通过安装、显示、传输或者存储软件等使用软件的，可以不经软件著作权人许可，不向其支付报酬。

5. 排序算法

6. 多态

多态（polymorphism)是不同的对象收到同一消息可以进行不同的响应，产生完全不同的结果，用户可以发送一个通用的消息，而实现细节则由接收对象自行决定，使得同一个消息就可以调用不同的方法，即一个对象具有多种形态。

Cardelli和Wegner将多态分为4种不同的形式：参数多态、包含多态、过载多态和强制多态。其中参数多态是应用比较广的多态，包含多态在许多语言中都存在，最常见的例子就是子类型化。过载多态是同一个名字在不同的上下文中所代表的含义。

7. 软件测试

广义的软件测试由“确认”、“验证”、“测试”三个方面组成

• 确认：是想证实在一个给定的外部环境中软件的逻辑正确性，检查软件在最终的运行环境上是否达到预期的目标

软件修改后要进行退化测试(Regression Test)，因为在修改过程中纠正了老的错误又会引入新的错误，退化测试就是用来防止出现新错误的s。退化测试包括以下步骤：

• 插入新代码，程序成为新版本
• 测试可能受新代码影响功能
• 测试修改前的基本功能
• 测试新版本的功能

对面向对象软件的测试可分为下列的4个层次进行。

（1）算法层：测试类中定义的每个方法。

（2）类层：测试封装在同一个类中的所有方法与属性之间的相互作用。

（3）模板层：测试一组协同工作的类之间的相互作用。

（4）系统层：把各个子系统组装成完整的面向对象软件系统，在组装过程中同时进行测试。

8.死锁资源数计算

例题：如果有3个进程，每个进程需要5个资源，则最少需要___个资源才能避免死锁？

公式：(n1-1) + (n2-1) + (n3-1) = 12个