数据的表示

R进制转十进制：按权展开法

二进制1001010.01=
整数部分：1001010从左向右看
第一位：0×2¹，第二位：1×2¹，第二位：0×2²……
小数部分：01
第一位：0×2^-1，第二位：1×2^-2
以此类推，将求得的值加上就是十进制的值（Tip：0乘任何数都为0，因此在求解的时候可以不用写出来），以上解的值为74.25。
其余进制也是相同的求法，不同的地方在于要将2改成对应的进制，例如是8进制即是8的多少次方。

十进制整数转R进制

全为整数：短除法

例如：98转二进制
98÷2=49余0
49÷2=24余1
24÷2=12余0
12÷2=6余0
6÷2=3余0
3÷2=1余1
1（逆序排上去）
结果为：1100010

有小数转R进制

整数部分使用短除法，小数部分乘上对应的进制数，取其整数部分的数值，小数部分继续相乘（Tip：有些数值并不总能转换成对应的R进制的小数，就需要采用取近似值的方法）
例如：0.25转二进制
第一次：0.25×2=0.5取0
第二次：0.5×2=1取1
0.25的二进制表示就为：0.01
若要转为其它进制只需要将2改成对应的进制即可。

二进进制，八进制，十六进制相互转换

二进进制转八进制

每三个二进制位对应一个八进制
例如：10001110
从右至左分段，每三个分一段：10 001 110（Tip：最左边的也许会不足三个，只需要补上0即可）
然后分别使用按权展开相加即可
110=1×2¹+1×2²=6
001=1×2⁰=1
10=1×2¹=2
10001110对应的八进制即：216

二进进制转十六进制

每四个二进制位对应一个十六进制
例如：10001110
从右至左分段，每四个分一段：1000 1110（Tip：最左边的也许会不足三个，只需要补上0即可）
然后分别使用按权展开相加即可
1110：1×2¹+1×2²+1×2³=14
14对应十六进制的的E（Tip：不清楚的可以去看看16进制表）
1000：1×2³=8
10001110对应的十六进制即：8E
如果是需要八进制转十六进制的，我还不知道咋整，我是把八进制转回二进制再转成十六进制的。

原码计算

将十进制转为二进制，如果不足八位，在前面补0，直至满八位。

	数值1	数值-1
原码	0000 0001	1000 0001

最高位为符号位（表格中加粗的），0表示整数，1表示负数

反码计算

	数值1	数值-1	1-1
反码	0000 0001	1111 1110	1111 1111

正数的反码、补码、原码相同，负数的符号位保持不变，其余各位分别取反。
由此可得，
反码进行1-1的计算后得：1111 1111
由于是反码，求解时需要将其转为源码
符号位不变得：1000 0000
转为十进制得：-0，与我们需要得到的结果接近
我们平时肯定直接说0而不会说-0

补码计算

	数值1	数值-1	1-1
补码	0000 0001	1111 1111	0000 0000

负数的补码在反码的基础上+1
1-1得到值为0，求解完毕。

移码计算

	数值1	数值-1	1-1
移码	1000 0001	0111 1111	1000 0000

在补码的基础上将首位进行取反操作

原反补的取值范围

	整数
原码	-（2n-1-1）~2n-1-1 （设n=8，-127~127）
反码	-（2n-1-1）~2n-1-1
补码	-2n-1~2n-1-1

补码之所以表示的范围比原码与反码多一位，是由于0与-0在原码与反码中表示的形式是不一样的，而在补码中的表示形式是一样的。

浮点数运算

浮点数表示：N = M×R^e
M：尾数，e：指数，R：基数
运算步骤：对阶→尾数计算→结果格式化
例题：1×10³+1.19×10²
①1.19×10²转为0.119×10³
②1×10³+0.119×10³ = 1.119×10³
结果格式化是指：结果必须是科学计数法的形式，第一位不能为0或小数点前只能有一位。

计算机结构

主机组成：CPU和主存储器（内存）

运算器（被称作算数逻辑单元ALU）用于运算
累加寄存器AC：是一个通用的寄存器，在运算的过程中它会去存储一些运算时需要用到的值
数据缓冲寄存器DR：在对内存储器进行读写操作时用于暂存数据
状态条件寄存器PSW：用于存储运算当中相关的标志位例如进位，溢出，中断等涉及到状态时需要保存就存在PSW中
控制器用于指令操作，与指令相关的往往与控制器相关
程序计数器PC：在运行完一条指令后，要了解运行下一条指令的位置，由PC完成

Flynn分类法

分类指标：指令流，数据流

CISC与RISC

CISC：在计算机还没全面推广时提出的。

流水线

概念

一条指令的执行过程

计算

流水线执行时长：



执行部分时间最长的一段表示为流水线周期
依照例题，三个部分中执行时间最长的为2ns，因此流水线周期为2

理论公式

t1，t2+…+tk表示的是分为几个部分
依照例题：分为了三个部分：取值，分析，执行
花费的时间分别是：2，2，1
相加结果为5
n表示的是共有几条指令
n-1是因为(t1+t2+…+tk)已经将第一条计算完毕了
Δt表示流水线周期
理论公式求解例题：(2+2+1)×(100-1)×2=203

实践公式

k表示分为几个部分，例题中分为3个部分
n表示共有几条指令
Δt表示流水线周期
实际公式求解例题：(3+100-1)××2=204
考试中一般采用理论公式，如果理论公式找不到答案再采用时间公式的答案

吞吐率（Though Put rate TP）计算

概念

单位时间内处理的任务的数量

公式

吞吐率最基本的公式：

以上面例题为例：
指令条数：100
流水线执行（理论）时间：203
TP=100/203

流水线最大吞吐率：

1/Δt是最理想化的状态，忽略的流水线的准备时间，认为一个流水线周期就能够完成一条指令。

加速比

概念

完成同一批任务，不适用流水线所用的时间与使用流水线所用的时间的比值。

公式

以上一个例题：
不使用流水线执行时间：(2+2+1)×100=500
使用流水线的（理论）时间=203
S=500/203

效率

概念

衡量在整个时空图上，有多少时间片属于有效利用，多少时间片属于没有有效利用的比例

公式

例题：

被有效利用的时间片：(Δt+Δt+Δt+3Δt)×4=24Δt
乘以4：共有4个任务执行
全部的时间片：15Δt*4=60Δt
乘以4：共有4个控件执行
从图中可以看出
E=24Δt/60Δt
综上：在每个部分所需要的时间都均等的清空下，效率较高。

层次化存储结构

Cache是一种以内容存取方式的存储器，它的速度相对于按地址存储的存储器速度要快
寄存器在CPU中

Cache

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

假设h为95%，t₁=1ns，t₂=1ms=1×10⁶
t₃=95%×1ns+(1-95%)×1×10⁶ns=50000.95ns
有命中率因素是因为cpu在访问时会先范文Cache中的内容，若Cache中没有所需要的数据，cpu会再去访问内存中的内容
直接在Cache中就获取到的几率就是命中率，没有在Cache中获取到在内存中获取到的就称为失效率

局部性原理

时间局部性

刚刚被方位的指令立刻又需要被访问

空间局部性

当程序访问了一个空间后又立即访问了它相邻的控件。

主存

分类

随机存储器（RAM）：内存（断点数据就丢失）
只读存储器（ROM）：BIOS

编址

共有（）K个地址单元
算总共有多少个地址单元时，先用（末地址位-首地址位）+1，一般先加1再做减法

芯片每个存储单元存储（）位
先设存储单元位h位
总：112k×16
求解：(112k×16)/28×16k×h
先将k约掉，然后正常计算就能得出结果
求得h为：4

磁盘

磁道保存数据
磁头读取数据
存取时间=寻道时间+等待时间（平均定位时间+转动延迟）
等待时间一般为磁头转一圈时间的一半

由磁盘旋转周期为33ms且共有11个物理块的已知条件可以得到每个磁盘的读取需要3ms
且有每个记录处理时间为3ms以及系统使用单缓冲区顺序处理
且当前磁头在R₀处
可得：处理R₀需要6ms
剩余的每个磁道需要(3×10)+3
因为磁头一旦开始读取数据操作就不会停下，当缓冲区在处理完数据时，已经过3ms，本该在R₁位置的磁头此时已经到了R₂，所以磁头需要继续往下寻道才能找到R₁。
除R₀外每个磁道都需要R₁这样的操作。
因此处理11个记录的最长时间为6+((3×10)+3)×10=336
对信息优化进行处理

上图是数据存储优化后的结果，当R₀被读取结束后，刚好能够直接读取R₁（因为在缓冲区处理数据是需要耗时3ms，而磁头读取数据不会停止，因此处理完R₀时，此时磁头在R₁开始的这个位置上)

总线

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

系统可靠性分析

串联系统

每个系统都必须可靠，任何一个系统不可靠都不行
可靠度：每个系统的可靠度相乘
为什么要相乘：因为这个相当于时在R₁系统可靠的基础上，R₂系统也必须可靠，因此是相乘起来。
失效率：所有系统的失效率累加起来，这个失效率的计算是一个近似的公式，有一定概率不准确。
举例：有20个系统串联，每个系统的可靠度是0.9，失效率为0.1
所有系统的失效率叠加起来为2，因此系统的失效率会等于200%此时就是不准确的。
该失效率的公式适用于当前系统较多，且失效率极低时使用。

并联系统

并联系统：只要有一个系统能够正常运行，则整个系统就都能正常运行

可靠率：1-(1-R₁)×(1-R₁)……×(1-R_n)
(1-R₁)：每个系统的失效率
相乘是求出所有系统的失效率
用1去减是求出整个并联系统的失效率

模冗余系统

使R₁至R_m都做同样的计算，系统最终采用的结果通过表决器决定

混合系统

从整体上看，整个系统使串联的
因此可靠性只要讲三个系统的可靠性都分别求出来后相乘就能得到结果

差错控制

概念

