计算机组成原理与体系结构

数据的表示

进制的转换

• 十进制转二进制用 短除法
• 二进制转十进制用 按权展开法

原码反码补码

表示范围 ：

浮点数运算

• 首先要对阶，最后要结果格式化

CPU结构

运算器与控制器的组成

主存储器即内存。

寄存器：

• 指令寄存器（IR）用来保存当前正在执行的指令。当执行一条指令时，先把它从内存取到数据寄存器（DR）中，然后再传送给IR，为了执行任何给定的指令，必须对操作码进行测试，以便识别所要求的操作，指令译码器（ID）就是做这项工作的。指令寄存器中的操作码字段的输出就是指令译码的输入。操作码一经译码后，即可向操作控制器发出具体操作的特定信号
• 地址寄存器（AR）用来保存当前CPU所访问的内存单元的地址。由于在内存和CPU之间存在着操作速度上的差别，所以必须使用地址寄存器来保持地址信息，直到内存的读/写操作完成为止
• 为了保证程序指令能够连续地执行下去，CPU必须具有某些手段来确定下一条指令的地址。而程序计数器正式起到这种作用，所以通常又称为指令计数器

Flynn分类法简介（可以不看）

• 是一种计算机体系结构的分类法
• 两个指标 ：指令流&数据流，分别都分成两种类型 ：单的和多的。那么就组成了四种体系结构。

CISC & RISC

指令系统类型 的 区别比较 ：

CISC 是在以前计算机还没有大规模通用化（计算机定制）时被提出的，定制，设计，e.g.天气预报计算机。根据不同用户做不同的指令，且指令数量很多且复杂，所以是复杂的。
后来计算机要成为了通用设备，就要精简化 计算机指令系统。比如把乘法删掉，看成了多个加法，大大降低系统的指令数量。
可变长格式 ： 指令在系统中有一个二进制的编码，编码的长度可以不同；而在RISC中是定长格式。
RISC引入寄存器，因为速度极快效率极高。
硬布线逻辑控制 ：效率高

流水线

流水线，流水线周期及流水线执行时间

• 由于取址，分析，执行 这三个步骤是由不同的部件来完成的

• 流水线执行时间计算 ：
• 理论时间 是 203。
• 实践时间 ：k 是指分几段（这里是3），三角形t就是流水线周期。204。
• 百分之80的概率 考试用的是 理论时间公式

流水线吞吐率，加速比，效率

计算出不使用流水线的时间为500，使用流水线的时间为203。

• 时空图中所有颜色块的面积大小
• 也因此得出 每一个工作段时长是相等的 的情况下 的流水线效率是最高的，一个执行完后下一个立即开始执行，连接非常紧密，那么浪费掉的只有刚开始建立的小片空间 和 最后完成时小块的空间，中间都是密集的。

流水线加速比：不使用流水线所用的时间与使用流水线所用的时间之比称为流水线的加速比，加速比越大越好。

流水线采用异步控制并不会给流水线性能带来改善，反而会增加控制电路的复杂性。

最大吞吐率是流水线在达到稳定状态后所得到的吞吐率，它取决于流水线中最慢的一段所需要的时间。

层次化存储结构

• 寄存器在CPU里，容量极小，速度很快。
• Cache是高速缓存存储器
• Cache按内容存取 速度远高于 按地址

Cache的基本概念

• Cache工作于CPU和 主存之间
• 在整个存储体系中，除了寄存器，Cache速度是最快的
• 图上这题的数据中 引入Cache后 使得速度提升了近20倍

影响Cache命中率的因素包括高速存储器的容量、存储单元组的大小、组数多少、地址联想比较方法、替换算法、写操作处理方法和程序特性等，这些因素相互影响，没有关键影响因素。

在嵌入式系统设计时，高速缓存对程序员来说是透明的。

时间局部性与空间局部性

即局部性原理，得到最佳效果。

随机存储器与只读存储器

主存的分类

