在DMA方式下，I/0设备向DMA控制器发出传输请求后，DMA控制器开始从I/0设备读取数据，并将数据写入到内存中。这个过程中需要逐段读取和写入数据，在每一次读取操作和写入操作中均需要占用一个总线周期和若干个存储周期。DMA控制器完成一次数据传输通常是分为以下步骤:DMA控制器向I/0设备发送请求并等侍响应;I/0设备返回数据并被DMA控制器接收，此时占用一个总线周期。DMA控制器将接收到的数据暂存在内部缓冲区中;等待DMA控制器从I/0设备读取到足够多的数据准备进行一次写入操作，期间会占用数个存储周期。DMA控制器将暂存在缓冲区中的数据按顺序写入到主存中，期间也会占用数个存储周期。重复执行前面的步骤。

输入/输出处理机(IOP)：输入/输出处理机是一个专用处理机，用于完成主机的输入/输出操作。IOP 根据主机的 I/O 命令，完成对外设数据的输入/输出。

1.11 指令的流水处理-流水线技术

通过重叠多个任务的执行阶段，提高了处理器的效率。

流水线执行时间=流水线建立时间+(n-1)*流水线周期。其中指令中执行时间最长的那个阶段作为流水线周期

1.12 计算机可靠性

从它开始运行(t=0)到某个时刻 t这段时间内能正常运行的概率

MTBF：即平均故障间隔时间。相邻两次故障之间的平均工作时间。

MTRF：即平均恢复时间。故障发生到机器修复平均所需要的时间。

可靠性模型：

串行系统：

并联系统：

1.13 磁盘调度

磁盘调度，主要用于优化磁盘访问性能。当有多个访问者同时请求磁盘操作时，系统需要采用一定的调度策略来决定各等待访问者的执行次序。磁盘调度主要可以分为两类：移臂调度和旋转调度。

移臂调度，负责确定磁道访问顺序，以减少平均寻道时间。移臂调度有多种算法，如先来先服务、最短寻道时间优先和单向扫描调度算法等。

旋转调度，则发生在移动臂定位到目标磁道后。当一条磁道上有多个扇区访问请求时，旋转调度负责确定扇区访问顺序，以减少旋转延迟时间。

1.14 半导体存储器类型

*RAM随机存取，*ROM只读

DRAM（动态随机存取存储器）主要作为计算机的主存使用，它的存储信息依赖于电容的电荷，因此必须定时刷新才能维持数据。DRAM具有较高的密度和较低的成本，但访问速度相对较慢，且能耗较大。

SRAM（静态随机存取存储器）利用触发器原理存储信息，存取速度非常快，功耗也较低。它通常被用作处理器的高速缓存，但由于成本较高，并不适合用作主存。

EPROM（可擦除可编程只读存储器）是一种可编程的只读存储器，用户可以写入内容，但只能写入一次。如果需要修改内容，必须将其全部内容擦除后再重新编程。擦除过程是通过紫外线照射实现的。

EEPROM（电可擦除可编程只读存储器）与EPROM类似，但擦除操作是通过电信号完成的，无需紫外线照射。这使得EEPROM的擦写更为方便，适用于需要频繁更新数据的场合。

2. 程序设计语言基础知识

2.1 程序设计语言的分类

命令式程序设计语言：Fortran、Pascal 和 C 语言

面向对象的程序设计语言：C++、Java和 Smalltalk 、Eiffel

函数式程序设计语言：LISP

逻辑型程序设计语言：Prolog

脚本语言是一种解释性的语言，例如 Python、JavaScript、ActionScript 等。

2.2 栈帧

从逻辑上讲，栈帧就是一个函数执行的环境:函数参数、函数的局部变量、函数执行完后返回到哪里(函数的返回地址)等等。

2.3 算术表达式

2.4 几种常用的中间代码表示形式

后缀式、树形式、三元式、四元式。

2.5 编译器和解释器

编译器和解释器均完成对源程序的翻译。

编译器：编译器将整个源程序一次性编译成可执行的目标代码，执行时不需要编译器，直接在支持目标代码的平台上运行。编译型语言的特点是执行速度快、效率高，但跨平台性较差，因为需要根据不同的操作系统编译代码。

解释器：解释器则是一种逐行转译高级编程语言的程序。它不会一次性把整个程序转译过来，而是对源程序的翻译与执行一次性完成，不生成可存储的目标代码。解释型语言的特点是执行速度慢、效率低，但跨平台性好，同一套代码可以几乎在所有的操作系统上执行，而无需根据操作系统做修改。

