考试占比

报名

报名条件：凡遵守中华人民共和国宪法和各项法律，恪守职业道德，具有一定计算机技术应用能力的人员，均可报考软件设计师。也就是说不限制考生的学历、专业、工作经验及年限、年龄等。【点击查看软件设计师报名条件详解】

报名时间：上半年一般在==3月份报名==，下半年在==8月份报名==，各地报名具体时间不一样，考生届时需要多留意当地报名时间。【点击查看各地软件设计师报名时间】

考试时间：上半年一般是==5月份开考==，下半年一般是==11月份开考==
上午基础知识科目考试为9:00-11:30，下午应用技术科目考试时间为14:00-16:30

报名方式：考生自己在当地规定时间内进入软考办官网，即中国计算机技术职业资格网的报名入口进行报名。【点击查看软件设计师报名入口】

报名费用：各地不同，一般在100-160元之间，具体以当地为准，其中辽宁不收取报名费(大连考区除外)【点击查看报名费用】

成绩查询：一般是考后40天左右公布成绩，成绩公布后大家可以在软考办官网进行查询

考试证书：两科均通过分数线即可领取证书，各地领证时间不同，上半年证书一般集中在9-10月份发放，下半年证书一般集中在次年2-3月份发放。错过证书领取时间，证书由发证机构代为保管，考生可咨询相关领取事宜，但是超过5年没领取的证书将被销毁。软件设计师证书可以在中国计算机技术职业资格网和中国人事考试考试网的“证书查询”栏目进行查询。【点击查看详情】

进制转换

二进制转八进制 八进制转十六进制
二进制转十进制 (分权相乘 整数AND小数)
十进制转二进制 (短除法)

原码 反码 补码 转码

负数

• 原码(数字首 负数为1 正数为0)

  • +9 = **0**000 1001
  • -9 = **1**000 1001
  • Min → 1111 1111 = —127
  • Max → 0111 1111 = +127
  • 缺点：0有两种表示方式：+0=00000000 -0=10000000[零的二义性给机器判断带来了麻烦] ****
  • 原码的数值0有两种表示方式 +0 -0

  比如：1-2=-3 → ∵ +1+(-2) → +1 -> 0000 000$1_原$ ; -2 -> 1000 001$0_原$

  ∴ 0000 0001 + 1000 0010 = 1000 001$1_原$ = -3

  为了解决这个问题，科学家使用补码

  -33的原码是 *1010 0001* 反码是 1101 1110

• 反码

  • 原码的符号位不变，其余位取相反得到
  • 反码存在的意义就是为了由原码计算补码方便

• 补码

  • 反码+1得到
  • 优点

  1、在补码表示中，0有唯一的编码 0 = 0000 0000

  2、用10000000表示 -128，比原码可多表示一个编码

  3、利用补码可以方便地进行运算

正数

• 原码=反码=补码

☆☆ 正数：正数的原码、反码、补码都一样 ☆☆

☆☆ 负数：负数将原码的符号位保持不变，数值位各位取反再末位加1，就可以将原码转换为补码 ☆☆

@@ 计算机中常采用原码、反码、补码和移码表示数据，其中±0编码相同的是补码和移码[这里一定要考虑正数和负数]

@@ 负数-5在计算机中的补码是 ？

直接从原码变补码、补码变原码 口诀：从右向左复制，直到有1被赋值 其余取相反(符号位 => 第一位不变)

• 移码

一般运用于浮点运算中的阶码，在补码的基础上把首位取反

	数值1 (正数前三都相同)	数值-1
原码	0000 0001	1000 0001
反码	0000 0001	1111 1110
补码	0000 0001	1111 1111
移码	1000 0001	0111 1111

表示范围

	整数
原码	-[2$^{(n-1)}-1$]  ~  2$^{(n-1)}-1$
反码	-[2$^{(n-1)}-1$]  ~  2$^{(n-1)}-1$
补码	-[2$^{(n-1)}$]   ~   2$^{(n-1)}-1$ [少占用一个+0 -0]

浮点数运算

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

步骤：对阶 → 尾数计算 → 结果格式化

小阶数朝着大阶数化
1000 + 119 => 1.0 × 1$0^3$ + 1.19 × 1$0^2$ => 1.0 × 1$0^3$ + 0.119 × 1$0^3$ = 1.119 × 1$0^3$

结果格式化：如果答案是 0.1119 × 1$0^3$ 把结果变成 1.119 × 1$0^2$
确保尾数的第一个位置不能是0, 也不能是1以上的；最多是一位

计算机结构

==硬件 = 主机 + 外设==

==主机 = CPU (CPU = 运算器 + 控制器) + 内存==

==外设 = 输入设备 + 输出设备 + 外存==

==存储器 = 内存 + 外存==

运算器：
① 算术逻辑单元ALU
② 累加寄存器AC
③ 数据缓冲寄存器DR [对内存储器读取的时候 有暂存的作用]
④ 状态条件寄存器PSW [存储运算过程中的标志位状态信息]

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

计算机体系结构分类 — Flynn

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

CISC与RISC

指令系统类型	指令	寻址方式	实现方式	其他
CISC(复杂)	数量多，使用频率差别大，可变长格式	支持多种	微程序控制技术(微码)	研制周期长
RISC(精简)主流	数量少，使用频率接近，定长格式，大部分微单周期指令 操作寄存器，只有Load/Store操作内存	支持方式少	大量增加了通用寄存器(增加速度)； 硬布线逻辑控制为主 适合采用流水线	优化编译，有效支持高级语言

CISC(Complex Instruction Set Computer, 复杂指令集计算机) 进一步增强原有指令的功能，用更为复杂的新指令取代原先由软件子程序完成的功能，实现软件功能的硬化，导致机器的指令系统越来越庞大而复杂。

RISC(Reduced Instruction Set Computer, 精简指令集计算机) 通过减少指令总数和简化指令功能，降低硬件设计的复杂度，使指令能单周期执行，并通过优化编译，提高指令的执行速度，采用硬线控制逻辑，优化编译程序。

流水线(计算)[运用于工业 可节省时间]

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

执行一条指令分为 取指 → 分析 → 执行

未使用流水线执行指令情况

1			2			3
	1			2			3
		1			2			3

使用流水线执行指令情况

1	2	3
	1	2	3
		1	2	3

• 流水线周期取指+分析+执行为运算时间最长的一段
• 流水线运算时间计算公式为：
  ①条指令运算总时长 + (指令条数-1) × 流水线周期
  ① 理论公式：**(t1 + t2 +…+ tk) + (n - 1) × △t**
  ② 实践公式：**(k + n-1) × △t**

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

取指	1	2	3	.	.	n
分析		1	2	3	.	.	n
执行			1	2	3	.	.	n

答：1.周期最长的时间是2ns，所以流水线周期是2ns每一个流水线的周期就会完成一条指令的运行
2.(2+2+1) + (100-1) × 2 = 203理论公式①计算 / [3分三段+ (100 - 1) ] × 2 = 204实践公式②计算

• 流水线吞吐率计算
  是指在单位时间内流水线所完成的任务数量或输出的结果数量。

  流水线吞吐率基本公式：TP = $\frac{指令条数}{流水线运算时间}$
  流水线最大吞吐率：TPmax = Limn→∞$\frac{n}{(k+n-1)△t}$=$\frac{1}{△t}$

==根据上述题目== 可以算出 TP = $\frac{100}{203}$; TPmax = $\frac{1}{2}$

• 流水线加速度比
  是指完成同样一批任务，不使用流水线所用的时间与使用流水线所用的时间之比称为流水线的加速比
  S = $\frac{不使用流水线执行时间}{使用流水线执行时间}$

==根据上述题目==
不使用流水线执行时间：(2+2+1) × 100 = 500ns
使用流水线执行时间：203ns
S = $\frac{500}{203}$

• 流水线的效率
  是指流水线的设备利用率。在时空图上，流水线的效率定义为n个任务占用的时空区与k个流水段总的时空区之比
  E = $\frac{n个任务占用的时空区}{k个流水段总的时空区}$ = $\frac{T0}{KTk}$

入 → S1(△t) → S2(△t) → S3(△t) → S4(3△t) → 出

↑ 此方法效率不高，因为在S4所需要的时间太长，导致其他的会遭到空闲状态

横轴是时间△t；纵轴是空间

S4				1	1	1	2	2	2	3	3	3	4	4	4
S3			1			2			3			4
S2		1			2			3			4
S1	1			2			3			4

n个任务占用的时空区：(△t + △t + △t + 3△t) × 4
k个流水段总的时空区：15△t × 4
E = $\frac{(△t + △t + △t + 3△t) × 4}{15△t × 4}$

层次化存储结构

容量最下层的最大 向上依次递减

Cache — 概念

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