• 内存 是 随机存储器
• 随机存储器RAM 特点 ：内存一旦断电，内存中所有数据都将被清除掉，保存不下来
• 而 只读存储器ROM 在 掉电后，仍然能存储相应信息

主存的编址

• 就是把芯片组成相应的存储器

• 8 ∗ 4 位的意思是 ：8代表它有8个地址空间，4代表每一个地址空间是存储是4个bit位的信息，比如说000这一个空间里面就有4个bit的容量

用大的地址-小的地址+1即可，K是1024，即2¹^0.

磁盘工作原理

计算机总线

• 内部总线 ：微机内部各个外围的芯片 与 处理器之间的总线。是 芯片 的级别
• 系统总线 ：微机中各个插电版 和 系统版 之间的总线。属于 插件版 这一层级
• 外部总线 ：微机 和 外部设备 的总线

计算机执行程序时，在一个指令周期的过程中，为了能够从内存中读指令操作码，首先是将程序计数器（PC）的内容送到地址总线上。

PCI总线是并行内总线，SCSI总线是串行内总线。

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

串联系统

可靠率R，失效率lamda。注意这里的两个公式中，右边失效率的公式是近似的，当子系统比较多，且每个失效率极低的时候，可以用这个公式快速计算结果。

并联系统

模冗余模型

• 提高系统可靠性时可以用冗余的方式进行。表决器中少数服从多数

常考题型

先看总体是串联还是并联

差错控制

循环校验码CRC

CRC可以做检错但不能做纠错的一种编码

• 要在原始报文后加若干个0，加的个数就是生成多项式的长度-1
• 进行%2除法后得到一个四位的余数，把这个四位替换刚才补上的4个0的位置，就得到了CRC编码
• 得到的结果和11011做%2除法运算，如果得到的结果是0那就对了

海明校验码

• 2^r=4+r+1中的4就是信息位的位的个数，r就是校验位的位的个数
• 海明校验码除了可以检错还可以纠错（两个结果异或就知道哪位出错，再取反就纠错了）

寻址方式

寻址方式：

• 立即寻址：立即寻址方式只针对源操作数，此时源操作数是一个立即数，它作为指令的一部分，紧跟在指令的操作码之后，存放于内存的代码段中
• 直接寻址：直接寻址表示参加运算的数据放在内存中，指令中给出的是数据存放的偏移地址
• 寄存器寻址：当操作数不放在内存中，而是放在CPU的通用寄存器中时，可采用寄存器寻址方式。此时指令给出的操作数地址不是内存的地址单元号，而是通用寄存器的编号。
• 隐含寻址：有些指令的操作码不仅包含了操作的性质

操作系统基本原理

操作系统概述

进程管理

进程状态转换图

• 图一中的就绪是只缺一个资源-CPU资源，万事俱备，只限东风；等待是除了没有CPU资源，还差其他状态；运行是这个进程所需要的所有资源都配足了，并且给它了CPU资源。
• 图一中，注意没有从等待到运行的箭头，说明在运行时缺了个资源，在补好后不能直接回到运行状态。CPU资源宝贵，所以采用时间片方式，用完一片要等下一次。调度。
• 发现三种状态不足以涵盖，比如人为暂停某个进程，提出五态模型。图二中，运行，活跃就绪，活跃阻塞对应原先的三态模型。挂起。

前趋图

• 用前趋图的形式来表达的其实是要完成的一系列活动它的先后的约束关系。如图一会让人误解必须先什么再什么，但其实它们之间没有约束关系。D到E有一条线表示约束。哪些任务可以并行，哪些任务有先后关系。

进程的同步与互斥

• 互斥 ：在同一时刻，只允许某一个进程去使用资源，即，同一个资源不能同时服务于多个进程
• 同步 和 互斥 不是互为反义词，互斥的反义词是共享，同步的反义词是异步
• 同步 ：当差距拉的比较大时，要求速度快的停下来等

生产者与消费者问题

