软件设计师笔记

软考

字数统计: 19k阅读时长: 71 min

 2021/04/07   Share

计算机组成与体系结构

1 数据的表示

1.1 R进制转十进制使用按权展开法

其具体操作方式为：将 R 进制数的每一位数值用 R^k 形式表示，即幂的底数是 R，指数为 k ，k 与该位和小数点之间的距离有关。当该位位于小数点左边，k 值是该位和小数点之间数码的个数，而当该位位于小数点右边，k 值是负值，其绝对值是该位和小数点之间数码的个数加 1 。

例如：二进制 10100.01 =1 x 2⁴ + 1 x 2² + 1 x 2^-2
例如：七进制 604.01= 6 x 7² + 4 x 7⁰ + 1 x 7^-2

1.2 十进制转R进制使用短除法

将 42 转换为二进制数。

1.3 二进制转八进制与十六进制数

1.4 原码

原码就是符号位加上真值的绝对值，即用第一位表示符号，其余位表示值。例如 8 位二进制：:

1 2	[+1]原 = 0000 0001 [-1]原 = 1000 0001

1.5 反码

反码的表示方法是：

正数的反码是其本身。
负数的反码是在其原码的基础上，符号位不变，其余各个位取反。

1 2	[+1] = [00000001]原 = [00000001]反 [-1] = [10000001]原 = [11111110]反

1.6 补码

补码的表示方法是：

正数的补码就是其本身。
负数的补码是在其原码的基础上，符号位不变，其余各位取反，最后 + 1。 (即在反码的基础上 + 1)

1 2	[+1] = [00000001]原 = [00000001]反 = [00000001]补 [-1] = [10000001]原 = [11111110]反 = [11111111]补

1.7 原码、反码、补码的数值表示范围

数据类型	整数
原码	-(2^n-1-1)~2^n-1-1
反码	-(2^n-1-1)~2^n-1-1
补码	-2^n-1~2^n-1-1

1.8 浮点数运算

浮点数表示：$N = M * R^e$
其中M称为尾数，e是指数，R为基数。

例题：两浮点数 x = 0.1101 2⁰¹，y = (-0.1010)\2¹¹，求 x + y

对阶
1. 求补码
  
  [x]_补 = 00,01;00.1101
  
  [y]_补 = 00,11;11.0110
2. 求阶差
  
  小阶向大阶对阶，同时尾数右移，移动位数为阶差。
  
  00.11 - 00.01 = 00.10 = 2
  
  阶差为 2
  
  [x]_补= 00,11;00.0011
尾数求和

将对阶后的两个尾数按定点加减运算规则进行运算。
上述对阶后得：[x]_补 = 00,11;00.0011 [y]_补 = 00,11;11.0110
[x+y]_补=00,11;11.1001。
规格化
1. 左规
  
  尾数出现 00.0xx…x 或 11.1xx…x 时需要进行左规，左规时尾数左移一位，阶码减一，直到成为：00.1xx…x 或 11.0xx…x。即尾数第一位和符号位相同。
  如上例求和结果为：
  [x+y]补= 00,11;11.1001
  故将其尾数左移一位，阶码减一，得：
  00,10;11.0010
  规格化后这是补码，求其尾数的原码即可，故结果为
  x + y = (-0.1110) * 2¹⁰
2. 右规
  
  当尾数出现01.xx…x或10.xx…x时表示尾数溢出，需要进行右归，右归时尾数右移，阶码加1。即两位符号位的数值不相同（01 / 10）。
  例题：已知浮点数 x = 0.1101 x 2¹⁰，y = 0.1011 x 2⁰¹，求 x + y
  
  对阶：
  
  求补码：[x]_补 = 00,10;00.1101，[y]_补 = 00,01;00.1011。
  
  求阶差：00,10 - 00,01 = 00,01 = 1 ，故阶差为 1 ，故[y]_补=00,10;00.0101
  
  尾数求和：
  
  [x+y]_补 = 00,10;01.0010
  故需要进行右规，尾数向右移动一位，阶码加 1 得：[x+y]补 = 00,11;00.1001
  
  则 x + y = 0.1001 x 2¹¹
舍入

舍入，是指数据的长度超过了计算机当中存储数据的物理器件所保存的数据长度。低位部分就要进行处理，保证数据能够以比较精确的精度保存在计算机当中。

在对阶和右规过程中，可能出现尾数末位丢失，引起误差。为了尽可能减小误差，就需要考虑舍入。

舍入的方法：
1. 截断法
  
  将移出的数据一律舍去。该方法简单，很常用。但是影响精度。
2. 0舍1入法
  
  移掉的是1，则尾数末尾加 1，移掉的是 0，就不加。
3. 恒置“1”法
  
  将要保留的末位数据恒置 1，无论右移掉的是 1 还是 0，末位是 1 还是 0。

2 计算机结构

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

4 流水线

流水线是指在程序执行时多条指令重叠进行操作的一种准并行处理实现技术。各种部件同时处理是针对不同指令而言的，它们可同时为多条指令的不同部分进行工作，以提高各部件的利用率和指令的平均执行速度。

4.1 流水线计算

流水线周期为执行时间最长的一段
流水线计算公式为：1 条指令执行时间 + （指令条数 - 1）流水线周期
理论公式（At 为流水线周期）：$(t1+t2+..+ tk)+(n-1)At$

实践公式（At 为流水线周期，k 为几部分）：$kAt+（n-1）At$

例题：若指令流水线把一条指令分为取指、分析和执行三部分，且三部分的时间分别取指 2ns，分析 2ns，执行 1ns。那么，流水线周期是多少？100条指令全部执行完毕需要的时间是多少？

流水线周期：2ns

理论公式：$（2+2+1）+（100-1）* 2 = 203$

实践公式：$32+（100-1）2 = 204$

4.2 流水线吞吐率计算

流水线的吞吐率（Though Put rate，TP）是指在单位时间内流水线所完成的任务数量或输出的结果数量。计算流水线吞吐率的最基本的公式如下：
$$
TP =\frac{指令条数}{流水线执行时间}
$$
流水线最大吞吐率：
$$
TP_{max}=\lim_{n\rightarrow+\infty}\frac{n}{(k+n-1)\Delta{t}}=\frac{1}{\Delta{t}}(\Delta{t}为流水线周期)
$$
例题：若指令流水线把一条指令分为取指、分析和执行三部分，且三部分的时间分别取指 2ns，分析 2ns，执行 1ns。请计算吞吐率和最大吞吐率。

吞吐率：$TP=\frac{100}{203}=0.49$

最大吞吐率：$TP_{max}=\frac{1}{2}=0.5$

4.3 流水线的加速比

完成同样一批任务，不使用流水线所用的时间与使用流水线所用的时间之比称为流水线的加速比。计算流水线加速比的基本公式如下:
$$
S=\frac{不使用流水线的执行时间}{使用流水线的执行时间}
$$
例题：若指令流水线把一条指令分为取指、分析和执行三部分,且三部分的时间分别取指2ns ,分析2ns,执行1ns。请计算流水线的加速比。
$$
S=\frac{(2+2+1)100}{(2+2+1)+(100-1)2}=\frac{500}{203}=2.46
$$

4.3 流水线的效率

流水线的效率是指流水线的设备利用率。在时空图上，流水线的效率定义为 n 个任务占用的时空区与k个流水段总的时空区之比。

计算流水线效率的公式：
$$
E=\frac{n个任务占用的时空区}{k个流水段总的时空区}=\frac{T_0}{KT_k}
$$

$$
E=\frac{（\Delta{t}+\Delta{t}+\Delta{t}+3\Delta{t}）4}{415\Delta{t}}=0.4
$$

5 层次化存储结构

6 Cache

Cache 的功能：提高 CPU 数据输入输出的速率，突破冯●诺依曼瓶颈，即 CPU 与存储系统间数据传送带宽限制。
在计算机的存储系统体系中，Cache 是访问速度最快的层次。
使用 Cache 改善系统性能的依据是程序的局部性原理。

