备考时候的一些笔记，可能会有不对或者个人主观的知识点

---

---

前言

(1)掌握计算机内的数据表示、算术和逻辑运算方法；

(2)掌握相关的应用数学及离散数学基础知识；

(3)掌握计算机体系结构以及各主要部件的性能和基本工作原理；

(4)掌握操作系统、程序设计语言的基础知识，了解编译程序的基本知识；

(5)熟练掌握常用数据结构和常用算法；

(6)熟悉数据库、网络和多媒体的基础知识；

(7)掌握C程序设计语言，以及C++、Java中的一种程序设计语言；

(8)熟悉软件工程、软件过程改进和软件开发项目管理的基础知识；

(9)掌握软件设计的方法和技术；

(10)了解信息化、常用信息技术标准、安全性，以及有关法律、法规的基础知识；

(11)正确阅读和理解计算机领域的英文资料。

• 考试科目设置

(1)计算机与软件工程知识，考试时间为150分钟；

(2)软件设计，考试时间为150分钟。

• 题型设置
  上午题
  
  下午题
  

---

一、计算机内数据的表示

1.1 原反补移码

• 原码：若机器字长n+1位，原码整数的表示范围: $$-(2^n-1)\le x\le 2^n-1（关于原点对称)$$
  • 原码中，0有+0和-0两种
  • 最高位为符号位
• 反码：若符号位为0，则反码与原码相同。若符号位的负、则数值位全部取反。
  • 若机器字长n+1位，反码整数的表示范围: $$-(2^n一1)\le x\le 2^n-1(关于原点对称)$$
  • 0有+0和-0两种
    
• 补码：正数的补码=原码；负数的补码=负数的反码末位+1
  • 补码的真值0只有一种表示形式，即0,000000
  • 机器字长n+1位，补码整数的表示范围:$$-(2^n)\le x\le 2^n-1$$
• 移码：在补码的基础上，符号位取反
  • 机器字长n+1位，补码整数的表示范围:$$-(2^n)\le x\le 2^n-1$$
    

1.2 浮点数

浮点数由尾数M和阶码E构成
$$F=M\ast 2^E$$
其中，M称为尾数，R称为基数，E称为阶码。

• 阶码，决定浮点数所能表示的数值范围;
• 尾数，决定浮点数所能表示的数值精度。

组成

阶符	阶码数值	数符	尾数
0/1	E	0/1	M

运算时，对阶：规则是阶码小的向阶码大的数对齐，尾数右移（即小数点左移）
为什么小的对阶大的：因为小对大得到的差错对于大对小得到的差错要小很多
若阶码相等则不用对阶；

1.3 校验码

码距：任何一种编码都由许多码字构成，任意两个码字之间最少变化的二进制位数就称为数据校验码的码距。
如：用4位二进制表示16种状态,则有16个不同的码字,此时码距为1。如0000与0001。
如：{00，11}这个集合中，码距为2。

1.3.1奇偶校验

• 奇校验:在校验位上补0或1，使得编码中1的个数为奇数
• 偶校验:在校验位上补0或1，使得编码中1的个数为偶数

在传送数据中，如果进行的是偶校验，但接收到的编码1个数有奇数个，则发生了错误，奇校验类似。

局限性：只能检测奇数个bit位出错，出现偶数个bit位出错，不能检测
只能检错，不能纠错

1.3.2 CRC冗余校验码(理解特点即可)

数据发送、接受方约定一个“除数”(二进制)。冗余校验码由k位信息位和R位校验位组成，在k位信息码后拼接R位校验位。
对接收的数据进行模2除，如果余数为0，代表没有出错。不为0则出错。

只能检错，不能纠错

1.3.3 海明校验码

设信息位有n位，校验位有k位，则有不等式：
$$2^k\ge n+k+1$$
由信息位，可得校验位k
例题

可检错，可纠错

二、 计算机系统组成

2.1 冯诺依曼结构

1. 由五大部件组成：输入设备，输出设备，存储器，运算器，控制器
2. 指令和数据以同等地位存储在存储器中，可按地址寻访
3. 指令和数据皆以二进制表示
4. 指令由地址码和操作码组成
5. 存储程序
6. 早期以运算器为中心，现在以存储器为中心

CPU=运算器+控制器

完成一条指令过程:

1. 取指令 PC+1
2. 分析指令IR
3. 执行指令CU

2.2 Flynn分类法

2.3 指令系统

一条指令通常要包括操作码字段和地址码字段两部分

2.3.1 七种寻址方式（了解）

指令构成：

操作码(OP)	地址码(A)

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

2.3.2 CISC/RISC

RISC硬布线逻辑控制为主，适合采用流水线。增加通用寄存器数目以减少访存次数。

2.3.3 指令流水（流水线计算）

流水线是准并行，而非并行

• 吞吐率(Though Put rate, TP)∶是指在单位时间内流水线所完成的任务数量或输出的结果数量。
  计算公式如下:
  $$TP=\frac{指令条数}{流水执行时间}$$
• 加速比:
  $$S=\frac{不使用流水线时间}{使用流水线时间}$$
• 流水线周期 t 为执行时间最长的一段，有n个程序的流水线计算公式为
  $$T=一个程序执行时间+(n-1)\times t$$

2.4 输入输出技术

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

1. 直接程序控制方式
   直接程序控制方式是指在完成数据的输入/输出中，整个输入/输出过程是在CPU执行程序的控制下完成的。这种方式还可以分为以下两种:
   (1) 无条件传送方式：无条件地与CPU交换数据。
   (2) 程序查询方式：先通过CPU查询外设状态，准备好之后再与CPU交换数据。硬件开销小，但效率不高。
2. 中断方式
   利用中断机制，使I/О系统在与外设交换数据时，CPU无须等待，也不必查询I/O状态，即可以抽身出来处理其他任务，因此提高了系统效率。
3. DMA方式
   直接存储器存取(Direct Memory Access,DMA)方式是在存储器与I/Q设备间直接传送数据，即在内存与I/O设备之间传送一个数据块的过程中，不需要CPU的任何干涉，是一种完全由DMA硬件完成l/O操作的方式。

CPU是在一个总线周期结束时响应DMA请求的。
【

4. 输入/输出处理机
   输入/输出处理机(IOP)是一个专用处理机，用于完成主机的输入/输出操作。IOP根据主机的l/O命令，完成对外设数据的输入/输出。

2.5 存储系统（分类，了解）

按工作方式，可分为读/写存储器和只读存储器。

• 读/写存储器(RAM) 它指既能读取数据也能存入数据的存储器。

  • DRAM
    掉电丢失数据。每隔一段时间就要刷新一次数据，才能保存数据。
    DRAM保留数据的时间很短，速度也比SRAM慢，不过它还是比任何的ROM都要快；
    从价格上来说DRAM相比SRAM要便宜很多
    计算机主存就是DRAM的；
  • SRAM
    不需要刷新电路，掉电丢失数据，而且一般不是行列地址复用的。
    制造相同容量的SRAM比DRAM的成本高的多
    SRAM基本上只用于CPU内部的一级缓存以及内置的二级缓存。

• 只读存储器(ROM) 工作过程中仅能读取的存储器。

根据数据的写入方式，又可细分为ROM RROM、EPROM和EEPROM等类型。
① 固定只读存储器(ROM)。这种存储器是在厂家生产时就写好数据的，其内容只能读出，不能改变。一般用于存放系统程序BIOS和用于微程序控制。
② 可编程的只读存储器(Programming ROM)。其中的内容可以由用户一次性地写入，写入后不能再修改。
③ 可擦除可编程的只读存储器(EPROM。其中的内容既可以读出，也可以由用户写入，写入后还可以修改，紫外线照射擦除信息。
④ 电擦除可编程的只读存储器(EEPROM)。EEPROM中的内容既可以读出，也可以进行改写，电擦除的方法进行数据的改写。
⑤ 闪速存储器(Flash Memory)。简称闪存,闪存的特性介于EPROM和EEPROM之间，类似于EEPROM，也可使用电信号进行信息的擦除操作。整块闪存可以在数秒内删除，速度远快于EPROM。

2.6 Cache

位于CPU和主存之间，采用高速缓存的主要目的是：提高存储器的平均访问速度，使存储器的速度与CPU的速度相匹配。
利用时间局部性和空间局部性原理

2.6.1 主存和Cache的地址映射

由硬件自动完成Cache与主存之间的地址映射

1. 全相联映像
   主存中任意一块可装入cache中的任何一块
   优点：块冲突概率最低，cache的空间利用率最高。
   缺点：cache容量很大时，查表速度很慢

全相联主存地址：

主存块号标记	块内地址

2. 直接映像
   把主存按cache大小等分成区，每区内的各块只能按位置一一对应到Cache的相应块的位置上。
   优点：硬件简单，成本低。
   缺点：容易产生冲突，适合大容量cache采用。

直接映射主存地址：

主存标记	Cache块号	块内地址

3. 组相联映像
   各组之间直接映像，组内各块全相联映像。
   特点：组相联比全相联在成本上要低，但是性能上可接近于全相联。

组相联主存地址：

主存标记	Cache组号	块号	块内地址

2.6.2 替换算法

替换算法:

1. 随机替换算法（RAND)
2. 先进先出算法(FIFO)：总是替换最旧的那一块。
3. 最不经常使用(LFU)∶每访问一次，计数器+1，替换访问次数最少的，替换后被替换的那一行的计数器清
   零。
4. 近期最少使用(LRU):每被访问一次，被访问的清0，未访问的行计数器+1，替换最大的行。

2.6.3 Cache性能分析

若H为Cache的命中率，t0为 Cache的存取时间，tm为主存的访问时间，则Cache的等效访问时间ta为
$$ta=Ht0+(1-H)tm$$
使用Cache 比不使用Cache的CPU访问存储器的速度提高的倍数r可以用下式求得
$$r=\frac{tm}{ta}$$

2.7 虚拟存储器

