反码 正数与原码相同；负数，除符号位外，按位取反

补码 正数与原码相同；负数=反码+1

海明码

设数据位是n位，校验位是k位，则n和k必须满足关系： 2ᵏ-1>=n+k

Flynn分类法

MISD（多指令流单数据流）：被证明不可行，没有实际应用

指令集

CISC (Complex Instruction Set Computer，复杂指令集计算机)

指令：指令集庞杂，各指令使用频率差别大，指令可变长格式

寻址方式：支持多种

实现方式：微程序控制技术（微码）

其它：研制周期长

RISC（Reduced Instruction Set Computer，精简指令集计算机）

指令：通过减少指令总数和简化指令功能，降低硬件设计的复杂度，使指令能单周期执行。操作寄存器，只有Load/Store操作内存

寻址方式：支持方式少

实现方式：增加了通用寄存器，硬布线逻辑控制为主，适合采用流水线

其它：优化编译，有效支持高级语言

PV操作

P操作：对信号量减一。测试前置节点是否完成

V操作：对信号量加一。通知后置节点

位示图

某字长为32位的计算机的文件管理系统采用位示图（bitmap）记录磁盘的使用情况。若磁盘的容量为300GB，物理块的大小为1MB，那么位示图的大小为（ 9600）个字。

分析：

一个字32位，一个位指向一个物理块。

3001024MB/1MB=3001024块

300*1024/32=9600

三级模式

内模式：内部视图，物理级数库 概念模式：DBA视图，概念级数据库 外模式：用户视图，用户级数据库

数据库范式

1NF

属性值都是不可分的原子值 在关系模式R中，当且仅当所有域只包含原子值，即每个分量都是不可再分的数据项

2NF

基于1NF，消除非主属性对候选键的部分依赖 当且仅当R满足1NF，且每一个非主属性完全依赖主键（非部分依赖）

3NF

基于2NF，消除非主属性对候选键的传递依赖 当且仅当R满足2NF，且R中非主属性直接依赖主属性（消除传递依赖）

例：给定关系R（A ， B ， C ，D）和关系S（A ，C ，E ，F） πA，C （R）：选取R中的A、C列

σA＞B （R）：选取R中A>B的行

σ3＜4（R×S）：选取笛卡尔积RXS中第三列小于第四列的行

网络协议

POP3、FTP等为应用层

TCP、UDP为传输层

IP、ARP等为网络层

220.112.179.92/22：表示前22位为网络号，后10位为主机号

179=128+32+16+2+1→ 10110011，前6位为网络号

（1）逻辑覆盖

语句覆盖。语句覆盖是指选择足够的测试数据，使被测试程序中每条语句至少执行一次。语句覆盖对程序执行逻辑的覆盖很低，因此一般认为它是很弱的逻辑覆盖。

判定覆盖（分支覆盖）。判定覆盖是指设计足够的测试用例，使得被测程序中每个判定表达式至少获得一次“真”值和“假”值。或者说是程序中的每一个取“真”分支和取“假”分支至少都通过一次，因此判定覆盖也称为分支覆盖。

条件覆盖。条件覆盖是指构造一组测试用例，使得每一判定语句中每个逻辑条件的各种可能的值至少满足一次。

路径覆盖。路径覆盖是指覆盖被测试程序中所有可能的路径。(分支之间组合)

耦合

数据耦合。指两个模块之间有调用关系，传递的是简单的数据值，相当于高级语言中的值传递。这种耦合程度较低，模块的独立性较高。控制耦合。指一个模块调用另一个模块时，传递的是控制变量，被调模块通过该控制变量的值有选择地执行块内的某一功能。公共耦合。指通过一个公共数据环境相互作用的那些模块之间的耦合。内容耦合。这是程度最高的耦合。当一个模块直接使用另一个模块的内部数据，或通过非正常入口而转入另一个模块内部，这种模块之间的耦合为内容耦合，这种情况往往出现在汇编程序设计中。

内聚

