软件设计师选择题笔记（完善中）

admin 管理员组

文章数量: 887018

一、计算机组成与体系结构前言

1.1 数据的表示

1.1.1 进制转换

（1）R进制转为十进制：

按权展开法：

例如：

二进制10100.01=1*2＾4+1*2＾2+1*2＾(-2)

（2）十进制转为R进制：

短除法：

例如：

94转为二进制

94÷2=47……0

47÷2=23……1

23÷2=11……1

11÷2=5……1

5÷2=2……1

2÷2=1……0

1÷2=0……1

从下往上读，该二进制为1011110

（3）二进制转八进制与十六进制：

例如：

二进制：10001110

方法：从右往左每3位一组

即：10  001  110  —>不足的补0

即：010  001  110

按照转10进制的按权展开法算：

即： 010=1*2＾1=2

001=1*2＾0=1

110=1*2＾2+1*2＾1=6

即最终转换八进制为 216

（4）其它

二进制转换为十六进制同理，只不过是4位一组，

10开始的数由ABCDE表示

1.1.2  原码 反码 补码 移码

原码：不能直接运算，最高位为符号位

反码：原码的符号位不变，其它取反

补码：正数不变，负数的反码末位+1

移码：与补码的符号位相反，剩下跟补码一样

数值(整数)表示范围：例如8位

原码：-(2＾(n-1)-1 ) ~ 2＾(n-1)-1 =-127～127

反码：-(2＾(n-1)-1 ) ~ 2＾(n-1)-1=-127~127

补码：-2＾(n-1)~ 2＾(n-1)-1=-128~127

1.1.3 浮点数运算

(类似于科学计数法)

浮点数表示：

N=M*R＾e

M成为尾数，e是指数，R为基数

尾数不能为0或1位以上的数

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

例如：

1000+119

1000=1.0*10＾3

119=0.119*10＾3(不能取1.19*10＾2)

相加后为1.119*10＾3，这个结果符合格式化规则

1.2 计算机结构

主机：

主存储器(内存)：

cpu：

运算器：

算法逻辑单元ALU

累加寄存器AC

数据缓冲寄存器DR

状态条件寄存器PSW(标志位)

控制器：

程序计数器PC

指令寄存器IR

指令译码器

时序部件

1.3 Flynn分类法

是计算机体系结构的分类

依据数据流，指令流分类

单，多

以下四种：

单指令流单数据流SISD。结构为：控制部分1个，处理器1个，主存模块1个，关键特性无。代表：单处理器系统，4086等

单指令流多数据流SIMD。结构为：控制部分1个，处理器多个，主存模块多个，关键特性：各处理器以异步的形式执行同一条指令。代表：并行处理机，阵列处理机，超级向量处理机。阵列处理机适合处理数组。

多指令流单数据流MISD。结构为：控制部分多个，处理器1个，主存模块多个。关键特性：被证明不可能，至少是不实际的。代表：目前没有，有文献称流水线计算机为此类。

多指令流多数据流MIMD。控制部分多个，处理器多个，主存模块多个。关键特性：能够实现作业，任务，指令等各级全面并行。代表：多处理机系统，多计算机。

1.4 CISC与RISC

CISC(复杂)。指令：数量多，使用频率差别大，可变长格式。寻址方式：支持多种。实现方式：微程序控制技术(微码)。其它：研制周期长。

RISC(精简)。指令：数量少，使用频率接近，定长格式，大部分为单周期指令，操作寄存器，只有Load/Store操作内存。寻址方式：支持方式少。实现方式：增加了通用寄存器，硬布线逻辑控制为主，适合采用流水线。其它：优化编译，有效支持高级语言。

1.5 流水线技术

1.5.1 流水线概念

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

——>取指——>分析——>执行

例如：

未使用流水线执行指令情况(一组一组完成)：

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

使用流水线执行指令情况(一个一个完成)：

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

1.5.2 流水线计算

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

流水线计算公式为：

1条指令执行时间+(指令条数-1)*流水线周期。

理论公式：(t1+t2+...+tk)+(n-1)*Δt

实践公式：(k+n-1)*Δt

这里的k指的是几部分。

取指   123……n

分析    123……n

执行     123……n

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

解：流水线周期为执行时间最长的一段，就是2ns。

所需时间：

(理论公式计算)(2+2+1)+(100-1)*2=5+198=203

(实践公式计算)(3+100-1)*2=204

注意：考试一般用理论公式，如果理论公式没有正确答案的话，就用实践公式。

1.5.3 流水线吞吐率计算：

流水线吞吐率(Though Put rate，TP)是指在单位时间内流水线所完成的任务数量或输出的结果数量。也可以说等于流水线周期的倒数。

以年为单位

最基本的格式：

TP=指令条数/流水线执行时间

流水线最大吞吐率：

TPmax=Lim(n->∞)  n/(k+n-1)*Δt=1/Δt

以上题为例，求该流水线的吞吐率：

即100/203，最大吞吐量为1/2

1.5.4 流水线的加速比：

概念：完成同样一批任务，不使用流水线所用的时间与使用流水线所用的时间之比。加速比越高越好。

基本公式：

S=不使用流水线执行时间/使用流水线执行时间

还是上面那道例题：

不使用流水线执行时间：

(2+2+1)*100=500  (也就是各部分时间相加乘以指令条数)

使用流水线执行时间为203

故流水线的加速比为S=500/203

流水线的效率：

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

计算公式：

E=n个任务占用的时空区/k个流水段的总的时空区=Tₒ/kTₖ

题目写在草稿纸上。

1.6 存储系统

1.6.1 计算机层次存储结构：

快↑     CPU     →寄存器

↑

↑    Cache    →按内容存取

速↑

度↑   内存(主存)

↑

↑

慢↑   外存(辅存)  →硬盘，光盘，U盘等

速度快的容量小，又要快又要大的贵。

cache是为了提速度。

局部性原理：

时间局部性，空间局部性。

1.6.2 Cache基本概念

功能：提高CPU数据输入输出的速率，突破冯诺依曼瓶颈，即CPU与存储系统间数据传送带宽限制。

在计算机的存储系统体系中，Cache是访问速度最快的层次。但请注意，寄存器是最快的，因为它在CPU里。其次是Cache。

使用Cache改善系统性能的依据是程序的局部性原理。

数据会首先在Cache中寻找。

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

t₃=h*t₁+(1-h)*t₂

其中，(1-h)又称为失效率(未命中率)

注意单位要一致，注意ns或ms

1ms=1000ns

1.6.3 局部性原理

概念：时间局部性     空间局部性

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

例如：

int i,s=0;

for(i=1;i<1000;i++)

for(j=1;j<1000;j++)

s+=j;

printf("结果为：%d",s)

这个不用都去主存拿数据，可以在cache拿。

1.6.4，

主存-分类(2种)：

随机存储存储器：（掉电就无）

DRAM(Dynamic RAM，动态  RAM)-SDRAM（掉电就无，电容，周期刷新）

SRAM(Static RAM，静态)（晶体管）

只读存储器（晶体管）：

MPOM(Mask ROM，掩模式ROM)

PROM(Programmable  ROM，一次可编程ROM)

EPROM(Erasable  PROM，可擦除的PROM)

闪速存储器(flash memory，闪存)

主存-编址：

在草稿纸上

1.6.5 磁盘工作原理

磁盘结构与参数：

存取时间=寻道时间+等待时间(平均定位时间+转动延迟)

注意：寻道时间是指磁头移动到磁道所需的时间;等待时间为等待读写的扇区转到磁头下方所用的时间。

一个磁道会分很多扇区。

例题：

假设某磁盘的每个磁道划分成11个物理块，每块存放1个逻辑记录。逻辑记录R₀，R₁ ,.... ....,R₉,R₁₀存放在同一个磁道上，记录的存放顺序如下表所示：

物理块	1	2	3	4	5	6	7	8	9	10	11
逻辑记录	R₀	R₁	R₂	R₃	R₄	R₅	R₆	R₇	R₈	R₉	R₁₀

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

解析：

磁盘一旦处理起来不会停，会按匀速进行转动。

第一问：

磁头从R0开始，将R0读进单缓冲区后，磁头来到R1，但这时无法读取R1，因为单缓冲区里面的R0需要3ms来处理，所以磁头接着转，等磁头来到R2时，单缓冲区处理完，但是不能把R2读进去，因为R0处理完后要读取R1,(可能要按顺序来读)，所以磁头只好再转一圈回来R1，把R1读取进去，依次类推。

所以R1的读取与处理花费了(30+3+3)ms的时间，并且此时已将磁头定在了R3上。

依次类推R1到R10都是这样处理的，所以要(30+3+3)*10

R0读取与处理总共需要(3+3)，因为磁盘周期是33ms，共有11个物理块，所以每读取一个物理块需要(33/11)ms

故处理11个记录的最长时间需要(30+3+3)*10+(3+3)=366ms

第二问：

题目说可以优化信息存储的分布,所以可以考虑将R1放在R2的位置让它处理完R0时接着读取R1,而不用转一圈。

依次类推，可以把R2放在R4位置，让物理块顺利被读取。

故消耗最少时间为(3+3)*11=66ms

1.7 总线系统

总线：

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

内部总线：

芯片层级的总线

系统总线：

数据总线：宽度指可以传输数据的bit位

地址总线：地址空间是2^地址总线

控制总线：控制发送信号

外部总线：

外部设备层级的总线

1.8 可靠性

串联系统与并联系统可靠度计算：

系统可靠性分析-串联系统与并联系统：

草稿纸上写有笔记

系统可靠性分析-模冗余系统与混合系统：

草稿纸上写有笔记

1.9 校验码

差错控制-CRC与海明校验码：

1.9.1 基本概念

什么是检错和纠错?

什么是码距?

一个编码系统的码距是整个编码系统中任意(所有)两个码字的最小距离。简单说，就是两个码字之间，其中一个要改变多少bit位才能跟第二个码字一样。

例如：

若用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

1.9.2 循环校验码(CRC)

校验码-循环校验码CRC：

模2除法：除法运算中不计其进位的除法

看草稿纸笔记。

1.9.3 海明校验码(难点，考查频度高)

校验码：海明校验码

看草稿纸笔记

注意：已被海明校验码占用的位，那一列不能放信息。

二、操作系统概述(5-7分)

2.1 操作系统-概述：

草稿纸笔记

管理系统的硬件，软件，数据资源

控制程序允许

人机之间的接口

应用软件与硬件之间的接口

进程管理：

进程的状态

前趋图

PV操作

死锁问题

存储管理：

  分区存储组织：首次适应法，最佳适应法，最差适应法，循环首次适应法。

页式存储组织：

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

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

段式存储组织：

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

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

段页式存储：

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

  缺点：管理软件增加导致复杂性高，硬件和内存需求增加，执行速度下降。

页面置换算法：

  先进先出FIFO

  最佳适应算法：这个应该跟上面的最佳适应法同个原理。

  最近最少使用LRU：最近使用的排最后

文件管理：

索引文件

位示图

作业管理

设备管理

微内核操作系统：虚设备与SPOOLING技术

抖动现象：页数增加了，缺页次数反而增加了。