前提条件：
采用1位长度的二进制编码。若A=1，B=0
采用2位长度的二进制编码。若A=11，B=00。
采用3位长度的二进制编码。若A=111，B=000。
检错：能够从接收到的编码中发现错误
假设传输的是1位长度的二进制编码A，在传输过程中发生错误1变为0，当接收方接收到位0时便会以为对方传输的时B，因为0与1都是合法的，因此时无法检错的。
假设传输的是2位长度的二进制编码A，在传输过程中发生错误11变为10，当接收方接收到位10时便会发现错误，因为10是非法的，但无法纠错。
纠错：能够从接收到的编码中发现错误并纠错
假设传输的是3位长度的二进制编码A，在传输过程中发生错误111变为110，当接收方接收到位110时便会发现错误，因为10是非法的，通常认为通信电路时比较靠谱的，不会出现多位的错误，因此会讲110与正确的编码进行对比，发现110与111更为接近，因此会讲110修正为111
码距：一个编码系统的码距使整个编码系统中任意（所有）两个码字的最小距离
例如采用1位长度的二进制编码。若A=1，B=0。
A与B之间至多只需要修改1位就能够表示对方，码距：1
A与B之间至多只需要修改2位就能够表示对方，码距：2

CRC

采用模2除法


模2除法采用的异或的算法，当两个位置的数值不相同，结果为1，若两个位置的数值相同结果为0


后面要加几个0的问题主要看多项式的最高次数，最高次数是几，就要添上几个0
多项式为x⁴+x³+x+1，由于没有x²，因此得到的码为11011
最终获得的将模2除法运行得到的结果替换到之前添加的那个位置即可
原本报文信息：110 0101 0101
最后获得的CRC编码：110 0101 0101 0011
得到的这个CRC编码110 0101 0101 0011对11011进行模2运算得到最后得结果为0就是正确的

海明校验码

校验码：分别在与2ⁿ次方位
校验位与信息位的关系（设校验位为x，信息位为y）2^x≥y+x+1

信息位：4位
要存放下4位的信息位，数据位数就要有3位校验码
校验码的位置分别在2⁰+2¹+2²（1，2，4）

在第7个位置有信息
7=2²+2¹+2⁰，说明在第0，1，2个校验码受到7这个信息位的影响
其它的类推求得

在将其进行异或操作，以r₂为例：
因为7，6，5这个三个都含有2²因此他们的数据对于第2个校验码都会产生影响
因此r₂会等于三个位置的数据进行异或得到的结果
按顺序两两进行异或求解
r₂=1⊕0⊕1=0
求解步骤：
1⊕0=1
再用1⊕1=0
最后结果为0
其它位计算方式一样

因此求得的编码为：1010101
假设接收方接收到的数据变为了1110101（假设只错一位）
我们就可以通过海明校验码去纠正错误的位数
①先提取出海明校验码：001
②通过信息位求出当前的海明校验码：111
③将两个海明校验码进行异或运算：110=6
④上一步得6证明是第6个位置得数据出现错误，只需要把第6个位置得数据取反即就是正确的

操作系统

五种管理：进程管理，存储管理，文件管理，作业管理，设备管理

运行态：需要的所有资源都已经准备就绪，且分配到cpu资源
就绪态：需要的所有资源都已经准备就绪
等待态：除cpu资源外还需要其它资源，例：与外设交互等

前驱图

与pv操作结合考察
前驱图要表达的是要完成的一系列活动的先后约束关系。

进程的同步与互斥

互斥（对应共享）

资源同一个时间只能有一个人使用

同步（对应异步）

速度快的要等速度慢的，相当于是两者必须同时完成工作

生产者消费者

单缓冲区：
互斥：市场只有一个位置，当生产者在生产东西时，就不允许消费去拿东西，当消费者进行消费时，生产者就不能胜场东西。
同步：当生产者生产了一个物品后必须等到消费者消费之后才能继续生产商品。
多缓冲区：
与单缓冲区的原理类似，不过就是在单缓冲区时，生产者生产一个商品后就不能继续生产商品了，而多缓冲区的生产者可以一次性生产多个商品。

PV操作

概念

信号量：主要用于PV操作的变量
P操作：信号量–
V操作：信号量++

例题

假设：b1与b2的pv操作不存在，收营员就会处于一直收费的状态，但是没有消费者提出收费的请求时，收营员的收费操作是无效的。所以首先应该由消费者提出收费请求。

因此：a1与b1应为一对PV操作，先由a1进行V操作唤醒b1，再由b1进行P操作，由此可知a1与b1中的信号量应该是相同的

在收营员进行收费结束后，需要对书进行消磁等操作，消费者才能够离开书店，因此要做如下操作

由收营员进程首先进行V操作去唤醒消费者进程，进而消费者进行P操作
因此答案为：A，C

将前驱图转为PV操作

将前驱图的每一个活动都转成相应的进程，然后在并发执行时，依然按照前驱图的约束关系先后执行
前驱图主要表达进行的这些活动的依赖关系


每一个箭头都表示一个PV操作所以都对应一个信号量，对应的规则是：从左到右，从上到下

每个箭头起点位置的V操作对应箭头末尾的P操作

答案：C，A，A

死锁问题

至少多少资源不会造成死锁

至少有多少系统资源不会发生死锁的题目：

假设有k个进程，每个进程需要x个资源
至少需要的系统资源个数=k(x-1)+1
即：先给所有的进程都分配他们所需的资源数-1个资源，再多加上一个系统资源，那么此时该系统资源给任何一个进程都能够使任意一个进程完成任务释放资源，继而不会造成死锁。

预防与避免

互斥：同一时刻只能有一个进程使用
保持和等待：所有进程都保持自己所拥有的资源并等待别人释放更多的资源
不可剥夺：系统不会剥夺已分配给进程的资源
环路等待：进程之间相互等待对方释放资源，形成一个闭环

银行家算法

一：计算出每个进程都分别还需要多少的资源数
二：计算出目前系统还剩余的资源数
三：检查剩余的资源数足够分配给哪个进程
四：每次一个进程执行结束后剩余的资源数=剩余的资源数+已分配的资源数量（因为进程执行结束后就会返回所有的资源）

存储管理

分区存储组织-分配算法

首次适应算法（FF）

实现：将所有空闲分区按照地址递增的次序链接，在申请内存分配时，从链首开始查找，将满足需求的第一个空闲分区分配给作业。
特点：该算法倾向于使用内存中低地址部分的空闲区，在高地址部分的空闲区很少被利用，从而保留了高地址部分的大空闲区。显然为以后到达的大作业分配大的内存空间创造了条件。
不足：低地址部分不断被划分，留下许多难以利用、很小的空闲区，而每次查找又都从低地址部分开始，会增加查找的开销。

最佳适应算法(BF):

实现：将所有空闲分区按照从小到大的顺序形成空闲分区链，在申请内存分配时，总是把满足需求的、最小的空闲分区分配给作业。
特点：综合性能最好，算法开销小，回收分区后一般不需要对空闲分区队列重新排序，会有更多的大分区被保留下来，更能满足大进程需求。
不足：算法开销大，回收分区后可能需要对空闲分区队列重新排序。会产生很多太小的，难以利用的碎片。

最差适应算法(WF)

实现：将所有的空闲分区按照从大到小的顺序形成空闲分区链，在申请内存分配时，总是把满足需求的、最大的空闲分区分配给作业。
特点：减少难以利用的小碎片。
不足：大分区容易被用完，不利于大进程，算法开销大，原因同上。

循环首次适应算法（NF）

实现：将所有空闲分区按照地址递增的次序链接，在申请内存分配时，总是从上次找到的空闲分区的下一个空闲分区开始查找，将满足需求的第一个空闲分区分配给作业。
特点：不用每次都从低地址开始检索，算法开销小，原因同首次适应算法。
不足：高地址的大分区也被用完。

段页式存储

页式存储

将用户程序等分成大小相等的页
将内存等分成对应大小的存储区
当程序到内存中运行时，只将程序要运行的页面调入，将程序调入内存时会产生一个页面用于存储用户程序块的存储位置
特点：提高内存的利用率
不足：增加系统开销，有可能产生抖动现象。

逻辑地址与物理地址

逻辑地址	物理地址
根据题目所给的页面大小与逻辑地址计算	相对应的块号/页帧号
根据题目所给的页面大小与逻辑地址计算	逻辑地址的页内号

将逻辑地址转为物理地址时，首先要将逻辑地址中的页号与页内号分开，页号的物理地址就是对应的内存块号，而逻辑的页内地址就是物理的页内地址。物理地址：块号+页内地址

（1）物理地址应为十六进制：
已知可得：
页面大小为4k=2¹²→业内地址12位
逻辑地址：5A29H→低位的12位为页内地址A29为业内地址，5为页号
页号5对应的页帧号为6，将求得的页帧号与页内地址连接起来即为物理地址：6A29H，因此选D
（2）应该淘汰的页号（）页面
状态位值为1的页面在内粗一年中
由图中的可看出0，1，2，5页在内存中
由访问位值为1可以看出，0，2，5刚被访问过
因此应该首先淘汰没有被访问过的页面，所以要淘汰的页号：1，因此选B

段式存储

段式是按照逻辑结构来划分的，段的大小可不一样。

段页式存储

快表

快表是放在cache存储器当中的，相对于页表和段表，它们是放在内存当中的，称之为慢表

页面置换算法

先进先出置换算法（FIFO）

从第二个置换的结果中我们发现，当内存的页面增多时，缺页的次数反倒增多了，因此可以判断它发生了抖动现象。

最近最少使用(LRU)

LRU与FIFO置换算法对比


题目已知：
没有使用快表，说明每次读取程序的块需要先在内存中查询表，查询表之后才能继续读取内存块，因此一个块需要进行两次内存的访问
共有6个块，因此会产生12次对内存的访问，因此选B
缺页中断次数：默认无论程序被分为几个块，都默认一次性调入
考试中指令会产生2次缺页中断，而指令只会产生一次缺页中断
有题目已知：swapA，B是16位的指令，A和B是两个16位操作数，而计算机是按字节编址的8位计算机系统，因此指令和两个操作数都跨两个页面。
而指令只会产生一次中断，而操作数跨几页就产生几次
因此可以看出共会产生5次缺页中断，因此选C