2.6 编译原理

词法分析阶段（单词）：从前到后逐个字符地扫描，从中识别出一个个“单词”符号。检查单个词是否正确。

语法分析阶段（语句）：根据语言的语法规则将单词符号序列分解成各类语法单位。识别判断程序语句形式是否正确。

语义分析阶段（类型）：进行类型分析和检查。

2.7 有限自动机(DFA)

2.8 引用传递和值传递

2.9 python 3题

Python 语言的特点：跨平台、开源、支持面向对象、解释型语言。

Python 中的变量赋值不需要类型声明。

python 并不支持 switch 语句，所以多个条件判断，只能用 elif 来实现。

Python 提供了 for 循环和 while 循环（在 Python 中没有 do..while 循环）。

Python 中可以使用引号 ( ' 或 " ) 来创建字符串。Python 不支持单字符类型，单字符在 Python 中也是作为一个字符串使用。

Python 的元组与列表类似，不同之处在于元组的元素不能修改。元组使用小括号，列表使用方括号。

内置函数

abs() 函数返回数字的绝对值

range() 函数可创建一个整数列表。range(0, 10, 3)=[0, 3, 6, 9]

input() 函数接受一个标准输入数据，返回为 string 类型。

divmod() 函数把除数和余数运算结果结合起来，返回一个包含商和余数的元组(a // b, a % b)。

all() 函数用于判断给定的可迭代参数 iterable 中的所有元素是否都为 TRUE，如果是返回 True，否则返回 False。

int() 函数用于将一个字符串或数字转换为整型。

str() 返回一个对象的string格式。

type() 一个参数返回对象类型。

id() 返回对象的内存地址。

2.10 正规集

运算符“ | ”、“ . ” 、“ * ” 分别称为“或”、“连接”和“闭包”。

(0|10)* 表示的正规集为{ε，0，10,00,100,010,0100,1000,1010,10010，……}。

2.11 Java语言的三大特征

封装、继承、多态

封装：封装就是将类的信息隐藏起来（private），不允许外部程序直接访问，而是通过该类的方法实现对隐藏信息的访问。

继承：继承是类与类之间的一种关系。比如说，狗属于动物。就可以看成狗类继承了动物类，那么狗类就是动物类的子类（派生类），动物类就是狗类的父类（基类）。在Java中是单继承的，也就是说一个子类只有一个父类。

多态：多态指的是对象的多种形态。多态有两种：引用多态和方法多态。继承是多态的实现基础。

引用多态：父类的引用可以指向本类的对象；父类的引用可以指向子类的对象。

方法多态：创建父类对象时，调用的方法为父类方法；创建子类对象时，调用的方法是子类重写的方法或继承自父类的方法。动态绑定是实现多态的基础。

3. 计算机网络

3.1 ARP地址解析协议

ARP request报文用来获取目的主机的MAC地址，ARP request报文采用广播的方式在网络上传送，该网络中所有主机包括网关都会接受到此ARP Request报文。接收到报文的目的主机会返回一个ARP Response报文来响应，其中包含自己的MAC地址。ARP Response报文是以单播的方式传送的。

3.2 OSI参考模型

3.3 入侵检测系统(IDS)

入侵检测系统(IDS)是一种用于通过实时监控网络流量来定位和识别恶意流量的软件，入侵检测系统并不能阻止攻击，而只是发出警报。入侵防御系统的功能：

(1)监测并分析用户和系统的活动。

(2)核查系统配置和漏洞。

(3)评估系统关键资源和数据文件的完整性。

(4)识别已知的攻击行为。

(5)统计分析异常行为。

(6)操作系统日志管理，并识别违反安全策略的用户活动。

3.4 ip地址和mac地址的区别

MAC地址是物理地址，IP地址是逻辑地址。MAC地址是不可改变的，IP地址是可以更改的。

MAC长度为48位，IP地址目前主流是32位长。IP地址和MAC地址通过ARP协议联系到一起。

IP地址的分配是基于网络拓扑，MAC地址的分配是基于制造商。

IPv4 32位；IPv6 128位

4. 软件知识产权

(1)软件著作权中的翻译权是将原软件从一种自然语言文字转换成另一种自然语言文字的权利，例如中文翻译成英文。

(2)接受他人委托开发的软件，其著作权的归属由委托者与受委托者签订书面合同约定;无书面合同或者合同未作明确约定的，其著作权由受托人享有。

(3)计算机软件著作权自软件开发完成之日起产生，专利权、商标权都需要去相关部门申请注册之后才能受到保护，而商业秘密由于其特殊性无须申请注册,权利人自商业秘密产生之日就自动取得。

(4)作者的署名权、修改权、保护作品完整权的保护期不受限制。

(5)自然人的作品,其发表权、复制权、发行权等权利的保护期为作者终生及其死亡后五十年,截止于作者死亡后第五十年的12月31日。

(6)软件著作权属于自然人的，该自然人死亡后，在软件著作权的保护期内，软件著作权的继承人可以依照《中华人民共和国继承法》的有关规定，继承软件保护条例第8条规定的除署名权以外的其他权利。

(7)商标：谁先使用谁先获得。

5. 软件工程基础知识

软件工程的基本要素包括方法、工具和过程

5.1 软件开发模型

原型模型：适用于需求不明确的场景，可以帮助用户明确需求。

瀑布模型：将软件生存周期中的各个活动规定为依线性顺序连接的若干阶段，包括需求分析、设计、编码、测试和运行与维护。

增量模型：融合了瀑布模型的基本成分和原型实现的迭代特征，可以有多个可用版本的发布。其核心功能往往最先完成，在此基础上，每轮迭代会有新的增量发布，确保核心功能得到充分测试。

螺旋模型：典型特点是引入了风险分析，结合了瀑布模型和演化模型的优点。

V模型：强调测试贯穿项目始终，而不是集中在测试阶段，是一种测试的开发模型。

喷泉模型：典型的面向对象的模型，特点是迭代、无间隙。会将软件开发划分为多个阶段，但各个阶段无明显界限，并且可以迭代交叉。

快速应用开发（RAD）：是瀑布模型的一个高速变种，强调极短的开发周期，通常基于构件的开发方法获得快速开发。

5.2 软件开发方法

结构化方法：总的指导思想是自顶向下、逐层分解，基本原则是功能的分解与抽象。它包括结构化分析、结构化设计、结构化程序设计，是一种面向数据流的开发方法。此方法适用于数据处理领域的不太复杂的软件。

Jackson方法：是一种面向数据结构的开发方法，它以数据结构为驱动，适合于小规模的项目。Jackson方法把问题分解为可由三种基本结构形式表示的各部分的层次结构。

原型方法：比较适合于用户需求不清、需求经常变化的情况。通过快速构建和迭代原型，可以不断获取用户反馈，逐步优化软件设计。

面向对象方法：以对象作为最基本的元素，对象也是分析问题、解决问题的核心。这种方法强调对象的封装性、继承性和多态性，有助于提高软件的可维护性和可扩展性。

可视化开发方法：在可视开发工具提供的图形用户界面上，通过操作界面元素来自动生成应用软件。这类应用软件的工作方式是事件驱动。

敏捷开发方法：是一种注重迭代和交互的开发方式，强调快速响应变化和紧密合作。敏捷过程的典型方法很多，主要有极限编程、水晶法、并列争球法、自适应软件开发几种：

       极限编程(XP)，是一种轻量级(敏捷)、高效，低风险、柔性、可预测的、科学的软件开发方法，它由价值观、原则、实践和行为4个部分组成。

       水晶法(Crystal)，每一种不同的项目都需要一套不同的策略、约定和方法论。

       并列争球法(Scrum)，用迭代的方法，其中把每30天一次的选代称为一个“冲刺”，并按需求的优先级来实现产品。多个自组织和自治小组并行地递增实现产品。

       自适应软件开发(ASD)，ASD的核心是三个非线性的、重叠的开发阶段：预测，协作与学习。

5.3 环路度量

McCabe复杂性度量一种基于程序控制流的软件质量度量方法，又称为环路度量。v(G)=m-n+2，其中"m"是有向图的弧，"n"为有向图的节点数。

5.4 判定表

针对不同逻辑条件的组合值，分别执行不同的操作。判定表很适合于处理这类问题。

5.5 耦合度

耦合是模块之间的相对独立性(互相连接的紧密程度)的度量。耦合取决于各个模块之间接口的复杂程度、调用模块的方式以及通过接口的信息类型等。

5.6 加密算法

典型的对称加密算法: *ES

        DES：数据加密标准，是一种较早的对称加密算法，速度较快，但密钥长度较短，安全性相对较低。

        3DES：基于DES的改进算法，通过三次使用不同的密钥进行加密，提高了安全性。

        AES：高级加密标准，是目前广泛使用的对称加密算法之一，具有多种密钥长度选择，安全性高且性能优越。

典型的非对称加密算法:*SA、*CC

        RSA：一种基于大数因子分解问题的非对称加密算法，安全性高，广泛应用于各种安全通信场景。

        ECC：基于椭圆曲线数学的加密算法，使用较短的密钥长度就能达到与RSA相当的安全性，适用于资源受限的环境。

        DSA：主要用于数字签名的非对称算法，通过私钥签名和公钥验证，确保数据的完整性和真实性。

典型的摘要算法:

MD5：一种常见的消息摘要算法，生成的摘要长度为128位，广泛应用于数据完整性校验和身份认证等领域。

SHA系列：包括SHA-1、SHA-256等多种算法，生成的摘要长度不同，具有更高的安全性和抗碰撞性，逐渐取代MD5成为最常用的哈希算法之一。

5.7 加密协议

PP2P工作于数据链路层，用于链路加密。

IPSec工作于网络层，为IP数据报文进行加密。

HTTPS是HTTP与SSL的结合体，为传输层以上层次数据加密。

TLS安全传输层协议用于在两个通信应用程序之间提供保密性和数据完整性。

5.8 软件测试

在软件开发过程中，系统测试阶段的测试目标在需求分析阶段就要确认好。

白盒测试方法：在白盒测试中，覆盖方法用于衡量测试用例对程序内部结构的覆盖程度。以下是关于判定覆盖、语句覆盖、条件覆盖和路径覆盖（起点到终点的路径）的详细解释：

5.9 维护的类型

根据维护对象的不同，信息系统维护可以分为以下五类：

根据维护的原因不同，可以将软件维护分为以下四种：

改正性维护：改正软件性能上的缺陷、排除实施中的误使用，应当进行的诊断和改正错误的过程就称为改正性维护。

适应性维护：在使用过程中，为使软件适应外部环境(新的硬、软件配置)、数据环境(数据库、数据格式、数据输入/输出方式、数据存储介质)变化。

改善性维护：对软件提出新的功能与性能要求。

预防性维护：预先提高软件的可维护性、可靠性等，为以后进一步改进软件打下良好基础。

5.10 面向对象的测试层次

从不同层次测试“面向对象软件系统“

算法层：用于测试类中定义的每个方法，基本相当于传统软件测试中的单元测试。

类层：用于测试封装在同一个类中的所有方法与属性之间的相互作用。在面向对象软件中类是基本模板，因此可认为这是面向对象测试中所特有的模块测试。

模板层：用于测试组协同工作的类之间的相互作用。大体上相当于传统软件测试中的集成测试。但这个也有面向对象的特点，如对象之间通过发送消息相互作用。

系统层：把各个子系统组织完成的面向对象的软件系统。测试子系统之间的相互作用。

5.11 软件工具

软件开发工具：

需求分析工具；设计工具；编码与排错工具；测试工具。

软件维护工具：

版本控制工具；文档分析工具；开发信息库工具；逆向工程工具；再工程工具。

软件管理和软件支持工具：

项目管理工具；配置管理工具；软件评价工具。

5.12 软件的质量属性

可用性	MTBF/(1+MTBF)，其中MTBF为平均失效间隔时间	在给定的时间点上，一个系统能够按照规格说明正确运作的概率。
可靠性	MTTF/(1+MTTF)，其中MTTF为平均无故障时间	一个系统对于给定的时间间隔内、在给定条件下无失效运作的概率。
可维护性	1/(1+MTTR)，其中 MTTR 为平均修复时间

6. 结构化开发方法

6.1 最长路径

影响工程进度的关键活动往往是其需要时间最长的活动，因此关键路径也就是最长路径。

6.2 内聚类型（因...而聚集在一起）

偶然内聚(巧合内聚)。指一个模块内的各处理元素之间没有任何联系。

逻辑内聚。指模块内执行若干个逻辑上相似的功能，通过参数确定该模块完成哪一个功能。

时间内聚。把需要同时执行的动作组合在一起形成的模块称为时间内聚模块。

过程内聚。指一个模块完成多个任务，这些任务必须按指定的过程执行。

通信内聚。指模块内的所有处理元素都在同一个数据结构上操作，或者各处理使用相同的输入数据或者产生相同的输出数据。

顺序内聚。指一个模块中的各个处理元素都密切相关于同一功能且必须顺序执行，前一功能元素的输出就是下一功能元素的输入。

功能内聚。这是最强的内聚，指模块内的所有元素共同作用完成一个功能，缺一不可。

7. 面向对象技术

7.1 Java与 C++的区别

完全面向对象。

没有指针。

没有多继承。

解释执行。

7.2 面向对象分析

面向对象分析包含5个活动：认定对象、组织对象、描述对象间的相互作用、确定对象的操作、定义对象的内部信息。

7.3 面向对象设计

面向对象设计时包含的主要活动是识别类及对象、定义属性、定义服务、识别关系、识别包。

7.4 面向对象设计的5大原则

单一责任原则（一个类应该只负责一项职责）；

开放-封闭原则（对扩展开发，对修改封闭）；

里氏替换原则（子类能够替换其基类（或父类））；

依赖倒置原则（抽象不应该依赖于细节，细节应该依赖于抽象）；

接口分离原则（将一个大的接口拆分成更小的和更具体的接口）；

共同封闭原则（包中的所有类应该对于同一类性质的变化是封闭的，这意味着当一个包需要修改时，修改应该只发生在该包内部，而不应该影响到其他包）；

共同重用原则（包中的所有类应该一起被重用，如果一个类被重用了，那么与该类相关的其他类也应该被重用）。

7.5 统一建模语言(UML)中有4种关系

依赖、关联、泛化和实现

依赖。依赖是两个事物之间的语义关系，其中一个事物发生变化会影响另一个事物的语义。

关联。关联描述一组对象之间连接的结构关系，对象之间的连接为链。

泛化。泛化是一般化和特殊化的关系，特殊元素(子元素)的对象可替换一般元素(父元素)的对象。泛化通常通过抽象类或接口来实现。

实现。实现是类之间的语义关系，其中的一个类指定了由另一个类保证执行的契约。

各种关系图例：

7.6 统一建模语言(UML)中的图

类图：类图用于对系统的静态视图建模，主要支持系统的功能需求。类图展现了一组对象、接口、协作和它们之间的关系。在面向对象系统的建模中所建立的最常见的图就是类图。

通常以下述3种方式之一使用类图：(1)对系统的词汇建模；(2)对简单的协作建模；(3)对逻辑数据库模式建模。

对象图：对象图展现了某一时刻一组对象以及它们之间的关系，描述了在类图中所建立的事物的实例的静态快照。对象图一般包括对象和链，如图 7-12 所示。

用例图：用例图用于对系统的静态用例视图进行建模，主要支持系统的行为，用例图展现了一组用例、参与者(Actor)以及它们之间的关系。用例图中包含(include)、扩展(extend)和泛化(generalization)三种关系。

构件图：构件图展现了一组构件之间的组织和依赖。构件图专注于系统的静态实现视图。它与类图相关，通常把构件映射为一个或多个类、接口或协作。

部署图：部署图给出了体系结构的静态实施视图。部署图是用来对面向对象系统的物理方面建模的方法，展现了运行时处理结点以及其中构件(制品)的配置。它与构件图相关。

交互图：交互图用于对系统的动态方面进行建模。一张交互图表现的是一个交互，由一组对象和它们之间的关系组成，包含它们之间可能传递的消息。交互图表现为序列图、通信图、交互概览图和计时图。

序列图（顺序图）：序列图是强调消息时间顺序的交互图；

通信图：通信图是强调接收和发送消息的对象的结构组织的交互图；

活动图：活动图专注于系统的动态视图，用于描述系统中一系列动态过程的执行逻辑。活动图可以表示分支、合并、分岔和汇合。

状态图，状态图关注系统的动态视图，通常是对反应型对象建模。

        状态：描述一个对象在生命周期内的一个时间段。

        转换：表示从一个状态到另一个状态的变化。在状态图中，状态之间的转移通过带箭头的连线表示，箭头指明了转换方向。转换的五要素如下：①源状态②目标状态③触发事件④监护条件（布尔表达式，决定是否激活转换）⑤动作（转换激活时的操作）

        事件：触发状态转换的因素。在UML状态图中，事件可以附加到状态转移上，表示该事件触发了从一个状态到另一个状态的转换。(先达到状态然后触发实现才会转换)

        活动：在状态内部执行的行为或操作。

        动作：在状态转换过程中执行的操作或行为

包图：包图描述的是模型中的包及其包含的元素组合，是维护和控制系统总体结构的重要建模工具。

        包可以拥有其他元素，这些元素可以是类、接口、构件、节点、协作、用例和图，甚至可以是其他包。

        系统中的每个元素都只能为一个包所有，一个包可嵌套在另一个包中。一个包图可以是任何一种的UI图组成，通常是用例图或类图。

        绘制包图的两个注意事项：1)相同包内元素不能重名。2)包和包之间需要尽可能减少耦合度。

