第一章计算机组成与体系结构

原码、反码、补码、移码

正数：原码、反码、补码相同，移码在补码的基础上取反

负数：反码取反，补码=反码+1

使用补码参与加减运算

浮点的表示：N=尾数*基数指数

浮点的运算过程：对阶→尾数计算→结果格式化

浮点运算的特点：

1、一般尾数用补码，阶码用移码

2、阶码的位数决定数的表示范围，位数越多范围越大

3、尾数的位数决定数的有效精度，位数越多精度越高

4、对阶时，小数向大数看齐

5、对阶是通过较小数的尾数右移实现的

计算机结构

运算器：①算数逻辑单元ALU、②累加寄存器、③数据缓冲寄存器、（④状态条件寄存器？）

控制器：①程序计数器PC、②指令寄存器IR、地址寄存器③指令译码器、④时序部件

寻址方式：立即寻址方式、直接寻址方式、间接寻址方式、寄存器寻址方式、寄存器间接寻址方式

CISC与RISC比较：指令数量、指令使用频率、寻址方式、寄存器、流水线支持、高级语言支持。

CISC(Complex Instruction Set Computer)：复杂，指令数量多，频率差别大，多寻址

RISC(Reduced Instruction Set Computing)：精简，指令数量少，操作寄存器，单周期，少寻址，多通用寄存器，流水线

流水线周期为执行时间最长的一段

流水线计算理论公式：（t1+t2+t3+…+tk）+（n-1）*△t

流水线计算实践公式：k*△t +（n-1）*△t

流水线的吞吐率（though put rate，TP）=指令条数/流水线执行时间

流水线的最大吞吐率TP=1/△t

层次化存储结构

CPU（寄存器，最快，容量小，成本高）→Cache（按内容存取）→内存→外存

Cache-映像：①直接相联映像（硬件电路比较简单，但冲突率很高）②全相联映像（电路难于设计和实现，只适用于小容量的cache，冲突率较低）③组相联映像（直接相联与全相联的折中）

地址映像是将主存与Cache的存储空间划分为若干大小相同的页（或成为块）

主存-编址与计算

总片数=总容量/每片的容量

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

总线的分类：内部总线（微机内部外围芯片与处理器的总线，芯片级别）、系统总线（各个插件版与系统版之间的总线，插件级别）、外部总线（微机与外部的总线）

系统总线分为：

1.数据总线（Data Bus）：在CPU于RAM之间来回传送需要处理或者需要储存的数据。

2.地址总线（Address Bus）：用来指定在RAM（RandomAccess Memory）之中存储的数据的地址。

3.控制总线（Control Bus）：将微处理器控制单元（ControlUnit）的信号传送到周边设备，一般常见的为USB Bus和1394 Bus。

检验码

奇偶校验：可检查1位的错误，不可纠错

循环校验码CRC：可检错，不可纠错

海明校验码：可检错，也可纠错。2r≥m+r+1

第 2 章操作系统

进程的状态：运行、就绪、等待

进程的同步与互斥：直接制约关系、间接制约关系、临界资源

存储管理

分区存储组织

1.首次适应法：空闲区域从当前地址开始，在首次能够容纳N k空间的地方分配

2.最佳适应法：空闲区间从小到大排列，适配N k空间存放（容易造成大量碎块）

3.最差适应法：空闲区域从大到小排列，适配N k空间存放

4.循环首次适应法：空闲区域从当前地址开始分配，尾部与首部连接。避免每次都在相同区域分配。

页式存储：将程序与内存划分为同样大小的块，以页为单位存储

优点：利用率高，碎片小，分配及管理简单

缺点：增加了系统开销，可能产生抖动现象

段式存储：按用户作业中的自然段来划分逻辑空间，然后调入内存，段的长度可以不一样

优点：多道程序共享内容，各段程序修改互不影响

缺点：内存利用率低，内存碎片浪费大