偶然内聚。指一个模块内的各个处理元素之间没有任何联系。逻辑内聚。指模块内执行几个逻辑上相似的功能，通过参数确定该模块完成哪一个功能。时间内聚。把需要同时执行的动作组合在一起形成的模块为时间内聚模块。通信内聚。指模块内所有处理元素都在同一个数据结构上操作，或者指各处理使用相同的输入数据或者产生相同的输出数据。顺序内聚（过程内聚）。指一个模块中各个处理元素都密切相关于同一功能且必须顺序执行，前一功能元素的输出就是下一功能元素的输入。（也叫过程内聚）功能内聚。这是最强的内聚。指模块内所有元素共同完成一个功能，缺一不可。耦合性和内聚性是模块独立性的两个定性标准，将软件系统划分模块时，尽量做到高内聚、低耦合，提高模块的独立性。软件开发过程模型（重点，各模型的特点和区别）

瀑布模型:

瀑布模型是将软件生存周期各个活动规定为依线性顺序连接的若干阶段的模型。需求是明确和完整的。

它是一种理想的线性开发模式，缺乏灵活性，特别是无法解决软件需求不明确或不准确的问题。

螺旋模型：

螺旋模型最大的特点在于引入了其他模型不具备的风险分析，使软件在无法排除重大风险时有机会停止，以减小损失。同时，在每个迭代阶段构建原型是螺旋模型用以减小风险的途径。螺旋模型更适合大型的昂贵的系统级的软件应用。

对于复杂的大型软件，开发一个原型往往达不到要求。螺旋模型将瀑布模型和演化模型结合起来，加入了两种模型均忽略的风险分析，弥补了这两种模型的不足。

螺旋模型将开发过程分为几个螺旋周期，每个螺旋周期大致和瀑布模型相符合。在每个螺旋周期分为如下4个工作步。

（1）制定计划。确定软件的目标，选定实施方案，明确项目开发的限制条件。

（2）风险分析。分析所选的方案，识别风险，消除风险。

（3）实施工程。实施软件开发，验证阶段性产品。

（4）用户评估。评价开发工作，提出修正建议，建立下一个周期的开发计划。

喷泉模型:

喷泉模型是一种以用户需求为动力，以对象作为驱动的模型，适合于面向对象的开发方法。它克服了瀑布模型不支持软件重用和多项开发活动集成的局限性。喷泉模型使开发过程具有迭代性和无间隙

性。迭代意味着模型中的开发活动常常需要重复多次，在迭代过程中不断地完善软件系统。无间隙是指在开发活动（如分析、设计、编码）之间不存在明显的边界，也就是说，它不像瀑布模型那样，需求分析活动结束后才开始设计活动，设计活动结束后才开始编码活动，而是允许各开发活动交叉、迭代地进行。

增量模型

增量模型是一种非整体开发的模型，该模型具有较大的灵活性，适合于软件需求不明确的一种模型。使用该模型开发产品，一般是尽快构造出可运行的产品，然后在该产品的基础上再增加需要的新的构建，使产品更趋于完善。

原型模型

原型模型基于这样一种客观事实：并非所有的需求在系统开发之前都能准确地说明和定义。因此，它不追求也不可能要求对需求的严格定义，而是采用了动态定义需求的方法。它适用于需求不明确的开发环境。

软件复杂性

McCabe度量法:

节点数n＝6，弧数m＝9，p＝1

V(G)=m-n+2p=9-6+2=5

UML

（2）关联（association）。关联是一种结构关系，它描述了一组链，链是对象之间的连接。聚集（aggregation）是一种特殊类型的关联，它描述了整体和部分间的结构关系。关联和聚集的图形化表示如图10-13和图10-14所示。

关联：直线，两端有重复度（数字）和角色

聚集：虚心菱形

在关联上可以标注重复度（multiplicity）和角色（role）。

组合：实心菱形

（3）泛化（generalization）。泛化是一种特殊／一般关系，特殊元素（子元素）的对象可替代一般元素（父元素）的对象。用这种方法，子元素共享了父元素的结构和行为。在图形上，把一个泛化关系画成一条带有空心箭头的实线，它指向父元素，如图10-15所示

（4）实现（realization）。实现是类元之间的语义关系，其中一个类元指定了由另一个类元保证执行的契约。在两种地方要遇到实现关系：一种是在接口和实现它们的类或构件之间；另一种是在用例和实现它们的协作之间。在图形上，把一个实现关系画成一条带有空心箭头的虚线，如图10-16所示

设计模式

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

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

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

装饰模式

一种对象结构型模式，可动态地给一个对象增加一些额外的职责，就增加对象功能来说，装饰模式比生成子类实现更为灵活。通过装饰模式，可以在不影响其他对象的情况下，以动态、透明的方式给单个对象添加职责；当需要动态地给一个对象增加功能，这些功能可以再动态地被撤销时可使用装饰模式；当不能采用生成子类的方法进行扩充时也可使用装饰模式。