单缓冲区情况 ：市场容量只有1，且同一时刻不允许既有生产者去存东西又有消费者去搬东西，这就是互斥，市场是一个互斥资源，只允许一个人操作，不能同时操作；生产者把东西放进去，放了一个，市场就满了，不能再放了，不允许，只有等到消费者把市场里的东西消费掉，才允许生产者再放东西，这就是同步。
多缓冲区情况 ：类似，只是同步的情况可以放的步子大一点而已。

PV操作

• 临界资源 ：独木桥就是一个临界资源。共享，互斥（某一时间点只允许一个人）。
• 临界区 ：访问临界资源的代码。是代码段，不是缓冲区之类的。
• 信号量 ：P ( S ) P(S)P(S)，V ( S ) V(S)V(S)等中的S SS就是信号量。特殊体现在它是应用于PV操作中的专属变量。
• PV操作 ：是两大原子操作的一个组合，有P操作和V操作。

解决问题

• 加入PV操作使得某些错误操作引刃而解

PV操作练习题

• 最多允许n个购书者进入，如何做到这一点 ：在进入的时候把信号量-1，一直减到到负数的时候，就阻塞别人进入，也就是P操作，当S小于0时当前进程将被阻塞，阻塞会如何被唤醒激活呢？就是当有车驶离停车场，就进行V操作，把资源释放出来，这就是图中的P ( S n ) P(S_n)P(S
  n )和V ( S n ) V(S_n)V(S n )这一对信号量的操作，或者说这一对PV操作，实现的功能就是书店最多允许n个购书者的进入，因为n+1个进来的时候就会被阻塞
• 付款操作不是购书者单人就能完成的操作，需要收银员，在这个过程中会有同步的关系在里面
• 收银员进程中，假如没有b1,b2，那直接就变成了收费，周而复始收费的动作，问题就在于如果没有购书者提出付款的申请，收费动作没有意义，所以一开始没有人提出付款需求，收银员收费是不允许的，所以b1位置要有一个P操作，且这个P操作应该由付款动作来唤醒，一旦有人要付款，就要进行一个V操作，V操作唤醒收银员则a1和b1的信号量是同一个，且是一对PV操作
• 付款得等收银员收费后才可以走，所以a2对购书者也会有一个阻塞操作，让它等待收银员进程完成它的职能，这个a2和b2是对应起来，有一对PV操作
• 所以，a1和a2分别是V ( S 1 ) , P ( S 2 ) V(S_1),P(S_2)V(S 1 ),P(S 2 )，b1和b2分别是P ( S 1 ) , V ( S 2 ) P(S_1),V(S_2)P(S 1 ),V(S 2 ),PV操作题目关键点在于找出约束关系.

PV操作与前趋图

• 对于A活动而言，在它前面是没有任何活动的，所以它一开始就能执行，并不受什么约束，B，C也是如此；但对于D而言，一开始没办法执行，要执行它必须要先完成ABC这些，而要执行E必须先完成D

其实就是P自减，V自增
简单方法 ：要用到的信号量是S1到S4，那么在箭线上标出这四个信号量，遵循从左到右，从上到下，每一个箭头对应一个信号量，箭头的起点位置是V操作，终点位置是P操作

因此答案是CAA

死锁问题

答案是13个。在分析最少多少个资源不会发生死锁时，就先给每个进程分配它所需的总数-1个资源，然后系统里还有一个资源，这样就不会产生死锁

银行家算法

• 死锁的四大条件，缺一不可
• 互斥 ：大家不能同时使用
• 保持和等待 ：各个进程会保持自己的资源且会等待别人释放更多的资源给自己
• 不剥夺 ：系统不会去把分配给某个进程的资源剥夺掉

• 环路等待
• 因此，解决死锁问题有两种方案 ：方案一、死锁的预防；方案二、死锁的避免

• 系统状态是安全的，即，系统没有发生死锁状态。
• 要计算出当前系统还剩了多少个资源

存储管理

分区存储组织