段页式存储：段式与页式的综合体。先分段，再分页。一个程序有若干个段，每个段中可以有若干页，每个页的大小相同，单每个段的大小不同

优点：空间浪费小、存储共享容易、存储保护容易、能动态链接

缺点：由于管理软件的通知，复杂性和开销也随之增加，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降

页面置换算法：

最优（Optimal，OPT）算法

随机（RAND）算法

先进先出（FIFO）算法：有可能产生“抖动”。

最近最少使用（LRU）算法：不会抖动，理论依据是“局部性原理”

时间局部性：刚被访问的内容，立即又被访问

空间局部性：刚被访问的内容，临近的空间很快被访问

磁盘管理：存取时间=寻道时间+等待时间（平均定位时间+转动延迟）

磁盘调度算法：先来先服务（FCFS）、最短寻道时间优先（SSTF）、扫描算法（SCAN）、循环扫描（CSCAN算法）

作业调度算法：先来先服务法、时间片轮转法、短作业优先法、最高优先权优先法、高响应比优先法（响应比=作业等待时间/作业执行时间）

数据传输控制方式：（效率由低到高）

程序控制（查询）方式：分为无条件传输和程序查询方式两种。方法简单，硬件开销小，但I/0能力不高，严重影响CPU的利用率

程序中断方式：与程序控制方式相比，中断方式因为CPU无需等待而提高了传输的响应速度

DMA方式：DMA方式是为了在主存和外设之间实现告诉、批量数据交换而设置的。DMA方式比程序控制方式与中断方式都高效。

通道方式

I/O处理机

第 3 章数据库系统

三层模式-两层映射:

外模式（用户模式。视图级）

—-概念模式映射—-

概念模式（表级）

—-内模式映射—-

内模式（存储模式。文件级）

数据库设计过程：需求分析（数据流图、数据字典、需求说明书）、概念结构设计（ER模型）、逻辑结构设计（关系模式）、物理设计

E-R模型

○属性

□实体

◇联系

—○—特殊化

|□|弱实体

关系代数：

并（S1 U S2）：合并表，会剔除相同的

交（S1 ∩ S2）：查交集

差（S1 – S2）：在S1的基础上去掉S2有的

笛卡尔积（S1×S2）：S1的每一条单独和S2的每一条组合

投影（πS*（S1）或π1（S1））：投影S1中的S*列/投影S1中的第一列

选择（δS*=**（S1））：在S1中选择符合条件S*=**的数据

联接（S1▷◁S2）：把S1和S2自然连接、去重复的行、去重复的列。相当于，做笛卡尔积后做选择后做投影

规范化理论

重复的数据信息会存在：数据冗余、修改异常、插入异常、删除异常。

键：候选键（唯一表示元组，切无冗余）、主键（候选键任选一个）、外键（其他关系）

范式：

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

第二范式（1NF）：当且仅当关系模式R是第一范式（1NF），且每一个非主要属性完全依赖候选键（没有不完全依赖）时，则称关系模式R是第二范式。（反例：A+B→C、A→D，存在不完全依赖关系，应拆成两个表）

第三范式（3NF）：当且仅当关系模式R是第二范式（2NF），且R中没有非主属性传递依赖于候选键时，则称关系模式R是第三范式（反例：存在A→B，B→C。则A可以间接推导出C，存在传递依赖）

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

SQL语句

建表语句 CREATE TABLE <表名1> (<列名> <数据类型>)

设主键 PRIMARY KEY

设非空值 NOT NULL

设唯一 UNIQUE

设外键FOREIGN KEY (Sno) REFERENCES S(Sno)连接到S表

删除表 DROP TABLE<表名>

增删改表结构ALTER TABLE <表名> [ADD <新列名><数据类型>] [DROP <列名>] [MODIFY/CHANGE<列名><数据类型>]

分组 GROUP BY

排序ORDER BY

插入数据 INSERT INTO ~

修改数据 UPDATE ~ SET~

删除数据DELETE FROM~

并发控制

事务：原子性、一致性、隔离性、持续性