虚拟存储器是由主存、辅存、存储管理单元及操作系统中的存储管理软件组成的存储系统。程序员决使用该存储系统时，可以使用的内存空间可远远大于主存的物理空间，但实际上并不存在那么大的主存，故称其为虚拟存储器。

虚拟存储器使存储系统既具有相当于外存的容量又具有接近于主存的访问速度。
两级存储结构：主存+辅存
三级存储结构：主存+辅存+Cache

2.8 磁盘存储器

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

2.9 磁盘阵列(了解各等级的说明)

磁盘阵列由多台磁盘存储器组成，是快速、大容量且高可靠的外存子系统。现在常见的独立冗余磁盘阵列(RAID)就是一种由多块独立磁盘构成的冗余阵列。RAID技术分为几种不同的等级，分别可以提供不同的速度、安全性和性价比。

2.10 计算机可靠性计算以及性能指标

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

选B

若MTTF和MTTR分别表示平均无故障时间和平均修复时间，则公式
$$\frac{MTTF}{1+MTTF}$$
可用于计算软件可靠性。

• CPU主频=1/CPU时钟周期 Hz
• CPI︰执行一条指令所需的时钟周期数
• 执行一条指令的耗时= CPI*CPU时钟周期
• 所以对于整个程序的耗时：$$CPU执行时间=指令数\ast CPI\ast 时钟周期$$
• IPS:每秒执行多少条指令=主频/CPI

2.11 总线系统（待补充）

三、 数据结构与算法

3.1 循环队列

为了区分队空还是队满：

1. 牺牲一个单元来区分队空还是队满，即队头指针在对位指针的下一个位置作为队满的标志。
   队满：(Q.rear+1)%MaxSize == Q.front
   队空：Q.rear==Q.front
   队长：（Q.rear+MaxSize-Q.front）%MaxSize

3.2 广义表

广义表通常记作:LS = (a1, a2,…, an)

广义表通常用链表进行存储

其中:LS为表名，n为表的长度，每一个ai为表的元素。ai可以是表，也可以是数据
操作：

• 取表头
  若LS非空(n≥1)，则其第一个元素a1就是表头。
  记作head(LS)= a1。
  注:表头可以是原子，也可以是子表。

• 取表尾
  除表头之外的其他元素组成的表。
  记作tail(LS)= (a2,… an)。
  注:表尾不是最后一个元素，而是一个字表。

3.3 二叉树

3.3.1 树转二叉树

3.3.2 二叉排序树

左孩子小于根，右孩子大于根
如：89，48，56，112，51，20构成的二叉排序树

关键码序：就是出现在二叉排序树中的，对二叉排序树的各个结点进行排序的一个结点序列。
依据左子树的各个结点的值都小于父结点的值，右子树的各个结点的值都大于父结点的值 的条件进行排序。
比如上述例子中，二叉树的关键码序就是89，48，56，112，51，20

3.3.3 哈夫曼树

假设有一组权值5，29，7，8，14，23，3，11，构造哈夫曼树
思想：首先选最小的两个权值节点作为叶子，相加后的值放入数组中，之后在更新的数组中选最小的两个节点作为叶子

1. 选5，3（5+3=8），更新后：8，29，7，8，14，23，11
2. 选7，8（7+8=15），更新后：15，29，8，14，23，11
3. 以此类推

带权外部路径长度计算；
$$W=\Sigma 叶子权重\times 对应路径长度$$
此题中：W = （5+3）×5+7×4+（14+8+11）×3+（29+23）×2

3.3.4 线索二叉树

在二叉树的基础上，在每个节点加入了两个指针域，分别指向前驱和后继节点，若没有则为NULL。
即对前序/中序/后序线索二叉树写出遍历序列后，节点前后即为前驱和后继
例，中序线索二叉树：

BDAEC
图中B无前驱，C无后继，因为B是第一个结点，C是最后一个。

3.3.5 平衡二叉树

性质：树上任一结点的左子树和右子树的高度之差不超过1。
结点的平衡因子=左子树高-右子树高

3.4 查找

1. 顺序查找，O(n)
2. 折半查找，只适用于顺序表，O(logn)
3. 分块查找，将查找表分为若干块，块内元素可以无序，但块之间是有序的用，顺序或者折半查找关键字所在的块，再在块内用顺序查找
   由折半查找过程中所产生的树，必为平衡树
4. 哈希表

3.5 排序

3.5.1 快排每一趟

以第一个为基准，从后往前找比基准小的，从前往后找比基准大的，分别找到之后交换两者的位置，如此循环，知道找到中间值，然后交换中间值和基准的位置。这是第一趟

此后以上一趟为基础，对左右两边递归调用此算法。
图解版解释快排每一趟

3.5.2 归并排序每一趟

四、 操作系统

进程管理、存储管理、文件管理、作业管理、设备管理

4.1 线程

线程是一个基本的CPU执行单元，也是程序执行流的最小单元。
一个进程内部有多个线程，若线程的切换发生在同一个进程内部，则只需要很少的时空开销。

• 线程共享的内容包括：进程代码段、进程的公有数据（利用这些共享的数据，线程很容易的实现相互之间的通讯）、进程打开的文件描述符、信号的处理器、进程的当前目录、进程用户ID与进程组ID 。(线程共享的东西不会维护在为线程开辟的堆栈中，而是维护在全局区)
• 线程独有的内容包括：线程ID、寄存器组的值、线程的堆栈、错误返回码、线程的信号屏蔽码。

4.2 进程（熟练状态变迁）

进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。它由程序块、进程控制块(PCB)和数据块三部分组成。

1. 运行态：正在处理机上运行。
2. 就绪态：进程获得了除CPU处理机以外地一切所需资源，只等待CPU调度。
3. 阻塞态：即等待态。进程正等待某一事件（如请求I/O）而暂停运行。
4. 静止就绪
5. 静止阻塞
   前3种状态是基本状态。
   

等待某个事件：说明这个事件没有发生，从运行到阻塞
等待事件发生：说明这个事件发生了，从阻塞到了就绪

4.3 进程同步和互斥PV操作

理解互斥锁和PV操作在程序中加载的位置

为禁止两个进程同时进入临界区，同步机制应遵循：

1. 空闲让进。临界区空闲时可以访问。
2. 忙则等待。临界区上锁时，其它进程等待。
3. 有限等待。等待时间应是有限的。
4. 让权等待。当进程不能进入临界区时，应立即释放处理器。

4.3.1 前趋图与PV操作（3分左右，重点）

前趋图：节点与节点之间有明显的逻辑关系（类似拓扑图）
通过前趋后继关系来定义各种PV操作

D在前趋活动ABC都完成后，才能开始。E同理。

例题：

4.4 死锁

死锁条件：

1. 互斥：资源互斥访问。
2. 不剥夺：进程的资源在未使用完之前不被强行夺走。
3. 请求并保持：进程已经保持了至少一个资源，并提出新资源请求但被占用而阻塞，自己的资源不释放。
4. 循环等待：存在一种进程资源循环等待链，链中每个进程已获得资源同时被下一个进程请求。

（需要计算）系统不可能发生死锁的最小资源数：每个进程都分配了（所需最少资源数-1）个资源，此时再增加一个资源，即不会发生死锁。

答案：4

4.4.1 死锁预防（破坏四个条件之一）

1. 破坏互斥条件：允许资源共享使用，如SPOOLing技术。但有些资源如打印机只能互斥使用。所以此方法不太行。
2. 破坏不剥夺条件：当一个以获得资源的进程请求新资源而得不到满足时，它必须释放已经保持的所有资源。此方法常用于状态易于保存和回复的资源。
3. 破坏请求并保持条件：采用预先静态分配方法，即进程在运行前，一次性申请完所需要的全部资源，并保持。但容易造成资源浪费，如有些资源只用一会就闲置。
4. 破坏循环等待条件：采用顺序资源分配法。

4.4.2 死锁避免（银行家算法）

4.4.3 资源分配图

一般进程结点的入边表示分配边，出边表示请求边。
R1分配给P1两个资源，分配给P2一个资源，并受到P2一个资源请求
R2分配给P2一个资源，并受到P1一个资源请求

资源图判定死锁

1. 在资源分配图中，找出既不阻塞也不孤立的进程Pi（即找到有向边与它相连，并且边对应资源的申请数量小于等于系统中的空闲资源数量）。如R1无空闲资源，R2有一个，则P1进程满足条件。
2. 进程Pi释放资源，消去Pi所连接的所有有向边，唤醒因等待这些资源而阻塞的进程，继续简化。若能消去所有边，则图能简化。
   

S为死锁的条件是当且仅当S状态的资源分配图不可完全化简。

4.5 段页式存储

4.5.1 页式存储（重点）

进程中的块称为页或页面，内存中的块称为页帧或页框。为进程分配内存，形成了页与页框一 一对应。

为每个进程建立一张页表，记录页面在内存中对应的物理块号。一般存放在内存中。
页表项第一部分是页号，第二部分是物理内存块号。

地址转换（掌握）

• 通过逻辑地址的页号，在页表中查找对应的物理页号，物理页号+页内偏移量=物理地址
• 页内偏移量的位数通过页的大小可得，比如页大小为4KB=2的12次方B，则偏移量位数为12，剩下位数的就是页号

页面置换算法（了解）

• 最佳置换算法OPT：每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面
• 先进先出置换FIFO：优先淘汰最早进入内存的页面。实现简单，但是性能差，可能出现Belady异常（即分配给进程的物理块增多，但缺页次数反而增多）。
• 最近最久未使用置换LRU：基于局部性原理，选择最近最长时间未被访问过的页面置换。性能好，但需要硬件支持，算法开销大。

4.5.2 段式存储

段号的位数决定了每个进程最多可以分几个段。段内地址位数决定了每个段的最大长度是多少。每个作业段长可能不一样。

每个进程都有一张逻辑空间与内存空间映射的段表。每个段表项对应进程的一段。段表项结构：

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

4.6 磁盘管理

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

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