• 最佳适应法的缺陷 ：使用最佳适应法后，整个系统中内存的碎块会非常多，且那些碎块很不好利用。因此我们考虑最差适应法。
• 循环首次适应法 ：就是把这些空闲的区域按顺序连成一个环状，然后顺次分配，那就不会每次都只盯着第一个了

页式存储组织

• 前面讲到的分区存储组织，就是在内存中划定一个用户区域，供用户程序调用内存时使用，会出现超越内存容量的问题，不好
• 而在页式存储组织中，就解决了超越内存容量的问题，比如如果内存是2G，甚至可以运行4G的程序
• 逻辑地址 和 物理地址 间的 页内地址是相同的，页号不一样，因为逻辑地址的页号对应着物理地址的块号，可以看到，页号和块号不是相等的，当然也可以是相等的，没有严格的限制，因此要查表才能得知
• 如何通过逻辑地址求物理地址 ？首先要知道逻辑地址中哪一部分是页号，哪一部分是业内地址，将页内地址直接写下来就是物理地址的页内地址，然后再通过页号去查找块号，把两部分拼接起来就是物理地址

• 淘汰页号，淘汰的必须是在内存中的，就是0125中，再看访问位，刚刚被访问过的访问位为1，不能淘汰，只有访问位为0的才能淘汰，所以应该被淘汰的应该是1

段式存储组织

• 段式存储分为段号和段内地址两个部分，虽然从地址的结构来看给人段式存储和页氏存储一样的感觉，但实际上并不是，因为它们分割的方式有较大差异，段式按照逻辑结构来划分，段的大小不要求一致，而在页式中这是不允许的，
• 好处 ：便于共享
• 段表存的是段号，段长，基址

段页式存储组织

• 先分段再分页
• 缺点 ：查了段表还要查页表

快表

• 相联存储器 ：是按内容存取的，特点 ：速度非常快，效率非常高，快表是放在了高速缓存器Cache里，相对应来讲，如果把段表，页表之类的放在内存中，那称之为慢表，快表是放在Cache里的，慢表是放在内存中的

页面置换算法

• FIFO
• 对比图二和图一，把内存页加到四页的时候，发现缺页次数反而增加了，这就产生了抖动现象

练习

• 没有使用快表，说明，每一个块，需要两次内存的访问，总共有6个块，所以会产生12次对内存的访问
• 对于第二问缺页中断的问题 ：默认指令一次性读入即只产生1次 ，而这里的操作数每个都会产生2次

• 因此第二问缺页中断次数为5

文件管理

索引文件结构

• 这种结构本身的容量很有限，但它引入了一种扩展机制，可以很方便的将文件容量扩大很多倍
• 一般的索引文件结构有13个结点（0-12）

• 逻辑块号往往从0开始
• 可以看到5号逻辑块对应的物理块号是58

所以选C和D

文件和树形目录结构

位示图-空闲存储空间的管理

• 在磁盘上面有大量的空间，需要管理，以便有依据分配空间，有这四个管理方法
• 位示图法 ：1表达的区域已经被占用，0表达还是空闲，把存储空间分成很多个物理块，直观表达空闲还是占用

4195号物理块其实是第4196个物理块，那么( 4195 + 1 ) / 32 = 131.125 (4195+1)/32=131.125(4195+1)/32=131.125，超过131，说明把前131个都填满，并且当前在第132个中.

• 占用，所以是1，所以AC排除，而根据上图，就是第3位置，因此B
• 细节 ：“第X个字”是从1开始算，“多少位置”是从0开始算

设备管理

数据传输控制方式

• 数据传输控制方式主要指的是 内存 和 外设 之间的数据传输控制问题
• 程序控制方式 又称为 程序查询方式，这种方式是最为低级的，也是CPU介入最多的机制，外设在这种方式中非常被动
• 程序中断方式 很多方面和程序控制方式一样，但主动性强些，有中断机制，如果外设完成了相应的数据的传输，这时，它会发一个中断出来，系统就会做下一步的处理，因此，效率会比查询方式高一些
• DMA方式，也称，直接存取控制方式，有专门控制器，CPU只要在开头初始化，整个过程都由DMA的控制器来完成监管，完成后再由CPU接管，效率高很多