7.7 设计模式

创建型模式与对象的创建有关；结构型模式处理类或对象的组合；行为型模式对类或对象怎样交互和怎样分配职责进行描述。

创建型设计模式：

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

抽象工厂（Abstract Factor）：提供一个创建一系列相关或相互依赖对象的接口，而无须指定它们的具体类。抽象工厂模式是指当有多个抽象角色时，使用的一种工厂模式。抽象工厂模式可以向客户端提供一个接口，使客户端在不必指定产品的具体情况下，创建多个产品族中的产品对象。

        工厂方法（Factory Method）：定义一个用于创建对象的接口，让子类决定实例化哪一个类。Factory Method 使一个类的实例化延迟到其子类。

        生成器模式（Builder）：将一个复杂对象的构建与其表示分离，使得同样的构建过程可以创建不同的表示。

        原型模式（prototype）：用原型实例指定创建对象的种类，并且通过拷贝这些原型创建新的对象。

结构型设计模式：

结构性模式涉及如何组合类和对象以获得更大的结构。

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

        桥接（bridge）：将对象的抽象部分与其实现部分分离，从而可以独立地改变它们。

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

        装饰（Decorator）：描述了如何动态地为对象添加职责。这一模式采用递归方式组合对象，允许添加任意多的对象职责。

        外观（ Facade）：为子系统中的一组接口提供一个一致的界面，Facade 模式定义了一个高层接口，这个接口使得这一子系统更加容易使用。

        享元（lyweight）：为共享对象定义了一个结构。至少有两个原因要求对象共享：效率和一致性。Flyweight 模式的对象共享机制主要强调对象的空间效率。使用很多对象的应用必须考虑每一个对象的开销。

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