读取一块数据的总时间为以上三个时间之和。

4.6.1 磁盘调度

1. 先来先服务
2. 最短寻找时间优先：选择调度处理的磁道是与当前磁头所在距离最近的磁道，以便每次的寻找时间最短。会产生饥饿现象
3. 扫描算法SCAN：当前移动方向上选择与当前磁头距离最近的请求最为下一次服务对象，然后按着这个方向，只有到了磁道边缘才能换方向。
4. 循环扫描算法C-SCAN：规定磁头单向移动提供服务，回返时直接快速移动至起始端而不服务任何请求。

4.6.2 缓冲区

1. 单缓冲区
   假设某用户进程请求某种块设备读入若干块的数据。若采用单缓冲的策略，操作系统会在主存中为其分配一个缓冲区（若题目中没有特别说明，一个缓冲区的大小就是一个块）。
   注意:当缓冲区数据非空时，不能往缓冲区冲入数据，只能从缓冲区把数据传出；当缓冲区为空时，可以往缓冲区冲入数据，但必须把数据读完后，才能从缓冲区把数据传出。
   

2. 双缓冲区
   假设某用户进程请求某种块设备读入若干块的数据。若采用双缓冲的策略，操作系统会在主存中为其分配两个缓冲区（若题目中没有特别说明，一个缓冲区的大小就是一个块)。此时就不存在“当缓冲区数据非空时，不能往缓冲区冲入数据”的问题，即可以边送入用户区，边读入缓冲区。
   

例题：



这道题的重点是，磁盘的旋转周期为33ms，并且磁道被划分为11个物理块，因此每个物理块有一个3ms的划过时间，可以理解为读取时间。
11个记录最长时间：旋转时间+读取时间+处理时间，30×10+3×11+3×11=366
最少时间（每次处理完刚好转到下一个要处理的物理块）：读取时间刚好和处理时间相等，则3×11+3×11=66

4.7 I/O软件层次结构（了解分层次序，作用不用记）

1. 用户层I/O软件
   实现与用户交互的接口，用户可直接调用在用户层提供的与I/O操作有关的库函数对设备进行操作。
   I/O软件向用户提供的是逻辑接口
2. 设备独立性软件
   设备独立性又称设备无关性，使得应用程序独立于具体使用的物理设备。
   主要功能：
   • 向上层提供统一的调用接口（如read/write系统调用)
   • 设备的保护。（原理类似与文件保护。设备被看做是一种特殊的文件，不同用户对各个文件的访问权限是不一样的，同理，对设备的访问权限也不一样。）
   • 差错处理（设备独立性软件需要对一些设备的错误进行处理）
   • 设备的分配与回收
   • 数据缓冲区管理（可以通过缓冲技术屏蔽设备之间数据交换单位大小和传输速度的差异）
   • 建立逻辑设备名到物理设备名的映射关系;根据设备类型选择调用相应的驱动程序
3. 设备驱动程序
   不同设备的内部硬件特性也不同，这些特性只有厂家才知道，因此厂家须提供与设备相对应的驱动程序，CPU执行驱动程序的指令序列，来完成设置设备寄存器，检查设备状态等工作。与硬件直接相关。计算柱面号、磁头号和扇区号的工作等。
4. 中断处理程序
   进行中断处理，也会和硬件直接交互。

4.8 文件管理

而在用户进行的输入/输出中，以文件为基本单位。
逻辑结构:有结构的记录式文件、无结构的流式文件。
物理结构:连续结构、链接结构、索引结构、多个物理块的索引表。

文件控制块FCB
用来存放控制文件所需要的各种信息的数据结构，以实现“按名存取”。FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。
FCB主要包含以下：

• 基本信息：如文件名，文件物理位置等。
• 存取控制信息：文件主的存取权限，一般用户的存取权限等。
• 使用信息：建立信息，更新信息等。

一个文件目录也是一个文件，称为目录文件。

4.8.1 位示图

利用二进制的一位来表示磁盘中一个盘块的使用情况。为“0”时空闲，为“1”时分配。

如图所示，做题时要注意行/列坐标的起始是1还是0，这涉及到坐标的转换。例如给你第几个位置，转换为坐标。没有说明的话，就是位从1开始编号，字从0开始，行号是字，纵号是列

选D，算物理块数，这也就是对应总位数。用总位数除以32得字数。

4.9 索引文件（重点，涉及计算）

一级二级间接索引的计算

4.10 作业管理

执行过程和CPU状态转换相似。调度算法：

• 先来先服务法
• 时间片轮转法
• 短作业优先法
• 最高优先权优先法
• 高响应比优先法

高响应比优先调度：
$$高响应比=\frac{等待时间+执行时间}{执行时间}$$

结果越大，优先级越高

4.11 嵌入式操作系统

嵌入式操作系统的特点：
（1）微型化，从性能和成本角度考虑，希望占用的资源和系统代码量少；
（2）可定制，从减少成本和缩短研发周期考虑，要求嵌入式操作系统能运行在不同的微处理器平台上，能针对硬件变化进行结构与功能上的配置，以满足不同应用的需求；
（3）实时性，嵌入式操作系统主要应用于过程控制、数据采集、传输通信、多媒体信息及关键要害领域需要迅速响应的场合，所以对实时性要求较高；
（4）可靠性，系统构件、模块和体系结构必须达到应有的可靠性，对关键要害应用还要提供容错和防故障措施；
（5）易移植性，为了提高系统的易移植性，通常采用硬件抽象层和板级支撑包的底层设计技术。

五、 数据库

5.1 分布式数据库

特点：

• 数据独立性
• 集中与自治共享结合
• 适当增加数据冗余度
• 全局的一致性、可串行性、可恢复性

透明性：

1. 分片透明：是指用户不必关心数据是如何分片的，它们对数据的操作在全局关系上进行，即如何分片对用户是透明的。
2. 复制透明：用户不用关心数据库在网络中各个节点的复制情况，被复制的数据的更新都由系统自动完成。
3. 位置透明：是指用户不必知道所操作的数据放在何处，即数据分配到哪个或哪些站点存储对用户是透明的
4. 局部映像透明性 - 逻辑透明∶是最低层次的透明性，该透明性提供数据到局部数据库的映像，即用户不必关心局部DBMS支持哪种数据模型、使用哪种数据操纵语言，数据模型和操纵语言的转换是由系统完成的。

5.2 三级模式结构（掌握）

数据库系统的三级模式结构

• 外模式：是数据库用户看到的数据视图，是模式的子集
• 概念模式：也称逻辑模式，数据库中全体数据的逻辑结构和特征的描述，所有用户的公共数据视图，一个数据库只能有一个概念模式。对表的操作就是概念模式级别（也就是模式）
• 内模式：也称存储模式，是数据物理结构和存储方式的描述，是底层描述，只能有一个。例如创建索引，会改变内模式。

二级模式映射

• 外模式/概念模式:
  对于每一个外模式，数据库都有一个外模式/概念模式的映像保证了数据与程序的逻辑独立性，即数据的逻辑独立性
• 概念模式/内模式
  是唯一的，保证了数据与程序的物理独立性，即数据的物理独立性

5.3 数据仓库

• 面向主题:数据按主题组织。
• 集成的:消除了源数据中的不一致性，提供整个企业的一致性全局信
• 相对稳定的(非易失的):主要进行查询操作，只有少量的修改和删除操作（或是不删除).
• 反映历史变化(随着时间变化):记录了企业从过去某一时刻到当前各个阶段的信息，可对发展历程和未来趋势做定量分析和预测。

上图显示了数据处理的一系列操作，数据预处理(ETL)->数据仓库存储->数据分析->数据展示

• OLAP：联机分析，是数据仓库主要的目标
• OLTP：联机事务处理，着重数据库操作处理

记住以上英文缩写

5.4 数据库设计过程

5.4.1 需求分析和概念设计

集成的方法:

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

集成产生的冲突及解决办法:(针对同一对象)

• 属性冲突：同一属性可能会存在于不同的分E-R图，由于设计人员不同或是出发点不同，对属性的类型、取值范围和数据单位等可能会不一致。
• 命名冲突：相同意义的属性在不同的分E-R图中有着不同的命名，或是名词相同的属性在不同的分E-R图中代表这不同的意义。
• 结构冲突：同一实体在不同的分E-R图中有不同的属性，同一对象在某一分E-R图中被抽象为实体，而在另一分E-R图中又被抽象为属性，需要统一。

5.4.2 E-R图

• 椭圆表示属性
• 矩形表示实体
  • 矩形加线条表示特殊实体
• 菱形表示联系

三元关系

在判断对应关系时，分别以三元关系中的一个实体作为中心，假设另两个实体都只有一个实例;
以病房为中心，一个病人住一个病房，一个医生管理一个病房，所以病房端为1
以病人为中心，一个病人住一个病房，一个医生治疗多个病人，只要有一端为多个，就填多数n
以医生为中心，一个医生管理一个病房，一个医生治疗多个病人，所以填m

弱实体

是指某实体是否存在对于另一些实体具有很强的依赖关系，即一个实体的存在必须以另一个实体为前提，而将这类实体称为弱实体，如家属与职工的联系，附件与邮件。

用嵌套菱形和嵌套矩形表示弱实体联系

外部实体

外部实体指系统以外，又和系统有联系的人或事物。
外部实体一般为组织机构、人员、第三方系统

某考试系统的部分功能描述如下：审核考生报名表；通过审核的考生登录系统，系统自动为其生成一套试题，考试中心提供标准答案；阅卷老师阅卷，提交考生成绩；考生查看自己的成绩。若用数据流图对该系统进行建模，则（考生、阅卷老师、考试中心）是外部实体。

5.4.3 逻辑结构设计

关系模式

在用户观点下，关系模型中数据的逻辑结构是一张二维表，它由行和列组成。
关系必须是规范化的，满足一定的规范条件
最基本的规范条件:关系的每一个分量必须是一个不可分的数据项,即不允许表中还有表