2.2. 进程状态转换图

草稿纸笔记

2.3 前趋图

草稿纸笔记

2.4 进程的同步与互斥

单缓冲区情况

多缓冲区情况

2.5 PV操作

临界资源：

诸进程间需要互斥方式对其进行共享的资源，如打印机，磁带机等

临界区：

每个进程中访问临界资源的那段代码称为临界区

信号量：是一种特殊的变量

其实PV操作可以理解为这是一对同步问题，而其中P操作是等待，V操作是唤醒P操作。

看草稿纸笔记

2.6 PV操作与前趋图

看草稿纸笔记

2.7 死锁问题

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

看草稿纸笔记

2.8 银行家算法

死锁的预防

↓

打破四大条件：

互斥

环路等待

保持和等待

不剥夺

↑

死锁的避免：

有序资源分配法

银行家算法

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

当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程。

进程可以分期请求资源，但请求的总数不能超过最大需求量。

当系统现有的资源不能满足进程尚需资源数时，对进程的请求可    以推迟分配，但总能使进程在有限的时间里得到资源。

2.9 存储管理-分区存储组织

2.10 存储管理-页式存储组织

2.11 存储管理-段页式存储组织

2.12 存储管理-快表

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

2.13 存储管理-页面置换算法

最优(Optimal，OPT)算法：这是"事后法"，没法实际应用。

随机(RAND)算法

先进先出(FIFO)算法：有可能产生"抖动"。例如，432143543215序列，用3个页面，比4个缺页要少。常考

最近最少使用(LRU)算法：不会"抖动"。常考

2.14 文件管理-索引文件结构

2.15 文件和树型目录结构

文件属性：

R只读文件属性

A存档属性

S系统属性

H隐藏属性

文件名的组成：

驱动器号

路径

主文件名

扩展名

绝对路径：是从盘符开始的路径。

相对路径：是从当前路径开始的路径。

若当前目录为：D1，要求F2路径，则：绝对路径：/D1/W2/F2,相对路径：W2/F2

图片看草稿纸

2.16 文件管理-空闲存储空间的管理(重点是位示图法)

空闲区表法(空闲文件目录)

空闲链表法

位示图法

成组链接法

位示图：1表占用，0表空闲

注意：行(字号)是从1开始算的，列(位号)是从0开始算的，这是多年的指标

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

(主要指内存和外设之间的数据传输)

以下方式逐渐加强效率

程序控制方式

程序中断方式

DMA方式

通道：

A1 A2 ...↘

B1 B2...→通道→A1 B1 C1 A2 B2 ...

C1 C2...↗

字节多路通道的传送方式

A1 A2 ...↘

B1 B2...→通道→A1 A2.. B1 B2 ...

C1 C2...↗

选择通道的传送方式

输入输出处理机

(一般后两个要用专用的计算机，一般不考，主要考前三个)

2.18 设备管理-虚设备与SPOOLING技术

2.19 微内核操作系统

客户进程	客户进程	进程服务器	终端服务器	...	文件服务器	存储器服务器
↓  ↑__________________________↑  ↓ 请求                                   回答

上面表格，第一行是用户态，第二行是核心态。

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

微内核操作系统：

也就是用户态出错了，不用重启整个系统，只需要解决用户态的问题，但是一旦内核态出错了，那将会很严重。

三、数据库系统前言

3.1 课程内容提要：

数据库模式

ER模型

关系代数与元祖演算

规范化理论

并发控制

数据库完整性约束

分布式数据库

数据仓库与数据挖掘

3.2 三级模式-两级映射

   三级模式：

外模式（视图）：也称用户模式、子模式。是用户得到的数据描述，即视图。

 概念模式（表）：也称模式。是数据库全部数据的整体逻辑结构的描述，即表（结构）。

 内模式（存储）：也称存储模式。物理存储方面的描述，定义所有内部记录类型、索引和文件的组织方式，以及数据控制方面的细节。

   两级映射：

      内模式映射—>概念模式(概念模式映射)—>外模式

变化时只需要改变映射。

3.3 数据库设计过程

3.4 ER模型

也就是画ER图

矩形表示实体

菱形表示联系

椭圆表示属性

例如：一个学生可以选多门课

一门课可以被多个学生选择

所以学生与选课之间是多对多的关系

集成的方法：

多个局部E-R图一次集成

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

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

属性冲突：包括属性域冲突和属性取值冲突。

命名冲突：包括同名异义和异名同义。

结构冲突：

包括同一对象在不同应用中具有不同的抽象，以及同一实体在不同局部E-R图中所包含的属性个数和属性排列次序不完全相同。例如一个应用中的老师是一个列，但在另外一个应用中却是一张表。

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

1:1联系  1:n联系  m:n联系

大题中一比多写成1:*

多比多也写成 *:*

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

3.5 关系代数

并：相同的数据只显示一次

交：找出公共部分，形成新的一种关系

差:找出我有的，你没有的部分，简单来说就是去掉公共部分

笛卡尔积(常考)

投影：选出所需要的列(属性)，符号为：Π

选择：根据指定的属性值来选行，选的是行，符号为：σ

联接(常考)：没有写条件的为自然连接，两个关系之间相同字段做等值连接。

关系S1
Sno	Sname	Sdept
No0001	Mary	IS
No0003	Candy	IS
No0004	Jam	IS

关系S2
Sno	Sname	Sdept
No0001	Mary	IS
No0008	Katter	IS
No0021	Tom	IS

S1∩S2(交)
Sno	Sname	Sdept
No0001	Mary	IS

S1∪S2(并)
Sno	Sname	Sdept
No0001	Mary	IS
No0003	Candy	IS
No0004	Jam	IS
No0008	Katter	IS
No0021	Tom	IS

S1-S2(差)
Sno	Sname	Sdept
No0003	Candy	IS
No0004	Jam	IS

自然连接：

会把后表跟前表不一样的属性加到前表里，形成一个新的表。

3.6 规范化理论-函数依赖

   部分函数依赖；

   传递函数依赖；

例如：学号可以确定姓名，而姓名不能确定学号，因为姓名可以重名

设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。

3.7 规范化理论-价值与用途

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

3.8 规范化理论-键

超键：可以是单个属性，也可以是属性的组合。

超键的特点就是可能存在冗余属性。

例如：学号，姓名，性别

学号可以确定性别

学号跟姓名的组合键也可以确定性别。

学好跟姓名的组合键可以称为超键，但不能称为候选键，因为姓名冗余了。

候选键可以有多个，而主键只能有一个。（出现在大题，问主键跟外键，其实外键也是别的关系的主键），很奇怪，可能要看情况，看看如果关系里面只有两个外键的主键，那么这两个一起作为该关系的主键和外键。

3.9 规范化理论-求候选键

步骤：

1．将关系模式的函数依赖关系用"有向图"的方式表示

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

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

3.10 规范化理论-范式(几乎必考)

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

非主属性：除候选键外的属性。

达到第二方式必须要达到第一范式，以此类推。

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

例如：

系名称	高级职称人数
	教授	副教授
计算机系	6	10
电子系	3	5

上面就不满足1NF，因为"高级职称人数"这个属性还可以再分，而不是原子属性。直接把"高级职称人数"去掉，就变成了1NF。

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

例如：

Sno	Cno	Grade	Credit
SO1	CO1	75	4
SO2	CO1	92	4
SO3	CO1	87	4
SO4	CO1	55	4
SO1	CO2	87	2
SO2	CO2	95	2
SO1	CO3	94	5
...	...	...	...

候选键为Sno,Cno。

Cno可以决定Credit，所以造成部分依赖。

如果有新的课程和学分，则录入不进去，因为没人选，这就是 插入异常。万一学生毕业，把学生信息删除后，课程和学分也会被删除，这就是删除异常。

此表，数据冗余，更新异常，插入异常，删除异常。

解决方式：把Cno和Credit提取出来做一个新的关系模式，在原来的关系模式(上表)中去掉Credit，但不去掉Cno。这样就由1NF到了2NF。

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

例如：

SNO	SNAME	DNO	DNAME	LOCATION
SO1	张三	DO1	计算机系	1号楼
SO2	李四	DO1	计算机系	1号楼
SO3	王五	DO1	计算机系	1号楼
SO4	赵六	DO2	信息系	2号楼
...	...	...	...	...

此表，数据冗余，更新异常，插入异常，删除异常。

解决方式：DNO，DNAME，LOCATION做一个新的关系模式，原来的关系模式(上表)去除DNAME，LOCATION，保留DNO，这样就解决了传递依赖问题。达到3NF。

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

例子看草稿纸笔记

3.11 规范化理论-模式分解

◆保持函数依赖分解：

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

◆无损分解：

有损：不能还原

无损：可以还原

无损联接分解：

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

定理：

如果R的分解为p={R1,R2},F为R所满足的函数依赖集合，分解p具有无损联接性的充分必要条件是：R1∩R2→(R1-R2)或R1∩R2→(R2-R1),其中，R1∩R2表示模式的交，为R1与R2中公共属性组成，R1-R2或R2-R1表示模式的差集，R1-R2表示R1中去除R1和R2的公共属性所组成。当模式R分解成两个关系模式R1和R2时，如果R1和R2的公共属性能函数决定R1中或R2中的其它属性，这样的分解就具有无损联接性。

这定理只适用于一分为二，例如R分为R1和R2。

3.12 并发控制-基本概念

事务(例如银行转账事务)：

原子性

一致性

隔离性

持续性

并发产生的问题：

丢失更新

不可重复读问题

"脏"数据的读出

封锁协议：

S封锁

X封锁

一级封锁协议：

事务T在修改数据R之前必须先对其加X锁，直到事务结束才释放。可防止丢失修改。

二级封锁协议：

一级封锁协议加上事务T在读取数据R之前先对其加S锁，读完后即可释放S锁。可防止丢失修改，还可防止读"脏" 数据。

三级封锁协议：

一级封锁协议加上事务T在读取数据R之前先对其加S锁，直到事务结束才释放。可防止丢失修改，防止读"脏"数据与防止数据重复读。

两段锁协议：

可串行化的。可能发生死锁。

死锁问题：

预防法

死锁的解除法

3.13 数据库完整性约束

实体完整性约束

参照完整性约束

用户自定义完整性约束

触发器

例如约束主键不能为空等情况。

触发器可以用于更加复杂的约束。

3.14 数据库安全

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

3.15 数据备份

冷备份：

也称为静态备份，是将数据库正常关闭，在停止状态下，将数据库的文件全部备份(复制)下来。

热备份：

也称为动态备份，是利用备份软件，在数据库正常运行的状态下，将数据库中的数据文件备份出来。

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

依据数据的量备份方式：

完全备份：

备份所有数据。

差量备份：

仅备份上一次完全备份之后变化的数据。

增量备份：

备份上一次备份之后变化的数据。这个"上一次备份"可以是这三个备份。备份速度快，但恢复麻烦。增量备份后系统出故障，则增量备份前所有备份都得恢复一遍。

转储也是一种备份。

静态海量转储：

在系统中无运行事务时进行，每次转储全部数据库。

静态增量转储：

在系统中无运行事务时进行，每次只转储上一次转储后更新过的数据。