行为型设计模式：

行为型模式对类或对象怎样交互和怎样分配职责进行描述。行为类模式使用继承机制在类间分派行为;行为对象模式使用对象复合而不是继承。

        责任链模式：它将请求的处理者组织成一条链，并沿着这条链传递请求，直到有一个处理者能够处理它为止。责任链模式的主要目的是通过解耦请求的发送者和接收者来简化对象的交互，让多个对象都有机会处理请求，从而避免了请求的发送者和接收者之间的耦合。

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

        状态模式：允许对象在其内部状态改变时改变他的行为。

        策略模式：定义一系列的算法，把他们一个个封装起来，并使他们可以互相替换。

        中介者模式：用一个中介对象来封装一系列的对象交互，中介者使各对象不需要显式地相互引用，从而使其耦合松散，而且可以独立地改变它们之间的交互。中介者模式属于行为型对象模式。

        命令模式：将一个请求封装为一个对象，从而使得可以用不同的请求对客户进行参数化；对请求排队，或记录请求日志，以及支持可撤销的操作。属于行为型对象模式。

        Memento(备忘录)：在不破坏封装性的前提下捕获一个对象的内部状态，并在对象之外保存这个状态。这样以后就可以将对象恢复到原先保存的状态。

        emplate Method(模板方法)：定义一个操作中的算法骨架，而将一些步骤延迟到子类中。Template Method 使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤。

        Visitor(访问者)：表示一个作用于某对象结构中的各元素的操作。它允许在不改变各元素的类的前提下定义作用于这些元素的新操作。