看门狗技术是一种计算机程序监视技术，防止程序由于干扰等原因而进入死循环，一般用于计算机控制系统。看门狗通过不断监测程序循环运行的时间，一旦发现程序运行时间超过循环设定的时间，就认为系统已陷入死循环，然后强迫程序返回到已安排了出错程序的入口地址，使系统回到正常运行。从其定义与特点可知，当看门狗定时器超时的时候，会产生看门狗中断。

为了便于实现多级中断嵌套，使用堆栈来保护断点和线程最有效。

中断响应时间，是指从中断请求到开始进入中断服务程序所需要的时间。

虚设备与SPOOLING技术

• SPOOLING技术核心在于开辟了缓冲区，把要输出或输入的数据先缓存起来，这样就解决了外设的低俗和内部系统的高效之间的瓶颈差异，一般系统内部都内置了这个技术

微内核操作系统

• 将内核做小的操作系统，问题出现的概率大大降低了
• 微内核操作系统中分了用户态和核心态，核心态就是微内核中的内核情况，用户态就是核心态之外进行的，即，在用户态这里出现的问题都没有关系，都可以通过一定方式解决，但核心态出现故障就会比较严重；用户态和核心态之间有交互，只有到了非常关键的部分才会在核心态处理

数据库系统

三级模式-两级映射

数据库设计过程

ER模型

• 学生这个实体可能包含多个属性，实体和实体之间会有联系

关系代数

规范化理论-函数依赖

规范化理论-价值与用途

规范化理论-求候选关键字键

• 超键和候选键的唯一区别就是超键可能有冗余属性，而候选键不存在冗余属性；候选键也是可以唯一标识元组的

• 候选键和主键的区别 ：候选键可以有多个，主键只能有一个

求候选键

• “A和B”和“AB”区别 ：后者是组合键

规范化理论-范式

第一范式

第二范式

• SNO和CNO的组合键才是主键，因为联合起来才能确定成绩；而学分是可以通过课程号来确定的；那么候选键就是SNO和CNO的组合键，这里存在部分函数依赖，带来的问题是数据冗余…。解决方案是把CNO和学分提取出来新的关系模式，在原来的关系模式中去掉学分，但不能去掉CNO

第三范式

• 这里的主键标出来了只有单属性，是不可能有部分函数依赖问题存在的，所以肯定也是满足了第二范式
• 但这张表里依然有数据冗余的问题
• 解决方案就是把DNO和DNAME和LOCATION独立出来成为一个关系模式，原来的关系模式就只剩下三个字段了

BC范式

只要在候选键中出现过的就是主属性
这里STJ都是主属性，没有非主属性，所以肯定是满足第二范式和第三范式的
由于T − > J 中T不是候选键，所以这个不是BC范式

范式练习题

• 不属于第三范式有两种可能 ：1.属于第二范式但不属于第三范式；2.连第二范式都没有达到。一般不会连第一范式都没有达到
• 职工和部门是多对一的关系，所以应该在职工表中加上部门号
• 第二空时已经在职工号和部门号之间建立了关系，所以不需要“部门号”，所以排除CD，剩下的AB之间的差别只是B多了个商品名称，这个商品名称是没有必要的，因为商品号就可以查到商品名称，一旦出现就是冗余
• 答案为：C，D，A

规范化理论-模式分解

模式分解-例题

数据库并发控制

存在的问题实例

数据库完整性约束

数据库安全

数据库备份与恢复

数据备份

数据库故障与恢复

数据仓库与数据挖掘

反规范化技术

大数据基本概念

补充内容

SQL注入的首要目标是，获取数据库访问权限。

笛卡尔积和自然连接区别：笛卡尔积会保留所有列，自然连接会去掉重复列。