第4章计算机网络与信息安全

OSI七层模型

层次

名称

主要功能

主要设备及协议

对应TCP/IP模型

7

应用层

实现具体的应用功能

基于TCP：POP3（110）、FTP（主动端口20/控制端口21）、HTTP（80）、HTTPS（443）、TELNET（23）、SMTP（25）

基于UDP：DHCP（67）、TFTP（小文件传输协议69）、SNMP（网络管理协议161）、DNS（53）

应用层

6

表示层

数据的格式与表达、加密、压缩

5

会话层

建立、管理和终止会话

4

传输层

端到端的连接（单位：报文）

TCP（传输控制协议，面向连接）、UDP（用户数据报协议，无连接）

传输层

3

网络层

分组传输和路由选择（单位：包）

三层交换机、路由器

ARP（地址解析协议，IP→MAC）、PARP（反向地址解析协议）、IP（网际协议）、ICMP（因特网控制协议）、IGMP（组播协议、网关协议）

网际层

2

数据链路层

传输以帧为单位的信息

网桥、交换机（多端口网桥）、网卡

PPTP、L2TP、SLIP、PPP

网络接口层

1

物理层

二进制传输（单位：bit）

中继器、集线器（Hub，端口中继器）

SCMA/CD（载波监听多路访问）

对称加密算法：DES、3DES（三重DES）、RC-5、RDEA

非对称加密算法：RSA、ECC（椭圆曲线加密算法）。加密速度慢，加密强度高

信息摘要：MD5（128位）、SHA（160位）

第5章系统开发基础

开发模型：

瀑布模型：适用于需求比较明确的

①定义阶段【软件计划（可行性分析报告+软件计划书）→需求分析（需求规格说明书）】

②→开发阶段【软件设计（概要设计说明书+详细设计说明书）→程序编码→软件测试（测试计划+测试用例+测试报告）】

③→维护阶段【运行维护】

V模型：

需求分析→概要设计→详细设计→编码→单元测试→集成测试→系统测试→验收测试

喷泉模型：面向对象的开发模型

分析、设计、实现、测试、维护、演化

原型化模型（探索模型、实验模型、演化模型）

螺旋模型（综合瀑布模型和原型化模型，适合于开发高风险项目）

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

初始→细化→构建→交付

敏捷开发方法：XP（极限编程。费用严格控制）、cockbum的水晶系列方法（用最少的纪律约束而能获得成功的方法）、开放式源码（程序开发人员在地域上分布很广）、SCRUM（并列争球法，明确定义了的可重复的方法过程）、Coad的功用驱动开发方法、ASD方法（猜测、合作与学习）

信息系统开发方法：

结构化方法（面向数据流）

原型法

面向对象方法

面向服务的方法

需求分析：

需求的任务

需求的过程（问题识别、分析与综合、编制需求分析文档、需求分析与评审）

需求的分类（功能需求、非功能需求、设计约束）

应用的工具（数据流图DFD、数据字典DD、判定表、判定树）

软件设计——应用的工具：IPO图（输入处理输出图）、PDL（程序描述语言）、PAD（问题分析图）、程序流程图、N/S盒图

模块的独立性：高内聚低耦合

内聚性由高到低：功能内聚、程序内聚、通信内聚、过程内聚、限时内聚（时间内聚）、逻辑内聚、偶然内聚（巧合内聚）

耦合性由低到高：非直接耦合、数据耦合、标记耦合、控制耦合、外部耦合、公共耦合、内容耦合

耦合性：①如果一个模块访问另一个模块时，彼此之间是通过数据参数（不是控制参数、公共数据结构或外部变量）来交换输入、输出信息的，则称这种耦合为数据耦合②如果一组模块通过数据结构本身传递，则称这种耦合为标记耦合③若一组模块都访问同一个公共数据环境，则它们之间的耦合就称为公共耦合④若一个模块直接访问另一个模块的内部数据、一个模块不通过正常入口转到另一个模块内部、两个模块有一部分程序代码重叠或者一个模块有多个入口，上述几个情形之一发生则说明两个模块之间就发生了内容耦合。