如果以h代表对Cache的访问命中率，t1表示Cache的周期时间，t2表示主存储器周期时间，以读操作为例，使用”Cache + 主存储器“的系统的平均周期为t3，则 t3 = h × t1 + (1 - h) × t2，其中(1-h)又称为失效率(未命中率)
若h=95%, t1=1ns, t2=1ms=1000ns ===> t3 = 1ns × 95% + (1 - 95%) × 1000ns = 50.95ns

CPU在读取数据中首先对Cache中读取，如果读到了则表示对该数据的命中，如果Cache中没有我们需要的数据，CPU会在内存里去调

局部性原理

时间局部性
空间局部性(适用于数组)
工作集理论：工作集是进程运行时被频繁访问的页面集合短时间不被替换成cache

int i, s = 0;  ==>  全局变量直接调用Cache
for(i = 1; i < 1000; i++)   ==> 在内存中循环100w次
    for(j = 1; j < 1000; j++)
        s+=j;
cout << s << end;

内存+外存

• 内存

  • ROMBIOS 只读存储器
    ROM-Read Only Memory只读存储器。断电后信息不丢失，如计算机启动用的BIOS芯片。
    MROM(Mask ROM, 掩模式ROM)
    PROM 可编程只读存储器
    EPROM 可擦写可编程只读存储器
    EEPROM 点可擦可编程只读存储器
    Flash Memory 闪存 ≈ SSD
  • RAM随机存储器
    DRAM(动态存储器) 不断刷新 速度比SRAM慢 价格低 常用于主存储器
    SRAM(静态存储器 ) 不需刷新 速度比DRAM快 价格贵 cache属于SRAM
    CPU → Cache → 内存 → 外存

• 外存

  • 硬盘：机械硬盘HDD(SATA、IDE、SCSI接口) 固态硬盘SSD(SATA接口)
  • 光盘：CD/VCD：650MB、CD-ROM(只读光盘)、CD-R(一次性写入、永久读)、CD-RW(可重复擦写光盘)
    DVD：4.7GB、DVD-ROM、DVD-R、DVD-RW

主存 — 编址

8 × 4 位的存储器 ==> 8个地址空间，每一个存储空间存储了4个bit位的信息

000 这一存储空间	存放了4个	bit的	信息容量
001
010
011
100
101
110
111

@@ 内存地址从AC000H到C7FFFH，共有 1C000/ $2^{10}$=112 K个地址单位
如果该内存地址按字(16bit)编址，由28片存储器芯片构成。已知构成此内存的芯片每片有16K个内存单元，则该芯片每个存储单元存储 4 位

原理是后面地址-前面地址+1； C7FFFH + 1 - AC000H = 1C000H
K = $2^{10}$B ==> 共有 1C000/ $2^{10}$=112K 个地址单位

用一系列的芯片组成这样 112K×16bit位 的内存块，需要28个芯片，每个芯片是16K个存储单元**$\frac{112K×16}{28×16K×a}$ = 1**，比值是1因为用这些芯片去成立这个空间。解得a=4

磁盘结构与参数

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

• 硬盘

机械硬盘(HDD)：存储介质 磁介质；参数：[主慈善]**磁(道)头数、柱面数、扇区(**硬盘的基本读写单位，大小是512B)；

硬盘容量 = 磁头数 * 柱面数 * 扇区数 * 512B；
性能指标：存储容量、转速、访问时间、传输速率、缓存等；
[硬盘内部结构按扇区、磁道、柱面的格式组织存储信息]

接口：SATA、IDE、SCSI、光纤通道

固态硬盘(SSD)：存储介质(Flash Memory闪存) 接口 SATA等

旋转的延迟时间是磁盘转一圈的时间

@@ 假设某磁盘的每个磁道划分成11个物理块，每块存放1个逻辑记录。逻辑记录R0，R1，…… ，R9，R10存放在同一个磁道上，记录的存放顺序如下表所示：

物理块	1	2	3	4	5	6	7	8	9	10	11
逻辑记录	R1	R2	R3	R4	R5	R6	R7	R8	R9	R10	R11

如果磁盘的旋转周期为33ms，磁头当前处在R0的开始处。若系统使用单缓存区顺序处理这些记录，每个记录处理时间为3ms，则处理这11个记录的最长时间为366ms；若对信息存储进行优化分布后，处理11个记录的最少时间为66ms

一圈11个记录 转一圈33ms，则每个记录旋转的时间是3ms，读取一个记录的时间是3ms；告诉单缓存区，转到R0时处理R0需要3ms因为是单缓存区，不能同时进行，必须等R0处理完成才能进入下一个任务处理[处理的途中磁盘仍在转动,磁头仍在向前]，而一个记录正好也需要3ms，所以当处理完R0时，磁头已经到达了R2的位置，所以要再转一圈才能去处理R1，以此类推，除了最后一个R10就可以找到规律，把R0处理完，再等到指针走到R1的位置的时候转了一圈加一条记录的时间 = [33+3] = 36ms，以此类推R0 ~ R9都是这样处理的，所以处理R0~R9共需要 36ms × 10，最后一个R10，把它读取出来3ms，再处理完3ms。综上一共需要 (33+3)×10+6 = 366ms；

优化处理：当处理完R0的时候，磁头正好下一位置是R1，而不用再去等它转动一个周期后；优化后的图为右侧图二！旋转+处理=(3ms+3ms)×10个=66ms

总线

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

内部总线

是指微机内部各个外围的芯片与处理器之间的总线 属于芯片级别

系统总线

是指各个插件板和系统板之间的总线 属于插件版级别

• ==数据总线(DB)==：用来传输数据信息 双向传输
• ==地址总线(AB)==：用来传输数据地址 单向传输

地址总线的位数决定了CPU可直接寻址的内存空间大小

若地址总线为n位，寻址空间为2的n次方个B，如微机的地址总线为16位，则最大寻址空间为64KB

• ==控制总线(CB)==：用来传输控制信号

外部总线

是指微机和外部设备的总线

系统可靠性分析 — 串联系统与并联系统

【串联】输入 → R1 → R2 → … → Rn → 输出
R = R1 × R2 × … × Rn
λ = λ1 + λ2 + … + λn

【并联】

     →R1

输入 →R2 → 输出
→Rn

R = 1 - (1 - R1) × (1 - R2) × … × (1 - Rn)
**μ = **$\frac{1}{\frac{1}{λ}\quad\sum_{j=1}^{n}\frac{1}{j}}$

【模冗余系统与混合系统】

​ →R1 →↓

输入 →R2 → 表决器 → 输出

​ →Rm →↑

**R = **$\quad\sum_{j=1}^{n}{C{^j}{_m}×R{0}{^i}(1-R{0})^{m-i}}$

【串并联】

​ |— R —| |—R—|
—R —|— R —|—— | |——
​ |— R —| |—R—|

R×(1-(1-R$)^3$×(1-(1-R$)^2$))

差错控制

什么是码距？

一个编码系统的码距是整个编码系统中任意(所有)两个码字的最小距离
例：
若用1位长度的二进制编码。若A=1，B=0。这样A,B之间的最小码距为1
若用2位长度的二进制编码。若以A=11，B=00为例，A,B之间的最小码距为2
若用3位长度的二进制编码。可选用111,000作为合法编码。A,B之间的最小码距为3[检错可以进一步提高码距]

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

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

校验码 — 循环冗余校验码CRC

什么是模2除法？(异或运算相同为0,不同为1)

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

加0，多项式阶数为r(等于多项式位数减1)，则加r个0
eg：要发送数据1101011011，采用CRC校验，生成多项式10011(加四个0)，则最终发送数据为？
11010110110000 ÷ 10011 => 采用异或运算
[待发送的信息补零 ÷ 多项式系数]
仅仅采用了CRC检验，如果检测到一个错误，则丢弃帧。缺重传机制，数据链路层的传输还不是可靠的传输

CRC编码 = 原始报文 后面补上 CRC校验码
注意：最后得到的位数必然是校验码位数，不够的需要补0
这里得到的结果是11，但是需要凑位数，所以校验码=0011

校验码 — 海明校验码