部分函数依赖：主键的是两个列的组合键，其中某一个就可以确定唯一的一行记录。

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

• 超键：唯一标识元组，超键可能存在冗余属性
• 候选键：唯一标识元组，候选键不存在冗余属性
• 主键：候选键可以有多个，主键只能有一个
• 外键：其他关系的主键

求候选键：

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

计算机网络

OSI/RM七层模型

网络技术标准及协议

• HTTP ：超文本传输协议，用来传输网页数据
• FTP ：文件传输协议
• Telnet ：远程登录
• POP3，SMTP ：邮件传输协议
• UDP ：
• DHCP ：局域网中一般都会有DHCP服务器用来做动态的IP地址的分配工作
• TFTP ：小文件传输协议
• SNMP ：简单网络管理协议
• DNS ：域名解析

对应的端口尽量都背下来：

• IpSec工作于网络层，为IP数据报文进行加密
• PP2P工作于数据链路层，用于链路加密
• HTTPS是HTTP与SSL的结合体，为传输层以上层次数据加密
• TLS安全传输协议用于两个在通信应用程序之间提供保密性和数据完整性

邮件使用的协议：

• SMTP：简单邮件传输协议，用于发送邮件，是电子邮件客户端向服务器发送邮件的协议
• POP3：邮局协议，用于从目的邮件服务上读取邮件，POP3允许用户服务器上把邮件存储到本地主机上，同时删除保存在邮件服务器上的邮件。默认传输协议为TCP，端口为110
• IMAP4：交互式邮件存取协议，与POP3类似，但不同的是，它在电子邮件客户端收取的邮件仍然保留在服务器上，同时在客户端上的操作都会反馈到服务器，如删除邮件、标记已读等
• MIME：多用途互联网邮件扩展类型，MIME消息可以包含文本、图像、音频、视频等多媒体数据

TCP和UDP均提供了端口寻址的功能。

UDP是一种不可靠的、无连接的协议，没有连接管理能力，不负责重新发送丢失或出错的数据消息，也没有流量控制的功能。

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

• 第一种分类方法 ，按分布范围分 ：办公室范围的-局域网；全球性的网络-因特网
• 第二种分类方法 ，按拓扑结构分 ：总线型 ：用一条总线把各个终端连起来；星型 ：中间会有一个中心节点，中心节点连接各个其他的节点，一旦中心节点被破坏，整个网络都瘫痪，存在“单点故障”问题；环形 ：可靠性相比之下占有优势，不存在单点故障，任何一个出故障，可以绕过去；办公室一般是星型，且中心节点是交换机

网络规划与设计

逻辑网络设计

物理网络设计

分层设计

• 顶层是核心层，底层是接入层，都只有一个层次，中间是汇聚层，可以有多个层次，同时顶层和底层功能都非常简单

IP地址与子网划分

子网划分

特殊含义IP地址

HTML

无线网

网络接入技术

IPv6

系统安全分析与设计

信息系统安全属性

对称加密与非对称加密

对称加密技术

• 对称加密技术就是在加密和解密的时候所使用的密钥是完全一样的

非对称加密技术

信息摘要

• 原始信息发生变化，特征值也会发生变化

数字签名

数字信封与PGP

设计邮件加密系统（实例）

各个网络层次的安全保障

网络威胁与攻击

防火墙技术

数据结构与算法基础

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

最优二叉树（哈夫曼树）

• 构造哈夫曼树就是让一棵树的带权路径长度是最短的情况
• 最后就是把每个叶子节点的带权路径长度求出来再累加，所有的中间节点都不是一开始的，都是构造出来的

图-拓扑排序

• 拓扑排序实际上是用一个序列来表达一个图当中哪些事件可以先执行，。。后。。，约束关系，必须先完成哪个才能完成哪个

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

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

编译过程

在计算机中，对于高级语言程序的处理，往往有两种处理方式，一种以解释的方式进行，一种以编译的方式进行，编译是整段的程序都弄好了，按编译运行的时候才然后进行执行。