内聚性：

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

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

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

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

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

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

软件测试-McCabe

计算有向图G的环路复杂度V(G)=M-N+2（m边数，n节点数）。或者计算，封闭区间数+1

软件维护

可维护性因素决定：可理解性、可测试性、可修改性

软件维护类型：改正性维护、适应性维护、预防性维护、完善性维护

第6章面向对象技术

基本概念：对象、类（实体类/控制类/边界类）、继承与泛化、封装、多态、接口、重载、模板类、消息和消息通信

面向对象7大设计原则：单一职责原则、开放-封闭原则、李氏（Liskov）替换原则、依赖倒置原则、接口隔离原则、组合重用原则、迪米特（Demeter）原则（最少知识法则）

UML 通用建模语言

Booch、OOSE、OMT(ObjectModeling Technique)→UML2.0

Jackson、结构化方法→面向数据结构

UML：结构图（类图、对象图、包图、组合结构图、构件图、部署图、制品图）、行为图（用例图、顺序图、通信图、定时图、状态图、活动图、交互概览图）

类图的四种关系：

依赖关系：一个事物变化会影响另一个实物 – – – – – – – – — -▶（虚线+实心右箭头）

泛化关系：特殊与一般的关系 ——————▷（实线+空心右箭头）

关联关系：包含聚合关系和组合关系。描述了一组链，链是对象之间的连接。

聚合关系：整体与生命周期不同 ——————◇（实线+空心菱形）

组合关系：整体与生命周期相同 ——————◆（实线+实心菱形）

实现关系：接口与类之间的关系 – – – — – – – – – -▷（虚线+空心右箭头）

（1）用例视图（Use-case View）

由专门描述可被最终用户、分析人员、测试人员看到的系统行为的用例图组成。

最终用户使用用例图——理解要完成的系统的功能，确认是否符合自己的要求。

分析人员使用用例图——描述用户需求。

测试人员使用用例图——根据用例图验证实现后的系统是否符合用户需求。

（2）设计视图（Logical View）

包含了主要的设计包、子系统、类和接口，主要从软件角度描述系统要解决的问题和解决方案。

（3）进程视图（Process View）

主要针对系统性能、可扩展行和吞吐量。

（4）实现视图（Implementation View）

在UML实现视图用类图、包图、对象图、顺序图、合作图、状态图、和活动图来描述。编程人员根据设计视图和进程视图来最终实现系统。

（5）部署视图（Deployment View）

包含了系统硬件拓扑结构点各种软件模块和构件模块。

需求

–采用用例图描述需求。

分析

–采用类图描述静态结构

–采用顺序图、合作图、活动图、状态图描述动态行为

设计

–采用类图、包，对类的接口进行设计

实现

–将类用某现象对象语言实现

继承与交付

–构件图、包、部署图

–单元测试——类图和类的说明书

–继承测试——类图、包、构件图、合作图

–系统测试——例图

设计模式的分类

创建型模式：工厂方法（factorymethod）模式、抽象工厂（abstract factory）模式、原型（prototype）模式、单例（singleton）模式、构建器（builder）模式

结构型模式：适配器（adapter）模式、桥接（bridge）模式、组合（composite）模式、装饰（decorator）模式、外观（facade）模式、享元（flyweight）模式、代理（proxy）模式

行为型模式：职责链（chain ofresponsilbility）模式、命令（command）模式、解释器（interpreter）模式、迭代器（iterator）模式、中介者（mediator）模式、备忘录（memento）模式、观察者（observer）模式、状态（state）模式、模板方法（template method）模式、访问者（visitor）模式

第7章数据结构与算法基础

稀疏矩阵：个数=(n*n-n)/2+n

线性表：顺序表、链表（单链表、循环链表、双向链表）