数据模型三要素:
数据结构︰描述数据库的组成对象以及对象之间的联系
数据操作∶对数据库中各种对象和实例允许执行的操作的集合
数据的完整性约束条件：一组完整性规则

候选键：唯一标识元组，且无冗余（就是能标识一个实体的最少属性集合），可以有多个
在候选键中任选一个作为主键

完整性约束

1. 实体完整性：主键唯一且非空
2. 参照完整性：外键：本关系中一个元组，要么为其他关系的主键，要么为空，则这个元组是本关系的外键
3. 用户定义的完整性：用户自定义的约束，如性别用数字01还是用汉字

触发器作用：监听一些数据元组，当发生变化时，可以完成一些复杂的完整性约束

E-R图转关系模式（上下午均涉及，重点）

• 一对一关系的转换
  
  分别是两种转换方式：独立出一个关系模式（将两端主键并入到新的关系模式中），归并到任意一端（一端的主键归并到另一端）
• 一对多关系
  
  

两种转换方式：独立出一个关系模式（将两端主键并入到新的关系模式中），归并到多端（一端的主键归并到多端）
因为若多端归并到一端，会出现主键重复的情况

• 多对多关系
  
  
  只有独立出一个关系模式，且这个模式的主键为两个实体主键的组合元组

关系代数

• 笛卡尔积：$$A\times B=(a,b)\mid a\in A\text{ and }b\in B$$
  例如，假设 ( A = {1, 2} ) 和 ( B = {x, y} )，那么
  $$A\times B=(1,x),(1,y),(2,x),(2,y)$$

• 投影:用π表示
  从R中选择出若干属性列组成新的关系
  

• 选择：用σ表示，即为select操作的where条件

• 连接：从笛卡尔乘积结果中取一些满足条件的结果，分为等值连接和自然连接

  • 自然连接：在笛卡尔乘积结果中，将重复的属性值列进行去重，然后同名属性列取值相等，等价于先做相关属性的选择再做投影
    

  • 等值连接：从关系R与S的广义笛卡尔积中选取A、B属性值相等的那些元组
    

select *
from R,S
where XXX

• select实质就是投影对应的属性列
• from后面跟R,S两张表，实质就是R,S两张表的笛卡尔乘积
• where对应选择操作

查询效率最高就是先做筛选，去掉一些行数，再做笛卡尔积进行后续操作

左/右外连接

左/右外连接：取出左/右侧关系中所有与右/左侧关系中任一元组都不匹配的元组，用空值NULL填充所有来自右/左侧关系的属性，将结果加入自然连接的结果中。

左外连接

右外连接

5.5 规范化理论（是逻辑结构设计的内容，重点）

5.5.1 函数依赖(需要再次学习)

设R(U)是一个属性集U上的关系模式，X和Y是U的子集。
若对于R(U)的任意一个可能的关系r ，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称“X函数确定Y"或“Y函数依赖于X”，记作X→Y。
(可以类比于数学中函数的定义，不存在两个相同的x，但是y不等)

部分函数依赖

主键的子部分能确定属性

{A,B}->C且A->C，则称C部分依赖于A

传递函数依赖

A->C,B->C，且B不能确定A（即A和B不等价）,则A->C

Armstrong 公理

设U是关系模式R的属性集，F 是R 上成立的只涉及U中属性的函数依赖集。函数依赖的推理规则有以下三条：

• 自反律：若属性集Y包含于属性集X，属性集X包含于U，则X→Y 在R上成立。（此处X→Y是平凡函数依赖）
• 增广律：若X→Y 在R上成立，且属性集Z包含于属性集U，则XZ→YZ 在R上成立。
• 传递律：若X→Y 和 Y→Z在R 上成立，则X→Z 在R 上成立。

根据上面三条推理规则，又可推出下面三条推理规则：

• 合并规则：若X→Y，X→Z，则X→YZ为F所蕴含；
• 伪传递规则：若X→Y，WY→Z，则XW→Z为F所蕴含；
• 分解规则：若X→Y，Z⊆Y，则X→Z为F所蕴含。

5.5.2 候选键（有向图法找候选键题型）

有向图求候选键
1、将关系的函数依赖关系，用“有向图”的方式表示。
2、找出入度为0的属性并以该属性集合为起点，尝试遍历有向图，若能正常遍历图中所有结点，则该属性集即为关系模式的候选键。
3、若入度为0的属性集不能遍历图中所有结点，则需要尝试性的将一些中间结点(既有入度，也有出度的结点)加入入度为0的属性集中，直至该集合能遍历所有结点，集合为候选键。
4、若没有入度为0的，就找入度最小的属性集、防止冗余

主属性与非主属性：组成候选码的属性就是主属性，其它的就是非主属性。
做题时需要先找到候选键，然后再判断主属性、非主属性。

5.5.3 范式（掌握范式级数判断以及如何拆分）

只要没达到3NF，数据冗余、修改异常、插入异常、删除异常
这些缺点都可能存在
做范式判断题型步骤：

1. 找候选键（有向图法）
2. 找非主属性
3. 判断是否存在非主属性对候选键存在部分依赖（即候选键的一部分可以决定非主属性），即是否满足2NF
   • 不满足时，就需要进行分割，消除部分依赖
4. 判断是否有非主属性传递依赖与候选键，即是否满足3NF

第一范式（不可分割）