索引文件结构

索引节点一般为13个，编号由0~12
若索引节点中都是直接索引，假设每个索引节点可以存储4k的字节，那么13个所有节点最多只能存放4k×13=52k的数据
一级间接索引：该索引节点存放的是下一级索引的地址，假设每个地址占4个字节
4k÷4=1024，该索引节点对应的物理盘块存储1024个物理盘块的地址，对应的那些物理盘块才存索引内容
一级间接索引存储的容量空间：4k×1024

文件和树型目录结构

绝对路径最前面有一个’/'符号

空闲存储空间的管理

位示图：
1表示的区域已被占用
0表示的区域还是空闲

例题

(1)
由于物理号是从0开始计算的，因此：(4195+1)÷32=131.125
4195+1：这是因为它是从0开始编号的，因此编号为4195的物理块，实际上是第4196个物理块。
由于字是从1开始计算的，取整为：132
因此答案为132，选择D
(2)
位置是从第0个位置开始计算
因此选择B
细节：第几个字的下标是从1开始计算的，多少位的下标是从0开始计算的。

设备管理

数据传输控制方式

程序控制方式（程序查询方式）：最低级也是CPU介入最多的一种方式。
程序中断方式：当外设完成相应数据的处理，它会发一个中断指令，系统收到后就会进行下一步的处理。
DMA（直接存储控制方式）：有专门的控制器，只要是外设与内存的数据交换过程中这个控制器会进行管控，CPU只需要在开始的时候进行介入，整个过程由DMA控制器进行监管，完成后再由CPU进行接管。

虚拟设备与SPOOLING技术

spooling技术的核心就是开辟了缓冲区，处理外设的低速与内部系统高效之间的瓶颈差异。

微内核操作系统

数据库系统

数据库模式（三级模式-两级映射）

三级模式：
外模式：视图
概念模式：表
内模式：数据的存储方式
两级映射：
外模式-概念模式映射：当表发生变化时，我们只需要改映射，就能看到相应的数据，而不需要修改应用程序。
概念模式-内模式映射：当存储结构发生改变时只需要修改映射关系。

数据库设计

数据库设计准确来说是从概念结构设计算起

ER模型

正方形表示实体
椭圆形表示实体的属性
菱形表示实体之间的联系

1：1联系：这种联系既可以放在与之关联的任意一个实体上。
1：n联系：这种联系放在n的实体的这一边，作为它的一个属性。
m：n联系：这种联系就需要单独新建一张表来表示两个实体之间的联系。

首先：A、B、C三个实体要相对应的转成3张表
联系：m：n：p这个联系只需要转为一张表即可
解析：即时有多张表之间有多个关系，这个关系也只需要转为1张表即可，不需要转为多张表
因此答案为4，选C

关系代数与元组演算

并：两个表中有的数据都显示出来，且如果在两个表中都有该数据，也只显示一次。
交：两个表中都有的数据才会被筛选出来。

差集（结果集）：我有的对方没有，将两者的公共部分去除

笛卡尔积：
结果集的属性数是参与操作的两个关系的属性数之和
记录数是两个关系的记录数之积
投影：对列进行操作，只有在符合筛选条件中条件的列才会被显示出来
选择：对行进行操作，只有在符合筛选条件中条件的行才会被显示出来

在进行投影或选择操作时，有时用的时属性名，有时用的是属性编码代号
例如图中的π_Sno,Sname也可写成π_1,2，选择也是如此

连接：两个关系中，相同的字段只会显示一次，且会将两个关系中的不同字段都显示一遍。
在连接过程中普遍都会有连接的条件，如S1.Sno=S2.Sno
如果没有连接条件则是自然连接
自然连接：将相同的字段进行比较，筛选出相同的字段进行连接

规范化理论

函数依赖

部分函数依赖：属性A与属性B一起构成的组合主键时，若A就能够唯一确定一个属性C此时就称为部分函数依赖
传递函数依赖：当属性A可以确定属性B而属性B又可以确定属性C时，则可推出属性A能够唯一确定一个属性C（此处有个条件B不能够为A）。

规范化的价值

键

求解候选键

例题

1、找到入度为0的节点，由题目可得度为0的节点是A1
2、从入度为0的节点尝试遍历所有的节点，如果能够遍历完所有的节点，则该节点便是候选关键字
由已知可得A1→A2，A2→A3，A2→A4，从A1出发即可可以遍历完所有的节点
因此A1是候选关键字，选择A


答案为ABCD


1、没有入度为0的节点尝试找出中间节点，指既有入度也有出度的节点
2、由图中已知可以看出，节点A、B都是中间节点
3、从节点A或B出发都能够遍历完所有的节点
因此节点A或B都能够称为候选关键字，所以答案是A和B，选B

范式

范式越高数据粒度越小，因此只会要求达到3NF即可


当发现某个非主属性对主键部分依赖时就要将其拆分出去作为一个单独的表进行处理。
若候选键是单属性的，则一定满足第二范式。



1、写出所有的候选键
ST，SJ都可以作为候选键
2、SJ→T，T→J
从定义中：R属于BCNF当且仅当其F中每个依赖的决定因素必须包含R的某个候选码。
通俗说就是说决定右边属性的这个左边的决定因素必须是候选码。
SJ→T，SJ是候选码所以没有问题
T→J，T不是候选码
因此这个无法满足BCNF范式。

例题

1、
部门号可以作为主键决定所有的属性，只需要一个属性就能作为主键，不存在部分依赖所以一定满足第二范式
因此不满足第三范式的原因只能是消除部份依赖而没有消除传递依赖
2、
观察图4，我们可以得出，图4是需要职工号和部门名的，因此需要在图1与图3之间建立联系，根据之前在ER模型中所学的内容，我们需要将1：n联系将该属性放在n的那个表中，而部门表与员工表的关系为1个部门对应n个员工，因此要在员工表中新增一个部门号属性。
3、
观察图4我们可以发现要得到图4的结果，
其中月销售这个属性我们需要数量与日期构成，因此可以排除B、D
职工号与部门号在员工表中已经新增属性将两者连接产生关系了，因此排除C
选CDA

模式分解

保持函数依赖

有一个关系R(A,B,C)，含有函数依赖，A→B，B→C
分解为关系R₁(A,B)，R₂(B,C)
则依然函数函数依赖，A→B，B→C，即保持函数依赖
若分解为R₁(A,B)，R₂(A,C)，不能够找到B→C
即没有保持函数依赖

无损分解例题

局限性较强只适用于一分为二的情况

并发控制

原子性：要么全做，要么全不做
一致性：事物执行后跟执行前的状态是保持一致的
隔离性：事物之间是隔离的，互不影响
持续性：事物执行后的影响是持续的

产生的问题

封锁协议

S：读锁，加上了读锁之后可以再加上读锁但不能加写锁。
X：写锁，加上了写锁之后就不能够再加任何的锁了，读锁写锁都不行。

数据库完整性约束

实体完整性约束：约束主键，主键不能够为空也不能够重复。
参照完整性约束：约束外键，要求填入的数据必须是参照的那个表主键的值，可为空。
用户自定义完整性约束：用户自己设定的要求。
提高数据可靠性。
触发器：可编写脚本来保障数据库的数据安全。

数据库安全

用户标识和鉴定：身份认证，用户需要输入自己的账号和口令进行验证。
存取控制：对用户的权限进行授权。
密码存储和传输：在远程传输数据过程中可以加密进行传输。
视图的保护：根据不同权限的用户分配不同的权限。
审计：以日志的方式记录用户对数据库的操作，然后可以根据日志对用户的操作进行分析。

数据备份

冷备份：以文件级别进行备份，无法精确到表。
热备份：相比于冷备份更加灵活高效，能够精确到表的级别。
以数据库的量进行区分的备份方式：

数据库故障与恢复

分布式数据库

数据仓库

抽取：从不同的数据源将需要的数据抽取出来。
清理：抽取出来的数据也许会存在格式不同等等其它问题，此时就会需要清理工作。
装载：将抽取出来的数据装载到数据仓库中去。
刷新：定期刷新就是往里面添加一些数据。
数据集市：部门级的数据仓库。
OLAP服务器：联机分析服务器，专做分析处理工作。

数据挖掘

反规范化

牺牲空间以及规范化的程度换取时间，提高查询的效率。


重新组表：依据查询效率的原则进行重新组表。
分割表：从查询的效率出发，进行垂直分隔或水平分割。

大数据

对海量数据进行处理的技术。

计算机网络

OSI/RM七层模型

三层交换机：加上了路由的交换机。
网桥：连接两个同类型网络的设备。
交换机：多端口的网桥，用于连接多个设备。
网卡MAC就是帧地址。
二进制数据：高电平与低电平。

该题考查局域网与广域网的差别。
局域网工作在七层模型的最下面两层（物理层与数据链路层），典型设备：交换机。
由题可知：不能够通过的路径说明是跨越了网络的，因为在局域网中只有同属于一个局域网中的设备才能够进行通信。
A：P和Q，这两个计算机是用网桥连接的，而网桥是属于数据链路层的设备，因此这个路径是能够通过的。
B：P和S，这两计算机是用的路由器连接，路由器是属于网络层的设备，因此该路径无法通过。
C：Q和R，这两计算机是集线器连接，集线器是物理层设备，该路径可通过。
D：S和T，这两计算机时交换机连接，交换机是数据链路层设备，该路径可通过。
选B

网络技术标准与协议