动态海量转储：

转储期间允许对数据库进行存取或修改，每次转储全部数据库。

动态增量转储：

转储期间允许对数据库进行存取或修改，每次只转储上一次转储后更新过的数据。

日志文件：

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

3.16 数据库故障与恢复

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

3.17，数据仓库与数据挖掘

这个先略过

3.18，反规范化

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

技术手段：

增加派生性冗余列

增加冗余列

重新组表

分割表

4，大数据基本概念

数据量 Volume

速度   Velocity

多样性 Variety

值     Value

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

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

（高扩展，高性能，高容错，异构，短分析，接口，低成本，下兼容）

高度可扩展性

高性能

高度容错

支持异构环境

较短的分析延迟

易用且开放的接口

较低成本

向下兼容性

5，计算机网络

5.1，OSI/RM七层模型

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

数据链路层的设备是处于同个局域网，可以广播。物理层设备就相当于一条电线，没有啥功能。

当到网络层时，就把局域网给切断了。

5.2，网络技术标准与协议

TCP/IP协议：

Internet，可扩展，可靠，应用最广，牺牲速度和效率。

IPX/SPX协议：NOVELL，路由，大型企业网。

NETBEUL协议：IBM，非路由，快速。

应用层	应用层
	表示层
	会话层
传输层	传输层
Internet层	网络层
网络接口层	数据链路层
	物理层

网络接口层：以太网，令牌环，帧中继，ATM。

ARP：IP地址转MAC地址

RARP：MAC转IP

TCP的三次握手来建立连接。

DNS协议：

主机向本地域名服务器的查询采用递归查询。

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

递归查询：

服务器必需回答目标IP与域名的映射关系。

迭代查询：

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

根域名服务器负担重，效率低，故很少采用递归查询。

5.3，计算机网络的分类-拓扑结构

按分布范围分：

局域网LAN

城域网MAN

广域网WAN

因特网

按拓扑结构分：

总线型

星型

环型

5.4，网络规划与设计

网络规划原则：

实用性

开放性

先进性

网络设计任务：

确定网络总体目标

确定总体设计原则

通信子网设计

资源子网设计

设备选型

网络操作系统与服务器资源设备

网络安全设计

网络设计原则：

可用性：

指网络或网络设备可用于执行预期任务时间所占总量的百分比。

可靠性：

网络设备或计算机持续执行预定功能的可能性。

可恢复性：

指网络从故障中恢复的难易程度和时间。

适应性：

指在用户改变应用要求时网络的应变能力。

可伸缩性：

指网络技术或设备随着用户需求的增长而扩充的能力。

网络实施原则：

可靠性

安全性

高效性

可扩展性

网络实施步骤：

工程实施计划

网络设备到货验收

设备安装

系统测试

系统试运行

用户培训

系统转换

网络规划与设计-逻辑网络设计：

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

逻辑网络设计图

IP地址方案

安全方案

具体的软硬件，广域网连接设备和基本服务

招聘和培训网络员工的具体说明

对软硬件，服务，员工和培训的费用初步估计

网络规划与设计-物理网络设计：

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

网络物理结构图和布线方案

设备和部件的详细列表清单

软硬件和安装费用的估算

安装日程表，详细说明服务的时间以及期限

安装后的测试计划

用户的培训计划

网络规划与设计-分层设计(考的较多)：

接入层：向本地网段提供用户接入

汇聚层：网络访问策略控制，数据包处理，过滤，寻址

核心层：数据交换

5.5，IP地址与子网划分

IP地址：

A,B,C,D,E,类

子网划分：

子网掩码

将一个网络划分成多个子网(取部分主机号当子网号)

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

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

答：B类IP有固定有16位网络号，2＾5=32＞27，故要多留5位网络号，总共16+5=21位网络号。子网掩码为255.255.248.0

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

答：2＾10=1024＞700，故要留10位主机号

32-10=22位网络号。子网掩码为255.255.252.0

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

例题：分配给某公司网络的地址块是210.115.192.0/20，该网络可以被划分为______个C类子网。

答：16

5.6，特殊含义的IP地址

IP                                说明

127网段	回播地址
网络号全0地址	当前子网中的主机
全1地址	本地子网的广播
主机号全1地址	特定子网的广播
10.0.0.0/8	10.0.0.1至10.255.255.254
172.16.0.0/12	172.16.0.1至172.31.255.254
192.168.0.0/16	192.168.0.1至192.168.255.254
169.254.0.0	保留地址，用于DHCP失效(WIN)
0.0.0.0	保留地址，用于DHCP失效(Linux)

5.7，HTML

主要是html的一些标签，跟前端开发一样。

5.8，无线网

优势：

移动性

灵活性

成本低

容易扩充

接入方式：

有接入点模式

无接入点模式

802.11

无线局域网(WLAN，802.11，Wi-Fi)

无线城域网(WMAN，802.16，WiMax)

无线广域网(WWAN，3G/4G)

无线个人网(WPAN，802.15，Bluetooth)

5.9，网络接入技术

有线接入：

公用交换电话网络(PSTN)

数字数据网(DDN)

综合业务数字网(ISDN)

非对称数字用户线路(ADSL)

同轴光纤技术(HFC)

无线接入：

IEEE 802.11(WiFi)

IEEE 802.15(蓝牙Bluetooth)

红外(IrDA)

WAPI

3G/4G：

WCDMA

CDMA2000

TD-SCDMA（中国）

LTE-Advanced

WirelessMAN-Advanced(802.16m)(WiMAX)

5.10，IPv6

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

IP地址长度为128位，地址空间增大了2＾96倍。

灵活的IP报文头部格式。使用一系列固定格式的扩展头部取代了IPv4中可变长度的选项字段。IPv6中选项部分的出现方式也有所变化，使路由器可以简单路过选项而不做任何处理，加快了报文处理速度。

IPv6简化了报文头部格式，字段只有8个，加快报文转发，提高了吞吐量。

提高安全性。身份认证和隐私权是IPv6的关键特性。

支持更多的服务类型。

允许协议继续演变，增加新的功能，使之适应未来技术的发展。

单播地址(Unicast)：用于单个接口的标识符。

任播地址(Anycast)：泛播地址。一组接口的标识符，IPv4广播地址。

组播地址(Multicast)：IPv6中的组播在功能上与IPv4中的组播类似。

6，信息系统安全属性

6.1，安全属性：

保密性：最小授权原则，防暴露，信息加密，物理保密。

完整性：安全协议，校验码，密码校验，数字签名，公证。

可用性：

综合保障(IP过滤，业务流控制，路由选择控制，审计跟踪)

不可抵赖性：数字签名。

6.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。

缺陷：

加密强度不高

密钥分发困难

非对称加密技术：

加密和解密的密钥是不同的。公钥加密私钥解密，私钥加密公钥解密。

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

RSA：512位(或1024位)密钥，计算量极大，难破解（适用于X.509）。

Elgamal：其基础是Diffie-Hellman密钥交换算法。

ECC：椭圆曲线算法（适用于SM2数字证书）。

其它非对称算法包括：背包算法，Rabin，D-H

缺陷：加密速度慢，不适合加密大信息量数据。

平常的pdf，压缩包加密属于对称加密技术。

在实际应用过程中，对称跟非对称是互为补充的。往往用对称方式加密大内容，用非对称方式加密对称的密钥，来传密钥。（对称加密内容，非对称加密密钥）

6.3，信息摘要

简单来说：类似于论文的摘要，总概作用。

单向散列函数(单向Hash函数)，固定长度的散列值。

单向散列函数：可以通过明文获得摘要，但不能用摘要反向得到明文。

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

6.4，数字签名

主要是一种防抵赖技术。

理解一下数字签名过程：

A用私钥加密信息包发给B，B用A的公钥解密，而A的私钥只有A有，这说明A是用A的私钥加密信息包的，相当于A在这段信息包中做了签名。

一般来说，A用A的私钥来加密，这个过程叫做数字签名过程，不叫加密过程，而B用A的公钥解密的过程叫做数字签名的验证过程，不叫解密过程。

数字签名没有保密功能，只有识别身份的功能。

只对信息摘要进行数字签名。

6.5，数字信封与PGP

发送方将原文用对称密钥加密传输，而将对称密钥用接收方公钥加密发送给对方。

接收方收到电子信封，用自己的私钥解密信封，取出对称密钥解密得明文。

PGP是一种协议。是为了区分公钥属于谁的等等等。CA机构颁发数字证书。

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

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

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

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

6.6，练习题-设计邮件加密系统

6.7，网络安全-各个网络层次的安全保障

PGP	Https	SSL	应用层
			表示层
			会话层
TLS	SET		传输层
防火墙		IPSec	网络层
链路加密	PPTP	L2TP	数据链路层
隔离		屏蔽	物理层

PPTP，L2TP类似于在通道传输。

IPSec针对IP包加密。两种加密，一种是拆开加密，一种是整个包都加密，再复加一个头。

SET面向电子商务加密。

6.8，网络安全-网络威胁与攻击

威胁名称	描述
重放攻击(ARP)	所截获的某次合法的通信数据拷贝，出于非法的目的而被重新发送。（非法重发）
拒绝服务(DOS)	对信息或其它资源的合法访问被无条件地阻止。（合法被阻）
窃听	用各种可能的合法或非法的手段窃取系统中的信息资源和敏感信息。例如对通信线路中传输的信号进行搭线监听，或者利用通信设备在工作过程中产生的电磁泄露截取有用信息等。
业务流分析	通过对系统进行长期监听，利用统计分析方法对诸如通信频度，通信的信息流向，通信总量的变化等参数进行研究，从而发现有价值的信息和规律。（长期监听，发现规律）
信息泄露	信息被泄露或透露给某个非授权的实体。
破坏信息的完整性	数据被非授权地进行增删，修改或破坏而收到损失。
非授权访问	某一资源被某个非授权的人，或以非授权的方式使用。

威胁名称	描述
假冒	通过欺骗通信系统(或用户)达到非法用户冒充成为合法用户，或者特权小的用户冒充成为特权大的用户的目的。黑客大多是采用假冒进行攻击。（非法冒合法）
旁路控制	攻击者利用系统的安全缺陷或安全性上的脆弱之处获得非授权的权利或特权。例如，攻击者通过各种攻击手段发现原本应保密，但是却又暴露出来的一些系统"特性"。利用这些"特性"，攻击者可以绕过防线守卫者侵入系统的内部。（利用系统缺陷侵入）
授权侵犯	被授权以某一目的的使用某一系统或资源的某个人，却将此权限用于其它非授权的目的，也称作"内部攻击"。（有权限，但做无权限的事）
特洛伊木马	软件中含有一个察觉不出的或者无害的程序段，当它被执行时，会破坏用户的安全。
陷阱门	在某个系统或某个部件中设置了"机关"，使得当提供特定的输入数据时允许违反安全策略。
抵赖	这是一种来自用户的攻击，比如：否认自己曾经发布过的某条信息，伪造一份对方来信等。

6.9，网络安全-防火墙

网络级的防火墙只是检查IP数据包头部的信息，不会查看内部信息。（网络级防火墙只查头不查容）