求信息1011的海明码[$2^r$ ≥ 4信息位 + r校验位 + 1全部正确]
①n+r个数 有 $2^r$ ≥ n信息位 + r校验位 + 1全部正确个错
确定校验码为3位：$2^3$ ≥ 4 + 3 + 1；分别放在$2^0$=1、$2^1$=2、$2^2$=4 位
[校验位/位置 $2^n$；奇偶校验(0√ 1×)；检验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$⊕$I_3$⊕$I_2$
$r_1$=$I_4$⊕$I_3$⊕$I_1$
$r_0$=$I_4$⊕$I_2$⊕$I_1$
③ 根据公式得r2=0，r1=0，r0=1
④ 将数据加入表格

7	6	5	4	3	2	1	位数
I4	I3	I2		I1			信息位
1	0	1	r2	1	r1	r0	校验位

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

@@ 求信息1010海明校验码

$2^r$ ≥ n + r+ 1 => 4+r+1=> r=3 ==> n+r=4+3=7 下列表画7列
$2^n $=$2^0$,$2^1$,$2^2$,$2^3$

①001	②010	③011	④100	⑤101	⑥110	⑦111	位数
001	010	011	100	101	110	111	二进制
P1($2^0$)	P2($2^1$)	1	P3($2^2$)	0	1	0	校验位

①001	②010	③011	④100	⑤101	⑥110	⑦111	位数
1 ↑	0 ↑	1	**1 **↑	0	1	0	校验位

P1寻找位数二进制后尾是1的 => ③⑤⑦ => 1⊕0⊕0 => 1
P2第二位有1 => ③⑥⑦ => 1⊕1⊕0 => 0
P3最高位有1 => ⑤⑥⑦ => 0⊕1⊕0 => 1
故海明码：1011010

@@ 求信息D8—D1的10101011海明校验码

$2^r$ ≥ n + r+ 1 => n=8, 解得r=4; 一共要画8+4=12列
r=4 ==> $2^n$=$2^0$,$2^1$,$2^2$,$2^3$

⑫	⑪	⑩	⑨	⑧	⑦	⑥	⑤	④	③	②	①	位数
1100	1011	1010	1001	1000	0111	0110	0101	0100	0011	0010	0001	二进制
1	0	1	0	P4($2^3$)	1	0	1	P3($2^2$)	1	P2($2^1$)	P1($2^0$)	校验位

P1 => ③⑤⑦⑨⑪ => 1⊕1⊕1⊕0⊕0 => 1
P2 => ③⑥⑦⑩⑪ => 1⊕0⊕1⊕1⊕0 => 1
P3 => ⑤⑥⑦⑫ => 1⊕0⊕1⊕1 => 1
P4 => ⑨⑩⑪⑫ => 0⊕1⊕0⊕1 => 0
故海明校验码为：101001011111

操作系统基本原理

操作系统 — 概述：

• 管理系统的硬件、软件、数据资源
• 控制程序运行
• 人机之间的接口
• 应用软件与硬件之间的接口[API接口]

操作系统 — 管理职能：

• 进程管理
  • 进程的状态
  • 前趋图
  • PV操作
  • 死锁问题
• 存储管理
  • 段页式存储
  • 页面置换算法
• 文件管理
  • 索引文件
  • 位示图
• 作业管理
• 设备管理
• 微内核操作系统
  • 虚设备与SPOOLING技术

所属范围：应用程序【语言处理程序{操作系统[计算机硬件]}】

进程管理 — 前趋图

A:绞肉 B:切葱末 C:切姜末 D:搅拌 E:包饺子
① A → B → C → D → E
② A↘
B → D → E
C↗

进程管理 — 进程的同步与互斥

互斥：千军万马过独木桥
同步：(小明步行, 小红自行车从A到B点) 速度有差异，在一定情况停下等待
互斥反义词是共享，同步反义词是异步
进程的互斥:是指当有若干个进程都要使用某一共享资源时，任何时刻最多只允许一个进程去使用该资源，其他要使用它的进程必须等待，直到该资源的占用着释放了该资源。
进程的同步:是指在并发进程之间存在这一种制约关系，一个进程依赖另一个进程的消息，当一个进程没有得到另一个进程的消息时应等待，直到消息到达才被唤醒。

进程管理 — PV操作

PV操作是一种实现进程互斥与同步的有效方法。PV操作与信号量的处理相关
P表示通过的意思，V表示释放的意思。
P操作可以看作是获得或者请求、消耗一个信号量
V操作可以看作是释放或者发送一个信号量

P操作会阻塞；
V操作会唤醒P操作；
P操作与V操作成对出现；

int f1=0; //表示进程P1是否执行完毕

main()
{
cobegin
p1();

​ coend
}

p1() {
…
v(f1);
v(f1);
}

临界资源：诸进程间需要互斥方式对其进行共享的资源，如打印机、磁带机等。
临界区：每个进程中访问临界资源的那段代码称为临界区
信号量：信号量的值与相应资源的使用情况有关。当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数。

P(S)操作：S-=1 → S<0 →T 进程队列 or →F向下进行
V(S)操作：S+=1 → S≤0 →T 进程队列 or →F向下进行

P(S)、V(S)中的S就是信号量
T–进程操作阻塞（不会往下执行）
F–继续循环操作（执行下面的内容）

单缓冲区生产者、消费者问题PV原语描述：S1初值1，S2初值0

生产者：(先执行)	消费者：
生产一个产品；	P(S2); [S2=0]
P(S1); [S1=0, S1=-1]	从缓冲区取产品;
送产品到缓冲区;	V(S1);
V(S2); [S2=1]	消费产品;

付款要双方的配合，会有同步的关系；假设没有这个操作；若先进行收银员操作，则没有购书者先购书，收银员无法操作。此时b1有个P操作，P操作需要付款V操作来唤醒；所以一开始的PV是同一信号量P(S1), V(S1)；对于购书者有个等待阻塞操作，等待收银员P(S2), V(S2)。【V(S1)唤醒P(S1)，收费后由收银员的V(S2)唤醒付款的P(S2)】
n+1个人进来的话会被阻塞。

注意：
①P操作具备阻塞的职能，V操作不具备阻塞能力。
②PV操作关键要找到约束，找到谁是因变量，谁是自变量，谁约束谁。【PV操作是成对出现的】
③一对儿PV操作信号量是相同的。
看题发现已经存在了一对PV操作，信号量为Sn，Sn的值为n，很容易想到这对PV操作的作用就是控制进入书店的人数的。当人数达到n了，阻止人继续进入书店，这种状态直到有人付款离开书店为止。

再来看题发现还有两对PV操作，首先通过图能知道购书者和收银员之间存在约束关系，收银员要等待购书者付款才能工作，购书者要等待收银员反馈才能离开书店。那么这两对PV操作就是控制这个约束的。

先从购书者分析，购书者开始付款了，收银员才能开始收款，所以a1与b1之间是一对PV操作，进一步分析，如果没有购书者付款，那么收银员是不能执行收款操作的，也就是说收银员进程应该及时阻塞，故b1应该是P（S1）,a1应该是V（S1）。

购书者发起付款操作的时候，不能马上离开书店，因为他要等收银员的反馈，付款成功拿到 小票才能离开，也就是说购书者在等待收银员反馈的时候应该及时阻塞住，故a2与b2之间是一对PV操作，且a2是P（S2），对应的b2就是V（S2）。

再检查一遍看看是否合理呢？

从收银员角度开始，假设没有人付款，P操作能及时阻塞，使得收银员进程不会进入收费状态，所以b1位置放P操作没有问题，进一步分析信号量S1的初始值应该为0，经过b1后S1为-1，阻塞。

从购书者角度看，开始付款的时候激活收银员进程，所以a1是V操作也没有问题，通过a1的操作，S1信号量又为0了，收银员进程可以进行收费了。

再返回收银员角度，收费完毕后要给购书者信号，购书者从才能离开，所以b2为V操作没有问题。

从购书者角度看，a2应该是P操作，应该及时阻塞住。进一步分析，S2信号量也应该是0才符合要求。

😁总结
PV操作从做题的角度出发，我认为首先要找到约束关系，就是谁和谁是一对约束，第二步确定这对约束谁是P谁是V（用反证方法推一下看看），最后一步考虑信号量，信号量为多少取决于是否马上阻塞还是说执行几次后再阻塞，这个要结合具体问题具体分析。

(53条消息) 软考必考题型之PV操作_pv操作中p和v各代表什么_du-hyper的博客-CSDN博客
(53条消息) 软考–快速掌握操作系统的PV操作_pv操作 软考_韦_恩的博客-CSDN博客

箭头的起始位置是V操作，箭头的终止位置是P操作

进程管理 — 死锁问题

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

资源都被分配且无法得到资源释放

例题：系统有3个进程：A、B、C。这3个进程都需要5个系统资源。如果系统至少有多少个资源，则不可能发生死锁[有多少资源 无论怎么分配都不会产生死锁]

进程A	进程B	进程C

如果每个进程需要n个资源，总共有k个进程 =>分配情况：k × (n-1) + 1
答：每个进程都需要5个资源，共有3个进程 => n = 5; k = 3 ==> 3 × (5 - 1) + 1 = 12+1 =13

打破互斥：让大家同时共享资源
打破保持和等待：得不到相应的资源就会把资源分享出去，不会霸占并等待别人给与
打破不剥夺：不去抢别人分配到的资源

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

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

@@ 例：假设系统中有三类互斥资源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

• 若先不执行P2，先执行P1，则右图R1还需资源数还需要5个，则你R1剩下的2个不够分配到，会发生进程死锁。即第一个先执行 P2。
• 若先执行P2，再执行P1，则我们发现进程P1需要R1资源为5，我们能提供的R1资源为4，所以序列无法进行下去，为不安全序列
  【只要现有资源可以满足需要资源的分配即可True，执行完后释放资源给下一步进程使用】

存储管理 — 分区存储组织

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

最佳适应算法：分配任务空间时。任务由闲余空间从小到大依次尝试是否能成功分配。若小闲余空间能分配就分配。不可则进入下一个闲余空间进行空间区域切割划分。缺陷：内存的碎块(几k的闲余空间)；
最差适应算法：则逆过来表示(先考虑从大的块中分配出来)
循环首次适应法：(分配较均匀)

存储管理 — 页式存储组织

逻辑地址的页号对应物理地址的块号(通过查表可得出)；其页内地址都是一样的(调用的时候以页为单位, 偏移量不会有太大的变化)

例：进程P有6个页面，页号分别为0-5，页面大小为4K，页面转换表如下所示。表中状态位等于1和0分别表示页面在内存和不在内存。假设系统给进程P分配了4个存储块，进程P要访问的逻辑地址为十六进制5A29H，那么该地址经过变换后，其物理地址应为十六进制(6A29H)；如果进程P要访问的页面4不在内存，那么应该淘汰页号为(1)的页面。

页号	页帧号	状态位	访问位	修改位
0	2	1	1	0
1	3	1	0	1
2	5	1	1	0
3	一	0	0	0
4	一	0	0	0
5	6	1	1	1

(1) A. 1A29H B. 3A29H C. 5A29H D. 6A29H
(2) A. 0 B. 1 C. 2 D. 5

4k = 4×1024 = 2$^{2+10}$ = $2^{12}$ 说明一个页内地址是12位，高于12位的就是页号
由于进制P要访问的逻辑地址是十六进制5A29H，则一个十六进制位 = 4个二进制位
说明有3个位是页内地址 => A 2 9；所以页内地址无需求，是为A29
页号5需要查表观测它的页帧号是6；然后与后面拼接起来 为6A29H
将要淘汰的页号一定是在存在的里面选出 存在的才能淘汰，则1代表存在；
就要从页号0 1 2 5中淘汰一个，看其访问位，刚刚访问过的是1不能淘汰，
只能淘汰访问位是0的，综上所述，应该淘汰1页号

存储管理 — 段式存储组织

存储管理 — 段页式存储组织

先查段表 查完段表 查页表

存储管理 — 快表

快表是一块小容量的相联存储器(Associative Memory), 由高速缓存器组成，速度快，并且可以从硬件上保证按内容并行查找，一般用来存放当前访问最频繁的少数活动页面的页号。
若将这些东西放在内存当中则称为慢表(放在内存)、快表(放在Cache)

存储管理 — 页面置换算法(运用于分层的置换体系中)

页面淘汰算法

☆ 最优(Optimal, OPT) 算法

☆ 随机(RAND) 算法

★ 先进先出(FIFO) 算法：有可能产生”抖动”

抖动：给你更多的资源去处理反而效率降低了
例如432143543215序列用3个页面，比4个缺页要少
缺页：当加入内存中的页面序列是全新版本(内存中没有)，则内存内部需要这个版本，因为缺少这个版本
第八-九列 编号为4的程序页不缺页(没有往前推进的原因是因为内存中还存有4的残渣[第八列]；有3的残渣[第九列])

(9次)	4	3	2	1	4	3	5	4	3	2	1	5
1	4	4	4	3	2	1	4	4	4	3	5	5
2		3	3	2	1	4	3	3	3	5	2	2
3			2	1	4	3	5	5	5	2	1	1
缺页	√	√	√	√	√	√	√			√	√

(10次)	4	3	2	1	4	3	5	4	3	2	1	5
1	4	4	4	4	4	4	3	2	1	5	4	3
2		3	3	3	3	3	2	1	5	4	3	2
3			2	2	2	2	1	5	4	3	2	1
4				1	1	1	5	4	3	2	1	5
缺页	√	√	√	√			√	√	√	√	√	√

横向代表：访问的页面序列
纵向代表：内存的几号页面(第一列是编号为4的程序页)

LRU：最近被访问的则不需要被淘汰，淘汰掉最久没有被访问到的
FIFO：先入先出原则

★ 最近最少使用(LRU) 算法：不会”抖动”

根据局部性原理，刚刚访问过的资源是不会被淘汰出去的

每读一次程序块，先在内存上面查一下表之后读取相应的内存块，所以每一个内存块需要进行两次内存的访问。总共有⑥个块，会产生12次内存的访问

A块在2号页有一半，在3号页面也有一半。所以总的缺页次数是5次；对于指令而言无论占用几个块都会一次性调用不会产生两次垄断，只有一次缺页垄断；∴swap A,B 一次；A上半页一次, 下半页一次；B上半页一次, 下半页一次；1+2+2=5次；1k有1024个单元(字节)

文件管理 — 索引文件结构

一个物理盘块是1K大，一个地址4Byte，除一下，每一个盘块可以存256个地址; ↓ ↓ ↓ ↓ ↓ ↓

File1的信息是二级地址索引表

操作系统 — 文件和树型目录结构

文件属性：R 只读文件属性 A 存档属性 S 系统文件 H 隐藏文件
文件名的组成：驱动号、路径、主文件名、扩展名
绝对路径：是从盘符开始的路径
相对路径：是从当前路径开始的路径
若当前目前位：D1，要求F2路径
则：绝对路径：/D1/W1/F2； 相对路径：W2/F2

文件管理 — 空闲存储文件的管理

空闲区表法(空闲文件目录)、空闲链表法、**位示图法**、成组链接法

(1) (4195+1) / 32 = 131.125 ≈ 第132字
(2) 用物理块毫无疑问是要制成1的 所以AC排除，131×32=4192 (0→4191)，故第132字中：
第0位置→4192 第1位置→4193 第2位置→4194 第3位置→4195
第多少个字是从1开始算, 多少位置是从第0个位置开始算。

第1字 1 0 1 0 0 … 1 1
第2字 0 1 1 0 … 0 1
第3字 1 1 1 1 0 … 1 0
… …
第n字 0 0 0 1 1 … 0 0

设备管理 — 数据传输控制方式

设备管理 — 虚设备与SPOOLING技术

要输出输入的先缓存起来(输入井 输出井)

微内核操作系统

数据库系统

三级模式 — 两级映射

内模式：管我们如何去存储这些数据 也叫存储模式，对应于物理级
概念模式：表之间有一定的关联 逻辑模式 对应概念级
外模式：对应着数据库里的视图(对数据更灵活的控制) 子模式或用户模式，对应用户级
期间都存在着映射(起到逻辑独立性/物理独立性)

什么是外模式？
1）数据库的用户使用的局部数据的逻辑结构和特征的描述
2）数据库用户的数据视图，是与某一应用程序有关的数据的逻辑表示。（如应用程序A只能看见其相对于的外模式1，应用程序B只能看见其相对于的外模式2，不能看见不属于自己的外模式。相当于是模式的一个子集）

外模式的地位：介于模式与应用之间。

模式与外模式的关系：一对多
1）外模式是模式的子集
2）一个数据库可以有多个外模式，反应了不同的用户的应用需求、看待数据的方式、对数据保密的要求。
3）对于模式中的同一个数据，不同外模式可以对数据的长度、类型等有不同的定义。

外模式与应用的关系：一对多。
1）同一外模式可以为某一个用户的多个应用系统所使用
2）但一个应用程序只能使用一个外模式

外模式的用途：
1）保证数据库安全，每个用户只能看见自己对应外模式的数据
2）保证数据独立性。

总结:外模式是模式的一部分，是部分用户看到的数据库的样子。

内模式：
1）数据物理结构和存储方式的描述
2）是数据在数据库内部的表示方式
Ⅰ.记录的存储方式：如顺序存储，按B树结构存储，Hash存储）
Ⅱ.索引的组织方式：B+树索引，hash索引，Join index索引
Ⅲ.数据是否压缩存储
Ⅳ.数据是否加密
注：一个数据库只有一个内模式。

总结：内模式处于最底层，是对数据在数据库底层的存储的描述。

数据库特点：

数据结构化、数据的共享、冗余度低、数据独立性高、数据由DBMS统一管理和控制

数据库设计过程

E-R模型

概念模型 面向用户 用户角度出发 用户分析
逻辑结构/模型
物理结构/模型(数据库对象) 跟计算机系统发生联系

主码：[也称住关键字，它能够唯一标识一个元组。码可以是一个属性或属性组]

框框表示实体[客观存在并相互区别的事物]
椭圆表示属性[实体所具有的特征]
菱形表示联系[实体与实体之间的关系]
域：属性值的取值范围
实体型：用实体名及其属性名集合来描述同类实体也称为实体型 学生(学号, 姓名, 性别)
实体之间有各种各样的连信息(一对一联系1:1、一对多联系1:n、多对多联系m:n)

1个学生对应N个课程，1个课程对应M个学生；所以学生和课程是N:M的关系

集成的方法：

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

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

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

关系代数

基本运算

并 交 差 笛卡尔积 投影 选择 联接

★★★★ 考点 ★★★★

规范化理论—函数依赖

规范化理论—价值与用途

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

超键可能存在冗余属性
候选键不存在冗余属性

规范化理论—求候选键

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

规范化理论—范式

主属性(SNO CNO)：属性属于候选键的一部分 (在任何一个候选关键字里出现过的都是主属性)
没有非主属性 肯定满足第二范式和第三范式

规范化理论—综合例题

规范化理论—模式分解

当范式级别不够的时候把模式进行拆分 这样范式级别就可以上升

并发控制—基本概念

数据库完整性约束

√ 实体完整性约束：约束主键(主键为空 没有输入具体值)
√ 参照完整性约束：填入的数据必须是按照表里主键的内容(允许为空)
√ 用户自定义完整性约束：(年龄不允许输入负数 或者200以上的值)

√ 触发器(较复杂的要求)：可以写脚本来约束数据库数据的要求

数据库安全

措施	说明
用户标识和鉴定	最外层的安全保护措施，可以使用用户账户，口令及随机数检验等方式
存取控制	对用户进行授权，包括操作类型(如查找, 插入, 删除, 修改等动作)和数据对象(主要是数据范围)的权限
密码存储和传输	对远程终端信息用密码传输
视图的保护	对视图进行授权
审计	使用一个专用文件(日志)或数据库，自动将用户对数据库的所有操作记录下来

数据备份

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

备份方式 / 优缺点	优点	缺点
冷备份	非常快速的备份方法只需要复制文件；容易归档(简单复制即可)；容易恢复到某个时间点上(只需要将文件再复制回去)；能与归档方法相结合，做数据库”最佳状态“的恢复；低度维护，高度安全	单独使用时，只能提供到某一个时间点上的恢复；再实施备份的全过程中，数据库必须要作备份二不能做其他工作；若磁盘空间有限只能复制到磁带等其他外部存储设备上，速度会很慢；不能按表或按用户恢复
热备份	可再表空间或数据库文件级备份，备份的时间短；备份时数据库仍可使用；可达到秒级恢复(恢复到某一时间点上)；可对几乎所有数据库实体做恢复；恢复是快速的	不能出错，否则后果严重；如我热备份不成功所得结果不可用于时间点的恢复；因难于维护，所以要特别小心，不允许”以失败告终“

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

日	一	二	三	四	五	六
完	增	增	增	差	增	增

若在周一的增量备份后系统出现故障，首先恢复周日的完整版，再其上恢复周一增量版
如果周三的增量备份系统出现了故障，首先恢复周日的完整版，再其上恢复周一周二周三增量版
这样恢复太麻烦，所以提出了差量备份, 周四的差量备份直接针对周日的差量变化
如果周四的增量备份系统出现了故障，首先恢复周日的完整版，再其上恢复周四的差量版

• 静态海量存储：在系统中无运行事务时进行, 每次存储全部数据库

• 静态增量存储：在系统中无运行事务时进行，每次只存储上一个转储后更新过的数据库

• 动态海量存储：转储期间允许对数据库进行存取或修改，每次转储全部数据库

• 动态增量转储：转储期间允许对数进行存取或修改，每次只转储上一次转储后更新过的数据

日志文件：事务日志是针对数据库改变所做的记录，它可以记录针对数据库的任何操作(增删改查)，并将记录结果保存在独立的 (先写日志 再写数据文件)

故障关系	故障原因	解决办法
事务本身的可预期故障	本身逻辑	再程序中预先设置Rollback语句
事务本身的不可预期故障	算数溢出, 违反存储保护	由DBMS的恢复子系统通过日志,撤销事务对数据库的修改,回退到事务初始状态
系统故障	系统停止运转	通常采用检查点法
介质故障	外存被破坏	一般使用日志重做业务

数据仓库与数据挖掘

数据仓库是面向各各主题的；会记录一些集成式的数据(报表)

反规范化(牺牲空间+规范化程度来换时间)

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

技术手段

√ 增加派生性冗余列 (在成绩表里添加 姓名/课程名 能够快速查到哪个人成绩多少分)
√ 增肌冗余列
√ 重新组表(依据查询效率的原则)
√ 分割表(从效率角度看进行垂直分割、水平分割)

大数据 4V

Volume 数据量 Velocity 速度 Variety 多样性 Value 价值

比较维度	传统数据	大数据
数据量	GB或TB	PB级或以上
数据分析需求	现有数据的分析与检测	深度分析(关联分析、回归分析)
硬件平台	高端服务器	集群平台

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

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

计算机网络

中继器：类似于烽火狼烟
网桥：链接两个同类型的设备
交换机：用来链接多个设备

按分布范围分

局域网LAN 城域网MAN 广域网WAN 因特网

按拓扑结构分

总线型 星型 环型

层次	名称	主要功能	主要设备及协议
7	应用层	实现具体的应用功能	POP3、FTP、HTTP、Telnet、SMTP、DHCP、TFTP、SNMP、DNS
6	表示层	数据的格式与表达、加密、压缩	POP3、FTP、HTTP、Telnet、SMTP、DHCP、TFTP、SNMP、DNS
5	会话层	建立、管理和终止会话	POP3、FTP、HTTP、Telnet、SMTP、DHCP、TFTP、SNMP、DNS
4	传输层	端到端的连接	TCP、UDP
3	网络层	分组传输和路由选择	三层交换机、路由器、ARP、RARP、IP、ICMP、IGMP
2	数据链路层	传送以帧为单位的信息	网桥、交换机、网卡、PPTP、L2TP、SLIP、PPP
1	物理层	二进制传输	中继器、集线器

TCP/IP 协议体系结构
(1) 采用 分层结构，将复杂的大问题，划分成若干个简单的小问题
(2) TCP/IP从下向上，依次划分为 “网络接口层、网络层 、传输层、应用层”
【注意】”网络接口层” 对应了 OSI的 物理层和数据链路层
(3) 常用协议
① 数据链路层 [PPP 点对点协议 PPPoE 基于 局域网的PPP协议 over Ethernet]
用于 建立、维护 数据链路(数据通道)
② 网络层
IP：互联网协议，是所有通信必须使用的协议；作用：保证数据到达正确的目的地
ARP：地址解析协议，实现 局域网 中主机的 IP地址转网卡的物理地址
ICMP：互联网控制报文协议，功能：差错控制和查询主机
RARP：逆向ARP，局域网中 物理地址 转 虚拟IP地址

ping 127.0.0.1 回环测试本地主机内部网络状态是否正常

③ 传输层
TCP：传输控制协议，面向连接、可靠通信协议；功能：保证到达目的地的数据是正确的
UDP：用户数据报协议，无连接、不可靠通信协议，用于 大数据传输(流媒体)：音频、视频
④ 应用层
HTTP 超文本传输协议：用于访问网络
HTTPS 加密/安全超文本传输协议
SMTP/MIME 简单邮件传输协议：用于发送电子邮件
POP3/IMAP 邮局协议第三版：用于接收电子邮件
FTP 文件传输协议：用于 上传下载文件
TELNET 远程登录协议
DNS 域名解析协议：实现 中英文域名 转换为 数字的IP地址

DHCP + DNS协议

网络规划与设计

★★★ 非常重要 IP地址相关计算题 ★★★

IP地址和子网掩码换算

已知ip地址和子网位数，例如：C网192.168.1.53/27， [子网位数是27]
求
1.具体的子网掩码
2.子网数
3.最大可容纳主机数
4.可用的主机数
5.网络地址
6.广播地址
7.地址范围
8.主机号

一、如何求具体的子网掩码（根据默认子网掩码和给出的子网位数求）：

**1.**C网默认的子网掩码是：255.255.255.0
转换成二进制是：11111111.11111111.11111111.00000000
（1代表网络号，0代表主机号）
前24位是1，代表网络号，后8位是0，代表主机号
==已知子网位数是27==，代表网络号向主机号借用了3位（8+8+8+3）
得：11111111.11111111.11111111.11100000
把二进制转换为十进制：255.255.255.224
求出192.168.1.53/27对应的子网掩码是255.255.255.224

二、子网数

1.网络号向主机号借了3位（27-24），得**$2^3$=8个**

三、最大可容纳主机数（根据求出的子网掩码和给出的子网位数求）1.由一可知子网掩码是：255.255.255.254，转换为二进制是11111111.11111111.11111111.11100000
1代表网络号，0代表主机号，有5个0，得最大可容纳主机数是2^5=32

四、可用的主机数

由三可知，最大可容纳主机数是32个，32-2广播地址+网络地址=30

五、网络地址（把IP地址和子网掩码进行与运算）

192.168.1.53/27， 把IP地址和子网掩码进行与运算，IP地址转换为二进制：11000000.10101000.00000001. 0011010153;
子网掩码255.255.255.254转换为二进制：11111111.11111111.11111111.11100000，
进行与运算得：
IP地址： 11000000.10101000.00000001. 00110101
子网掩码： 11111111.11111111.11111111. 11100000（子网掩码连续全1的是网络地址，后面的是主机地址）
11000000.10101000.00000001. 00100000=====转换为十进制得：192.168.1.32
所以网络地址是192.168.1.32

六、广播地址（网络地址中的网络地址部分不变，主机地址变为全1，结果就是广播地址）

1.网络地址： 11000000.10101000.00000001. 00100000（标黄部分是网络地址），变为1得：11000000.10101000.00000001. 00111111

2.广播地址转换为十进制：192.168.1.63

七、地址范围

1.网络地址+1——-广播地址-1，得192.168.1.33—-192.168.1.62

八、主机号（子网掩码取反再和IP做与运算）

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

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

十进制	二进制
168.195.0.0	1010 1000 1100 0011 0000 0000 0000 0000

$2^R$ ≥ N；R=5时 N=32 ＞ 27
网络位要向主机位借5位
该例中需27个子网，按公式，需借5位

子网掩码：1111 1111 1111 1111 1111 1000 0000 0000 → 255.255.248.0每个子网能容纳的有效主机数为$2^{11}-2$=2046台
只要划分子网 就是变化的子网掩码

例2，将B类IP地址168.195.0.0划分称若干个子网，每个子网内有主机700台，则子网掩码为多少？(这两个子网掩码是根据不同的条件而得到的)

$2^R$ ≥ N；N=700；R=10 也就是剩余10个零地址位(网络位)只要有10位就够了
子网掩码：1111 1111 1111 1111 1111 1100 0000 0000 → 255.255.252.0

无分类编址(无类域间路由)

IP地址 :: = {<网络前缀>, <主机号>}
128.14.32.0/20 表示的地址块共有$2^{12}$个地址
这个地址块的起始地址是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的主机号地址一般不使用

例3，分配给某公司网络的地址块是210.115.192.0/20，该网络可以被划分位(16)个C类子网；

C类地址 24个子网位 8个主机位，题目是/20 前面20位为网络号；证明还要从主机号里拿出4个位来做子网号；4个位得到的子网数量是16个

特殊含义的IP地址

HTML

无线网

优势

灵活性 移动性 成本低 容易扩充

接入方式

有接入点模式 无接入点模式(对等网模式)

无线局域网(WLAN, 802.11, Wi-Fi)
无线城域网(WMAN, 802.16, WiMax)
无线广域网(WWAN, 3G/4G)
无线个人网(WPAN, 802.15, Bluetooth)

有线接入

公用交换电话网络(PSTN) 原始拨号上网 pose机+传真
数字数据网(DDN) 数字专用网(专线)
综合业务数字网(ISDN) 允许打电话的时候上网
非对称数字用户线路(ADSL) 老旧小区电话线部署
同轴光纤技术(HFC) 家里有线电视

无线接入

IEEE 802.11(WiFi)
IEEE 802.15(蓝牙Bluetooth)
红外(IRDA)
WAPI

3G/4G

WCDMA
CDMA2000
TD-SCDMA (国外多 速率低 功耗大)
LTE-Advanced
WirelessMAN-Advanceed(802.16m) (WiMAX)

IPV6

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

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

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

信息系统安全属性

安全属性

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

加密技术

信息摘要(不能用作加密算法 因为不能解密) （无法篡改）

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

数字签名

数字证书：识别人的身份

数字信封与PGP

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

PGP可用于电子邮件，也可以用于文件存储。采用了杂合算法，包括IDEA、RSA、MD5、ZIP数字压缩算法

PGP承认两种不同的证书格式：PGP证书和X.509证书

PGP证书包含PGP版本号、证书持有者的公钥、证书持有者的信息、证书拥有者的数字签名、证书的有效期、密钥首选的对称加密算法

X.509证书包含证书版本、证书的序列号、签名算法标识、证书有效期、以下数据：证书发行商名字、证书主题名、主体公钥信息、发布者的数字签名

练习题 — 设计邮件加密系统

要求邮件以**加密方式传输(加密解密技术 )，邮件最大附件内容可达500MB( 对称加密 )，发送者不可抵赖** ( 数字签名 )，若邮件被第三方截获，**第三方无法篡改** ( 信息摘要技术 )。

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

网络安全 — 网络威胁与攻击

防火墙技术

数据结构与算法基础

数组与矩阵、线性表、广义表、树与二叉树、图、排序与查找、算法基础及常见的算法

数组

数组类型	存储地址计算
一维数组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

1 a[0] [0]	2 a[0] [1]	3 a[0] [2]
4 a[1] [0]	5 a[1] [1]	6 a[1] [2]
7 a[2] [0]	8 a[2] [1]	9 a[2] [2]

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

a[i] [j]的存储地址(按行存储)：a + ( i * n + j) * len
(2 * 5 + 3) * 2，a[2] [3]是存储的第14个元素，由于编号是从0开始算的，有13个偏移量
∴ a + 13 * 2 = 每一个元素所占的字节数 a[0] [0] = a

√	√	√	√	√
√	√	√	√	√
√	√	√	√

稀疏矩阵

数据结构

数据结构是指互相之间存在一种或多种特定关系的数据元素的集合
图包含树 树包含线性结构

线性结构 O-O-O-O
非线性结构 树 + 图

线性表

顺序表 + 链表(单链表、循环列表、双向链表)

顺序存储与链式存储对比

性能类别	具体项目	顺序存储	链式存储
空间性能	存储密度	=1，更优 (1=100%)	< 1 (有节点专门存地址信息)
	容量分配	事先确定	动态变化，更优 (动态改变分配)
时间性能	查找运算	O(n/2)	O(n/2)
	读运算	O(1)，更优	O([n+1]/2), 最好情况为1，最坏情况为n (需要一格一格的移)
	插入运算	O(n/2)，最好情况为O，最坏情况为n	O(1)，更优 (局部小外科手术)
	删除运算	O([n-1]/2)	O(1)，更优 (局部小外科手术)

线性表—队列与栈

广义表

树与二叉树

二叉树遍历

反向构造二叉树

树转二叉树

查找二叉树

最优二叉树(哈夫曼树)

线索二叉树

平衡二叉树

树和图的最大区别：树是没有环路的

完全图

邻接图

图的遍历(深度+广度)

图 — 拓扑排序

图的最小生成树 — 普里姆算法

算法基础

算法的特性

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

算法的复杂度

时间复杂度：是指程序运行从开始到结束所需要的时间。通常分析时间复杂度的方法是从算法中选取一种对于所研究的问题来说是基本运算的操作，以该操作重复执行的次数作为算法的时间量度。一般来说，算法中原操作重复执行的次数是规模n的某个函数T(n)。由于许多情况下要精密计算T(n)是困难的，因此引入了渐进时间复杂度在数量上估计一个算法的执行时间。其定于如下：
如果存在两个常数c和m，对于所有的n，当n≥m时有f(n) ≤ cg(n), 则有f(n) = O(g(n))，也就是说，随着n的增大，f(n)逐进地不大于g(n)。例如，一个程序的实际执行时间为T(n)=3$n^3$+2$n^2$+n, 则T(n) = O($n^3$) [以最高的时间复杂度为准！三重for循环时间复杂度是O($n^3$)]

常见的对算法执行所需时间的量度：
O(1) < O(lo$g_2$n) < O(n) < O(nlo$g_2$n) < O($n^2$) < O($n^3$) < O($2^n$)

log的由来：排序二叉树 找结点 有7个结点的完全二叉树，向下比较 最多比较3次(二叉树的层数) 最坏的情况多少层就比较多少次 所以有lo$g_2$n，n就是结点数量

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

查找 — 顺序查找与二分查找

查找 — 散列表

排序

直接插入排序

希尔排序(效率高于直接插入排序)

直接选择排序

堆排序(适合于：不需要求全部 求前一部分)

冒泡排序

快速排序

归并排序

基数排序

算法排序汇总

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

编译过程

文法定义

有限自动机与正规式

程序语言基础—表达式

函数调用—传值与传址

程序语言基础—各种程序语言特点

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

法律法规 — 课程内容提要

从所涉及的法律法规角度

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

@@ 著作权因作品的完成而自动产生，不必履行任何形式的登记或注册手续，也不论其是否已经发便，所以甲对该软件作品享有著作权，乙未经甲的许可擅自使用甲的软件作品的行为，侵犯了甲的软件著作权

@@ 关于软件著作权产生的时间是自作品完成创作之日

从试题考点分布的角度

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

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

著作权：一般保护作者的利益
邻接权：别人盗写我出的书，不仅破坏了我的权益，还有**出版商的权益
地理标志权：新疆**哈密瓜 只有在标志的地理位置生产(这一区域都拥有)

法律法规 — 保护期限, 知识产权人

侵权判定

中国公民、法人或者其他组织的作品，无论是否发表，都享有著作权

开发软件所用的思想、处理过程、操作方法或者数学概念不受保护

著作权法不适用于下列情形：

√ 法律、法规、国家机关的决议、决定、命令和其他具有立法、行政、司法性质的文件，及其官方正式译文

√ 时事新闻

√ 历法、通用数表、通用表格和公式

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

标准化基础知识—标准的分类

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

→ 国标、国外标准代号：标准代号+专业类号+顺序号+年代号
→ 我国国家标准代号：强制性代号为GB、推荐性标准代号为GB/T、指导性标准代号为GB/Z、实物标准代号GSB

→ 行业标准代号：由汉语拼音大写字母组成(如电子行业为SJ)
→ 地方标准代号：由DB加上省级行政区划代码的前两位
→ 企业标准代号：由Q加上企业代号组成

多媒体基础

人耳：20Hz—20kHz 小于20Hz是次声波 大于20kHz是超声波
说话：300—3400Hz
乐器：20Hz —20kHz
白噪音：20 ~ 20kHz

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

采样点密集程度越高，时间间隔越短，还原度越好
采样精度画格子的数量 y轴平行于x做直线

图像相关概念

色彩三要素色

亮度是光作用于人眼时所引起的明亮程度的感觉，它与被观察物体的发光强度有关。
色相是当人眼看一种或多种波长的光时所产生的彩色感觉，它反映颜色的种类，是决定颜色的基本特性。
饱和度是指颜色的纯度，也可以叫做纯度、彩度或浓度等，即掺入白光的程度，或者是指颜色的深浅程度。

HSB彩色模式
是根据日常生活中人眼的视觉特征而制定的一套色彩模式。HSB颜色模式以色相、饱和度和亮度描述颜色的基本特征。

CMY颜色模式
是采用**青(Cyan、品红或洋红(Magenta)、黄(Yellow)**3种基本颜色按一定比例合成颜色的方法。颜色的产生是来自于照射在颜料上反射回来的光线。
图像打印输出时用CMY颜色模式。

Lab颜色模式
分别用**亮度或光亮度分量(Luminosity)和两个色度分量(a、b)**来表示颜色
L表示亮度。L的值域由0到100，L=50时，相当于50%的黑。
a表示从洋红色至绿色的范围，
b表示从黄色至蓝色的范围，
a和b的值域是由+127至-128。

索引颜色模式
最多使用256种颜色，当图像被转换为索引颜色模式时，通常会构建一个调色板存放图像中的颜色并编制颜色索引。

位图模式
位图模式的图像只有黑色与白色两种像素，每个像素用1位二进制数表示,”0”表示黑色,“1”表示白色。

灰度模式
用单一色相表现图像，最多使用256级。图像中的每个像素有一个0(黑色)～255(白色)之间的亮度值。此外，灰度值也可以用黑色油墨覆盖的百分比来表示(0%表示白色，100%表示黑色)。

颜色深度
位图图像中各像素的颜色信息是用二进制数据描述的。
色彩由颜色深度决定，不是分辨率
二进制的位数就是位图图像的颜色深度。颜色深度决定了图像中可以呈现的颜色的最大数目。

分辨率:
图像分辨率(Image Resolution):指单位图像线性尺寸中所包含的像素数目，通常以**像素/英寸(pixel per inch,ppi)**为计量单位。

彩色空间：RGB彩色显示器、YUV(电视, 兼容方案)、CMY[K黑]、HSV(HSB)艺术家角度

光的颜色采取叠加原理
印刷的三原色采取相减原理

媒体的种类

感觉媒体，指通过人的感觉器官能直接感受的媒体，如视觉。
表示媒体，用于传播和表达感觉媒体的中介媒体，是信息的表示和表现形式，如JPG编码
表现媒体(显示媒体)，是进行信息输入和输出的一类媒体，如显示器
传输媒体，是用于通信传输的信息载体，如双绞线。
存储媒体，是存放表示媒体的物理实体，如光盘

感觉媒体：听觉、触觉、嗅觉；
表示媒体：文字、数字、音频、视频、编码方式；
表现媒体(显示媒体)：输入显示媒体键盘、鼠标和麦克风、输出显示媒体显示器、打印机和音箱
存储媒体：存储数据的物理设备，硬盘、磁盘、光盘U盘
传输媒体：存储数据的物理载体，电缆、光缆和交换设备

• D/A转换，数字音频模拟化输出

计算

• 波形音频文件容量的计算 容量=声道数 * 采样频率 * 量化位数 * 长度 / 8
  其中频率单位Hz，量化单位bit，长度秒，容量单位字节B
• 波形音频文件码率的计算 码率=声道数 * 采样频率 * 量化位数 码率的单位是bps

常见波形文件格式

• ==.wav== 微软和IBM共同开发的PC标准音频格式，未压缩，声音达到CD音质，码率约为1.4Mb/s，Windows XP录音机默认音频格式
• .mp3 有损压缩，最常用 互联网、MP3音乐
• ==.wma==微软公司的有损压缩，压缩比高于MP3，Win7录音机默认格式
• .m4a 苹果公司的无损压缩
• .flac 无损压缩，高品质数字音乐
• .ape 无损压缩音频格式

@@ WAV文件称为波形声音文件，其音质与CD差不多
@@ MP3文件能够达到很高的压缩比，并能保持较高的音质；通常那个说WAV文件比MP3文件大[比WAV/CD好]
@@ MIDI不能从CD、磁带、麦克风等录制MIDI文件；通常MIDI文件小于MP3

MIDI格式

• MIDI乐器数字接口，垫桌子音乐制造商们建立的通信标准
• MIDI传输的不是声音信号，记录声音的信息，是在线音乐的一组指令，是音符、控制参数等指令，它指示MIDI设备要做什么，怎么做; 如演奏哪个音符，音量多大等
• .mid 或 .midi

==知识点总结==

图像

• 位图：.bmp不压缩 .gif无损压缩 .jpg/jpeg有损压缩 .png无损压缩 .tif
• 矢量图：.swf .ai .dwg .cdr

波形

• .wav .mp3有损压缩 .wma有损压缩：录音机(微软)

• .m4a无损压缩(苹果) .flac无损压缩(高质量数字音乐) .ape无损压缩音频

• MIDI [.mid/.midi]乐谱

视频编码

• .mpeg/.mp4 H.26X .avi .asf .wmv .rm/.rmvb .flv .mkv .mov

流媒体

• RM、WMV、ASF

音频信息在计算机中的表示

波形数字音频

音频信息处理的流程

• A/D转换[采样]，模拟音频的数字化【影响数字化质量的主要原因】

多媒体相关计算问题

图像容量计算640(水平像素)×480(垂直像素)

颜色深度的单位是 “位 bit “，图像容量的单位是字节B； 1 Byte = 8 Bits

条件	示例
知道像素，位数	每个像素为16位，图像位640×480像素，求容量： 640×480×16÷8=614400B
知道像素，色数	640×480像素，256色的图像，求容量： 640×480×log2(256)÷8=307200B

音频容量计算

音频容量 = 声道数 * 采样频率(Hz) * 量化位数 * 长度 / 8

视频容量计算

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

常见的多媒体标准

==@@ 存储动画的文件格式有FLC、GIF、SWF==

==@@ 网络视频格式包括MOV、RM、ASF、WMV==

==@@ 多媒体视频图像文件格式有AVI、MPG、ASF、MP4==

==@@ 声音、音频文件格式有WAV、WMA、MP3、MIDI、RA、APE==

==@@ 属于图像文件格式有GIF、BMP、JPG、PNG、TIF==

==.wma==微软公司的有损压缩，压缩比高于MP3，Win7录音机默认格式

@@ 位图（Bitmap）=> BMP

@@ 语音识别技术体现了多媒体技术与人工智能技术相结合

数据压缩基础

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

空间冗余：图片大面积相同色(白色)，记录哪些信息是白色
时间冗余：固定在一个界面跳舞时，后面的物体不会动，墙面不会动。不动的记录下来。有变动的就分析
视觉冗余：jpeg人眼视觉识别盲区(视觉边界点压缩)
信息熵冗余：不同的信息编码冗余度不一样，通过合理的信息编码
结构冗余：某个部件有大量冗余，地砖花纹一样
知识冗余：可以通过知识分析得到的信息

有损压缩与无损压缩

无损压缩编码法(Lossless compression coding)：也称之为**冗余压缩法或熵编码法**
有损压缩编码法(Loss compression coding)：**熵压缩法**

jpeg属于有损(比较高的压缩比)，无法还原成原始图(位图)

软件开发模型

瀑布模型、演化模型、增量模型、螺旋模型、快速原型模型、喷泉模型、V模型

迭代模型/迭代开发方法、快速应用开发、构件组成模型/基于构件的开发方法、敏捷开发方法、模型驱动的开发方法、基于架构的开发方法

@@ 在面向对象技术构建软件系统时，很多敏捷方法都建议的一种重要的设计活动是重构，它是一种重新组织的技术，可以简化构件的设计而无需改变其功能或行为

瀑布模型(SDLC)

原型、演化模型、增量模型

螺旋模型

V模型 喷泉模型 RAD

构件组装模型(CBSD)

统一过程

敏捷开发方法

信息系统开发方法

需求分类与需求获取

结构化设计：基本原则、内聚与耦合

结构化设计 — 系统结构/模块结构

软件测试 — 测试原型与类型

软件测试 — 测试用例设计

软件测试 — 测试阶段

McCabe复杂度

McCabe度量法概念：

McCabe度量法是通过定义环路复杂度，建立程序复杂度的度量，他是基于一个程序模块的程序图中环路的个数。计算G的环路复杂型有两种方法：
第一种是V(G)=m-n+2（m值得是有向弧数，也就是箭头的个数，n指的是结点个数
另外一种求法就是闭合区域的个数+1

系统运行与维护

软件过程改进—CMMI

项目管理

风险

风险是指”损失或伤害的可能性”

软件风险一般包含不确定性和损失。救火和危机管理是对不适合但经常采用的软件风险管理策略，已知风险和未知风险是对软件风险进行分类的一种方式。员工和预算是在识别项目风险时需要识别的因素

项目风险(关心未来)、技术风险(关心变化)、商业风险(关心选择)
风险曝光度(Risk Exposure)：计算方法是风险出现的概率 × 风险可能造成的损失
假设正在开发的软件项目可能存在一个未被发现的错误，而这个错误出现的概率是0.5%，给公司造成的损失将是1000000元，那么这个错误的风险曝光度就应该为1000000×0.5%=5000元

需求开发,需求分析,OOA — 相关概念

面向对象设计 — 设计原则

单一职责原则：设计目的单一的类 (单一会降低程序的耦合度)
开放—封闭原则: 对扩展开放，对修改封闭 (用新的类去解决问题 不去修改[容易引入错误影响原先])
李氏(Liskov)替换原则：子类可以替换父类 (不要盲目修改父类 不要去重载)
接口隔离原则：使用多个专门的接口比使用单个的总接口要好
组合重用原则：要尽量使用组合，而不是继承关系达到重用的目的
**迪米特(Demeter)原则(最少知识法则)**：一个对象应当对其他对象又尽可能少的了解

UML

设计模式的概念

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

面向对象 — 设计模式的分类

面向对象 — 创建型模式

设计模式名称	简要说明
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 访问者模式	表示一个作用于某对象结构中的各元素的操作，使得在不改变各元素的类的前提下定义作用于这些元素的新操作

数据流图(DFD)

数据流图基本概念

数据字典

符号	含义	举例说明
=	被定义为
+	与	x=a+b, 表示x由a和b组成
[… , …]或[… | …]	或	x=[a,b], x=[a|b], 表示x由a或由b组成
{…}	重复	x={a}, 表示x由0个或多个a组成
(…)	可选	x=(a), 表示a可在x中出现, 也可以不出现

机票 = 姓名 + 日期 + 航班号 + 起点 + 终点 + 费用
航班号 = “Y7100”..”Y8100”
终点 = [长沙|上海|北京|西安]

选择四个其中的一个终点

数据流图平衡原则

父图与子图之间的平衡、子图内平衡

答题技巧

试题1

第一问解析

第二问解析

第三问解析

试题二

试题2第一问、第二问

试题2第三问 (顶层和0层进行匹配)、第四问(从题干推导)

数据库设计过程

ER模型 — 实体间联系类型

数据库设计答题技巧

详细分析试题说明

熟练掌握基本知识

试题1

试题2

解析

UML建模

用例图、类图与对象图、顺序图、活动图、状态图、通信图、构件图

用例图

类图与对象图

顺序图

活动图

状态图

通信图 (顺序图+通信图=交互图)

区别：顺序图会强调时间顺序

试题1

解析

试题2

第一问

第二、三问

★★数据结构及算法应用★★(下午题)

分治法、回溯法、贪心法、动态规划法

分治法(★★ 分解 解决 合并 ★★) [一般用到递归]

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

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

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

int F(int n)
{
    if(n==0) return 1;
    if(n==1) return 1;
    if(n>1) return F(n-1)+F(n-2);
}

分治法 → 二分查找

function Binary_Search(L,a,b,x){
    if(a > b) return(-1);
    else{
        m=(a+b)/2;
        if(x==L[m]) return(m);
        else if(x > L[m])
            return(Binary_Search(L,m+1,b,x));
        else
            return(Binary_Search(L,a,m-1,x));
    }
}

回溯法

贪心法

动态规划法

数据结构算法例题

试题1

解析

试题2及解析

★★★★★面向对象程序设计(下午题)★★★★★

C++ 类与派生类的定义

class 类名{
    public:
        公有数据成员或公有函数成员的定义;
    protected:
        保护数据成员或保护函数成员的定义;
    private:
        私有数据成员或私有函数成员的定义;
};

class 派生类名：继承方法1 基类名1，继承方法2 基类名2,...{
    public:
        派生类的公有数据和函数
    protected:
        派生类的保护数据和函数
    private:
        派生类的私有数据和函数
};

在类外定义函数体的格式如下：
返回值类型 类名 :: 成员函数名(形参表){
    函数体;
}
::是类的作用域分辨符，用在此处，放在类名后成员函数前，表明后面的成员东西函数属于前面的那个类

C++构造函数与析构函数

构造函数相对于一般函数来说，具有如下特殊的性质：
1.构造函数的函数名必须与定义它的类同名
2.构造函数没有返回值。如果在构造函数前加void是错误的
3.构造函数被声明定义为公有函数
4.构造函数在建立对象时由系统自动调用

构造函数相对于一般函数来说，具有如下特殊的性质：
1.析构函数没有任何参数，不能被重载，但是可以是虚函数，一个类只有一个析构函数
2.析构函数没有返回值
3.析构函数名与类名相同，但在类名前加一个逻辑非运算符 “~” 以表示与构造函数对比区别
4.析构函数一般由用户自己定义，在对象消失时由系统自动调用，如果用户没有定义析构函数，系统将自动生成一个不做任何事的默认析构函数

对象指针的语法定义形式如下：
    类名 *对象指针名;

对象引用的定义形式如下：
    类名 &对象引用名 = 被引用对象;

注意：通过对象名或对象引用访问对象的成员，使用的运算符是 “.” 而使用对象指针访问对象成员，使用的运算符是 “->”

对象指针名 -> 数据成员名或 : 对象指针名 -> 成员函数名(参数表) 

C++虚函数

虚函数定义的一般语法形式如下:
virtual 函数类型 函数名(形参表){
    函数体;
}
纯虚函数定义形式如下：
virtual 函数名 = 0;

JAVA 类的定义

类的定义格式如下：
[import包]
[类修饰符] class xxxclass [extends超类] [implements接口]{
    public:
        公有数据成员或公有函数成员的定义;
    protected:
        保护数据成员或保护函数成员的定义;
    private:
        私有数据成员或私有函数成员的定义;
}
说明：
import包：引入包中的类
类修饰符：主要由四个修饰符(public、abstract、final、private)
class为关键字, xxxclass为类名，命名遵循Java标识符的命名规则
extends为继承关键字，implements为接口关键字
    
抽象类定义
abstract class Shape{
    abstract public void draw() [定义了draw抽象方法]
}

class Rectangle extends Shape{}
通过extends可以看出来Shape不是接口而是抽象类

import java.util.*;
(1) class Beverage{ //饮料
    String description = "Unknown Beverage";
    public (2) (){return description;}
        public (3);
}
abstract class CondimentDecorator extends Beverage{
    //配料
    (4);
}

(1) abstract
(2) String getDescription
(3) abstract int cost()
(4) Beverage beverage

JAVA 接口的定义

interface IFactory{}
class SqlServerFactory implements IFactory
通过implements实现关键字来反推interface关键字

面向程序设计

试题1及解析

试题2及解析