如果以 h 代表对 Cache 的访问命中率，t₁ 表示 Cache 的周期时间，t₂ 表示主存储器周期时间，以读操作为例，使用 Cache + 主存储器的系统的平均周期为 t₃，则：

$t_3 = ht_1+(1-h)t_2$

其中，（1 - h）又称为失效率（未命中率）。

例题：Cache的访问命中率为95%，Cache的周期时间为1ns，主存储器周期时间为1ms（1ms=1000ns），以读操作为例，求使用 Cache + 主存储器的系统的平均周期。

$t_3 = ht_1+(1-h)t_2=95\%1ns+(1-95\%)1000ns=50.95ns$

7 局部性原理

时间局部性
空间局部性

工作集理论：工作集是进程运行时被频繁访问的页面集合。

8 主存储器

主存储器编址

例题：内存地址从 AC000H 到 C7FFFH，共有多少 K 个地址单元？如果该内存地址按字（16bit）编址，由 28 片存储器芯片构成。已知构成此内存的芯片每片有 16K 个存储单元，则该芯片每个存储单元存储多少位？

地址单元的个数：将内存大地址减去小地址再加 1

$C7FFFH-AC000H+1=1C000H（给7加的是16，因为是16进制）$

转为 K 个地址单元：将十六进制转成十进制再除以 1024

$\frac{16^4+12*16^3}{1024}=112$

故共有 112K 个地址单元

设每个存储单元存储X位

$\frac{112K16}{2816K*X}=1$

得 X = 4

则每个存储单元存储 4 位

9 磁盘结构与参数

存取时间 = 寻道时间 + 等待时间（平均定位时间 + 转动延迟）
注意：寻道时间是指磁头移动到磁道所需的时间，等待时间为等待读写的扇区转到磁头下方所用的时间。

最长时间：

磁盘旋转周期为33ms，因此磁盘旋转一周时间为33ms，磁盘总共有11个物理块，所以每个物理块需要的读取时间为3ms。

磁头当前在R₀开始处，所以数据从R₀开始读取。
使用单缓冲区顺序处理记录，所以需要一条数据读取完毕并且处理完毕后才能读取下一条数据。

磁头首先读取出R₀放在缓冲区处理。3ms之后R₀读取完毕放入缓冲区，此时磁头位于R₁的开始处，但是由于单缓冲区所以此时无法直接读取R₁并对R₁进行操作，于是磁盘继续转动，3ms之后R₀处理完毕，此时磁头位于R₂的开始处，并非我们需要处理的R₁，因此磁盘继续转动寻找R₁，直到再转一圈（33ms）到达R₁的开始处开始读取R₁（3ms）。

因此R₀需要的时间为读取3ms加处理3ms，剩余R₁到R₁₀需要的时间为(33+3)*10=360ms，所以总处理时间为360+6=366ms。

最短时间：

在对数据进行重新排列后此时磁盘上数据的存储顺序为：

1	2	3	4	5	6	7	8	9	10	11
R₀	R₆	R₁	R₇	R₂	R₈	R₃	R₉	R₄	R₁₀	R₅

此时开始处理，磁头从R0开始处读取，读取（3ms）完毕后放入缓冲区处理（3ms），此时磁盘继续转动，R0处理完毕时此时磁头正好处于R1的开始处，开始对R1读取并处理。因此这是对存储优化分布之后最理想的读取情况，所需时间为：

（读取（3ms）+处理（3ms））*11=66ms。

10 总线

根据总线所处的位置不同,总线通常被分成三种类型,分别是：

内部总线
系统总线
- 数据总线
- 地址总线
- 控制总线
外部总线

11 系统可靠性分析

串联系统（所有都正常，系统才能正常运行）

$$
可靠度：R=R_1R_2…*R_n
$$

$$
失效率：\lambda=\lambda_1+\lambda_2+…+\lambda_n
$$

并联系统（一个正常，系统就正常）

$$
可靠度：R=1-(1-R_1)(1-R_2)…*(1-R_n)
$$

$$
失效率：\mu=1-R
$$

模冗余系统（少见）

m是子系统的个数

混合系统（先看整体）

例题：

整体为串联系统，局部为并联系统
$$
R_1=R(1-(1-R)^3)(1-(1-R)^2)
$$

12 差错控制

12.1 什么是检错和纠错？

检测：检测错误。

纠错：检测出错误并纠正错误。

12.2 什么是码距？

一个编码系统的码距是整个编码系统中任意（所有）两个码字的最小距离。
例:
若用 1 位长度的二进制编码。若 A= 1, B = 0。这样A, B之间的最小码距为 1。
若用 2 位长度的二进制编码，若以 A = 11, B = 00为例，A、B之间的最小码距为 2。
若用 3 位长度的二进制编码，可选用 A = 111,B = 000作为合法编码。A, B之间的最小码距为 3。

12.3 码距与检错、纠错有何关系？

在一个码组内为了检测 x 个误码，要求最小码距 d 应该满足：d >= x + 1
在一个码组内为了纠正 x 个误码，要求最小码距 d 应该满足：d >= 2x + 1

12.4 CRC

什么是模2除法，它和普通的除法有何区别？

模 2 除法是指在做除法运算的过程中不计其进位的除法。

例题：10111对110进行模2除法为

普通除法运算过程：

模2除法运算过程：

例题：原始报文为11001010101，其生成多项式为：x⁴+x³+x+1。对其进行CRC编码后的结果为？

被除数：原始报文 + 生成多项式的最高次方个 0 = 110010101010000

除数：生成多项式有幂次就为 1，没有幂次就为 0 = 11011

被除数对除数进行模 2 除法运算

CRC编码：原始报文 + 余数 = 110010101010011

CRC编码对除数进行模2除法运算得出的余数为0，即传输的信息没有出错。

12.5 海明校验码

例题：求信息1011的海明码。

因信息1011有4位，故x=4，代入公式2^r>=x+r+1，得2^r>=4+r+1

故确定校验码为3位：2³>=4+3+1。

分别放在2⁰=1、2¹=2、 2²=4 位。（分别放在2⁰到2^{检验码的位数-1}）
列出校验位公式。
$$
7=2^2+2^1+2^0
$$

$$
6=2^2+2^1
$$

$$
5=2^2+2^0
$$

$$
3=2^1+2^0
$$

$$
r_2 = I_4 \bigoplus I_3 \bigoplus I_2 \
r_1 = I_4 \bigoplus I_3 \bigoplus I_1 \
r_0 = I_4 \bigoplus I_2 \bigoplus I_1
$$

| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 位数 |
| :———–: | :———–: | :———–: | :———–: | :———–: | :———–: | :———–: | :—-: |
| I₄ | I₃ | I₂ | | I₁ | | | 信息位 |
| | | | r₂ | | r₁ | r₀ | 校验位 |
根据公式得r₂=0，r₁=0，r₀=1。
$$
r_2 = I_4 \bigoplus I_3 \bigoplus I_2 = 1 \bigoplus 0 \bigoplus 1 = 0\
r_1 = I_4 \bigoplus I_3 \bigoplus I_1 = 1 \bigoplus 0 \bigoplus 1 = 0\
r_0 = I_4 \bigoplus I_2 \bigoplus I_1 = 1 \bigoplus 1 \bigoplus 1 = 1
$$
将数据加入表格，如表所示。

7	6	5	4	3	2	1	位数
1	0	1		1			信息位
			0		0	1	校验位

海明码纠错：将收到的校验码异或正确的校验码转成十进制就知道哪个位置出错了。

操作系统基本原理

1 概述

管理系统的硬件、软件、数据资源
控制程序运行
人机之间的接口
应用软件与硬件之间的接口
进程管理
存储管理
文件管理
作业管理
设备管理

2 进程管理

2.1 进程的状态

2.2 前趋图

2.3 进程的同步与互斥

2.4 PV操作

临界资源：诸进程间需要互斥方式对其进行共享的资源，如打印机、磁带机等
临界区：每个进程中访问临界资源的那段代码称为临界区
信号量：是一种特殊的变量