应用级的防火墙会整个拆开来检查。

（应用级防火墙整体检查）

防火墙的双穴主机跟屏蔽主机不怎么考。

防火墙防外不防内。

7，数据结构与算法基础

7.1，课程内容提要

数组与矩阵

线性表(重点)

广义表

树和二叉树(重点)

图

排序与查找(重点)

算法基础及常见的算法(重点)

7.2，数组

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

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

解：每个元素大小len=2

默认初始地址为a，则该存储地址为a+(2*5+3)*2

7.3,稀疏矩阵

稀疏矩阵	示意图	要点
上三角矩阵	草稿纸有	在矩阵中下标分别为i和j的元素，对应的一维数组的下标计算公式为:(2n-i+1)*i/2+j
下三角矩阵	草稿纸有	在矩阵中下标分别为i和j的元素，对应的一维数组的下标计算公式为:(i+1)*i/2+j

上面这两个公式对应一维数组下标是从0开始的。如果不是从0开始的，那么公式最后要+1。

7.4，数据结构的定义

1，数据结构的概念

2，数据逻辑结构

线性结构

非线性结构:例如树，图

7.5，线性表的定义

1，线性表的概念

(a1,a2,....,an)

2,线性表常见的两种存储结构

顺序存储结构:

顺序表

链式存储结构:

链表:

单链表

循环链表

双向链表

链表的基本操作:

单链表删除结点

单链表插入结点

双向链表删除结点

双向链表插入结点

7.6，线性表-顺序存储与链式存储对比

性能类别	具体项目	顺序存储	链式存储
空间性能	存储密度	=1，更优	<1
	容量分配	事先确定	动态改变，更优
时间性能	查找运算	O(n/2)	O(n/2)
	读运算	O(1),更优	O([n+1]/2),最好情况为1，最坏情况为n
	插入运算	O(n/2),最好情况为0，最坏情况为n	O(1),更优
	删除运算	O([n-1]/2)	O(1)更优

存储密度是指空间利用率。

链式存储空间还要拿出一部分存储指针。

读的时候链式存储要从头结点一点一点找。

7.7，线性表-队列与栈

7.8，广义表

广义表是n个表元素组成的有限序列，是线性表的推广。

通常用递归的形式进行定义，记做:LS=(a0,a1,...,an)。

注:其中LS是表名，ai是表元素，它可以是表(称做子表)，也可以是数据元素(称为原子)。

其中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字母取出，操作就为？

解：

取表尾tail(LS1)=((b,c),(d,e))

再取表头head(tail(LS1))=(b,c)

再去表头head(head(tail(LS1)))=b

综上，答案为head(head(tail(LS1)))

7.9，树与二叉树

结点的度:

一个结点拥有的孩子结点数

树的度:

一个结点拥有的孩子结点数最 多的，也就是说哪个结点的度最高，就作为树的度。

叶子结点

分支结点

内部结点:

除了根结点和叶子结点之外的结点。

父结点:是相对的

子结点:是相对的

兄弟结点:同层的结点

层次:层数

二叉树的重要特性:

在二叉树的第i层上最多有2^(i-1)个结点，i>=1

深度为k的二叉树最多有2^k-1个结点，k>=1

对任何一颗二叉树，如果其叶子结点数为n0,度为2的结点数为n2,则n0=n2+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

7.10，树与二叉树-二叉树遍历

前序遍历:根，左，右

中序遍历:左，根，右

后序遍历:左，右，根

层次遍历:按层从左到右逐个遍历

7.11，树与二叉树-反向构造二叉树

   根据前序/中序/后序序列其中两个来构造出二叉树。

7.12，树与二叉树-树转二叉树

转的原则:

孩子结点-全部划为左子树结点

兄弟结点-全部划为右孩子结点

每个部分都按这样来

7.13，树与二叉树-查找二叉树(排序二叉树)

二叉排序树

左孩子小于根

右孩子大于根

插入结点:

若该键值结点已存在，则不再插入，如:48；

若查找二叉树为空树，则以新结点为查找二叉树；

将要插入结点键值与插入后父结点键值比较，就能确定新结点是父结点的左子结点，还是右子结点。

删除结点:

若待删除结点是叶子结点，则直接删除；

若待删除结点只有一个子结点，则将这个子结点与待删除结点的父结点直接连接，如:56；

若待删除的结点p有两个子结点，则在其左子树上，用中序遍历寻找关键值最大的结点s，用结点s的值代替结点p的值，然后删除结点s,结点s必属于上述第一行，第二行的情况之一，如:89；

7.14，树与二叉树-最优二叉树(哈夫曼树)

需要了解的基本概念:

树的路径长度:

树的路径有多长的问题，简单说就是叶子结点到根结点的路径条数。

权:

某个叶子结点的数值，代表这个结点的出现频度

带权路径长度:

权*路径长度

树的带权路径长度(树的代价):

将所有叶子结点的带权路径长度累加起来。

构造哈夫曼树的理念就是让最终树的带权路径长度最小。

7.15，树与二叉树-线索二叉树

为什么要有线索二叉树:

因为很多结点是没有孩子的，导致很多结点的左右指针都是空的。利用起这些空闲资源，串起来得到线索二叉树，便于遍历。

线索二叉树的概念：

就是在二叉树的基础上画上虚箭头就是线索二叉树。

线索二叉树的表示

如何将二叉树转化为线索二叉树

7.16，树与二叉树-平衡二叉树

平衡二叉树提出的原因:（其实就是排序二叉树的一种形式）

排序二叉树可以有多颗形式不同的排序二叉树

平衡二叉树的定义:

任意结点的左右子树深度相差不超过1

每结点的平衡度只能为-1，0或1

子结点的平衡度为0

结点的平衡度=左子树的深度-右子树的深度。

平衡树的建立过程

动态调平衡问题

7.17，图-基本概念

完全图:

在无向图中，若每对顶点之间都有一条边相连，则称该图为完全图。、

无向图的邻接矩阵是对称的

在有向图中，若每对顶点之间都有两条有向边相互连接，则称该图为完全图。

7.18，图的存储-领接矩阵

7.19，图的存储-邻接表（结点，权值，指针）

7.20，图-图的遍历

7.21，图-拓扑排序

  每取一个入度为0的结点，就将与其有关的箭头断掉，以此类推。

一般问哪个序列正确，这就要注意各顶点的约束关系了。

7.22，图的最小生成树-普里姆算法

这个算法简单来说就是取每个集合中顶点权值最小的那条边，使最后生成树的带权路径长度最小。用线连起来的为一个集合。

树没有环路，图可以有环路。

7.23，图的最小生成树-克鲁斯卡尔算法

这个比较容易，从边出发，直接选图中最小的边即可，但注意不能形成环路。

7.24，算法基础-算法的特性

有穷性:执行有穷步之后结束

确定性:算法中每一条指令都必须有确切的含义，不能含糊不清

输入(>=0):要有0个或者多个输入

输出(>=1):至少要有1个或以上输出

有效性:算法的每个步骤都能有效执行并能得到确定的结果。例如a=0,b/a就无效

7.25，算法基础-算法的复杂度

时间复杂度:

指程序运行从开始到结束所需要的时间。通常分析时间复杂度的方法是从算法中选取一种对于所研究的问题来说是基本运算的操作，以该操作重复执行的次数作为算法的时间度量。一般来说，算法中原操作重复执行的次数是规模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)=3n＾3+2n＾2+n，则T(n)=O(n＾3)。

常见的对算法执行所需时间的度量:

O(1)<O(log₂n)<O(n)<O(nlog₂n)<O(n＾2)<O(n＾3)<O(2ⁿ)

空间复杂度:

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

7.26，查找-顺序查找

顺序查找的思想:

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

7.27，查找-二分查找

基本思想:

(设R[low，....,high]是当前的查找区，这个序列是有序排列的)

确定该区间的中间位置:mid=[(low+high)/2]。注意，这里是取整。

将待查的k值与R[mid].key比较，

若相等，则查找成功并返回此位置，否则需确定新的查找区间，继续二分查找，具体方法如下:

若R[mid].key>k，则由表的有序性可知R[mid，....,n].key均大于k，因此若表中存在关键字等于k的结点，则该结点必定是在位置mid左边的子表R[low，....,mid-1]中。因此，新的查找区间是左子表R[low，....，high]，其中，high=mid-1

若R[mid].key<k，则要查找的k在mid的右子表R[mid+1，....,high]中，即新的查找区间是右子表R[low，....，high],其中low=mid+1

若R[mid].key=k，则查找成功，算法结束

下一次查找是针对新的查找区间进行，重复1，2步骤

在查找过程中，low逐步增加，而high逐步减少。如果high<low，则查找失败，算法结束。

二分查找也叫折半查找，折半查找在查找成功时关键字的比较次数最多为log₂n向下取整+1次

折半查找的时间复杂度为O(log₂n)

7.28，查找-散列表

基本思想:

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

解决存储位置冲突的方法:

线性探测法:

所属空间被占，就放在下一单元，以此类推。

只需一个循环来查找下一个空闲位置。

容易产生聚集现象，即哈希表中的某些位置被频繁使用，而其他位置很少被使用。

伪随机数法：

   生成随机数序列，具有随机性，可用于模拟实际随机事件。。

   实现较为复杂，需要算法来生成随机数

7.29，排序

排序的概念:

稳定与不稳定排序:

稳定是指序列中两个相同的值，排序前后的相对位置不变。

内排序与外排序:

内排序指在内存内的排序。

排序方法分类:

插入类排序:

直接插入排序

希尔排序

交换类排序:

冒泡排序

快速排序

选择类排序:

简单选择排序

堆排序

归并排序

基数排序

7.30，排序-直接插入排序

直接插入排序:

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

简单来说就是拿出一个跟其它值逐个比，直到合适。

7.31，排序-希尔排序

希尔(Shell)排序（其实就是一种分组插入）:

先取一个小于n的整数d₁作为第一个增量，把文件的全部记录分成d₁个组。所有距离为d₁的倍数的记录放在同一个组中。先在各组内进行直接插入排序(同一组内两两比较，判断是否交换)，然后，取第二个增量d₂<d₁重复上述的分组和排序，直至所取的增量dt=1(dt<d(t-1)<0<d₂<d₁)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。

7.32，直接选择排序

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

7.33，堆排序

堆排序的基本思想为:

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

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

（1）初始时将顺序表R[1...n]中元素建立为一个大顶堆，堆顶位于R[1]，待序区为R[1...n]。

（2）循环执行步骤3-步骤4，共n-1次。

（3）假设为第i次运行，则待序区为R[1...n-i+1],将堆顶元素R[1]与待序区尾元素R[n-i+1]交换，此时顶点元素被输出，新的待序区为R[1..n-i]。

（4）待序区对应的堆已经被破坏，将之重新调整为大顶堆。

建堆时按完全二叉树顺次来建：

从最后一个非叶子结点开始调，跟他的孩子比较决定是否交换。

接着调倒数第二个非叶子结点，也是跟他的孩子比较决定是否交换，以此类推，但是如果说该非叶子结点的孩子还有孩子，则要一起进行比较调整。