在对高级语言源程序进行编译的过程中，为源程序中变量所分配的存储单元的地址属于逻辑地址。

• 词法分析阶段：非法字段、单词拼写错误等
• 语法分析阶段：标点符号错误、表达式中缺少操作数、括号不匹配等有关语言结构上的错误
• （静态）语义分析阶段：运算符与运算对象类型不合法等错误
• 目标代码生成（执行阶段）：动态语义错误，包括陷入死循环、变量取零时做除数，引用数据元素下标越界等错误

文法的定义以及语法推导树

文法的类型

语法推导树：

一般以小写字母代表终结符，大写是非终结符，非终结符就是这种符号可以推出其他符号。

有限自动机与正规式

以双圈代表的往往是结束。

例题：

• ｜是或，( a ∣ b ) ∗ (a|b)(a∣b)∗中代表循环多次，*从0到无穷，所以这个可以表达空串
• 第二空使用代入法会更快，第一问中已经知道ABC都可以被表达出来，那么第二问中就看四个选项中哪一个可以把前面这些串都表达出来，就可能是正确答案，如果不能就肯定可以排出；A，只要是a和b组成的任意串都可以表达，连第一问的D也可以，也就是说比文法的范围还要大，所以不是等价关系，排出A；D对于第一问C这种情况不能。

有限自动机例题

• A是起点，C是终点
• A选项就是问能否通过输入4个0从A到达C，可以就是可以被识别

表达式

• 这棵树的中序遍历就可以得到这个中缀表达式，，前，，后，，
• 这道题，要先把这个表达式的树给构建出来，注意括号决定了顺序，同时也是体现出了顺序，因为括号不需要构造到树中

函数调用（传值与传址）

对比：

例题：

各种程序语言特点

法律法规

保护期限

• 保护期限涉及到著作权，软件著作权，商标权，专利权，反不正当竞争法
• 对于著作权而言，它把要保护的作品分为公民作品（个人）和单位作品（单位，集体）；没有限制就是永久保护；单位作品类似，只是没有作者终生这个概念
• 公民软件作品和单位软件作品和前面非常类似，
• 注册商标，有效期10年，可以续注，期满会注销
• 发明专利权，有效期20年
• 实用新型和外观设计专利权（10年）和发明专利权的区别 ：创新程度不一样，实用新型一般是已有的东西上附属改良，而发明强调了自主创新的部分要比较大
• 商业秘密最为独特，保护期限是不确定的，分经营和技术两个方面，前提是单位做了相应的机密的保护措施，比如有明文规定；如果擅自公开了别人的商业秘密，这属于违反了反不正当竞争法。

知识产权人确定

• 主要是用来区分一个作品完成后，著作权归单位拥有还是个人拥有
• 专利权的职务作品界定比前面两种更为严苛

• 委托创作的规则和职务作品恰恰相反，
• 合作开发是大家共同拥有著作权
• 商标和专利是先申请先拥有的原则

侵权判定

• 所谓发表，就是公之于众，不一定要在报刊杂志上，网站上也算是发表
• 开发软件时思想过程不受保护

标准化基础知识

标准的分类

• 常考 ：国家标准，行业标准，地方标准，企业标准（企业规范）

标准的编号

• 给GB，要知道它不仅是国标，而且是强制性的，而推荐性的国家标准会在后面加一个“/T”，指导性。。。，实物。。。
• 行业标准代号容易重复，因此一般通过排除法
• 地方标准代号就是DB开头，很好识别
• 企业标准，以Q代表企业

软件工程

软件开发模型

瀑布模型SDLC

• 根本原因在于需求分析阶段难以把控
• 适用于需求明确或者是二次开发，否则不适合

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

• 原型和瀑布模型是一对相当互补的
• 原型法从诞生开始就是定位于需求不明确的情况
• 原型强调构造一个简易的系统
• 增量模型就是强调先做一块再做一块。。。好处在于比较早的和用户进行了接触，一次一次的审视核心功能，风险小很多