P(Sn) 指的就是每当有一个人进入就对信号量进行 P 操作（-）
V(Sn) 就是指购书成功离开书店进行V操作
首先我先猜测一下付款的流程，就是先排队，再付款，因为收银员只有一人，一次只能接一单，所以得先排队，再付款，排队其实就是用 V 操作 V(S1) 而付款则是P(S2)，这里大家可能有一个问题就是没有 V(S2) 怎么 P(S2) 呢，其实 V(S2) 的操作是在收银员处执行的，因此第一题答案就是选A

第二题收银员则是先将正在排队的人进行 P 操作也就是 P(S1) 付款完成再将可进行付款的人进行 V 操作，那么就可以有新的人进来付款也就是 V(S2)
答案选 C

2.5 PV操作与前趋图

2.6 死锁问题

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

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

不可能发生死锁的最小资源数（K为进程的数量，n为进程需要的资源数）
$$
\begin{align}
X&=K(n-1)+1\
&=3（5-1）+1\
&=13
\end{align}
$$
故系统至少需要13个资源，则不可能发生死锁。

银行家算法：分配资源的原则

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

首先求剩下的资源数:
R1 = 9-(1+2+2+1+1) = 2
R2 = 8-(2+1+1+2+1) = 1
R3 = 5-(1+1+3) = 0

3 存储管理

3.1 分区存储组织

某计算机系统的内存大小为 128k ，采用可变分区分配方式进行内存分配，当前系统的内存分块情况如下图所示，现有作业 4 申请内存 9k，几种不同的存储分配算法在分配中，会产生什么样的结果呢？

3.2 页式存储组织

高级程序语言使用逻辑地址。
运行状态,内存中使用物理地址。

优点：利用率高，碎片小，分配及管理简单
缺点：增加了系统开销，可能产生抖动现象

页面大小为4K = 2¹²，故页内位移占12位。

逻辑地址位5A29H，故页号为5，页内位移为A29。

页号为5对应的页帧号为6。

故选D

淘汰页号：只有状态位为1，访问位为0的才能被淘汰。

故选B

3.3 段式存储组织

优点：多道程序共享内存，各段程序修改互不影响
缺点：内存利用率低，内存碎片浪费大

3.4 段页式存储组织

优点：空间浪费小、存储共享容易、存储保护容易、能动态连接
缺点：由于管理软件的增加，复杂性和开销也随之增加，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降

3.5 快表

快表是一块小容量的相联存储器（Associative Memory），由高速缓存器组成，速度快，并且可以从硬件上保证按内容并行查找，一般用来存放当前访问最频繁的少数活动页面的页号。

3.6 页面置换算法

最优（Optimal，OPT）算法
随机（RAND）算法
先进先出（FIF0）算法：有可能产生“抖动”。例如，432143543215序列，用3个页面，比4个缺页要少
最近最少使用（LRU）算法：不会“抖动”

FIFO

8位计算机，16位的指令，16位的操作数。

没有使用快表，故每一个块需要进行俩次内存的访问。

进程在执行时，首先查找页表，然后再取指令或者取数据。可见执行16位的swap指令时，首先需要取指令，即先访问页表，取指令的高字节，接着再一次访问页表，取指令的低字节，共需访问主存4次。然后取操作数A，访问页表，取操作数A的高字节，再访问页表，取操作数A的低字节，共需访问主存4次。同理，取操作数B也需要访问主存4次。

共有6个块，所以需要访问12次内存。

==指令产生1次缺页中断，操作数产生2次缺页中断。==

有1条指令，2个操作数，所以将产生5次缺页中断。

3.7 索引文件结构

设一个索引节点为 4K，每个间接索引的地址为 4 字节

直接索引：直接存储物理盘块（0-9：10*4K = 40K）

一级间接索引：可间接存储物理盘块（10：（4K/4）*4K = 4096K）

二级间接索引：可间接存储物理盘块（11：（4K/4）*（4K/4）* 4K）

三级间接索引：可间接存储物理盘块（12：（4K/4）*（4K/4）*（4K/4）* 4K）

注意点：逻辑块号的序号从0开始。

3.8 文件和树形目录结构

文件属性

R 只读文件属性
A 存档属性
S 系统文件
H 隐藏文件

文件名的组成

驱动器号
路径
主文件名
扩展名

绝对路径：是从盘符开始的路径。
相对路径：是从当前路径开始的路径。
若当前目前为：D1，要求F2路径

则绝对路径：/D1/W2/F2 ，相对路径：W2/F2

3.9 空闲存储空间的管理

空闲区表法（空闲文件目录）
空闲链表法
位示图法

（1）物理块编号从0开始，故4195号是第4195+1个物理块（从1开始），字长为32位
$$
\begin{align}
X & = 第几个物理块/字长 \
& =（4195+1）/32\
&= 131.125
\end{align}
$$
故选择D

（2）商的小数位为0.125，字长为32位（位置从0开始）
$$
\begin{align}
X &= 商的小数位字长-1\
&=0.12532-1\
&=3
\end{align}
$$
故选择B

成组链接法

4 设备管理

4.1 数据传输控制方式

4.2 虚设备与SPOOLING技术

5 微内核操作系统

数据库系统

1 三级模式 - 两级映射

2 数据库设计过程

3 E-R模型

椭圆表示属性
矩形表示实体
菱形表示联系

集成的方法：

多个局部 E-R 图一次集成。
逐步集成，用累加的方式一次集成两个局部 E-R 。

集成产生的冲突及解决办法：

属性冲突：包括属性域冲突和属性取值冲突。
命名冲突：包括同名异义和异名同义。
结构冲突：包括同一对象在不同应用中具有不同的抽象，以及同一实体在不同局部E-R图中所包含的属性个数和属性排列次序不完全相同。

一个实体型转换为一个关系模式

1: 1 联系至少转换为 2 个关系模式（有2个实体型，转换为 2 个关系模式）
1: n 联系至少转换为 2 个关系模式（有2个实体型，转换为 2 个关系模式）
m: n 联系至少转换为 3 个关系模式（有2个实体型，转换为 2 个关系模式。有 1 个多对多联系，转换为 1 个关系模式。所以有三个关系模式）

三个以上实体间的一个多元联系

有3个实体型，故转换为3个关系模式。

有1个多对多联系，故转换为1个关系模式。

所以最少转化为4个关系模式。

4 关系代数

并（合并，重复的值只出现一次）
交（找公共部分）

差（去掉公共部分）
笛卡尔积

投影（选列）（sno可以用1代替，依次类推）

选择（选行）（sno可以用1代替，依次类推）

联接

5 规范化理论

5.1 函数依赖

设 R(U) 是属性U上的一个关系模式，X 和 Y 是 U 的子集，r 为 R 的任一关系，如果对于 r 中的任意两个元组 u，v ，只要有 u[X] = v[X]，就有 u[Y] = v[y]，则称 X 函数决定 Y ，或称 Y 函数依赖于 X ，记为 X → Y。

部分函数依赖：设 X，Y 是关系 R 的两个属性集合，存在 X → Y，若 X’ 是 X 的真子集，存在 X ’→ Y，则称 Y 部分函数依赖于 X。

例：学生基本信息表 R 中（学号，身份证号，姓名）当然学号属性取值是唯一的，在 R 关系中，（学号，身份证号）->（姓名），（学号）->（姓名），（身份证号）->（姓名）；所以姓名部分函数依赖与（学号，身份证号）。
完全函数依赖：设 X， Y是关系 R 的两个属性集合，X ’是 X 的真子集，存在 X → Y，但对每一个 X’都有 X’! → Y，则称 Y 完全函数依赖于 X。

例：学生基本信息表R（学号，班级，姓名）假设不同的班级学号有相同的，班级内学号不能相同，在R关系中，（学号，班级）->（姓名），但是（学号）->(姓名)不成立，（班级）->(姓名)不成立，所以姓名完全函数依赖与（学号，班级）。
传递函数依赖：设 X，Y，Z 是关系 R 中互不相同的属性集合，存在 X→Y (Y !→X)， Y→Z，则称 Z 传递函数依赖于 X。