当取走堆顶时，对堆进行调整，先将最后一个叶子结点替补它，然后按照大/小顶堆的要求以此跟它孩子比较决定是否交换。

每一次只能取出一个堆顶元素，适合那种取出前几名的数据。

7.34，冒泡排序

基本思想是:

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

7.35，快速排序

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

两个步骤:

第一步，在待排序的n个记录中任取一个记录，以该记录的排序码为准，将所有记录都分成两组，第一组都小于该数，第二组都大于该数，如图所示。

第二步，采用相同的方法对左，右两组分别进行排序，直到所有记录都排到相应的位置为止。

7.36，归并排序

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

7.37，基数排序(考的少)

（就是用个位，十位等位数来选择数值）

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

7.38，排序算法的时间复杂度和空间复杂度

类别	排序方法	时间复杂度		空间复杂度	稳定性
		平均情况	最坏情况	辅助存储
插入排序	直接插入	O(n²)	O(n²)	O(1)	稳定
	Shell排序	O(n＾1.3)	O(n²)	O(1)	不稳定
选择排序	直接选择	O(n²)	O(n²)	O(1)	不稳定
	堆排序	O(nlog₂n)	O(nlog₂n)	O(1)	不稳定
交换排序	冒泡排序	O(n²)	O(n²)	O(1)	稳定
	快速排序	O(nlog₂n)	O(n²)	O(log₂n)	不稳定
归并排序		O(nlog₂n)	O(nlog₂n)	O(n)	稳定
基数排序		O(d(r+n))	O(d(r+n))	O(r+n)	稳定

稳定是指元素排序前后相对位置没变过。

8，程序设计语言与语言处理程序基础前言

8.1，课程内容提要

编译与解释:

文法:

正规式:重要

有限自动机:

表达式:重要

传值与传址:重要

多种程序语言特点:

8.2，编译过程

词法错误:

非法字符，关键字或标识符拼写错误

语法分析:

语法结构出错，if，endif不匹配，缺分号

语义错误:

死循环，零除数，其它逻辑错误

8.3，文法定义

闭包之类的几乎不考

文法类型:

类型	别称	说明	对应自动机
0型	短语文法	G的每条产生式α→β满足a属于V的正则闭包且至少含有一个非终结符，而β属于V的闭包	图灵机
1型	上下文有关文法	G的任何产生式α→β满足|α|<=|β|，仅仅S→ε例外，但S不得出现在任何产生式右部。	线性界限自动机
2型	上下文无关文法	G的任何产生式为A→β,A为非终结符，β为V的闭包	非确定的下推自动机
3型	正规文法	G的任何产生式为A→αB或A→α，α属于非终结符的闭包，A,B都属于非终结符	有限自动机

8.4，语法推导树

一颗语法树应具有以下特征:

每个结点都有一个标记，此标记是V的一个符号；

根的标记是S；

若一结点n至少有一个它自己除外的子孙，并且有标记A，则A肯定在Vₙ中；

如果结点n的直接子孙，从左到右的次序是结点n1,n2,...,nk，其标记分别是:A1,A2,...,Ak，那么A→A1,A2,...,Ak，一定是P中的一个产生式。

8.5，有限自动机

8.6，正则式

8.7，程序语言基础-表达式

8.8，函数调用-传值与传址

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

传值相当于把实参的值复制到形参的空间里。传址相当于把实参的地址交给了形参，形参的空间就存储着指向实参的指针，一但形参的值发生改变，就等于指向实参的指针发生改变。

8.9，程序语言基础-各种程序语言特点

Fortran语言(科学计算，执行效率高)

Pascal语言(为教学而开发的，表达能力强，Delphi)

C语言(指针操作能力强，高效)

Lisp语言(函数式程序语言，符号处理，人工智能)

C++语言(面向对象，高效)

Java语言(面向对象，中间代码，跨平台)

C#语言(面向对象，中间代码，.Net)

Prolog语言(逻辑推理，简洁性，表达能力，数据库和专家系统)

9，法律法规(2-3分)

9.1，法律法规-课程内容提要

从所涉及的法律法规角度

著作权法

计算机软件保护条例

商标法

专利法

没有涉及知识产权法

从试题考点分布的角度(主要靠这个)

保护期限

知识产权人确定

侵权判断

知识产权:

著作权及邻接权:

邻接权就是例如有人盗版我的书，那么我书的出版商的权利也给侵犯了。

专利权

工业品外观设计权

商标权

地理标志权:

例如水果店哈密瓜贴了个新疆哈密瓜，但这个哈密瓜不是新疆产的，就侵权了。

集成电路布图设计权(不需要了解)

9.2，法律法规-保护期限

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

署名权例如李白，杜甫的诗集是无限制的，那样才知道作者是李白，杜甫。

署名权、修改权、保护作品完整权没有时间限制

9.3，法律法规-知识产权人确定

情况说明		判断说明	归属
作品	职务作品	利用单位的物质技术条件进行创作，并由单位承担责任的	除署名权外其他著作权归单位
		有合同约定，其著作权属于单位	除署名权外其他著作权归单位
		其他	作者拥有著作权，单位有权在业务范围内优先使用
软件	职务作品	属于本职工作中明确规定的开发目标	单位享有著作权
		属于从事本职工作活动的结果	单位享有著作权
		使用了单位资金，专用设备，未公开的信息等物质，技术条件，并由单位或组织承担责任的软件	单位享有著作权
专利权	职务作品	本职工作中作出的发明创造	单位享有专利
		履行本单位交付的本职工作之外的任务所作出的发明创造	单位享有专利
		离职，退休或调动工作后1年内，与原单位工作相关	单位享有专利

情况说明		判断说明	归属
作品软件	委托创作	有合同约定，著作权归委托方	委托方
		合同中未约定著作权归属	创作方
	合作开发	只进行组织，提供咨询意见，物质条件或者进行其他辅助工作	不享有著作权
		共同创作的	共同享有，按人头比例。成果可分割的，可分开申请。
商标		谁先申请谁拥有(除知名商标的非法抢注)，不管谁先使用。 同时申请，则根据谁先使用(需提供证据)。 无法提供证据，协商归属，无效时使用抽签(但不可不确定)
专利		谁先申请谁拥有。同时申请则协商归属，但不能够同时驳回双方的专利申请。

9.4，侵权判定

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

开发软件所用的思想，处理过程，操作方法或者数学概念不受保护。如果真的有独到之处，可以申请专利，专利法保护。

著作权法不适用下列情形:

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

时事新闻；

历法，通用数表，通用表格和公式。

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

注意跟钱挂钩的行为。

9.5，标准化基础知识-标准的分类

国际标准:

ISO，IEC等国际标准化组织。

国家标准:重点

GB-中国，ANSI-美国，BS-英国，JIS-日本。

区域标准:

又称为地区标准，如

PASC 太平洋地区标准会议，

CEN 欧洲标准委员会，

ASAC 亚洲标准咨询委员会，

ARSO 非洲地区标准化组织。

行业标准:重点

GJB 中国军用标准，

MIT-S 美国军用标准

IEEE 美国电气电子工程师协会

地方标准:

国家的地方一级行政机构制订的标准。

企业标准

项目规范

9.6，标准化基础知识-标准的编号

国际，国外标准代号:

标准代号+专业类号+顺序号+年代号

我国国家标准代号:

强制性标准代号为GB，推荐性标准代号为GB/T，指导性标准代号为GB/Z，实物标准代号GSB。

行业标准代号:

由汉语拼音大写字母组成(如电子行业为SJ)。

地方标准代号:

由DB加上省级行政区划代码的前两位。

企业标准代号:

由Q加上企业代号组成。

10，多媒体基础前言(1-3分)

10.1，课程内容提要

多媒体技术基本概念

多媒体相关计算问题

常见多媒体标准

数据压缩技术

10.2，多媒体技术基本概念-音频相关概念

声音的带宽:

人耳:20Hz-20kHz

说话:300-3400Hz

乐器:20Hz-20kHz

采样:

采样频率

采样精度

采样频率应为声音最高频率的2倍(这样才可以保障不失帧)

大于人耳20kHz的为超声波，小于人耳20Hz的为次声波。

固定电话采样频率一般是8k。

CD印制往往是40k以上。

10.3，多媒体技术基本概念-图像相关概念

亮度

色调(红，绿)

饱和度(颜色看起来是否鲜艳)

彩色空间:

RGB

YUV(电视，兼容):

衍生出YIQ，ycbcr

CMY(CMYK):

CMK调色比较贵，故用CMYK。

HSV(HSB)

光的三原色:

red，green，blue

印刷三原色:

cyan，magenta， yellow

10.4，多媒体技术基本概念-媒体的种类

感觉媒体:

指人们接触信息的感觉形式。如:视觉，听觉，触觉，嗅觉和味觉等。

表示媒体:

指信息的表示形式。如:文字，图形，图像，动画，音频和视频等。

显示媒体(表现媒体):

表现和获取信息的物理设备。如:输入显示媒体键盘，鼠标和麦克风等，输出显示媒体显示器，打印机和音箱等。

存储媒体:

存储数据的物理设备，如磁盘，光盘和内存等。

传输媒体:

传输数据的物理载体，如电缆，光缆和交换设备等。

10.5，多媒体技术基本概念-多媒体相关计算问题

图像容量计算:

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

音频容量计算:

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

这个“量化/采样位数(位)”就是样本精度。

视频容量计算:

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

实例:

图像容量计算:

例题:某数码相机内置128MB的存储空间，拍摄分辨率设定为1600*1200像素，颜色深度为24位，若不采用压缩存储技术，使用内部存储器最多可以存储_____张照片。

解:1600*1200*24÷8=5760000B

5760000/1024/1024=5.493MB

124/5.493=23.3张，故最多可存储23张。

音频容量计算:

例题:CD上声音的采样频率为44.1KHz，样本精度为16bit，双声道立体声，那么其未经压缩的数据传输率为_____。

解:44.1*16*2=1411.2kb。故最终答案是1411.2kb。

视频容量计算:

例题:若视频图像每帧的数据量为6.4MB，帧速率为30帧/秒，则显示10秒的视频信息，其原始数据量为_____MB。

解:6.4*30*10=1920MB。故最终答案为1920MB。

你会发现，计算音频跟视频跟公式不太一样，这要注意。

传输数据时k是1000，存储的时候的k是1024。

10.6，常见多媒体标准

JPEG:有损，RGB转YUV，离散余弦(扩展名为.jpg)

JPEG-2000:有损与无损都有，压缩比更高，小波变换，医学图像应用

MPEG-1:离散余弦，VCD，MP3

MPEG-2:离散余弦，Huffman，DVD，有线/卫星电视，AAC

MPEG-4:网络应用/可视电话，无线通信，增强交互性，数码权限管理，多媒体传输集成框架

MPEG-7:多媒体内容描述接口，具备描述功能，不是编码标准

MPEG-21:融合不同协议，制定新标准，标准集成

有损就表示被压缩了。

10.7，数据压缩基础

空间冗余(几何冗余)

时间冗余

视觉冗余

信息熵冗余

结构冗余

知识冗余

10.8，有损压缩与无损压缩

一类是无损压缩编码法，也称冗余压缩法或熵编码法。