ICMP：因特网控制协议。采用Ping命令测试网络的就是属于该协议
ARP：IP地址转为MAC地址
RARP：MAC地址转IP地址
HTTP：超文本传输协议
FTP：文件传输协议
Telnet：远程登陆协议
SMTP：邮件传输协议（发）
POP3：邮件传输协议（收）
DHCP：动态分配IP地址
TFTP：简单文件传输协议
SNMP：简单网络管理协议
DNS：域名解析系统

TCP

TCP：是有连接的，可靠的通信协议，进行信息传输时会有反馈信息。
TCP进行连接之前会进行的三次握手。

DHCP

特殊的ip地址：
169.264.x.x和0.0.0.0：表示没有被分配到ip地址或是DHCP服务出故障。

DNS协议

迭代查询

负责将DNS地址与域名的转换

迭代查询：上层服务器跟你说你应该去找谁，然后你去找结果。

递归查询

递归查询：上层服务器会层层的查询，直到查询到结果后再返回。

DNS解析例题

从图中可以看出本地域名服务器向根域名服务器发出请求时，根域名服务器直接就回复了本地域名服务器，而不是向中介域名服务器区询问，因此这种方式迭代查询。
本地域名服务器向中介域名服务器发出请求时，中介域名到授权域名服务器中去查询，因此这种方式是递归查询，综上选择A
选A

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

在办公室一般采用的是星系的拓扑结构，中间节点是交换机。

网络规划与设计

逻辑网络设计

核心：IP地址方案，安全方案

物理网络设计

分层设计

顶层是核心层，底层是接入层，中间层是汇聚层，
顶层与底层都只有一个层次，中间层可有多个层次
底层只处理终端的接入，顶层一般进行数据的高速转发
分层思想设计时一般要由下而上的看，根据底层接入的情况等，决定顶层应该达到什么样的性能指标。

IP地址

特殊的地址：
全为0：网络地址
全为1：广播地址

类别	网络号范围	网络号位数	主机号位数	可容纳的主机数
A类地	0-127	8（第一位为0）	24	224-2
B类地	128-191	16（第二位为0）	16	216-2
C类地	192-224	24（第三位为0）	8	216-2

网路号范围计算：
以A类地址举例：因第一位为0，且A类地址只有8位网络号，因此除去第一位。剩下位置全为0为最低的网络号，全为1为最高的网络号，就能够计算出A类网络的范围：0~127。
B类：第一位固定为1，第二位固定为0，然后接着采用与A类地址相同方式就能计算出B类网络号的范围。
主机数：2的该地址主机号位数的次方。

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

/24表示的是该地址的网路号是24位。

子网划分

划分子网就是将主机号拿来当作网络号。
子网数=2ⁿ(n就是取了多少个主机号)
题目要求要划分27个子网，2ⁿ≥27，求得结果是5，因此要拿5个主机号充当网络号。
而B类地址本身就有16个位数是网络号，因此进行划分27个子网后，该地址的网络号变成了21位。

前面的16位是网络号，后面的5个1是子网号，后面0的部分是主机号。
转为十进制：


由题已知每个子网内需要有主机700台
根据可容纳的主机数的公式计算可得出，2ⁿ≥700，求得n=10，因此主机号要10位，网络号要22位。

综上求得子网掩码为：1111 1111 1111 1111 1111 1100 0000 0000。

转为十进制：

128.14.32.0的最大地址为128.14.47.255是因为将器网络号化为二进制时得到的是
1000 0000 0000 1110 0010 0000 0000 0000
子网掩码是20位
1000 0000 0000 1110 0010 0000 0000 0000
1111 1111 1111 1111 1111
将剩下的主机位全化为1即可求得
1000 0000 0000 1110 0010 1111 1111 1111
128.14.47.255

由题目已知条件可得：
有20位网路号，12位主机号，C类网路有24为网络号，因此网络可以从主机号中拿出4为当作子网号，子网号的数量=2⁴，因此可得该网络可以被划分为16个C类子网。

特殊含义的IP地址

HTML

无线网

网络接入技术

TD-SCDMA：名义上是我国研发的标准，但是由于功耗大，性能低，使用的很小众。
LTE-Advanced：分为TDD，FDD
TDD由TD-SCDMA发展而来
FDD由WCDMA发展而来
在4G时代，由于在3G时代TD-SCDMA国家的大力推广，TDD与FDD的差距较小。

IPV6

信息系统安全属性

对称加密

非堆成加密复杂，如果用于加密长内容的数据耗时将会很长，所以一般采用对称密钥加密内容，非对称密钥加密对称密钥。

信息摘要

信息摘要是信息的特征值，如果信息变化，那么信息摘要也会跟着变化。
两个知识点：
信息摘要采用的加密算法：单项散列函数（单项Hash函数），我能够通过信息生成摘要，但不能够通过摘要还原信息。

数字签名

当A给B发信息时，A会使用自己的私钥进行加密，而B会使用A的公钥进行解密，当B使用A的公钥成功将信息解密之后就证明该信息是由A发出的，因为A的公钥才能够解开A私钥加密的信息，而A的私钥只有A自己才有，这就算是一个数字签名。
A采用私钥进行加密的过程称之为数字签名。
B采用A的公钥进行解密称之为数字签名的验证过程。

数字信封与PGP

例题-设计邮件加密系统

邮件内容可达500MB-对称加密
发送者不可抵赖-数字签名
第三方无法篡改-信息摘要

网络安全

PGP协议：既可以加密文件，也可以加密邮件。
网络层：最常见的就是防火墙。
数据链路层：协议，在发送信息之前对信息进行加密，或是直接对链路进行加密。
物理层：以物理的方式来保障信息安全。
考试一般会问哪个协议是属于哪个层次的。

网络威胁与攻击

业务流分析：长期监听，且有统计分析。
窃听：就是窃听，没有分析。（简单粗暴的记一下吧，说不定考试就用上了）

旁路控制：攻击者利用系统的缺陷进行攻击。

防火墙

网络级防火墙：工作层次较低，效率较高。网络级防火墙只看ip头，就看这个数据是从哪个ip段发出的，进行筛选过滤。
应用级防火墙：工作层次较高，效率较低。应用级防火墙不仅看ip头，还看里面的数据，会对数据进行抽样检查看看是否有病毒存在。
屏蔽子网（安全性最高）：在防火墙与内部网络之间还有一个屏蔽子网（隔离区），该区域一般放对外提供服务的服务器（如web服务器，邮件服务器等），要进入到内部网路还需要经过一道防火墙，较大的提高了安全性。

数据结构

数组

稀疏矩阵

稀疏矩阵就是指一个矩阵中存放的数据大量都是0。

代入法：
从题目中我们可以得到数组M的下标是从1开始的，所以A_0,0应该存放在M[1]中
将0，0带入下面四个选项中之后能够发现，有AD能够符合条件
再挑选一个带入，例如A_1,1，将1，1带入AD后需要得到3（因为A_1,1是数组中的第三个元素，下标为3），发现只有A符合条件，因此选A。

数据逻辑结构

广义的图：包含树和线性结构
广义的树：包含线性结构

线性表

概念

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

顺序表

开辟一片连续的空间，顺次的将数据存储进去（一维数组）

链表

顺序存储与链式存储对比

队列与栈

为了判断循环队列是否满了的情况下，一般在循环队列中会少存储一个元素，通过公式进行计算就能够判断循环队列是否已经存储满了。

分析：
要得输出序列就是要在队列中获得对应的队列然后根据题目的要求进行输出。
A选项：无论是从左方进入队列还是右方进入队列，都能够获得这样的输出队列，因此是成立的。
其余的选项也是一样的做法，经过排查能够发现是选项D获取不到
要获得D的输出序列：首先从右方进入e1，然后若从左方进入e2，获得e2，e1.，若从右方进入则会获得e1，e2，无论如何都获取不到e3，e1的序列，因此，无法获取到选项D的输出序列。
选择D

广义表

长度：元素的个数
深度：嵌套的层数
表头：第一个元素
表尾：除了第一个元素之外的所有元素

树与二叉树

节点的度：指节点的孩子节点
例如1号节点，它有两个子节点，因此1号节点的度为2
3号节点只有一个孩子，因为3号节点的度为1
树的度：所有节点中最高的度
叶子节点：度为0的节点
分支结点：有父结点和多个子结点的结点
内部节点：除根结点和子结点的其他结点

满二叉树与完全二叉树

树与二叉树-二叉树遍历

前序遍历：根左右，12457836
中序遍历：左根右，42785136
后续遍历：左右根，48752631
层次遍历：就是一层一层从左到右遍历过去。12345678

反向构造二叉树

推算规则：
前中：根据前序遍历找出根节点，在根据中序遍历找出左子树与右子树，在根据前序找出子树的根节点，然后继续分出左右子树。
后中：根据前后遍历找出根节点，在根据中序遍历找出左子树与右子树，在根据后序找出子树的根节点，然后继续分出左右子树。
前后：不知道中序遍历的情况下是无法还原树的

树转二叉树

连线规则：只保留第一个孩子节点的连接，其它的孩子节点之间相互连接。

查找（排序）二叉树

左子树所有的节点都小于根节点，右子树所有的节点都大于根节点

最优二叉树（哈夫曼树）

用于压缩算法，属于无损压缩

节点的路径长度：从根出发到改节点会经过的路径数。
权：节点上标注的数字。
节点的带权路径长度：节点的路径长度×节点的权值。
树的带权路径长度：树上所有的叶子节点的带权路径相加。
最优二叉树就是找到能够构成最短带权路径长度的二叉树。
因为所有的中间节点都是构成哈夫曼树时产生的节点，所以不能计算进去。

①：找到权值最小的两个节点，它们的权值和为它们的根节点。构成一颗小树。

②然后剩下的权值为7，8，8，11，14，23，29
再从剩余的权值中找出最小的两个，它们的权值之和作为它们的根节点，再继续构成树，发现节点的权值相同时随便选择一个节点来构成树。经过比较后发现时7与8，那么就用这两节点再构成树。

后面依次类推，最后构成的最优二叉树，最优二叉树不一定只存在一颗。但是它们的最短的带权路劲长度一定的都是相等的。最短带权路径时唯一的。