例子：在关系 R (学号 ,宿舍, 费用)中，(学号)->(宿舍)，宿舍 != 学号，(宿舍) -> (费用)，费用 != 宿舍，所以符合传递函数的要求。

5.2 价值与用途

非规范化的关系模式，可能存在的问题包括：数据冗余、更新异常、插入异常、删除异常。

5.3 键

超键：唯一标识元组（可能存在多余属性）（一般不考）

候选键：唯一标识元组（已消除多余属性）

主键：任选一个候选键

外键：其他关系的主键

5.4 求候选键

将关系模式的函数依赖关系用”有向图”的方式表示。
找入度为0的属性，并以该属性集合为起点，尝试遍历有向图，若能正常遍历图中所有结点，则该属性集即为关系模式的候选键。
若入度为0的属性集不能遍历图中所有结点，则需要尝试性的将一-些中间结点(既有入度，也有出度的结点)并入入度为0的属性集中，直至该集合能遍历所有结点，集合为候选键。

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

例题2：关系模式P(A,B,C,D,E,F,G,H,I,J)满足下列函数依赖: FD={ABD→E, AB→G, B→F, C→J, CJ→I，G→H},求候选码？（ABD→E：ABD的组合键确定E（不等于A→E，B→E，D→E））

==ABCD==

例题3：关系R (A, B, C)满足下列函数依赖：F {B→C,B→A, A→BC}，关系R的候选关键字为？
A. AB ==B. A和B== C. A和BC D. AC和AB

5.5 范式

主属性：属于候选键的一部分。

非主属性：不属于候选键的一部分。

第一范式(1NF) ：在关系模式R中，当且仅当所有域只包含原子值，即每个分量都是不可再分的数据项，则称R是第一范式。

例题：下表所示的关系R是否满足1NF,如果不满足，应如何调整？

调整后：

系名称	教授	副教授
计算机系	6	10
电子系	3	5

第二范式(2NF) ：当且仅当R是1NF，且每一个非主属性完全依赖主键（不存在部分依赖）时，则称R是第二范式。

思考题：请思考该关系模式会存在哪些问题(从数据冗余、更新异常、插入异常、删除异常这几个方面来考虑)，解决方案是什么？

SNO：学号 CNO：课程号 GRADE：成绩 CREDIT：绩点

拆分为两个表（简略）：

表1

SNO	CNO	GRADE
S01	C01	75
S02	C01	92

表2

CNO	CREDIT
C01	4
C02	2

第三范式(3NF) ：当且仅当R是1NF，且E中没有非主属性传递依赖于主键时，则称R是第三范式。

思考题：请思考该关系模式会存在哪些问题(从数据冗余、更新异常、插入异常、删除异常这几个方面来考虑)，解决方案是什么？

拆分为两个表（简略）：

表1

SNO	SName	DNO
S01	张三	D01
S02	李四	D01

表2

CNO	DNAME	LOCATION
D01	计算机系	1号楼
D02	信息系	2号楼

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

==C D A==

5.6 模式分解

保持函数依赖分解

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

无损分解

什么是有损，什么又是无损？
有损：不能还原。无损：可以还原。

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

思考题：

有关系模式：成绩(学号，姓名，课程号，课程名，分数)
函数依赖：学号→姓名，课程号→课程名，(学号，课程号)→分数
若将其分解为:
成绩(学号，课程号，分数)
学生(学号，姓名)
课程(课程号，课程名)

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

由于有：学号→姓名，所以：
成绩(学号，课程号，分数，姓名)
由于有：课程号→课程名，所以：
成绩(学号，课程号，分数，姓名，课程名)

6 并发控制

6.1 基本概念

6.2 存在的问题

6.3 封锁协议

一级封锁协议。事务T在修改数据R之前必须先对其加X锁，直到事务结束才释放。==可防止丢失修改==
二级封锁协议。一级封锁协议加上事务T在读取数据R之前先对其加S锁，读完后即可释放S锁。==可防止丢失修改，还可防止读“脏”数据==
三级封锁协议。一级封锁协议加上事务T在读取数据R之前先对其加S锁，直到事务结束才释放。==可防止丢失修改、防止读“脏”数据与防止数据重复读==
两段锁协议。可串行化的。可能发生死锁

7 数据库完整性约束

实体完整性约束
参照完整性约束
用户自定义完整性约束
触发器

8 数据库安全

9 数据备份

冷备份也称为静态备份，是将数据库正常关闭，在停止状态下，将数据库的文件全部备份(复制)下来。
热备份也称为动态备份，是利用备份软件，在数据库正常运行的状态下，将数据库中的数据文件备份出来。

完全备份：备份所有数据
差量备份：仅备份上一次完全备份之后变化的数据
增量备份：备份上一次备份之后变化的数据

星期一	星期二	星期三	星期四
完全备份	增量备份	增量备份	差量备份
	备份星期一备份之后变化的数据	备份星期一备份之后变化的数据备份星期二备份之后变化的数据	备份星期一备份之后变化的数据

静态海量转储：在系统中无运行事务时进行，每次转储全部数据库。
静态增量转储：在系统中无运行事务时进行，每次只转储上一次转储后更新过的数据。
动态海量转储：转储期间允许对数据库进行存取或修改，每次转储全部数据库。
动态增量转储：转储期间允许对数据库进行存取或修改，每次只转储上一次转储后更新过的数据。

日志文件：事务日志是针对数据库改变所做的记录，它可以记录针对数据库的任何操作，并将记录结果保存在独立的文件中。

10 数据库故障与恢复

11 数据仓库与数据挖掘

面向主题
集成的
相对稳定的(非易失的)
反映历史变化(随着时间变化)

数据挖掘方法：

决策树
神经网络
遗传算法
关联规则挖掘算法

数据挖掘方法分类：

关联分析：挖掘出隐藏在数据间的相互关系。
序列模式分析：侧重点是分析数据间的前后关系(因果关系)。
分类分析：为每一个记录赋予-个标记再按标记分类。
聚类分析：分类分析法的逆过程。

12 反规范化

由于规范化会使表不断的拆分，从而导致数据表过多。这样虽然减少了数据冗余，提高了增、删、改的速度，但会增加查询的工作量。系统需要进行多次连接,才能进行查询操作,使得系统效率大大下降。

技术手段：

增加派生性冗余列
增加冗余列
重新组表
分割表

13 大数据

大数据处理系统应该具有的重要特征：

高度可扩展性
高性能
高度容错
支持异构环境
较短的分析延迟
易用且开放的接口
较低成本
向下兼容性

计算机网络

1 OSI/RM七层模型

例题：某IP网络连接如图所示，在这种配置下IP全局广播分组不能够通过的路径是_ (1)_ 。
A.计算机P和计算机Q之间的路径 ==B.计算机P和计算机S之间的路径==
C.计算机Q和计算机R之间的路径 D.计算机S和计算机T之间的路径

==集线器属于一层设备，网桥和交换机属于二层设备，路由器属于三层设备。二层设备可能分割冲突域，三层设备可能分割广播域。==

2 网络技术标准与协议

TCP/IP协议：Internet，可扩展，可靠，应用最广，牺牲速度和效率
IPX/SPX协议：NOVELL，路由，大型企业网
NETBEUI协议：IBM，非路由，快速

2.1 TCP协议（可靠传输）

TCP连接状态：

第一次握手：SYN_RECV

第二次握手：SYN_RECV

第三次握手：ESTABLISHED

2.2 DHCP协议

客户机/服务器模型
租约默认为8天
当租约过半时，客户机需要向DHCP服务器申请续租
当租约超过87 .5%时，如果仍然没有和当初提供IP的DHCP服务器联系上，则开始联系其他的DHCP服务器。
固定分配、动态分配和自动分配。
169.254.X.X （windows）和0.0.0.0（liunx）（如果地址为这些，则认为分配失败）

2.3 DNS协议

递归查询：服务器必需回答目标IP与域名的映射关系。
迭代查询：服务器收到一次迭代查询回复一次结果，这个结果不一定是目标IP与域名的映射关系，也可以是其它DNS服务器的地址。

