阿里云新用户优惠

软考中级|软件设计师笔记

2023-08-23 · 2065 words · 10 minute read

软考笔记

一、计算机组成原理与体系结构基础知识

1. 数据的表示

二进制是Binary，简写为B
八进制是Octal，简写为O
十进制为Decimal，简写为D
十六进制为Hexadecimal，简写为H

Ⅰ、进制的转换：

任意进制$\to$十进制

二进制：$10010010.110 = 1*{2^7} + 1*{2^4} + 1*{2^1} + 1*{2^{-1}} + 1*{2^{-2}} = 146.75$
八进制：$251.5 = 2*{8^2} + 5*{8^1} + 1*{8^0} + 5*{8^{-1}} = 168.625$
十六进制：$AE86.1 = 10*{16^3} + 14*{16^2} + 8*{16^1} + 6*{16^0} + 1*{16^{-1}} = 44678.0625$

十进制$\to$任意进制
使用短除法

二进制$\leftarrow\to$八进制、十六进制

二进制$\to$八进制
3位一组，每组转换成对应的八进制符号
$\frac {001}{1} \frac {111}{7} \frac{000}{0} \frac{010}{2} . \frac{011}{3} \frac{010}{2} = 1 7 0 2 . 3 2 $
八进制$\to$二进制
每位八进制对应的3位二进制
${(251.5)_8} = {(\frac{010}{2} \frac{101}{5} \frac{001}{1}. \frac{101}{5})_2} $
二进制$\to$十六进制
4位一组，每组转换成对应的十六进制符号
$\frac{0011}{3} \frac{1100}{C} \frac{0010}{2} . \frac{0110}{6} \frac{1000}{8} = 3C2.68$
十六进制$\to$二进制
每位十六进制对应的4位二进制
${(AE86.1)_16} = {(\frac{1010}{A} \frac{1110}{E} \frac{1000}{8} \frac{0100}{4} . \frac{0001}{1})_2}$

Ⅱ、真值与机器数

$\frac{15\to1111}{8\to1000} \frac{+15\to01111}{-8\to11000}$ $\to 原码、反码、补码和移码$

真值：符合人类习惯的数字
机器数：数字实际存到机器里的形式，正负号需要被 数字化

定点数：小数点的位置固定

无符号数：整个机器字长的全部二进制位均为数值位没有符号位相当于数的绝对值。通常只有无符号整数，而没有无符号小数。
有符号数
- 原码：
  - 用数值部分表示真值的绝对值，左边第一位是符号位，“0/1”对应“正/负
  - ${[+0]}_原 = 00000000$
  - ${[-0]}_原 = 10000000$
- 反码：
  - 正数的反码=原码
  - 负数的反码=原码数值位取反
  - ${[+0]}_反 = 00000000$
  - ${[-0]}_反 = 11111111$
- 补码：
  - 正数的补码=原码
  - 负数的补码=反码末位+1(要考虑进位)
  - ${[+0]}_补 = {[-0]}_补 = 00000000$
- 移码：
  - 补码的基础上将符号位取反。注意:移码只能用于表示整数
  - ${[+0]}_移 = {[-0]}_移 = 10000000$

正数	负数
${[+19D]}_原 = 00010011$ 符号位0是正数	${[-19D]}_原 = 10010011$ 符号位1是负数
${[+19D]}_反 = 00010011$ 反码=原码	${[-19D]}_反 = 11101100$ 反码=原码数值位取反
${[+19D]}_补 = 00010011$ 补码=原码	${[-19D]}_补 = 11101101$ 补码=反码末位+1(进位)
${[+19D]}_移 = 10010011$ 补码符号位取反	${[-19D]}_补 = 0101101$ 补码符号位取反

浮点数：小数点的位置不固定
- 浮点数是小数点位置不固定的数，它能表示更大范围的数。在浮点表示法中，阶码通常为带符号的纯整数，尾数为带符号的纯小数。
- 表示格式: | 阶符| 阶码| 数符| 尾数|
- 浮点数通常表示成 $ N = M \cdot {R^E}$ 其中，M称为尾数，R称为基数，E称为阶码
  - 阶码，决定浮点数所能表示的数值范围
  - 尾数，决定浮点数所能表示的数值精度

2. 校验码

Ⅰ、奇偶校验

奇偶校验是一种简单有效的校验方法。其基本思想是: 通过在编码中增加一位校验位来使编码中1的个数为奇数(奇校验)或者为偶数(偶校验)，从而使码距变为2。对于奇校验它可以检测代码中奇数位出错的编码，但不能发现偶数位出错的情况，即当合法编码中奇数位发生了错误，也就是编码中的 1 变成0或0变成1，则该编码中1的个数的奇偶性就发生了变化，从而可以发现错误。
常用的奇偶校验码有 3 种:

水平奇偶校验
垂直奇校验码
水平垂直奇偶校验码

海明码
海明码的构成方法是:在数据为之间插入个校验码，通过扩大码距来实现检错和纠错。
设数据位是n位，校验位是k位，则n和k必须满足以下关系: ${2^k}-1 \geqslant n+k$

Ⅱ、循环冗余校验码

3. 冯·诺依曼计算机的特点

计算机由五大部件组成（存储器、输入设备、运算器、输出设备、控制器）
指令和数据以同等地位存于存储器，可按地址寻访
指令和数据用二进制表示
指令由操作码和地址码组成
存储程序
以运算器为中心

4.主存储器

主存储器包含存储体、MAR、MDR
存储单元：每个存储单元存放一串二进制代码
存储字(word)：存储单元中二进制代码的组合
存储字长：存储单元中二进制代码的位数
存储元：即存储二进制的电子元件，每个存储元可存 1bit
MAR: 地址寄存器
MDR：数据寄存器
一个字节（Byte）= 8bit
MAR = 4位 $\to$ 总共有 $ 2 * 2 * 2 * 2 $个存储单元
MDR = 16位 $\to$ 每个存储单元可存放16bit，1个字(word) = 16bit

5.运算器

运算器:用于实现算术运算 (如: 加减乘除)、逻辑运算 (如: 与或非)
ACC:累加器，用于存放操作数，或运算结果
MQ:乘商寄存器，在乘、除运算时，用于存放操作数或运算结果
X:通用的操作数寄存器，用于存放操作数
ALU:算术逻辑单元，通过内部复杂的电路实现算数运算、逻辑运算。
DR:数据缓存寄存器
PSW:状态条件寄存器，用来保存指令运行标志
CU:控制单元，分析指令，给出控制信号
IR:指令寄存器，存放当前执行的指令
PC:程序计数器，存放下一条指令地址，有自动加1功能
AR:地址寄存器，保存当前CPU所访问的内存单元地址
ID:指令译码器，对操作码进行分析

完成一条指令步骤：1、取指令 2、分析指令 3、执行指令

6.Flynn分类法

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

7.指令

指令 (又称机器指令) :是指示计算机执行某种操作的命令，是计算机运行的最小功能单位。
一台计算机的所有指令的集合构成该机的指令系统，也称为指令集。

Ⅰ、指令格式

一条指令就是机器语言的一个语句，它是一组有意义的二进制代码。
一条指令通常要包括操作码字段和地址码字段两部分

操作码 (OP)	地址码(A)
用户要干什么?	对谁进行操作?
停机中断求反求补加减乘除	不需要操作对象需要一个操作对象需要两个操作对象

Ⅱ、寻址方式

指令寻址	数据寻址
下一条欲执行指令的指令地址	确定本条指令的地址码指明的真实地址

Ⅲ、数据寻址

立即寻址：操作数作为指令的一部分直接写在指令中，这种操作数称为立即数
寄存器寻址: 指令所要的操作数已存储在某寄存器中，或把目标操作数存入寄存器
直接寻址：指令所要的操作数存放在内存中，在指令中直接给出该操作数的有效地址
寄存器间接寻址：操作数在存储器中，操作数的有效地址用SI、DI、BX和BP四个寄存器之一来指定
寄存器相对寻址: 操作数在存储器中，其有效地址是一个基址寄存器(BX、BP)或变址寄存器(SI、DI)的内容和指令中的8位/16位偏移量之和。
基址加变址寻址方式: 操作数在存储器中，其有效地址是-一个基址寄存器(BX.BP)和一个变址寄存器(SI、DI)的内容之和。
相对基址加变址寻址：操作数在存储器中,其有效地址是一个基址寄存器(BX.BP)的值、一个变址寄存器(SI、DI)的值和指令中的8位/16位偏移量之和。

Ⅳ、CISC和RISC

	CISC (Complex)	RISC (Reduced)
指令系统	复杂，庞大	简单，精简
指令数目	一般大于200条	一般小于100条
指令字长	不固定	定长
可访存指令	不加限制	只有Load/Store指令
各种指令执行时间	相差较大	绝大多数一个周期内
各种指令使用频度	相差较大	都比较常用
通用寄存器数量	较少	多
控制方式	绝大多数为微程序控制	绝大多数为组合逻辑控制
指令流水线	可以通过一定方式实现	必须实现

Ⅴ、指令的流水处理

指令控制方式有顺序方式、重叠方式和流水方式三种
流水方式:是指并行性或并发性嵌入计算机系统里的一种形式，它把重复的顺序处理过程分解为若干子过程，每个子过程能在专用的独立模块上有效地并发工作

Ⅵ、流水线的计算

例：若指令流水线把一条指令分为取指、分析和执行三部分,且三部分的时间分别是取指2ns分析2ns ,执行1ns。
那么,流水线周期是多少? 100条指令全部执行完毕需要的时间是多少?
答：（2+2+1）+（100-1）*2
解析：流水线周期为执行时间最长的一段流水线计算公式为: 1条指令执行时间 +(指令条数-1)*流水线周期

流水线的吞吐率(Though Put rate, TP)：是指在单位时间内流水线所完成的任务数量或输出的结果数量。
计算流水线吞吐率的最基本的公式如下： $ TP = \frac {指令条数}{流水线执行时间} $

流水线开始工作后，须经过一定时间才能达到最大吞吐率，这就是建立时间。
若m个子过程所用时间一样，均为to，则建立时间To=m x to。

完成同样一批任务，不使用流水线所用的时间与使用流水线所用的时间之比称为流水线的加速比。
计算流水线加速比的基本公式如下: $ S = \frac {不使用流水线执行时间}{使用流水线执行时间} $

8.存储系统的层次结构

主存一辅存：实现虚拟存储系统，解决了主存容量不够的问题
Cache一主存：解决了主存与CPU速度不匹配的问题

Ⅰ、高速缓存Cache

空间局部性:在最近的未来要用到的信息(指令和数据)，很可能与现在正在使用的信息在存储空间上是邻近的。
- Eg:数组元素、顺序执行的指令代码
时间局部性:在最近的未来要用到的信息，很可能是现在正在使用的信息
- Eg:循环结构里面的指令代码

基于局部性原理，不难想到，可以把CPU目前访问的地址“周围”的部分数据放到Cache中，以提高访问效率。
在计算机的存储系统体系中，Cache是访问速度最快的层次。
使用Cache改善系统性能的依据是程序的局部性原理。

要把主存种的地址映射为Cache存储器里面的地址，地址映像方法有三种

直接映像:就是主存的块与Cache中块的对应关系是固定的。这种方式的优点是地址变换很简单，缺点是灵活性差。
全相联映像:允许主存的任一块可以调入Cache的任一块的空间。这种方式的优点是主存的块调入Cache的位置不受限制，十分灵活。其缺点是无法从主存块号中直接获得Cache的块号，变换比较复杂，速度比较慢。
组相联映像:这种方式是前面两种方式的折中。具体方法是将Cache先分成组再分块组相联映像就是组间采用直接映像方式，而组内的块采用全相联映像方式。

全相联映射：主存物理地址 = 标记 + 块内地址
组相联映射：主存物理地址 = 标记 + 组号 + 块内地址
直接映射：主存物理地址 = 标记 + cache行号 + 块内地址

选择替换算法的目标是使Cache获得最高的命中率。常用的替换算法有以下几种

随机替换(RAND)算法:用随机数发生器产生一个要替换的块号，将该块替换出去。
先进先出(FIFO)算法: 将最先进入的Cache信息块替换出去
近期最少使用(LRU)算法: 将近期最少使用的Cache中的信息块替换出去。这种算法较先进先出算法要好些，但此法也不能保证过去不常用的将来也不常用。
优化替换(OPT)算法: 先执行一次程序，统计Cache的替换情况。有了这样的先验信息，在第二次执行该程序时便可以用最有效的方式来替换，达到最优目的。