线索二叉树

为什么会有线索二叉树：树种很多叶子节点的左子树与右子树是空的，资源浪费。为了将资源利用，使二叉树更方便与遍历，因此提出了线索二叉树。
前序线索二叉树：左子树指向自己在前序遍历的前驱节点，右子树指向自己在前序遍历的后驱节点。

平衡二叉树

平衡二叉树与排序二叉树的定义差不多，差别是平衡二叉树是唯一的，且平衡二叉树的查询效率对于普通的排序二叉树来效率更高。

左右子树的深度：看它的左边的子树最深到第几层，深度就是几

例如上图的节点39，它左子树最深到3层那它的左子树深度就为3，它没有右子树，因此它的右子树的深度就为0。
那么它左右子树的深度就相差3。

图

上面的两幅图都属于完全图。
完全图：该连接的边都连满了，没有再其它的边都能连接的。
在无向图中，只需要连接一条边，两个点就能够相互到达，而在有向图中，必须要两条线指向对方，双方才能够相互访问。

邻接矩阵

当图为无向图时，邻接矩阵的存储的0与1时成对角线对称的，因此在存储时可以只存储上三角或下三角节约存储空间。

邻接表

首先有一个表存储了所有的节点，然后该节点能够到达哪些节点用链表的方式存储。
例如节点V1，从图中可以看出它能够到达点V2，V4，V6，距离分别为6，1，50
所以在邻接表中的V1链表中存储了

图的遍历

深度优先：优先先访问孩子节点，再访问兄弟节点（前序遍历）
广度优先：优先访问兄弟节点，再访问孩子节点（层次遍历）

在做这类题时最好是先根据邻接表将图画出来，在做遍历时有地方参考查错。
深度优先：V0→V4→V6→V7→V3（到这里，这条深度已经走完，回退到V4）→V1→V2→V5
广度优先：V0→V4→V3→V1（先将V0所有的邻接节点都访问结束，然后在访问V4节点）→V6→V2→V7→V5

拓扑排序

用一个序列表达哪些事件可以先执行，哪些事件需要后执行。

由于0没有入度，说明没有任何一个事件能够约束它，所以所有可行的拓扑序列都必须它先执行。
执行0之后可以执行1或者执行2都可以。
接着必须使事物1与事物2都执行完毕之后才能够继续向下执行，因为事物4必须等到1与2都执行完成后才能执行，而事物3必须等待事物4执行后。后面的节点就是依照这种方式继续排拓扑序列即可。
上图的拓扑序列还有很多。

图的最小生成树-普利姆算法

将图中留下的边能够遍历整张图，它们的权值相加最小。

将所有的节点分为红点集与蓝点集
一开始红点集中没有节点，所有的节点都属于蓝点集。
首先任选一个点加入红点集。
例如将点A加入红点集，剩余的点就是蓝点集，从所有的红点集中选择一条权值最短的路径，然后将路径到达的点加入红点集

不难看出权值最小的路径是到点B的100，然后接续从能够到达节点的所有的路劲中找到最短的路径。

由上图不难看出此时最短的路径是点A到点E的路径，权值为200，剩下的节点也是按照类似的方法将所有的节点利用权值最短的路劲相连接。
最后就能够的到最小路径。

在构成最小路劲时要注意一定不能够构成环路。
红点集只能与蓝点集中的节点相连而不能与红点集中的节点相连。

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

将图中留下的边能够遍历整张图，它们的权值相加最小。

克鲁斯卡尔算法就是找到权值最短的边，然后将它们连接起来，同样的是要注意一定不能形成环路。
从上图中，在所有的边中可以找到权值最短的边为100，所以先将点AB连接
剩余边权值较小的为200，因此可以将点AE与点DF连接
权值：250，将点AE连接
权值：300，权值300的边有一对是点BF与CD，若连接BF则会产生回路，因此要选择连接CD权值为300的那条边，剩下的按照这样的方法找完所有的边。
就能够得到最小生成树。

图与树的区别

树与图最大的区别就是树不会形成环路而图能够形成环路，例如树有n个节点，那么它最多可以有n-1条边，如果该树有n条边，那它就会形成环路，那么此时它就是图。

算法

算法特性

算法复杂度

所有能以常数表达的复杂度都是以O(1)表示。
假设有一层循环，循环次数不能够确定，那个它的事件复杂度就为O(n)，若是双重循环，那么此时的复杂度为O(n²)，三重循环就依次类推。

一个知乎链接，讲的挺好的。

查找

顺序查找

查找长度：
最好的情况就是只查找一次就找到了需要的元素，最坏的情况就是找到最后一个才找到需要的元素，这就构成一个等差队列，而等差队列的平均值的计算公式：(首项+末项)/2
时间复杂度：O(n)

二分查找

使用二分查找的前提要求是序列必须是有序的，例如排序树那样的序列，若序列是杂乱无章的，那么是无法使用二分查找的。

细节：
在确定中间的位置时，如果有小数部分，则是直接去掉小数部分，而并非四舍五入或是进行其它方式的运算。
例如：要计算从下标1到下标12中间的那个值，那么(1+12)/2=6.5，则取整得到6
再次进行二分查找时，
若要查找的值在左边则最大的下标的位置，上一次计算的值-1
若要查找的值在右边则最大的下标的位置，上一次计算的值+1
例如：上次计算后获得的下标为6，该处值为18，但是我们要查找的数值为17，因此应该是1+5/2计算两者的中间的数值，因为下标为6的元素已经经过计算了，它不需要在计算一次。

散列表查找

以空间换取时间的方式

线性探测法：
在例题中，关键码3与8根据散列函数计算存储的位置，在计算8的存储位置时会发现位置已经被3占用了，因此8会存储到3的下一个位置上。
在存储12与17是，在计算17时，会发现它的位置已经被12占用了，下一个位置也有数值了，那么它就会一直往下找，直到找到一个空的位置存储。
较可能的避免冲突（冲突不一定能完全避免，但可尽可能的避免冲突）：
将存储的空间设置的足够大/多设置几个散列函数，当采用一个散列函数计算发现冲突后换一个散列函数计算。

排序

稳定排序：例如上图，在需要排序的队列中有两个21，一个是红色的21一个是黑色的21，在经过排序后，黑色的21与红色的21的顺序依然不会改变。
不稳定排序则于稳定排序相反。
内排序：只涉及到内部的存储空间。
外排序：涉及到外部的存储空间。

插入排序

希尔排序

例如：取一个增量d₁=5，那么数组中所有的数据隔5个作为一组（1，6），然后俩俩进行比较，小的往前方，大的往后放。每一组都比较完毕后，将增量d₁/2作为增量d₂，然后与步骤一相同再做一次，直到增量d变为1，即完成排序。

直接选择排序

每一次都找到未排序中最小的元素，然后将这个最小的元素放到第一个位置上。

堆排序

简单来说：建立堆，取走堆顶元素，剩下的元素再建堆，再取走堆顶元素，以此类推。（要从小到达排序就建立大顶堆，要从大到小排序就建立小顶堆）
以下构造大顶堆

①找到树种最后一个非叶子节点，与它的孩子节点比，因为是构造大顶堆，所以若自己比孩子节点小，那么就要把较大的那个节点与自己交换。
然后调整完之后调整下一个非叶子节点，直到所有的非叶子节点都调整好之后就完成了树的建造。（有时交换不止一次，要交换多次才能够满足要求）

调整堆结构：
①取走第堆顶元素
②将堆的最后一个节点放在堆顶
③进行调整重新构造大顶堆（这边是从大大小）至于怎么实现我也忘记了，暑假玩玩玩，结果连就没时间做了。。。
④取走堆顶元素
⑤重复以上步骤，最终取走堆上的所有元素完成排序。

冒泡元素

①从最底下开始比较，最先比较最后两个元素。
②将较小的元素向上放置，然后再将该元素与自己上一个元素比较
③重复步骤②
④每完成一次全部的排序就会从上至下确定一个元素的位置。
第一遍全部比较之后能够确定第一个元素的，第二遍 确定第二个。。
注意：
冒泡排序要注意实时变化的下标的位置

快速排序

每一次排序都会将需要排序的数据一分为二。

归并排序

进行归并排序时，kj分别取指向57与52进行比较，52较小则就把52放入到一个新的数组中，然后指向52的j，进行+1操作，变成57与59比较，然后将57放入52的下一个位置上，指向57的k，进行+1操作依次类推。
对两个有序表进行合并操作，合并方法为取两个有序表最小元素进行比较，取走两个最小元素中较小一个，以此循环

基数排序

基数排序就是将一个数值拆分为多个关键字，然后以关键字进行排序，最终得到有序序列。

时间复杂度、空间复杂度、稳定性

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

编译过程

文法定义

语法推导树

在文法G=({a,b},{S,A},S,P)中
ab是终结符（因为它们无法再推出其他的语法）
SA是非终结符（它们可以推出其它的语法）
S：起始符
P：产生式
因为S→aAS|a表示S→aAS，S→a，因此有后面的语法树

有限自动机

双圈的f表示结束
考试一般就是考通过图能不能够到达某一个点，且指定路上通过指定的状体连起来的串。

有限自动机例题

选项A表示，从A开始能不能输入4个0到达终态C，从A走0到B，然后B本身走0可以循环到自己还是B，但是最后到C一定要过线路1，因此选项A无法满足
选项C，从A开始过0到B，B再过1到C，C再过0到B，B再过1到C，因此获得了0101，所以C成立
选C

正规式（重）

正规式是有限自动机的另一种表达形式