主机向本地域名服务器的查询采用递归查询。
本地域名服务器向根域名服务器的查询通常采用迭代查询。

主机向本地域名服务器的查询采用递归查询。
本地域名服务器向根域名服务器的查询采用了递归查询。
根域名服务器负担重，效率低故较少采用。

==A==

3 计算机网络的分类

按分布范围分类
- 局域网（LAN）
- 城域网（MAN）
- 广域网（WAN）
- 因特网
按拓扑结构分类
- 总线型
- 星形
- 环形

4 网络规划与设计

4.1 逻辑网络设计

利用需求分析和现有网络体系分析的结果来设计逻辑网络结构，最后得到一份逻辑网络设计文档，输出内容包括以下几点：

逻辑网络设计图
IP地址方案
安全方案
具体的软硬件、广域网连接设备和基本服务
招聘和培训网络员工的具体说明
对软硬件、服务、员工和培训的费用初步估计

4.2 物理网络设计

物理网络设计是对逻辑网络设计的物理实现，通过对设备的具体物理分布、运行环境等确定，确保网络的物理连接符合逻辑连接的要求。输出如下内容:

网络物理结构图和布线方案
设备和部件的详细列表清单
软硬件和安装费用的估算
安装日程表，详细说明服务的时间以及期限
安装后的测试计划
用户的培训计划

4.3 分层设计

接入层：向本地网段提供用户接入
汇聚层：网络访问策略控制、数据包处理、过滤、寻址
核心层：数据交换

5 IP地址

A类（前8位为网络号，后24位为主机号）：主机数为2²⁴-2

B类（前16位为网络号，后16位为主机号）：主机数为2¹⁶-2

C类（前24位为网络号，后8位为主机号）：主机数为2⁸-2

6 子网划分

子网掩码
将一个网络划分成多个子网(取部分主机号当子网号)
将多个网络合并成一个大的网络(取部分网络号当主机号)

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

B类IP地址前16位为网络号，所以子网掩码前16位为1

需要划分成27个子网，设子网号为R位
$$
27<2^R\
R=5
$$
故子网号为5位

子网掩码：11111111 11111111 11111000 00000000 -> 255.255.248.0

例题2：将B类IP地址168.195.0.0划分成若干子网，每个子网内有主机700台，则子网掩码为多少？

因为每个子网有700台主机，设主机号为x位
$$
2^x-2>=700\
x=10
$$
故主机号为10位

子网掩码：11111111 11111111 11111100 00000000 -> 255.255.252.0

7 无分类编址（无类域间路由）

IP地址::={<网络前缀>，<主机号>}

128.14.32.0/20表示的地址块共有2¹²个地址。
这个地址块的起始地址是128.14.32.0.
在不需要指出地址块的起始地址时,也可将这样的地址块简称为“/20地址块”
128.14.32.0/20地址块的最小地址: 128.14.32.0
128.14.32.0/20地址块的最大地址: 128.14.47.255
全0和全1的主机号地址一般不使用。

例题：分配给某公司网络的地址块是210.115.192.0/20，,该网络可以被划分为（）个C类子网。
A.4 B.8 ==C.16== D.32

8 特殊含义的IP地址

9 HTML

10 无线网

11 网络接入技术

有线接入：

公用交换电话网络(PSTN)
数字数据网(DDN)
综合业务数字网(ISDN)
非对称数字用户线路(ADSL)
同轴光纤技术(HFC)

无线接入：

IEEE 802. 11 (WiFi)
IEEE 802. 15 (蓝牙Bluetooth)
红外(IrDA)
WAPI

3G/4G：

WCDMA(3G)
CDMA2000(3G)
TD- SCDMA(3G)
LTE-Advanced(4G)
WirelessMAN-Advanced (802. 16m) (WiMAX)(4G)

12 IPv6

IPv6是设计用于替代现行版本IP协议( IPv4 )的下一代IP协议。

IPv6地址长度为128位,地址空间增大了2⁹⁶倍
灵活的IP报文头部格式。使用一系列固定格式的扩展头部取代了IPv4中可变长度的选项字段。IPv6中选项部分的出现方式也有所变化，使路由器可以简单路过选项而不做任何处理，加快了报文处理速度
IPv6简化了报文头部格式，字段只有8个，加快报文转发，提高了吞吐量
提高安全性。身份认证和隐私权是IPv6的关键特性
支持更多的服务类型
允许协议继续演变，增加新的功能，使之适应未来技术的发展

单播地址(Unicast) ：用于单个接口的标识符。
任播地址(Anycast) ：泛播地址。一组接口的标识符，IPV4广播地址。
组播地址( Multicast) ： IPv6中的组播在功能上与IPv4中的组播类似。

系统安全分析与设计

1 信息系统安全属性

安全属性：

保密性：最小授权原则、防暴露、信息加密、物理保密
完整性：安全协议、校验码、密码校验、数字签名、公证
可用性：综合保障(IP过滤、业务流控制、路由选择控制、审计跟踪)
不可抵赖性：数字签名

2 对称加密技术（适合大信息量）

加密、解密的密钥相同

缺陷：

加密强度不高。
密钥分发困难。

常见对称密钥加密算法：

DES ：替换+移位、56位密钥、64位数据块、速度快、密钥易产生
3DES(三重DES) ：两个56位的密钥K1、K2
```
加密：K1加密-> K2解密-> K1加密
解密：K1解密-> K2加密-> K1解密
```
AES ：高级加密标准Rijndael加密法，是美国联邦政府采用的一-种区块加密标准。这个标准用来替代原先的DES。对其要求是“至少与3DES一样安全”。
RC-5：RSA数据安全公司的很多产品都使用了RC-5。
IDEA算法：128位密钥、64位数据块、比DES的加密性好、对计算机功能要求相对低，PGP。

3 非对称加密技术（适合小信息量）

公钥加密，私钥解密（甲公钥加密，只有甲私钥才能解密）

缺陷：加密速度慢

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

RSA：512位(或1024位)密钥、计算量极大、难破解
Elgamal ：其基础是Diffie-Hellman密钥交换算法
ECC：椭圆曲线算法
其它非对称算法包括：背包算法、Rabin、 D-H

4 信息摘要

单向散列函数 (单向Hash函数)、固定长度的散列值。（信息可以形成摘要，摘要不能还原成信息）

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

5 数字签名

6 数字信封与PGP

发送方将原文用对称密钥加密传输，而将对称密钥用接收方公钥加密发送给对方。
接收方收到电子信封，用自己的私钥解密信封，取出对称密钥解密得原文。

PGP可用于电子邮件，也可以用于文件存储。采用了杂合算法，包括IDEA、RSA、MD5、ZIP数据压缩算法。
PGP承认两种不同的证书格式：PGP证书和X.509证书。
PGP证书包含PGP版本号、证书持有者的公钥、证书持有者的信息、证书拥有者的数字签名、证书的有效期、密钥首选的对称加密算法。
X.509证书包含证书版本、证书的序列号、签名算法标识、证书有效期、以下数据：证书发行商名字、证书主体名、主体公钥信息、发布者的数字签名。

例题：要求邮件以加密方式传输，邮件最大附件内容可达500MB，发送者不可抵赖，若邮件被第三方截获，第三方无法篡改。（K是对称密钥）

7 各个网络层次的安全保障

8 网络安全

9 防火墙

数据结构与算法基础

1 数组

例题：已知5行5列的二维数组a中的各元素占两个字节,求元素a[2][3]按行优先存储的存储地址？
$$
a+(25+3)2=a+26
$$

2 稀疏矩阵

公式法

如上图
代入法

代入值，排除错误答案

例如：

A[0][0]应放入M[1]中，将i=0，j=0代入下列选项

A：M[1] B：M[0] C：M[0] D：M[1]

故B、C为错误答案，排除B、C选项

A[1][0]应放入M[2]中，将i=1，j=0代入下列选项

A：M[2] D：M[1]

故D为错误答案，排除D选项

所以答案为A

3 数据结构的定义

数据结构的概念
数据逻辑结构
- 线性结构
- 非线性结构

4 线性表的定义

线性表的概念