Ⅱ、硬盘

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

Ⅲ、总线系统

片内总线
片内总线是芯片内部的总线。它是CPU芯片内部寄存器与寄存器之间、寄存器与ALU之间的公共连接线。
系统总线
系统总线是计算机系统内各功能部件 (CPU、主存、/0接口)之间相互连接的总线。按系统总线传输信息内容的不同，又可分为3类:数据总线、地址总线和控制总线
通信总线

Ⅳ、输入输出技术

CPU与外设之间的数据传送方式

直接程序控制方式直接程序控制方式是指在完成数据的输入/输出中，整个输入/输出过程是在CPU执行程序的控制下完成的。这种方式还可以分为以下两种:

无条件传送方式:无条件地与CPU交换数据。
程序查询方式:先通过CPU查询外设状态，准备好之后再与CPU交换数据

中断方式
直接存储器存取方式直接存储器存取(Direct Memory Access，DMA)方式是在存储器与I/0设备间直接传送数据，即在内存与I/0设备之间传送一个数据块的过程中，不需要CPU的任何干涉，是-种完全由DMA硬件完成1/O操作的方式。

Ⅴ、可靠性

计算机系统的可靠性是指从它开始运行(t=0)到某个时刻t这段时间内能正常运行的概率，用R(t)表示。

串联部件的可靠度=各部件的可靠度的乘积
并联部件的可靠度=1-部件失效率的乘积

二、数据结构

1、基本概念

Ⅰ、什么是数据?

数据:数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。

Ⅱ、数据元素、数据项

数据元素、数据项: 数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位

数据结构是相互之间存在一种或多种特定关系的数据元素的集合

数据结构的三要素

逻辑结构
- 集合：各个元素同属一个集合，别无其他关系
- 线性结构：数据元素之间是一对一的关系。除了第一个元素，所有元素都有唯前驱;除了最后一个元素，所有元素都有唯一后继。
- 树形结构：数据元素之间是一对多的关系
- 图状结构 (网状结构)：数据元素之间是多对多的关系
物理结构(存储结构)
- 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中
- 链式存储：逻辑上相邻的元素在物理位置上可以不相邻
- 索引存储：在存储元素信息的同时，还建立附加的索引表
- 散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希(Hash)存储
数据的运算

Ⅲ、什么是算法?

程序 = 数据结构 + 算法

算法的五个特性

有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。
可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

算法效率的度量

时间复杂度：时间开销与问题规模 n 之间的关系
空间复杂度：空间开销 (内存开销)与问题规模 n 之间的关系

时间复杂度
时间开销与问题规模n的关系 T(n)=O(n)

空间复杂度
无论问题规模怎么变，算法运行所需的内存空间都是固定的常量算法空间复杂度为 S(n)= O(1)
注:S表示“Space"

算法原地工作——算法所需内存空间为常量只需关注存储空间大小与问题规模相关的变量

函数递归调用带来的内存开销
S(n)= O(n) 空间复杂度 = 递归调用的深度 $O(1) < O(log_2 n) < O(n) < O(nlog_2n) < O(n^2) < O(n^3)< O(2^n)< O(n!) < O(n^n)$

2、线性表

逻辑结构
存储 (物理) 结构
- 顺序表(顺序存储)
- 链表(链式存储)
  - 双向链表
  - 循环链表
  - 静态链表
插入删除操作

Ⅰ、线性表定义

线性表是具有相同数据类型的n (n >= 0)个数据元素的有限序列，其中n为表长，当n = 0时线性表是一个空表。若用L命名线性表，则其一般表示为:
L = (a1, a2, … , ai , ai+1, … , an)

几个概念:

ai是线性表中的“第i个”元素线性表中的位序
a1是表头元素;an是表尾元素。
除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。

Ⅱ、插入删除操作

顺序存储: 插入元素前要移动元素以挪出空的存储单元，然后再插入元素删除元素时同样需要移动元素，以填充被删除元素的存储单元。
链式存储:

3、栈和队列

Ⅰ、栈定义

线性表是具有相同数据类型的n (n20)个数据元素的有限序列，其中n为表长，当n =0时线性表是一个空表。若用L命名线性表，则其一般表示为:
L = (a1, a2, … , ai , ai+ 1, … , an)
栈(Stack) 是只允许在一端进行插入或删除操作的线性表。

Ⅱ、队列定义

队列是一种先进先出(FIFO)的线性表，它只允许在表的一端插入元素，而在表的另一端删除元素。在队列中，允许插入元素的一-端称为队尾 (Rear)允许删除元素的一-端称为队头 (Front)。

循环队列

4、串、数组、矩阵和广义表

Ⅰ、串

串是仅由字符构成的有限序列，是取值范围受限的线性表。一般记为S = a1 a2~~~ an，其中S是串名，a1 az an是串值。

空串:长度为零的串，空串不包含任何字符
空格串:由一个或多个空格组成的串。
子串:由串中任意长度的连续字符构成的序列。含有子串的串称为主串。子串在主串中的位置指子串首次出现时，该子串的第-个字符在主串中的位置。空串是任意串的子串。
串相等:指两个串长度相等且对应位置上的字符也相同
串比较:两个串比较大小时以字符的ASCII码值作为依据。比较操作从两个串的第一个字符开始进行，字符的ASCII码值大者所在的串为大;若其中一一个串先结束，则以串长较大者为大。
对串进行的基本操作有以下几种。

赋值操作StrAssign(s,):将串t的值赋给串s。
连接操作Concat(s,t):将串t接续在串s的尾部，形成一个新串
求串长StrLength(s):返回串s的长度。
串比较StrCompare(s,t):比较两个串的大小。
求子串SubString(,tart,len):返回串s中从start开始的、长度为len的字符序列。

串的存储结构

串的顺序存储:定长存储结构
串的链式存储:块链
子串的定位操作通常称为串的模式匹配，它是各种串处理系统中最重要的运算之一。子串也称为模式串。

Ⅱ、数组

存储地址计算

一维数组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

Ⅲ、稀疏矩阵

Ⅳ、广义表

广义表是n个表元素组成的有限序列，是线性表的推广通常用递归的形式进行定义，记做:LS=(ao,a…,an)
注:其中LS是表名，a;是表元素，它可以是表(称做子表)，也可以是数据元素(称为原子)。其中n是广义表的长度(也就是最外层包含的元素个数)，n-0的广义表为空表;而递归定义的重数就是广义表的深度，直观地说，就是定义中所含括号的重数(原子的深度为0，空表的深度为1)。
基本运算:取表头head(Ls)和取表尾tail(Ls)。
若有:LS1=(a，(b,c)，(d,e))
head(LS1)=a
tail(LS1)=( ( b ,c) ,(d , e ) )

5、树和二叉树

Ⅰ、树的基本概念

Ⅱ、二叉树的基本概念

二叉树的重要特性:

在二叉树的第i层上最多有$2^{i-1}$个结点$(i>=1)$;
深度为k的二又树最多有$2^k -1$个结点$(k>=1)$;
对任何一棵二叉树，如果其叶子结点数为$n_0$，度为2的结点数为$n_2$，则$n_o=n_2+1$。
如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层[log2n]+1层，每层从左到右)，则对任一结点$i(1<=i<=n)$，有:

如果$i=1$，则结点$i$无父结点，是二叉树的根;如果$i>1$，则父结点是$[i/2]$;
如果$2i>n$，则结点$i$为叶子结点，无左子结点; 否则，其左子结点是结点$2i$;
如果$2i+1>n$，则结点$i$无右子叶点，否则，其右子结点是结点$2i+1$。

Ⅲ、二叉树的遍历

前序遍历：根左右
中序遍历：左根右
后序遍历：左右根

图中前序遍历结果是?
- 12457836
图中中序遍历结果是?
- 42785136
图中后序遍历结果是?
- 48752631

Ⅳ、反向构造二叉树

由前序序列为ABHFDECG; 中序序列为HBEDFAGC构造叉树。

Ⅴ、树转二叉树

孩子结点一左子树结点
兄弟结点一右孩子结点

Ⅵ、查找二叉树（二叉排序树）

特点: 左孩子小于根，右孩子大于根。例如序列: 89，48，56，112，51，20

插入结点:
- 若该键值结点已存在,则不再插入，如:48
- 若查找二叉树为空树,则以新结点为查找二又树
- 将要插入结点键值与插入后父结点键值比较，就能确定新结点是父结点的左子结点,还是右子结点。
删除结点:
1. 若待删除结点是叶子结点,则直接删除
2. 若待删除结点只有一个子结点,则将这个子结点与待删除结点的父结点直接连接，如: 56。
3. 若待删除的结点p有两个子结点，则在其左子树上，用中序遍历寻找关键值最大的结点s，用结点s的值代替结点p的值，然后删除节点s，节点s必属于上述1、2情况之一，如89。

Ⅶ、构造霍夫曼树(最优)

树的路径长度？
权？
带权路径长度？
树的带权路径长度(树的代价)？
例: 1，2，4，8

例:假设有一组权值5,29,7,8,14,23,3,11请尝试构造哈夫曼树。

Ⅷ、线索二叉树

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

Ⅷ、平衡二叉树

平衡二叉树的提出原因？例：对数列1,5,7,9,8,39,73,88构造排序二叉树，可以构造出多棵形式不同的排序二叉树。

定义:任意结点的左右子树深度相差不超过1，每结点的平衡度只能为-1、0或1。

6、图

Ⅰ、图的基本概念

有向图
无向图
完全图:在无向图中，若每对顶点之间都有一条边相连，则称该图为完全图在有向图中,若每对顶点之间都有二条有向边相互连接,则称该图为完全图。
度，入度与出度

Ⅱ、存储结构 (邻接矩阵)

用一个n阶方阵R来存放图中各结点的关联信息，其矩阵元素Ri定义为: $$ R_{ij} = \begin{cases} 1, & \text{若顶点i到顶点j有邻接边} \\ 0, & \text{若顶点i到顶点j无邻接边} \end{cases} $$

Ⅲ、存储结构 (邻接表)

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

Ⅳ、图的遍历

Ⅴ、拓扑排序

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

上图的拓扑序列有:02143567，01243657，02143657，01243567

Ⅵ、最小生成树

普利姆算法 Prim算法（普利姆算法）普利姆算法查找最小生成树的过程，采用了贪心算法的思想。对于包含 N 个顶点的连通网，普利姆算法每次从连通网中找出一个权值最小的边，这样的操作重复 N-1 次，由 N-1 条权值最小的边组成的生成树就是最小生成树。

克鲁斯卡尔算法
Kruskal算法（克鲁斯卡算法）克鲁斯卡尔算法查找最小生成树的方法是：将连通网中所有的边按照权值大小做升序排序，从权值最小的边开始选择，只要此边不和已选择的边一起构成环路，就可以选择它组成最小生成树。对于 N 个顶点的连通网，挑选出 N-1 条符合条件的边，这些边组成的生成树就是最小生成树。

7、查找

Ⅰ、基本概念

查找-在数据集合中寻找满足某种条件的数据元素的过程称为查找。
查找表(查找结构)-用于查找的数据集合称为查找表，它由同一类型的数据元素(或记录)组成。
数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的关键字查找，查找结果应该是唯一的。
查找长度-在查找运算中，需要对比关键字的次数称为查找长度。
平均查找长度(ASL,Average Search Length)-所有查找过程中进行关键字的比较次数的平均值。
查找
- 静态查找表
  - 顺序查找
  - 折半查找
  - 分块查找
- 动态查找表
  - 二叉排序树
  - 平衡二叉树
  - B-树
- 哈希表

Ⅱ、顺序查找

顺序查找，又叫“线性查找”，通常用于线性表算法思想:从头到 jio 挨个找 (或者反过来也OK)
一般情况下，$c_i = n-i+l$，因此在等概率情况下，顺序查找成功的平均查找长度为 $ASL_{ss} = \sum_{i=1}^n p_ic_i = \frac 1n \sum_{i=1}^n(n-i+1) = \frac{n+1}2$

Ⅲ、折半查找

折半查找，又称“二分查找”，仅适用于有序的顺序表
折半查找在查找成功时关键字的比较次数最多为 $log_2n +1$次。
折半查找的时间复杂度为 $O(log_2n)$。