8. 算法设计与分析

8.1 排序算法的时间空间复杂度

        时间复杂度和空间复杂度是评估算法性能的两个重要指标：

        时间复杂度：描述算法执行时间随输入规模增长的趋势。通常用大O表示法（Big O notation）来表示，例如O(n)、O(n^2)、O(log n)等。

        空间复杂度：描述算法执行过程中所需额外空间随输入规模增长的趋势。同样使用大O表示法来表示。

        以下是一些常见排序算法的时间复杂度和空间复杂度：n 是待排序数组的元素数量。

8.2 算法问题的四种常用策略

        分治法：分治法是一种将问题分解为若干个规模较小但结构与原问题相似的子问题，递归地解决这些子问题，并将子问题的解合并起来得到原问题解的方法。这种方法通常用于解决可以划分为相同子问题的问题，如归并排序、快速排序、二分查找等。

        动态规划：动态规划通常用于求解具有重叠子问题和最优子结构性质的问题。通过将问题分解为子问题，并将子问题的解保存起来以避免重复计算，动态规划可以有效地解决许多复杂问题。例如，背包问题、最短路径问题、最长公共子序列等都是动态规划的典型应用。

        贪心算法：贪心算法在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。贪心算法并不保证得到最优解，但在某些问题中，贪心策略可以得到全局最优解，如最小生成树问题中的普里姆算法和克鲁斯卡尔算法。

        回溯法：回溯法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化来丢弃该解，即“回溯”并尝试另一个可能的解。这种方法通常用于解决组合问题，如八皇后问题、图的着色问题等。

        分支限界法：分支限界法的求解目标是找出满足约束条件的一个解即可。由于求解目标不同，其探索方式与回溯法也不同，分支限界法以广度优先或以最小耗费优先的方式搜索解空间树。