第一范式(1NF）是指数据库表的每一列都是不可分割的基本数据项，同一列中不能有多个值，即实体中的某个属性不能有多个值或者不能有重复的属性值。

• 不满足，有重复的属性值
  
• 满足
  

第二范式（消除部分依赖）

在第一范式的基础上消除部分函数依赖，就是每一个非主属性完全依赖候选键，即为第二范式。

第三范式（消除传递依赖）

当且仅当关系模式R是第二范式(2NF)，且R中没有非主属性传递依赖于候选键时，则称关系模式R是第三范式。

BC范式（掌握判断）

设R是一个关系模式，F是它的依赖集，R属于BCNF当且仅当其F中每个依赖的决定因素必定包含R的某个候选键。
也就是写出依赖集合后，箭头的尾部中必定包含候选键（并不是说“是候选键”）
当有一个依赖不满足，就不是BC范式，需要在第三范式的基础上消除不含码的决定因素。

5.5.4 模式分解

由R1和R2连接后，传递依赖，可得与原依赖集合F等价，所以保持了函数依赖，F中的A->C是冗余依赖
R1和R2的分解就是模式分解的形式

无损分解

• 有损:不能还原。
• 无损:可以还原。
  • 无损连接分解:指将一个关系模式分解成若干个关系模式后，通过自然连接等运算仍能还原到原来的关系模式

判断是否无损分解

• 表格法判断
  

1. 第一步，初始表。每个行号是关系模式名称，每个列号是属性值名称。
   如果此关系模式有这个属性，则填为a，下标为列号
   如果此关系模式没有这个属性，则为b，下标为行号+列号
   
2. 对初始表进行改进，如果此关系模式有对应的函数依赖，可以把对应的函数依赖中是b的属性值改为a
   当有一行全部为a时，则表示是无损分解
   
   由学号→姓名，将有学号属性的关系模式中，姓名改为a，由课程号→课程名，课程名也改为a
   所以成绩关系模式全部为a，此为无损分解

• 定理法（针对只有两个的分解）
  如果R的分解为{R1， R2 }，F为R所满足的函数依赖集合，分解p具有无损联接性的充分必要条件是:
  R1∩R2 → (R1减R2) 或 R1∩R2 → (R2减R1)
  
  所以ρ1是无损分解，ρ2不是无损分解

5.6 SQL

分类	动词
数据查询	SELECT
数据定义	CREATE、DROP、ALTER
数据操纵	INSERT、UPDATE、DELETE
数据控制	GRANT、REVORK

5.6.1 普通查询

题型，给出关系代数补全查询语句，AC
自然连接时，同名属性列要在WHERE后跟相等条件

5.6.2 分组查询

5.6.3 权限控制（了解关键字）

GRANT 语句的一般格式：

GRANT <权限>[,<权限>]…
[ON <对象类型> <对象名>]
TO<用户[,<用户>]…
[WITH GRANT OPTION];

• 语义:将对指定操作对象的指定操作权限授予指定的用户
• WITH GRANT OPTION：当指定该语句，则获得权限的用户可以向别的用户再次授予该权限
  
  REVOKE语句的一般格式为:

REVOKE<权限> [,<权限>].….
[ON <对象类型><对象名>]
FROM<用户> [<用户>]…
[CASCADE]

• CASCADE：表示级联回收，也就是该用户所赋予给其他用户的权限也会一并回收
  

5.7 并发控制

事务是并发控制的基本单位

事务的特性：

1. 原子性
2. 一致性
3. 隔离性
4. 持久性

并发控制机制的任务

• 对并发操作进行正确调度
• 保证事务的隔离性
• 保证数据库的一致性

5.7.1 并发出现的问题（了解）

并发操作带来的数据不一致性

1. 丢失修改(Lost Update)：两个以上的事务同时对数据库修改，可能产生覆盖问题导致丢失
2. 不可重复读(Non-repeatable Read)：一个事务读之后，另一个事务进行了修改，导致事务想重复读的时候数据变化
3. 读“脏”数据(Dirty Read)：事务想读取另一个事务操作后的结果，但是最终另一个事务的操作rollback了，读取了不是预期的数据

5.7.2 封锁协议（了解两个锁的内容）

封锁就是事务T在对某个数据对象（例如表、记录等）操作之前，先向系统发出请求，对其加锁。加锁后事务T就对该数据对象有了一定的控制，在事务T释放它的锁之前，其它的事务不能更新此数据对象。

基本封锁类型

• 排它锁(Exclusive Locks，简记为X锁)
• 共享锁(Share Locks，简记为S锁)

排他锁又叫写锁

• 若事务T对数据对象A加上X锁，则只允许T读取和修改A，其它任何事务都不能再对A加任何类型的锁，直到T释放A上的锁

共享锁又称为读锁

• 若事务T对数据对象A加上S锁，则事务T可以读A但不能修改A，其它事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁
• 保证其他事务可以读A，但在T释放A上的S锁之前不能对A做任何修改

5.8 反规范化技术

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

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

就是牺牲空间来换取时间效率

六、 计算机网络

七层模型

记忆以下各协议基于哪种协议。并且对应哪个层次

各协议对应的端口号，其中FTP控制端口一般为21，而数据端口不一定是20，这和 FTP的应用模式有关，如果是主动模式，应该为20，如果为被动模式，由服务器端和客户端协商而定

一个标准的URL格式如下：
协议：//主机名 . 域名 .域名后缀或IP地址（：端口号）/ 目录 / 文件名
如http://www.ceiaec.org中，http表示所使用的协议，www.ceiaec.org表示访问的主机和域名。

七、 多媒体基础知识

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

• 多媒体技术基本概念
• 多媒体相关计算问题
• 常见多媒体标准
• 数据压缩技术

7.1 音频

彩色空间：
光的三原色RGB
YUV(电视，兼容)
印刷三原色CMY(CMYK)
HSV(HSB)

7.2 多媒体计算问题

1. 图像容量计算

条件	示例
知道像素，位数	每个像素为16位，图像为640x480像素，求容量: 640×480×16÷8=614，400 B
知道像素，色数	640x480像素，256色的图像，求容量:640x480xlog2 (256)÷8=307，200 B

640x480表示水平像素为640个，垂直像素有480个

2. 音频容量计算
   $$容量=采样频率(Hz)\times 采样位数(位)\times 声道数➗8B$$
3. 视频容量计算
   $$容量=每帧图像容量(Byte)\times 每秒帧数\times 时间+音频容量\times 时间$$

常见的多媒体标准

7.3 数据压缩

7.4 无线通信技术wifi、蓝牙、Zigbee

1、WIFI，WIFI是目前应用最广泛的无线通信技术，传输距离在100-300M，速率可达300Mbps，功耗10-50mA。

2、Zigbee，传输距离50-300M，速率250kbps，功耗5mA，最大特点是可自组网，网络节点数最大可达65000个。

3、蓝牙，传输距离2-30M，速率1Mbps，功耗介于zigbee和WIFI之间。

这3种无线技术，
　　从传输距离来说，是WIFI>ZigBee>蓝牙;
　　从功耗来说，是WIFI>蓝牙>ZigBee，后两者仅靠电池供电即可;
　　从传输速率来讲，是WIFI>蓝牙>ZigBee。

八、 软件开发

从工程管理的角度，可以将软件设计分为两个阶段:概要设计阶段和详细设计阶段。

• 结构化设计方法中，概要设计阶段进行软件体系结构的设计、数据设计和接口设计;详细设计阶段进行数据结构和算法的设计。
• 面对对象设计方法中，概要设计阶段进行体系结构设计、初步的类设计/数据设计、结构设计;详细设计阶段进行构件设计。

结构化设计和面向对象设计是两种不通过的设计方法，结构化设计根据系统的数据流图进行设计，模块体现为函数、过程及子程序;面向对象设计基于面向对象的基本概念进行，模块体现为类、对象和构件等。

内聚类型

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

过程内聚与顺序内聚的区别是： 顺序内聚中是数据流从一个处理单元流到另一个处理单元，而过程内聚是控制流从一个动作流向另一个动作。

8.1 开发模型

瀑布模型

以下情况优先选择这种生命周期：

• 项目需求明确
• 二次开发（因为还是需求明确）
• 充分了解拟交付的产品
• 有厚实的行业实践基础
• 整批一次性交付产品有利于干系人。

• 优点：有利于大型软件开发过程中人员的组织、管理，有利于软件开发方法和工具的研究，从而提高了大型软件项目开发的质量和效率。

• 缺点：开发过程一般不能逆转，否则代价太大；很难严格按该模型进行；瀑布模型是由文档驱动的，缺乏灵活性；很难清楚地给出所有的需求。

原型模型

用最经济的方法开发出一个可实际运行的系统模型（不一定功能完善），用户在运行使用整个原型的基础上，通过对其评价，提出改进意见，对原型进行修改，统一使用，评价过程反复进行，使原型逐步完善，直到完全满足用户的需求为止

优：

• 增加用户与开发人员的交流
• 满足用户的动态需求
• 降低开发风险

缺：

• 因为用户的参与，使得忽视原型对实际环境的适应性等技术问题，所以不适合大型、复杂项目开发
• 对于技术层面远大于其分析层面的问题不宜使用原型法

螺旋模型

该模型是快速原型法，以进化的开发方式为中心，在每个项目阶段使用瀑布模型法。这种模型的每一个周期都包括需求定义、风险分析、工程实现和评审4个阶段，由这4个阶段进行迭代。

• 最大的特点在于引入了其他模型不具备的风险分析，使软件在无法排除重大风险时有机会停止。
• 螺旋模型更适合大型的昂贵的系统级的软件应用

优：

• 设计上的灵活性,可以在项目的各个阶段进行变更
• 以小的分段来构建大型系统,使成本计算变得简单容易
• 客户始终参与每个阶段的开发,保证了项目不偏离正确方向以及项目的可控性

缺：

• 很难让用户确信这种演化方法的结果是可以控制的
• 建设周期长，而软件技术发展比较快，所以经常出现软件开发完毕后，和当前的技术水平有了较大的差距，无法满足当前用户需求

V模型

V模型强调测试，需求分析阶段回去设计验收测试，概要设计阶段设计系统测试，详细设计设计单元测试

• 缺乏灵活性
• 不适用于大型项目
• 测试存在局限性：V模型的测试过程是在开发过程的后期进行的，这意味着问题在测试阶段被发现可能会导致较高的修复成本。

喷泉模型（面向对象）

是面向对象软件过程模型，体现迭代和无缝的特性。

“喷泉”一词体现了面向对象方法的迭代和无间隙性。迭代是指各阶段需要多次重复，例如，分析和设计阶段常常需要多次、重复进行，以更好的实现需求。无间隙性是指各个阶段之间没有明显的界限，并常常在时间上互相交叉，并行进行。

该模型认为软件开发过程自下而上周期的各阶段是相互重叠和多次反复的，就像水喷上去又可以落下来，类似一个喷泉。

优：

1. 各个阶段没有明显的界限，开发人员可以同时进行多步骤，故软件项目开发效率高，节省开发时间。
2. 软件的某个部分通常被重复多次。

缺：

1. 该模型的各个阶段没有明显的界限，开发人员可以同步进行开发，则开发过程中需要大量开发人员。
2. 需严格管理文档，从而又使得审核的难度加大，因为随时面对加入的各种信息、需求与资料等

构件组装模型

极大的提高了软件的复用性，降低成本，提高可靠性

统一过程模型（UP）

可应用于大型软件开发

• 以用例和风险驱动
  • 用例（User Case） ：是用户对系统的业务需求，即用例是能够像用户提供有价值结果的系统中的一种功能。
• 以架构为中心
• 迭代和增量

敏捷开发方法（XP极限编程）

敏捷开发以用户的需求进化为核心，采用迭代、循序渐进的方法进行软件开发。（用户直接参与）
尽可能早地、持续地对有价值的软件的交付
适应于需求变化快、有创新性、大型复杂的项目

• Scrum并列争球法：
  Scrum 是一个用于开发和维持复杂产品的框架，是一个增量的、迭代的开发过程，是敏捷开发的一种实现机制。主张知识源于经验, 以及基于已知的东西做决定。整个开发过程由若干个短的迭代周期组成，一个短的迭代周期称为一个冲刺。

• XP极限编程：XP适用于规模小、进度紧、需求变化大、质量要求严的项目。
  XP是一种轻量（敏捷）、高效、低风险、柔性、可预测、科学而且充满乐趣的软件开发方式。与其他方法论相比，其最大的不同在于：

  • 在更短的周期内，更早地提供具体、持续的反馈信息。
  • 在迭代的进行计划编制，首先在最开始迅速生成一个总体计划，然后在整个项目开发过程中不断的发展它。
  • 依赖于自动测试程序来监控开发进度，并及早地捕获缺陷。
  • 依赖于口头交流、测试和源程序进行沟通。
  • 高频率的重新设计和重构
  • 测试先行，先测试，再写代码

• 水晶球法：
  按照项目不同，分为不同颜色的水晶，每种水晶对应的参与人员的种类不同。
  所以该方法认为每一个不同的项目需要一套不同的策略。

优点：

• 敏捷开发的高适应性，以人为本的特性。
• 更加的灵活并且更加充分的利用了每个开发者的优势，调动了每个人的工作热情。

缺点：

• 由于其项目周期很长，所以很难保证开发的人员不更换，而没有文档就会造成在交接的过程中出现很大的困难。

8.2 软件测试

动态测试

• 黑盒测试法

  • 把程序看作一个黑盒子，完全不考虑程序内部结构和处理过程。只检查程序功能是否能按照规格说明书的规定正常使用，程序是否能适当地接受输入数据并产生正确的输出信息。

• 白盒测试法（一般更加全面）

  • 把程序堪称装在透明的白盒子中，测试者完全知道程序结构和处理算法，按照程序内部的逻辑测试程序，检测程序中的主要执行通路是否按预定要求工作。
    • 常用的白盒测试用例设计方法有:
      语句覆盖、判定覆盖、条件覆盖、条件判定覆盖、条件组合覆盖、路径覆盖等，发现错误的能力呈由弱至强的变化。
      • 语句覆盖：每条语句至少执行一次。
      • 判定覆盖：每个判定的每个分支至少执行一次。
      • 条件覆盖每：个判定的每个条件应取到各种可能的值。
      • 判定/条件覆盖同时满足判定覆盖条件覆盖。
      • 条件组合覆盖：每个判定中各条件的每一种组合至少出现一次。
      • 路径覆盖：使程序中每一条可能的路径至少执行一次。

• 灰盒测试法

静态测试

• 代码走查
• 桌前检查
• 代码审查

8.2.1 测试阶段

8.2.2 调式方法

常用的调试方法有试探法、回溯法、对分查找法、演绎法和归纳法。

• 试探法：调试人员分析错误的症状，猜测问题所在的位置，利用在程序中设置输出语句，分析寄存器、存储器的内容等手段获得错误的线索，一步一步地试探和分析出错误所在。这种方法效率都很低，适合于错误比较简单的程序。

• 回溯法：调试人员从发现错误症状的位置开始，人工沿着程序的控制流程往回跟踪代码，直到找出错误根源为止。这种方法适合于小型程序，对于大规模程序，由于其需要回溯的路径太多而变得不可操作。

• 对分查找法：这种方法主要用来缩小错误的范围，如果已经知道程序中的变量在若干位置的正确取值，可以在这些位置给这些变量以正确值，观察程序运行的输出结果，如果没有发现问题，则说明从赋予变量一个正确值开始到输出结果之间的程序没有错误，问题可能在除此以外的程序中。否则错误就在所观察的这部分程序中，对含有错误的程序段再使用这种方法，直到把故障范围缩小到比较容易诊断为止。

• 归纳法：归纳法就是从测试所暴露的问题出发，收集所有正确或不正确的数据，分析它们之间的关系，提出假想的错误原因，用这些数据来证明或反驳，从而查出错误所在。

• 演绎法：演绎法根据测试结果，列出所有可能的错误原因；分析已有数据，排除不可能和彼此矛盾的原因；对其余原因，选择可能性最大的，利用已有的数据完善该假设，使假设更具体；用假设来解释所有的原始测试结果，如果能解释这一切，则假设得以证实，也就是找出错误，否则，要么是假设不完备或不成立，要么有多个错误同时存在，需要重新分析，提出新的假设，直到发现错误为止。

8.3 McCabe复杂度计算（环路复杂度）

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

8.4 软件维护

（1）更正性维护(纠错性维护)。
诊断和修正系统中遗留的错误，就是纠错性维护。 纠错性维护是在系统运行中发生异常或故障时进行的。

（2）适应性维护
适应性维护为了使系统适应环境的变化而进行的维护工作

（3）完善性维护
在系统的使用过程中， 用户往往要求扩充原有系统的功能 ，增加一些在软件需求规范书中没有规定的功能与性能特征，以及对处理效率和编写程序的改进。核心：基于用户对软件完善。例如：用户觉得某处不行，我们去改，这就是完善性维护。

（4）预防性维护
系统维护工作不总是被动地等待用户提出要求后才进行，应进行主动的预防性维护， 即选择那些还有较长使用寿命， 目前尚能正常运行， 但可能将要发生变化或调整的系统进行维护， 目的是通过预防性维护为未来的修改与调整奠定更好的基础 。

8.6 项目管理

8.6.1 甘特图

• Gantt图能清晰地描述每个任务从何时开始，到何时结束，任务的进展情况以及各个任务之间的并行性。
• 但是它不能清晰地反映出各任务之间的依赖关系，难以确定整个项目的关键所在，也不能反映计划中有潜力的部分

甘特图示例：

8.6.2 PERT图

PERT 图可以表示出依赖关系。

1. 求所有事件的最早发生时间ve()：ve(k)=Max{ve(j)+Weight(vj,vk)}，vk为vj的任意后继。
   比如，ve(4)=Max{3+2，2+4}=6
   

2. 求所有事件的的最迟发生时间vl()：即从汇点出发，结点的最迟发生时间=Min{所有后继结点的ve-权值}。
   比如v3有v4，v6两个后继，vl(3)=Min{8-3，6-4}=4
   

3. 求所有活动的最早发生时间e()：活动的最早时间就是边的尾结点的事件最早时间。
   

4. 求所有活动的最迟发生时间l()：用弧头的事件最迟时间减去边的权值。
   

5. 求所有活动的时间余量d()：活动最迟时间-活动最早时间，即l(i)-e(i)
   

6. 所有余量d为0的活动就是关键活动，由关键活动可得关键路径
   

综上，

• 若关键活动耗时增加，整个工程的时间将增加。
• 缩短关键活动的时间，可以缩短整个工程的工期。但是当缩短到一定程度时，关键活动可能变成非关键活动。
• 可能有多个关键路径，则若要缩短工期则要缩短所有关键路径，一条可不行。

8.6.3 风险

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

9.7 软件质量评估模型

ISO9126软件质量模型是一个分层的质量模型，有6个影响质量的特性，模型中说明了质量特性及其子特性的关系。

9.8 COCOMO 估算模型

COCOMO 模型是一种精确的、易于使用的成本估算模型。

COCOMO 模型按其详细程度分为：基本 COCOMO 模型、中级 COCOMO 模型、详细 COCOMO 模型。

1. 基本 COCOMO 模型
   基本 COCOMO 模型是一个静态单变量模型，用于对整个软件系统进行估算。

2. 中级COCOMO 模型
   中级 COCOMO 模型是一个静态多变量模型，它将软件系统模型分为系统和部件两个层次，系统由部件构成，它把软件开发所需的人力(成本)看作是程序大小和一系列“成本驱动属性”的函数。
   中级 COCOMO 模型以基本 COCOMO 模型为基础，并考虑了 15 种影响软件工作量的因素，通过工作量调节因子 (EAF) 修正对工作量的估算，从而使估算更合理。

3. 详细 COCOMO 模型
   它将软件系统模型分为系统、子系统和模块3 个层次，除包括中级模型所考虑的因素外，还考虑了在需求分析、软件设计等每一步的成本驱动属性的影响。

• COCOMOII模型

最初的 COCOMO 模型是得到产业界最广泛应用和讨论的软件成本估算模型之一，现在它已经演化成更全面的估算模型，称为 COCOMOII。

和其前身一样，COCOMOII 也是一种层次结构的估算模型，被分为 3 个阶段性模型。
(1) 应用组装模型；（使用对象点）
(2) 早期设计阶段模型；（使用功能点）功能点可以转化为对应的代码行数
(3) 体系结构阶段模型；（使用代码行）

和所有的软件估算模型一样，COCOMOII 模型也需要使用规模估算信息，在模型层次结构中有3 种不同的规模估算选择：对象点、功能点和代码行。

9.9 CMM的等级结构

CMM 包括五个成熟度等级，每个等级都代表了组织在过程改进上达到的阶段。下面我将逐一介绍这五个成熟度等级：

1. 初始级（Initial）- 等级 1
   组织的过程是不可预测的，且因项目而异。成功依赖于个人努力，缺乏稳定的环境。
   共性目标是过程将可标识的输入工作产品转换成可标识的输出工作产品，以实现支持过程域的特定目标
   例子：一家初创软件公司可能没有固定的开发流程，项目的成功很大程度上依赖于员工的个人经验和努力。

2. 可重复级（Repeatable）- 等级 2
   组织已经建立了基本的项目管理过程来跟踪成本、进度和功能。这个级别的组织能够重复之前成功的项目的结果。
   例子：软件公司开始实施项目管理标准，能够使用之前成功项目的经验来管理新项目，减少了因管理不善导致的风险。

3. 已定义级（Defined）- 等级 3
   组织的过程已经被标准化、文档化，并且被整个组织所接受。这意味着所有项目都遵循一个统一的开发过程。
   例子：公司建立了一套标准的软件开发流程，所有项目团队都必须遵守这些流程，确保了项目开发的一致性和预测性。

4. 已管理级（Managed）- 等级 4
   组织通过收集详细的度量标准，对其过程和产品进行量化管理。这使组织能够控制过程的变异，并持续改进过程性能。
   例子：公司不仅有一套成熟的开发流程，还通过收集项目过程中的数据（如缺陷率、开发时间等）来分析和改进这些流程。

5. 优化级（Optimizing）- 等级 5
   组织持续进行过程改进和创新，通过量化的反馈和先进的技术方法不断优化过程性能。
   例子：公司定期审视和调整其软件开发流程，利用新技术和方法来提高效率和产品质量，确保持续的优化和创新。

9.10 容错系统

容错系统是指在一定程度上具有容错功能的系统，实现容错的主要办法就是冗余
冗余附加技术的构成主要包括：

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

9.11 界面设计三条黄金准则

• 置于用户于控制之下
• 减少用户的记忆负担
• 保持界面一致
  • 没有界面美观

9.12 结构化分析

结构化方法的分析结果由以下几部分组成：

• 一套分层的数据流图、
• 一本数据词典、
• 一组小说明（也称加工逻辑说明）、
• 补充材料。

9.13 管道 - 过滤器架构

管道-过滤器模式的体系结构是面向数据流的软件体系结构，主要用于实现复杂的数据多步转换处理。
每个处理步骤封装在一个过滤器组件中。数据通过相邻过滤器之间的管道传输。

管道过滤器风格具有许多很好的特点：
（1）使得软件构件具有良好的隐蔽性和高内聚、低耦合的特点；
（2）允许设计者将整个系统的输入/输出行为看成是多个过滤器的行为的简单合成；
（3）支持软件重用；
（4）支持并行执行；
（5）允许对一些如吞吐量、死锁等属性的分析。
但是不能提高性能。

九、UML

9.1 数据流图DFD（重点）

• 数据流的起点或者终点必是加工

数据流图示例

9.1.1 数据流图的分层

9.1.2 数据流图的平衡原则

平衡原则有两个维度：父图与子图之间的平衡、子图内平衡

1. 父图与子图之间的平衡
   已知父图或者子图，将其子图或者父图补充完整
2. 子图内平衡
   数据流的正常加工必须是既有输入，也有输出，而且每条数据流的起点或终点必须是加工，
   只有输入没有输出的数据流称之为黑洞，只有输出没有输入的数据流被称之为奇迹(白洞)，二者都属于不正常的数据流。

父图与子图的平衡定义：父图中某加工的输入输出数据流必须与它的子图的输入输出数据流在数量、名字和方向上保持一致。
如果父图的一个输入(或输出)数据流对应于子图中几个输入(或输出）数据流，而子图中组成这些数据流的数据项全体正好是父图中的这一个数据流那么它们仍然算是平衡。

9.2 数据字典

例题讲解

做第三问时，可以从前两问的基础上，直接进行图的对比，将信息放入图中后，对比两图得到错误信息。

9.3 UML图

9.3.1 用例图（动态）

由参与者（Actor）、用例（Use Case）以及它们之间的关系构成的用于描述系统功能的动态视图称为用例图。

用例之间的关系

1. 包含
   包含关系指用例可以简单地包含其他用例具有的行为，并把它所包含的用例行为作为自身行为的一部分。
   　　
2. 扩展
   把新的行为加入到已有的用例中，获得的新用例叫做扩展用例(Extension)，原有的用例叫做基础用例(Base)，从扩展用例到基础用例的关系就是扩展关系。
   
3. 泛化
   用例的泛化指的是一个父用例可以被特化形成多个子用例，而父用例和子用例之间的关系就是泛化关系。
   当多个用例共同拥有一种类似的结构和行为的时候，可以将它们的共性抽象成为父用例，其他的用例作为泛化关系中的子用例。
   　

9.3.2 类图与对象图（静态）

用于描述系统中的类(对象)本身的组成和类(对象)之间的各种静态关系。
类之间的关系： 依赖、泛化（继承）、实现、关联、聚合与组合

数字也可以改成其他的，表示对应n个对象


泛化关系主要指向实体类，通常是继承。
实现关系主要指向接口，实现了某个接口。

类图内部的含义：

• 第一行，表示类的名字，如 书籍列表；
• 第二行，表示类的属性，如 书名，格式为属性名：类型 = 默认值，其中可以不包含默认值；
• 第三行，表示类的方法，如 新增()，格式为方法名（参数列表）：返回值，其中可以不含参数，无返回值。

注意，+、-表示属性是公开的还是私有的（public 或 private），此外还有#表示保护（protected），static静态方法。

9.3.3 活动图（动态）

活动图是UML用于对系统的动态行为建模的另一种常用工具，它描述活动的顺序，展现从一个活动到另一个活动的控制流，活动图在本质上是一种流程图

带泳道的活动图

9.3.4 状态图（动态）

状态图是一种行为图。描述一个特定对象的所有可能的状态以及引起状态转换的事件。

起始状态：黑色实心
终止状态：用一对同心圆(内圆为实心圆)表示
行为转移：两个状态之间带箭头的连线，箭头指明了转换方向。
中间状态：用圆角矩形表示，可以用两条水平横线把它分成上、中、下3个部分。（上面部分为状态的名称，这部分是必须有的；中间部分为状态变量的名字和值，这部分是可选的；下面部分是活动表，这部分也是可选的）

转换（迁移）是从源状态和目的状态之间的一种关系，可以包含触发事件、监护条件、状态（源状态和目的状态）、动作

做题时，找出几种状态，还有引起状态改变的原因

9.3.5 通信图

通信图更适用于展示系统中的对象结构，而顺序图则擅长表现交互中消息的顺序。

9.3.6 组件图（静态）

1. 组件图又叫构件图（Component Diagram）
2. 展现了一组构件之间的组织和依赖
3. 构件图专注于系统的静态实现视图
4. 它与类图相关，通常把构件映射为一个或多个类、接口或协作

供接口表示提供接口，提供接口需要被实现的
需接口表示需要接口，是去实现接口的地方
上图中就是Order System调用Inventory System所实现的接口

【注意】：构件的特点

9.3.7 部署图（静态）

下午题不考！

部署图是用来对面向对象系统的物理方面建模的方法。

展现了运行时处理结点以及其中构件(制品)的配置。
部署图对系统的静态部署视图进行建模，它与构件图相关。

通常，一个结点是一个在运行时存在并代表一项计算资源的物理元素，至少拥有一些内容常常具有处理能力，包含一个或多个构件。

部署图展现了系统的软件、硬件之间的关系。
部署图在实施阶段使用。

9.4 UML题型举例

问题1：S1:普卡会员，S2:银卡会员，S3:金卡会员，T1:25000<=里程<5000，T2:里程>=50000，T3:里程>=50000
问题2：略
问题3：状态模式，travel方法应具有计算里程数的功能，以此判断是否需要调整会员等级

十、 网络安全

安全属性及其方法：

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

主动攻击和被动攻击

1. 主动攻击：
   • 在主动攻击中，攻击者直接与目标系统交互，试图更改或破坏系统资源、数据或服务。
   • 主动攻击往往会对目标系统产生直接和显著的影响。
   • 主动攻击的例子包括：篡改数据、拒绝服务攻击（DoS）、伪造身份、中断服务等。
2. 被动攻击：
   • 被动攻击是指攻击者尝试获取信息而不影响系统资源的攻击。
   • 被动攻击通常难以被察觉，因为它们对目标系统没有直接的破坏性影响。
   • 被动攻击的例子包括：窃听（监听通信）、流量分析、密码破解等。

总之，主动攻击和被动攻击的主要区别在于攻击者与目标系统的交互方式以及对系统资源的影响程度。主动攻击直接影响系统资源，而被动攻击更注重收集信息而不干扰系统。

• 对称加密算法：对称加密算法是指使用相同的密钥对信息进行加密和解密，即发送方和接收方使用相同的密钥。常见的对称加密算法包括DES、3DES、AES等。
• 非对称加密算法：非对称加密算法是指使用两个密钥，分别为公钥和私钥，对信息进行加密和解密。公钥用于加密，私钥用于解密。常见的非对称加密算法包括RSA、ECC等。
• 消息摘要算法：消息摘要算法是一种单向加密算法，主要用于生成消息的哈希值或数字签名。常见的消息摘要算法包括MD5、SHA-1、SHA-256等。

对称加密都是用不公开的密钥加密，非对称加密使用公私钥进行加密

10.1 对称/非对称加密

对称加密：加密和解密所使用的密钥一致。适合大数据量加密，比如几百M的数据
缺陷：
1、加密强度不高。
2、密钥分发困难。

非对称加密：加解密所使用的密钥不一致，适合小数据量加密
缺陷：
加密速度慢

10.2 信息摘要

信息摘要就是原数据通过某个算法生成的一个固定长度的单向Hash散列值
信息摘要的特点：当一大串数据内容中即使很小的一个字符发生变化，都会引起信息摘要发生很大的变化。因此可以通过信息摘要来判断原始数据是否被篡改。

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

信息摘要不能用来做加密，一般用于生成数字签名。

10.3 数字签名

Bob 用自己的私钥对邮件内容计算一个「签名」，将「签名」和邮件内容一起发送出去，接受者 Alice 可以使用 Bob 的公钥验证这个签名是否正确，这就叫「验签」。

如果不是 Bob 的私钥计算的签名，那么 Alice 用 Bob 公钥验签将会出错。

「签名」的作用本身也不是用来保证数据的机密性，而是用于验证数据来源的防止数据被篡改的，也就是确认发送者的身份。
如果数据量大的时候计算数字签名将会比较耗时，所以一般做法是先将原数据进行 Hash 运算，得到的 Hash 值就叫做「摘要」。
「摘要」就像人的指纹一样，可以代表一个人，只要内容发生了改变，计算出来的摘要也应该变化。

发送者使用私钥对「摘要」计算数字签名。那么接收者如何验证呢？

接受者 Alice 收到后，取下数字签名，同时用 Bob 的公钥解密，得到「摘要1」，证明确实是 Bob 发的。
再对邮件内容使用相同的散列函数计算「摘要2」，与上面得到的「摘要1」进行对比，两者一致就说明信息未被篡改。

数字信封与PGP

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

• PGP可用于电子邮件，也可以用于文件存储。采用了杂合算法，包括IDEA、RSA、MD5、ZIP数据压缩算法。PGP（全称：Pretty Good Privacy，优良保密协议），是一套用于信息加密、验证的应用程序，可用于加密电子邮件内容。
• PGP承认两种不同的证书格式:PGP证书和X.509证书。
  • PGP证书包含PGP版本号、证书持有者的公钥、证书持有者的信息、证书拥有者的数字签名、证书的有效期、密钥首选的对称加密算法。
  • X.509证书包含证书版本、证书的序列号、签名算法标识、证书有效期、以下数据:证书发行商名字、证书主体名、主体公钥信息、发布者的数字签名。
    • X.509证书标准支持三种不对称加密算法：RSA, DSA, Diffie-Hellman algorithms。最常用的是RSA算法。

数字证书

数字证书是由权威机构——CA证书授权（Certificate Authority）中心发行的，能提供在Internet上进行身份验证的一种权威性电子文档，人们可以在因特网交往中用它来证明自己的身份和识别对方的身份。
数字证书包含版本、序列号、签名算法标识符、签发人姓名、有效期、主体名和主体公钥信息等并附有CA的签名，用户获取网站的数字证书后通过CA的公钥验证CA的签名，从而确认数字证书的有效性，然后验证网站的真伪。

10.4 各个网络层次的防护技术

10.5 网络威胁与攻击

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

10.6 病毒类型

• 宏病毒 （Macro表示宏病毒）：一种脚本病毒，它的最主要特征是它是一种寄存在文档或模板的宏中的计算机病毒。宏病毒主要感染文件有Word、Excel的文档。并且会驻留在Normal面板上。宏病毒的前缀是:Macro，第二前缀是: Word、Excel其中之一。如:Macro.Word.WhiteScreen、美丽莎(Macro.Melissa)等。
• 蠕虫病毒：欢乐时光、熊猫烧香、红色代码、爱虫病毒、震网。
  蠕虫病毒（Worm）的名字由来与其在网络上的传播方式和行为特性有关。蠕虫病毒是一种自我复制的代码，能够在网络中传播并感染其他计算机。其传播方式类似于生物学中的蠕虫移动和繁殖，因此得名“蠕虫病毒”。
• 木马软件：冰河、X卧底
  特洛伊木马病毒通过电子邮件、附件、横幅广告、弹出广告、网站链接等方式进行传播，也可能隐藏在自由下载的文件中。一旦运行，木马病毒会自动复制到系统文件夹中，并在注册表、启动组等位置设置好触发条件，接受来自远程攻击者的控制命令。

十一、 编译原理

11.1 编译过程

知道编译的先后顺序以及错误的类型

语义分析分为静态语义分析和动态语义分析。
静态语义分析在编译器就可确定，动态语义分析在运行期才能确定。
静态语义分析包括：声明和类型是否匹配，类型转换包括将浮点型转换成整型。动态语义分析包括把0作为除数。

编译全过程：

• 预处理：处理源代码中的预处理指令，如#include、#define等。
• 编译：将预处理后的代码转换为汇编代码。
• 汇编：将汇编代码转换为机器码。
• 链接：将各个目标文件、库文件等链接起来，生成最终的可执行文件。

正规式（重点）

将正规文法转换为正规式 ：可反复采用以下三条规则，直到只剩下一个开始符号定义的正规式为止。

• 产生式A→xB, B→y对应正规式A=xy;
• 产生式A→xA|y对应正规式A=x*y;
• 产生式A→x, A→y对应正规式A=x|y;

S→aA
S→a
A→aA
A→dA
A→a
A→d由文法G[S]得
S=aA|a
A = aA|dA|a|d=(aA|dA)|(a|d)=(a|d)A|(a|d)=(a|d)*(a|d)= (a|d)+
则
S= a(a|d)+|a= a((a|d)+|ε)= a(a|d)*

有限自动机

其中：δ（S,0）=B表示对S输入0可以转换为B

一般题型会出，该有限自动机能不能解析出如01这样的串，也就是有没有从起点到终点的路径上有没有这样的字符串。
其中：δ（S,0）=B表示对S输入0可以转换为B

表达式（重点）

重点就是表达式的二叉树的构造

十二、法律法规

我国保护计算机软件著作权的两个基本法律文件是《中华人民共和国著作权法》（一般简称《著作权法》）和《计算机软件保护条例》（简称《软著权法》）

• 保护期限
  

• 知识产权人的确定

• 确定侵权判断
  

十三、 专业英语

（1）通过首句或出现的核心词汇来推断全文的信息。短文的首句往往是主题句，或出现了核心词汇，能为理解文章的大意和主要内容提供必要线索。一般首句还擢供背景资料，因此要特别注意首句，抓住整个段落的纲要。
（2） 把握文章发展的基本线索。文章总是按照定思路发展起来的，不同的逻辑关系主要依靠使用逻辑连接词来表达，文章如果没有内在的逻辑关系，就会出现语义不清、逻辑混乱的问题。所以，通过表示逻辑关系的词汇把握文章发展的基本线索是至关重要的。
（3） 借助语法知识和专业背景知识确定正确的词汇选项。

• 专业词汇

十四、 面向对象技术

多态类型：

• 参数多态：方法的参数可以接受不同类型的对象，并根据实际传递的对象类型来执行不同的操作。
  • 假设有一个抽象类Shape和其子类Rectangle和Circle，它们都有一个方法draw()用于绘制图形。我们可以定义一个绘图方法drawShape()，其参数类型为Shape，可以接受不同类型的图形对象，并调用draw()方法来绘制图形。
• 包含多态：同样的操作可用于一个类型及其子类型。包含多态一般需要进行运行时的类型检查。包含多态在许多语言中都存在，最常见的例子就是子类型化，即一个类型是另外一个类型的子类型。
• 强制多态：编译程序通过语义操作，把操作对象的类型强行加以变换，以符合函数或操作符的要求。
  • 指通过类型转换将一个对象视为另一个类型的行为。在参数多态中，可以将子类对象强制转换为父类对象，并将其作为参数传递给接受父类对象的方法。通过强制多态，可以实现对象的向上转型和多态的传递。
• 过载多态：过载多态是指在同一个类中，方法名相同但参数类型或参数个数不同的多个方法，它们可以根据不同的参数进行重载。 目前软设考查比较多的是过载多态。

LISP是一种通用高级计算机程序语言，是第一个声明式系内函数式程序设计语言
命令式系内过程式的C、Fortran
面向对象的Java、C#等结构化程序设计语言。

• 动态绑定：程序运行过程中，把函数（或过程）调用与响应调用所需要的代码相结合的过程。
• 静态绑定：在程序编译过程中，把函数（方法或者过程）调用与响应调用所需的代码结合的过程。

14.1 设计模式

结构类型的单词开头就是ABCDFFP
创建型比较简单好记
余下的就是行为型，就可以简单记住分类了。

14.2 创建型

创建型模式抽象了实例化过程，它们帮助一个系统独立于如何创建、组合和表示它的那些对象。一个类创建型模式使用继承改变被实例化的类，而一个对象创建型模式将实例化委托给另一个对象。

14.2.1 工厂模式（Factory Method）

问题：由于需求的变化，需要创建的对象的具体类型经常变化。

功能：定义一个用于创建对象的接口，让子类决定实例化哪一个类。

Factory Method模式通过面向对象的手法，将所要创建的具体对象工作延迟到子类，从而实现一种扩展（而非更改）的策略，较好地解决了这种紧耦合关系。

适用场景：

• 当一个类不知道它所必须创建的对象的类的时候。
• 当一个类希望由它的子类来指定它所创建的对象的时候。
• 当类将创建对象的职责委托给多个帮助子类中的某一个，并且你希望将哪一个帮助子类是代理者这一信息局部化的时候。

14.2.2 生成器模式（Bulider）

• 意图
  将一个复杂对象的构建与它的表示分离，使得同样的构建过程可以创建不同的表示。

• 结构
  

• Builder为创建一个Product对象的各个部件指定抽象接口。

• ConcreteBuilder实现 Builder的接口以构造和装配该产品的各个部件,定义并明确它所创建的表示，提供一个检索产品的接口。

• Director构造一个使用Builder接口的对象。

• Product表示被构造的复杂对象。ConcreteBuilder创建该产品的内部表示并定义它的装配过程。包含定义组成组件的类，包括将这些组件装配成最终产品的接口。

• 适用场景

  • 当需要创建的对象包含多个部件，并且需要按照特定顺序或逻辑来构建对象时。
  • 当对象的构建过程复杂且需要隐藏构建细节时。
  • 当需要创建不同表示的对象，但构建过程相同或相似。

14.2.3 原型模式（Prototype）

• 意图
  用原型实例指定创建对象的种类，并且通过复制这些原型创建新的对象。

• 结构
  

• Prototype 声明一个复制自身的接口。

• ConcretePrototype 实现一个复制自身的操作。

• Client 让一个原型复制自身从而创建一个新的对象。

• 使用场景

  • 当一个系统应该独立于它的产品创建、构成和表示时。
  • 当要实例化的类是在运行时刻指定时，例如，通过动态装载。
  • 为了避免创建一个与产品类层次平行的工厂类层次时。
  • 当一个类的实例只能有几个不同状态组合中的一种时。建立相应数目的原型并克隆它们，可能比每次用合适的状态手工实例化该类更方便一些。

14.3 结构型设计模式

14.3.1 适配器模式（Adapter）

• 意图
  将一个类的接口转换成客户希望的另外一个接口。Adapter模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。
• 结构
  类适配器使用多重继承对一个接口与另一个接口进行匹配，
  
  对象适配器依赖于对象组合
  
  Target定义Client使用的与特定领域相关的接口。
  Client与符合Target接口的对象协同。
  Adaptee定义一个已经存在的接口，这个接口需要适配。
  Adapter 对Adaptee的接口与Target接口进行适配。

可以理解为，Client使用USB接口，而Adaptee是TypeC类型，Adapter是转换器，让用户可以使用
也就是说Client使用Target接口，然后Adapter通过对Adaptee进行接口转换，使Client可以使用Adaptee。

• 适用场景
• 想使用一个已经存在的类，而它的接口不符合要求。
• 想创建一个可以服用的类，该类可以与其他不相关的类或不可预见的类(即那些接口可能不一定兼容的类)协同工作。
• (仅适用于对象Adapter)想使用一个已经存在的子类，但是不可能对每一个都进行子类化以匹配它们的接口。对象适配器可以适配它的父类接口。

14.3.2 桥接模式（Bridge）

• 意图
  将抽象部分与其实现部分分离，使它们都可以独立地变化。

• 结构
  

• Abstraction 定义抽象类的接口，维护一个指向Implementor类型对象的指针。

• RefinedAbstraction 扩充由Abstraction定义的接口。

• Implementor 定义实现类的接口，该接口不一定要与Abstraction的接口完全一致;

• ConcreteImplementor实现 Implementor接口并定义它的具体实现。

• 适用场景

  • 不希望在抽象和它的实现部分之间有一个固定的绑定关系。例如，这种情况可能是因为，在程序运行时刻实现部分应可以被选择或者切换。
  • 类的抽象以及它的实现都应该可以通过生成子类的方法加以扩充。这是Bridge模式使得开发者可以对不同的抽象接口和实现部分进行组合，并分别对它们进行扩充。
  • 对一个抽象的实现部分的修改应对客户不产生影响，即客户代码不必重新编译
  • (C++）想对客户完全隐藏抽象的实现部分。
  • 有许多类要生成的类层次结构|
  • 想在多个对象间共享实现（可能使用引用计数)，但同时要求客户并不知道这点。

14.3.3 组合模式（Composite）

• 意图
  将对象组合成树型结构以表示“部分-整体”的层次结构。
  Composite使得用户对单个对象和组合对象的使用具有一致性。
• 结构
  

14.3.4 装饰器模式（Decorator）

• 意图
  动态地给一个对象添加一些额外的职责,就增加功能而言，Decorator模式比生成子类更加灵活。
• 结构
  

后续内容