Ⅳ、分块查找

特点块内无序、块间有序
第一步在索引表中确定待查记录所在的块，第二步在块内顺序查找

Ⅴ、哈希表 (散列表)

散列表(Hash Table)又称哈希表。是一种数据结构，特点是:数据元素的关键字与其存储地址直接相关。若不同的关键字通过散列函数映射到同一个值，则称它们为“同义词”
通过散列函数确定的位置已经存放了其他元素，则称这种情况为“冲突”

解决冲突的方式：
- 开放地址法
- 链地址法
- 再哈希法
- 建立一个公共溢出区

8、排序

Ⅰ、基本概念

排序:就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。

排序方法分类
- 插入类排序
  - 直接插入排序
  - 希尔排序
- 交换类排序
  - 冒泡排序
  - 快速排序
- 选择类排序
  - 简单选择排序
  - 堆排序
- 归并排序
  - 基数排序

Ⅱ、直接插入排序

算法思想:每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中直到全部记录插入完成。

Ⅲ、希尔排序

算法思想:先将待排序表分割成若干形如 L[i,i + d,i + 2d,…,i + kd]的“特殊”子表，对各个子表分别进行直接插入排序。缩小增量d，重复上述过程，直到d=1为止。

Ⅳ、冒泡排序

算法思想:从后往前(或从前往后) 两两比较相邻元素的值，若为逆序 (即A[i-1]>AI)则交换它们，直到序列比较完。称这样过程为“一趟”冒泡排序。

Ⅴ、快速排序

算法思想:在待排序表L[1…n]中任取一个元素pivot作为枢轴 (或基准，通常通过一趟排序将待排序表取首元素)，划分为独立的两部分L[1…k-1]和L[k+1…n]，使得L[1…k-1]中的所有元素小于pivot，L[k+1…n]中的所有元素大于等于 pivot，则pivot放在了其最终位置L(k)上，这个过程称为一次“划分”然后分别递归地对两个子表重复上述过程，直到每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

Ⅵ、简单选择排序

算法思想:每一趟在待排序元素中选取关键字最小的元素加入有序子序列。

Ⅶ、堆排序

设有n个元素的序列$\{K1,K2，… Kn\}$,当且仅当满足下述关系之时，称之为堆。

$ K_i =< K_(2i) $;且$K_i =< K_(2i+1)$
$ K_i >= K_(2i) $;且$K_i >= K_(2i+1)$
其中 1 称为小顶堆，2 称为大顶堆

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

Ⅷ、归并排序

算法思想:把两个或多个已经有序的序列合并成一个
[57 68][52 59][28 72][33 96]
[52 57 59 68][28 33 72 96]
[28 33 52 57 59 68 72 96]

Ⅸ、基数排序

基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法
基数的选择和关键字的分解是根据关键字的类型来决定的。
例如:关键字是十进制数，则按个位、十位来分解。

Ⅹ、评价指标

三、算法设计与分析

1、分治法

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

要求
- 该问题的规模缩小到一定的程度就可以容易地解决。
- 该问题可以分解为若干个规模较小的相同问题。
- 利用该问题分解出的子问题的解可以合并为该问题的解。
- 该问题所分解出的各个子问题是相互独立的。
一般来说，分治算法在每一层递归上都有3个步骤
- 分解。将原问题分解成一系列子问题。
- 求解。递归地求解各子问题。若子问题足够小，则直接求解。
- 合并。将子问题的解合并成原问题的解。

递归:就是在运行的过程中调用自己函数递归调用带来的内存开销 S(n) = O(n)空间复杂度 = 递归调用的深度

2、回溯法

Ⅰ、回溯法一深度优先搜索法

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

3、贪心法

Ⅰ、贪心法—局部最优

总是做出在当前来说是最好的选择，而并不从整体上加以考虑,它所做的每步选择只是当前步骤的局部最优选择，但从整体来说不一定是最优的选择。由于它不必为了寻找最优解而穷尽所有可能解，因此其耗费时间少，一般可以快速得到满意的解，但得不到最优解。也常用于解决最优化的问题用贪心法求解的问题一般具有两个重要的性质

最优子结构。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。问题的最优子结构是该问题可以采用动态规划法或者贪心法求解的关键性质。
贪心选择性质。指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。这是贪心法和动态规划法的主要区别。

4、动态规划法

Ⅰ、动态规划法—子问题不独立(区别分治法)

基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解，每个解都对应于一个值，我们希望找到具有最优值的那个解。当然，最优解可能会有多个，动态规划算法能找出其中的一个最优解。

Ⅱ、动态规划法—整体最优 (区别贪心法)

对一个给定的问题，若其具有以下两个性质，则可以考虑用动态规划法来求解。

最优子结构。如果一个问题的最优解中包含了其子问题的最优解，就说该问题具有最优子结构。当一个问题具有最优子结构时，提示我们动态规划法可能会适用，但是此时贪心策略可能也是适用的。
重叠子问题。指用来解原问题的递归算法可反复地解同样的子问题，而不是总在产生新的子问题。即当一个递归算法不断地调用同一个问题时，就说该问题包含重叠子问题。此时若用分治法递归求解，则每次遇到子问题都会视为新问题，会极大地降低算法的效率，而动态规划法总是充分利用重叠子问题，对每个子问题仅计算一次，把解保存在一个在需要时就可以查看的表中，而每次查表的时间为常数。

四、操作系统

1、基本概念

基本概念
操作系统(Operating System，OS)是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分，以提供给用户和其他软件方便的接口和环境，它是计算机系统中最基本的系统软件。

功能和目标

作为系统资源的管理者
向上层提供方便易用的服务
作为最接近硬件的层次

特征

并发
共享
虚拟
异步

发展与分类

手工操作阶段
批处理阶段
- 单道批处理系统
- 多道批处理系统(操作系统开始出现)
分时操作系统
实时操作系统
网络操作系统
分布式操作系统
个人计算机操作系统

2、进程管理

Ⅰ、状态转换图

进程正在被创建时，它的状态是“创建态”在这个阶段操作系统会为进程分配资源、初始化PCB。便进入“就绪态”处于就绪态的进程已经具备运行条件
当进程创建完成后但由于没有空闲CPU，就暂时不能运行。
如果一个进程此时在CPU上运行，那么这个进程处于“运行态”，CPU会执行该进程对应的程序(执行指令序列)。
在进程运行的过程中，可能会请求等待某个事件的发生(如等待某种系统资源的分配，或者等待其他进程的响应)。在这个事件发生之前，进程无法继续往下执，当CPU空闲时行，此时操作系统会让这个进程下CPU，并让它进入“阻塞态”又会选择另一个“就绪态”进程上CPU运行。
一个进程可以执行exit系统调用，请求操作系统终止该进程。此时该进程会进“终止态”，操作系统会让该进程下CPU,并回收内存空间等资源，最后还要回收该进程的PCB。当终止进程的工作完成之后，这个进程就彻底消失了。

Ⅱ、前驱图

Ⅲ、进程同步机制

进程具有异步性的特征。异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。
看一个例子:进程通信一管道通信

读进程和写进程并发地运行，由于并发必然导致异步性，因此“写数据”和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中又必须按照“写数据一读数据”的顺序来执行的。如何解决这种异步问题，就是“进程同步机制”所讨论的内容。

Ⅳ、进程互斥机制

进程的“并发”需要“共享”的支持。各个并发执行的进程不可避免的需要共享一些系统资源(比如内存，又比如打印机、摄像头这样的I/0设备)

我们把一个时间段内只允许一-个进程使用的资源称为临界资源。许多物理设备(比如摄像头、打印机)者属于临界资源。此外还有许多变量、数据内存缓冲区等都属于临界资源。

对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则:

空闲让进临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
忙则等待。当己有进程进入临界区时，其他试图进入临界区的进程必须等待
有限等待。对请求访问的进程，应保证能在有限时间内进入临界区(保证不会饥饿)
让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待

Ⅴ、信号量机制

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。
信号量其实就是一个变量(可以是一个整数，也可以是更复杂的记录型变量)，可以用一个信号量来表示系统中某种资源的数量，比如:系统中只有一台打印机，就可以设置一个初值为1的信号量。
原语:是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。
一对原语: wait(S) 原语和signal(S)原语，可以把原语理解为我们自己写的函数，函数名分别为wait和signal，括号里的信号量S其实就是函数调用时传入的一个参数。
wait、signal原语常简称为P、V操作(来自荷兰语proberen和verhogen)。因此，做题的时候常把wait(S)、signal(S)两个操作分别写为P(S)、V(S)。

实现进程互斥
实现进程同步
实现进程的前驱关系

不要一头钻到代码里，个信号量对应要注意理解信号量背后的含义:种资源信号量的值=这种资源的剩余数量(信号量的值如果小于0，说明此时有进程在等待这种资源)。

Ⅵ、PV操作

P(S)-申请一个资源S如果资源不够就阻塞等待，即S-1。
V(S)-释放一个资源S，如果有进程在等待该资源，则唤醒一个进程，即S+1。

Ⅶ、PV操作实现前驱操作

进程P1中有句代码S1，P2中有句代码S2，P3中有句代码S3….P6中有句代码S6。这些代码要求按如下前驱图所示的顺序来执行:
其实每一对前驱关系都是一个进程同步问题(需要保证一前一后的操作)
因此:

要为每一对前驱关系各设置一个同步信号量
在“前操作”之后对相应的同步信号量执行V操作
在“后操作”之前对相应的同步信号量执行p操作

Ⅷ、死锁产生的必要条件

产生死锁必须同时满足以下四个条件，只要其中任一条件不成立，死锁就不会发生

互斥条件:只有对必须互斥使用的资源的争抢才会导致死锁(如哲学家的筷子打印机设备)。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的(因为进程不用阻塞等待这种资源)。
不剥夺条件:进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
请求和保持条件: 进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放
循环等待条件:存在一种进程源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。

Ⅸ、死锁的处理策略

预防死锁:破坏死锁产生的四个必要条件中的一个或几个。
避免死锁:用某种方法防止系统进入不安全状态，从而避免死锁( 银行家算法)。
死锁的检测和解除。允许死锁的发生不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁

银行家算法 安全序列:就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。
如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后，可能所有进程都无法顺利的执行下去。
如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全就有安全序列，不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态。
因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态以此决定是否答应资源分配请求。这也是“银行家算法”的核心思想。

3、存储管理

Ⅰ、内存的分配与回收

连续分配管理方式
- 单一连续分配
- 固定分区分配
- 动态分区分配
  - 首次适应算法
  - 最佳适应算法
  - 最差适应算法
  - 邻近适应算法

Ⅱ、首次适应算法

算法思想:每次都从低地址开始查找，找到第一个能满足大小的空闲分区。如何实现:空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

Ⅲ、最佳适应算法

算法思想:由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区,即，优先使用更小的空闲区。如何实现:空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第-个空闲分区。

Ⅳ、最差适应算法

算法思想:为了解决最佳适应算法的问题，即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用如何实现:空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第-一个空闲分区。

Ⅴ、邻近适应算法