螺旋模型

• 螺旋模型特征一 ：由多个模型组合，所以具备多个模型的特点；在选择题碰到需求不明确，且选项即有原型又有螺旋形，就选原型，如果没有原型就选螺旋形
• 螺旋模型引入了风险分析，是之前的一系列模型都没有的特征

V模型

• 和瀑布模型很相似，只是在这种模型中，测试有着更重要的地位，测试有着细化；强调测试，强调要提早的进行测试，测试要贯穿于开发的始终，而不是压到最尾端
• V型有深意，因为在需求分析阶段就去画验收测试和系统测试计划了，就是希望提早发现问题

喷泉模型与RAD

• 喷泉模型最大的特点是面向对象，而瀑布模型属于是结构化的典型代表
• RAD，快速开发模型，由瀑布模型和CBSD也就是构建化开发模型组合形成的模型，最大的特点就是能快速构建应用系统

构建组装模型CBSD

• 极大提高了软件开发的复用性，使得软件开发市场降低，成本降低，可靠性增加
• 构建一个构建库->可靠性
• 架构设计在瀑布模型中没有提到

敏捷开发办法

• 不是一个模型，而是一组模型，有着共同的价值观
• 局限性 ：一般只做小型项目，大型就力不从心

信息系统开发方法

需求工程

需求开发-需求分类

结构化设计

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

软件设计-测试用例设计

软件测试-测试阶段

• 单元测试和集成测试之间都是先做单元测试再做集成测试的，但确认测试和系统测试不一定

软件测试-McCabe复杂度

• 假设有向图中有m条有向边，n个节点，用m-n+2可以得到整个图的环路复杂度
• 将所有分叉的地方抽象成节点，或者不抽象成节点，环路复杂度不会发生改变

系统运行与维护

软件过程改进CMMI

项目管理

• 各任务之间的依赖关系再Gantt图中不能非常直观的表达出来，这是它们最大的区别
• 图为PERT图
• 关键路径，就是，在整个图中，从开始节点到结束节点最长的一条路径，它对应的是整个项目的最短工期，因为在一个项目中有很多任务可以并行的开展
• 先用正推的方式把所有事件的最早开始时间求出，再通过逆推的方式把所有方式的最晚开始时间逆向求出
• 事件1在0时刻就可以进行了，事件2必须在事件1完成后，所以事件2最早的开始时间是2。。。依次算出事件9的最早开始事件是15，由于它是最后的一个事件，那么最迟的开始时间也是15

• 因此第二空的答案是10

需求工程

设计原则

UML

设计模式的概念

设计模式的分类

创建型模式

结构型模式

行为型模式

数据流图DFD

数据流图基本概念

数据字典

平衡原则

父图中的某个加工的输入输出流必须与其子图的输入输出数据流在数量和名字上相同。父图的一个输入（或输出）数据流对应于子图中的几个输入（或输出）数据流，而子图中组成的这些数据流的数据项全体正好是父图中的这一个数据流。

UML建模

UML图-用例图

UML图-类图与对象图

• 一个书籍列表对应0到多本书籍

顺序图

• 顺序图最大的特点是体现出处理事情的时候的时间顺序情况如何，按顺序一步一步下来

活动图

• 结构上，像程序流程图
• 粗横线，产生了两个不同的线程

• 这种活动图指示了不同的对象，可以指示哪个活动是归属于哪个人的

状态图

• 以状态为节点，箭线代表的是触发事件，导致状态的变迁
• 先识别总共有几种状态，再看这些状态之间转化的条件

通信图

• 其实是顺序图的另一种表达方式；顺序图就是上面一排的对象，完了之后引出相应的生命线，对象之间的一些交互就是在这个上面以顺序表达消息的传递。
• 通信图中，对象就是这一系列的节点，对象的交互还是通过箭头的方式来标识，所以它和顺序图的区别就是它时间方面没强调的那么明晰，其他方面基本一致。所以把顺序图和通信图统称为交互图。