另一类是有损压缩编码法，也称为熵压缩法。

无损压缩是可以还原的，例如WINRAR压缩。

有损压缩是不可以还原的，已经丢失一些信息了，例如jpg图片。

常见无损编码:

变长编码:Huffman，Shannon-FannO等

行程编码

算术编码

其他编码

常见有损编码:

预测编码:运动补偿预测，自适应预测，线型顶测，非线形预测，δ调制等。

变换编码:

KLT，DCT，ADCT，DWT等

基于模型编码:

分形编码，轮廓编码，识别合成编码等

直接影射:

矢量量化，神经网络等

其他编码

11，软件工程基础

11.1，软件开发模型

模型	方法
瀑布模型	迭代模型/迭代开发方法
演化模型	快速应用开发
增量模型	构件组装模型/基于构件的开发方法
螺旋模型	统一过程/统一开发方法
快速原型模型（小型项目）	敏捷开发方法（小型项目）
喷泉模型	模型驱动的开发方法
V模型	基于架构的开发方法

11.2，软件开发模型-瀑布模型(SDLC)

这个是按照需求不变的情况下从头做到尾，但当需求变化时要往前重新改，这样往往导致失败，所以这个面临淘汰。

11.3，软件开发模型-快速原型模型（不带反馈环）

面对需求不明确情况下，快速构造简易系统，让用户先了解大概，再让用户的需求能够明确，最后根据需求对这个系统进行多轮调整

这个只适用于需求分析阶段。

11.4增量模型

一部分一部分开发功能模块，然后给用户使用，相当于给用户审视，风险小。

11.5，螺旋模型

螺旋模型里面包含了原型，但是考试的时候同时出现了螺旋模型和原型模型，只能选原型，考试遵循最匹配原则。大型项目。

只有这个引入了风险分析

11.6，V模型

把测试分得很细，重视了测试部分

在需求分析阶段时就已经开始验收测试和系统测试了，这样可以从测试眼光看待问题

概要设计时同时进行集成测试计划

详细计划时同时进行单元测试计划

说明测试贯穿开发的始终。

11.7，喷泉模型

是一种面向对象的模型，独特一点

特点:

迭代

无间隙

11.8，快速开发模型(RAD)

结合了瀑布模型SDLC和构件化开发CBSD的特点

特点是能快速构建应用系统

11.9，构件组装模型(CBSD)

广泛认可与应用

把功能做成构件，再把构件组装形成软件

提高了复用性，开发效率提高。

11.10，统一过程(UP或RUP)

可应用于一些大型项目

结合草稿纸的图形:

初始:

确定项目范围和边界

识别系统的关键用例

展示系统的候选架构

估计项目费用和时间

评估项目风险

细化:

分析系统问题领域

建立软件架构基础

淘汰最高风险元素

构建:

开发剩余的构件

构件组装与测试

交付:

进行β测试

制作发布版本

用户文档定稿

确认新系统

培训，调整产品

开发的二八定理:

20%来需求分析

80%系统开发

α测试指有开发人员陪同测试

β测试指让用户去使用来测试

11.11，敏捷开发方法

属于比较年轻的一类

这个方法不是一个模型，而是一组模型

比较适合做小型项目，强调小步快跑

11.12，信息系统开发方法

结构化法:

(方法是比较固定的，不灵活的，例如瀑布模型)

用户至上

严格区分工作阶段，每阶段有任务与成果

强调系统开发过程的整体性和全局性

系统开发过程工程化，文档资料标准化

自顶向下，逐步求解(求精)

原型法:

适用于需求不明确的开发

包括抛弃式原型和演化式原型

面向对象方法:

更好的复用性

关键在于建立一个全面，合理，统一的模型

分析，设计，实现三个阶段，界限不明确

面向服务方法:(新方法，还不成熟)

SO方法有三个主要的抽象级别:操作，服务，业务流程

SOAD分为三个层次:

基础设计层(底层服务构件)

应用结构层(服务之间的接口和服务级协定)

业务组织层(业务流程建模和服务流程编排)

服务建模:分为服务发现，服务规约和服务实现三个阶段

11.13，需求开发-需求分类与需求获取

11.14，结构化设计-基本原则

保持模块的大小适中

尽可能减少调用的深度

多扇入，少扇出

单入口，单出口

模块的作用域应该在模块之内

功能应该是可预测的

11.15，结构化设计-内聚与耦合

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

以上表格，内聚从高到低按功能内聚到偶然内聚排序

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

以上表格，耦合从低到高按非直接耦合到内容耦合。

11.16，结构化设计-系统结构/模块结构

   变换型系统结构

   事务型系统结构

   混合型系统结构

11.17，软件测试-测试原则与类型

尽早，不断的进行测试

程序员避免测试自己设计的程序

既要选择有效，合理的数据，也要选择无效，不合理的数据

修改后应进行回归测试

尚未发现发错误数量与该程序已发现错误数成正比

动态测试:

黑盒测试法

白盒测试法

灰盒测试法

静态测试:

桌前检查

代码走查

代码审查

11.18，软件测试-测试用例设计

黑盒测试:

等价类划分

边界值分析

错误推测

因果图

白盒测试:

基本路径测试

循环覆盖测试

逻辑覆盖测试

逻辑覆盖测试：

语句覆盖

判定覆盖

条件覆盖

条件判定覆盖

修正的条件判断覆盖

条件组合覆盖

点覆盖

边覆盖

路径覆盖

11.19，软件测试-测试阶段

11.20，软件测试-McCabe复杂度

11.21，系统运行与维护

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

可维护性:

易分析性

易改变性

稳定性

易测试性

维护类型:

改正性维护  25%

适应性维护  20%

完善性维护  50%

预防性维护  5%

11.22，软件过程改进-CMMI

阶段式:

组织成熟度等级	过程域
一，混乱级	-
二，已管理级	需求管理，项目计划，配置管理，项目监督与控制，供应商合同管理，度量和分析，过程和产品质量保证
三，已定义级	需求开发，技术解决方案，产品集成，验证，确认，组织级过程焦点，组织级过程定义，组织级培训，集成项目管理，风险管理，集成化的团队，决策分析和解决方案，组织级集成环境
四，定量管理级	组织级过程性能，定量项目管理
五，优化级	组织级改革与实施，因果分析和解决方案

连续式:

连续式分组	过程域
过程管理	组织级过程焦点，组织级过程定义，组织级培训，组织级过程性能，组织级改革与实施
项目管理	项目计划，项目监督与控制，供应商合同管理，集成项目管理，风险管理，集成化的团队，定量项目管理
工程	需求管理，需求开发，技术解决方案，产品集成，验证，确认
支持	配置管理，度量和分析，过程和产品质量保证，决策分析和解决方案，组织级集成环境，因果分析和解决方案

11.23，项目管理

九大知识领域:

范围管理

时间管理

成本管理

质量管理

人力资源管理

沟通管理

风险管理

采购管理

整体管理

11.24，需求开发-需求分析-OOA-相关概念

对象

类(实体类，边界类，控制类):

边界类:一些类需要跟外界交互

控制类:类与类之间需要衔接

抽象

封装:把相关的东西封装在一起

继承与泛化:

泛化:多个类有共同的东西，抽出来形成一个上层的类

多态:

同样的操作，控制不同的对象，操作有差异。简单来说就是一个操作，控制多个对象形式各自的内容。

接口:

特殊的类，只有方法的定义，没有方法的实现

消息:

异步

组件

模式和复用

11.25，面向对象设计-设计原则

单一职责原则:设计目的单一的类

开放-封闭原则:对扩展开放，对修改封闭

李氏替换原则:子类可以替换父类

依赖倒置原则:

要依赖于抽象，而不是具体实现。针对接口编程，不要针对实现编程。

接口隔离原则:使用多个专门的接口比使用单一的总接口要好

组合重用原则:要尽量使用组合，而不是继承关系达到重用目的。

迪米特原则(最少知识法则):一个对象应当对其他对象有尽可能少的了解

一个类实现的职责越多，越容易跟其他类耦合。

11.26，需求开发-需求分析-OOA-UML

11.27，面向对象设计-设计模式的概念

架构模式:

软件设计中的高层决策，例如C/S结构就属于架构模式，架构模式反映了开发软件系统过程中所作的基本设计决策。

设计模式:

主要关注软件系统的设计，与具体的实现语言无关

惯用法:

是最低层的模式，关注软件系统的设计与实现，实现时通过某种特定的程序设计语言来描述构件与构件之间的关系。每种编程语言都有它自己特定的模式，即语言的惯用法。例如引用-计数就是C++语言中的一种惯用法。

一般到构件时用到设计模式

例如建房子，整体的框架是架构模式，里面各个部分的设计是设计模式。

11.28，面向对象设计-设计模式的分类

创建型模式:

工厂方法模式

抽象工厂模式

原型模式

单例模式

构建器模式

结构型模式:(主要是处理类和对象的组合)

适配器模式

桥接模式

组合模式

装饰模式

外观模式

亨元模式

代理模式

行为型模式:(主要是描述类和对象交互的情况，以及职责的分配问题)

职责链模式

命令模式

解释器模式

迭代器模式

中介者模式

备忘录模式

观察者模式

状态模式

策略模式

模板方法模式

访问者模式

有下划线的表示既可以是类模式，也可以是对象模式。无下划线的表示只是对象模式。

11.29，面向对象设计-创建型模式

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

11.30，面向对象设计-结构型模式

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

11.31，面向对象设计-行为型模式

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

11.31，数据流图(DFD)15分

考试题型稳定

课程内容提要:

数据流图基本概念

数据字典

数据平衡原则

11.32，数据流图基本概念

元素	说明	图元
数据流	由一组固定成分的数据组成，表示数据的流向。每个数据流通常有一个合适的名词，反映数据流的含义	→
加工	加工描述了输入数据流到输出数据流之间的变换，也就是输入数据流做了什么处理后变成了输出数据流	○  圆矩形
数据存储(文件)	用来表示暂时存储的数据，每个文件都有名字。流向文件的数据流表示写文件，流出的表示读文件
外部实体	指存在于软件系统外的人员或组织	矩形

11.33，数据流图的分层(DFD)

数据流图也叫分层数据流图

11.34，数据字典

符号	含义	举例说明
=	被定义为
+	与	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”

终点=[长沙|上海|北京|西安]

11.35，数据流图平衡原则

两个维度:

父图与子图之间的平衡:

也就是顶层图与0层图的数据流要一致，没有的就是缺失的。

子图内平衡:

只有输入没有输出的称为"黑洞"

只有输出没有输入的称为"奇迹"

加工输入不足以产生输出的称为"灰洞"

11.36，数据流图答题技巧

详细分析试题说明:

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

提取:

数据管理员是一个外部实体。

中间件中有"用户管理""操作管理""权限管理"这些加工。

中间件中有"用户表"这个数据存储，且该存储与"用户管理"相关。

后端数据库是一个外部实体。

中间件中有"操作表"这个数据存储，且该存储与"操作管理"相关。

中间件中有""权限表这个数据存储，且该存储与"权限管理"相关。

利用数据平衡原则:

例题:

