一、计算机组成原理

1.1 数据的表示

按权展开法：

十进制：1227 = 1*10^3 + 2*10^2 + 2*10^1 + 7*10^0
二进制：10100.01 = 1*2^4 + 1*2^2 + 1*2^-2
七进制：604.01 = 6*7^2 + 4*7^0 + 1*7^-2

十进制转二进制：（短除法）

二进制转八进制、十六进制

10 001 110(二) -> 2 1 6(八)  每3位二进制数对应1位8(2^3)进制数
1000 1110(二) -> 8E(十六)    每4位二进制数对应1位16(2^4)进制数

原码、反码、补码、移码

正数：原码、反码、补码一致，移码：补码符号位取反

负数：原码；反码：原码中除了符号位(二进制表示的第一位数字)，其余全部取反；补码：反码+1，移码：补码符号位取反

负数的原码和补码互转都是取反+1

	1	-1	1-1
原码	0000 0001	1000 0001	1000 0010
反码	0000 0001	1111 1110	1111 1111
补码	0000 0001	1111 1111	0000 0000
移码	1000 0001	0111 1111	1000 0000

1.2 数值表示范围

码制	定点整数	定点小数
原码	-（2 ^ (n-1) - 1）~ +（2 ^ (n-1) - 1）	-（1 - 2 ^ - (n-1) ）~ +（1 - 2 ^ - (n-1) ）
反码	-（2 ^ (n-1) - 1） ~ + （2 ^ (n-1) - 1）	-（1 - 2 ^ - (n-1) ）~ +（1 - 2 ^ - (n-1) ）
补码	- 2 ^ (n-1) ~ + （2 ^ (n-1) -1）	-1 ~ +（1 - 2 ^ - (n-1) ）
移码	- 2 ^ (n-1) ~ + （2 ^ (n-1) -1）	-1 ~ +（1 - 2 ^ - (n-1) ）

四位：_ _ _ _ 原码：1111~0111 -2^3-1~2^3-1

补码和移码多了个-0（1000 0000）

人为规定：

• 整数：1000 0000 = -128
• 小数：1000 0000 = -1

1.3 浮点数的运算

浮点数表示：

• N = 尾数 * 基数 ^ 指数(阶码)

运算过程：

• 对阶 > 尾数计算 > 结果格式化

特点：

• 一般尾数用补码，也可以用原码；阶码用移码
• 尾数的阶码决定数的表示范围，位数越多范围越大
• 尾数的位数决定数的有效精度，位数越多精度越高，范围在[0.5,1]（规格化）
• 对阶时，小数向大数看齐
• 对阶是通过较小数的尾数算术右移实现的

存储：

3.14*10^3 -->  0 111 3.14

3.14*10^3 + 1.2*10^5  对阶后  0.0314*10^5 + 1.2*10^5

1.4 计算器结构（重点）

CPU是计算机的控制中心，主要由运算器、控制器、寄存器组和内部总线等部件组成。

运算器

• 算术逻辑单元ALU：数据的算术运算和逻辑运算
• 累加寄存器AC：通用寄存器，为ALU提供一个工作区，用在暂存数据
• 数据缓冲寄存器DR：写内存时，暂存指令或数据
• 状态条件寄存器PSW：存状态标志与控制标志==（争议：也有将其归为控制器的）==

控制器：不仅要保证指令的正确执行，还要能够处理异常事件

• 程序计数器PC：存储下一条要执行指令的地址
• 指令寄存器IR：存储即将执行的指令，位数取决于指令字长，存储（操作码+地址码）
• 指令译码器ID：对指令中的操作码字段进行分析解释
• 时序部件：提供时序控制信号
• 地址寄存器DR

程序员可以操控程序计数器，指令寄存器对用户完全透明

程序指令顺序执行，程序计数器PC自动+1

计算机中主机与外设间进行数据传输的输入输出控制方法有程序控制方式，中断方式，DMA等。

• DMA：可使主存间的数据块传送无需CPU干预，CPU在一个总线周期结束时响应DMA请求的；在主存与外设建立数据连接。
• 程序控制方式：由CPU执行程序控制数据的输入输出过程
• 中断：外设准备好输入数据或接收数据时向CPU发出中断请求信号，若CPU决定响应该请求，则暂停正在执行的任务，转而执行中断服务程序进行数据的输入输出处理，之后再回去执行原来被中断的任务。中断嵌套 => 堆栈

1.5 计算机体系结构分类-Flynn

体系结构类型	结构	关键特征	代表
单指令流单数据流（SISD）	控制部分：一个 处理器：一个 主存储块：一个		单处理器系统
单指令流多数据流（SIMD）	控制部分：一个 处理器：多个 主存储块：多个	各处理以异步的形式执行同一条指令	并行处理器 阵列处理机 超级向量处理机
多指令流单数据流（MISD）	控制部分：多个 处理器：一个 主存储块：多个	被证明不可能，至少是不实际	目前没有，有文献称 流水线计算机为此类
多指令流多数据流（MIMD）	控制部分：多个 处理器：多个 主存储块：多个	能够实现作业、任务、指令等各级全面并行	多处理机系统，多计算机

1.6 指令的基本概念

一条指令就是机器语言的一个语句，它是一组有意义的二进制代码，指令的基本格式如下：

操作码部分指出了计算机要执行什么性质的操作，如加法、减法、取数、存数等。地址码字段需要包含各操作数的地址及操作结果的存放地址等，从其地址结构的角度可以分为三地址指令、二地址指令、一地址指令和零地址指令。

三地址：a+b=c OP=+ A1=a,A2=b,A3=c

二地址：a+b=c OP=+ A1=a,A2=b,A1存c

一地址：a++ OP=++ A1=a

零地址：存取

1.7 寻址方式

采用不同的寻址方式的目的是扩大寻址空间并提高编程灵活性

• 立即寻址方法

特点：操作数直接在指令中，速度快，灵活性

• 直接寻址方式

特点：指令中存放的是操作数的地址，操作数存放在内存单元中

• 间接寻址方式

特点：指令中存放了一个地址，这个地址对应的内容是操作数的地址

• 寄存器寻址方式

特点：寄存器存放操作数

• 寄存器间接寻址方式

特点：寄存器内存放的是操作数的地址

• 相对寻址

指令地址码给出的是一个偏移量（可正可负），操作数地址等于本条指令的地址加上该偏移量。

• 变址寻址

操作数地址等于变址寄存器的内容加偏移量。

1.8 CISC（复杂指令计算机）与RISC（精简指令计算机）(常见)

• CISC：复杂、指令数量多、频率差别大、多寻址
• RISC：精简、指令数量少、操作寄存器、单周期、少寻址、多通用、流水线，更适合采用硬布线逻辑执行

1.9 流水线

常考：计算题

①流水线周期=执行时间最长的一段
②流水线执行时间=1条指令执行时间+(指令条数-1)*流水线周期
③流水线吞吐率=指令条数/流水线执行时间
④流水线最大吞吐率=1/流水线周期

①（3+2+4）*10 = 90
② max(3t,2t,4t) = 4
③（3+2+4）+ （10-1）*4 = 45

1.10 层次化存储结构

• 常用的虚拟存储器由主存-辅存完成

• 输入输出操作通过访存指令来完成

1.11 Chche

• 由硬件完成与Cache相关的操作
• 相联存储器按内容访问，不按寻址方式划分

1.12 串联系统和并联系统计算

串联系统和并联系统的计算即计算系统的可靠性R

串并联组合：

1.13 校验码

考点：主要判断是否可以检错，纠错和海明校验码的公式计算

奇偶校验

• 奇偶校验码的编码方法是：由若干位有效信息（如一个字节），再加上一个二进制位（校验位）组成校验码。
• 奇校验：整个校验码（有效信息位和校验位）中“1”的个数为奇数。
• 偶校验：整个校验码（有效信息位和校验位）中“1”的个数为偶数。
• 奇偶校验，可检查1位的错误，不可纠错。

循环冗余校验CRC

• CRC校验，可检错，不可纠错。
• CRC的编码方法是：==在k位信息码之后拼接r位校验码。==应用CRC码的关键是如何从k位信息位简便地得到r位校验位（编码），以及如何从k+r位信息码判断是否出错。
• 循环余校验码编码规律如下：模2除法

海明校验码