9. 数据库技术基础

9.1 关系模式

关系模式R(U,F)中，R代表关系名，即数据表的名字；U表示属性集合，即数据表中的列名的集合；F表示依赖集合，主要描述属性之间的约束关系，如函数依赖和多值依赖。

9.2 候选键

候选码是用来确保数据库表中每一行数据的唯一性的关键标识。

9.3 将关系模式的函数依赖关系用“有向图”的方式表示

找到入度为0的属性，并以该属性集合为起点，尝试遍历有向图，若能正常遍历图中所有结，则该属性集即为为关系模式的候选键。

若入度为0的属性集不能遍历图中所有结点，则需要尝试性的将一些中间结点(即有入度，也有出度的结点)并入度为0的属性集中，直至该集合能遍历所有结点，集合为候选键。

9.4 主属性和非主属性

主属性是那些包含在任何一个候选码中的属性。非主属性是那些不包含在任何候选码中的属性。

9.5 判断候选码的方法

        如果有属性不在函数依赖集中出现，那么它必须包含在候选码中；

        如果有属性只在函数依赖集右边出现，那么它必不包含在候选码中；

        如果有属性只在函数依赖集的左边出现，则该属性一定包含在候选码中。

        如果有属性或属性组能唯一标识元组，则它就是候选码，也就是说，通过函数依赖所求出的候选码的闭包中，能够包含所有的属性。

        其中如果A和C是入度为0的属性，候选键集合必须包含AC组合键，即AC