（1）
|：或的关系
*：循环，例如(a|b)，则可以表示空，也能够表示a,aa,ab,b,bb,bb只要是a和b的循环，或者是a或b的循环都可以
题目中A选项：ababab，有G[S]中，S→aA|bB可推出
aA
由A→bS|b，推：abS
由S→aA|bB，推：abaA
由A→bS|b，推：ababS
由S→aA|bB，推：ababaA
由A→bS|b，推：ababab
其余选项一样的做法即能够推出无法识别的D
（2）
选择一项能够表达出ABC的正规式
A：只要是ab组成的式子它都能够表达，因此它的范围要比 G[S]表示的范围要大得多，因此排除A
B：它能够表达的都是abab，要么一个ab要么两个ab，不能够表达baba的这种形式，因此排除
C：它既能够表达ab也能够表示ba，因此abc的三个选项它都能够表示出，因此暂时考虑
D：表示的是n个ab+n个ba，不能够交替出现，因此也排除D
选择C

表达式（重）

根据表达式我们要构造一棵树出来
要注意括号的位置，首先构造(a-b)与(c+5)

在构造树的时候要注意，不要把括号一起构造进去
举例：当表达式没有括号时的构造树
a-bc+5，按照计算法则，bc优先进行计算，所以要将bc优先构造出来

然后按照计算规则是a-bc

最后要计算a-b*c+5

这就是最后构造出来的树

传值与传址（重）

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

法律法规

计算机软件保护条例（软件著作权）

知识产权

保护期限

知识产权人确定

侵权判断

标准化

标准化分类

多媒体基础

音频

图像

亮度：画面的明亮度，当亮度高时，画面变亮，当亮度低时画面变暗。
色调（红，绿）：指画面色调的差异，有些画面看起来偏红，有些画面看起来偏绿。
饱和度：色彩的艳丽程度，饱和度低时，色彩显得灰灰的较不鲜艳，饱和度高时，色彩较为鲜艳。

彩色空间

电脑显示器采用的一般为RGB空间
YUV：在彩色电视出现之后为了兼容黑白电视接收信号，进而产生的一种彩色空间，该彩色空间中有一个灰度值，黑白电视只需要接收灰度值就可以， 彩色电视只需要将另外两个量偏移进来就能够完成彩色的显示。
电视上还能够使用的彩色空间：YIQ，YCBCR（由YUV变化来）
CMY：印刷领域使用
CMYK：因为黑色是由印刷的三原色叠加相减形成的，但这样形成的黑色常不够黑，且成本过于高昂，因此后面多衍生出了K，但是这种就足够表示黑色，不需要其它的颜色进行叠加相减。
印刷三原色使用的是吸收的方式显示出对应的颜色，例如你能够看到印刷出来的黄色，是因为这种颜料吸收了除了黄色的其它颜色，所以你能够看到黄颜色。
而光的三原色是通过叠加的方式来显示多种颜色的，例如白色就是绿红蓝三种颜色叠加形成的。

媒体

多媒体相关计算问题

图像容量计算

先计算出每张照片需要的bit位
然后计算出每张照片需要的MB
最后将总的存储空间除去每张照片所需的MB位数就能够求出存储器最多可以存储几张照片。

音频容量计算

视频容量计算

k：1000（传输时用），K：1024（存储时用）在计算时要多注意单位的区别。

常见的多媒体标准

数据压缩基础

有冗余才能够压缩

空间冗余：有一大部分都是相同的。
时间冗余：视频中上一帧与下一帧没有变化的。
视觉冗余：找到视觉的盲区，当人眼区分不出这么多种颜色时就将这些颜色都压缩成同一种颜色。
信息熵冗余：利用合理的编码降低冗余。
结构冗余：强调某个结构有很多冗余的部分。
知识冗余：可以通过知识分析得到的信息。

有损压缩与无损压缩

无损压缩：熵编码法
有损压缩：压缩比更高，熵压缩码

软件工程

开发模型

瀑布模型

瀑布模型是属于结构化方法中的模型，一般用于结构化开发
适用于瀑布模型开发的场景：需求明确，二次开发
瀑布模型最大的不足就是无法把握需求分析

其它经典模型

原型：构造一个简易的系统，针对于需求不明确的情况。

增量模型

螺旋模型

风险分析是螺旋模型最显著的特点

V模型

V模型强调测试的重要性，强调测试要贯穿开发的始终
在做需求分析同时验收测试与系统测试的测试计划
概要设计-集成测试
详细设计-单元测试

喷泉模型

喷泉模型时面向对象的开发模型

快速开发模型

特点：能够快速的构建应用系统。

构建组装模型（CBSD）

敏捷开发方法

信息系统开发方法

需求分类

结构化设计

基本原则

内聚与耦合

非直接耦合的耦合程度是最低的。
内容耦合的耦合程度是最高的。

系统结构/模块结构

变换控制要主要掌握，传入是和传出都是都是只有一个箭头指出或指入，而变换是有双向箭头可以进行变化的。

软件测试

测试原型与类型

回归测试：修改了一段代码之后不仅要测试修改之后的那段代码还要测试修改之前的代码，看看会不会发生其它的bug。
尚未发现的错误数量与该程序已发现错误数成正比：假设有AB两个程序，A程序中发现了50个bug，B程序中发现100个bug，那么在程序修改之后依然要重点测试B程序，因为程序B本来的bug就比较多，那就说明原程序的漏洞较大，可能还有些隐蔽的bug暂时还没有被发现，因此需要主要测试。而程序A测试出的bug较少说明原程序写的较为完善，因此可以减少测试。

动态测试：由计算机进行
静态测试：由人工进行

测试用例

黑盒测试：不知道其内部结构，只知道程序的功能是什么，输入的参数，输出结果，在衡量结果是否正确时判断输出的结果跟输入的参数需要的结果是否一致。
白盒测试：能够看到程序具体的结构。
理论上：白盒测试能够做的比黑盒测试更加完善。

黑盒测试

等价类划分：将测试的数据进行分类，在每一个的分类中都选择一个出来进行测试。
边界值分析：注重边界值

边界值求解

当给一个区间求取边界值时：
在该区间的两个端点，以及略小于端点的值与略大于端点的值。

两个端点：0与150
略小于端点：-1
略大于端点：151
错误推测：根据经验或是灵感进行测试。
因果图：由结果或者原因对原因进行推测。

白盒测试

逻辑覆盖测试（了解）

语句覆盖：程序中所有的语句都要被执行过一遍。（层次最低）
判定覆盖：所有的判定的真假分支都要被执行。
条件覆盖：一个判定可能包含有多个条件，而条件覆盖就要令所有可能出现的条件都出现。
路径覆盖：所有的路径，可能出现的情况全部覆盖。

测试阶段

单元测试：测试局部的功能与数据的数据结构、数据模块的相关功能。
集成测试：将各个模块组装起来测试，此时测试的是模块之间的衔接，模块的接口，模块之间相互配合工作会不会有问题。
一次性组装：一次性将所有的模块组装起来进行测试。
增量式组装：先组装几个模块测试一次，然后再组装几个模块再测试一次，每次模块组装都要进行测试，相对于一次性组装工作量更大，但是也更加稳妥。
确认测试：确认需求。

系统测试

偏向于压力，性能测试。

负载测试

强调不同负载之下的性能表现。
举例：在并发一千时，响应时间是多少。在并发两千时，响应时间又会是多少。

强度测试

在系统发生异常的情况下，系统资源不是正常分配的情况下，能否正常运行。

容量测试

本身设置的是一万人可以同时访问，那么在十万人同时访问时，系统能不能正常运行。

McCabe复杂度（考的可能性高）

公式中：m：边。n：点
若在考试中不记得或记混了可以使用以下的方式帮助区分一下。
构造一附最简单的流程图

该流程图有3个点2条线，且只有一条路径，所以环路复杂度应该为1。那么公式计算出的环路复杂度也应该为1，因此只需要把点和线带入公式计算一下就能够分清m与n哪个是点哪个是边了。

图转为界限图（抽象节点问题）

类似于这种分叉中，原程序中没有相应的语句，在转为界限图时既可它们抽象为一个节点也可以不抽象为一个节点，因为结果都是相同的。
例如将它们都抽象为节点了，虽然节点增加了，但边也同时增加了。
若不抽象为节点，那么节点不增加，边也没有增加，所以是一样的。

系统运行与维护

确保系统能够正常运行。


易分析性：在维护时代码应该是简单易懂的。
易改变性：涉及到耦合性的问题，代码修改起来难易程度。
易测试性：做了些相关调整后，做回归测试时方不方便。
改正性维护：当程序运行时出现bug，修复了该bug就称为改正性维护。
适应性维护：当程序更换了运行环境（软件或硬件），或者是数据类型，修改修改程序来适应，进而正常运行。
完善性维护：需求发生改变需要扩充功能或是改变功能。
预防性维护：现在修复以后可能会出现的bug（千年虫问题）

软件过程改进-CMMI

由CMM发展而来的。
CMM：能力成熟度模型。是指软件开发的成熟度，指开发软件承包商改善软件指标的能力

混乱级：默认在没有管理之前都是属于混乱级。
已管理级：项目级，具体就是把上图要求的那些文档的标准达到CMMI中规定的标准。
已定义级：把隐性的知识转成显性的方式。关键词：文档化，标准化。
定量管理级：关键字：量化，强调量化。
优化级：持续优化
在考试过程中一般会给出一些描述，然后问这是CMMI中的第几级或是跟你说CMMI第几级有些什么特征，然后问说对还是不对。
连续式：列出很多的选择，让企业自己去选择，看看自己需要哪些方面就去选择哪些方面。
阶段式：更适用于标准化的评级，需要达到什么样的要求才能达到我们需要的标准。

项目管理

主要考点：时间管理，风险管理。

时间管理

关键路径：从开始节点到结束节点最长的那条路径。（对应的是项目的最短工期）

（1）
甘特图简单，从图中可以很明显的看出计划的进展，哪项工作计划在什么时候开展，实际情况与计划情况如何，但由于简单明了无法表示各个任务之间的依赖关系，无法清楚的表示哪些工作应该先做，哪些工作应该后做，任务执行的先后顺序无法很清晰明了的表达。
选D
（2）
最早时间：从开始事件出发，到达该事件花费的最长的时间。
最晚时间：计算执行到最后一步需要的最大时间然后再通过路径逆推回去达到那个事件上。
选C