看草稿纸

11.37，数据流图的案例1

阅读下列说明和图，回答问题1至问题4，将解答填入答题卡的对应栏内。【说明】

某大型企业的数据中心为了集中管理，控制用户对数据的访问并支持大量的连接需求，欲构建数据管理中间件，其主要功能如下:

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

(2)中间件验证前端应用提供的用户信息。若验证不通过，返回非法用户信息；若验证通过，中间件将等待前端应用提交操作请求。

(3)前端应用提交操作请求后，中间件先对请求进行格式检查。如果格式不正确，返回格式错误信息；如果格式正确，则进行权限验证(验证用户是否有权执行请求的操作)，若用户无权执行该操作，则返回权限不足信息，否则进行连接管理。

(4)连接管理连接相应的后台数据库并提交操作。连接管理先检查是否存在空闲的数据库连接，如果不存在，新建连接；如果存在，则重用连接。

(5)后端数据库执行操作并将结果传给中间件，中间件对收到的操作结果进行处理后，将其返回给前端应用。

现采用结构化方法对系统进行分析与设计，获得如图11-1所示的顶层数据流图和图11-2所示的0层数据流图。

【问题1】3分。

使用说明中的词语，给出图11-1中的实体E1-E3的名称。

【问题2】3分。

使用说明中的词语，给出图11-2中的数据存储D1-D3的名称。

【问题3】6分。

给出图11-2中加工P的名称及其输入，输出流。

	名称	起点	终点
输入流
输出流		p

除加工p的输入与输出流外，图11-2还缺失了两条数据流，请给出这两条数据流的起点和终点。

起点	终点

注:名称使用说明中的词汇，起点和终点均使用图11-2中的符号或词汇。

【问题4】3分。

在绘制数据流图时，需要注意加工的绘制。请给出三种在绘制加工的输入，输出时可能出现的错误。

11.38，数据流图案例2

阅读以下说明和数据流图，回答问题1至问题4，将解答填入答题纸的对应栏内。

【说明】

现准备为某银行开发一个信用卡管理系统CCMS，该系统的基本功能为:

1.信用卡申请。非信用卡客户填写信用卡申请表，说明所要申请的信用卡类型及申请者的基本信息，提交CCMS。如果信用卡申请被银行接受，CCMS将记录该客户的基本信息，并发送确认函给该客户，告知客户信用卡的有效期及信贷限额；否则该客户将会收到一封拒绝函。非信用卡客户收到确认函后成为信用卡客户。

2.信用卡激活。信用卡客户向CCMS提交激活请求，用信用卡号和密码激活该信用卡。激活操作结束后，CCMS将激活通知发送给客户，告知客户其信用卡是否被成功激活。

3.信用卡客户信息管理。信用卡客户的个人信息可以在CCMS中进行在线管理。每位信用卡客户可以在线查询和修改个人信息。

4.交易信息查询。信用卡客户使用信用卡进行的每一笔交易都会记录在CCMS中，信用卡客户可以通过CCMS查询并核实其交易信息(包括信用卡交易记录及交易额)。

图11-3和图11-4分别给出了该系统的顶层数据流图和0层数据流图的初稿。

【问题1】3分。

根据【说明】，将图11-3中的E1-E3填充完整。

【问题2】3分。

图11-3中缺少三条数据流，根据【说明】，分别指出这三条数据流的起点和终点。(注:数据流的起点和终点均采用图中的符号和描述)

【问题3】5分。

图11-4中有两条数据流是错误的，请指出这两条数据流的名称，并改正。(注:数据流的起点和终点均采用图中的符号和描述)

【问题4】4分。

根据【说明】，将图11-4中的P1-P4的处理名称填充完整。

以上两个例题的图和答案在草稿纸。草稿纸的答案格式不是很准确，要看自己刷题看解析总结，但是答案是正确的。

11.39，数据库设计

课程内容提要:

数据库设计过程

ER模型

答题技巧

主要是ER模型，ER模型转关系模式，关系模式

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

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

11.41，数据库设计答题技巧(题型较稳定)

详细分析试题说明

熟练掌握基本知识

11.41，数据库实例试题1

希赛公司拟开发一个宾馆客房预订子系统，主要是针对客房的预订和入住等情况进行管理。

【需求分析结果】

（1）员工信息主要包括:员工号，姓名，出生年月，性别，部门，岗位，住址，联系电话和密码等信息。岗位有管理和服务两种。岗位为"管理"的员工可以更改(添加，删除和修改)员工表中的本部门员工的岗位和密码，要求将每一次更改前的信息保留；岗位为"服务"的员工只能修改员工表中本人的密码，且负责多个客房的清理等工作。

（2）部门信息主要包括:部门号，部门名称，部门负责人，电话等信息；一个员工只能属于一个部门，一个部门只有一位负责人。

 （3）客房信息包括:客房号，类型，价格，状态等信息。其中类型是指单人间，三人间，普通标准间，豪华标准间等；状态是指空闲，入住和维修。

（4）客户信息包括:身份证号，姓名，性别，单位和联系电话。

（5）客房预定情况包括:客房号，预定日期，预定入住日期，预定入住天数，身份证号等信息。一条预定信息必须仅对应一位客户，但一位客户可以有多条预定信息。

【概念模型设计】

根据需求阶段收集的信息，设计的实体-联系图(不完整)如图12-1所示。

【逻辑结构设计】

逻辑结构设计阶段设计的部分关系模式(不完整)如下:

员工( (4)，姓名，出生年月，性别，岗位，住址，联系电话，密码)

权限(岗位，操作权限)

部门(部门号，部门名称，部门负责人，电话)

客房((5)，类型，价格，状态，入住日期，入住时间，员工号)

客户((6)，姓名，性别，单位，联系电话)

更改权限(员工号，(7)，密码，更改日期，更改时间，管理员号)

预定情况((8)，预定日期，预定入住日期，预定入住天数)

【问题1】3分。

根据问题描述，填写图12-1中(1)-(3)处联系的类型。联系类型分为一对一，一对多和多对多3种，分别使用1:1，1:n或1:*，m:n或*:*表示。

【问题2】2分。

补充图12-1中的联系并指明其联系类型。

【问题3】7分。

根据需求分析结果和图12-1，将逻辑结构设计阶段生成的关系模型中的空(4)-(8)补充完整。(注:一个空可能需要填多个属性。)

【问题4】3分。

若去掉权限表，并将权限表中的操作权限属性放在员工表中(仍保持管理和服务岗位的操作权限规定)，则与原有设计相比有什么优缺点(请从数据库设计的角度进行说明)。

答案和图在草稿纸上。

11.42，数据库实例试题2

阅读下列说明，回答问题1至问题3，将解答填入答题纸的对应栏内。

【说明】

某集团公司拥有多个大型连锁商场，公司需要构建一个数据库系统以方便管理其业务运作活动。

【需求分析结果】

1.商场需要记录的信息包括商场编号(编号唯一)，商场名称，地址和联系电话。

某商场信息如表12-1所示。

                   表12-1 商场信息表

商场编号	商场名称	地址	联系电话
PS2101	淮海商场	淮海中路918号	021-64158818
PS2902	西大街商场	西大街时代盛典大厦	029-87283220
PS2903	东大街商场	碑林区东大街239号	029-87450287
PS2901	长安商场	雁塔区长安中路38号	029-85264953

2.每个商场包含有不同的部门，部门需要记录的信息包括部门编号(集团公司分配)，部门名称，位置分布和联系电话。某商场的部门信息如表12-2所示。

                    表12-2 部门信息表

部门编号	部门名称	位置分布	联系电话
DT002	财务部	商场大楼六层	82504342
DT007	后勤部	商场地下副一层	82504347
DT021	安保部	商场地下副一层	82504358
DT005	人事部	商场大楼六层	82504446
DT001	管理部	商场裙楼三层	82504668

3.每个部门雇用多名员工处理日常事务，每名员工只能隶属于一个部门(新进员工在培训期不隶属于任何部门)。员工需要记录的信息包括员工编号(集合公司分配)，姓名，岗位，电话号码和工资。员工信息如表12-3所示。

                     表12-3 员工信息表

员工编号	姓名	岗位	电话号码	工资
XA3310	周超	理货员	13609257638	1500.00
SH1075	刘飞	防损员	13477293487	1500.00
XA0048	江雪花	广播员	15234567893	1428.00
BJ3132	张正华	部门主管	13345698432	1876.00

4.每个部门的员工中有一名是经理，每个经理只能管理一个部门，系统需要记录每个经理的任职时间。

【问题1】6分。

根据问题描述，补充四个联系，完善图12-2的实体联系图。联系名可用联系1，联系2，联系3和联系4代替，联系的类型分为1:1，1:n和m:n。

【问题2】6分。

根据实体联系图，将关系模型中的空(a)-(c)补充完整，并分别给出部门，员工和经理关系模式的主键和外键。

【问题3】3分。

为了使商场有紧急事务时能联系到轮休的员工，要求每位员工必须且只能登记一位紧急联系人的姓名和联系电话，不同的员工可以登记相同的紧急联系人。则在图12-2中还需添加的实体是(1)，该实体和图12-2中的员工存在什么联系(填写联系类型)。给出该实体的关系模式。

答案和图在草稿纸上。

11.43，UML建模(稳定的必出，图多，难度略大，变化大)

课程内容提要:

    用例图

    类图与对象图

    顺序图

    活动图

    状态图

    通信图

    构建图

UML考查一般有涵盖用例图，类图。

各图都已画在草稿纸上。

类图与对象图，类与类的聚合关系（可理解为包含关系），箭头指向被包含的对象。

11.44，UML案例分析试题1

    已知某唱片播放器不仅可以播放唱片，而且可以连接电脑并把电脑中的歌曲刻录到唱片上(同步歌曲)。连接电脑的过程中还可自动完成充电。

    关于唱片，还有以下描述信息:

    （1）每首歌曲的描述信息包括:歌曲的名字，谱写这首歌曲的艺术家以及演奏这首歌曲的艺术家。只有两首歌曲的这三部分信息完全相同时，才认为它们是同一首歌曲。艺术家可能是一名歌手或一支由2名或2名以上的歌手所组成的乐队。一名歌手可以不属于任何乐队，也可以属于一个或多个乐队。

    （2）每张唱片由多条音轨构成；一条音轨中只包含一首歌曲或为空，一首歌曲可分布在多条音轨上；同一首歌曲在一张唱片中最多只能出现一次。

    （3）每条音轨都有一个开始位置和持续时间。一张唱片上音轨的次序是非常重要的，因此对于任意一条音轨，播放器需要准确地知道，它的下一条音轨和上一条音轨是什么(如果存在的话)。

    根据上述描述，采用面向对象方法对其进行分析与设计，得到了如表13-1所示的类列表，如图13-1所示的初始类图以及图13-2所示的描述播放器行为的UML状态图。

【问题1】

根据题目中的描述，使用表13-1给出的类的名称，给出图13-1中的A-F所对应的类。

【问题2】

根据题目中的描述，给出图13-1中(1)-(6)处的多重度。

【问题3】

图13-1中缺少了一条关联，请指出这条路关联两端所对应的类以及每一端的多重度。    