广义表：head（LS）取广义表的头，tail（LS）取广义表除了头之外的其他

树转二叉树：孩子节点在左子树节点；兄弟节点在右孩子节点

查找二叉树：二叉排序树，左孩子小于根，右孩子大于根

哈夫曼树：求带权路径长度，所有值乘以深度的和

线索二叉树

平衡二叉树：任意节点的左右子树深度相差不超过1

完全图：无向图每对顶点之间都有一条边相联；有向图每对顶点之间都有二条有向边相联

图的最小生成树：类似城市规划修路

第 8 章程序设计语言与语言处理程序基础

文法定义G=（V,T,S,P）

V：非终结符。不是语言组成部分，不是最终结果，可理解为占位符

T：终结符。是语言的组成部分，是最终结果

S：起始符。是语言的开始符号

P：产生式。用终结符替代非终结符的规则。

有限自动机M=（S,Σ,δ,S0,Z）

S是一个有限集，每个元素为一个状态

Σ是一个有穷字母表，每个元素为一个输入字符

δ是转换函数，是一个单值对照

S0属于S，是其唯一的初态

Z是一个终结集（可空）

第 9 章多媒体基础知识

音频：

采样：采样频率、采样精度；采样频率应为声音最高频率的2倍

A/D转换：采样→量化→编码

常见音频格式：WAVE、MP3、MIDI

每秒容量=采样频率（Hz）*量化/采样位数（位）*声道数/8

图像：位数=log2(色数)

媒体的种类

1感觉媒体

2表示媒体

3显示媒体（表现媒体）：输入设备+输出设备

4交换媒体（转化媒体、转换媒体）（储存媒体+传输媒体）

数据压缩

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

常见多媒体标准：JPEG-2000（有损&无损、压缩比更高、小波变换、医学图像应用）、MPEG-1（VCD、MP3）、MPEG-2（DVD、有线/卫星电视）、MPEG-4（增强交互性）、MPEG-7（多媒体内容描述接口）、MPEG-21（标准集成）、JPEG（RGB转YUV）

第 10 章知识产权与标准化

法律法规名称

保护对象及范围

注意事项

著作权法（版权）

著作权

文学、绘画、摄影等作品

1.不需要申请，作品完成即开始保护

2.绘画或摄影作品原件出售（赠予）著作权还归原作者，原件拥有者有所有权、展览权

软件著作权法

计算机软件保护条例

软件著作权

软件作品

1.不需要申请，作品完成即开始保护

2.登记制度便于举证

专利法

专利权

需要申请，专利权有效期从申请日开始计算

商标法

商标权

需要申请，核准之日起商标受保护

反不正当竞争法

商业秘密权

1.商业秘密包括技术与经营两个方面

2.必须有保密措施才能认定商业秘密

第 11 章数据流图

三个要素：实体、加工、存储

数据流图平衡原则：父图与子图之间的平衡、子图内平衡

第 12 章数据库设计

数据库设计阶段：需求分析、概念结构设计、逻辑结构设计、物理设计

第 13 章 UML建模

用例图关系：包含关系、扩展关系、泛化关系（类似于继承关系）

类图与对象图

1：一个集合中的1个对象对应另一个集合中1个对象；

0..*：表示一个集合中的1个对象对应另一个集合中的0个或多个对象（可以不对应）；

1..*: 表示一个集合中的1个对象对应另一个集合中的1个或多个对象（至少对应一个）；

*：表示一个集合中的1个对象对应另一个集合中的多个对象。

第 14 章数据结构与算法应用

主要考察方法：

1.分治法：

特征：把一个问题拆分成多个小规模的相同子问题，一般可用递归解决。

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

2.回溯法

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

经典问题：N皇后问题、迷宫、背包问题

3.贪心法（用于求最满意解）

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

经典问题：背包问题（如装箱）、多机调度、找零问题

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

特征：划分子问题，并把子问题结果使用数组存储，利用查询子问题结果构造最终问题

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

时间复杂度总结

O(1)