（a₁,a₂,…,a_n）
线性表常见的两种存储结构
- 顺序存储结构
  - 顺序表
- 链式存储结构
  - 链表

5 顺序存储与链式存储对比

6 队列和栈

队列：先进先出

栈：先进后出

例题：元素按照a、b、c的次序进入栈，请尝试写出其所有可能的出栈序列。

a、b、c

b、a、c

b、c、a

c、b、a

==D==

解析：

A（全由左端输入）

B（e1、e2由左端输入，e3由右端输入，e4由左端输入）

C（e1由左端输入，e2由右端输入，e3、e4由左端输入）

7 广义表

广义表是n个表元素组成的有限序列，是线性表的推广。
通常用递归的形式进行定义，记做： LS =(a₀, a₁,… a_n)。
注：其中LS是表名，a_i是表元素，它可以是表(称做子表)，也可以是数据元素(称为原子)。其中==n是广义表的长度(也就是最外层包含的元素个数)==， n=0的广义表为空表；而递归定义的==重数就是广义表的深度，直观地说，就是定义中所含括号的重数==(原子的深度为0 ,空表的深度为1 )。

基本运算：取表头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) )，,则其长度为？深度为？

长度为3，深度为2。

例题2：有广义表LS1= (a, (b,c) , (d, e) ) ，要将其中的b字母取出，操作为？

head(head(tail(LS1)))

8 树与二叉树

结点的度（一个结点拥有的孩子结点的数量）（1结点的度为2）
树的度（所有结点中最高的度）（树的度为2）
叶子结点（没有孩子结点）（4、5、7、8）
分支结点（2、3、6）
内部结点（2、3、6）
父结点
子结点
兄弟结点
层次

8.1二叉树遍历

前序遍历（根左右）
中序遍历（左根右）
后序遍历（左右根）
层次遍历（一层一层遍历）

图中前序遍历结果是？

1、2、4、5、7、8、3、6

图中中序遍历结果是？

4、2、7、8、5、1、3、6

图中后序遍历结果是？

4、8、7、5、2、6、3、1

图中层次遍历结果是？

1、2、3、4、5、6、7、8

8.2 反向构造二叉树

例题：由前序序列为ABHFDECG；中序序列为HBEDFAGC构造二叉树。

8.3 树转二叉树

孩子结点->左子树结点
兄弟结点->右孩子结点

8.4 查找二叉树

二叉排序树

左孩子小于根
右孩子大于根

插入结点：

若该键值结点已存在，则不再插入。如：48 。
若查找二叉树为空树，则以新结点为查找二叉树。
将要插入结点键值与插入后父结点键值比较，就能确定新结点是父结点的左子结点，还是右子结点。

删除结点：

若待删除结点是叶子结点，则直接删除。
若待删除结点只有一个子结点，则将这个子结点与待删除结点的父结点直接连接。如: 56。
若待删除的结点p有两个子结点，则在其左子树上，用中序遍历寻找关键值最大的结点s，用结点s的值代替结点p的值，然后删除节点s，节点s必属于上述①，②情况之一。如89。

8.5 最优二叉树（哈夫曼树）

需要了解的基本概念：

树的路径长度（根节点到节点之间的线段数量）
权
带权路径长度（树的路径长度*权）
树的带权路径长度

例题：假设有一组权值5，29，7，8，14，23，3，11请尝试构造哈夫曼树（树的带权路径长度最小）。

先由小到大排序：3，5，7，8，11，14，23，29

3和5构造二叉树，得8。由小到大排序：7，8，8，11，14，23，29

7和8构造二叉树，得15。由小到大排序：8，11，14，15，23，29

8和11构造二叉树，得19。由小到大排序：14，15，19，23，29

14和15构造二叉树，得29。由小到大排序：19，23，29，29

以此类推，选最小的两个值构成一个二叉树，从序列中删除这两个值。再将它两相加的值，放入序列排序，直到序列为空。

树的带权路径长度
$$
（5+3）5+74+（14+8+11）3+（29+23）2=219
$$

8.6 线索二叉树

为什么要有线索二叉树
线索二叉树的概念
线索二叉树的表示
如何将二叉树转化为线索二叉树

前序遍历：ABDEHCFGI

中序遍历：DBHEAFCGI

后序遍历：DHEBFIGCA

以前序线索二叉树为例：D的前趋节点为B，后继节点为E。

8.7 平衡二叉树

平衡二叉树的提出原因
平衡二叉树的定义
- 任意结点的左右子树深度相差不超过1
- 每结点的平衡度只能为-1、0或1
平衡树的建立过程
动态调平衡问题

例题：对数列{1,5,7,9,8,39,73,88}构造排序二叉树，可以构造出多棵形式不同的排序二叉树。

最后一个为平衡二叉树

9 图

完全图

在无向图中，若每对顶点之间都有一条边相连，则称该图为完全图( complete graph)
在有向图中，若每对顶点之间都有二条有向边相互连接，则称该图为完全图

9.1 图的存储-邻接矩阵

用一个n阶方阵R来存放图中各结点的关联信息，其矩阵元素Rij定义为：

9.2 图的存储-邻接表

首先把每个顶点的邻接顶点用链表示出来，然后用一个一维数组来顺序存储上面每个链表的头指针。

9.3 图的遍历

如果从邻接表的存储来看，从V0开始

深度优先遍历：04671253

广度优先遍历：04316275

9.4 拓扑排序

我们把用有向边表示活动之间开始的先后关系。这种有向图称为用顶点表示活动网络，简称AOV网络。

上图的拓朴序列有： 02143567 , 01243657 , 02143657 , 01243567

9.5 最小生成树-Prim算法

此算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。

9.5 最小生成树-Kruskal算法

此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。

10 算法基础

有穷性：执行有穷步之后结束。
确定性：算法中每一条指令都必须有确切的含义,不能含糊不清。
输入(>=0)
输出(>=1)
有效性：算法的每个步骤都能有效执行并能得到确定的结果。例如a=0 ， b/a就无效

10.1 算法的复杂度

时间复杂度是指程序运行从开始到结束所需要的时间。通常分析时间复杂度的方法是从算法中选取一种对于所研究的问题来说是基本运算的操作，以该操作重复执行的次数作为算法的时间度量。一般来说，算法中原操作重复执行的次数是规模n的某个函数T(n)。由于许多情况下要精确计算T(n)是困难的，因此引入了渐进时间复杂度在数量上估计一个算法的执行时间。其定义如下:
如果存在两个常数c和m，对于所有的n ,当n>=m时有f(n)<=g(n) ，则有f(n)= O(g(n))。也就是说，随着n的增大，f(n)渐进地不大于g(n)。例如，一个程序的实际执行时间为T(n)= 3n³+2n²+n ,则T(n)=O(n³)。
常见的对算法执行所需时间的度量:
0(1)<0(log₂n)<o(n)<O(nlog₂n)<O(n₂)<O(n₃)<0(2ⁿ)

空间复杂度是指对一个算法在运行过程中临时占用存储空间大小的度量。一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小。

11 查找

11.1顺序查找

顺序查找的思想：将待查找的关键字为key的元素从头到尾与表中元素进行比较，如果中间存在关键字为key的元素，则返回成功；否则，则查找失败。

时间复杂度：O(n)

11.2 二分查找

时间复杂度：O(log₂n)

查找的序列有两个要求：

一是该序列必须是有序的（即该序列中的所有元素都是按照大小关系排好序的，升序和降序都可以）
二是该序列必须是顺序存储的。

例题：请给出在含有12个元素的有序表{1, 4, 10, 16, 17, 18, 23, 29,33,40,50, 51}中二分查找关键字17的过程。

11.3 散列表

散列表查找的基本思想是：已知关键字集合U，最大关键字为m，设计一个函数Hash，它以关键字为自变量，关键字的存储地址为因变量，将关键字映射到一个有限的、地址连续的区间T[0..n-1](n<<m)中,这个区间就称为散列表，散列查找中使用的转换函数称为散列函数。

冲突时的办法：

线性探测法
伪随机数法