9.6 1NF、2NF、3NF、4NF

4种规范化形式，规范化过程的目标是减少数据冗余和依赖问题。重复的数据叫做数据冗余。

1NF 关注列的原子性。

2NF 在1NF的基础上，要求非主键列完全依赖于整个主键。

3NF 在2NF的基础上，进一步要求非主键列之间没有传递依赖关系。即非主属性必须直接依赖于主键。

4NF 限制关系模式的属性之间不允许有非平凡且非函数依赖的多值依赖。

9.7 数据库的三级模式结构

9.8 关系代数

1.条件 / 2.先投影后关联

9.9 数据库设计的6个阶段

(1) 系统需求分析阶段
(2) 概念结构设计阶段
(3) 逻辑结构设计阶段
(4) 物理结构设计阶段
(5) 数据库实施阶段
(6) 数据库运行和维护阶段

10. 数据结构

10.1 折半查找(或称为二分查找，向下取整)

[1..13]中：首先将要查找的元素与中间元素 A[7](下标计算方法为：|1+13|/2=7)进行比较；

第二次比较用的有序表是A[8..13],中间元素的下标为[8+13]/2=10(符号[]表示向下取整),而不是11。

10.2 队列与栈

队列：先进先出，插入数据时移动队尾指针（逻辑+1）；删除数据时移动队头指针（逻辑+1）。

栈：先进后出。

10.3 循环队列

循环队列是将顺序队列形成一个环状结构，元素入队时修改尾指针，元素出队时修改头指针，入队和出队操作都不需要移动队列中的其他元素。

10.4 无向图与邻接矩阵存储

无向图的邻接矩阵就是为了表示图中各个顶点间的关系，有关系是1，没有关系是0.且是一个中线对称的。设图G有n个顶点，则邻接矩阵是一个n*n的方阵，定义为:

10.5 哈夫曼树Huffman和哈夫曼编码

最优二叉树（哈夫·曼树），带权路径长度最小（即代价最小）的二叉树。哈夫曼树中不存在度为1的结点，所以结点。在哈夫曼树中，从根到每个叶子节点的路径可以用来生成对应字符的编码。我们约定，指向左子树的分支表示“0”码，指向右子树的分支表示“1”码。