类	多重度

【问题4】

根据图13-2所示的播放器行为UML状态图，给出从"关闭"状态到"播放"状态所经过的最短事件序列(假设电池一开始就是有电的)。

11.45，UML案例分析试题2

11.46，数据结构及算法应用

(掌握必得分的题，拿到6-8分左右)

课程内容提要:

   分治法

   回溯法

   贪心法

   动态规划法

11.47，分治法

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

该问题的规模缩小到一定的程度就可以容易地解决

该问题可以分解为若干个规模较小的相同问题

利用该问题分解出的子问题的解可以合并为该问题的解

该问题所分解出的各个子问题是相互独立的

分解

解决

合并

11.48分治法(递归技术)

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

11.49，回溯法

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

试探部分:

满足除规模之外的所有条件，则扩大规模。

(扩大规模)

回溯部分:

(缩小规模)

    1.当前规模解不是合法解时回溯(不满足约束条件D)。

    2.求完一个解，要求下一个解时，也要回溯。

11.50，贪心法

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

11.51，动态规划法

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

11.52，数据结构及算法应用案例分析试题1

【说明】

    设有n个货物要装入若干个容量为C的集装箱以便运输，这n个货物的体积分别为{S1,S2,......,Sn}，且有Si<=C(1<=i<=n)。为节省运输成本，用尽可能少的集装箱来装运这n个货物。

    下面分别采用最先适宜策略和最优适宜策略来求解该问题。

    最先适宜策略(firstfit)首先将所有的集装箱初始化为空，对于所有货物，按照所给的次序，每次将一个货物装入第一个能容纳它的集装箱中。

    最优适宜策略(bestfit)与最先适宜策略类似，不同的是，总是把货物装到能容纳它且目前剩余容量最小的集装箱，使得该箱子装入货物后闲置空间最小。

【C代码】

下面是这两个算法的C语言核心代码。

（1）变量说明

n:货物数

C:集装箱容量

s:数组，长度为n，其中每个元素表示货物的体积，下标从0开始

b:数组，长度为n，b[i]表示第i+1个集装箱当前已经装入货物的体积，下标从0开始

i,j:循环变量

k:所需的集装箱数

min:当前所用的各集装箱装入了第i个货物后的最小剩余容量

m:当前所需要的集装箱数

temp:临时变量

【问题1】8分。

根据【说明】和【C代码】，填充C代码中的空(1)-(4)。

【问题2】4分。

根据【说明】和【C代码】，该问题在最先适宜和最优适宜策略下分别采用了(5)和(6)算法设计策略，时间复杂度分别为(7)和(8)(用O符号表示)。

【问题3】3分。

考虑实例n=10,C=10,各个货物的体积为{4，2，7，3，5，4，2，3，6，2}。该实例在最先适宜和最优适宜策略下所需的集装箱数分别为(9)和(10)。考虑一般的情况，这两种求解策略能否确保得到最优解？(11)(能或否)

11.53，

11.54，面向对象程序设计

C++及Java语法要点

设计模式程序实现

C++的类与派生类的定义

class 类名 

{

public:

   公有数据成员或公有函数成员的定义；

protected:

    保护数据成员或保护函数成员的定义；

private:

    私有数据成员或私有函数成员的定义；

}；

class 派生类名:继承方式1 基类名1，继承方式2 基类名2，.....

{

private:

    派生类的私有数据和函数

public:

    派生类的公有数据和函数

protected:

    派生类的保护数据和函数

}；

C++类外定义函数体格式:

返回值类型  类名::成员函数名(形参表)

{

   函数体；

}

:: 是类的作用域分辨符，用在此处，放在类名后成员函数前，表明后面的成员函数属于前面的那个类。

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

构造函数的函数名必须与定义它的类同名。

构造函数没有返回值。如果在构造函数前加void是错误的。

构造函数被声明定义为公有函数。

构造函数在建立对象时由系统自动调用。

构造函数相对于一般函数来说，具有如下特殊的性质:

析构函数没有任何参数，不能被重载，但可以是虚函数，一个类只有一个析构函数。

析构函数没有返回值。

析构函数名与类名相同，但在类名前加上一个逻辑非运算符"~"，以示与构造函数对比区别。

析构函数一般由用户自己定义，在对象消失时由系统自动调用，如果用户没有定义析构函数，系统将自动生成一个不做任何事的默认析构函数。

C++对象指针与对象引用:

对象指针的语法定义形式如下:

    类名  *对象指针名；

对象引用的定义形式如下:

    类名  &对象引用名=被引用对象；

注意:通过对象名或对象引用访问对象的成员，使用的运算符是"."；

而使用对象指针访问对象的成员，使用的运算符是"→"。如:对象指针名→数据成员名或:对象指针名→成员函数名(参数表)。

C++虚函数:

虚函数定义的一般语法形式如下:

virtual 函数类型 函数名(形参表)

{

   函数体；

}

纯虚函数定义形式如下:

  virtual 函数名=0；

Java类的定义格式如下:

[import包]

[类修饰符]class  xxxclass[extends超类][implements 接口]

{

    poblic:

        公有数据成员或公有函数成员的定义；

    protected:

        保护数据成员或保护函数成员的定义；

    private:

        私有数据成员或私有函数成员的定义；

}

说明:

import包:引入包中的类。

类修饰符:主要有四个修饰符，public，abstract，final，private。

class为关键字，xxxclass为类名，命名遵循Java标识符的命名规则。

extends为继承关键字，implements为接口关键字。

Java接口的定义:

interface  IFactory{}

class  SqlServerFactory  implements  IFactory

接口的例题:

(1)Drawing{

(2)；

(3)；

}

class V1Drawing implements Drawing{

     public void drawLine(double x1,double y1,double x2,double y2){/*代码省略*/}

     public void drawCircle(double x,double y，double r){(4)；}

}

解析:

由implement Drawing知道Drawing是一个接口，故(1)为interface，在V1Drawing中有两个函数的实现函数，这两个函数的定义是在V1Drawing继承的接口里面定义的，故(2)为void drawLine(double x1,double y1,double x2,double y2)。(3)void drawCircle(double x，double y，double r)。

类的定义:

class Department{/*代码省略*/}

class SqlserverDepartment  (3) {}

abstract class Shape{

abstract public void draw()

}

class Rectangle extends Shape{

}

类的定义例题:

import java.util.*;

（1）class Beverage{//饮料

String  description ="Unknown Beverage"；

public （2） (){return description；}

     public（3）；

}

abstract class CondimentDecorator extends Beverage

{//配料

（4）；

}

解析:由extends Beverage可以知道Beverage类跟CondimentDecorator类是同个类型的，故(1)为abstract 。剩下的答案因为题目不完整，先看看就行。(2)为String getDescription。(3)为abstract int cost()。(4)Beverage beverage。

11.55，面向对象程序设计案例分析试题1

【说明】

现欲开发一个软件系统，要求能够同时支持多种不同的数据库，为此采用抽象工厂模式设计该系统。以SQL server和Access两种数据库以及系统中的数据库表Department为例，其类图如图6-1所示。

【Java代码】

import java.util.*;

class Department{/*代码省略*/}

interface  IDepartment{

  (1)；

  (2)；

}

class  SqlserverDepartment  (3) {

   public void Insert(Department department){

     System.out.println("Insert a record into Department in SQL Server!")；

//其余代码省略

 }

   public Department GetDepartment(int id){

     /*代码省略*/

 }

}

class  AccessDepartment (4){

   public void Insert(Department department){

      System.out.println("Insert a record into Department in ACCESS!")；

//其余代码省略

  }

   public Department GetDepartment(int id) {

      /*代码省略*/

  }

}

    (5){

    (6)；

}

class SqlServerFactory implements IFactory{

    public IDepartment CreateDepartment(){

       return new SqlserverDepartment()；

  }

   //其余代码省略

}

class AccessFactory implements IFactory{

   public IDepartment CreateDepartment(){

      return new AccessDepartment()；

 }

  //其余代码省略

}

解析:

容易知道(1)为void Insert(Department department)

(2)为Department GetDepartment(int id)

(3)为implements IDepartment

(4)为implements IDepartment

(5)为interface IFactory

(6)为IDepartment  CreateDepartment()

11.56,面向对象程序设计案例分析试题2

【说明】

欲开发一个绘图软件，要求使用不同的绘图程序绘制不同的图形。以绘制直线和圆形为例，对应的绘图程序如表6-1所示。

	DP1	DP2
绘制直线	draw_a_line(x1,y1,x2,y2)	drawline(x1,x2,y1,y2)
绘制圆	draw_a_circle(x,y,z)	drawcircle(x,y,r)

该绘图软件的扩展性要求，将不断扩充新的图形和新的绘图程序。为了避免出现类爆炸的情况，现采用桥接(Bridge)模式来实现上述要求，得到如图6-1所示的类图。

【Java代码】

（1）Drawing{

（2）；

（3）；

}

class DP1{

static public void draw_a_line(double x1,double y1,double x2,double y2){/*代码省略*/}

static public void draw_a_circle(double x,double y,double r)

{/*代码省略*/}

}

class DP2{

static public void drawline(double x1,double y1,double x2,double y2){/*代码省略*/}

static public void drawcircle(double x,double y,double r){/*代码省略*/}

}

class V1Drawing implements Drawing{

   public void drawLine(double x1,doubley1,double x2,double y2){/*代码省略*/}

   public void drawCircle(double x,double y,double r){（4）；}

}

class V2Drawing implements Drawing{

   public void drawLine(double x1,double y1,double x2,double y2){/*代码省略*/}

   public void drawCircle(double x,double y,double r){（5）;}

}

Abstract class Shape{

   Private Drawing_dp；

   （6）；

   Shape(Drawing dp){_dp=dp；}

   public void drawLine(double x1,double y1,double x2,double y2){

        _dp.drawLine(x1,y1,x2,y2);

  }

   public void drawCircle(double x,double y,double r){

        _dp.drawCircle(x,y,r)；

  }

}

class Rectangle extends Shape{

   private double _x1,_x2,_y1,_y2;

   public Rectangle(Drawing dp，double x1,double y1,double x2,double y2){/*代码省略*/}

   public void draw(){/*代码省略*/}

}

class Circle extends Shape{

   private double _x,_y,_r；

   public Circle(Drawing dp,double x,double y,double r){/*代码省略*/}

   public void draw(){drawCircle(_x,_y,_r)；}

}

解析:

(1)interface

(2)void drawLine(double x1,double y1,double x2,double y2)

(3)void drawCircle(double x,double y,double r)

(4)由类图知道V1Drawing会调用DP1来画圆，则答案为DP1.draw_a_circle(x,y,r)

(5)由类图知道V2Drawing会调用DP2来画圆，则答案为DP2.drawcircle(x,y,r)

(6)抽象的方法跟接口的方法一样，只有定义部分，这个定义部分也叫做虚方法，继承它的才会去具体实现这个方法。故答案为abstract public void draw()

注意，这种填空题的具体代码不会让我们自己编造，而是在题目可以找到的。

类爆炸指的是这个类的子类很多。

本文标签： 选择题 设计师 笔记 软件