例题：记录关键码为( 38,12, 17,9)，取m=10 (存储空间为10)， p=5 ，散列函数h=key%p。

12 排序

排序的概念
- 稳定与不稳定排序
  
  稳定排序：排序前后两个相等的数相对位置不变，则算法稳定。
  非稳定排序：排序前后两个相等的数相对位置发生了变化，则算法不稳定。
  
  选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。
- 内排序与外排序
  
  内排序：指在排序期间数据对象全部存放在内存的排序。
  外排序：指在排序期间全部对象太多，不能同时存放在内存中，必须根据排序过程的要求，不断在内，外存间移动的排序。
排列方法分类
- 插入类排序
  - 直接插入排序
  - 希尔排序
- 交换类排序
  - 冒泡排序
  - 快速排序
- 选择类排序
  - 简单选择排序
  - 堆排序
- 归并排序
- 基数排序

12.1 直接插入排序

直接插入排序：即当插入第i个记录时，R1, R2, … R;均已排好序，因此，将第i个记录R_i依次与R_i-1，…. R₂, R₁进行比较,找到合适的位置插入。它简单明了，但速度很慢。

12.2 希尔排序

希尔（Shell）排序：先取一个小于n的整数d₁作为第一个增量,把文件的全部记录分成d₁个组。所有距离为d₁的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d₂ <d₁，重复上述的分组和排序，直至所取的增量d_t=1(d_t<d_t-1<O<d₂<d₁)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。

12.3 直接选择排序

直接选择排序的过程是，首先在所有记录中选出排序码最小的记录，把它与第1个记录交换，然后在其余的记录内选出排序码最小的记录，与第2个记录交…..依次类推，直到所有记录排完为止。

12.4 堆排序

设有n个元素的序列{K₁, K₂, .. K_n}，当且仅当满足下述关系之时，称之为堆。

k_i≤k_2i且k_i≤k_2i+1;
k_i>=k_2i且k_i>=k_2i+1;
其中(1)称为小顶堆，(2)称为大顶堆

堆排序的基本思想为：先将序列建立堆，然后输出堆顶元素，再将剩下的序列建立堆，然后再输出堆顶元素，依此类推，直到所有元素均输出为止，此时元素输出的序列就是一个有序序列。

堆排序的算法步骤如下(以大顶堆为例) ：

初始时将顺序表R[1..n]中元素建立为一个大顶堆，堆顶位于R[1]待序区为R[1..n]。
循环执行步骤3~步骤4 ,共n-1次。
假设为第i次运行，则待序区为R[1..n-i+1] ，将堆顶元素R[1]与待序区尾元素R[n-i+1]交换,此时顶点元素被输出，新的待序区为R[1..n-i]。
待序区对应的堆已经被破坏，将之重新调整为大顶堆。

假设有数组A= {1,3, 4, 5, 7, 2, 6, 8, 0},初建堆过程如下：

将顺序表R{80，60，16， 50，45，10，15，30，40，20}进行堆排序。

12.5 冒泡排序

冒泡排序的基本思想是：通过相邻元素之间的比较和交换，将排序码较小的元素逐渐从底部移向顶部。由于整个排序的过程就像水底下的气泡一样逐渐向上冒，因此称为冒泡算法。

12.6 快速排序

快速排序采用的是分治法，其基本思想是将原问题分解成若干个规模更小但结构与原问题相似的子问题。通过递归地解决这些子问题，然后再将这些子问题的解组合成原问题的解。

快速排序通常包括两个步骤：

在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录都分成两组，第1组都小于该数，第2组都大于该数，如图所示。
采用相同的方法对左、右两组分别进行排序,直到所有记录都排到相应的位置为止。

12.7 归并排序

归并也称为合并，是将两个或两个以上的有序子表合并成一个新的有序表。若将两个有序表合并成一个有序表，则称为二路合并。合并的过程是：比较A[i]和A[j]的排序码大小,若A[i]的排序码小于等于A[j]的排序码，则将第个有序表中的元素A[i]复制到R[k]中，并令i和k分别加1；如此循环下去，直到其中-一个有序表比较和复制完，然后再将另一个有序表的剩余元素复制到R中。

12.8 基数排序

基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。基数排序不是基于关键字比较的排序方法，它适合于元素很多而关键字较少的序列。基数的选择和关键字的分解是根据关键字的类型来决定的，例如关键字是十进制数，则按个位、十位来分解。

12.9 排序时间复杂度、空间复杂度和稳定性

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

1 编译过程

2 文法定义

一个形式文法是一个有序四元组G=(V, T, S, P)，其中：

V：非终结符。不是语言组成部分，不是最终结果，可理解为占位符。
T：终结符。是语言的组成部分，是最终结果。$V\cap T=0$
S：起始符。是语言的开始符号。
P：产生式。用终结符替代非终结符的规则。形如a→β

正则闭包： $A+=A^1∪A^2∪A^3U…∪A^n∪… $(也就是所有幂的组合)。
闭包:：A*=A⁰UA₊ (在正则闭包的基础上，加上A⁰= {$\varepsilon$} )。

3 语法推导树

一棵语法树应具有以下特征：

每个结点都有一个标记，此标记是V的一个符号
根的标记是S
若一结点n至少有一个它自己除外的子孙，并且有标记A，则A肯定在V_n中:
如果结点n的直接子孙，从左到右的次序是结点$n_1,n_2,..n_k$其标记分别是：$A_1,A_2,…,A_k$,那么A→$A_1,A_2…A_k$一定是P中的一个产生式。

例题：文法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

4 有限自动机

5 正规式

==D C==

A：S→aA→abS→abaA→ababS→ababaA→ababab

B：S→bB→baS→babB→babaS→bababB→bababa

C：S→aA→abS→abbB→abbaS→abbaaA→abbaab

例题：下图所示为一个有限自动机(其中，A是初态、C是终态)，该自动机可识别(1)。

解析：如果选项路线可以使初态（A）到达终态（C），即为正确。故选C。

==D==

6 函数调用-传值与传址

7 各种程序语言特点

Fortran语言(科学计算,执行效率高)
Pascal语言(为教学而开发的,表达能力强, Delphi )
C语言(指针操作能力强，高效)
Lisp语言(函数式程序语言,符号处理，人工智能)
C++语言(面向对象，高效)
Java语言(面向对象,中间代码，跨平台)
C#语言(面向对象,中间代码,.Net)
Prolog语言(逻辑推理,简洁性,表达能力,数据库和专家系统)

法律法规

从所涉及的法律法规角度：

著作权法
计算机软件保护条例
商标法
专利法

从试题考点分布的角度：

保护期限
知识产权人确定
侵权判断

知识产权：

著作权及邻接权
专利权
工业品外观设计权
商标权
地理标志权
集成电路布图设计权

1 保护期限

2 知识产权人确定

3 侵权判定

中国公民、法人或者其他组织的作品，不论是否发表，都享有著作权。
开发软件所用的思想、处理过程、操作方法或者数学概念不受保护。

著作权法不适用于下列情形：
法律、法规，国家机关的决议、决定、命令和其他具有立法、行政、司法性质的文件，及其官方正式译文。
时事新闻。
历法、通用数表、通用表格和公式。

4 标准化基础知识

4.1标准的分类

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

4.2 标准的编号

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

多媒体基础

1 音频相关概念

2 图像相关概念

RGB：彩色显示器

YUV：电视

CMY：印刷

3 媒体的种类

感觉媒体：指人们接触信息的感觉形式。如:视觉、听觉、触觉、嗅觉和味觉等。
表示媒体：指信息的表示形式。如:文字、图形、图像、动画、音频和视频等。
显示媒体(表现媒体)：表现和获取信息的物理设备（输入输出设备）。如：输入显示媒体键盘、鼠标和麦克风等；输出显示媒体显示器、打印机和音箱等。
存储媒体：存储数据的物理设备，如磁盘、光盘和内存等。
传输媒体：传输数据的物理载体，如电缆、光缆和交换设备等。

4 多媒体相关计算问题

4.1 图像容量计算