外观模式

一种对象的结构模式，要求外部与一个子系统的通信必须通过一个统一的外观对象进行，为子系统中的一组接口提供一个一致的界面，外观模式定义了一个高层接口，这个接口使得这一子系统更加容易使用。

策略模式：

策略模式定义了一系列的算法，并将每一个算法封装起来，而且使它们还可以相互替换。策略模式让算法独立于使用它的客户而独立变化。

应用场景：

1、 多个类只区别在表现行为不同，可以使用Strategy模式，在运行时动态选择具体要执行的行为。 2、 需要在不同情况下使用不同的策略(算法)，或者策略还可能在未来用其它方式来实现。

3、 对客户隐藏具体策略(算法)的实现细节，彼此完全独立。

状态模式：

当一个对象的内在状态改变时允许改变其行为，这个对象看起来像是改变了其类。

命令模式（Command）：

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

享元模式（Flyweight）：提供支持大量细粒度对象共享的有效方法。

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

职责链模式（Chain of Responsibility）：通过给多个对象处理请求的机会，减少请求的发送者与接收者之间的耦合。将接收对象链接起来，在链中传递请求，直到有一个对象处理这个请求。

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

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

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

桥接模式（bridge）：将抽象部分与实现部分分离，使得它们两部分可以独立地变化。

模式分类

创建型模式包括工厂方法（Factory Method）、抽象工厂（Abstract Factory）、单例（Singleton）、构建（Builder）、原型（Prototype）模式 。

结构型模式包括适配器（Adapter）、合成（Composite）、装饰（Decorator）、代理（Proxy）、享元（Flyweight）、门面（Façade）、桥接（Bridge）模式。

行为型模式包括策略（Strategy）、模板方法（Template Method）、迭代器（Iterator）、责任链（Chain of Responsibility）、命令（Command）、备忘录（Memento）、状态（State）、访问者（Visitor）、解释器（（Interpreter）、调停者（Mediator）、观察者（Observer）模式。

排序算法

稳定排序方法：直接插入、冒泡、归并、基数

拓扑排序通俗一点来讲，其实就是依次遍历没有前驱结点的结点。而某一时刻没有前驱结点的结点有可能存在多个，所以一个图的拓扑排序可能有多个。

使用队列可以对图进行广度优先遍历。

循环队列

设某循环队列Q的定义中有front和rear两个域变量，其中，front指示队头元素的位置，rear指示队尾元素之后的位置，如下图所示。若该队列的容量为M，则其长度为（ ）。

可以计算得知（Q.rear-Q.front+M）%M为队列中的元素个数（即队列长度）。

队尾元素指针：（Q.front+Q.size-1+M）%M

队头元素指针：（Q.rear-Q.size+M）%M

程序设计语言的语法基本上都是上下文无关文法。

编译程序的功能是把用高级语言书写的源程序翻译成与之等价的目标程序。编译过程划分成词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成6个阶段。目标程序可以独立于源程序运行。中间代码生成、代码优化不是必须的。

解释程序是一种语言处理程序，在词法、语法和语义分析方面与编译程序的工作原理基本相同，但在运行用户程序时，它是直接执行源程序或源程序的内部形式(中间代码)。因此，解释程序并不产生目标程序，这是它和编译程序的主要区别。

中间代码的表达形式有语法树，后缀式，三地址代码。

中间代码可以用树或图表示。

中间代码有利于进行与机器无关的优化处理。

表达式采用逆波兰式表示时，利用（ 栈 ）进行求值。

算术表达式默认为左中右排序。

1.如果取样速率大于模拟信号最高频率的2倍，则可以用得到的样本中恢复原来的模拟信号。

2.DPI：每英寸的像素

改变数字载波频率可以改变乐音的音调。

改变它的幅度就可以改变乐音的音高。

4.人耳能听到的声音视率范围是：20Hz-20KHz。低于这个区间的，叫次声波，高于这个区间的叫超声波。

卷烟、雪茄烟和有包装的烟丝，应当使用注册商标；申请注册商标，应当持国务院烟草专卖行政主管部门的批准生产文件，依法申请注册。”

注册商标有效期满，需要继续使用的，应当在期满前六个月内申请续展注册。专利权和著作权到期后都无法延长，而商业秘密权无期限限制。