算法思想:首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲.分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。如何实现:空闲分区以地址递增的顺序排列(可排成-一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

Ⅵ、分页存储管理

Ⅶ、分段存储管理

Ⅷ、段页式存储管理

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

Ⅸ、页面置换算法

页面置换算法
- 最佳置换算法 (OPT)
- 先进先出置换算法 (FIFO)
- 最近最久未使用置换算法 (LRU)
- 时钟置换算法(CLOCK)

最佳置换算法 (OPT): 每次选择淘汰的是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。
先进先出置换算法 (FIFO)：每次选择淘汰的页面是最早进入内存的页面。
最近最久未使用置换算法 (LRU)：每次淘汰的页面是最近最久未使用的页面。

4、文件管理

Ⅰ、文件目录

文件目录
- 文件控制块
  - 文件控制块(FCB)是系统为管理文件而设置的一一个数据结构。FCB是文件存在的标志，它记录了系统管理文件所需要的全部信息。
- 目录结构
  - 一级目录结构
  - 二级目录结构
  - 多级目录(树形目录结构)
    - 绝对路径
    - 相对路径

文件路径

Ⅱ、文件的结构

文件的结构
- 文件的逻辑结构
  - 无结构的流式文件
  - 结构的记录式文件
- 文件的物理结构 (文件的分配方式)
  - 连续分配
  - 链接分配
  - 索引分配

*索引分配

Ⅲ、空闲存储空间的管理（位示图法）

空闲区表。将外存空间上一个连续未分配区域称为空闲区。操作系统为外存上所有空闲区建立一张空闲表来管理空闲存储空间。
位示图。这种方法是在外存上建立一张位示图，记录文件存储器的使用情况。每一位对应文件存储器上的一个物理块，取值0和1分别表示空闲和占用。
空闲块链。每个空闲物理块中都有指向下一个空闲物理块的指针，所有空闲物理块构成-一个链表链表的头指针放在文件存储器的特定位置(如管理块中)。
成组链接法。在UNIX系统中，将空闲块分成若干组，每100个空闲块为一组，每组的第一个空闲块登记下一组空闲块的物理盘块号和空闲块总数，假如一个组的第一个空闲块号等于0,就意味着该组是最后一组，即无下一组空闲块。

5、设备管理

Ⅰ、I/O设备基本概念

Ⅱ、I/O控制方式

6、微内核操作系统

	实质	优点	缺点
单体内核	将图形、设备驱动及文件系统等功能全部在内核中实现，运行在内核状态和同一地址空间。	减少进程间通信和状态切换的系统开销，获得较高的运行效率	内核庞大，占用资源较多且不易剪裁系统的稳定性和安全性不好.
微内核	只实现基本功能，将图形系统、文件系统、设备驱动及通信功能放在内核之外	内核精练，便于剪裁和移植。系统服务程序运行在用户地址空间，系统的可靠性稳定性和安全性较高。可用于分布式系统	用户状态和内核状态需要频繁切换，从而导致系统效率不如单体内核

五、计算机网络基础

1、计算机网络的分类

2、七层网络体系结构

1、2、3重点记忆

3、网络的设备

4、TCP/IP协议族

TCP/IP作为Internet的核心协议，被广泛应用于局域网和广域网中，目前已成为事实上的国际标准。

TCP/IP分层模型：TCP/IP协议是Internet的基础和核心，和OSI参考模型一样，也是采用层次体系结构，从上而下分为应用层、传输层、网际层和网络接口层。
网络接口层协议
网际层协议-IP
ARP和RARP：地址解析协议(Address Resolution Protocol,ARP)及反地址解析协议(RARP)。ARP的作用是将IP地址转换为物理地址，RARP的作用是将物理地址转换为IP地址。
网际层协议-ICMP
传输层协议-TCP：TCP(Transmission Control Protocol,传输控制协议)为应用程序提供了一个可靠的、面向连接的数据传输服务。
传输层协议-UDP：用户数据报协议(User Datagram Protocol, UDP)是一种不可靠的、无连接的协议可以保证应用程序进程间的通信。TCP有助于提供可靠性，而UDP则有助于提高传输的高速率性。

TCP与UDP区别

TCP面向连接;UDP是无连接的
TCP 提供可靠的服务，通过TCP连接传送的数据，无差错、不丢失、不重复，且按序到达UDP尽最大努力交付，不保证可靠交付。
TCP面向字节流;UDP是面向报文的，没有拥塞控制，因此网络出现拥塞不会使源主机的发送速率降低。
每一条TCP连接只能是点到点的;UDP支持一对一、一对多、多对一和多对多的交互通信
TCP首部开销20字节;UDP的首部开销小，只有8个字节;
TCP的逻辑通信信道是全双工的可靠信道;UDP则是不可靠信道，整体来看UDP开销较小

5、IP地址和IPv6简介

IP地址的长度为32位，分为4段，每段8位，可以用十进制数和二进制数表示。每段数字范围为0~255，段与段之间用句点隔开。IP 地址由两部分组成，一部分为网络地址，另一部分为主机地址。

IP 地址分为 A、B、C、D、E 5类。

A 类 IP 地址。由1个字节的网络地址和 3 个字节的主机地址组成，网络地址的最高位必须是“0”，地址范围是 1.0.0.1~126.255.255.254。可用的 A 类网络有 126 个，每个网络能容纳 224-2 个主机。
B 类 IP 地址。由 2个字节的网络地址和 2 个字节的主机地址组成，网络地址的最高位必须是“10”，地址范围是 128.0.0.0~191.255.255.254。可用的 B 类网络有 16384 个，每个网络能容纳 65534 个主机。
C 类IP 地址。由 3 个字节的网络地址和 1 个字节的主机地址组成，网络地址的最高位必须是“110”，地址范围是 192.0.1.1~223.255.255.254。可用的 C 类网络有 22-2 个，每个网络能容纳 254 个主机。
D 类IP 地址。第一个字节以“1110”开始，是专门保留的地址。它并不指向特定的网络，目前这一类地址被用在多点广播(Multicast)中。多点广播地址用来一次寻址一组计算机.它标识共享同一协议的一组计算机。D 类IP 地址的地址范围是 224.0.0.1239.255.255.254
E 类IP地址。以“1111”开始，为将来使用保留，仅做实验和开发用。

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

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

6、Internet服务

DNS域名服务
- DNS用的是UDP端口
- 端口号是53
远程登录服务
- 端口号一般是23
- Telnet协议用的是TCP端口，
电子邮件服务电子邮件就是利用计算机进行信息交换的电子媒体信件。所用协议有简单邮件传送协议SMTP和用于接收邮件的POP3协议，
- 两者均利用TCP端口
- SMTP所用的端口号是25
- POP3所用的端口号是110
WWW服务
- WWW服务是一种交互式图形界面的Internet 服务，具有强大的信息连接功能。
- WWW用的是TCP端口，端口号是80
文件传输服务文件传输服务用来在计算机之间传输文件。
- 在客户机与服务器的内部建立两条TCP连接:
- 一条是控制连接，主要用于传输命令和参数(端口号是21)
- 另一条是数据连接，主要用于传送文件 (端口号是20)

六、数据库基础知识

1、基本概念*

数据库 (Database，缩写为DB)是指长期存储在计算机内的、有组织的、可共享的数据集合。数据库中的数据按一定的数据模型组织、描述和存储，具有较小的几余度、较高的数据独立性和易扩展性，并可为各种用户共享。
数据库管理系统(DatabaseManagement System，DBMS)是数据库系统的核心软件要在操作系统的支持下工作，解决如何科学地组织和存储数据、如何高效地获取和维护数据的系统软件问题。其主要功能包括数据定义功能、数据操纵功能、数据库的运行管理、数据组织存储、管理和数据库的建立与维护。

Ⅰ、DBMS的特征与分类

DBMS的特征

数据结构化且统一管理
有较高的数据独立性
提供数据控制功能

DBMS 的分类

关系数据库系统:是支持关系模型的数据库系统。
面向对象的数据库系统:是支持以对象形式对数据建模的数据库系统。
对象关系数据库系统:在传统的关系数据模型基础上，提供元组、数组、集合等更丰富的数据类型以及处理新的数据类型操作的能力，这样形成的数据模型称为对象关系数据模型。基于对象关系数据模型的DBS称为对象关系数据库系统。

2、数据库三级模式两级映像*

数据库系统采用三级模式结构，这是数据库管理系统内部的系统结构。

外模式：也称用户模式或子模式，是用户与数据库系统的接口，是用户用到的那部分数据的描述，由若干个外部记录类型组成。描述外模式的数据定义语言称为外模式DDL。
概念模式：也称模式，是数据库中全体数据的逻辑结构和特征的描述，它由若干个概念记录类型组成，只涉及行的描述，不涉及具体的值。概念模式的一个具体值称为模式的一个实例，同一个模式可以有很多实例。
内模式：也称存储模式是数据物理结构和存储方式的描述是数据在数据库内部的表示方式定义所有的内部记录类型索引和文件的组织方式，以及数据控制方面的细节。描述内模式的数据定义语言称为内模式DDL。
外模式/模式映像：该映像存在于外部级和概念级之间，实现了外模式到概念模式之间的相互转换。
模式/内模式映像：该映像存在于概念级和内部级之间，实现了概念模式到内模式之间的相互转换，DBMS的两级映像功能保证了数据的独立性。

3、数据库的分析与设计过程*

4、数据模型*

模型就是对现实世界特征的模拟和抽象。
数学模型是对现实世界数据特征的抽象。模型就是对现实世界特征的模拟和抽象
数学模型是对现实世界数据特征的抽象
数据模型是用来描述数据的一组概念和定义
数据模型的三要素是数据结构、数据操作、数据的约束条件
数据结构:是所研究的对象类型的集合，是对系统静态特性的描述
数据操作:是对数据库中各种对象的实例 (值)允许执行的操作的集合包括操作及操作规则。数据操作是对系统动态特性的描述。
数据的约束条件:是一组完整性规则的集合。对于具体的应用数据必须遵循特定的语义约束条件，以保证数据的正确、有效、相容。

E-R模型
实体-联系模型简称E-R模型，所采用的3个主要概念是实体、联系和属性。

关系模型 关系数据库系统采用关系模型作为数据的组织方式，在关系模型中用表格结构表达实体集以及实体集之间的联系，其最大特色是描述的一致性。
关系模型是由若干个关系模式组成的集合。一个关系模式相当于一个记录型，对应于程序设计语言中类型定义的概念。
关系模型的优点是：概念单一，存储路径对用户是透明的，所以具有更好的数据独立性和安全保密性，简化了程序的开发和数据库的建立工作。
关系模式中有下划线的属性是主键。

5、关系代数

数据库的4个关系模式 数据库的4个关系模式如下

候选码 (键): 若关系中的某一属性或属性组的值能唯一标识一个元组，则称该属性或属性组为候选码。
主码 (键)：若一个关系有多个候选码，则选定其中一个为主码。
主属性：包含在任何候选码中的诸属性称为主属性。不包含在任何候选码中的属性称为非主属性。
外码(键)：如果公共属性在一个关系中是主属性，那么这个公共属性被称为另一个关系的外码。由此可见，外码表示了两个关系之间的相关联系。
全码：若关系模式的所有属性组都是这个关系模式的候选码，则称为全码。

关系的三种类型

基本关系(通常又称为基本表、基表)：是实际存在的表，它是实际存储数据的逻辑表示。
查询表：查询结果对应的表。
视图表：是由基本表或其他视图表导出的表。由于它本身不独立存储在数据库中，数据库中只存放它的定义，所以常称为虚表

七种基本运算

并
交
差
笛卡尔积
投影（符号 $\Omega$）
选择（符号 $\Sigma$）
联接

关系代数表达式查询优化的原则如下：

提早执行选取运算。对于有选择运算的表达式，应优化成尽可能先执行选择运算的等价表达式，以得到较小的中间结果，减少运算量以及从外存读块的次数。
合并乘积与其后的选择运算为连接运算。
将投影运算与其后的其他运算同时进行，以避免重复扫描关系。
将投影运算和其前后的二目运算结合起来，因为没有必要为去掉某些字段再扫描一关系。
在执行连接前对关系适当地预处理，就能快速地找到要连接的元组。
存储公共子表达式。对于有公共子表达式的结果应存于外存（中间结果），这样，当从外存读出它的时间比计算的时间少时，就可节约操作时间。

6、数据库完整性约束

完整性规则提供了一种手段来保证当授权用户对数据库作修改时不会破坏数据的一致性，完整性规则是为了防止对数据的意外破坏。
关系模型的完整性规则是对关系的某种约束条件。完整性共分为3类:

规实体完整性：规定基本关系R的主属性A不能取空值。
参照完整性：若F是基本关系R的外码，它与基本关系S的主码相对应(基本关系R和S不一定是不同的关系)，则对于R中每个元组在F上的值必须为:或者取空值(F的每个属性值均为空值)，或者等于S中某个元组的主码值。
用户定义完整性：就是针对某一具体的关系数据库的约束条件，反映某一具体应用所涉及的数据必须满足的语义要求，由应用的环境决定。

7、关系型数据库SQL简介

SQL是在关系数据库中最普遍使用的语言，它不仅包含数据查询功能还包括插入、删除、更新和数据定义功能。
SQL具有综合统一、高度非过程化、面向集合的操作方式，两种使用方式，语言简洁且易学易用等特点。
SOL支持关系数据库的三级模式结构:视图对应外模式、基本表对应模式、存储文件对应内模式。

8、关系数据库的规范化

Ⅰ、函数依赖

Ⅱ、求候选码 (键)

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

Ⅲ、规范化理论（非规范化存在的问题）

非规范化的关系模式，可能存在的问题包括

数据冗余
更新异常
插入异常
删除异常

关系数据库设计的方法之一就是设计满足适当范式的模式通常可以通过判断分解后的模式达到几范式来评价模式规范化的程度。
范式有1NF、2NF、3NF、BCNF (巴斯克斯范式)4NF和5NF，其中1NF级别最低。这几种范式之间有 $ 5NF \subset 4NF \subset BCNF \subset 3NF \subset 2NF \subset 1NF $成立。
通过分解，可以将一个低一级范式的关系模式转换成若干个高一级范式的关系模式，这种过程叫作规范化。

$1NF$ (第一范式)
若关系模式R的每一个分量都是不可再分的数据项，则关系模式 $R$ 属于第一范式(1NF)。
$2NF$ (第二范式)
若关系模式$R \in 1NF$，目每一个非主属性完全依赖于主键，则关系模式$R\in 2NF$。换句话说，当1NF消除了非主属性对码的部分函数依赖，则称为2NF。
$3NF$ (第三范式)
若关系模式R(U，F)中不存在这样的码X、属性组Y及非主属性Z(Z不属于Y)，使得$X \to Y$，$Y \not\to X$，$Y \to Z$ 成立，则称关系模式$R \in 3NF$。当2NF消除了非主属性对码的传递函数依赖，则称为3NF。3NF的模式必是2NF的模式。产生冗余和异常的两个重要原因是部分依赖和传递依赖。
$BCNF$ (巴克斯范式)
若关系模式 $R \in 1NF$，若$X \to Y$，且Y属于X，X必含有码，则关系模式 $R \in BCNF $。
换句话说，当 3NF 消除了主属性对码的部分和传递函数依赖，则称为 BCNF。
一个满足 BCNF 的关系模式应具有以下性质。
- 所有非主属性对每一个码都是完全函数依赖。
- 所有非主属性对每一个不包含它的码也是完全函数依赖。
- 没有任何属性完全函数依赖于非码的任何一组属性。

关系模式分解 对一个给定的模式进行分解，使得分解后的模式是否与原来的模式等价有3种情况:

分解具有无损连接性。
分解要保持函数依赖。
分解既要有无损连接性，又要保持函数依赖。

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

9、数据库的控制功能

Ⅰ、事务管理

事务是一个操作序列，是数据库环境中不可分割的逻辑工作单位。
事务的4个特性是:原子性、一致性、隔离性和持久性

原子性:事务的所有操作在数据库中要么全做，要么全都不做
一致性:一个事务独立执行的结果将保持数据的一致性，即数据不会因为事务的执行而遭受破坏。
隔离性:一个事务的执行不能被其他事务干扰。
持久性:一个事务一旦提交，它对数据库中数据的改变必须是永久的，即便系统出现故障时也是如此。

Ⅱ、并发控制

并发控制的主要技术是封锁

排他锁(X锁):又称写锁，若事务T对数据对象A加上X锁，则只允许T读取和修改A，其他事务都不能再对A加任何类型的锁，直到T释放A上的锁。
共享锁(S锁):又称读锁，若事务T对数据对象A加上S锁，则只允许T读取A，，但不能修改A，其他事务只能再对A加S锁，直到T释放A上的S锁。

Ⅲ、备份和恢复

人为错误、硬盘损坏、计算机病毒、断电或是天灾人祸等都有可能造成数据的丢失，所以应该强调备份的重要性。

静态转储和动态转储。静态转储是指在转储期间不允许对数据库进行任何存取、修改操作:动态转储是指在转储期间允许对数据库进行存取、修改操作，因此，转储和用户事务可并发执行。
海量转储和增量转储。海量转储是指每次转储全部数据，增量转储是指每次只转储上次转储后更新过的数据。
日志文件。在事务处理的过程中，DBMS把事务开始、事务结束以及对数据库的插入、删除和修改的每一次操作写入日志文件。一旦发生故障，DBMS的恢复子系统便利用日志文件撤销事务对数据库的改变，回退到事务的初始状态。因此，DBMS利用日志文件来进行事务故障恢复和系统故障恢复，并可协助后备副本进行介质故障恢复。

10、数据仓库与数据挖掘基础

数据仓库(Data Warehouse),可简写为DW或DWH,数据仓库，是为了企业所有级别的决策制定计划过程，提供所有类型数据类型的战略集合。它出于分析性报告和决策支持的目的而创建。为需要业务智能的企业,为需要指导业务流程改进、监视时间，成本，质量以及控制等。数据仓库是依照分析需求、分析维度、分析指标进行设计的。

数据仓库是一个面向主题的、集成的、相对稳定的、反映历史变化的数据集合，它用于支持企业或组织的决策分析处理。是为了便于多维分析和多角度展现而将数据按特定的模式进行存储所建立起来的关系型数据库，它的数据基于OLTP源系统。

数据挖掘(Data Mining)就是从大量的数据中，提取隐藏在其中的，事先不知道的但潜在有用的信息的过程。数据挖掘的目标是建立一个决策模型，根据过去的行动数据来预测未来的行为。

分类

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

方法

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

11、大数据基本概念

大数据:一种规模大到在获取、存储、管理、分析方面大大超出了传统数据库软件工具能力范围的数据集合，具有海量的数据规模、快速的数据流转、多样的数据类型和价值密度低四大特征。

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

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

七、程序设计语言基础知识

1、基本概念

Ⅰ、低级语言和高级语言

低级语言: 通常称机器语言和汇编语言为低级语言。机器语言是指用0、1字符串组成的机0器指令序列，是最基本的计算机语言。汇编语言是指用符号表示指令的语言
高级语言：是从人类的逻辑思维角度出发、面向各类应用的程序语言，其抽象程度大大提高，需要编译成特定机器上的目标代码才能执行。这类语言与人们使用的自然语言比较接近大大提高了程序设计的效率。

程序设计语言的定义一般都涉及语法、语义、语用和语境等方面

语法:由程序设计语言的基本符号组成程序中的各个语法成分的一组规则，其中由基本字符构成的符号书写规则称为词法规则，由符号构成语法成分的规则称为语法规则。程序语言的语法可通过形式语言进行描述。
语义:程序语言中按语法规则构成的各个语法成分的含义，可分为静态语义和动态语义
语用:表示构成语言的各个记号和使用者的关系，涉及符号的来源、使用和影响。
语境:理解和实现程序设计语言的环境，包括编译环境和运行环境。

Ⅱ、程序设计语言的分类

命令式程序设计语言
命令式程序设计语言是基于动作的语言，在这种语言中，计算被看作是动作的序列.命令式语言族开始于Fortran Pascal和C语言，体现了命令式程序设计的关键思想。
面向对象的程序设计语言
面向对象的程序设计在很大程度上应归功于从模拟领域发展而来的Simua提出了对象和类的概念。C++、Java和Smalltalk是面向对象程序设计语言的代表
函数式程序设计语言函数式程序设计语言是一类以2-演算为基础的语言。该语言的代表是LISP其中大量使用了递归。
逻辑型程序设计语言逻辑型程序设计语言是一类以形式逻辑为基础的语言。该语言的代表是建立在关系理论和一阶谓词理论基础上的Prolog

2、编译与解释

汇编语言是为特定的计算机或计算机系统设计的面向机器的符号化的程序设计语言。用汇编语言编写的程序称为汇编语言源程序。汇编语言源程序由若干条语句组成。一个程序中可以有3类语句:指令语、伪指令语句和宏指令语句。

编译程序的功能是把用高级语言书写的源程序翻译成与之等价的目标程序。编译过程划分成词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段，实际的编译器可能会将其中的某些阶段结合在一起进行处理。

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

词法分析阶段的任务是:对源程序从前到后(从左到右)逐个字符进行扫描，从中识别出一个个“单词”符号。“单词”符号是程序设计语言的基本语法单位，如关键字、标识符等。
语法分析阶段的任务是:在词法分析的基础上，根据语言的语法规则将单词符号序列分解成各类语法单位，如“表达式”“语”和“程序”等词法分析和语法分析本质上都是对源程序的结构进行分析。
语义分析阶段主要是: 审查源程序是否存在语义错误，并收集类型信息供后面的代码生成阶段使用，只有语法和语义都正确的源程序才能翻译成正确的目标代码。语义分析的一个主要工作是进行类型分析和检查。
中间代码生成阶段的工作:是根据语义分析的输出生成中间代码。
代码优化阶段的任务是:对前一阶段产生的中间代码进行变换或进行改造，目的是使生成的目标代码更为高效，即省时间和省空间
目标代码生成阶段的任务是:把中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或汇编指令代码。这是编译的最后阶段，它的工作与具体的机器密切相关。

3、文法

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

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

Ⅰ、语法推导树

棵语法树应具有以下特征:

每个结点都有一个标记，此标记是V的一个符号；
根的标记是S;
若一结点n至少有一个它自己除外的子孙，并且有标记A，则A肯定在V中;
如果结点n的直接子孙，从左到右的次序是结点n,n2,..k，其标记分别是: A,A，”,A，那么A>A1,Az””A，一定是P中的一个产生式。

4、有限自动机

$M=(S,\Sigma,\delta,S0,Z)$

S是一个有限集，每个元素为一个状态
$\Sigma$是一个有穷字母表，每个元素为一个输入字符
$\delta$是转换函数:是一个单值对照
S0属于S，是其唯一的初态
Z是一个终态集(可空)

有限状态自动机可以形象地用状态转换图表示，设有限状态自动机: $DFA=(\lbrace S,A,B,C,f\rbrace,\lbrace 1,0 \rbrace, \delta ,S, \lbrace f \rbrace)$ 其中: $\delta(S,0)=B,\delta(S,1)=A,\delta(A,0)=f, \delta(A,1)= C,\delta(B,0)= C,\delta(B,1)=f,\delta(C,0)=f,\delta(C,1)=f$

5、正规式

有限自动机的另外一种表达形式
正规式是描述程序语言单词的表达式，对于字母$\Sigma$，其上的正规式及其表示的正规集可以递归定义如下。

E是一个正规式，它表示集合L(e)={e》。
若a是$\Sigma$上的字符，则a是一个正则式，它所表示的正规L(a)={a}
若正规式r和s分别表示正规集L(r)=L(s)，则
- $r|s$是正规式，表示集合$L(r) \bigcup L(s)$;
- $r*s$是正规式，表示集合L(r)L(s);
- r是正规式，表示集合(L(r));
- (r)是正规式，表示集合L(r)。

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

6、表达式

就是利用树的遍历来求前缀、中缀和后缀表达式。

前缀表达式（根左右）：(+ab)
中缀表达式（左根右）：(a+b)
后缀表达式（左右根）：(ab+)

7、传值与引用 (传址)

传值调用:形参取的是实参的值，形参的改变不会导致实参的值发生改变
引用(传址)调用:形参取的是实参的地址即相当于实参存储单元地址的引用因此其值改变的同时就改变了实参的值。

8、各种程序语言特点

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

八、软件工程基础知识

1、软件工程概述

Ⅰ、软件生存周期

同任何事物一样，软件也有一个孕育、诞生、成长、成熟、衰亡的生存过程，我们称其为计算机软件的生存周期。通常，软件生存周期包括可行性分析、项目开发计划、需求分析、设计(概要设计和详细设计)、编码、测试、维护等活动。

可行性分析:由软件开发方与需求方共同讨论，主要确定软件的开发目标及其可行性。
需求分析：在确定软件开发可行的情况下，对软件需要实现的各个功能进行详细分析。主要解决“做什么”的问题。
概要设计：主要根据需求分析的结果，对整个软件系统进行设计，如系统框架设计、数据库设计等
详细设计：是对每个模块完成的功能进行具体描述，要把功能转变为精确的、结构化的过程。
程序编码: 将软件设计的结果转换成计算机可运行的程序代码。在程序编码时，必须要制定统一符合标准的编写规范，以保证程序的可读性、易维护性，提高程序的运行效率。
软件测试:在软件设计完成后要经过严密的测试，以发现软件在整个设计过程中存在的问题并加以纠正。
维护:在软件开发完成并投入使用后，由于各种原因，软件会不能继续适应用户的要求。延续软件的使用寿命，就要对软件进行维护，包括纠错性维护和改进性维护两个方面。

Ⅱ、能力成熟度模型 (CMM)

软件能力成熟度模型(CMM)将软件组织的过程能力分成5个成熟度级别:初始可重复级、已定义级、已管理级和优化级。按照成熟度级别由低到高，软件开级发生产精度越来越高，每单位工程的生产周期越来越短。

初始级：软件过程是无序的，有时甚至是混乱的，对过程几乎没有定义，成功取决于个人努力。
可重复级：建立了基本的项目管理过程来跟踪费用进度和功能特性，制定了必要的过程纪律，能重复早先类似应用项目取得的成功。
已定义级：已将软件管理和工程两方面的过程文档化、标准化，并综合成该组织的标准软件过程。所有项目均使用经批准、剪裁的标准软件过程来开发和维护软件。
已管理级：收集对软件过程和产品质量的详细度量，对软件过程和产品都有定量的理解和控制。
优化级：过程的量化反馈和先进的新思想、新技术促使过程不断改进

Ⅲ、能力成熟度模型 (CMMI)

阶段式模型：结构类似于CMM，它关注组织的成熟度。有5个成熟度等级
- 初始的：过程不可预测且缺乏控制
- 已管理的：过程为项目服务
- 已定义的：过程为组织服务
- 定量管理的：过程已度量和控制
- 优化的：集中于过程改进
连续式模型:关注每个过程域的能力，一个组织对不同的过程域可以达到不同的过程域能力等级。CMMI中包括6个过程域能力等级，等级号为0~5。
- CLO(未完成的): 过程域未执行或未得到CL1中定义的所有目标。
- CL1(已执行的)：其共性目标是过程将可标识的输入工作产品转换成可标识的输出工作产品，以实现支持过程域的特定目标。
- CL2 (已管理的)：其共性目标集中于已管理的过程的制度化。根据组织级政策规定过程的运作将使用哪个过程，项目遵循已文档化的计划和过程描述，所有正在工作的人都有权使用足够的资源，所有工作任务和工作产品都被监控控制和评审。
- CL3(已定义级的)：其共性目标集中于已定义的过程的制度化。过程是按照组织的剪裁指南从组织的标准过程集中剪裁得到的，还必须收集过程资产和过程的度量,并用于将来对过程的改进。
- CL4(定量管理的)：其共性目标集中于可定量管理的过程的制度化。使用测量和质量保证来控制和改进过程域，建立和使用关于质量和过程执行的定量目标作为管理准则。
- CL5(优化的)：使用量化(统计学)手段改变和优化过程域，以满足客户要求的改变和持续改进计划中的过程域的功效。

Ⅳ、统一过程模型

统一过程(UP)模型：是一种“用例和风险驱动，以架构为中心，迭代并且增量”的开发过程，由UML方法和工具支持。迭代的意思是将整个软件开发项目划分为许多个小的“袖珍项目”，每个“袖珍项自”都包含正常软件项目的所有元素计划、分析和设计、构造、集成和测试，以及内部和外部发布。统一过程包括4个阶段：初始阶段、精化阶段、构建阶段、移交阶段

初始阶段$\to$生命周期目标
精化阶段$\to$生命周期架构
构建阶段$\to$初始运作功能
移交阶段$\to$产品发布。

2、软件开发模型

瀑布模型：迭代模型/迭代开发方法
- 优点：可强迫开发人员采用规范的方法（如结构化技术）；严格地规定了每个阶段必须提交的文档；要求每个阶段交出的所有产品都必须经过质量保证小组的仔细验证。
- 缺点：瀑布模型是由文档驱动，在可运行的软件产品交付给用户之前，用户只能通过文档来了解产品是什么样的。瀑布模型几乎完全依赖于书面的规格说明，很可能导致最终开发出的软件产品不能真正满足用户的需要。也不适合需求模糊的系统。
演化模型：快速应用开发，主要用于对软件需求缺乏准确认识的情况。
增量模型：构件组装模型/基于构件的开发方法，融合了瀑布模型的基本成分和原型实现的迭代特征，该模型采用随着日程时间的进展而交错的线性序列，每一个线性序列产生软件的一个可发布的增量。
螺旋模型：统一过程/统一开发方法。将瀑布模型和演化模型相结合就成了螺旋模型。这种模型综合了瀑布模型和演化模型的优点。
- 螺旋模型包括4个方面的活动:
- 制订计划
- 风险分析
- 实施工程
- 客户评估
快速原型模型：敏捷开发方法
V模型：基于架构的开发方法，瀑布模型的变体。
喷泉模型：模型驱动的开发方法，喷泉模型是一种以用户需求为动力，以对象为驱动的模型，主要用于采用对象技术的软件开发过程，具有迭代和无间隙特性。迭代意味着模型中的开发活动常常需要重复多次，在迭代中不断完善软件系统。无间隙是指在开发活动之间不存在明显的边界，允许开发活动交叉、迭代地进行。
基于构件的开发模型：本质上是演化模型，以选代方式构件软件。是指利用预先包装的构件来构造应用系统。构件可以是组织内部开发的构件，也可以是商品化成品软件构件。基于构件的开发模型本质上是演化模型，需要以迭代方式构件软件，不同之处在于采用预先打包的软件构件开发应用系统。

模型名称	技术特点	使用范围
瀑布模型	简单，分阶段，阶段间存在因果关系，各个阶段完成后都有评审，允许反馈，不支持用户参与，要求预先确定需求	需求易于完善定义且不易变更的软件系统
快速原型模型	不要求需求预先完备定义，支持用户参与支持需求的渐进式完善和确认，能够适应用户需求的变化	需求复杂、难以确定、动态变化的软件系统
增量模型	软件产品是被增量式地一块块开发的，允许开发活动并行和重叠	技术风险较大、用户需求较为稳定的软件系统
迭代模型	不要求一次性地开发出完整的软件系统，将软件开发视为一个逐步获取用广需求、完善软件产品的过程	需求难以确定、不断变更的软件系统
螺旋模型	结合瀑布模型、快速原型模型和迭代模型的思想，并引进了风险分析活动	需求难以获取和确定、软件开发风险较大的软件系统

Ⅰ、瀑布模型

Ⅱ、软件开发模型

Ⅲ、V模型

Ⅳ、喷泉模型

Ⅳ、基于构件的开发模型

3、软件开发方法

Ⅰ、结构化方法

结构化方法由结构化分析、结构化设计、结构化程序设计构成，它是一种面向数据流开发方法。结构化分析是根据分解与抽象的原则，按照系统中数据处理的流程，用数据流图来建立系统的功能模型，从而完成需求分析工作。
结构化方法总的指导思想是自顶向下、逐层分解，其基本原则是功能的分解与抽象。它是软件工程中最早出现的开发方法，特别适合于数据处理领域的问题但是不适合解决大规模、特别复杂的项目，且难以适应需求的变化。

Ⅱ、Jackson方法

Jackson方法是一种面向数据结构的开发方法。因为一个问题的数据结构与处理该数据结构的控制结构有着惊人的相似之处。这种方法首先描述问题的输入输出数据结构，分析其对应性，然后推出相应的程序结构，从而给出问题的软件过程描述。
JSP方法是以数据结构为驱动的，适合于小规模的项目。当输入数据结构与输出数据结构之间没有对应关系时，难以应用此方法。基于JSP方法的局限性又发展了JSD方法，它是JSP方法的扩充。

Ⅲ、原型化方法

原型化方法:并非所有的需求都能够预先定义，而且反复修改是不可避免的开发原型化系统首先要确定用户需求，开发原始模型，然后征求用户对初始原型的改进意见，并根据意见修改原型。
原型化方法比较适合于用户需求不清、业务理论不确定、需求经常变化的情况，当系统规模不是很大也不太复杂时，采用该方法是比较好的。

Ⅳ、面向对象方法

面向对象开发方法包括面向对象分析、面向对象设计和面向对象实现。面向对象开发方法有Booch方法、Coad方法和OMT方法等。
为了统一各种面向对象方法的术语、概念和模型OMG 1997 年推出了统一建模语言(Unified Modeling Language，UML)。它是面向对象的标准建模语言，通过统一的语义和符号表示，使各种方法的建模过程和表示统一起来已成为面向对象建模的工业标准。

Ⅴ、敏捷开发方法

敏捷开发的总体目标是通过尽可能早地、持续地对有价值的软件的交付使客户满意。
敏捷过程的典型方法很多，主要有极限编程、水晶法、并列争球法、自适应软件开发几种。
极限编程(XP)是一种轻量级(敏捷)高效、低风险、柔性、可预测、科学的软件开发方式。它由价值观、原则、实践和行为4个部分组成，它们彼此相互依赖、关联，并通过行为贯穿于整个生存周期。

4、需求分析

Ⅰ、需求分类

功能需求:考虑软件要做什么。
性能需求:考虑软件开发的技术性指标。
用户或人的因素:考虑用户的类型。
环境需求:考虑未来软件应用的环境，包括软件和硬件。
界面需求:考虑对数据格式、数据存储介质的规定。
文档需求:考虑需要哪些文档，针对哪些读者。
数据需求:考虑数据的格式、接收、发送数据的频率等。
资源使用需求:考虑软件运行时所需数据、内存空间等资源。
安全保密要求。
可靠性要求:考虑系统的可靠性。
软件成本消耗与开发进度需求。
其他非功能性要求。

Ⅱ、需求获取方法

收集资料
联合需求计划
用户访谈
书面调查
情节串联板
现场观摩
参加业务实践
阅读历史文档
抽样调查

5、系统设计

Ⅰ、结构化方法的结构化设计

自顶向下、逐步求精
信息隐蔽
模块独立(高内聚、低耦合、复杂度)
- 保持模块的大小适中
- 尽可能减少调用的深度
- 多扇入，少扇出
- 单入口，单出口
- 模块的作用域应该在模块之内
- 功能应该是可预测的

Ⅱ、内聚和耦合

内聚类型	描述
功能内聚	完成一个单一功能，各个部分协同工作，缺一不可
顺序内聚	处理元素相关，而且必须顺序执行
通信内聚	所有处理元素集中在一个数据结构的区域上
过程内聚	处理元素相关，而且必须按特定的次序执行
瞬时内聚(时间内聚)	所包含的任务必须在同一时间间隔内执行
逻辑内聚	完成逻辑上相关的一组任务
偶然内聚(巧合内聚)	完成一组没有关系或松散关系的任务

耦合类型	描述
非直接耦合	两个模块之间没有直接关系，它们之间的联系完全是通过主模块的控制和调用来实现的
数据耦合	一组模块借助参数表传递简单数据
标记耦合	一组模块通过参数表传递记录信息(数据结构)
控制耦合	模块之间传递的信息中包含用于控制模块内部逻辑的信息
外部耦合	一组模块都访问同一全局简单变量，而且不是通过参数表传递该全局变量的信息
公共耦合	多个模块都访问同一个公共数据环境
内容耦合	一个模块直接访问另一个模块的内部数据；一个模块不通过正常入口转到另一个模块的内部；两个模块有一部分程序代码重叠；一个模块有多个入口

6、系统测试

Ⅰ、原则和目的

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

Ⅱ、测试方法

静态测试
- 人工检测
- 计算机辅助静态检测
动态测试
- 黑盒测试
  - 等价类划分
  - 边界值分析
  - 错误推测
  - 因果图
- 白盒测试
  - 基本路径测试
  - 循环覆盖测试
  - 逻辑覆盖测试

Ⅲ、测试阶段

单元测试:也称为模块测试，在模块编写完成且无编译错误后就可以进行单元测试侧重于模块中的内部处理逻辑和数据结构。一般用白盒测试法
集成测试:就是把模块按系统设计说明书的要求组合起来进行测试。即使所有的模块都通过了测试，在集成之后，仍然可能出现问题。
确认测试:始于集成测试的结束，那时已测试完单个构件，软件已组装成完整的软件包，且接口错误已被发现和改正。
系统测试:是将已经确认的软件、计算机硬件、外设和网络等其他因素结合在一起，进行信息系统的各种集成测试和确认测试，其目的是通过与系统的需求相较，发现所开发的系统与用户需求不符或矛盾的地方。

7、软件开发项目管理

Ⅰ、Gantt图

Gantt图是一种简单的水平条形图,它以日历为基准描述项目任务。水平轴表示日历时间线(如时、天、周、月和年等)，每个条形表示一个任务，任务名称垂直地列在左边的列中，图中水平条的起点和终点对应水平轴上的时间，分别表示该任务的开始时间和结束时间，水平条的长度表示完成该任务所持续的时间。当日历中同一时段存在多个水平条时，表示任务之间的并发。

Ⅱ、PERT图

PERT图是一个有向图用箭头表示任务，它可以表示完成该任务所需的时间，箭头指向节点表示流入节点的任务的结束，并开始流出节点的任务，这里把节点当成事件。只有当流入该节点的所有任务都结束时，节点所表示的事件才出现，流出节点的任务才可以开始。事件本身不消耗时间和资源，它仅表示某个时间点。一个事件有一个事件号和出现该事件的最早时刻和最迟时刻。每个任务还有一个松弛时间，表示在不影响整个工期的前提下，完成该任务有多少机动余地。

8、软件质量

Ⅰ、软件质量特性

软件质量模型由3个层次组成: 第一层是质量特性，第二层是质量子特性，第三层是度量指标。该模型的质量特性和质量子特性的含文如下。

功能性:与一组功能及其指定的性质有关的一组属性。这里的功能是指满足明确或隐含需求的那些功能。
- 适合性：与规定任务能否提供-一组功能以及这组功能的适合程度有关的软件属性
- 准确性：与能否得到正确的或相符的结果或效果有关的软件属性。
- 互用性：与同其他指定系统进行交互操作的能力有关的软件属性。
- 依从性：使软件服从有关的标准、约定、法规及类似规定的软件属性
- 安全性：与避免对程序及数据的非授权的故意或意外访问的能力有关的软件属性
可靠性:与在规定的一段时间内和规定的条件下软件维持其性能水平的能力有关的一组属性。
- 成熟性: 与由软件故障引起失效的频度有关的软件属性。
- 容错性:与在软件错误或违反指定接口情况下，维持指定的性能水平的能有关的软件属性。
- 易恢复性:与在故障发生后重新建立其性能水平并恢复直接受影响数据的能力，以及为达此目的所需的时间有关的软件属性。
易使用性:与为使用所需的努力和由一组规定的或隐含的用户对这样的使用所做的个别评价有关的一组属性。
- 易理解性:与用户为理解逻概念及其应用范围所需努力有关的软件属性。
- 易学性:与用户为学习软件应用所需努力有关的软件属性。
- 易操作性:与用户为进行操作或控制所需努力有关的软件属性。
效率:与在规定条件下，软件的性能水平与所用资源量之间的关系有关的一组属性。
- 时间特性:与软件执行其功能时的响应和处理时间以及吞吐量有关的软件属性。
- 资源特性:与软件执行其功能时所使用的资源量以及使用资源的持续时间有关的软件属性。
可维护性:与进行规定的修改所需努力有关的一组属性。
- 易分析性:与为诊断缺陷或失效原因，或为判定待修改的部分所需努力有关的软件属性。
- 易改变性:与进行修改、调试或适应环境变化所需努力有关的软件属性。
- 稳定性:与修改造成的未预料后果的风险有关的软件属性。
- 易测试性:与为确认经修改软件所需努力有关的软件属性。

9、软件度量

Ⅰ、McCabe度量法

McCabe复杂性度量又称为环路度量，它认为程序的复杂性很大程度上取决于控制的复杂性。单一的顺序程序结构最为简单，循环和选择所构成的环路越多，程序就越复杂。根据图论，在一个强连通的有向图G中，环的个数V(G)由以下公式给出: V(G) = m - n +2 式中，V(G)为有向图G中的环路数， m为图G中弧的个数， n为图G中的节点数

九、结构化开发方法

1、系统设计基本原理

抽象
抽象是一种设计技术，重点说明一个实体的本质方面，而忽略或者掩盖不是很重要或非本质的方面。
模块化
模块化是指将一个待开发的软件分解成若干个小的、简单的部分一模块，每个模块可独立地开发、测试，最后组装成完整的程序。模块化的目的是使程序的结构清晰，容易阅读、理解、测试和修改。
信息隐蔽信息隐蔽是开发整体程序结构时使用的法则，即将每个程序的成分隐蔽或封装在一个单一的设计模块中，定义每一个模块时尽可能少地显露其内部的处理信息隐蔽原则对提高软件的可修改性、可测试性和可移植性都有重要的作用。 4、模块独立模块独立是指每个模块完成一个相对独立的特定子功能，并且与其他模块之间的联系简单。衡量模块独立程度的标准有两个:耦合和内聚。耦合是指模块之间联系的紧密程度。耦合度越高，则模块的独立性越差。内聚是指模块内部各元素之间联系的紧密程度。内聚度越低，则模块的独立性越差。因此，模块独立就是希望每个模块都是高内聚、低耦合的。

2、系统总体结构设计

Ⅰ、系统结构设计应遵循以下原则

分解一协调原则
自顶向下原则。
信息隐蔽、抽象的原则
一致性原则
明确性原则
模块之间的羯合度尽可能小，模块的内聚度尽可能高
模块的扇入系数和扇出系数要合理。
模块的规模适当

Ⅱ、子系统划分要遵循以下原则

子系统要具有相对独立性
子系统之间数据的依赖性尽量小
子系统划分的结果应使数据几余较小。
子系统的设置应考虑今后管理发展的需要
子系统的划分应便于系统分阶段实现
子系统的划分应考虑到各类资源的充分利用

Ⅲ、模块

模块是组成系统的基本单位，它的特点是可以组合、分解和更换。系统中任何处理功能都可以看成是一个模块。根据模块功能具体化程度的不同，可以分为逻辑模块和物理模块。一个模块要具备以下4个要素：

输入和输出: 模块的输入来源和输出去向都是同一个调用者，即一个模块从调用者那里取得输入，进行加工后再把输出返回给调用者。
处理功能:指模块把输入转换成输出所做的工作
内部数据:指仅供该模块本身引用的数据
程序代码:指用来实现模块功能的程序

3、数据流图

Ⅰ、基本概念

数据流图或称数据流程图，是一种便于用户理解、分析系统数据流程的图形工具。它摆脱了系统的物理内容，精确地在逻辑.上描述系统的功能、输入、输出和数据存储等，是系统逻辑模型的重要组成部分。

数据流图描述了系统的分解，但没有对图中各成分进行说明。数据字典用于对数据流图中的每个数据流、文件、加工，以及组成数据流或文件的数据项做出说明。

Ⅱ、数据字典

数据字典有4类条目:数据流条目、数据存储条目、加工条目和数据项条目.数据字典管理主要是指把字典条目按照某种格式组织后存储在字典中并提供排序、查找、统计等功能。

Ⅲ、基本成分

十、UML建模

1、概述

统一建模语言(UML)是面向对象软件的标准化建模语言。UML由3个要素成：UML的基本构造块、支配这些构造块如何放置在一起的规则和运用于整个语言的一些公共机制。

UML的词汇表包含3种构造块: 事物、关系和图。

事物是对模型中最具代表性的成分的抽象，关系把事物结合在一起，图聚集了相关的事物。

Ⅰ、事物

事物包括结构事物、行为事物、分组事物和注释事物。

结构事物(Structural Thing)。通常是模型的静态部分，描述概念或物理元素。结构事物包括类(Class)、接口(lnterface)、协作(Collaboration)、用例(Use Case)、主动类(Active Class)、构件(Component)和节点(Node)。
行为事物(Behavior Thing)。是UML模型的动态部分。它们是模型中的动词，描述了跨越时间和空间的行为。共有两类主要的行为事物: 交互(lnteraction)和状态机(StateMachine)。
分组事物(Grouping Thing)。是UML模型的组织部分。它们是一些由模型分解成的“盒子”。在所有的分组事物中，最主要的分组事物是包(Package)。
注释事物(Annotational Thing)。是UML模型的解释部分。这些注释事物用来描述说明和标注模型的任何元素。注解(Note)是一.种主要的注释事物。注解是一个依附于一个元素或者一组元素之上，对它进行约束或解释的简单符号。

Ⅱ、UML中有4种关系:依赖、关联、泛化和实现

依赖Dependency)。依赖是两个事物间的语义关系，其中一个事物(独立事物)发生变化会影响另一个事物(依赖事物)的语义。
关联(Association)。关联是一种结构关系，它描述了一组链，链是对象之间的连接聚合(Aggregation)是一种特殊类型的关联，它描述了整体和部分间的结构关系。组合(Composition)也是一种特殊类型的关联，它同样体现了整体与部分间的关系，但比聚合更强，也称为强聚合。
泛化(Generalization)。泛化是一种特殊/一般关系，特殊元素(子元素)的对象可替代一般元素(父元素)的对象。用这种方法，子元素共享了父元素的结构和行为。
实现(Realization)。实现是类元之间的语义关系，其中一个类元制定了由另一个类元保证执行的契约。在两种地方要遇到实现关系:一种是在接口和实现它们的类或构件之间，另一种是在用例和实现它们的协作之间。

2、类图*

类图(Class Diagram)展现了一组对象、接口、协作及其之间的关系。在面向对象系统的建模中所建立的最常见的图就是类图。

类图给出了系统的静态设计视图，包含主动类的类图给出了系统的静态进程视图。作为模型管理视图还可以含有包或子系统，二者都用于把模型元素聚集成更大的组块。

类图用于对系统的静态视图建模。这种视图主要支持系统的功能需求，即系统要提供给最终用户的服务。

当对系统的静态设计建模时，通常以下述3种方式之一使用类图:对系统的词汇建模;对简单的协作建模;对逻辑数据库模式建模。

1:表示一个集合中的一个对象对应另一个集合中1个对象。
0..*:表示一个集合中的一个对象对应另一个集合中的0个或多个对象(可以不对应
1..*:表示一个集合中的一个对象对应另一个集合中的一个或多个对象(至少对应一
*:表示一个集合中的一个对象对应另一个集合中的多个的对象。

3、用例图

用例图(Use Case Diagram)展现了一组用例、参与者(Actor)以及两者之间的关系。用例图通常包括用例、参与者、扩展关系、包含关系。用例图用于对系统的静态用例视图进行建模，主要支持系统的行为，即该系统在它的周边环境的语境中所提供的外部可见服务。

4、顺序图

顺序图(或称序列图)和协作图均被称为交互图，它们用于对系统的动态方面进行建模。

顺序图是强调消息时间序列的交互图，协作图则是强调接收和发送消息的对象的结构组织的交互图。

5、活动图

活动图专注于系统的动态视图，它对于系统的功能建模特别重要，并强调对象间的控制流程。

6、状态图

状态图(State Diagram)展现了一个状态机，它由状态、转换、事件和活动组成。状态图关注系统的动态视图，对于接口、类和协作的行为建模尤为重要，强调对象行为的事件顺序。

7、通信图

通信图(Communication Diagram)强调收发消息的对象的结构组织。通信图强调参加交互的对象的组织。通信图有路径
通信图有顺序号

8、构件图

构件图(Component Diagram)展现了一组构件之间的组织和依赖。构件图专注于系统的静态实现视图。如图所示，它与类图相关，通常把构件映射为一个或多个类、接口或协作。

十一、面向对象技术

1、基本概念

面向对象=对象+分类+继承+通过消息的通信

Ⅰ、对象

在面向对象的系统中，对象是基本的运行实体，它既包括数据(属性)，也包括作用于数据的操作(行为)，所以一个对象把属性和行为封装为一个整体。从程序设计者角度看，对象是一个程序模块，从用户角度看，对象为他们提供了所希望的行为。在对象内的操作通常叫作方法。一个对象通常可由对象名、属性和操作3部分组成。

Ⅱ、消息

对象之间进行通信的一种构造叫作消息。当一个消息发送给某个对象时，包含要求接收对象去执行某些活动的信息，接收到消息的对象经过解释，然后予以响应，这种通信机制叫作消息传递。发送消息的对象不需要知道接收消息的对象如何对请求予以响应。

Ⅲ、类

一个类定义了一组大体上相似的对象，一个类所包含的方法和数据描述一组对象的共同行为和属性。类是在对象之上的抽象，对象是类的具体化，是类的实例。

Ⅳ、继承

继承是父类和子类之间共享数据和方法的机制广这是类之间的一种关系在定义和实现个类的时候，可以在一个已经存在的类的基础上来进行，把这个已经存在的类所定义的内容作为自己的内容，并加入若干新的内容。
一个父类可以有多个子类，这些子类都是父类的特例，父类描述了这些子类的公共属性和操作。一个子类可以继承它的父类中的属性和操作，这些属性和操作在子类中不必定义。子类中还可以定义自己的属性和操作。

Ⅴ、多态

不同的对象收到同一消息可以产生完全不同的结果，这一现象叫作多态。在使用多态的这样，把具有时候，用户可以发送一个通用的消息，而实现的细节则由接收对象自行决定通用功能的消息存放在高层次，而把不同的实现这一功能的行为放在较低层次，在这些低层次上生成的对象能够给通用消息以不同的响应。

2、设计原则

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

3、设计模式的概念与分类

设计模式:主要关注软件系统的设计，与具体的实现语言无关
设计模式一般有以下4个要素:

模式名称。用一两个词来描述模式的问题、解决方案和效果。设计模式允许在较高的抽象层次上进行设计。
问题。描述了应该在何时使用模式。它解释了设计问题和问题存在的前因后果，可能描述了特定的设计问题，如怎样用对象表示算法等;也可能描述了导致不灵活设计的类或对象结构。
解决方案。描述了设计的组成成分、它们之间的相互关系及各自的职责和协作方式。模式就像一个模板，提供设计问题的抽象描述和怎样用一个具有一般意义的元素组合(类或对象组合)来解决这个问题。
效果。描述了模式应用的效果及使用模式应权衡的问题。

4、创建型模式

工厂方法(factory method)模式
- 定义一个创建对象的接口，但由子类决定需要实例化哪一个类。工厂方法使得子类实例化的过程推迟
抽象工厂(abstract factory)模式
- 提供一个接口，可以创建一系列相关或相互依赖的对象，而无需指定它们具体的类
原型(prototype)模式
- 用原型实例指定创建对象的类型，并且通过拷贝这个原型来创建新的对象
单例(singleton)模式
- 保证一个类只有一个实例，并提供一个访问它的全局访问点
构建器(builder)模式
- 将一个复杂类的表示与其构造相分离，使得相同的构建过程能够得出不同的表示

创建型模式抽象了实例化过程。它们帮助一个系统独立于如何创建、组合和一个类创建型模式使用继承改变被实例化的类，而一个对象创表示它的那些对象。建型模式将实例化委托给另一个对象。
创建型模式中有两个不断出现的主旋律。第一，它们都将关于该系统使用哪些具体的类的信息封装起来。第二，它们隐藏了这些类的实例是如何被创建和放在起的整个系统关于这些对象所知道的是由抽象类所定义的接口。
因此，创建型模式在为什么被创建，谁创建它，它是怎样被创建的，以及何时创建这些方面给予了很大的灵活性。它们允许用结构和功能差别很大的“产品对象配置-一个系统。配置可以是静态的(即在编译时指定),也可以是动态的(在运行时指定)。

5、结构型模式

适配器(adapter)模式
- 将一个类的接口转换成用户希望得到的另一种接口。它使原本不相容的接口得以协同工作
桥接(bridge)模式
- 将类的抽象部分和它的实现部分分离开来，使它们可以独立地变化
组合(composite)模式
- 将对象组合成树型结构以表示“整体-部分”的层次结构，使得用户对单个对象和组合对象的使用具有一致性
装饰(decorator)模式
- 动态地给一个对象添加一些额外的职责。它提供了用子类扩展功能的一个灵活的替代，比派生一个子类更加灵活
外观(facade)模式
- 定义一个高层接口，为子系统中的一组接口提供一个一致的外观，从而简化了该子系统的使用
享元(flyweight)模式
- 提供支持大量细粒度对象共享的有效方法
代理(proxy)模式
- 为其他对象提供一种代理以控制这个对象的访问

结构性模式涉及如何组合类和对象以获得更大的结构。结构性模式采用继承机制来组合接口或实现。
结构性对象模式不是对接口和实现进行组合，而是描述了如何对一些对象进行组合，从而实现新功能的一些方法

6、行为型模式

职责链(chain of responsibility)模式
- 通过给多个对象处理请求的机会，减少请求的发送者与接收者之间的耦合。将接收对象链接起来，在链中传递请求，直到有一个对象处理这个请求
命令(command)模式
- 将一个请求封装为一个对象，从而可用不同的请求对客户进行参数化，将请求排队或记录请求日志，支持可撤销的操作
解释器(interpreter)模式
- 给定一种语言，定义它的文法表示，并定义一个解释器，该解释器用来根据文法表示来解释语言中的句子
迭代器(iterator)模式
- 提供一种方法来顺序访问一个聚合对象中的各个元素，而不需要暴露该对象的内部表示
中介者(mediator)模式
- 用一个中介对象来封装一系列的对象交互。它使各对象不需要显式地相互调用，从而达到低耦合，还可以独立地改变对象间的交互
备忘录(memento)模式
- 在不破坏封装性的前提下，捕获一个对象的内部状态，并在该对象之外保存这个状态，从而可以在以后将该对象恢复到原先保存的状态
观察者(observer)模式
- 定义对象间的一种一对多的依赖关系，当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并自动更新
状态(state)模式
- 允许一个对象在其内部状态改变时改变它的行为
策略(strategy)模式
- 定义一系列算法，把它们一个个封装起来，并且使它们之间可互相替换，从而让算法可以独立于使用它的用户而变化
模板方法(template method)模式
- 定义一个操作中的算法骨架，而将一些步骤延迟到子类中，使得子类可以不改变一个算法的结构即可重新定义算法的某些特定步骤
访问者(visitor)模式
- 表示一个作用于某对象结构中的各元素的操作，使得在不改变各元素的类的前提下定义作用于这些元素的新操作

行为模式涉及算法和对象间职责的分配。行为模式不仅描述对象或类的模式还描述它们之间的通信模式。这些模式刻画了在运行时难以跟踪的复杂的控制流它们将用户的注意力从控制流转移到对象间的联系方式上来。

行为类模式使用继承机制在类间分派行为，主要有Template Method( 模板方法)和Interpreter(解释器)两种模式。

行为对象模式使用对象复合而不是继承。一些行为对象模式描述了一组对等的对象怎样相互协作以完成其中任一个对象都无法单独完成的任务。其他的行为对象模式常将行为封装在一个对象中并将请求指派给它。

7、Java程序设计

优点

跨平台。
代码可移动(与html相结合).
完全面向对象。
编出来的程序不易出错(没有指针，内存垃圾自动回收，不会产生内存泄露)。此外，还有简单、安全、多线程等优点

Java与C++的区别

完全面向对象:无全局变量、无结构和联合、自动回收内存垃圾。
没有指针
没有多继承。
解释执行。

Ⅰ、类

一个类是一些属性和方法的封装体类的定义用关键字class声明，用关键字public、protected、private指定类的成员的存取控制属性

private(私有)成员，只有类内部的方法才能访问;
protected(保护)成员，可被派生类和同一:文件夹下的类访问
public(公有)成员，可以从类的外部访问。

默认是public。这体现了面向对象的以下指导思想: 尽量将类内部的细节隐藏起来，对类的属性的操作应该通过类的方法来进行。

Ⅱ、继承

java中用关键字extends表示类间的继承关系

父类的公有属性和方法成为子类的属性和方法，子类如果有和父类同名同参数类型的方法，那么子类对象在调用该方法时，调用的是子类的方法，亦即方法的重置。如果想要调用父类的同名方法，需要用super关键字(属性)。

子类的对象可以作为祖先类的对象使用，即所谓类的向上转换，反之则不行。具体表现在:可以用子类对象来对祖先类对象赋值，可以用子类对象作为实参去调用以父类对象为形参的函数。

Ⅲ、重载

同一个类中的两个或两个以上方法，名字相同，而参数个数不同或参数类型不同，叫作重载。 注意: 方法名字和参数都一样，而仅仅返回值类型不同，这不是重载。

Ⅳ、静态属性和静态方法

静态属性和静态方法的声明用关键字static 实现。一个类的静态属性只有一个，由所有该类的对象共享。不需要创建对象也能访问类的静态属性和方法，访问方式为“类名.静态属性或静态方法”。静态方法与对象无关，因此不能在静态方法中访问非静态属性和调用非静态方法。

Ⅴ、this、super和final

this代表当前对象，super代表当前对象的父类
this的主要用途有:(1)一个构造函数调用另一个构造函数，对构造函数的调用必须是第一条语句。(2)将对象自身作为参数来调用一个函数。
super的用途: 在子类中调用父类的同名方法，或在子类的构造函数中调用父类的构造函数，此时也必须是第一条语句。
用final关键字定义的常量，在其初始化或第一次赋值后，其值不能被改变。常量必须先有值，然后才能使用。对于常量的第一次赋值只能在构造函数中进行。
final对象的值不能被改变，指的是该对象不能再指向其他对象，而不是指不能改变当前对象内部的属性值。
函数参数声明为final后，函数中的值不能改变。
final方法是不能被重置的方法。
final类不能被继承，其所有方法都是final的，但属性可以不是final 的。

Ⅵ、抽象类和接口

抽象类通过关键字abstract 实现，抽象类的目的是定义一个框架，规定某些类必须具有的一些共性。包含抽象方法的类一定是抽象类，所谓抽象方法是指没有函数体的方法。抽象类的直接派生类必须实现其抽象方法，抽象类只能用于继承，不能创建对象。

接口用关键字interface 声明，只能用于继承。注意:此时关键字为implements(实现)。接口用于替代多继承的概念，能实现多继承的部分特点，又避免了多继承的混乱，还能起到规定程序框架的作用。注意:接口也可以用于多态。直接继承了接口的类,必须实现接口中的抽象方法间接的则可以实现，也可以不实现。

抽象类与接口的异同 接口和抽象类都不能创建对象。
抽象类不能参与多继承，抽象类可以有非静态的成员变量，可以有非抽象方法。
接口可以参与多继承，所有属性都是静态常量，所有方法都是public抽象方法

一、计算机组成原理与体系结构基础知识

1. 数据的表示

Ⅰ、进制的转换：

Ⅱ、真值与机器数

2. 校验码

Ⅰ、奇偶校验

Ⅱ、循环冗余校验码

3. 冯·诺依曼计算机的特点

4.主存储器

5.运算器

6.Flynn分类法

7.指令

Ⅰ、指令格式

Ⅱ、寻址方式

Ⅲ、数据寻址

Ⅳ、CISC和RISC

Ⅴ、指令的流水处理

Ⅵ、流水线的计算

8.存储系统的层次结构

Ⅰ、高速缓存Cache

Ⅱ、硬盘

Ⅲ、总线系统

Ⅳ、输入输出技术

Ⅴ、可靠性

二、数据结构

1、基本概念

Ⅰ、什么是数据?

Ⅱ、数据元素、数据项

Ⅲ、什么是算法?

2、线性表

Ⅰ、线性表定义

Ⅱ、插入删除操作

3、栈和队列

Ⅰ、栈定义

Ⅱ、队列定义

4、串、数组、矩阵和广义表

Ⅰ、串

Ⅱ、数组

Ⅲ、稀疏矩阵

Ⅳ、广义表

5、树和二叉树

Ⅰ、树的基本概念

Ⅱ、二叉树的基本概念

Ⅲ、二叉树的遍历

Ⅳ、反向构造二叉树

Ⅴ、树转二叉树

Ⅵ、查找二叉树 （二叉排序树）

Ⅶ、构造霍夫曼树(最优)

Ⅷ、线索二叉树

Ⅷ、平衡二叉树

6、图

Ⅰ、图的基本概念

Ⅱ、存储结构 (邻接矩阵)

Ⅲ、存储结构 (邻接表)

Ⅳ、图的遍历

Ⅴ、拓扑排序

Ⅵ、最小生成树

7、查找

Ⅰ、基本概念

Ⅱ、顺序查找

Ⅲ、折半查找

Ⅳ、分块查找

Ⅴ、哈希表 (散列表)

8、排序

Ⅰ、基本概念

Ⅱ、直接插入排序

Ⅲ、希尔排序

Ⅳ、冒泡排序

Ⅴ、快速排序

Ⅵ、简单选择排序

Ⅶ、堆排序

Ⅷ、归并排序

Ⅸ、基数排序

Ⅹ、评价指标

三、算法设计与分析

1、分治法

2、回溯法

Ⅰ、回溯法一深度优先搜索法

3、贪心法

Ⅰ、贪心法—局部最优

Ⅵ、查找二叉树（二叉排序树）

Ⅲ、空闲存储空间的管理（位示图法）

Ⅲ、规范化理论（非规范化存在的问题）