例题：某数码相机内置128MB的存储空间，拍摄分辨率设定为1600x1200像素，颜色深度为24位，若不采用压缩存储技术，使用内部存储器最多可以存储(D)张照片。
A.12 B.22 C.13 ==D.23==
$$
1600120024/8==5760000\
5760000/1024/1024=5.493\
128/5.493=23.3
$$

4.2 音频容量计算

$$
容量=采样频率(Hz) 量化/采样位数(位) 声道数/8
$$

例题：CD上声音的采样频率为44.1kHz，样本精度为16bit，双声道立体声，那么其未经压缩
的数据传输率为（C）
A.88.2kb/s B .705.6kb/s ==C .1411.2kb/s== D .1536.0kb/s
$$
44.4k162=1411.2
$$
要注意单位，k=1000，K=1024。

4.3 视频容量计算

$$
容量=每帧图像容量(Byte)每秒帧数时间+音频容量*时间
$$

例题：若视频图像每帧的数据量为6.4MB，帧速率为30帧/秒，则显示10秒的视频信息，其原始数据量为（D） MB.
A. 64 B.192 C.640 ==D.1920==
$$
6.43010=1920
$$

5 常见多媒体标准

6 数据压缩基础

空间冗余(几何冗余)
时间冗余
视觉冗余
信息熵冗余
结构冗余
知识冗余

7 有损压缩与无损压缩

无损压缩编码法( Lossless compression coding)，也称冗余压缩法或熵编码法。

有损压缩编码法( Loss compression coding )，也称为熵压缩法。

软件工程

1 软件开发模型

1.1 瀑布模型（SDLC）

结构化开发，需求明确、二次开发。

1.2 其他经典模型

需求不明确

1.3 增量模型与螺旋模型

1.4 V模型、喷泉模型与RAD

喷泉模型：面向对象模型

1.5 构件组装模型（CBSD）

1.6 敏捷开发方法

1.7 信息系统开发方法

2 需求开发

3 结构化设计

4 软件测试

尽早、不断的进行测试
程序员避免测试自己设计的程序
既要选择有效、合理的数据，也要选择无效、不合理的数据
修改后应进行回归测试
尚未发现的错误数量与该程序已发现错误数成正比

动态测试：

黑盒测试法
白盒测试法
灰盒测试法

静态测试：

桌前检查
代码走查
代码审查（交叉检查）

4.1 测试用例设计

4.2 测试阶段

4.3 McCabe复杂度

计算有向图G的环路复杂度公式为：==V(G)=m-n+2==
说明：其中V(G)是有向图G中的环路个数，m是G中的有向弧数，n是G中的节点数。

5 系统运行与维护

软件维护是生命周期的一个完整部分。可以将软件维护定义为需要提供软件支持的全部活动，这些活动包括在交付前完成的活动，以及交付后完成的活动。交付前完成的活动包括交付后运行的计划和维护计划等；交付后的活动包括软件修改、培训帮助资料等。

可维护性：

易分析性
易改变性
稳定性
易测试性

维护类型：

改正性维护(25%)
适应性维护(20%)
完善性维护(50%)
预防性维护(5%)

6 软件过程改进-CMMI

7 项目管理

九大知识领域：

范围管理
时间管理
成本管理
质量管理
人力资源管理
沟通管理
风险管理
采购管理
整体管理

例题：进度安排的常用图形描述方法有Gantt图和PERT图。Gantt图不能清晰地描述（D）; PERT图可以给出哪些任务完成后才能开始另一些任务。下图所示的PERT图中,事件6的最晚开始时间是（C）。

（1）A.每个任务从何时开始 B.每个任务到何时结束
C.每个任务的进展情况 ==D.各任务之间的依赖关系==
（2） A.0 B.3 ==C.10== D.11

先正推求出最终项目的最早完成时间。事件9最早完成时间为15。

再逆推求出指定项目的最晚开始时间。事件6最晚开始时间为10。（15-4-1=10）

风险曝光度(Risk Exposure) ：计算方法是风险出现的概率乘以风险可能造成的损失。
假设正在开发的软件项目可能存在一个未被发现的错误，而这个错误出现的概率是0.5%，给公司造成的损失将是1000000元，那么这个错误的风险曝光度就应为1000000x0.5% = 5000元。

需求工程

1 面向对象的基本概念

对象
类(实体类、边界类、控制类)
抽象
封装
继承与泛化
多态
接口
消息
组件
模式和复用

2 设计原则

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

3 UML

4 设计模式

架构模式：软件设计中的高层决策，例如C/S结构就属于架构模式，架构模式反映了开发软件系统过程中所作的基本设计决策
设计模式：主要关注软件系统的设计，与具体的实现语言无关
惯用法：是最低层的模式，关注软件系统的设计与实现，实现时通过某种特定的程序设计语言来描述构件与构件之间的关系。每种编程语言都有它自己特定的模式，即语言的惯用法。例如引用-计数就是C+ +语言中的一种惯用法

4.1 设计模式的分类

4.2 创建型模式

4.3 结构性模式

4.4 行为性

数据流图

1 数据流图基本概念

2 数据字典

3 数据平衡原则

父图与子图之间的平衡

顶层数据流图：

0层数据流图：

子图内平衡

数据库设计

1 数据库设计过程

2 ER模型

2.1 实体间联系类型

2.2 E-R图向关系模型的转换

转换的基本原则是：实体和联系分别转换成关系，属性则转换成相应关系的属性。

一对一联系
一对多联系
多对多联系
多元联系

3 答题技巧

详细分析试题说明
熟练掌握基本知识

UML建模

1 用例图

包含关系\（必须使用的）
扩展关系\（不必须使用的）
泛化关系

2 类图与对象图

2.1 填类名，方法名，属性名

2.2 多重度

2.3 关系

依赖关系
泛化关系
关联关系
- 聚合关系
- 组合关系
实现关系

2.3 顺序图

2.4活动图

2.5 状态图

2.6 通信图

2.7 构件图

数据结构及算法应用

1 分治法

对于一个规模为n的向题，若该问题可以容易地解决（比如说规模n较小）则直接解决；否则将其分解为k个规模較小的子问题，这些子向题互相独立目与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

该问题的规模缩小到一定的程度就可以容易地解决
该问题可以分解为若干个规模较小的相同问题
利用该问题分解出的子问题的解可以合并为该问题的解
该问题所分解出的各个子问题是相互独立的
分解
解决
合并

1.1递归技术

递归，就是在运行的过程中调用自己。

1.2 二分查找

2 回溯法

回溯法是一种选优搜素法，按选优条件向前搜素，以达到目标。但当搜索到某步时，发现原先选择井不优或达不到目标，就退回一步重新选择。这种走不通就退回再走的技术就是回溯法。

3 贪心法

总是做出在当前来说是最好的选择，而并不从整体上加以考虑，它所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不必为了号找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解，但得不到最优解。

4 动态规划法

在求解问题中，对于每一步决策，列出各种可能的局部解，再依据某种判定条件，舍奔那些肯定不能得到最优解的局部解，在每一步都绍过筛选，以每一步都是最优解来保证全局是最优解。

例题1

j = 0;
b[j] = b[j] + s[i];
temp = min;
b[m] = b[m] + temp;

贪心法、贪心法、O（n²）、O（n²）

最先适宜策略

4、2、3
7、2
5、4
3、6
2

最优适宜策略

4 、2、4
7、3
5、2、3
6、2

否

例题2

分治

T（n）=2T（n/2）+ O（n） O（nlog(n)） O（n）

n1 + n2

面向对象程序设计

1 C++及Java语法要点

2 设计模式程序实现

例题1

1
2
3

(1)void Insert(Department department)
(2)Department GetDepartment(int id)
(3)implements IDepartment

1
2
3

(4)implements IDepartment
(5)interface IFactory
(6)IDepartment CreateDepartment

例题2

(1)interface
(2)void drawLine(double x1,double y1,double x2,double y2)
(3)void drawCircle(double x,double y,double r)
(4)DP1.draw_a_circle(x,y,r)
(5)DP2.draw_a_circle(x,y,r)
(6)abstract public void draw()