哈夫曼编码则是基于哈夫曼树的一种数据压缩方法。在哈夫曼编码中，每个字符（或符号）都被赋予一个唯一的二进制编码，这个编码的长度与字符在哈夫曼树中的路径长度相对应。

10.6 二叉树分类

满二叉树：每一层的结点数都达到最大值的二叉树。

完全二叉树：除了最后一层外，其他层节点数都达到最大值的二叉树，并且最后一层的节点都靠左排列。

平衡二叉树：它的左子树和右子树的深度之差的绝对值不超过1，并且它的左子树和右子树都是一棵平衡二叉树。

最优二叉树：带权路径长度最小（即代价最小）的二叉树。

10.7 二叉树遍历

前序遍历：遍历顺序规则为【根左右】。

中序遍历：遍历顺序规则为【左根右】。

后序遍历：遍历顺序规则为【左右根】。

10.8 图的遍历

图的遍历指的是从图中的某一顶点(不是给定顶点)出发，对图中的所有顶点访问一次且只访问一次。图的遍历分为深度优先遍历和广度优先遍历。深度优先遍历是树的先根遍历的推广；广度优先遍历是树的按层次遍历的推广。广度优先遍历的特点是尽可能先进行横向搜索，因此引入队列来保存已访问过的顶点序列，即每当一个顶点被访问后，就将其放入队列中，当队头顶点出队时，就访问其未被访问的邻接点并令这些邻接顶点入队。

10.9 大根堆

每个结点大于左右结点，为序列(55,60,40,10,80,65,15,5,75)建立初始大根堆的过程如图3-56所示

10.10 稀疏矩阵

11. 操作系统知识

11.1 段页式存储管理系统

        地址结构：从图中可见，

        页面地址的长度是13位，2^13=8192,即8K；

        页号部分的地址长度是11位，每个段最大允许有2^11=2048个页；

        段号部分的地址长度是8位，2^8=256,最大允许可有256个段。

11.2 死锁

在有限的资源下，要保证系统不发生死锁，可以按这种逻辑来分析：首先给每个进程分配所需资源数减 1个资源，然后系统还有 1个资源，则不可能发生死锁。

11.3 前趋图

前趋图是一个有向无循环图，它主要用于描述程序（或进程）之间执行的先后顺序。这里进程P1和P6分别是第一个进程和最后一个进程，因此P1只有v操作，信号量是S1、S2，即V(S1)、V(S2)。P6只有P操作，信号量是S7和S8，结果为P(S7)、P(S8)，中间进程P2、P3、P4、P5既有P操作也有V操作，分别是P2:P(S1)、V(S3)、V(S4)，P3:P(S2)、P(S3)、V(S5)，P4:P(S4)、V(86)、V(87)，P5:P(S6)、P(S6)、V(8)。

11.4 磁盘驱动调度

11.5 位示图

计算机字长为64位，那么利用位示图表示时每个字能够表示64个物理块的存储情况

12. 网络与信息安全基础知识

12.1 Web防火墙

是一种针对网络安全的入侵防御系统。Web 应用防火墙(WAF)通过对 HTTP(S)请求进行检测，识别并阻断 SQL 注入、跨站脚本攻击、跨站请求伪造等攻击，保护 web 服务安全稳定。对于正常的软件无法识别并有效阻止。

12.2 IPv4和IPv6

IPv4：32位地址空间

IPv6：128位地址空间

12.3 Internet 服务

域名服务：DNS.在访问主机的时候只需要知道域名，通过DNS服务器将域名变换为IP地址。DNS所用的是 UDP端口，端口号为53。

远程登录服务：Telnet协议

电子邮件服务：

        E-mail服务器主要采用 SMTP(简单邮件传输协议);

        后来的一些协议，包括多用途 Internet 邮件扩充协议(MIME)及增强私密邮件保护协议(PEM),弥补了 SMTP的缺点。

        TCP/IP 网络上的大多数邮件管理程序使用 SMTP来发信，且采用POP(Post Office Protocol,常用的是POP3)来保管用户未能及时取走的邮件。

万维网服务：超文本传输协议(HTTP)

文件传输服务：ftp

网络设计面临的冲突：最低的安装成本、最低的运行成本、最高的运行性能、最大的适应性、最短的故障时间、最大的可靠性、最大的安全性。不可能存在一个网络设计方案，能够使得所有的子目标都达到最优。可采用优先级和建立权重的方法权衡各目标的关心度。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/盐析白兔/article/detail/723548