• 海明校验，可检错，也可纠错。
• 海明校验码的原理是：在有效信息位中加入几个校验位形成海明码，使码距比较均匀地拉大，并把海明码的每个二进制位分配到几个奇偶校验组中。当某一位出错后，就会引起有关的几个校验位的值发生变化，这不但可以发现错误，还能指出错误的位置，为自动纠错提供了依据
• 2^r >= m+r+1 (m为数据位，r为插入r个校验位)

1.14 计算例题

①主存-编址与计算

43FFH - 4000H + 1 = 4400H - 4000H = 400H = 0000 0100 0000 0000B
(2^10 * 16) / 2^2 = 2^12

②若内存容量为4GB，字长为32，则地址总线和数据总线的宽度都为多少？

字长为32位 => 数据总线的宽度为32位
可寻址地址=4*1024*1024*1024 B=2^32 B => 地址总线宽度为32位

③已知内存容量nKB，用16K*4bit的存储器芯片构成该内存，共需多少片？（8bit=1B）

n/16（4/8）

二、操作系统

2.1 进程管理

2.1.1 进程的概念（了解）

• 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。它由程序块、进程控制块（PCB）和数据块三部分组成。
• 进程与程序的区别：
  • 进程是程序的一次执行过程，没有程序就没有进程。
  • 程序是完成某个特定功能的一系列程序语句的集合，只要不被破坏，它就永远存在。程序是一个静态的概念，而进程是一个动态的概念，它由创建而产生，完成任务后因撤销而消亡；进程是系统进行资源分配和调度的独立单位，而程序不是。

2.1.2 进程的状态——三态模型

2.1.3 进程的同步与互斥（重点）

• 初值
  • 同步信号量的初值一般设为0；互斥信号量的初值一般设为1
• 用途
  • 同步信号量的用途：防止被抢占 初始为空
    • 低优先级的任务持有信号量，高优先级的任务需要这个信号量，只有当低优先级的任务give（释放）信号量，高优先级的任务才能take（获取）信号量。通过这种机制低优先级的任务就可以防止被高优先级的任务抢占。give和take是分别在两个任务里做的。
  • 互斥信号量的用途：对临界区上锁 初始为满
    • 当一个任务想对临界区访问时，为了防止别的任务也对该临界区操作，它需要对该临界区上锁，即take（获取）一个互斥的信号量，以保证独享。当该任务take（获取）一个互斥的信号量以后，它仍然能被高优先级的任务抢占，但高优先级的用户仍然无法访问它已经上锁的临界区。而解锁也是由上锁的任务来做的。take和give是在一个任务里完成的。
• 值的含义
  • 同步信号量，值为资源可以使用的个数，信号量小于0，则线程进行等待，信号量大于0，表示可用资源个数。初始值为0
  • 互斥信号量只有两个值0或1，0表示资源正在被占用，线程等待。1表示，资源没有被使用，线程可以进入。初始值为1

2.1.4 PV操作

生产者消费者问题：

前驱图（重点）：

2.1.5 死锁问题

• 进程管理是操作系统的核心，但如果设计不当，就会出现死锁的问题。如果一个进程在等待一件不可能发生的事，则进程就死锁了。而如果一个或多个进程产生死锁，就会造成系统死锁。

例：系统有5个进程：A、B、C、D、E。这5个进程都需要4个系统资源。如果系统至少有多少个资源，则不可能发生死锁。

答：(4-1)*5+1=16个
解析：所需资源数-1平均分配给每一个进程所需要的资源数+1则可避免死锁问题

• 死锁的预防–>打破四大条件
  • 互斥
  • 保持和等待
  • 不剥夺
  • 环路等待
• 死锁的避免
  • 有序资源分配法
  • 银行家算法

2.1.6 资源分配图（重点）

先分配R中的资源看是否还有剩余，再看P是否向R中索取资源，如果R无资源，P也向R获取资源则P就是阻塞的，如果R有资源且足够分配，则不阻塞

2.1.7 银行家算法（重点）

分配资源原则：

• 当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程。
• 进程可以分期请求资源，但请求的总数不能超过最大需求量。
• 当系统现有的资源不能满足进程尚需资源数时，对进程的请求可以推迟分配，但总能使进程在有限的时间里得到资源。

银行家算法例子：

假设系统中有三类互斥资源R1、R2、R3，可用资源分别是9、8、5。在T0时刻系统中有P1、P2、P3、P4和P5五个进程，这些进程对资源的最大需求量和已分配资源数如下所示，如果进程按序列（）执行，那么系统状态是安全的。

A.P1->P2->P4->P5->P3
B.P2->P4->P5->P1->P3
C.P2->P1->P4->P5->P3
D.P4->P2->P4->P1->P3

思路：首先计算还剩下多少个资源（可用资源-已分配资源），分别计算各个进程各个资源还需有多少个(最大需求量-已分配资源)。优先分配可以分配完的进程。

R3所剩下的资源数量为0，只有进程P2的R3资源已经足够，所以先分配资源给P2；循环计算最终得出结果。

2.2 存储管理

2.2.1 页式存储组织

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

常见：计算逻辑地址、物理地址