风险管理

项目风险就是指当项目本来计划是100万的项目却只计划了95万结果导致项目没有完成。
技术风险：技术因素导致项目没有完成，例如使用的技术过于新颖却因为技术不够成熟而导致项目失败或使用的技术过于老旧在后续的维护与升级中长生问题。
商业风险：与市场有关，不在技术部门的考虑范围之内。
在项目经理可控制范围内的风险：项目风险。
风险的曝光度是为了量化风险，用于衡量一个风险是要重点管控还是不需要过于理睬。

面向对象的需求分析

对象：
类：将对象的共性抽取出来而形成的。
实体类：与数据相关的。
边界类：在该系统之内但是要跟外界的系统进行交互。
控制类：类与类之间的衔接。
封装：相关的数据封装在一起，封装的标志：需要用到封装对象中的数据不能直接获取到数据而是要通过该对象提供的接口进行相关操作。
继承与泛化：
继承：一个子类继承了父类的一些特性，称为继承。
泛化：将许多个子类的共享抽取出来作为一个上层的类，称泛化。
多态：做同样的操作，但是对象不同，那么之间的方法就可能不同，看上去是同一种形式但表现出来的是不同的状态。
接口：特殊类，只有方法的定义没有方法的实现。
消息：对象之间进行交互所采用的机制采用异步的方式进行传输的，对象之间的通信走的都是消息的模式。
组件：构件。
模式和复用：提出模式就是为了复用，模式是一种经验的传承，将以前解决这种方式归总整理起来进行规范化的调整，以后处理相同的问题都采取这种模式解决问题，根据模式的不同可分为架构模式，设计模式，惯用法等。

面向对象设计原则

单一职责原则：设计目的一个类，它的目的应该只有一个，解决一个单一的问题。
假设不这么做的话，一个类涉及到很多方面，那它的耦合度就会增加。
这样做能够降低整个程序的耦合度。
开闭原则：在原有的功能上要增加新的功能时，偏向于新增一个功能而不是去修改原有的功能。因为在修改原因的功能时可能会引入新的bug。
李氏替换原则：让子类能够替换父类。
子类不能够替换父类的情况：子类继承了父类，但是对于继承的方法进行了重载，导致它们的职能发生了改变，此时的子类就不能够替换父类。
因此子类继承了父类时，不要盲目的对于继承下来的方法进行重载。
依赖倒置原则：依赖接口，在升级时会更加的便利。
接口隔离原则：多个接口说明接口的功能设计的比较单一，降低了耦合度。
组合重用原则：在一个新的对象里面使用一些已有的对象，使之成为新对象的一部分。继承是紧耦合的关系，因为父类变子类也会跟着变。
迪米特原则：使用封装的方式将对象的属性封装为私有的，其它对象想要获取其中的数据就只能通过它开发的接口进行访问。

需求分析

OOA-UML（大题必考）

主要看构造块中的关系和图
图：UML的主体部分，特别注意：用例图，有些地方将用例图归为静态但大部分归为动态，在考试时先确定其它图是属于哪类的，最后再去确定用例图是属于静态还是动态。
主要掌握这些图的关系，与作用，在静态图中如类图就表达的是类与类之间的关系，但是部署图的表达比较不同，部署图：软件的部件应该部署在哪个硬件的节点上。
行为图中各有各的特征，因此行为图要特别注意。
用例图：系统与外部之间交互的关系。
顺序图：强调按时间顺序
通信图：与顺序图相比，该图不强调时间顺序。
状态图：状态的变迁，转移的情况。
活动图：与流程的结构是一致的。

设计模式

架构模式：从全局看待问题，解决问题，得出结论。
设计模式：局部的设计问题（在构件层级时会采用）。
惯用法：与语言相关。
区分架构模式与设计模式：看它是从全局设计还是局部设计。
全局设计：架构模式
局部设计：设计模式
惯用法与设计模式：看它是否与语言相关。
语言相关：惯用法。
与语言无关：设计模式。

设计模式分类

创建型模式：用于创建对象的模式。
结构型模式：主要是处理类或是组的问题。
行为型模式：描述类或对象的交互情况，以及职责的分配问题。
首先要分清楚各个模式是属于哪类的模式。

创建型模式

抽象类模式：针对具体的系列而不是针对具体的类，例如创建一个专门操作sql数据库的对象，那么该对象就是专门操作sql数据库的，针对sql数据库这一系列所需要的，所对应的对象。
构建器模式：一个实例需要用到不同的部件，可以使用构建器为该实例的各个部分指定不同的部件最终形成实例。
工厂方法：创建接口，由子类决定具体的类。
原型模式（克隆模式）：拷贝现有对象，创建新的对象。
单例模式：在系统中只存在一个实例。

结构型模式

桥接模式：一棵树的变化点有两个不同的方面，将该树拆成两个树，然后进行桥接，相当于是对于继承树进行拆分。如下图所示，将一棵树的两个不同的方向拆成两棵树，然后进行桥接。

行为型模式

职责链模式：有一个请求，向上申请，如果该请求能够处理就直接处理，如果该请求无法处理则会将该请求向上抛，直至该请求被处理。
例如：
一个项目需要申请500元的经费，主管就直接审批了。
另一个项目需要500万的经费，主管无法审批就需要请示经理，经理也无法审批就要请示财务总监，财务总监也无法审批就要请示董事长，一层一层向上申请，直至有人能用处理该请求（就保证了请求者只需要请求一次，不需要向多个人发出多次请求）。
命令模式：最大的特征：将命令封装成了一个对象，而不是一个简单的消息，命令模式可方便的进行日志记录操作以及撤销命令。
解释器模式：相当于是构造了一个虚拟机来处理问题。

备忘录模式：先开辟一个空间，将对象的原始信息记录下来，用于做恢复的操作。
观察者模式：例如有一个A1，A3依赖于A1，当A1发生改变时就会通知A3也进行改变。
状态模式：将状态封装为一个类，状态的改变也会改变对象当前能够执行的行为，在该情况下我们只需做好状态的变迁，在该状态下它能够做些什么操作它会根据自己当前的状态做相应的变化。例如会员。
策略模式：例如有多种排序方式，那么要使用哪种模式进行排序有多种方案可以进行选择，那么就需要使用策略模式进行多种方案的切换。

数据流图（DFD重点考察-练）

数据流图基本概念

在上图中用户信息是一个数据流，但在数据流上只有一个名称，没有具体的解释，所以需要数据字典，在数据字典中会有对该名称具体的解释。
加工：（用户管理）（操作管理），在程序中体现出来的就是处理过程或是函数之类的东西。
数据存储：为了存储细节，往往是以表为单位。在题目中表达为某某文件，某某表之类的就表达的是数据存储。
外部实体：系统之外的人员或是外部系统。
数据流图又称为分层数据流图。

在顶层的大椭圆是我们要开发的系统，两边的方框是外部实体。
在第二层中会有多个职能处理部件，这几个处理职能部件之间会有数据流转。
数据流图的分层思想使它作为结构化开发最为主流的一个工具
在构图时，要保证上层与下层保持平衡。

数据字典

数据字典中要记住它的作用以及它的各个符号的作用。

数据平衡原则

父图与子图之间的平衡

在题目中会给出0层数据流图要我们补充顶层数据流图缺失的数据流或是相反。
找0层数据流图缺少的数据流时就看顶层数据流图中的哪些外部实体与系统中有什么样的数据流，或是相反。这些数据流必是外部实体与系统的联系，因为内部的数据流在0层数据流图中能够体现出但是在顶层数据流图都是在中间件内部的，是无法看出来的。
在检查数据流的题目中不仅要检查数据流是否有缺少也要检查箭头的方向是否正确。
子图内部平衡

黑洞：只有输出没有输出
奇迹：没有输入却有输出
必须要有正确的输入和输出。

数据流图的答题技巧

例题

试题一

问题4：在绘制加工时可以会出现的错误：
加工本身就不合格，数据流就没有平衡：例如奇迹与黑洞。
数据流命名问题：输入流与输出流一样或输入流经过加工根本不可能产生该种输出流。

问题1：
E1：前端应用
E2：数据管理员
E3：后端数据库
问题2：

数据存储的操作要么是某某表，要么是某某文件，然后根据描述在图中进行定位，例如用例信息会存储在用户表中，那么D1这个表的数据流中既有用户信息的输入也有用户信息的输出，因此可以判定它就是用户表，其它的表的判定方式一致。
D1：用户表
D2：操作表
D3：权限管理维护表
问题3：

①找到0层图与顶层图之间缺失了哪些数据流，与题干的描述又缺失了哪些数据流。
答案已在上图中。
试题二：



问题1：

E1：非信用卡客户
E2：信用卡客户
E3：银行
问题2：
信用卡申请表：E1->CCMS。
激活请求：E2->CCMS。
交易信息：CCMS->E2。
问题三：
要找到错误的数据流，就是将0层图与顶层图进行匹配，进行匹配前必须先将图中缺少的数据流补全再进行比较才有意义。

经过对比发现：
在下面的图中的信用卡申请表的方向是错的。在上面图中可以看出信用卡申请表应该是从非信用卡用户到系统中的。
激活请求的方向与对象是错的，激活请求应该是信用卡用户向信用卡管理系统发出请求，因此激活请求应该从E2出发然后连到P4。
P1~P4的名称可以通过文字描述与数据流的描述中看出。
P1：交易信息查询。（数据流：交易信息，交易记录查询请求）
P2：客户信息管理。（数据流：查询/修改个人信息，个人信息）
P3：信用卡激活。（数据流：激活通知）
P4：信用卡申请。（数据流：信用卡申请信息）

数据库设计

设计过程

概念结构设计：完成ER模型（实体联系模型）建模工作。

ER模型

实体间联系类型