• 逻辑地址 = 页号 + 页内地址
• 物理地址 = 页帧号（物理块号）+ 页内地址
• 十六进制第一位为页号(物理块号）、页帧号

例如，页内存储系统中，每个页的大小为4KB。

• 逻辑地址：10 1100 1101 1110(B)—> 2CDE(B)
  • 页号为2(H)
• 对应的物理地址为： 110 1100 1101 1110(B)—> 6CDE(H)
  • 页帧号为6(H)

逻辑地址变为物理地址 —> 将页号变为物理块号（页帧号）

页面淘汰算法（重点）

页面淘汰，先看是否在内存中，不在内存中不需要淘汰，再看有没有被访问，优先淘汰没有被访问的，最后看有没有被修改，优先淘汰未修改的。

2.2.2 段页式存储组织

求页、段、每个段最大允许有多少的页均为2的n次方，n为范围 大-小+1 （所占位数）

页面置换算法（了解）：

• 最优（Optimal，OPT）算法
• 随机（RAND）算法
• 先进先出（FIFO）算法：有可能产生“抖动”。例如，432143543215序列，用3个页面，比4个缺页要少
• 最近最少使用（LRU）算法：不会“抖动”，LRU的理论依据是“局部性原理”。
• 时间局部性：刚被访问的内容，立即又被访问。
• 空间局部性：刚被访问的内容，临近的空间很快被访问。

2.2.3 磁盘管理（少见）

存取时间=寻道时间+等待时间，寻道时间是指磁头移动到磁道所需的时间；等待时间为等待读写的扇区转到磁头下方所用的时间。

硬盘容量计算：

非格式化容量=面数*（磁道数/面）*内圆周长*最大位密度
格式化容量=面数*（磁道数/面）*（扇区数/道）*（字节数/扇区）
磁道数=(外半径-内半径)*磁道密度 (注意单位要统一)

2.2.4 磁盘调度算法

• 磁盘调度管理中，先进行移臂调度寻找磁道，再进行旋转调度寻找扇区。

• 最短移臂调度算法、扫描算法（SCAN）、电梯，寻找距离当前最近的柱面号。

• 循环扫描算法（CSCAN），寻找大于当前的距离当前最近的柱面号，直到最大，又从最小的的开始。

读取磁盘数据时间计算：

读取磁盘数据的时间应包括以下三个部分：

• 找磁道的时间。
• 找块（扇区）的时间，即旋转延迟时间。
• 传输时间。

某磁盘磁头从一个磁道移至另一个磁道需要10ms。文件在磁盘上非连续存放，逻辑上相邻数据块的平均移动距离为10个磁道，每块的旋转延迟时间及传输时间分别为100ms和2ms，则读取一个100块的文件需要_ms时间。
A.10200
B.11000
C.11200
D.20200

答案：（（10*10）+100+2）*100

磁道转移读取：（磁道转移时间*磁道移动距离+延迟时间+传输时间）*文件块数

单缓冲区读取：

• （每个盘读入缓冲区的时间+缓冲区送到用户区的时间）*多少个磁盘块+每个磁盘块处理时间

双缓冲区读取：

• （每个盘读入缓冲区的时间*多少个磁盘块）+缓冲区送到用户区的时间+每个磁盘处理时间

旋转调度算法：

单缓冲区：先读取和处理第一个，转一圈回来处理第二个，有R0则跳过，第二个之后的处理和第二个一样。优化后，n个*(读取+处理)

2.3 作业管理

作业调度算法

• 时间片轮转法：用户n，时间片为q，响应时间为n*q

2.4 文件管理

2.4.1 索引文件结构

磁盘块大小为1KB，每个块号需占3B => 一个磁盘块可存放1024/3=341个块号

一级索引341*1024（磁盘块大小）/1024（单位）=341KB

二级索引341*341*1024（磁盘块大小）/1024（单位）=116281KB

每一级存储256个块号=磁盘大小/每个块需占内存，存储从0开始

0~4 5~256+5-1

访问文件F中第11264字节处的数据时，需要一级间接索引（11264/1024-1）

2.4.2 树形目录结构

• 相对路径:当前工作目录下的路径名

• 绝对路径:除了当前文件

• 全路径:绝对路径+当前文件（注意有盘符要包括盘符）

2.4.5 空闲存储空间的管理

• 物理块所在位置=（物理块号+1）/位数-1

• 位示图大小=磁盘容量/物理块/位数（单位MB/bit）

2.5 设备管理

数据传输控制方式:

• 程序控制（查询）方式：分为无条件传送和程序查询方式两种。方法简单，硬件开销小，但VO能力不高，严重影响CPU的利用率。
• 程序中断方式：与程序控制方式相比，中断方式因为CPU无需等待而提高了传输请求的响应速度。
• DMA方式：DMA方式是为了在主存与外设之间实现高速、批量数据交换而设置的。DMA方式比程序控制方式与中断方式都高效。
• 通道方式
• VO处理机

常见概念：

• DMA为主要考察点，与CPU没有任何关系

• 采用中断和DMA方式控制技术时，CPU与外设可并行工作

• windows在打开文件时，系统会自动通过建立的文件关联来决定使用什么程序打开

• 修改系统目录文件对系统的影响较大

三、数据库系统

3.1 三级模式-两层映射

3.2 数据库设计过程

3.3 E-R模型（重点）

1:1联系

1:n联系

m:n联系

联系转关系模式：

• 1：1联系：可将联系合并至任意一端的实体关系模式中。
• 1：n联系：可将联系合并至n端实体关系模式中。
• m:n联系：联系必须单独转成关系模式。

3.4 关系代数

3.5 规范化理论

3.5.1 求候选键

图示法求候选键

1、将函数依赖关系，用“有向图”的方式表示。

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

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

例：给定关系R（A1，A2，A3，A4）上的函数依赖集F={A1→A2，A3→A2，A2→A3，A2→A4}，R的候选关键字为（A）。
A.A1
B.A1A3
C.A1A3A4
D.A1A2A3

3.5.2 范式

主属性与非主属性定义：组成候选码的属性就是主属性，其它的就是非主属性

函数依赖：

• 第一范式：属性不可切割
• 第二范式：不能存在部分函数依赖
• 第三范式：不能存在传递函数依赖
  

3.5.3 模式分解

保持函数依赖分解

设数据库模式p={R1，R2，.…，Rk}是关系模式R的一个分解，F是R上的函数依赖集，p中每个模式Ri上的FD集是Fi。如果{1，F2，…，Fk）与F是等价的（即相互逻辑蕴涵），那么称分解p保持FD。

无损分解

什么是有损，什么又是无损？

有损：不能还原。无损：可以还原。

无损联接分解：指将一个关系模式分解成若干个关系模式后，通过自然联接和投影等运算仍能还原到原来的关系模式

思考题：
有关系模式：成绩（学号，姓名，课程号，课程名，分数）函数依赖：学号–>姓名，课程号–>课程名，（学号，课程号）–>分数
若将其分解为：

• 成绩（学号，课程号，分数）
• 学生（学号，姓名）
• 课程（课程号，课程名）

请思考该分解是否为无损分解？

由于有：学号→姓名，所以：
成绩（学号，课程号，分数，姓名）
由于有：课程号课程名，所以：
成绩（学号，课程号，分数，姓名，课程名）
综上，所以为无损分解

3.6 SQL语句

建表语句

删除语句

drop table <表名>;

修改语句

alter table <表名>
[add <新列名> <数据类型> [列级完整性约束]]
[drop <列名/完整性约束>]
[modify/change <列名> <数据类型>];

查询语句

select [all|distinct] <目标表达式> [,<目标表达式>...]
from <表名> [,<表名>]...
[where <条件表达式>]
[group by <列名1> [having <条件表达式>]]
[order by <列名2> [asc|desc]...];

处理类型	处理子类	实例/语法
结果排序	升序或降序	order by 字段名 desc|asc
集函数	统计	count([distinct|all] <列名>)
	计算一类中值的总和	sum([distinct|all] <列名>)
	计算一列值的平均值	avg([distinct|all] <列名>)
	求一列值中的最大值	max([distinct|all] <列名>)
	求一列值中的最小值	min([distinct|all] <列名>)
对结果分组	将查询结果按列值分组	group by <列名>
对分组结果筛选	对分组结果筛选	having <条件表达式>

3.7 并发控制

ACID：

• 原子性：事务是原子的，要么做，要么都不做。
• 一致性：事务执行的结果必须保证数据库从一个一致性状态变到另一个一致性状态。
• 隔离性：事务相互隔离。当多个事务并发执行时，任一事务的更新操作直到其成功提交的整个过程，对其他事务都是不可见的。
• 持久性：一旦事务成功提交，即使数据库崩溃，其对数据库的更新操作也永久有效。

锁：

• x锁（排它锁）（写锁）：对数据进行写操作时进行锁定。如果事务T对数据A加上X锁后，就只允许事务T读取和修改数据A，其他事务对数据A不能再加任何锁，从而也不能读取和修改数据A，直到事务T释放A上的锁。

• s锁（共享锁）（读锁）：对数据进行读操作时进行锁定。如果事务T对数据A加上了S锁后，事务T就只能读数据A但不可以修改，其他事务可以再对数据A加S锁来读取，只要数据A上有S锁，任何事务都只能再对其加S锁（读取）而不能加X锁（修改）。

3.8 分布式数据库

• 分片透明：指用户或应用程序不需要知道逻辑上访问的表具体是怎么分块存储的。
• 复制透明：指采用复制技术的分布方法，用户不需要知道数据是复制到哪些节点，如何复制的。
• 位置透明：指用户无需知道数据存放的物理位置。
• 逻辑透明：即局部数据模型透明，是指用户或应用程序无需知道局部场地使用的是那种数据模型。

四、计算机网络

4.1 OSI、RM七层模型

一些概念：

• 集线器连接的主机构成一个冲突域，交换机的每个端口属于一个冲突域，路由器连接几部分网络就有几个广播域。集线器没有自动寻址的作用。

• PPP中的安全认证协议是CHAP，三次握手传送密文

• 属于应用层协议的是简单网络管理协议SNMP,它的传输层协议是UDP

• 默认路由，当主机无选择时所选择的路由，即最后选择的路由

4.2 TCP、IP协议族

端口：

• POP3：110端口，邮件收取
• SMTP：25端口，邮件发送
• FTP：20数据端口/21控制端口，文件传输协议
• HTTP：80端口，超文本传输协议，网页传输
• DHCP：67端口，IP地址自动分配
• SNMP：161端口，简单网络管理协议
• DNS：53端口，域名解析协议，记录域名与IP的映射关系
• TCP：可靠的传输层协议
• UDP：不可靠的传输层协议
• ICMP：因特网控制协议，PING命令来自该协议
• IGMP：组播协议
• ARP：地址解析协议，IP地址转换为MAC地址
• RARP：反向地址解析协议，MAC地址转IP地址
• HTTPS：443

一些概念：

• ICMP：数据单元封装在IP数据报

• DNS域名查询的次序是：本地hosts文件 -> 本地DNS缓存 -> 本地DNS服务器 -> 根域名服务器

• 主机域名查询次序是：本地缓存 -> 转发域名服务器

• DHCP客户端可从DHCP服务器获得DNS服务器的地址和DHCP服务器的地址

• protocol://hostname[:port]/path/filename

  • protocol：协议类型，GET读取一个页面，默认使用http协议
  • hostname：主机名（www） 域名（xxx.com）
  • port：端口号
  • path：路径
  • filename：文件名

• TCP和UDP均提供了端口寻址功能；VoIP允许数据丢失，使用UDP协议

• 默认网关和本地IP地址应属于同一网段；主机路由的子网掩码是255.255.255.255

• netstat用于显示IP、TCP、UDP和ICMP协议相关数据

• nslookup、ping、tracert用来诊断DNS

4.3 IP地址

• 隧道技术：现有的IPv4向IPv6过渡

• 翻译技术：纯IPv6与纯IPv4通信

• IPV6的地址空间是IPV4的2^96倍
  
  匹配路由表

例题： 与地址220.112.179.92匹配的路由表的表项是（）。

A 220.112.145.32/22
B 220.112.145.64/22
C 220.112.147.64/22
D 220.112.177.64/22

地址220.112.179.92转换成二进制是：1101 1100 0111 0000 1011 0011 0101 1100

根据选项，要求是22位网络号，也就是说1101 1100 0111 0000 1011 0011 0101 1100加粗部分的22位网络号是固定不变的，剩下的10位是主机号。

也就是说斜线记法的地址是在1101 1100 0111 0000 1011 0000 0000 0000（220.112.176.0/22）~ 1101 1100 0111 0000 1011 0011 1111 1111（220.112.179.255/22）范围内（不包含全0或全1的情况），就D符合条件。

以220.112.177.64/22为例，先转换成二进制1101 1100 0111 0000 1011 0001 0100 0000
CIDR地址块的范围是1101 1100 0111 0000 1011 0000 0000 0000（220.112.176.0/22）~ 1101 1100 0111 0000 1011 0011 1111 1111（220.112.179.255/22），同样220.112.179.92也在范围内。

4.4 子网划分

1. 子网掩码
2. 将一个网络划分成多个子网（取部分主机号当子网号）
3. 将多个网络合并成一个大的网络（取部分网络号当主机号）

例1，将B类IP地址168.195.0.0划分成27个子网，子网掩码为多少？

4.5 网络接入技术

• TD-SCDMA是中国自主研发的

五、网络安全

5.1 对称（共享）加密技术

特点：

• 加密强度不高，但效率高
• 密钥分发困难
• 使用同一套秘钥

常见对称密钥加密算法:

• DES/3DES（三重DES）
• RC-5、IDEA算法
• RC5适合对大量的明文消息进行加密传输

5.2 非对称（公开）秘钥加密技术

特点：

• 加密速度慢，但强度高

常见非对称密钥加密算法：

• RSA
• ECC
• DSA

5.3 数字签名

• RSA算法

• 数字签名用户通信的A、B双方，使得A向B发送签名的消息P，提供以下服务：

  • B可以验证消息P确实是来源于A
  • A不能否认发送过消息P
  • B不能编造或修改消息P

5.4 信息摘要

常用的消息摘要算法有MD5，SHA等，市场上广泛使用的MD5，SHA算法的散列值分别为128和160位，由于SHA通常采用的密钥长度较长，因此安全性高于MD5。

5.5 PKI公钥体系

• PKI体制中，保证数字证书不被篡改的方法使用CA的私钥对数字证书签名，访伪造，不可抵赖

• 从CA中心获取用户的数字证书，用CA的私钥做数字签名

• 数字证书做身份认证

5.6 Dos（拒绝服务）与DDos

拒绝服务攻击即攻击者想办法让目标机器停止提供服务，是黑客常用的攻击手段之一。

• 迫使服务器的缓冲区满，不接收新的请求
• 使用IP欺骗，迫使服务器把合法用户的连接复位，影响合法用户的连接。

SYN Flooding攻击属于DoS攻击。

5.7 防火墙

• 应用级网关防火墙是内部网和外部网的隔离点，可对应用层的通信数据流进行监控和过滤。

• 包过滤防火墙对数据包的过滤依据包括源IP地址、源端口号、目标IP地址、目标端口号，包过滤技术对应用和用户是透明的。

• 受保护程序从高到低：内网、DMZ、外网

• 防火墙不具备查毒功能

5.8 计算机木马与病毒

病毒：编制或者在计算机程序中插入的破坏计算机功能或者破坏数据，影响计算机使用并且能够自我复制的一组计算机指令或者程序代码。

木马：是指通过特定的程序来控制另一台机器。木马程序的客户端运行在攻击者的机器上。

• 系统病毒（前缀：Win32、PE、W32，如：KCOM-Win32.KCOM）
• 蠕虫病毒（如：红色代码、爱虫病毒、熊猫烧香、Nimda病毒、艾丽兹病毒、震网病毒）
• 木马病毒、黑客病毒（如：QQ消息尾巴木马—Trojan.QQ3344）
• 脚本病毒（如：红色代码——Script.Redlof）
• 宏病毒（如：美丽莎—Macro.Melissa）：一般感染以DOC、Excel为扩展名的文件
• 后门病毒（如：灰鸽子—Backdoor.Win32.Huigezi）
• 病毒种植程序病毒（冰河播种者—Dropper.BingHe2.2C）
• 破坏性程序病毒（杀手命令—Harm.Command.Killer）
• 玩笑病毒（如：女鬼—Jioke.Grl ghost）
• 捆绑机病毒（如：捆绑QQ—Binder.QQPass.QQBin）

其他概念：

• 与电子邮箱服务无关的是MIME
• 报文摘要算法用来保证数据完整性
• kerberos系统采用的是时间戳方案来防止重放攻击
• 漏洞扫描技术是检测远程或本地系统安全脆弱性的一种安全技术。通过目标主机TCP/IP端口建立连接并请求某些服务（FTP等）。漏洞扫描不可以发现网络入侵者
• ARP攻击（ARP欺骗）是欺骗攻击的一种，通过伪造IP地址和MAC地址，能够在网络中产生大量的ARP通信量使网络阻塞

六、系统开发基础

6.1 软件开发模型

• 瀑布模型：将软件生存周期各个活动规定为依线性顺序连接的若干阶段的模型，适合于软件需求很明确的软件项目。（重视需求）
• V模型：是瀑布模型的一种演变模型，将测试和分析与设计关联进行，加强分析与设计的验证。（重视测试）
• 原型模型：是一种演化模型，通过快速构建可运行的原型系统，然后根据运行过程中获取的用户反馈进行改进。
• 增量模型：是一种非整体开发的模型，该模型具有较大的灵活性，可以快速构建核心产品，适合于软件需求不明确的一种模型。
• 演化模型：适用于对软件需求缺乏准确认识的情况。
• 螺旋模型：将瀑布模型和演化模型结合起来，加入了两种模型均忽略的风险分析。
• 喷泉模型：典型的面向对象生命周期模型，是一种以用户需求为动力，以对象作为驱动的模型。
• 统一过程模型（RUP）：是一种“用例和风险驱动，以架构为中心，迭代并且增量”的开发过程，定义了不同阶段及其制品。

  • 起始阶段：专注于项目的初创活动。声明周期目标。

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

  • 构建阶段：关注系统的构建，产生实现模型。初始运作功能。

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

  • 产生阶段：运行软件并监控软件的持续使用，提供运行环境的支持，并提交评估缺陷报告和变更请求。

    • 角色 -> 谁做
    • 活动 -> 怎么做
    • 制品 -> 做什么
    • 工作 -> 什么时候做

6.2 软件开发方法

• 需求不清晰且规模不太大时采用原型化方法最为合适，而数据处理领域的不太复杂的软件，适用于结构化方法进行开发。

• 结构化开发方法有结构化分析、结构化设计、和结构化程序设计过程，是一种面向数据流的开发方法。指导思想：自顶向下、逐步分解、抽象到具体。

  • 体系结构设计：定义软件的主要结构元素及其关系
  • 数据设计：基于实体联系图确定软件涉及的文件系统的结构及数据库的表结构
  • 接口设计：描述用户界面，软件和其他硬件设备，软件与外部环境之间的交互关系
  • 过程设计：算法及内部数据结构

• 结构化分析模型包括数据流图、实体联系图、状态迁移图、加工逻辑和数据字典。

• 结构图的基本成分不包括数据

• 面向对象方法

  • 更好的复用性
  • 关键在于建立一个全面、合理、统一的模型
  • 分析、设计、实现三个阶段、界限不明确

6.3 需求分析

• 需求分析：确定软件要完成的功能及非功能性要求
• 概要设计：确定模块之间的调用关系，进行软件体系结构的设计、数据设计和接口设计。系统分解为若干个子系统。
• 结构化设计：根据系统的数据流图进行设计，模块体现为函数、过程及子程序。
• 面向对象设计：基于面向对象的基本概念进行，模块体现为类、对象和构建等。
• 详细设计：将模块进行细化，得到详细的数据结构与算法
• 编码：根据详细设计进行代码的编写，得到可以运行的软件，并进行单元测试。

6.4 软件设计

模块化设计：

• 追求高内聚、低耦合、保持模块的相对独立性
• 模块的规模适中
• 模块的扇入和扇出要合理
• 深度和宽度适当

内聚类型：内聚性、模块独立性由低到高

• 巧合（偶然）内聚：指一个模块内的各处理元素之间没有任何联系。（内聚性最低）
• 逻辑内聚：指模块内执行若干个相似的功能，通过参数确定该模块完成哪一个功能。
• 时间（瞬时）内聚：把需要同时执行的动作组合在一起形成的模块。
• 过程内聚：指一个模块完成多个任务，这些任务必须按指定的过程执行。
• 通信内聚：指模块内的所有处理元素都在同一个数据结构上操作，或者各处理使用相同的输入数据或产生相同的输出数据。
• 顺序内聚：指一个模块中的各个处理元素都密切相关于同一个功能且必须顺序执行，前一个功能的输出就是下一个功能的输入。
• 功能内聚：完成一个单一功能，各部分协同工作，缺一不可。（内聚性最高）

耦合类型：耦合性由低到高，模块独立性由高到底；耦合程度不取决于，模块提供的功能数。

• 直接耦合：两个模块之间没有直接关系，它们之间的联系完全是通过主模块的控制和调用来实现的。
• 数据耦合：一个模块访问另一个模块时，彼此之间是通过简单数据参数（不是控制参数、公共数据结构或外部变量）来交换输入、输出信息。
• 标记耦合：一组模块通过参数表传递记录信息，就是标记耦合。（某一数据结构的子结构）
• 控制耦合：如果一个模块通过传送开关、标示、名字等控制信息，明显地控制选择另一模块的功能，就是控制耦合。
• 外部耦合：一组模块都访问同一全局简单变量而不是同一全局数据结构，而且不是通过参数传递该全局变量的信息。
• 公共耦合：一组模块都访问同一个公共数据环境。
• 内容耦合：一个模块直接访问另一个模块的内部数据；一个模块不通过正常入口转到另一个模块；两个模块有一部分程序代码重叠（只出现在汇编语言中）；一个模块有多个入口。

在设计过程中，发现模块作用范围不在其控制范围之内，可以用“上移判点”或“下移受判断影响的模块，将它下移到判断所在模块的控制范围内”的方法加以改进

6.5 软件测试

软件测试按阶段划分为单元测试、集成测试和系统测试。

• 回归测试：在软件发送变更之后进行的测试，以发现在变更时可能引起的其他错误。
• 验收测试：有效性测试、软件配置审查、验收测试
• 系统测试：恢复测试、安全性测试、强度测试、性能测试、可靠性测试和安装测试，测试目标来自需求分析
• 集成测试：模块间的接口和通信

  • 自顶向下

    • 从最顶层的构建开始，逐步向下。

    • 优点：较早地验证了主要控制和判断点；按深度优先可以首先实现和验证一个完整的软件功能；功能较早证实 ，带来信心；只需要一个驱动，减少驱动器开发的费用；支持故障隔离。

    • 缺点：柱的开发量大；底层验证被推迟；底层组件测试不充分。

  • 自底向上

    • 从系统层次中最底层的构建开始测试，逐步向上。

    • 优点：对底层组件行为较早验证；工作最初可以并行集成；比自顶向下效率高；减少了桩开发（不需要写桩程序）；支持故障隔离。

    • 缺点：驱动的开发工作量大；对高层的验证被推迟，设计上的错误不能被及时发现。

  • 三明治

    • 结合自底向上和自顶向下两种测试策略。

  • 一次性

    • 对所有构件一次性测试，然后集成。
• 单元测试：模块接口、局部数据结构、边界条件、独立的路径、错误处理

McCabe复杂度：

计算有向图G的环路复杂度公式为：V(G)=m-n+2

说明：其中V(G)是有向图G中的环路个数，m是G中的有向弧数，n是G中的结点数。

例：若采用白盒测试方法测试以下代码，并满足条件覆盖，则至少需要（1）个测试用例。采用McCabe度量法算出该程序的环路复杂度为（2）。

Int find_max(int i,int j,int k){
	int max; // 1
	if(i>j) // 2
		if (i>k) // 3
			max = i; // 5
		else max = k; // 6
		else if(j>k) // 4
			max = j; // 7
		else max  = k; // 8
}
return; // 9

6.6 软件维护

软件维护工具主要有：

• 版本控制工具
• 文档分析工具
• 开发信息库工具
• 逆向工程工具
• 再工程工具
• 配置管理支持工具（无配置管理工具）

软件系统的可维护性评价指标包括：

• 可理解性
• 可测试性
• 可修改性

6.7 软件工程国家标准

系统开发计划是用于系统开发人员与项目管理人员沟通的主要文档，它包括了RERT图、甘特图、预算分配表等。

概要设计文档包含系统架构、模块划分、系统接口、数据设计，不包含模块内算法设计。

REPT图和Gantt图

• Gannt图不能清晰表示依赖关系，不能清晰的确定影响进度的关键任务。
• REPT图不能清晰描述并行关系

6.8 软件过程改进-CMMI

• 过程能力成熟度模型基于这样的理念：改进过程将改进产品，尤其是软件产品
• 软件组织为提高自身的过程能力，把不够成熟的过程提升到较成熟的过程设计4个方面，这4个方面构成了软件过程改进的框架，即过程改进基础设施、过程改进线路图、软件过程评估方法和软件过程改进计划。
• 在进行评估后需要把发现的问题转化为软件过程改进计划
• 每一次改进要经历4个步骤：评估、计划、改进和监控

CMM

• 五级：优化级，通过对来自过程、新概念和新技术等方面的各种有用信息的定量分析，能够不断的、持续的对促进过程进行改进
• 四级：已管理级，软件过程和产品质量有详细的度量标准。软件过程和产品质量得到了定量的认识和控制
• 三级：已定义级，用于管理的和工程的软件过程均已文档化、标准化、并形成了整个软件组织的标准软件过程
• 二级：可重复级，已建立了基本的项目管理过程，可用于对成本、进度和功能特性进行跟踪
• 一级：初始级，过程无序，进度，预算，功能和质量等方面不可预测，实现支持过程域的特定目标（输入输出）

6.9 项目管理

质量管理：质量控制不属于软件配置管理

风险管理：不属于配置管理

• 风险识别：试图系统化地确定对项目计划（估算、进度、资源分配）的威胁。
• 风险预测（风险估算）：它从两个方面评估一个风险：风险的可能性或概率，以及如果风险发生时所产生的后果。
• 风险评估：根据风险及其发生的概率和产生的影响预测是否影响参考水平值。
• 风险控制：目的是辅助项目组建立处理风险的策略，有效的策略应考虑风险避免、风险监控、风险管理及意外事件计划。
• 风险避免：放弃或不进行可能带来损失的活动或工作。
• 风险监控：在决策主体的运行过程中，对风险的发展与变化情况进行全程监督，并根据需要进行应对策略的调整。
• 风险管理：指在一个肯定有风险的环境里把风险减至最低的管理过程。
• 风险影响：是当风险发生时造成的损失。
• 风险概率：是风险发生的可能性。
• 风险暴露：是一种量化风险影响的指标，等于风险影响乘以风险概率。

时间管理-关键路径法（重要）

• 关键路径法是在制订进度计划时使用的一种进度网络分析技术。关键路线法沿着项目进度网络路线进行正向与反向分析，从而计算出所有计划活动理论上的最早开始与完成日期、最迟开始与完成日期，不考虑任何资源限制。(最长路径)==>求最早开始时间、关键路径、完成项目最少时间。
• 总时差（松弛时间）：在不延误总工期的前提下，该活动的机动时间。活动的总时差等于该活动最迟完成时间与最早完成时间之差，或该活动最迟开始时间与最早开始时间之差。
• 松弛时间也可以用关键路径-当前路径的最长路径求得

考点：根据类似下面的图求关键路径、松弛时间

其他概念

COCOMO II：

• 在模型层次结构中有3中不同规模估算选择，即对象点、功能点、代码行。
• 基本模型：静态单变量模型
• 中级模型：涉及产品、硬件、人员项目等方面属性的影响因素来调整工作量的估算
• 详细模型：包含中级，还要考虑对软件工程过程中分析、设计等各步骤的影响

冗余附加技术：

• 在屏蔽硬件错误的容错技术中，冗余附加技术包括：

  • 关键程序和数据的冗余及调用
  • 检测、表决、切换、重构和复算的实现

• 在屏蔽软件错误的容错技术中，冗余附加技术包括：

  • 冗余备份程序的存储及调用
  • 实现错误检测和错误恢复的程序
  • 实现容错软件所需的固化程序

• 不包括关键程序和数据的冗余存储和调用

• 结构冗余：静态、动态、和混合冗余。

七、面向对象技术

7.1 面向对象的基本概念

• 对象：属性（数据）+ 方法（操作）+对象ID
• 类（实体类/控制类/边界类）
  • 实体类：主要负责数据和业务逻辑
  • 边界类（接口类）：负责和用户进行交互，即用户界面
  • 控制类：负责实体类和界面类的交互
• 继承与泛化：复用机制
• 封装：隐藏对象的属性和实现细节，仅对外公开接口
• 多态：不同对象收到同样的消息产生不同的结果
• 接口：一种特殊的类，他只有方法定义没有实现
• 重载：一个类可以有多个同名而参数类型不同的方法
• 模板类
• 消息和消息通信：消息是异步通信的

面向对象设计7大原则

• 单一职责原则：设计目的单一的类
• 开放-封闭原则：对扩展开放，对修改封闭
• 李氏（Liskov）替换原则：子类可以替换父类
• 依赖倒置原则：要依赖于抽象，而不是具体实现；针对接口编程，不要针对实现编程
• 接口隔离原则：使用多个专门的接口比使用单一的总接口要好
• 组合重用原则：要尽量使用组合，而不是继承关系达到重用目的
• 迪米特（Demeter）原则（最少知识法则）：一个对象应当对其他对象有尽可能少的了解

多态类型

• 参数多态：应用比较广的多态
• 强制多态：把操作对象的类型强行加以变换
• 包含多态：在许多语言中都存在，最常见的例子就是子类型化
• 过载多态：同一个名字在不同的上下文中所代表的含义

7.2 UML

事件触发一个没有特定监护条件的迁移，对象不一定离开当前状态

7.2.1 用例图

包含、扩展、泛化

• 包含关系：其中这个提取出来的公共用例称为抽象用例，而把原始用例称为基本用例或基础用例系：当可以从两个或两个以上的用例中提取公共行为时，应该使用包含关系来表示它们。
• 扩展关系：如果一个用例明显地混合了两种或两种以上的不同场景，即根据情况可能发生多种分支，则可以将这个用例分为一个基本用例和一个或多个扩展用例，这样使描述可能更加清晰。
• 泛化关系：当多个用例共同拥有一种类似的结构和行为的时候，可以将它们的共性抽象成为父用例，其他的用例作为泛化关系中的子用例。在用例的泛化关系中，子用例是父用例的一种特殊形式，子用例继承了父用例所有的结构、行为和关系。

7.2.2 类图（重要）

聚合和组合是关联的特殊种类

7.2.3 顺序（时序）图

7.2.4 活动图

• 业务处理流程进一步建模

• 第一条横线：并发分叉

• 第二条横线：并发汇流

• 椭圆：动作

• [NO]：监护表达式

• 菱形：分支

7.2.5 状态图

7.2.6 通信图

箭头表示消息
方框表示对象

7.2.7 构建（组件）图

7.2.8 部署图

软件组件和硬件之间的物理关系

7.3 面向对象分析

面向对象分析主要回答软件系统需要解决什么问题，在面向对象分析阶段，并不考虑系统实现以及系统的测试问题。

7.4 面向对象设计

创建性模式

设计模式名称	简要说明	速记关键字
Abstract Factory抽象工厂模式	提供一个接口，可以创建一系列相关或相互依赖的对象，而无需指定它们具体的类	生产成系列对象
Builder构建器模式	将一个复杂类的表示与其构造相分离，使得相同的构建过程能够得出不同的表示	复杂对象构造
Factory Method工厂方法模式	定义一个创建对象的接口，但由子类决定需要实例化哪一个类。工厂方法使得子类实例化的过程推迟	动态生产对象
Prototype原型模式	用原型实例指定创建对象的类型，并且通过拷贝这个原型来创建新的对象	克隆对象
Singleton单例模式	保证一个类只有一个实例，并提供一个访问它的全局访问点	单实例

结构性（对象）模式

设计模式名称	简要说明	速记关键字
Adapter适配者模式	==将一个类的接口转换成用户希望得到的另一种接口。==它使原本不相容的接口得以协同工作（类、对象结构模式）	转换接口
Bridge桥接模式	将类的抽象部分和它的实现部分分离开来，使它们可以独立地变化，与适配者模式有相似特征，涉及到从自身以外的一个接口向这个对象发送请求	继承树拆分
Composite组合模式	将对象组合成树型结构以表示==“整体-部分”==的层次结构，使得用户对单个对象和组合对象的使用具有一致性	树型目录结构
Decorator装饰模式	动态地给一个对象添加一些额外的职责。它提供了用子类扩展的一个灵活的替代，比派生一个子类更加灵活	附加职责
Facade外观模式	定义一个高层接口，为子系统中的一组接口提供一个一致的外观，从而简化了该子系统的使用，即为复杂子系统提供一个简单接口	对外统一接口
Flyweight享元模式	提供支持大量细粒度对象共享的有效方法	文章共享文字对象
proxy代理模式	==为其他对象提供一个代理（接口）==以控制这个对象的访问

行为性模式

设计模式名称	简要说明	速记关键字
Chain of Responsibility职责链模式	通过给多个对象处理请求的机会，减少请求的发送者与接受者之间的耦合。将接收对象链接起来，在链中传递请求，直到有一个对象处理这个请求	传递职责
Command命令模式	将一个请求封装为一个对象，从而可用不同的请求对客户进行参数化，将请求排队或记录请求日志，支持可撤销的操作	日志记录，可撤销
Interpreter解释器模式	给定一种语言，定义它的文法表示，并定义一个解释器，该解释器用来根据文法表示来解释语言中的句子	虚拟机的机制
Iterator迭代器模式	提供一种方法来顺序访问一个聚合对象中的各个元素，而不需要暴露该对象的内部表示	数据库数据集
Mediator中介者模式	用一个中介对象来封装一系列的对象交互。它使督对象不需要显式地相互调用，从而达到低耦合，还可以独立地改变对象间的互	不直接引用
Memento备忘录模式	在不破坏封装性的前提下，捕获一个对象的内部状态，并在该对象之外保存这个状态，从而可以在以后将该对象恢复到原先保存的状态
Observer观察普横式	定义对象间的一种一对多的依赖关系，当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并自动更新	联动
State状态横式	允许一个对象在其内部状态改变时改变它的行为	状态变成类
Strategy策略模式	定义一系列算法，把它们一个个封装起来，并且使它们之间可互相替换，从而让算法可以独立于使用它的用户而变化	多方案切换
Template Method模板方法模式	定义一个操作中的算法骨架，而将一些步吸延迟到子类中，使得子类可以不改变一个算法的结构即可置新定义算法的某些特点步骤
Visitor访问者模式	表示一个作用于某对象结构中的各元素的操作，使得在不改变各元素的类的前提下定义作用于这些元素的新操作，多态accept

观察者模式

• Subject（目标、被观察者）知道它的观察者，可以有任意多个观察者观察同一个目标；提供注册和删除观察者对象的接口，可以对应着多个Observe对象
• Observe（观察者）为那些目标发生改变时需获得通知的对象定义一个更新接口
• ConcreteSubject（具体目标）将有关状态存入各ConcreteObject对象；当它的状态发生改变时，向其各个观察者发出通知
• ConcreateObserver（具体观察者）维护一个指向ConcreteSubject对象的引用；存储有关状态，这些状态与目标对应的状态保持一致；实现Observe的更新接口，以使自身状态与目标的状态保持一致
• 一个观察者观察一个被观察者，而一个被观察者可以被多个观察者关注

八、数据结构与算法

8.1 数组

数组类型	存储地址计算
一维数组a[n]	a[i]的存储地址为：a+i*len
二维数组a[m][n]	a[i][j]的存储地址(按行存储)为：a+(i*n+j)*len a[i][j]的存储地址(按列存储)为：a+(j*m+i)*len

例：已知5行5列的二维数组a中的各元素占两个字节，求元素a[2][3]按行优先存储的存储地址？

8.2 线性表

了解顺序表、链表（单链表、双向链表、循环链表）、队列与栈的基本概念

• 队列：先进先出
• 栈：先进后出

顺序存储和链式存储对比：

• 顺序存储读改快
• 链式存储插入删除快

循环队列的判断：

• 空：tail==head
• 满：（tail+1）% max ==head

8.3 广义表

基本运算：取表头head（Ls）和取表尾tail（Ls）。

若有：LS1=（a，（b，c），（d，e））

head（LS1）=a
tail（LS1）=（（b，c），（d，e））

例1，有广义表LS1=（a，（b，c），（d，e）），则其长度为？深度为？
例2，有广义表LS1=（a，（b，c），（d，e）），要将其中的b字母取出，操作就为？

例题1答案：长度为3，深度为2。
例题2答案：head（head（tail（LS1）））。

8.4 树与二叉树

树的相关术语：

• 结点的度：一个结点含有的子树的个数称为该结点的度；
• 叶结点：度为0的结点称为叶结点，也可以叫做终端结点
• 分支结点：度不为0的结点称为分支结点，也可以叫做非终端结点
• 结点的层次：从根结点开始，根结点的层次为1，根的直接后继层次为2，以此类推
• 结点的层序编号：将树中的结点，按照从上层到下层，同层从左到右的次序排成一个线性序列，把他们编成连续的自然数。
• 树的度：树中所有结点的度的最大值
• 树的高度(深度)：树中结点的最大层次
• 路径与路径长度：两个结点ki和kj的结点序列（ki，ki1，ki2，…，kj）称为由ki到kj的一条路径
• 路径长度等于路径所通过的结点数目减1（即路径上分支数目）
• 子孙结点和祖先结点：在一棵树中，一个结点的所有子树中的结点称为该结点的子孙结点。从根结点到达一个结点的路径上经过的所有结点被称作该结点的祖先结点。
• 森林：m（m>=0）个互不相交的树的集合，将一颗非空树的根结点删去，树就变成一个森林；给森林增加一个统一的根结点，森林就变成一棵树

二叉树的基本定义

• 二叉树就是度不超过2的树(每个结点最多有两个子结点)
• 满二叉树：一个二叉树，如果每一个层的结点树都达到最大值，则这个二叉树就是满二叉树
• 完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树

二叉树的性质：

• 性质1 非空二叉树上叶结点数等于双分支结点数加1。即：n0=n2+1
• 性质2 非空二叉树上第i层上至多有==2^(i-1)==个结点（i≥1）
• 性质3 高度为h的二叉树至多有2^h-1个结点（h≥1）
• 性质4 完全二叉树性质（含n为结点）：
  
  
  
• 性质5 n个结点的完全二叉树深度为： ==㏒2(n+1)==或 ㏒2(n) +1

考点：

• 二叉树的遍历（前、中、后、层）
• 反向构造二叉树
• 查找二叉树
• 最优二叉树（哈夫曼树）

8.5 图

图的遍历

拓扑排序

最小生成树

完全连通无向图边数：m=n(n-1)/2

九、多媒体基础知识（近几年没考过）

9.1 音频相关的概念

采样

• 采样频率
• 采样精度
• 采样频率应为声音最高频率2倍

MIC输出的是音频模拟信号，声卡从MIC获取音频模拟信号后，通过模数转换器（ADC）将声波振幅信号采样转换成一串数字信号并存储到计算机中。重放时，这些数字信号送到数模转换器（DCA），以同样的采用速度还原为模拟波形，放大后送到扬声器发声，这一技术称为脉冲编码调制技术（PCM）。

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

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

CIF视频格式图像分辨率为：352*288

音乐合成技术主要有FM和Wave Table，其中Wave Table合成的音质更好，FM改变信号幅度可以改变音高

计算题公式：

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

样本精度=量化/采样位数（位）

CD上声音的采样频率为44.1kHz，样本精度为16bit，双声道立体声，那么其未经压缩的数据传输率为（C）。
A.88.2kb/s B.705.6kb/s C.1411.2kb/s D.1536.0kb/s

计算过程：44.1k*16bit*2=1411.2kb

9.2 图像相关概念

• 亮度：画面的明亮程度。

• 色调（红，绿）：颜色的种类，如红色、绿色、蓝色等不同颜色就是指色调。同时画面整体颜色倾向，也是色调。

• 饱和度：色彩的纯洁性，即颜色的艳丽程度。

• dpi：每英寸像素点

• 当显示深度小于图像深度时，不能完全反映

• 矢量图的基本单位是图元

• 位图的基本单位是像素，占用空间大，显示速度快

使用150DPI的扫描分辨率扫描一副3*4英寸的彩色照片，得到原始的24位真彩色图像的数据量是（810000）Byte。

(150*3)*(150*4)*24/8

9.4 媒体的种类

• 感觉媒体：指直接作用于人的感觉器官，使人产生直接感觉的媒体。如：声音、图形、图像、动画等。
• 表示媒体：指为了加工、处理和传输感觉媒体而人为研究、构造出来的一种媒体，常见的有各种编码方式，如文本编码、图像编码和声音编码等。
• 显示媒体（表现媒体）：表现和获取信息的物理设备。如：输入显示媒体键盘、鼠标和麦克风等；输出显示媒体显示器、打印机和音箱等。输入输出设备
• 存储媒体：存储数据的物理设备，如磁盘、光盘和内存等。
• 传输媒体：传输数据的物理载体，如电缆、光缆和交换设备等。

9.5 数据压缩基础

• 空间冗余（几何元余）
• 时间冗余
• 视觉冗余
• 信息篇冗余
• 结构冗余
• 知识冗余

9.6 有损压缩和无损压缩

一类是无损压缩编码法（Lossless compression coding），也称冗余压缩法或熵编码法；另一类是有损压缩编码法（Loss compression coding），也称为熵压缩法。

9.7 常见多媒体标准

十、程序设计语言与语言处理程序基础

10.1 HTML

<a>		定义锚
<b> 	定义粗体字
<title>	定义文档的标题
<strong>定义强调文本
<table>	定义表格
<tr>	行
<td>	定义表格中的单元
<alink>	正在被击中的链接的颜色
<vlink> 已使用的链接的颜色
<body>	定义文档的主体
<button>定义按钮
<center>定义居中文本
<col> 	定义表格中一个或多个列的属性值
<font>	定义文字的字体、尺寸和颜色
<form>	定义供用户输入的HTML表单
<frame>	定义框架集的窗口或框架
<h1>	定义HTML标题
<hr>	定义水平线
<html>	定义HTML文档
<img>	定义图像
<p>		定义段落
<l>		斜体
<script>定义客户端脚本
align:对齐方式
mailto：邮箱地址超链接

10.2 编译过程

中间代码生成和代码优化不是必须的

中间代码与具体的机器无关，使用中间代码有利于进行与机器无关的优化处理，以及提高编译程序的可移植性，常见的有逆波兰记号（后缀式）、四元式、三元式和树

编译程序生成源程序的目标程序，而解释程序反之

解释器参与运行控制、程序执行的速度慢

语法分析方法分为两类：

• 自上而下分析法：递归下降法和预测分析法
• 自下而上分析法：移进-规约分析法

语法制导翻译是一种静态语义分析方法

符号表的作用是记录源程序中各个符号的必要信息

记号流：词法分析输出记号流，语法分析输入记号流

字符流：IO操作

源程序：词法分析的任务是把源程序的字符串转换成单词符号序列

分析树：如果没有语法错误，语法分析后就能正确的构造出其语法树

10.3 文法定义

大多数程序设计语言的语法规则用上下文无关文法描述

10.4 语法推导树

例：文法G=({a,b},{S,A},S,P),其中：S->aAS|a；A->SbA|SS|ba。请构造句型aabAa的推导树。

S->aAS；S->a；A->SbA；A->SS；A->ba.

10.5 有限自动机

确定的有限自动机，当输入一个数字时只有一种可走的状态

有限自动机是进行词法分析的适当工具

正规式

正规式是描述程序语言单词的表达式，对于字母∑，其上的正规式及其表示的正规集可以递归定义如下。

①是一个正规式，它表示集合 L（e）={e}。

②若a是上的字符，则a是一个正则式，它所表示的正规 L（a）={a}。

③若正规式r和s分别表示正规集L（r）=L（s），则

（a）rls是正规式，表示集合L（r）UL（s）；
（b）r·s是正规式，表示集合L（r）L（s）；
（c）r*是正规式，表示集合（L（r））*；
（d）（r）是正规式，表示集合L（r）。

仅由有限次地使用上述三个步骤定义的表达式才是∑上的正规式。由此可见，正规式要么为空，要么由字母、或、连接、闭包运算符组成。其中闭包运算符“*”具有最高的优先级，连接运算具有次高优先级，或运算符“|”具有最低优先级。

10.5 数据类型与程序控制结构

常见的数据类型

• 数据数据类型
• 布尔类型
• 字符类型
• 枚举类型
• 指针类型

程序控制结构主要有：顺序结构、选择结构和循环结构

10.7 程序语言基础-表达式

10.8 函数调用-传值与传址

传递方式	主要特点
传值调用	形参取的是实参的值，形参的改变不会导致调用点所传的实参的值发生改变。
引用（传址）调用	形参取的是实参的地址，即相当于实参存储单元的地址引用因此其值的改变同时就改变了实参的值

10.9 各种语言的特点

1. Fortran语言（科学计算，执行效率高）
2. Pascal语言（为教学而开发的，表达能力强，Delphi）
3. C语言（指针操作能力强，高效）
4. Lisp语言（函数式程序语言，符号处理，人工智能）
5. C++语言（面向对象，高效）
6. Java语言（面向对象，中间代码，跨平台）
7. C#语言（面向对象，中间代码，.Net）
8. Prolog语言（逻辑推理，简洁性，表达能力，数据库和专家系统）
9. Python语言（解释型，面向对象，脚本语言）

十一、知识产权与标准化

11.1 保护范围与对象

法律法规名称	保护对象即范围	注意事项
著作权法（版权）	著作权 文学、绘画、摄影等作品	1、不需要申请，作品完成即开始保护 2、绘画或摄影作品原件出管（赠予）著作权还归原作者，原件拥有者有：所有权、展览权。
软件著作权 计算机软件保护条例	软件著作权 软件作品	1、不需要申请，作品完成即开始保护 2、登记制度便于举证
专利法	专利权	需要申请，专利权有效期是从申请日开始计算
商标法	商标权	需要申请，核准之日起商标受保护
反不正当竞争法	商业秘密权	1、商业秘密包括技术与经营两个方面 2、必须有保密措施才能认定商业秘密

11.2 保护期限

客体类型	权利类型	保护期限
公民作品	1、署名权、修改权、保护作品完整权 2、发表权、使用权和获得报酬权	1、没有期限 2、作者终生及其死亡后的50年（第50年的12月31日）
单位作品	发表权、使用权和获得报酬权	50年（首次发表后的第50年的12月31日），若其间未发表，不保护
公民软件产品	1、署名权、修改权 2、发表权、复制权、发行权、出租权、信息网络传播权、翻译权、使用许可权、获得报酬权、转让权	1、没有期限 2、作者终生及其死亡后的50年（第50年的12月31日）合作开发，以最后死亡作者为准
单位软件产品	发表权、复制权、发行权、出租权、信息网络传播权、翻译权、使用许可权、获得报酬权、转让权	50年（首次发表后的第50年的12月31日），若其间未发表，不保护
注册商标		有效期10年（若注册人死亡或倒闭1年后，未转移则可注销，期满前6个月内必须续注）
发明专利权		保护期为20年（从申请日开始）
实用新型和外观设计专利权		保护期为10年（从申请日开始）
商业秘密		不确定，公开后公众可用

11.3 知识产权确定（重点）

11.4 侵权的判定

• 中国公民、法人或者其他组织的作品，不论是否发表，都享有著作权。
• 开发软件所用的思想、处理过程、操作方法或者数学概念不受保护
• 著作权法不适用于下列情形：
  • 法律、法规，国家机关的决议、决定、命令和其他具有立法、行政、司法性质的文件，及其官方正式译文；
  • 时事新闻；
  • 历法、通用数表、通用表格和公式。

不侵权	侵权
①个人学习、研究或者欣赏； ②适当引用； ③公开演讲内容 ④用于教学或科学研究 ⑤复制馆藏作品； ⑥免费表演他人作品； ⑦室外公共场所艺术品临幕、绘画、摄影、录像； ⑧将汉语作品译成少数民族语言作品或盲文出版。	①未经许可，发表他人作品； ②未经合作作者许可，将与他人合作创作的作品 当作自己单独创作的作品发表的； ③未参加创作，在他人作品署名； ④歪曲、篇改他人作品的； ⑤盗窃他人作品的； ⑥使用他人作品，未付报酬； ⑦未经出版者许可，使用其出版的图书、期刊的版式设计的。

11.5 标准化

标准的分类

• 国际标准：ISO、IEC等国际标准化组织
• 国家标准：GB-中国、ANSI-美国、BS-英国、IS-日本
• 区域标准：又称为地区标准，如PASC-太平洋地区标准会议、CEN-欧洲标准委员会、ASAC-亚洲标准咨询委员会、ARSO-非洲地区标准化组织行业标准：GB-中国军用标准、MIT-S美国军用标准、IEEE美国电气电子工程师协会
• 地方标准：国家的地方一级行政机构制订的标准
• 企业标准
• 项目规范

标准的编号

• 国际、国外标准代号：标准代号+专业类号+顺序号+年代号
• 我国国家标准代号：强制性标准代号为GB、推荐性标准代号为GB/T；指导性标准代号为GB/Z、实物标准代号GSB
• 行业标准代号：由汉语拼音大写字母组成（如电子行业为SJ）
• 地方标准代号：由DB加上省级行政区代码的前两位
• 企业标准代号：由Q加上企业代号组成

十二、大题

大题题型固定，主要靠刷题

12.1 数据流图

答题技巧

详细分析试题说明

数据管理员可通过中间件进行用户管理、操作管理和权限管理。用户管理维护用户信息，用户信息（用户名、密码）存储在用户表中；操作管理维护数据实体的标准操作及其所属的后端数据库信息，标准操作和后端数据库信息存放在操作表中；权限管理维护权限表，该表存储用户可执行的操作信息。

==>

数据管理员是一个外部实体；
中间件中有“用户管理”、“操作管理”、“权限管理”这些加工；
中间件中有“用户表”这个数据存储，且该存储与“用户管理”相关；
后端数据库是一个外部实体；
中间件中有“操作表”这个数据存储，且该存储与“操作管理”相关：
中间件中有“权限表”这个数据存储，且该存储与“权限管理”相关。

利用数据平衡原则

1. 加工处理和数据流的正确使用，一个加工必须既有输入又有输出；数据流只能和加工相关，即从加工流向加工、数据源流向加工或加工流向数据源，每条数据流的起点或者终点必须是加工
2. 每个数据流和数据存储都要在数据字典中有定义
3. 数据流图中最底层的加工处理必须有加工处理说明
4. 父图和子图必须平衡
5. 加工处理说明和数据流图中加工处理涉及的元素保持一致。例如，在加工处理说明中，输入数据流必须说明其是如何使用，输出数据流说明如何产生或选取，数据存储说明如何选取、使用或修改
6. 一幅图中的元个数控制在7+2内

一、补充实体

实体可能是：
（1）人物角色：如客户、管理员、主管、经理、老师、学生
（2）组织机构：如银行、供应商、慕捐机构
（3）外部系统：如银行系统、工资系统、后台数据库（当要开发的是中间件时）

二、补充存储

存储的文字方面特征：“**文件” “**表” “**库” “**清单” “**档案”

三、补充数据流

1、数据平衡原则

（1）顶层图与0层图对比，是否有顶层图有，但0层图无的数据流，或反之。
（2）检查图中每个加工，是否存在只有入没有出，或只有出没有入，或根据输入的数据无法产生对应的输出的情况。

2、按题目说明与图进行匹配

说明中的每一句话，都能与图中有对应关系，当把说明中的实体与数据流标识出来之后，容易缩小对应范围，找出漏。

四、补充加工名

加工是用于处理数据流的，所以要补充加工名，可以把该加工涉及到的数据流，在说明中标识出来，再在数据流名称所在的句子中，找“动词+名词”的结构，分析是否可作为加工。

“动词+名词”如：生成报告，发出通知，批改作业，记录分数，当然这只是普遍情况，也有例外，如物流跟踪、用户管理

12.2 数据库设计

• 补画ER图
• 填写缺失属性、关系

12.3 UML

• 主要是用例图和结合类图考

12.4 算法

求时间复杂度、分治算法、回溯算法、贪心算法、动态规划算法（重点）

12.5 面向对象

C++/Java面向对象题目二选一，掌握面向对象知识即可