考题方式：给一段描述与一个不完整的ER模型，缺少ER模型的名与对应的关系我们补充。

在考题中常有联系模式空着一个属性，此时要多注意它与其它关系模式产生的联系，该联系也要作为该关系模式的属性。

答题技巧

ER模型是数据方面的建模，数据流图是功能方面的建模。

案例分析

案例分析1：




问题1：
（1）n（部门与员工的关系：1：n）
（2）n
（3）m（客房与客户的关系：n：m，一个客户可以预约多个客房，一个客房可以被多个用户预约，只要时间错开就可以了）
问题2：
从题目提供的ER图中可看到只有权限一个实体与其它的实体之间没有联系，因此缺少联系的就是权限这个实体与另一个实体的联系。经过分析结果的第一天信息可知权限是给员工使用的，且员工分为服务员与管理员两种类型。
权限与员工之间的联系：1：m，一个员工只能有一种权限（例如管理员权限，服务员权限），而一种权限可以给多个员工。
问题3：
在分析缺少的属性时就要看这个实体与什么实体有什么样的联系，如果现有属性中没有能够与它所联系的那个实体进行关联的，那么说明当前的属性是不完整的。
（4）员工号，部门号
（5）客房号
（6）身份证号
（7）岗位
（8）身份证号，客房号
问题4：考察规范化理论
优点：减少连接操作。
缺点：造成数据冗余。
案例分析2：






问题1：
商场与部门是存在关系的，从分析结果的第二条中就能看到一个商场会有多个部门，因此商场跟部分的联系（1：n）。
从分析结果第3条中可以看到每个部门雇佣多名员工，所以部门与员工的联系为（1：n）。
从分析结果第4条中可以看到每个经理只能管理一个部门，每名员工只隶属于一个部门，所以部门与经理的联系为（1：1）。
经理是属于特殊的员工。它们之间要这么画一下表示经理是特殊的员工。

问题2：
在分析缺少了什么属性时，可能常会发现它的属性都已经被填写好，那么就是要注意缺少的是联系。
（a）：商场编号
（b）：部门编号
（c）：员工编号
部门-主键：部门编号，外键：商场编号
员工-主键：员工编号，外键：部门编号
经理-主键：员工编号，外键：员工编号
问题3：
还需添加的实体：紧急联系人。
存在联系：一个员工只能对应一个紧急联系人，一个紧急联系人可以对应多个员工（员工与紧急联系人的联系，n：1）
紧急联系人的关系模式：员工编号，紧急联系人姓名，紧急联系人电话。

UML建模

用例图（重点）

考题类型：考题中有关于对项目详细描述，根据题干对题目给出的例图进行补充。
根据题干的意思分析两个用例之间的关系。
包含关系：include
扩展关系：extend
区分包含于扩展的关键在于是否必须，如果是必须就是包含，若是不必须则为扩展。例如上述用例图中的登记外借信息，用户必须登入才能登记外借信息，因此登记外借信息用例包含用户登录的用例。而查询书籍信息，如果查询到的书籍信息是自己所需要的，那就直接完成了查询，如果看到了查询的结果中信息是错误的，那么就需要修改书籍信息，修改书籍信息这一个用例不是必须执行的，而是查询书籍信息的扩展。

类图与对象图（重点）

考察方式就是上面写的填类名，填多重度，填关系
多重度：

0…*与 .是相等的。
填关系：

实现是对接口的，泛化是对类的。

顺序图

顶端是对象，每一个对象都会画一条虚线（生命线），箭头指向就是说明是谁在向谁发消息。
考察重点放在消息上，根据题目分析消息的名称，其次是填对象名。

活动图

能够表现整个处理流程的基本情况以及分支的状态。
粗横线表从粗横线的这个位置引出多少个并行的线程。
从图中可以看出在第一个粗横线的位置产生了两大分支，在下一个粗横线的位置合并了。
带甬道的活动图：
每个甬道中标出了不同的对象。
考法都是在图中扣去一部分然后根据题目给出的条件填入操作。

状态图

表示的状态的变迁，因此状态图也会被归为动态图。在状态图中以状态为节点。

考察方式：题目给出状态的描述，题目会将图中的一些信息，考生根据状态以及状态变迁的条件填入答案。
答题技巧：先识别共有几种状态，然后这种状态到另一种状态需要什么样的条件，回到先前的状态需要什么样的条件。

通信图

通信图是顺序图的另一种表达方式。对象是图像中的节点，消息在箭头边进行标注。
常将顺序图与通信图统称为交互图。

考察：图的内容扣掉一些，然后填入信息。
通信图与顺序图的差异在于顺序图强调时间顺序。

例题

问题1：
由描述信息中（1）的艺术家可能是一名歌手或是一个乐队，因此艺术家会泛化出歌手类与艺术家类。找到泛化线，从C与D出发连接在A上，得A这个类是艺术家，乐队是由歌手组成的，找到组合线，从D出发指向C，组合线的箭头由部分指向整体，得C类的名称是乐队，D类的名称是艺术家，A类与B类连接的线上写着编写与演奏指向B类，得B类是歌曲，歌曲由音轨组合而成，多条音轨聚合成唱片，找到组合线与聚合线得类E是音轨，类F是唱片。
问题2：写出类与类之间的关系
由问题一可以知道每个类的名字，得到类名后就能开始找它们之间对应的关系。
要注意的是在填写歌手的多重度时要站在乐队上（判断一个乐队需要多少名歌手组成），判定乐队的多重度时要站在歌手的上（判定一个歌手要属于多少个乐队），由描述信息（1）可得一个乐队可以由两个或多个歌手组成，一个歌手可以属于0个或多个乐队。
（1）0…*
（2）2…*
由描述（2）中可得，一条音轨上只能包含一首歌或为空，一首歌可以分布在多条音轨上。
（3）0…*
（4）2…*
由描述（2）中得一首歌曲可分布在多条音轨上，同一首歌曲在一张唱片中最多出现一次。
（5）1…*
（6）1
问题3：
在图干中找到那条缺少的关系，由于关系（1）（2）都已经在图中可以找到对应的关系，因此缺少的关系应该在（3）中找到，从（3）的描述（播放器需要准确地知道它地下一条音轨和上一条音轨是什么（如果存在的话））中可得，音轨这个类应该有个自己连接到自己身上的关系，且多重度为0…*。
问题4：
找到关闭状态与播放状态，在给出的路劲中找到最短的路径，从图中可以看出关闭状态到播放状态最短的路劲就是：关闭→按任意键（电量不为0）→选择歌曲→播放。
还可以走连接电脑的路劲，但是路径比上一个路径更长。

数据结构与算法应用

分治法

基本思想：

分治法（递归）

分治法（二分查找）

回溯法

是一种深度优先的搜索方法。
回溯法：在一个分叉口上，选择一条路径一直探下去，直到遇见底了，往上回退，然后找到上一个的另一个选择点，继续探下去，依次反复。

贪心法

贪心法：每一步，每一个选择我都选择最好的东西。
贪心法的基本思路：每一步都取最优，但最后得到的结果不一定是最优。

动态规划法

动态规划法：基本上都要使用查表得方式解决问题，它分出的每个子问题之间可能是有联系的，那么它就会构造出一张表用户存储这些结果，在解决更复杂的解时可以通过查找该表得到问题的解。

例题

问题1：
（1）j=0
（2）b[j]=b[j]+s[i]
（3）min=temp
（4）b[m]=b[m]+s[i]
问题2：
（5）贪心算法
（6）贪心算法
（7）O(n²)
（8）O(n²)
两个算法都是采用的局部最优解策略，因此都可以算是贪心算法。时间复杂度要看代码具体分析，找到代码时间复杂度最高的地方，两端代码中都有一个双重循环，且双重循环都与n有关，因此复杂度为n²。
问题3：
（9）5
（10）4
（11）否
虽然最优适应策略的每一步（局部）都选择了最优的，但是总体上来看它并不一定是最优的。




（1）k<r
这个地方要填写的是循环的终止条件，有题目可知，数组的开始位置是p结束位置是r，因此循环的终止条件为k<r。
（2）arr[k]=right[j]
根据前后代码可以看出right的元素小于left的元素，因此要把right的元素放入arr数组中。
（3）begin<end
在归并排序时，只有当开始位置小于结束位置时才有继续排序的意义，如果开始的位置大于结束的位置了，说明已经到底了，不用继续排序了。
（4）megeSort(arr,mid+1,end)
根据代码的上一条，我们已经知道了上一条代码已经将前半部分递归计算完毕，就剩后面的部分没有进行递归计算了，所以我们要让后面的部分也进行计算。
（5）
从题干中的将数组分成包含n/2个元素的两个子数组，由这点能够知道它采用的是分治法算法设计策略。
（6）T(n)=2T(n/2)+O(n)
（7）O(nlogn)
（8）O(n)
空间复杂度：它有几个元素就要用多少个空间。
（9）n1+n2
比较次数就是两个数组的元素个数之和。

面向对象程序设计

java接口定义

从低下的代码中可以看到implements Drawing，所以
在底下有两个方法，所以在（2）（3）空就是把代码中定义的方法语句抄到上面去，但注意不能实现的内容。

java类定义

例题

（5）看后面的代码中有两个类同时继承了一个接口，说明要定义该接口，（6）空中定义该接口中的方法。






在（4），（5）的空中需要我们完成画圆的代码，在考试中一般不会让我们填写完整的代码，而是调用已经给出的代码完成填空。依据现有的程序代码或是前面的uml类图找线索。

从上面的类图中可以看出V1Drawing与DP1之间存在依赖关系，依赖关系一个类或对象调用了另一个类的方法。
（4）

（5）

（6）

在这个空中需要的是在Abstract中填写，要填写什么在空中一般看不出来，要查看前后代码。

从这边可以看出这两个类继承了Shape这个类，并且都实现了draw方法，但该方法在抽象类Shape中并没有体现出，因此在Shape类中就应该要申明一些draw这个抽象方法。