软考：软件设计师 - 翻斗花园小秘密

本文最后更新于 112 天前，其中的信息可能已经有所发展或是发生改变。

更新日志

计算机组成原理

计算机的基本硬件由 运算器 、控制器 、存储器 、输入设备和输出设备 5大部件组成。
运算器、控制器等部件被集成在一起统称为中央处理单元（Central Processing Unit, CPU）。CPU是硬件系统的核心，用于数据的加工处理，能完成各种算术、逻辑运算及控制功能。
存储器是计算机系统中的记忆设备 ，分为内部存储器和外部存储器 。前者速度高、容量小，一般用于临时存放程序、数据及中间结果；而后者容量大、速度慢，可以长期保存程序和数据。
输入设备和输出设备合称为外部设备（简称“外设”）。

中央处理单元

CPU的功能：

程序控制：CPU 通过执行指令来控制程序的执行顺序。
操作控制：一条指令功能的实现需要若干操作信号配合来完成，CPU 产生指令的操作信号并将操作信号送往对应的部件，控制相应的部件按指令的功能要求进行操作。
时间控制：CPU 对各种操作进行时间上的控制，即指令执行过程中操作信号的出现时间、持续时间及出现的时间顺序都需要进行严格控制。
数据处理：CPU 通过对数据进行算数运算及逻辑运算等方式进行加工处理，数据加工处理的结果被人们所利用。即CPU最根本的任务是：对数据的加工处理。此外，CPU 还需要对 系统内部和外部的中断（异常）做出响应，进行相应的处理。

CPU 的组成：

CPU主要由运算器、控制器、寄存器组和内部总线等部件组成。

运算器：由算数逻辑单元 ALU（实现对数据的算术和逻辑运算）、累加寄存器 AC（运算结果或源操作数的存放区）、数据缓冲寄存器 DR（暂时存放内存的指令或数据）和状态条件寄存器 PSW（保存指令运行结果的条件码内容，如溢出标志等）组成。执行所有的算术运算；执行所有的逻辑运算并进行逻辑测试。
控制器：由指令寄存器 IR （暂存 CPU 执行指令）、程序计数器 PC（存放指令执行地址）、地址寄存器 AR（保存当前 CPU 所访问的内存地址）、指令译码器 ID（分析指令操作码）等组成。控制整个 CPU 的工作，最为重要。
CPU 依据指令周期的不同阶段来区分二进制的指令和数据，因为在指令周期的不同阶段，指令会命令 CPU 分别取取指令或数据。

【真题】

CPU 进行算术运算或者逻辑运算时，常将源操作数和结果暂存在（）中。
A.程序计数器（PC） B.累加器（AC）
C.指令寄存器（IR ） D.地址寄存器（AR）【B】
执行 CPU 指令时，在一个指令周期的过程中，首先需要从内存读取要执行的指令，此时先要将指令的地址即（）的内容送到地址总线上。 A.指令寄存器（IR ） B.通用寄存器（GR） C.程序计数器（PC） D.状态寄存器（PSW）
【C】

数据表示：

进制表示：
1. 二进制 B、0b
2. 八进制 O
3. 十六进制 H、0x
R进制整数转十进制：位权展开法。
例如有 6进制数 5043，此时 R=6，用6进制数的每一位乘以 6的n次方，n为变量，从 6进制数的整数最低位开始，n依次为 0,1,2,3，那么最终 5043 = 3*6^0 + 4*6^1 + 0*6^2 + 5*6^3 =1107
十进制转R进制：十进制整数（除以 R 倒取余数）
用十进制整数除以 R，记录每次所得余数，若商不为0，则继续除以R，直至商为0，而后将所有余数从下至上记录，排列成从左至右顺序，即为转换后的R进制数。
例如有十进制数200，转换为6进制，此时R=6，将200/6，得商为33，余数为2；因为商不等于0，因此将商33/6，得商为5，余数为3；再将5/6，得商为0，余数为5；此时商为0，将所有余数从下到上记录，得 532。
m进制转n进制：先将m进制转化为十进制数，再将十进制数转化为n进制数，中间需要通过十进制中转，但下面两种进制之间可以直接转化：
1. 二进制转八进制：每三位二进制数转换为一位八进制数。
  例如二进制数 01101有五位，前面补一个0就有六位，为 001 101，
  每三位转换为一位八进制数，即：
  001 = 1， 101 = 1+4=5，也就是 01101 = 15。
2. 二进制转十六进制：每四位二进制数转换为一位十六进制数。
  与上面同理，不再赘述。
机器数：各种数值再计算机中表现的形式，其特点是使用二进制计数值，数的符号用 0和1 表示，小数点则隐含，不占位置。
机器数有无符号数和带符号数之分。无符号数表示整数，没有符号位。带符号位最高位为符号位，正数符号位为0，负数符号位为1。
定点表示法分为纯小数和纯整数两种，其中小数点不占存储位，二十按照以下约定：
纯小数：约定小数点的位置在机器数的最高数值位之前。
纯整数：约定小数点的位置在机器数的最低数值位之后。
真值：机器数对应的实际数值。
带符号数有下列编码方式，当真值为 -45 时：原码：一个数的正常二进制表示，最高位表示符号，数值 0 的原码有两种形式：+0(0 0000000)和 -0(1 0000000)。 -45对应原码为 1010 1101 反码：正数的反码即原码；负数的反码是在原码的基础上，除符号位外，其他各位按位取反。数值 0 的反码也有两种形式： +0(0 0000000)，-0(1 1111111)。-45对应反码为 1101 0010 补码：正数的补码即原码；负数的补码是在原码的基础上，除符号位外，其他各位按位取反，而后末位+1，若有进位则产生进位。因此数值0的补码只有一种形式 +0 = -0 = 0 00000000。 -45对应补码为 1101 0011 移码：用作浮点运算的阶码，无论正数负数，都是将该原码的补码的首位（符号位）取反得到移码。-45对应移码为 01010011
浮点数：表示方法为 N = F 2^E，其中 E 称为阶码，F 称为尾数；类似于十进制的科学计数法，如 85.125 = 0.85125*10^2，二进制如 101.011 = 0.1010112^3. 在浮点数的表示中，阶码为带符号的纯整数，尾数为带符号的纯小数，要注意符号占最高位（正数0负数1），其表示格式如下：阶符阶码数符尾数一个浮点数的表示方法不是唯一的，浮点数所能表示的数值范围由阶码确定，所表示的数值精度由尾数确定。
浮点数的运算：对阶（使两个数的阶码相同，小阶向大阶看齐（低位丢弃对精度影响不大），较小阶码增加几位，尾数就右移几位） 0.10101*2^3^,–>0.0010101*2^5^
0.11101*2^5^, 尾数计算（相加，若是减运算，则加负数）结果规格化（即尾数表示规格化，带符号尾数转换为1.0xxxx或0.1xxxx）

【真题】

如果” 2X “的补码是” 90H “，那么X的真值是（）

A. 72 B. -56 C. 56 D. 111

【B】
90H = 1001 0000(补码)
反码 = 1,000 1111
原码 = 1,111 0000
2X = -112
X = -56

设16位浮点数，其中阶符1位、阶码值6位、数符1位、尾数8位。若阶码用移码表示，尾数用补码表示，则该浮点数所能表示的数值范围是（）

A. -2^64^ ~ (1-2^-8^)*2^64^
B. -2^63^ ~ (1-2^-8^)*2^63^
C. -2^64^ ~ (1-2-(1-2^-8^)2^64^ ~ (1-2^-8^)*2^64^
D. – (1-2^-8^)*2^63^ ~ (1-2^-8^)*2^63^

【B】
尾 2^阶^
n=数符（1）+尾数（8）= 9
N=数符（1）+阶码（6）= 7
-1 ~ 1-2^-(n-1)^ = -2^(N-1)^ ~ 2^(N-1)^
[-1 ~ 1-2^8^] * [2^(-64)~63^],两两相乘取边界
-2^-64^，(1-2^-8^)2^-64^，-2^63^，(1-2^-8^)*2^63^

校验码

码距：就单个编码A：00而言，其码距为1，因为其只需要改变一位就变成另一个编码。在两个编码中，从A码到B码转换所需要改变的位数称为码距，如A：00要转换为B：11，码距为2。一般来说，码距越大，越利于纠错和检错。
奇偶校验码：在编码中增加1位校验位来使编码中1的个数为奇数（奇校验）或者偶数（偶校验），从而使码距变成2。例如：奇校验：编码中，含有奇数个1，发送给接收方，接收方收到后，会计算收到的编码由多少个1，如果是奇数个，则无误；是偶数个，则有误。偶校验同理，只是编码中有偶数个1，由上述，奇偶校验只能检1位错，并且无法纠错。

CRC（循环冗余校验码）

CRC（循环冗余校验码）只能检错，不能纠错。使用CRC编码，需要先约定一个生成多项式G(x)。生成多项式的最高位和最低位必须是1。假设原始信息有m位，则对应多项式M(x)。生成校验码思想就是在原始信息位追加若干校验位，使得追加的信息能被G(x)整除。接收方接收到带校验位的信息，然后用G(x)整除。余数为0，则没有错误；反之则发生错误。

例如：假设原始信息串为 10110，CRC的生成多项式为 G(x)=x^4+x+1，求CRC校验码。

(1) 在原始信息位后面添0，假设生成多项式的阶为r，则在原始信息位后添加 r个0，本题中，G(x)阶为4，则在原始信息串后加 4个0，得到的新串为 10110 0000，作为被除数。

(2) 由多项式得到除数，多项中x的幂指数存在的位置1，不存在的位置0。本题中，x的幂指数为0,1,4的变量都存在，而幂指数为2,3的不存在，因此得到串 10011。

(3) 生成CRC校验码，将前两步得出的被除数和除数进行模2除法运算（即不进位也不借位的除法运算）。除法过程如下图所示。

得到余数1111。
注意：**余数不足r，则余数左边用若干个0补齐。如求得余数为11，r=4，则补齐两个0 得到 0011。

(4) 生成最终发送信息串，将余数添加到原始信息后。上例中，原始信息串 10110，添加余数 1111 后，结果为 10110 1111。发送方将此数据发送给接收方。

(5) 接收方进行校验。接收方的 CRC 校验过程与生成过程类似，接收方接收了带检验和的帧后，用多项式G(x) 来除。余数为0，则表示信息无错；否则要求发送方进行重传
注意：收发信息双方需使用相同的生成多项式。

【真题】

循环冗余校验码是数据通信领域中最常用的一种差错校验码，在校验方法中，使用多项式除法（模2 除法）运算后的余数为校验字段。若数据信息为 n 位，左移 k 位后，被长度为 k+1 位的生成多项式相除，所得的 k位余数即构成 k个校验位，构成 n+k位编码。若数据信息为 1100，生成多项式为 X^3+X+1(即 1011)，则 CRC编码是（）

A.1100 010 B.1011010 C.1100011 D.1011110

【A】
流程：
1、在原始信息位后加 k个 000，即 1100 000.
2、将1100 000 与生成多项式 1011 做模2除法，得到余数 010.
3、将原始信息位与余数连接起来得到 1100 010

海明码

海明码：本质也是利用奇偶性来检错和纠错的检验方法，构成方法是在数据位之间的确定位置上插入 k个校验位，通过扩大码距实现检错和纠错。设**数据位是 n位，检验位是 k位，则 n和k 必须满足以下关系： 2^k -1 >= n+k。例：求信息 1011 的海明码
1. 校验位的位数和具体的数据位的位数之间的关系 所有位都编号，从最低位编号，从 1开始递增，检验位处于 2的n(n =0,1,2…)次方中，即处于第 1，2，4，8，…位上，其余位才能填充真正的数据位，若信息数据为 1011，则可知，第1，2，4位为校验位，第3，5，6，7位为数据位，用来从低位开始存放 1011，得出信息位和校验位分布如下： 7 6 5 4 3 2 1 位数 i4 i3 i2 i1 信息位 r2 r1 r0 校验位 1 0 1 1 原始数据
2. 计算校验码将所有信息位的编号都拆分成二进制表示，如下图所示： 7 6 5 4 3 2 1 位数 1 0 1 1 原始数据 0 0 1 校验位 I4(7) = 2^2+2^1+2^0, I3(6) = 2^2+2^1, I25 = 2^2+2^0, 3 = 2^1+2^0;
  r2 = I4 ⊕ I3 ⊕ I2;
  r1 = I4 ⊕ I3 ⊕ I1;
  r0 = I4 ⊕ I2 ⊕ i1; 上式中，7=4+2+1，表示 7由第四位校验位r2和第二位校验位r1和第一位校验位r0共同校验，其余同理。可知，第四位校验位校验第7 6 5 三位数据位。因此，第四位校验位 r2 等于这三位数据位的值异或，第二位和第一位校验位计算原理同上。计算出三个校验位后，可知最终要发送的海明码校验码为 1010101
3. 检错和纠错原理接收方收到海明码之后，会将每一位校验位与其校验的位数分别异或，即做好下面三组运算： r2 ⊕ I4 ⊕ I3 ⊕ I2
  r1 ⊕ I4 ⊕ I3 ⊕ I1
  r0 ⊕ I4 ⊕ I2 ⊕ I1 如果是偶校验，那么运算得到的结果全为0，如果是奇校验，应全为1，结果才是正确，假设是偶校验，且接收到的数据为 101 1 101（第四位出错），此时运算的结果为： r2 ⊕ I4 ⊕ I3 ⊕ I2 = 1 ⊕ 1 ⊕ 0 ⊕ 1 = 1
  r1 ⊕ I4 ⊕ I3 ⊕ I1 = 0 ⊕ 1 ⊕ 0 ⊕ 1 = 0
  r0 ⊕ I4 ⊕ I2 ⊕ I2 = 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0 这里不全为0，表明传输过程有误，并且按照 r2r1r0排列为二进制 100，这里指出的就是错误的位数，表示第100，即第4位出错，找到了出错位，纠错的方法就是将该位逆转。

【真题】

海明码是一种纠错码，其方法是为需要校验的数据位增加若干校验位，使得校验位的值决定于某些被校验的数据，当被校数据出错时，可根据校验位的值的变化找到出错位，从而纠正错误，对于32位的数据，至少需要加（）个校验位才能构成海明码。

A.3 B.4 C.5 D.6

【D】
32+6=38，所以至少6个校验位

以10位数据为例，其海明码表示为 D9D8D7D6D5D4P4D3D2D1P3D0P2P1，其中 Di(0≤i≤9)表示数据位，Pj(1≤j≤4) 表示校验位，数据位 D9由P4、P3和P2进行校验（从右到左D9的位序为14，即等于 8+4+2，因此第8位的P4、第4位的P3和第2位的P2校验），数据位D5由（）进行校验

A.P4P1 B.P4P2 C.P4P3P1 D.P3P2P1

【B】
D5 = 10 = 8 + 2 = 2^3 + 2^ 1 = P4 ⊕ P2

体系结构

体系结构分类

按处理器数量进行分类：单处理系统（一个处理单元和其他设备集成）、并行处理系统（两个以上的处理机互联）、分布式处理系统（物理上远距离且松耦合的多计算机系统）。
Flynn分类法：分类有两个因素，即指令流和数据流，指令流由控制部分处理，每一个控制部分处理一个指令流，多指令流就有多个控制部分；数据流由处理器来处理，每一个处理器就处理一条数据流，多个数据流就有多个处理器；至于主存模块，是用来存储的，存储指令流或者数据流。因此，无论是多指令流还是多数据流，都需要多个主存模块来存储，对于主存模块，指令和数据都一样。
依据计算机特性，是由指令来控制数据的传输，因此，一条指令可以控制一条或多条数据流，但一条数据流不能被多条指令控制，否则会出错，就如同上级命令太多还互相冲突，不知道该执行哪个，因此多指令单数据MISD不可能实现。

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

指令系统

计算机指令的组成：一条指令由操作码和操作数两部分组成，操作码决定要完成的操作，操作数指参加运算的数据及其所在的单元地址。
在计算机中，操作要求和操作数地址都有二进制数码表示，分别称作操作码和地址码，整条指令以二进制编码的形式存放在存储器中。
计算机指令的指令过程：取指令–分析指令–执行指令三个步骤。受限将程序计数器PC中的指令地址取出，送入地址总线，CPU依据指令地址去内存中取指令内容存入指令寄存器IR；而后由指令译码器进行分析，分析指令操作码；后执行指令，取出指令执行所需的源操作数。
指令的寻址方式 顺序寻址方式：当执行一段程序时，是一条指令接着一条指令地顺序执行。
跳跃寻址方式：指下一条指令的地址吗不是由程序计数器给出，而由本条指令直接给出。程序跳跃后，按新的指令地址开始顺序执行。因此，程序计数器的内容也必须相应改变，以便及时跟踪心的指令地址。
指令操作数的寻址方式 立即寻址方式：指令的地址码字段指出的不是地址，而是操作数本身。
直接寻址方式：在指令的地址字段中直接指出操作数在主存中的地址。
间接寻址方式**：指令地址码字段所指向的存储单元中存储的是操作数的地址。
寄存器寻址方式：指令中的地址码是寄存器的编号。
基址寻址方式：将基址寄存器的内容加上指令中的形式地址形成操作数的有效地址，其优点是可以扩大寻址能力。
变址寻址方式：变址寻址方式计算有效地址的方式与基址寻址方式很类似，它是将变址寄存器的内容加上指令中的形式地址而形成操作数的有效地址。
指令系统类型 CISC 是复杂指令系统，兼容性强，指令繁多、长度可变，由微程序实现；
RISC是精简指令系统，指令少，使用频率接近，主要依靠硬件实现（通用寄存器、硬布线逻辑控制）具体区别如下：指令系统类型指令寻址方式实现方式其他 CISC（复杂）数量多，使用频率差别大，可变长格式支持多种微程序控制技术（微码）研制周期长 RISC（精简）数量少，使用频率接近，定长格式，大部分为单周期指令，操作寄存器，只有Load/Store操作内存支持方式少增加了通用寄存器；硬布线逻辑控制为主；适合采用流水线优化编译，有效支持高级语言

【真题】

Flynn分类法根据计算机在执行程序的过程中（）的不同组合，将计算机分为四类。当前主流的多和计算机属于（）计算机。

A.指令流和数据流 B.数据流和控制流 C.指令流和控制流 D.数据流和总线带宽
A.SISD B.SIMD C.MISD D.MIMD

【A、D】

以下关于复杂指令集计算机（Complex Instruction Set Computer, CISC）的叙述中，正确的是（）

A.只设置使用频度高的一些简单指令，不同指令执行时间差别很小
B.CPU中设置大量寄存器，利用率低
C.常采用执行速度更快的组合逻辑控制器
D.指令长度不固定，指令格式和寻址方式多

【D】

指令流水线原理：将指令分成不同段，每段由不同的部分取处理，因此可以产生叠加的效果，所有的部件去处理指令的不同段
RISC中的流水线技术： (1) 超流水线(Super Pipe Line)技术。它通过细化流水、增加级数和提高主频，使得在每个机器周期内能完成一个甚至两个浮点操作。其实质是以时间换取空间。 (2) 超标量(Super Scalar)技术。它通过内装多条流水线来同时执行多个处理，其时间频率虽然与一般流水接近，却又更小的CPI。其实质是以空间换取时间。 (3)超长指令集(Very Long Instruction Word, VLIW)技术。VLIW和超标量都是20世纪80年代出现的概念，其共同点是要同时执行多条指令，其不同在于超标量依靠硬件来实现并行处理的调度，VLIW则充分发挥软件的作用，而使硬件简化，性能提高。
流水线时间计算： (1) 流水线周期：指令分成不同执行段，其中执行时间最长的段为流水线周期。 (2) 流水线执行时间：1条指令总执行时间+（总指令条数 -1） * 流水线周期。 (3) 流水线吞吐率计算：吞吐率即单位时间内执行的指令条数。
公式：指令条数 / 流水线执行时间 (4) 流水线的加速比计算：加速比即使用流水线后的效率提升度，即比不使用流水线快了多少倍，越高表明流水线效率越高。
公式：不使用流水线执行时间 / 使用流水线执行时间

【真题】

流水线的吞吐率是指流水线在单位时间里所完成的任务书或=输出的结构数。设某流水线有5段，有1段的时间为 2ns，另外4段的每段时间为 1ns，利用此流水线完成 100个任务的吞吐率约为（）个/s。

A. 500*10^6 B.490*10^6 C.250*10^6 D.167*10^6

【B】
流水线执行100个任务所需要的时间为：(2+1+1+1) + (100 -1) 2 =204ns。所以每秒吞吐率为：（100/204)*10^9 = 49010^6

假设磁盘块与缓冲区大小相同，==每个盘块读入缓冲区的时间为15us，由缓冲区送至用户区的时间是5us==，在用户区内系统对每块数据的处理时间1us，若用户需要将大小为10个磁盘块的Docl文件逐块从磁盘读入缓冲区，并送至用户去进行处理，那么采用单缓冲区需要花费的时间为（）us；采用双缓冲区需要花费的时间为（）us。

A.150 B.151 C.156 D.201

【D、C】
单缓冲区：前两段要合并，是两段流水线，21+20*(10-1) =201
双缓冲区：标准三段流水线，21+15*(10-1) =156

流水线技术是通过并行硬件来提高系统性能的常用方法。对于一个k段流水线，假设其隔断的执行时间均相等（设为t），输入到流水线的任务是连续的理想情况下，完成n个连续任务需要的时间综合为（）。若某流水线浮点加法运算器分为5段，所需要的时间分别是6ns、7ns、8ns、9ns和6ns，则其最大加速比为（）。

A.nkt B.(k+n-1)t C.(n-k)kt D.(k+n+1)t
A.4 B.5 C.6 D.7

【B、A】
一条指令总执行时间+（总指令条数-1）*流水线周期
不使用流水线需要时间：(6+7+8+9+6)*n = 36n
使用流水线需要时间：36+(n-1)*9 = 9n+27
则加速比：36n / 9n+27
当n -> +∞，最大加速比=36n / 9n = 4

存储系统

计算机采用分级存储体系的主要目的是为了解决存储容量、成本和速度之间的矛盾问题。至上而下，速度越来越慢、容量越来越大、价格越来越低
两级存储： Cache – 主存、主存 – 辅存（虚拟存储体系）
局部性原理：总的来说，在CPU运行时，所访问的数据会趋向于一个较小的局部空间地址内，包括以下两个方面：时间局部性原理：如果一个数据项正在被访问，那么在近期它很可能会被再次访问，即在相邻的时间里会访问同一个数据项。空间局部性原理：在最近的将来会用到的数据的地址和现在正在被访问的数据地址很可能是相近的，即相邻的空间地址会被连续访问。
高速缓存Cache 用来存储当前最活跃的程序和数据，直接与CPU交互，位于CPU和主存之间，容量小，速度为内存的5~10倍，由半导体材料构成。其内容是主存内存的副本拷贝，对于程序员来说是透明的。
Cache由控制部分和存储器组成，存储器存储数据，控制部分判断部分判断CPU要访问的数据是否在Cache中，在则命中，不在则依据一定的算法从主存中替换。
地址映射：在CPU工作时，送出的是主存单元的地址，而应从Cache存储器中读 / 写信息。这就需要将主存地址转换为 Cache 存储器地址，这种地址的转换称为地址映像，由硬件自动完成映射，分为下列三种方法：直接映像：将Cache存储器等分成块，主存也等分成块并编号。主存中的块与Cache中的块的对应关系是固定的，也即二者块号相同才能命中。地址变换简单但不灵活，容易造成资源浪费。（如图所示）全相联映像：同样都等分成块并编号。主存中任意一块都与Cache中任意一块对应。因此可以随意调入Cache任意位置，但地址变换复杂，速度较慢。因此主存可以随意调入Cache任意块，只有当Cache满了才会发送块冲突，是最不容易发生块冲突的映像方式。组组相连映像：前面两种方式的结合，将Cache存储器先分块再分组，主存也同样先分块再分组，组间采用直接映像，即主存中组号与Cache中组号相同的组才能命中，但是组内全相联映像，也即组号相同的两个组内的所有块可以任意调换。
替换算法的目标就是使Cache获得尽可能高的命中率。常用的算法如下所示： (1) 随机替换算法。就是用随机数发生器产生一个要替换的块号，将该块替换出去。 (2) 先进先出算法。就是将最先进入Cache的信息块替换出去。 (3) 近期最少使用算法。这种方法是将近期最少使用的Cache中的信息块替换出去。 (4) 优化替换算法。这种方法必须先执行一次程序，统计Cache的替换情况。有了这样的先验信息，在第二次执行该程序时便可以用最有效的方式来替换。
命中率及平均时间 Cache有一个命中率的概念，即当CPU所访问的数据在Cache中时命中，直接从Cache中读取数据，设读取一次Cache时间为1ns，若CPU访问的数据不在Cache中，则需要从内存中读取，设读取一次内存的时间为1000ns，若在CPU多次读取数据过程中，有90%命中Cache，则CPU读取一次的平均时间为
(90%1 + 10%1000)ns。

【真题】

按照Cache地址映像的块冲突概率，从高到低排列的是（）

A.全相联映像→直接映像→组相联映像
B.直接映像→组相联映像→全相联映像
C.组相联映像→全相联映像→直接映像
D.直接映像→全相联映像→组相联映像

【B】

以下关于Cache与主存间地址映射的叙述中，正确的是（）

A.操作系统负责管理Cache与主存之间的地址映射
B.程序员需要通过编程来处理Cache与主存之间的地址映射
C.应用软件对Cache与主存之间的地址映射进行调度
D.由硬件自动完成Cache与主存之间的地址映射

【D】

基本概念：K、M、G是数量单位，在存储器中相差1024倍
B、b是存储单位，1B = 8b

地址编号从 80000H到BFFFFH 且按字节编址的内存容量为（5）KB，若用16K*4bit的存储器芯片构成该内存，共需要（）片

A.128 B.256 C.512 D.1024
A.8 B.16 C.32 D.64

【】
BFFFFH – 80000H = 40000H(个)
按字节编址，字节=1B，即40000HB = 4*16^4 B= 2^18 B = 2^8 K =256K
总容量 2^18，每块容量为 2^14K* 2^2bit = 2^16b = 2^13 B
2^18 / 2^13 = 2^5 = 32(片)
（特别提醒：不要硬算，要化简为2的幂指数来算）

磁盘结构和参数磁盘有正反两个盘面，每个盘面有多个同心圆，每个同心圆是一个磁道，每个同心圆又被划分为多个扇区，数据就被存放在一个个扇区中。磁头首先要寻找到对应的磁道，然后等待磁盘进行周期旋转，旋转到指定的扇区，才能读取到对应的数据。因此，会产生寻道时间和等待时间。公式为：存取时间=寻道时间+等待时间（平均定位时间+转动延迟）。注意：寻道时间是指磁头移动到磁道所需的时间；等待时间为等待读写的扇区转到磁头下方所用的时间。
磁盘调度算法磁盘数据的读取时间=寻道时间+旋转时间，也就是先找到对应的磁道，而后再旋转到对应的扇区才能读取数据，其中寻道时间耗时最长，需要重点调度，有如下调度算法： (1) 先来先服务FCFS：根据进程请求访问磁盘的先后顺序进行调度。 (2) 最短寻道时间优先SSTF：请求访问的磁道与当前磁道最近的进程优先调度，使得每次的寻道时间最短。会产生“饥饿”现象，即远处进程可能永远无法访问。 (3) 扫描算法SCAN：又称“电梯算法”，磁头在磁盘上双向移动，其会选择离磁头当前所在磁道最近的请求访问磁道，并且与磁头移动方向一致，磁头永远都是从里向外或者从外向里一直移动完才掉头，与电梯类似。 (4) 单项扫描调度算法CSCAN：与SCAN不同的是，其只做单向移动，即只能从里向外或者从外向里。

【真题】

假设某磁盘的每个磁道划分成11个物理块，每块存放1个逻辑记录。逻辑记录R0，R1，…，R9，R10存放在同一个磁道上，记录的存放顺序如下表所示：

物理块	1	2	3	4	5	6	7	8	9	10	11
逻辑记录	R0	R1	R2	R3	R4	R5	R6	R7	R8	R9	R10

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

A.33ms B.336ms C.366ms D.376ms
A.33ms B.66ms C.86ms D.93ms

【C、B】
读完每个物理块需要3ms，处理每个物理块需要3ms
当磁头在R0时读取R0信息，磁头紧接着旋转至R1（3ms），但此时磁头需要3ms时间以处理R0信息，故无法读取R1信息；磁头紧接着旋转至R2（3ms），此时磁头内容空，下一步磁头需要读取R1信息则需要依次通过R3~R10~R0 共10个物理块后（3ms10），才能下一步继续读取R1。当磁头读R1后，磁头旋转到R2（3ms），但磁头此时需要3ms时间以处理R1信息，故无法读取R2信息；磁头紧接着旋转至R3（3ms），此时磁头内容空，下一步磁头需要读取R2信息则需要依次通过R4~R10~R1 共10个物理块后（3ms10），才能下一步继续读取R2。以此类推，共需要10次循环，故10次循环共耗时36*10=360ms，加上R0的6ms，可以得到 360+6=366ms

优化存储分布后，即6ms*11=66ms，表格如下所示：

物理块	1	2	3	4	5	6	7	8	9	10	11
逻辑记录	R0	R6	R1	R7	R2	R8	R3	R9	R4	R10	R5

在磁盘调度管理中，应先进行移臂调度，再进行旋转调度。假设磁盘移动臂位于21号柱面上，进程请求序列如下表所示。如果采用最短移臂调度算法，那么系统的相应序列应为（）

请求序列	柱面号	磁头号	扇区号
1	17	8	9
2	23	6	3
3	23	9	6
4	32	10	5
5	17	8	4
6	32	3	10
7	17	7	9
8	23	10	4
9	38	10	8

A.283451769 B.238469157 C.123456789 D.283571469

【D】
磁盘移动臂初始位于21号柱面上，根据最短移臂调度算法得。系统首先响应柱面号为23的序列2，再以扇区从小到大响应，即序列为238；系统再次响应柱面号为17的序列1或者序列7（不看磁头号），再以扇区从小到大响应，即序列为571或517；系统再次响应柱面号为32的序列4，再以扇区从小到大响应，即序列为46；系统最后再响应柱面号为38的序列9。最后系统的响应序列应该为 283 517 46 9。

输入输出技术

内存与接口地址的编址方法

计算机系统中存在多种内存与接口地址的编址方法，常见的是下面两种： (1) 内存与接口地址独立编址方法内存地址和接口地址是完全独立的两个地址空间。访问数据时所使用的指令也完全不同，用于接口的指令只用于接口的读/写，其余的指令全都是用于内存的。因此，在编程序或读程序时很容易使用和辨认。这种编址方法的缺点是用于接口的指令太少、功能太弱。 (2) 内存与接口地址统一编址方法内存地址和接口地址统一在一个公共的地址空间里，即内存单元和接口共用地址空间。优点是原则上用于内存的指令全都可以用于接口，这就大大地增强了对接口的操作功能，而且在指令上也不再区分内存或接口指令。该编址方法的缺点在于整个地址空间被分为两部分，其中一部分分配给接口使用，剩余的为内存所用，这经常会导致内存地址不连续。

计算机和外设间的数据交互方式

(1) 程序控制（查询）方式：CPU主动查询外设是否完成数据传输，效率极低。

(2) 程序中断方式：外设完成数据传输后，向CPU发送中断，等待CPU处理数据，效率相对较高。中断响应时间指的是从发出中断请求到开始进入中断程序；中断处理时间指的是从中断处理开始到中断结束。中断向量提供中断服务程序的入口地址。多级中断嵌套，使用堆栈来保护断点和现场。

(3) DMA方式（直接主存存取）：CPU只需要完成必要的初始化等操作，数据传输的整个过程都由DMA控制器来完成，在主存和外设之间建立直接的数据通路，效率很高。

在一个总线周期结束后，CPU会响应DMA请求开始读取数据；CPU响应程序中断请求是在一条指令执行结束时。

首先中断请求，然后中断响应，关中断后最重要的两步是保存断点和保护现场，←以上为中断响应时间。接下来是中断处理时间→然后再执行开中断，执行中断服务程序，再关中断，恢复现场，再开中断，中断返回。

总线结构

总线（Bus），是指计算机设备和设备之间传输信息的公共数据通道。总线是连接计算机硬件系统内多种设备的通信线路，它的一个重要特征是由总线上的设备共享，因此可以将计算机系统内的多种设备连接到总线上。
从广义上讲，任意连接两个以上电子元器件的导线都可以称为总线，通常分为以下三类： (1) 内部总线：内部芯片级别的总线，芯片与处理器之间通信的总线。 (2) 系统总线：是板级总线，用于计算机内各部分之间的连接，具体分为数据总线（并行数据传输位数）、地址总线（系统可管理的内存空间的大小）、控制总线（传送控制命令）。代表的由ISA总线、EISA总线、PCI总线。 (3) 外部总线：设备一级的总线，微机和外部设备的总线。代表的由RS232（串行总线）、SCSI（并行总线）、USB（通用串行总线，即插即用，支持热插拔）

【真题】

计算机系统中常用的输入/输出控制方式有无条件传送、中断、程序查询和DMA方式等。当采用（）方式时，不需要CPU执行程序指令来传送数据。

A.中断 B.查询查询 C.无条件传送 D.DMA

【D】

以下关于总线的说法中，正确的是（）。

A.串行总线适合近距离高速数据传输，但线间串扰会导致速率受限
B.并行总线适合长距离数据传输，易提高通信时钟频率来实现高速数据传输
C.单总线结构在一个总线上适应不同种类的设备，设计复杂导致性能降低
D.半双工总线只能在一个方向上传输信息

【C】
串行适合长距离，是低速传输；并行适合短距离，是高速传输。
单总线结构同一时间只能有一个设备发送数据，但可同时接收数据。
单工总线：只能在一个方向上传输信息。
半双工总线：可以在两个方向上传输信息，但同一时刻只能在一个方向上传输信息。
全双工总线：可以在两个方向上传输信息，且同一时刻可以在两个方向上传输信息。

计算机可靠性

可靠性指标（理解概念即可）平均无故障时间MTTF= 1/失效率。平均故障修复时间MTTR= 1/修复率。平均故障间隔时间MTBF = MTTF+MTTR。系统可用性= MTTF/(MTTF + MTTR)*100%。
串并联系系统可靠性无论什么系统，都是由多个设备组成的，协同工作，而这多个设备的组合方式。可以是串联、并联，也可以是混合模式，假设每个设备的可靠性为R1，R2……Rn，则不同的系统的可靠性公式如下： 串联系统，一个设备不可靠，整个系统崩溃，整个系统可靠性R=R1*R2*…*Rn。 并联系统，所有设备都不可靠，整个系统才崩溃，整个系统的可靠性R=1 – (1-R1) * (1-R2) *…* (1-Rn)。 N模冗余系统：N模冗余系统由N个 (N= 2n + 1 ) 相同的子系统和一个表决器组成，表决器把N个子系统中占多数相同结果的输出作为输出系统的输出，如图所示。N个子系统中，只要有n+1个或n+1个以上的子系统能正常工作，系统就可以正常工作，输出正确结果。

【真题】

某系统的可靠性结构框图如下图所示，假设部件1、2、3的可靠度分别为0.90；0.80；0.80（部件2、3为冗余系统），若要求该系统的可靠度不小于0.85，则进行系统设计时，部件4的可靠度至少应为（）。

【A】
部件1可靠度 0.9；部件2、3可靠度均为0.8。假设部件4的可靠度为x。
串联系统的可靠性为 0.9 * ( ) * x >= 0.85
2、3的可靠性为 1-不可靠性，即当两个都不可靠时 (1-0.8) * (1-0.8)
得式子为 0.9* [1-(1-0.8)(1-0.8)]*x >= 0.85，则选A。

计组练习题

1.计算机中CPU对其访问速度最快的是（C）

A.内存 B.Cache C.通用寄存器 D.硬盘

解析：寄存器＞Cache＞内存＞硬盘

2.机器字长为n位的二进制数可以用补码来表示（A）个不同的有符号定点小数。

A.2^n B.2^(n-1) C.2^n -1 D.2^(n-1) +1

解析：在补码里，0只有一种表示方式，因此可以表示全2

^0个数值；但原码和反码可以表示的是 2^n -1个数值，因为原码和反码里0区分正0和负0

3.Cache 的地址映像方式中，发生块冲突次数最小的是（A）

A.全相联映像 B.组相联映像 C.直接映像 D.无法确定的

4.计算机中CPU的中断响应时间指的是（D）的时间

A.从发出中断请求到中断处理结束
B.从中断处理开始到中断处理结束
C.CPU分析判断中断请求
D.从发出中断请求到开始进入中断处理程序

5.总线宽度为 32bit，时钟频率为 200MHz，若总线上每 5 个时钟周期发送一个 32bit的字，则该总线的宽度为（C）MB/s

A.40 B.80 C.160 D.200

解析：一个时钟周期为 1/200M 秒，5个时钟周期就是 5/200M 秒，传送32bit，那么总线宽度就说用传输数据除以时间，即 32bit/(5/200M)= 160MB/s

6.以下关于指令流水线性能度量的叙述中，错误的是（D）

A.最大吞吐率取决于流水线中最慢一段所需时间
B.如果流水线出现断流，加速比会明显下降
C.要使加速比和效率最大化应该对流水线各级采用相同的运行时间
D.流水线采用异步控制会明显提高其性能

解析：流水线最理想的就是各级运行时间相同，这样可以保证无延迟；流水线是一种同步控制机制。

7.CPU是在（D）结束时响应DMA请求的

A.一条指令执行 B.一段程序

C.一个时钟周期 D.一个总线周期

解析：在一个总线周期结束后，CPU会响应DMA请求开始读取数据；CPU响应程序中断方式请求是在一条指令执行结束时；区分指令执行结束和总线周期结束。

8.虚拟存储体系由（A）两级存储器构成的

A.主存-辅存 B.寄存器-Cache

C.寄存器-主存 D.Cache-主存

9.浮点数能够表示的数的范围是由其（B）的位数决定的

A.尾数 B.阶码 C.数符 D.阶符

解析：浮点数的范围由阶码决定，精度由尾数决定。

10.在机器指令的地址字段中，直接指出操作数本身的寻址方式称为（D）

A.隐含寻址 B.寄存器寻址 C.立即寻址 D.直接寻址

解析：指令地址字段，操作数地址存储的就是操作数本身，是立即寻址。

11.内存按字节编址从 B3000H 到 DABFFH 的区域其存储容量为（B）

A. 123KB B. 159KB C. 163KB D. 194KB

12.CISC是（A）的简称

A.复杂指令系统计算机 B.超大规模集成电路
C.精简指令系统计算机 D.超长指令字

解析： C是complex，是复杂指令系统

13.VLIW是（D）的简称

A.复杂指令系统计算机 B.超大规模集成电路
C.单指令流多数据流 D.超长指令字

解析：A选项首个单词复杂英文是Complex，以C开头；C选项首个单词单个英文是single，以S开头；D选项超长指令字英文是 very long instruction word。

14.主存与Cache的地址映射方式中，（A）方式可以实现主存任意一块装入Cache中任意位置，只有装满才需要替换。

A.全相联 B.直接映射 C.组相联 D.串并联

15.如果“2X”的补码是“90H”，那么X的真值是（B）

A.72 B.-56 C.56 D.111

16.移位指令中的（A）指令的操作结果相对于对操作数进行乘2操作

A.算术左移 B.逻辑右移 C.算术右移 D.带进位循环左移

17.内存按字节编址，从 A1000H 到 B13FFH 的区域的存储容量为（C）KB

A.32 B.34 C.65 D.67

18.以下关于总线的叙述中，不正确的是（C）。

A.并行总线适合近距离高速数据传输
B.串行总线适合长距离数据传输
C.单总线结构在一个总线上适应不同种类的设备，设计简单且性能很高
D.专用总线在设计上可以与连接设备实现最佳匹配

19.在程序运行过程中，CPU需要将指令从内存中取出并加以分析和执行。CPU依据（A）来区分在内存中以二进制编码形式存放的指令和数据。

A.指令周期的不同阶段 B.指令和数据的寻址方式
C.指令操作码的译码结果 D.指令和数据所在的存储单元

解析：在指令周期的不同阶段，指令会命令CPU分别去取指令或数据。因此CPU是依据指令周期的不同阶段的命令去区分的。

20.计算机在一个指令周期的过程中，为从内存读取指令操作码，首先要将（C）的内容送到地址总线上。

A.指令寄存器（IR） B.通用寄存器（GR）
C.程序计数器（PC） D.状态寄存器（PSW）

解析：首先需要知道指令存放地址，才可以取出指令。指令的存放地址在程序计数器PC中。

21.设16位浮点数，其中阶符1位、阶码值6位、数符1位、尾数8位。若阶码用移码表示，尾数用补码表示，则该浮点数能表示的数值范围是（B）

A.-2^64^ ~ (1-2^-8^)*2^64^
B.-2^63^ ~ (1-2^-8^)*2^63^
C.-2^64^ ~ (1-2-(1-2^-8^) 2^64^ ~ (1-2^-8^)*2^64^)
D.-(1-2^-8^)*2^63^ ~ (1-2^-8^)*2^63^

22.已知数据信息为16位，最少应附加（C）位校验位，以实现海明码纠错。

A.3 B.4 C.5 D.6

23.将一条指令的执行过程分解位取指令、分析和执行三步，按照流水方式执行，若取指时间t 取指=4Δt、分析时间t分析=2Δt、执行时间t 执行=3Δt，则执行完100条指令，需要的时间为（D）Δt

A.200 B.300 C.400 D.405

解析：流水线中最长执行时间步骤为流水线周期，就是4。而后依据流水线指令的执行时间公式，可得时间为 4+2+3+(100-1)*4=405

24.以下关于Cache与主存间地址映射的叙述中，正确的是（D）

A.操作系统负责管理Cache 与主存之间的地址映射
B.程序员需要通过编程来处理Cache 与主存之间的地址映射
C.应用软件对Cache 与主存之间的地址映射进行调度
D.由硬件自动完成Cache 与主存之间的地址映射

25.CPU执行算术运算或者逻辑运算时，常将源操作数和结果暂存在（B）中

A.程序计数器（PC） B.累加器（AC）
C.指令寄存器（IR） D.地址寄存器（AR）

26.要判断字长为16位的整数a的低四位是否全为0，则（A）

A.将a 与 0x000F 进行“逻辑与”运算，然后判断运算结果是否等于0
B.将a 与 0x000F 进行“逻辑或”运算，然后判断运算结果是否等于F
B.将a 与 0x000F 进行“逻辑异或”运算，然后判断运算结果是否等于O
B.将a 与 0x000F 进行“逻辑与”运算，然后判断运算结果是否等于F

27.计算机系统中常用的输入/输出控制方式有无条件传送、中断、程序查询和DMA方式。当采用（D）方式时，不需要CPU执行程序指令来传送数据。

A.中断 B.程序查询 C.无条件传送 D.DMA

28.某系统由下图所示的冗余部件构成。若每个部件的千小时可靠度都为R，则该系统的千小时可靠度为（B）

A.(1-R^3^)(1-R^2^) B.(1-(1-R)^3^)(1-(1-R)^2^)
C.(1-R^3^)+(1-R^2^) D.(1-(1-R)^3^)+(1-(1-R)^2^)

29.以下关于Cache（高速缓冲存储器）的叙述中，不正确的是（A）

A.Cache 的设置扩大了主存的容量
B.Cache 的内容是主存部分内容的拷贝
C.Cache 的命中率并不随其容量增大线性地提高
D. Cache 位于主存与 CPU之间

30.在程序执行的过程中，Cache与主存的地址映射是由（C）完成的

A.操作系统 B.程序员调度 C.硬件自动 D.用户软件

31.某四级指令流水线分别完成取指、取数、运算、保存结果四步骤。若完成上述操作的时间依次为8ns、9ns、4ns、8ns，则该流水线的操作周期至少为（C）ns。

A.4 B.8 C.9 D.33

32.内存按字节编址。若用存储容量为 32K*8bit 的存储器芯片构成地址从 A0000H 到 DFFFFH 的内存，至少需要（B）片芯片。

A.4 B.8 C.16 D.32

33.计算机系统的主存主要是由（）构成的。

A.DRAM B.SRAM C.Cache D.EEPROM

解析：主存即内存。RAM是随机存储器，其中SRAM读写速度快，价格昂贵，一般是制作Cache；DRAM读写速度相对较慢，容量大价格低，用于制作主存。

34.以下关于海明码的叙述中，正确的是（A）

A.海明码利用就行进行检错和纠错
B.海明码的码距为 1
C.海明码可以检错但不能纠错
D.海明码中数据为的长度与校验位的长度必须相同

35.浮点数的表示分为阶和尾数两部分。两个浮点数相加时，需要先对阶，即（D）（n 为阶差的绝对值）。

A.将大阶向小阶对齐，同时将尾数左移 n 位
B.将大阶向小阶对齐，同时将尾数右移 n 位
C.将小阶向大阶对齐，同时将尾数左移 n 位
D.将小阶向大阶对齐，同时将尾数右移 n 位

解析：举例：

浮点数 A：阶码为 5，尾数为 0.1101（二进制），实际值为 0.1101×2^5^。
浮点数 B：阶码为 3，尾数为 0.1010（二进制），实际值为 0.1010×2^3^。
对阶过程：
1. 比较阶码：
2. 将小阶向大阶对齐：
  将 B的阶码从 3 调整为 5，同时将其尾数右移 2 位（因为阶差是 2）。
3. 调整尾数：
  B 的尾数原来是 0.1010，右移 22 位后变为 0.001010（注意右移后高位补零）。
4. 调整后的浮点数：
  - A 保持不变：0.1101×2^5^。
  - B 调整为：0.001010×2^5^。
总结：
- 对阶：将小阶向大阶对齐，尾数右移 n 位（n 为阶差）。
- 相加：对齐后直接对尾数相加。

操作系统

操作系统概述

操作系统定义：能有效地组织和管理系统中各种软/硬件资源，合理地组织计算机系统工作流程，控制程序的执行，并且向用户提供一个良好的工作环境和友好的接口
操作系统有两个重要的作用：第一、通过资源管理提高计算机系统的效率；第二、改善人机界面向用户提供友好的工作环境。
操作系统的四个特征：
1. 并发性
2. 共享性
3. 虚拟性
4. 不确定性

操作系统的功能

进程管理。实质上是对处理及的执行“时间”进行管理，采用多道程序等技术将CPU的时间合理地分配给每个任务，主要包括进程控制、进程同步、进程通信和进程调度。
文件管理。主要包括文件存储空间管理、目录管理、文件的读/写管理和存取控制。
存储管理。存储管理是对主存储器“空间”进行管理，主要包括存储分配与回收、存储保护、地址映射（变换）和主存扩充。
设备管理。实质是对硬件设备的管理，包括对输入/输出设备的分配、启动、完成和回收。
作业管理。包括任务、界面管理、人机交互、图形界面、语音控制和虚拟现实等。

操作系统的分类

批处理操作系统：单道批处理和多道批处理（主机与外设可并行）
分时操作系统：一个计算机系统与多个终端设备连接。将CPU的工作时间划分为许多很短的时间片，轮流为各个终端的用户服务。
实时操作系统：实时是指计算机对于外来信息能够以足够快的速度进行处理，并在被控对象允许的时间范围内做出快速反应。实时系统对交互能力要求不高，但要求可靠性有保障。
网络操作系统：是使联网计算机能方便而有效地共享网络资源，为网络用户提供各种服务的软件和有关协议的集合。三种模式：集中模式、客户端/服务器模式、对等模式。
分布式操作系统：分布式计算机系统是由多个分散的计算机经连接而成的计算机系统，系统中的计算机无主次之分，任意两台计算机可以通过通信交换信息。
微型计算机操作系统：简称微机操作系统，常用的由Windows、MacOS、Linux。
嵌入式操作系统主要特点： (1) 微型化。从性能和成本角度考虑，希望占用的资源和系统代码量少，如内存少、字长短、运行速度有限、能源少（用微小型电池） (2) 可定制。从减少成本和缩短研发周期考虑，要求嵌入式操作系统能运行在不同的微处理器平台上，能针对硬件变化进行结构与功能上的配置，以满足不同应用需要。 (3) 实时性。嵌入式操作系统主要应用于过程控制、数据采集、传输通信、多媒体信息及关键要害领域需要迅速响应的场合，所以对实时性要求较高。 (4) 可靠性。系统构件、模块和体系结构必须达到应有的可靠性，对关键要害应用还要提供容错和防故障措施。 (5) 易移植性。为了提高系统的易移植性，通常采用硬件抽象层和板级支撑包的底层设计技术。嵌入式系统初始化过程按照自底向上、从硬件到软件的次序依次为：片级初始化→板级初始化→系统初始化。

进程组成和状态

进程的组成：进程控制块PCB（唯一标志）、程序（描述进程要做什么）、数据（存放进程执行时所需数据）。
进程基础的状态是下左图的三态图。需要熟练掌握左下图的进程三态之间的转换。

【真题】

在单处理机系统中，采用先来先服务调度算法。系统中有4个P1、P2、P3、P4（假设进程按此顺序到达），其中P1为运行状态，P2为就绪状态，P3和P4为等待状态，且P3等待打印机，P4等待扫描仪。若P1（），则P1、P2、P3和P4的状态应分别为（）。

A.时间片到 B.释放了扫描仪 C.释放了打印机 D.已完成
A.等待、就绪、等待和等待 B.运行、就绪、运行和等待
C.就绪、运行、等待和等待 A.就绪、就绪、等待和运行

前趋图

用来表示哪些任务可以并行执行，哪些任务之间有顺序关系，具体如下图：可知，A B C可以并行执行，但是必须A B C都执行完毕后，才可以执行D，这就确定了两点：任务间的并行、任务间的先后顺序。

进程资源图

用来表示进程和资源之间的分配和请求关系，如下图所示： P 代表进程，R 代表资源。R 方框中有几个圆球就表示有几个这种资源，在上图中，R1 指向 P1，表示 R1 有一个资源已经分配给了 P1 ，P1 指向 R2，表示 P1 还需要请求一个 R2 资源才能执行。阻塞节点：某进程所请求的资源已经全部分配完毕，无法获取所需资源，该进程被阻塞了无法继续。如上图中的 P2。非阻塞节点：某进程所请求的资源还有剩余，可以分配给该进程继续运行。如上图中 P1、P3。当一个进程资源图中所有进程都是阻塞节点时，即陷入死锁状态。

【真题】

在如下所示的进程资源图中，（）；该进程资源图是（）。

A. P1、P2、P3都是阻塞节点
B. P1是阻塞节点、P2、P3是非阻塞节点
C. P1、P2是阻塞节点、P3是非阻塞节点
D. P1、P2是非阻塞节点、P3是阻塞节点

A. 可以化简的，其化简顺序为P1->P2->P3
B. 可以化简的，其化简顺序为P3->P1->P2
C. 可以化简的，其化简顺序为P2->P1->P3
D. 不可以化简的，因为P1、P2、P3申请的资源都不能得到满足

【C、B】
P3是非阻塞节点。
可以化简：最后能不能执行完，不进入到死锁状态。唯一能运行的是P3。

进程同步与互斥

临界资源：各进程间需要以互斥方式对其进行访问的资源。
临界区：指进程中对临界资源实施操作的那段程序。本质是一段程序代码。
互斥：某资源（即临界资源）在同一时间内只能由一个任务单独使用，使用时需要加锁，使用完后解锁才能被其他任务使用；如打印机。
同步：多个任务可以并发执行，只不过有速度上的差异，在一定情况停下等待，不存在资源是否单独或共享的问题；如自行车和汽车。
互斥信号量：对临界资源采用互斥访问，使用互斥信号量后其他进程无法访问，初值为1。
同步信号量：对共享资源的访问控制，初值一般是共享资源的数量。
P操作：申请资源，S=S-1，若S>=0，则执行P操作的进程继续执行；若S<0，则置该进程为阻塞状态（因为无可用资源），并将其插入阻塞队列。
V操作：释放资源，S=S+1，若S>0，则执行V操作的进程继续执行；若S<=0，则从阻塞状态唤醒一个进程，并将其插入就绪队列（此时因为缺少资源被操作阻塞的进程可以继续执行），然后执行V操作的进程继续。
经典问题：生产者和消费者的问题三个信号量：互斥信号量S0（仓库独立使用权），同步信号量S1（仓库空闲个数），同步信号量S2（仓库商品个数）。生产者流程：消费者流程：生产一个商品 S P(S0) P(S0) P(S2) P(S1) 取出一个商品将商品放入仓库中 V(S1) V(S2) V(S0) V(S0) 进程P1、P2、P3、P4和P5的前趋图如下图所示：

【真题】

若用PV操作控制进程P1、P2、P3、P4和P5并发执行的过程，则需要设置5个信号S1、S2、S3、S4和S5，且信号量S1~S5的初值都等于0。下图中a和b处应分别填（26）；c和d处应分别填写（27）；e和f处应分别填写（28）。

26、A. V(S1)、P(S2)和V(S3)
B. P(S1)、V(S2)和V(S3)
C. V(S1)、V(S2)和V(S3)
D. P(S1)、P(S2)和V(S3)

27、A. P(S2)和P(S4)
B. P(S2)和V(S4)
C. V(S2)和P(S4)
D. V(S2)和V(S4)

28、A. P(S4)和V(S2)、V(S5)
B. V(S5)和P(S4)、P(S5)
C. V(S3)和V(S4)、V(S5)
D. P(S3)和P(S4)、P(S5)

【C、B、B】

进程P1、P2、P3、P4、P5和P6的前趋图如下所示，若用PV操作控制这6个进程的同步与互斥的程序如下，那么程序中的空①和空②处应分别为（）；空③和空④处应分别为（）；空⑤和空⑥处应分别为（）。

【C、B、D】

进程调度

进程调度方式是指当有更高优先级的进程到来时如何分配CPU。分为可剥夺和不可剥夺两种。可剥夺指当有更高优先级进程到来时，强行将正在运行进程的CPU分配给高优先级进程；不可剥夺是指高优先级进程必须等待当前进程自动释放CPU。
在某些操作系统中，一个作业从提交到完成需要经历高、中、低三级调度。 (1) 高级调度。又称为“长调度”“作业调度”“接纳调度”，它决定处于输入池中的哪个后作业可以调入………………（后续只考虑重点知识点、真题）
先来先服务FCFS：先到达的进程优先分配CPU。用于宏观调度。
时间片轮转：
优先级调度：
多级反馈调度：

死锁

当一个进程在等待永远不可能发生的事件时，就会产生死锁，若系统中有多个进程处于死锁状态，就会造成系统死锁。

死锁产生的四个必要条件：资源互斥、每个进程占有资源并等待其他资源、系统不能剥夺进程资源、进程资源图是一个环路。

解决措施

死锁预防
死锁避免银行家算法
死锁检测允许死锁产生，系统定时运行一个检测死锁的程序，若检测到系统中发生死锁，则设法加以解除。
死锁解除死锁发生后的解除办法，如强制剥夺资源，撤销进程等。

死锁资源计算：系统内有n个进程，每个进程都需要R个资源。发生死锁最大资源数 n*(R-1)，其不会发生死锁的最小资源数为 n*(R-1)+1

【真题】

某系统中有3个并发进程竞争资源R，每个进程都需要 5 个R，那么至少有（）个R，才能保证系统不会发生死锁

13个。 n*(R-1)+1= 3*(5-1)+1=13

假设系统中有n个进程共享3台打印机，任一进程在任一时刻最多只能使用1台打印机。若用PV操作控制n个进程使用打印机，则相应信号量S的取值范围为（）；若信号量S的值为-3，则系统中有（）个进程等待使用打印机。

3，2，1，0，-1，……，-(n-3)

银行家算法真题：假设系统有三类互斥资源R1、R2和R3，可用资源数分别为10、5和3。在T0时刻系统有P1、P2、P3、P4和P5五个进程，这些进程对资源的最大需求和已分配资源数如下表所示，此时系统剩余的可用资源数分别为（）。如果进程按（）序列执行，那么系统状态是安全的。

2、0和1

A.P1-P2-P4-P5-P3
B.P5-P2-P4-P3-P1
C.P4-P2-P1-P5-P3
D.P5-P1-P4-P2-P3

【B】

线程

传统的进程有两个属性：可拥有资源的独立单位；可独立调度和分配的基本单位。

分区存储管理

分区存储组织，就是整存，将某个进程运行所需的内存整体一起分配给它，然后再执行。有三种分区方式：

固定分区静态分区方法，将主存分为若干个固定的分区，将要运行的作业装配进去，由于分区固定，大小和作业需要的大小不同，会产生内部碎片。
可变分区动态分区方法，主存空间的分区是在作业转入时划分，正好划分为作业需要的大小，这样就不存在内部碎片，但容易将整片主存空间切割成许多块，会产生外部碎片。
可重定位分区可以解决碎片问题，移动所有已经分配好的区域，使其成为一个连续的区域，这样其他外部细小的分区碎片可以合并为大的分区，满足作业要求。

系统分配内存算法：

首次适应法
最佳适应法
最差适应法
循环首次适应法

分页存储管理

逻辑页分为页号和页内地址，页内地址就是物理偏移地址，而页号与物理块号并非按序对应的，需要查询页表，才能得知页号对应的物理块号，再用物理块号加上偏移地址才得出了真正运行时的物理地址。

优点：利用率高，碎片小，分配及管理简单。
缺点：增加了系统开销，可能产生抖动现象。

2^20^个页，则页号为20个
4KB=2^12^个，则页内地址为12个

页号	页内地址
31、30、……、11、12 （20个）	11、10、……、1、0 （12个）

页面置换算法

最优算法：OPT，理论上的算法，无法实现，是在进程执行完后进行的最佳效率计算，用来让其他算法比较差距。原理是选择未来最长时间内不被访问的页面置换，这样可以保证未来执行的都是马上要访问的。
先进先出算法：FIFO，先调入内存的页最先被置换淘汰，产生抖动现象，即分配页数越多，缺页率可能越多（即效率越低）
最近最少使用：LRU
淘汰原则：优先淘汰最近未访问的，而后淘汰最近未修改的页面。

快表

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

快表是将页表存于Cache中；慢表是将页表存于内存上。慢表需要访问两次内存才能取出页，而快表是访问一次Cache和一次内存，因此更快。

【真题】

某计算机系统页面大小为4K，若进程的页面变换表如下所示，逻辑地址为十六进制1D16H。该地址经过变换后，其物理地址应为十六进制（）

页号	物理块号
0	1
1	3
2	4
3	6

3D16H

某进程有4个页面，页号为0~3，页面变换表及状态位、访问位和修改位的含意如下图所示，若系统给该进程分配了3个存储块，当访问签页面1不在内存时，淘汰表中页号为（）的页面代价最小。

页号	页帧号	状态位	访问位	修改位
0	6	1	1	1
1	–	0	0	0
2	3	1	1	1
3	2	1	1	0

页号3
根据局部性原理，应优先淘汰最近未被访问过的，而后淘汰最近未被修改过的，有页表得知，023最近都被访问过，只有3最近违背修改过，应该淘汰3。

分段存储管理

将进程空间分为一个个段，每段也有段号和段内地址，与页式存储不同的是，每段物理大小不同，分段是根据逻辑整体分段的，因此，段表与页表的内容不同，页表中直接是逻辑页号对应物理块号，而下图所示，段表有段厂和基址两个属性，才能确定一个逻辑段在物理段中的位置。

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

【真题】

设某进程的段表如下所示，逻辑地址（）可以转换为对应的物理地址。

段号	基地址	段长
0	1598	600
1	486	50
2	90	100
3	1327	2988
4	1952	960

A.(0,1597)、(1,30)和(3,1390)
B.(0,128)、(1,30)和(3,1390)
C.(0,1597)、(2,98)和(3,1390)
D.(0,128)、(2,98)和(4,1066)

【B】
段号0中，128<=600，段号1中，30<=50，段号3中，1390<=2988

段页式存储管理

（从来没考过）

对进程空间先分段后分页

优点：空间浪费小、存储共享容易、存储保护容易、能动态链接。
缺点：由于管理软件的增加，复杂性和开销页增加。

设备管理概述

设备是计算机系统与外界交互的工具，具体负责计算机与外部的输入/输出工作，所以常称为外部设备（简称外设）。

I/O软件

实例：当用户程序试图读一个硬盘文件时，需要通过操作系统实现这一操作。
与设备无关软件检查高速缓存中有无要读的数据块，若无，则调用设备驱动程序，向I/O硬件发出一个请求。
然后，用户进程阻塞并等待磁盘操作的完成。当磁盘操作完成时，硬件产生一个中断，转入中断处理程序。
中断处理程序检查中断的原因，认识到这是磁盘读取操作已经完成，于是唤醒用户进程取回从硬盘读取的信息，从而结束这次I/O请求。
用户进程在得到了所需的硬盘文件内容之后继续运行。

设备管理技术

一台独占设备，在同一时间只能由一个进程使用，其他进程只能等待，且不知道什么时候打印机空闲，此时，极大得浪费了外设的工作效率。

引入了SPOOLING（外围设备联机操作）技术，就是在外设上建立两个数据缓冲区，只需要将打印命令发出，数据就会排队存储在缓冲区中，打印机会自动按顺序打印，实现了物理外设的共享，使得每个进程都感觉在使用一个打印机，这就是物理设备的虚拟化。如下图所示：

【真题】

以下关于I/O软件的叙述中，正确的是（）

A.I/O软件开放了I/O操作实现的细节，方便用户使用I/O设备
B.I/O软件隐藏了I/O操作实现的细节，向用户提供物理接口
C.I/O软件隐藏了I/O操作实现的细节，方便用户使用I/O设备
D.I/O软件开放了I/O操作实现的细节，用户可以使用逻辑地址访问I/O设备

【C】
I/O软件隐藏了底层复杂的实现细节，只提供接口供用户方便地使用。

文件管理的概述

（不怎么考）

文件是具有符号名的、在逻辑上具有完整意义的一组相关信息项的集合。

文件的逻辑结构：有结构的记录式文件；无结构的流式文件。
文件的物理结构是指文件在物理存储设备上的存放方法，包括： (1) 连续结构 (2) 链接结构串联结构，它将逻辑上连续的文件信息（如记录）存放在不连续的物理块上，每个物理块设有一个指针指向下一个物理块。 (3) 索引结构 将逻辑上的连续信息（如记录）存放在不连续的物理块中，系统为每个文件建立一张索引表。索引表记录了文件信息所在的逻辑块号对应的物理块号，并将索引表的起始地址放在与文件对应的文件目录项中。 (4) 多个物理块的索引表在文件创建时由系统自动建立

索引文件结构

如图所示，系统中由13个索引节点，0-9为直接索引，即每个索引节点存放的是内容，假设每个物理盘大小为4KB，共可存4KB*10=40KB数据；

10号索引节点为一级间接索引节点，大小为4KB，存放的并非直接数据，而是链接到直接物理盘块的地址，假设每个地址占4B，则共有1024个地址，对应1024个物理盘，可存1024*4KB=4096KB数据。

二级索引节点类似，直接盘存放一级地址，一级地址再存放物理盘块地址，而后链接到存放数据的物理盘块，容量又扩大了一个数量级，为1024*1024*4KB数据。

【真题】

设文件索引节点中有8个地址项，每个地址项大小为4字节，其中5个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，磁盘索引块和磁盘数据块大小均为1KB，若要访问文件的逻辑块号分别为5和518，则系统应分别采用（），而且可表示的单个文件最大长度是（）KB。

A.直接地址索引和一级间接地址索引
B.直接地址索引和二级间接地址索引
C.一级间接地址索引和二级间接地址索引
D.一级间接地址索引和一级间接地址索引

A.517
B.1029
C.16513
D.66053

【C、D】
直接索引地址：0-4；一级间接地址索引1KB/4B=256个；二级间接地址索引可以存储1KB/4B=256个一级间接地址索引，即256KB*256KB。

文件目录

文件控制块中包含以下三类信息：基本信息类，存取控制信息类和使用信息类。

文件控制块的有序集合称为文件目录。

相对路径：是从当前路径开始的路径。
绝对路径：是从根目录开始的路径。
全文件名 = 绝对路径+文件名。

【真题】

若某文件系统的目录结构如下图所示，假设用户要访问文件Fault.swf，且当前工作目录为swshare，则该文件的全文件名为（），相对路径和绝对路径分别为（）。

【D、B】
路径最后一个可以省略。D中“ flash” 前面那个代表根目录，不能乱加。

文件存储空间管理

文件存取方法是指读/写文件存储器上的一个物理块的方法。通常有顺序存取和随机存取两种方法。

文件存储空间的管理：

空闲区表。适用于连续文件结构。将外存空间上的一个连续的未分配区域称为“空闲区”。操作系统为磁盘外存上的所有空闲区建立一张空闲表，每个表项对应一个空闲区。序号第一个空闲块号空闲块数状态 1 18 5 可用 2 29 8 可用 3 105 19 可用 4 — — 未用
位示图。这种方法是在外存上建立一张位示图（Bitmap），记录文件存储器的使用情况。每一位对应文件存储器上的一个物理块，取值 0 和1 分别表示空闲和占用。第 0 字节 1 0 1 0 0 1 …… 0 1 第1字节 0 1 1 1 0 0 …… 1 1 第…字节 0 0 0 0 0 0 …… 0 0
空闲块链。每个空闲物理块中有指向下一个空闲物理块的指针，所有空闲物理块构成一个链表。
成组链接法。例如，在实现时系统将空闲块分成若干组，每100个空闲块为一组，每组的第一个空闲块等级了下一组空闲块的物理盘块号和空闲块总数。假设某个组的第一个空闲块号等于0，意味着该组是最后一组，无下一组空闲块。

【真题】

某文件管理系统采用位示图（bitmap）记录磁盘的使用情况。如果系统字长为32位，磁盘物理块的大小为4MB，物理块依次编号为：0，1，2、……，位示图字依次编号为：0、1、2、……，那么16385号物理块的使用情况在位示图中的第（）个字中描述；如果磁盘的容量为1000GB，那么位示图需要（）个字来表示。

A. -128
B. 256
C. 512
D. 1024

A. 1200
B. 3200
C. 6400
D. 8000

【C、D】
16385 / 32 = 512……1，所以需要513个字，即0~512号
1000GB / 4MB = 250*2^10^ bit，250*2^10^ bit / 32 bit = 250 * 32 = 8000
即位示图需要 8000个字来表示。

操作系统练习题

若某企业拥有的总资金数为15，投资4个项目P1、P2、P3、P4，各项目需要的最大资金数分别是6、8、8、10，企业资金情况如表a所示。P1新申请2个资金，P2新申请1个资金，若企业资金管理处为项目P1和P2分配新申请的资金，则P1、P2、P3、P4尚需的资金数分别为（）；假设P1已经还清所有投资款，企业资金使用情况如表b所示，那么企业的可用资金数（）。若在图b所示的情况下，企业资金管理处为P2、P3、P4各分配资金数2、2、3，则分配后P2、P3、P4已用资金数分别为（）。

项目	最大资金	已用资金	尚需资金
P1	6	2	4
P2	8	3	5
P3	8	2	6
P4	10	3	7

项目	最大资金	已用资金	尚需资金
P1	—	—	—
P2	8	3	5
P3	8	2	6
P4	10	3	7

C.2、4、6、7，可用资金数为2，故资金周转状态是安全的

D.7

D.5、4、6，尚需资金数分别为3、4、4，故资金周转状态是不安全的

假设一台按字节编址的16位计算机系统，采用虚拟页式存储管理方案，页面的大小为2K，且系统中没有使用快表（或联想存储器）。某用户程序如图a所示，该程序的页面变换表如图b所示，表中状态位等于 1和0 分别表示页面在内存或不在内存。

【C B C】
MOVE指令放在内存的2047单元，实际上存放在第0页的最后一个单元和第1页的第1个单元中。同理，操作数Data1在第2页的最后一个单元和第3页的第一个单元中；Data2同理。
由图b知道，1、2、3、4和5号页面不在内存，该指令跨越两个页面0、1，查页面变换表可以发现1号不在内存，所以需要产生一次缺页中断；取地址为Data1的操作数时，由于该操作数不在内存且跨两个个页面2、3，需要将2、3页面装入内存，故产生两次缺页中断；同理取Data2的操作数时，需要将4、5页面装入内存，故产生两次缺页中断。因此执行该MOVE指令共产生5次缺页中断。

某计算机系统中有一个CPU、一台输入设备和一台输出设备，假设系统中有三个作业T1、T2和T3，系统采用优先级调度，且T1优先级＞T2优先级＞T3优先级。若每个作业具有三个程序段：输入Ii、计算Ci和输出Pi（i=1，2，3），执行顺序为Ii、Ci、Pi，则这三个作业各程序段并发执行的前趋图如下所示，图中①②分别为（），③④分别为（），⑤⑥分别为（）。

【①②：I2I3、③④：C1C2、⑤⑥：P2P3】

假设某分时系统采用简单时间片轮转法，当系统中的用户数为n、时间片为q时，系统对每个用户的相应时间T=（）

n*q

数据库技术基础【重要】

数据

数据：是数据库中存储的基本对象，是描述事物的符号记录。
种类：文本、图像、音频、视频等。

数据库DB：是长期存储在计算机内、有组织、可共享的大量数据的集合。

数据库的基本特征：
数据按一定的数据模型组织、描述和存储；
可为各种用户共享；
冗余度较小；
数据独立性较高；
易扩展。

数据库系统DBS：是一个采用了数据库技术，有组织地、动态地存储大量相关数据，方便多用户访问的计算机系统。

数据库管理系统DBMS的功能：
实现对共享数据有效的组织、管理和存取。
包括数据定义、数据库操作、数据库运行管理、数据库存储管理、数据库的建立和维护等。

三级模式-两级映像

内模式：管理如何存储物理的数据，对应具体物理存储文件。

模式：概念模式，就是我们常用的基本表，根据应用需求将物理数据划分成一张张表。

外模式：对应数据库中的视图这个级别，将表进行一定的处理后再提供给用户使用

外模式-模式映像：是表和视图之间的映射，存在于概念级和外部级之间，若表中数据发生了修改，只需要修改此映射，而无需修改应用程序。

模式-内模式映像：是表和数据的物理存储之间的映射，存在于概念级和内部级之间，若修改了数据存储方式，只需要修改此映射，而不需要修改应用程序。

数据库设计

需求分析：即分析数据存储的要求，产出物有数据流图、数据字典、需求说明书。
概念结构设计：就是设计E-R图，也就是实体-联系图，与物理实现无关，说明有哪些实体，实体有哪些属性。
逻辑结构设计：将E-R图，转换成关系模式，也就是转换成实际的表和表中的列属性。
物理设计：根据生成的表等概念，生成物理数据库。

【真题】

在数据库系统中，数据库的视图、基本表和存储文件的结构分别于（）对应；数据的物理独立性和数据的逻辑独立性是分别通过修改（）来完成的。

外模式、模式、内模式
模式与内模式之间的映像、外模式与模式之间的映像

在数据库逻辑结构设计阶段，需要（）阶段形成的（）作为设计依据

A.需求分析
B.概念结构设计
C.物理结构设计
D.数据库运行和维护

A.需求文档、数据字典和数据流图
B.需求说明文档、程序文档和数据流图
C.需求说明文档、数据字典和数据流图
D.需求说明文档、数据字典和程序文档

【A、C】

数据模型

关系模型是二维表的形式表述的实体-联系模型

概念模型是从用户角度进行建模的，E-R，是现实世界到信息世界的第一抽象。

数据模型三要素：数据结构（所研究的对象类型的集合）、数据操作（对数据库中各种对象的实例允许执行的操作的集合）、数据的约束条件（一组完整性规则的集合）。

用E-R图来描述概念数据模型，世界是由一组称为实体的基本对象和这些对象之间的联系构成的。

在E-R模型中，使用椭圆表示属性、长方形表示实体、菱形表示联系，联系的两端要填写联系类型，示例如下：

实体：客观存在并可相互区别的事物。
弱实体和强实体：弱实体依赖于强实体的存在而存在。
实体集：具有相同类型和共享相同属性的实体的集合。
属性：实体所具有的特性。
属性分类：简单属性和复合属性；单值属性和多值属性；NULL属性；派生属性（可以计算出的）。
域：属性的取值范围称为该属性的域。
码（key）：唯一标识实体的属性集。
联系
联系类型：（一对一、一对多、多对多）。
两个以上实体型的联系：
关系模型中数据的逻辑结构是一张二维表，由行列组成。用表格结构表达实体集，用外键标识实体间的联系。如下图：

E-R模型转换为关系模型：每一个实体都对应一个关系模式；联系分三种：

1：1联系中，连续可以放到任意两端实体中，作为一个属性（要保证1：1的两端关联），也可以转换为一个单独的关系模式；

1：N的联系中，联系也可以单独作为一个关系模式，也可以在N端中加入1端实体的主键；

N：N的联系中，联系必须作为一个单独的关系模式，其主键是M和N端的联合主键。

【真题】

某本科高校新建教务管理系统，支撑各学院正常的教学教务管理工作。经初步分析，系统中包含的实体有学院、教师、学生、课程等。考虑需要将本科学生的考试成绩及时通报给学生家长，新增家长实体；考虑到夜大、网络教育学生管理方式的不同，需要额外的管理数据，新增进修学生实体：规定一个学生可以选择多门课程，没门课程可以被多名学生选修；一个教师可以教授多门课程，一门课程只能被一名教师讲授。（）实体之间为多对多联系，（）属于弱实体对强实体的依赖联系。

A.学生、学院
B.教师、学院
C.学生、课程
D.教师、课程

A.家长、学生
B.学生、教师
C.学生、学院
D.教师、学院

【C、A】

部门、员工和项目的关系模式及它们之间的E-R图如下所示，其中关系模式中带下划线的属性表示主键属性。图中：
部门（部门代码，部门名称，电话）
员工（员工代码，姓名，部门代码，联系方式，薪资）
项目（项目编号，项目名称，承担任务）

由于员工和项目之间的联系类型为（），所以员工和项目之间的联系需要转换成一个独立的关系模式，该关系模式的主键是（）

【多对多、（项目编号，员工代码）】

关系代数

并：结果是两张表中所有记录数合并，相同记录只显示一次。
交：结果是两张表中相同的记录
差：S1-S2，结果是S1表中有而S2表中没有的那些记录。

笛卡尔积：S1*S2，产生的结果包括S1和S2所有属性列，并且S1中每条记录依次和S2中所有记录组合成一条记录，最终属性列为S1+S2属性列，记录数为S1*S2记录数。

投影：实际是按条件选择某关系模式中的某列，列也可以用数字表示。

选择：实际是按条件选择某关系模式中的某条记录。

自然连接的结果显示全部的属性列，但是相同属性列只显示一次，显示两个关系模式中属性相同且值相同的记录。
设有关系R、S如下左图所示，自然连接结果如下有图所示：

【真题】

给定关系R（A,B,C,D）和关系S（C,D,E），对其进行自然连接运算R⋈S后的属性列为（）个，与σ~R.B>S.E~（R⋈S）等价的关系代数表达式为（）

A.4
B.5
C.6
D.7

【B、D】

函数依赖

给定一个X，能唯一确定一个Y，就称X确定Y，或者说Y依赖于X，例如Y=X*X函数。

函数依赖又可扩展以下两种规则：

部分函数依赖：A可确定C，（A，B）也可确定C，（A，B）中的一部分（即A）可以确定C，称为部分函数依赖。
传递函数依赖：当A和B不等价时，A可确定B，B可确定C，则A可确定C，是传递函数依赖；若A和B等价，则不存在传递，直接就可确定C。

计算机组成原理

计算机的基本硬件由 运算器 、控制器 、存储器 、输入设备和输出设备 5大部件组成。
运算器、控制器等部件被集成在一起统称为中央处理单元（Central Processing Unit, CPU）。CPU是硬件系统的核心，用于数据的加工处理，能完成各种算术、逻辑运算及控制功能。
存储器是计算机系统中的记忆设备 ，分为内部存储器和外部存储器 。前者速度高、容量小，一般用于临时存放程序、数据及中间结果；而后者容量大、速度慢，可以长期保存程序和数据。
输入设备和输出设备合称为外部设备（简称“外设”）。

中央处理单元

CPU的功能：

程序控制：CPU 通过执行指令来控制程序的执行顺序。
操作控制：一条指令功能的实现需要若干操作信号配合来完成，CPU 产生指令的操作信号并将操作信号送往对应的部件，控制相应的部件按指令的功能要求进行操作。
时间控制：CPU 对各种操作进行时间上的控制，即指令执行过程中操作信号的出现时间、持续时间及出现的时间顺序都需要进行严格控制。
数据处理：CPU 通过对数据进行算数运算及逻辑运算等方式进行加工处理，数据加工处理的结果被人们所利用。即CPU最根本的任务是：对数据的加工处理。此外，CPU 还需要对 系统内部和外部的中断（异常）做出响应，进行相应的处理。

CPU 的组成：

CPU主要由运算器、控制器、寄存器组和内部总线等部件组成。

运算器：由算数逻辑单元 ALU（实现对数据的算术和逻辑运算）、累加寄存器 AC（运算结果或源操作数的存放区）、数据缓冲寄存器 DR（暂时存放内存的指令或数据）和状态条件寄存器 PSW（保存指令运行结果的条件码内容，如溢出标志等）组成。执行所有的算术运算；执行所有的逻辑运算并进行逻辑测试。
控制器：由指令寄存器 IR （暂存 CPU 执行指令）、程序计数器 PC（存放指令执行地址）、地址寄存器 AR（保存当前 CPU 所访问的内存地址）、指令译码器 ID（分析指令操作码）等组成。控制整个 CPU 的工作，最为重要。
CPU 依据指令周期的不同阶段来区分二进制的指令和数据，因为在指令周期的不同阶段，指令会命令 CPU 分别取取指令或数据。

【真题】

CPU 进行算术运算或者逻辑运算时，常将源操作数和结果暂存在（）中。
A.程序计数器（PC） B.累加器（AC）
C.指令寄存器（IR ） D.地址寄存器（AR）【B】
执行 CPU 指令时，在一个指令周期的过程中，首先需要从内存读取要执行的指令，此时先要将指令的地址即（）的内容送到地址总线上。 A.指令寄存器（IR ） B.通用寄存器（GR） C.程序计数器（PC） D.状态寄存器（PSW）
【C】

数据表示：

进制表示：
1. 二进制 B、0b
2. 八进制 O
3. 十六进制 H、0x
R进制整数转十进制：位权展开法。
例如有 6进制数 5043，此时 R=6，用6进制数的每一位乘以 6的n次方，n为变量，从 6进制数的整数最低位开始，n依次为 0,1,2,3，那么最终 5043 = 3*6^0 + 4*6^1 + 0*6^2 + 5*6^3 =1107
十进制转R进制：十进制整数（除以 R 倒取余数）
用十进制整数除以 R，记录每次所得余数，若商不为0，则继续除以R，直至商为0，而后将所有余数从下至上记录，排列成从左至右顺序，即为转换后的R进制数。
例如有十进制数200，转换为6进制，此时R=6，将200/6，得商为33，余数为2；因为商不等于0，因此将商33/6，得商为5，余数为3；再将5/6，得商为0，余数为5；此时商为0，将所有余数从下到上记录，得 532。
m进制转n进制：先将m进制转化为十进制数，再将十进制数转化为n进制数，中间需要通过十进制中转，但下面两种进制之间可以直接转化：
1. 二进制转八进制：每三位二进制数转换为一位八进制数。
  例如二进制数 01101有五位，前面补一个0就有六位，为 001 101，
  每三位转换为一位八进制数，即：
  001 = 1， 101 = 1+4=5，也就是 01101 = 15。
2. 二进制转十六进制：每四位二进制数转换为一位十六进制数。
  与上面同理，不再赘述。
机器数：各种数值再计算机中表现的形式，其特点是使用二进制计数值，数的符号用 0和1 表示，小数点则隐含，不占位置。
机器数有无符号数和带符号数之分。无符号数表示整数，没有符号位。带符号位最高位为符号位，正数符号位为0，负数符号位为1。
定点表示法分为纯小数和纯整数两种，其中小数点不占存储位，二十按照以下约定：
纯小数：约定小数点的位置在机器数的最高数值位之前。
纯整数：约定小数点的位置在机器数的最低数值位之后。
真值：机器数对应的实际数值。
带符号数有下列编码方式，当真值为 -45 时：原码：一个数的正常二进制表示，最高位表示符号，数值 0 的原码有两种形式：+0(0 0000000)和 -0(1 0000000)。 -45对应原码为 1010 1101 反码：正数的反码即原码；负数的反码是在原码的基础上，除符号位外，其他各位按位取反。数值 0 的反码也有两种形式： +0(0 0000000)，-0(1 1111111)。-45对应反码为 1101 0010 补码：正数的补码即原码；负数的补码是在原码的基础上，除符号位外，其他各位按位取反，而后末位+1，若有进位则产生进位。因此数值0的补码只有一种形式 +0 = -0 = 0 00000000。 -45对应补码为 1101 0011 移码：用作浮点运算的阶码，无论正数负数，都是将该原码的补码的首位（符号位）取反得到移码。-45对应移码为 01010011
浮点数：表示方法为 N = F 2^E，其中 E 称为阶码，F 称为尾数；类似于十进制的科学计数法，如 85.125 = 0.85125*10^2，二进制如 101.011 = 0.1010112^3. 在浮点数的表示中，阶码为带符号的纯整数，尾数为带符号的纯小数，要注意符号占最高位（正数0负数1），其表示格式如下：阶符阶码数符尾数一个浮点数的表示方法不是唯一的，浮点数所能表示的数值范围由阶码确定，所表示的数值精度由尾数确定。
浮点数的运算：对阶（使两个数的阶码相同，小阶向大阶看齐（低位丢弃对精度影响不大），较小阶码增加几位，尾数就右移几位） 0.10101*2^3^,–>0.0010101*2^5^
0.11101*2^5^, 尾数计算（相加，若是减运算，则加负数）结果规格化（即尾数表示规格化，带符号尾数转换为1.0xxxx或0.1xxxx）

【真题】

如果” 2X “的补码是” 90H “，那么X的真值是（）

A. 72 B. -56 C. 56 D. 111

【B】
90H = 1001 0000(补码)
反码 = 1,000 1111
原码 = 1,111 0000
2X = -112
X = -56

设16位浮点数，其中阶符1位、阶码值6位、数符1位、尾数8位。若阶码用移码表示，尾数用补码表示，则该浮点数所能表示的数值范围是（）

A. -2^64^ ~ (1-2^-8^)*2^64^
B. -2^63^ ~ (1-2^-8^)*2^63^
C. -2^64^ ~ (1-2-(1-2^-8^)2^64^ ~ (1-2^-8^)*2^64^
D. – (1-2^-8^)*2^63^ ~ (1-2^-8^)*2^63^

校验码

码距：就单个编码A：00而言，其码距为1，因为其只需要改变一位就变成另一个编码。在两个编码中，从A码到B码转换所需要改变的位数称为码距，如A：00要转换为B：11，码距为2。一般来说，码距越大，越利于纠错和检错。
奇偶校验码：在编码中增加1位校验位来使编码中1的个数为奇数（奇校验）或者偶数（偶校验），从而使码距变成2。例如：奇校验：编码中，含有奇数个1，发送给接收方，接收方收到后，会计算收到的编码由多少个1，如果是奇数个，则无误；是偶数个，则有误。偶校验同理，只是编码中有偶数个1，由上述，奇偶校验只能检1位错，并且无法纠错。

CRC（循环冗余校验码）

例如：假设原始信息串为 10110，CRC的生成多项式为 G(x)=x^4+x+1，求CRC校验码。

(3) 生成CRC校验码，将前两步得出的被除数和除数进行模2除法运算（即不进位也不借位的除法运算）。除法过程如下图所示。

得到余数1111。
注意：**余数不足r，则余数左边用若干个0补齐。如求得余数为11，r=4，则补齐两个0 得到 0011。

(4) 生成最终发送信息串，将余数添加到原始信息后。上例中，原始信息串 10110，添加余数 1111 后，结果为 10110 1111。发送方将此数据发送给接收方。

【真题】

A.1100 010 B.1011010 C.1100011 D.1011110

海明码

海明码：本质也是利用奇偶性来检错和纠错的检验方法，构成方法是在数据位之间的确定位置上插入 k个校验位，通过扩大码距实现检错和纠错。设**数据位是 n位，检验位是 k位，则 n和k 必须满足以下关系： 2^k -1 >= n+k。例：求信息 1011 的海明码
1. 校验位的位数和具体的数据位的位数之间的关系 所有位都编号，从最低位编号，从 1开始递增，检验位处于 2的n(n =0,1,2…)次方中，即处于第 1，2，4，8，…位上，其余位才能填充真正的数据位，若信息数据为 1011，则可知，第1，2，4位为校验位，第3，5，6，7位为数据位，用来从低位开始存放 1011，得出信息位和校验位分布如下： 7 6 5 4 3 2 1 位数 i4 i3 i2 i1 信息位 r2 r1 r0 校验位 1 0 1 1 原始数据
2. 计算校验码将所有信息位的编号都拆分成二进制表示，如下图所示： 7 6 5 4 3 2 1 位数 1 0 1 1 原始数据 0 0 1 校验位 I4(7) = 2^2+2^1+2^0, I3(6) = 2^2+2^1, I25 = 2^2+2^0, 3 = 2^1+2^0;
  r2 = I4 ⊕ I3 ⊕ I2;
  r1 = I4 ⊕ I3 ⊕ I1;
  r0 = I4 ⊕ I2 ⊕ i1; 上式中，7=4+2+1，表示 7由第四位校验位r2和第二位校验位r1和第一位校验位r0共同校验，其余同理。可知，第四位校验位校验第7 6 5 三位数据位。因此，第四位校验位 r2 等于这三位数据位的值异或，第二位和第一位校验位计算原理同上。计算出三个校验位后，可知最终要发送的海明码校验码为 1010101
3. 检错和纠错原理接收方收到海明码之后，会将每一位校验位与其校验的位数分别异或，即做好下面三组运算： r2 ⊕ I4 ⊕ I3 ⊕ I2
  r1 ⊕ I4 ⊕ I3 ⊕ I1
  r0 ⊕ I4 ⊕ I2 ⊕ I1 如果是偶校验，那么运算得到的结果全为0，如果是奇校验，应全为1，结果才是正确，假设是偶校验，且接收到的数据为 101 1 101（第四位出错），此时运算的结果为： r2 ⊕ I4 ⊕ I3 ⊕ I2 = 1 ⊕ 1 ⊕ 0 ⊕ 1 = 1
  r1 ⊕ I4 ⊕ I3 ⊕ I1 = 0 ⊕ 1 ⊕ 0 ⊕ 1 = 0
  r0 ⊕ I4 ⊕ I2 ⊕ I2 = 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0 这里不全为0，表明传输过程有误，并且按照 r2r1r0排列为二进制 100，这里指出的就是错误的位数，表示第100，即第4位出错，找到了出错位，纠错的方法就是将该位逆转。

【真题】

A.3 B.4 C.5 D.6

【D】
32+6=38，所以至少6个校验位

A.P4P1 B.P4P2 C.P4P3P1 D.P3P2P1

【B】
D5 = 10 = 8 + 2 = 2^3 + 2^ 1 = P4 ⊕ P2

体系结构

体系结构分类

按处理器数量进行分类：单处理系统（一个处理单元和其他设备集成）、并行处理系统（两个以上的处理机互联）、分布式处理系统（物理上远距离且松耦合的多计算机系统）。
Flynn分类法：分类有两个因素，即指令流和数据流，指令流由控制部分处理，每一个控制部分处理一个指令流，多指令流就有多个控制部分；数据流由处理器来处理，每一个处理器就处理一条数据流，多个数据流就有多个处理器；至于主存模块，是用来存储的，存储指令流或者数据流。因此，无论是多指令流还是多数据流，都需要多个主存模块来存储，对于主存模块，指令和数据都一样。
依据计算机特性，是由指令来控制数据的传输，因此，一条指令可以控制一条或多条数据流，但一条数据流不能被多条指令控制，否则会出错，就如同上级命令太多还互相冲突，不知道该执行哪个，因此多指令单数据MISD不可能实现。

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

指令系统

计算机指令的组成：一条指令由操作码和操作数两部分组成，操作码决定要完成的操作，操作数指参加运算的数据及其所在的单元地址。
在计算机中，操作要求和操作数地址都有二进制数码表示，分别称作操作码和地址码，整条指令以二进制编码的形式存放在存储器中。
计算机指令的指令过程：取指令–分析指令–执行指令三个步骤。受限将程序计数器PC中的指令地址取出，送入地址总线，CPU依据指令地址去内存中取指令内容存入指令寄存器IR；而后由指令译码器进行分析，分析指令操作码；后执行指令，取出指令执行所需的源操作数。
指令的寻址方式 顺序寻址方式：当执行一段程序时，是一条指令接着一条指令地顺序执行。
跳跃寻址方式：指下一条指令的地址吗不是由程序计数器给出，而由本条指令直接给出。程序跳跃后，按新的指令地址开始顺序执行。因此，程序计数器的内容也必须相应改变，以便及时跟踪心的指令地址。
指令操作数的寻址方式 立即寻址方式：指令的地址码字段指出的不是地址，而是操作数本身。
直接寻址方式：在指令的地址字段中直接指出操作数在主存中的地址。
间接寻址方式**：指令地址码字段所指向的存储单元中存储的是操作数的地址。
寄存器寻址方式：指令中的地址码是寄存器的编号。
基址寻址方式：将基址寄存器的内容加上指令中的形式地址形成操作数的有效地址，其优点是可以扩大寻址能力。
变址寻址方式：变址寻址方式计算有效地址的方式与基址寻址方式很类似，它是将变址寄存器的内容加上指令中的形式地址而形成操作数的有效地址。
指令系统类型 CISC 是复杂指令系统，兼容性强，指令繁多、长度可变，由微程序实现；
RISC是精简指令系统，指令少，使用频率接近，主要依靠硬件实现（通用寄存器、硬布线逻辑控制）具体区别如下：指令系统类型指令寻址方式实现方式其他 CISC（复杂）数量多，使用频率差别大，可变长格式支持多种微程序控制技术（微码）研制周期长 RISC（精简）数量少，使用频率接近，定长格式，大部分为单周期指令，操作寄存器，只有Load/Store操作内存支持方式少增加了通用寄存器；硬布线逻辑控制为主；适合采用流水线优化编译，有效支持高级语言

【真题】

Flynn分类法根据计算机在执行程序的过程中（）的不同组合，将计算机分为四类。当前主流的多和计算机属于（）计算机。

A.指令流和数据流 B.数据流和控制流 C.指令流和控制流 D.数据流和总线带宽
A.SISD B.SIMD C.MISD D.MIMD

【A、D】

以下关于复杂指令集计算机（Complex Instruction Set Computer, CISC）的叙述中，正确的是（）

【D】

指令流水线原理：将指令分成不同段，每段由不同的部分取处理，因此可以产生叠加的效果，所有的部件去处理指令的不同段
RISC中的流水线技术： (1) 超流水线(Super Pipe Line)技术。它通过细化流水、增加级数和提高主频，使得在每个机器周期内能完成一个甚至两个浮点操作。其实质是以时间换取空间。 (2) 超标量(Super Scalar)技术。它通过内装多条流水线来同时执行多个处理，其时间频率虽然与一般流水接近，却又更小的CPI。其实质是以空间换取时间。 (3)超长指令集(Very Long Instruction Word, VLIW)技术。VLIW和超标量都是20世纪80年代出现的概念，其共同点是要同时执行多条指令，其不同在于超标量依靠硬件来实现并行处理的调度，VLIW则充分发挥软件的作用，而使硬件简化，性能提高。
流水线时间计算： (1) 流水线周期：指令分成不同执行段，其中执行时间最长的段为流水线周期。 (2) 流水线执行时间：1条指令总执行时间+（总指令条数 -1） * 流水线周期。 (3) 流水线吞吐率计算：吞吐率即单位时间内执行的指令条数。
公式：指令条数 / 流水线执行时间 (4) 流水线的加速比计算：加速比即使用流水线后的效率提升度，即比不使用流水线快了多少倍，越高表明流水线效率越高。
公式：不使用流水线执行时间 / 使用流水线执行时间

【真题】

A. 500*10^6 B.490*10^6 C.250*10^6 D.167*10^6

【B】
流水线执行100个任务所需要的时间为：(2+1+1+1) + (100 -1) 2 =204ns。所以每秒吞吐率为：（100/204)*10^9 = 49010^6

A.150 B.151 C.156 D.201

【D、C】
单缓冲区：前两段要合并，是两段流水线，21+20*(10-1) =201
双缓冲区：标准三段流水线，21+15*(10-1) =156

A.nkt B.(k+n-1)t C.(n-k)kt D.(k+n+1)t
A.4 B.5 C.6 D.7

存储系统

计算机采用分级存储体系的主要目的是为了解决存储容量、成本和速度之间的矛盾问题。至上而下，速度越来越慢、容量越来越大、价格越来越低
两级存储： Cache – 主存、主存 – 辅存（虚拟存储体系）
局部性原理：总的来说，在CPU运行时，所访问的数据会趋向于一个较小的局部空间地址内，包括以下两个方面：时间局部性原理：如果一个数据项正在被访问，那么在近期它很可能会被再次访问，即在相邻的时间里会访问同一个数据项。空间局部性原理：在最近的将来会用到的数据的地址和现在正在被访问的数据地址很可能是相近的，即相邻的空间地址会被连续访问。
高速缓存Cache 用来存储当前最活跃的程序和数据，直接与CPU交互，位于CPU和主存之间，容量小，速度为内存的5~10倍，由半导体材料构成。其内容是主存内存的副本拷贝，对于程序员来说是透明的。
Cache由控制部分和存储器组成，存储器存储数据，控制部分判断部分判断CPU要访问的数据是否在Cache中，在则命中，不在则依据一定的算法从主存中替换。
地址映射：在CPU工作时，送出的是主存单元的地址，而应从Cache存储器中读 / 写信息。这就需要将主存地址转换为 Cache 存储器地址，这种地址的转换称为地址映像，由硬件自动完成映射，分为下列三种方法：直接映像：将Cache存储器等分成块，主存也等分成块并编号。主存中的块与Cache中的块的对应关系是固定的，也即二者块号相同才能命中。地址变换简单但不灵活，容易造成资源浪费。（如图所示）全相联映像：同样都等分成块并编号。主存中任意一块都与Cache中任意一块对应。因此可以随意调入Cache任意位置，但地址变换复杂，速度较慢。因此主存可以随意调入Cache任意块，只有当Cache满了才会发送块冲突，是最不容易发生块冲突的映像方式。组组相连映像：前面两种方式的结合，将Cache存储器先分块再分组，主存也同样先分块再分组，组间采用直接映像，即主存中组号与Cache中组号相同的组才能命中，但是组内全相联映像，也即组号相同的两个组内的所有块可以任意调换。
替换算法的目标就是使Cache获得尽可能高的命中率。常用的算法如下所示： (1) 随机替换算法。就是用随机数发生器产生一个要替换的块号，将该块替换出去。 (2) 先进先出算法。就是将最先进入Cache的信息块替换出去。 (3) 近期最少使用算法。这种方法是将近期最少使用的Cache中的信息块替换出去。 (4) 优化替换算法。这种方法必须先执行一次程序，统计Cache的替换情况。有了这样的先验信息，在第二次执行该程序时便可以用最有效的方式来替换。
命中率及平均时间 Cache有一个命中率的概念，即当CPU所访问的数据在Cache中时命中，直接从Cache中读取数据，设读取一次Cache时间为1ns，若CPU访问的数据不在Cache中，则需要从内存中读取，设读取一次内存的时间为1000ns，若在CPU多次读取数据过程中，有90%命中Cache，则CPU读取一次的平均时间为
(90%1 + 10%1000)ns。

【真题】

按照Cache地址映像的块冲突概率，从高到低排列的是（）

【B】

以下关于Cache与主存间地址映射的叙述中，正确的是（）

【D】

基本概念：K、M、G是数量单位，在存储器中相差1024倍
B、b是存储单位，1B = 8b

地址编号从 80000H到BFFFFH 且按字节编址的内存容量为（5）KB，若用16K*4bit的存储器芯片构成该内存，共需要（）片

A.128 B.256 C.512 D.1024
A.8 B.16 C.32 D.64

磁盘结构和参数磁盘有正反两个盘面，每个盘面有多个同心圆，每个同心圆是一个磁道，每个同心圆又被划分为多个扇区，数据就被存放在一个个扇区中。磁头首先要寻找到对应的磁道，然后等待磁盘进行周期旋转，旋转到指定的扇区，才能读取到对应的数据。因此，会产生寻道时间和等待时间。公式为：存取时间=寻道时间+等待时间（平均定位时间+转动延迟）。注意：寻道时间是指磁头移动到磁道所需的时间；等待时间为等待读写的扇区转到磁头下方所用的时间。
磁盘调度算法磁盘数据的读取时间=寻道时间+旋转时间，也就是先找到对应的磁道，而后再旋转到对应的扇区才能读取数据，其中寻道时间耗时最长，需要重点调度，有如下调度算法： (1) 先来先服务FCFS：根据进程请求访问磁盘的先后顺序进行调度。 (2) 最短寻道时间优先SSTF：请求访问的磁道与当前磁道最近的进程优先调度，使得每次的寻道时间最短。会产生“饥饿”现象，即远处进程可能永远无法访问。 (3) 扫描算法SCAN：又称“电梯算法”，磁头在磁盘上双向移动，其会选择离磁头当前所在磁道最近的请求访问磁道，并且与磁头移动方向一致，磁头永远都是从里向外或者从外向里一直移动完才掉头，与电梯类似。 (4) 单项扫描调度算法CSCAN：与SCAN不同的是，其只做单向移动，即只能从里向外或者从外向里。

【真题】

假设某磁盘的每个磁道划分成11个物理块，每块存放1个逻辑记录。逻辑记录R0，R1，…，R9，R10存放在同一个磁道上，记录的存放顺序如下表所示：

物理块	1	2	3	4	5	6	7	8	9	10	11
逻辑记录	R0	R1	R2	R3	R4	R5	R6	R7	R8	R9	R10

A.33ms B.336ms C.366ms D.376ms
A.33ms B.66ms C.86ms D.93ms

优化存储分布后，即6ms*11=66ms，表格如下所示：

物理块	1	2	3	4	5	6	7	8	9	10	11
逻辑记录	R0	R6	R1	R7	R2	R8	R3	R9	R4	R10	R5

请求序列	柱面号	磁头号	扇区号
1	17	8	9
2	23	6	3
3	23	9	6
4	32	10	5
5	17	8	4
6	32	3	10
7	17	7	9
8	23	10	4
9	38	10	8

A.283451769 B.238469157 C.123456789 D.283571469

输入输出技术

内存与接口地址的编址方法

计算机系统中存在多种内存与接口地址的编址方法，常见的是下面两种： (1) 内存与接口地址独立编址方法内存地址和接口地址是完全独立的两个地址空间。访问数据时所使用的指令也完全不同，用于接口的指令只用于接口的读/写，其余的指令全都是用于内存的。因此，在编程序或读程序时很容易使用和辨认。这种编址方法的缺点是用于接口的指令太少、功能太弱。 (2) 内存与接口地址统一编址方法内存地址和接口地址统一在一个公共的地址空间里，即内存单元和接口共用地址空间。优点是原则上用于内存的指令全都可以用于接口，这就大大地增强了对接口的操作功能，而且在指令上也不再区分内存或接口指令。该编址方法的缺点在于整个地址空间被分为两部分，其中一部分分配给接口使用，剩余的为内存所用，这经常会导致内存地址不连续。

计算机和外设间的数据交互方式

(1) 程序控制（查询）方式：CPU主动查询外设是否完成数据传输，效率极低。

在一个总线周期结束后，CPU会响应DMA请求开始读取数据；CPU响应程序中断请求是在一条指令执行结束时。

总线结构

总线（Bus），是指计算机设备和设备之间传输信息的公共数据通道。总线是连接计算机硬件系统内多种设备的通信线路，它的一个重要特征是由总线上的设备共享，因此可以将计算机系统内的多种设备连接到总线上。
从广义上讲，任意连接两个以上电子元器件的导线都可以称为总线，通常分为以下三类： (1) 内部总线：内部芯片级别的总线，芯片与处理器之间通信的总线。 (2) 系统总线：是板级总线，用于计算机内各部分之间的连接，具体分为数据总线（并行数据传输位数）、地址总线（系统可管理的内存空间的大小）、控制总线（传送控制命令）。代表的由ISA总线、EISA总线、PCI总线。 (3) 外部总线：设备一级的总线，微机和外部设备的总线。代表的由RS232（串行总线）、SCSI（并行总线）、USB（通用串行总线，即插即用，支持热插拔）

【真题】

计算机系统中常用的输入/输出控制方式有无条件传送、中断、程序查询和DMA方式等。当采用（）方式时，不需要CPU执行程序指令来传送数据。

A.中断 B.查询查询 C.无条件传送 D.DMA

【D】

以下关于总线的说法中，正确的是（）。

计算机可靠性

可靠性指标（理解概念即可）平均无故障时间MTTF= 1/失效率。平均故障修复时间MTTR= 1/修复率。平均故障间隔时间MTBF = MTTF+MTTR。系统可用性= MTTF/(MTTF + MTTR)*100%。
串并联系系统可靠性无论什么系统，都是由多个设备组成的，协同工作，而这多个设备的组合方式。可以是串联、并联，也可以是混合模式，假设每个设备的可靠性为R1，R2……Rn，则不同的系统的可靠性公式如下： 串联系统，一个设备不可靠，整个系统崩溃，整个系统可靠性R=R1*R2*…*Rn。 并联系统，所有设备都不可靠，整个系统才崩溃，整个系统的可靠性R=1 – (1-R1) * (1-R2) *…* (1-Rn)。 N模冗余系统：N模冗余系统由N个 (N= 2n + 1 ) 相同的子系统和一个表决器组成，表决器把N个子系统中占多数相同结果的输出作为输出系统的输出，如图所示。N个子系统中，只要有n+1个或n+1个以上的子系统能正常工作，系统就可以正常工作，输出正确结果。

【真题】

计组练习题

1.计算机中CPU对其访问速度最快的是（C）

A.内存 B.Cache C.通用寄存器 D.硬盘

解析：寄存器＞Cache＞内存＞硬盘

2.机器字长为n位的二进制数可以用补码来表示（A）个不同的有符号定点小数。

A.2^n B.2^(n-1) C.2^n -1 D.2^(n-1) +1

解析：在补码里，0只有一种表示方式，因此可以表示全2

^0个数值；但原码和反码可以表示的是 2^n -1个数值，因为原码和反码里0区分正0和负0

3.Cache 的地址映像方式中，发生块冲突次数最小的是（A）

A.全相联映像 B.组相联映像 C.直接映像 D.无法确定的

4.计算机中CPU的中断响应时间指的是（D）的时间

A.从发出中断请求到中断处理结束
B.从中断处理开始到中断处理结束
C.CPU分析判断中断请求
D.从发出中断请求到开始进入中断处理程序

5.总线宽度为 32bit，时钟频率为 200MHz，若总线上每 5 个时钟周期发送一个 32bit的字，则该总线的宽度为（C）MB/s

A.40 B.80 C.160 D.200

解析：一个时钟周期为 1/200M 秒，5个时钟周期就是 5/200M 秒，传送32bit，那么总线宽度就说用传输数据除以时间，即 32bit/(5/200M)= 160MB/s

6.以下关于指令流水线性能度量的叙述中，错误的是（D）

解析：流水线最理想的就是各级运行时间相同，这样可以保证无延迟；流水线是一种同步控制机制。

7.CPU是在（D）结束时响应DMA请求的

A.一条指令执行 B.一段程序

C.一个时钟周期 D.一个总线周期

8.虚拟存储体系由（A）两级存储器构成的

A.主存-辅存 B.寄存器-Cache

C.寄存器-主存 D.Cache-主存

9.浮点数能够表示的数的范围是由其（B）的位数决定的

A.尾数 B.阶码 C.数符 D.阶符

解析：浮点数的范围由阶码决定，精度由尾数决定。

10.在机器指令的地址字段中，直接指出操作数本身的寻址方式称为（D）

A.隐含寻址 B.寄存器寻址 C.立即寻址 D.直接寻址

解析：指令地址字段，操作数地址存储的就是操作数本身，是立即寻址。

11.内存按字节编址从 B3000H 到 DABFFH 的区域其存储容量为（B）

A. 123KB B. 159KB C. 163KB D. 194KB

12.CISC是（A）的简称

A.复杂指令系统计算机 B.超大规模集成电路
C.精简指令系统计算机 D.超长指令字

解析： C是complex，是复杂指令系统

13.VLIW是（D）的简称

A.复杂指令系统计算机 B.超大规模集成电路
C.单指令流多数据流 D.超长指令字

解析：A选项首个单词复杂英文是Complex，以C开头；C选项首个单词单个英文是single，以S开头；D选项超长指令字英文是 very long instruction word。

14.主存与Cache的地址映射方式中，（A）方式可以实现主存任意一块装入Cache中任意位置，只有装满才需要替换。

A.全相联 B.直接映射 C.组相联 D.串并联

15.如果“2X”的补码是“90H”，那么X的真值是（B）

A.72 B.-56 C.56 D.111

16.移位指令中的（A）指令的操作结果相对于对操作数进行乘2操作

A.算术左移 B.逻辑右移 C.算术右移 D.带进位循环左移

17.内存按字节编址，从 A1000H 到 B13FFH 的区域的存储容量为（C）KB

A.32 B.34 C.65 D.67

18.以下关于总线的叙述中，不正确的是（C）。

19.在程序运行过程中，CPU需要将指令从内存中取出并加以分析和执行。CPU依据（A）来区分在内存中以二进制编码形式存放的指令和数据。

A.指令周期的不同阶段 B.指令和数据的寻址方式
C.指令操作码的译码结果 D.指令和数据所在的存储单元

解析：在指令周期的不同阶段，指令会命令CPU分别去取指令或数据。因此CPU是依据指令周期的不同阶段的命令去区分的。

20.计算机在一个指令周期的过程中，为从内存读取指令操作码，首先要将（C）的内容送到地址总线上。

A.指令寄存器（IR） B.通用寄存器（GR）
C.程序计数器（PC） D.状态寄存器（PSW）

解析：首先需要知道指令存放地址，才可以取出指令。指令的存放地址在程序计数器PC中。

21.设16位浮点数，其中阶符1位、阶码值6位、数符1位、尾数8位。若阶码用移码表示，尾数用补码表示，则该浮点数能表示的数值范围是（B）

A.-2^64^ ~ (1-2^-8^)*2^64^
B.-2^63^ ~ (1-2^-8^)*2^63^
C.-2^64^ ~ (1-2-(1-2^-8^) 2^64^ ~ (1-2^-8^)*2^64^)
D.-(1-2^-8^)*2^63^ ~ (1-2^-8^)*2^63^

22.已知数据信息为16位，最少应附加（C）位校验位，以实现海明码纠错。

A.3 B.4 C.5 D.6

A.200 B.300 C.400 D.405

解析：流水线中最长执行时间步骤为流水线周期，就是4。而后依据流水线指令的执行时间公式，可得时间为 4+2+3+(100-1)*4=405

24.以下关于Cache与主存间地址映射的叙述中，正确的是（D）

A.操作系统负责管理Cache 与主存之间的地址映射
B.程序员需要通过编程来处理Cache 与主存之间的地址映射
C.应用软件对Cache 与主存之间的地址映射进行调度
D.由硬件自动完成Cache 与主存之间的地址映射

25.CPU执行算术运算或者逻辑运算时，常将源操作数和结果暂存在（B）中

A.程序计数器（PC） B.累加器（AC）
C.指令寄存器（IR） D.地址寄存器（AR）

26.要判断字长为16位的整数a的低四位是否全为0，则（A）

27.计算机系统中常用的输入/输出控制方式有无条件传送、中断、程序查询和DMA方式。当采用（D）方式时，不需要CPU执行程序指令来传送数据。

A.中断 B.程序查询 C.无条件传送 D.DMA

28.某系统由下图所示的冗余部件构成。若每个部件的千小时可靠度都为R，则该系统的千小时可靠度为（B）

A.(1-R^3^)(1-R^2^) B.(1-(1-R)^3^)(1-(1-R)^2^)
C.(1-R^3^)+(1-R^2^) D.(1-(1-R)^3^)+(1-(1-R)^2^)

29.以下关于Cache（高速缓冲存储器）的叙述中，不正确的是（A）

A.Cache 的设置扩大了主存的容量
B.Cache 的内容是主存部分内容的拷贝
C.Cache 的命中率并不随其容量增大线性地提高
D. Cache 位于主存与 CPU之间

30.在程序执行的过程中，Cache与主存的地址映射是由（C）完成的

A.操作系统 B.程序员调度 C.硬件自动 D.用户软件

A.4 B.8 C.9 D.33

32.内存按字节编址。若用存储容量为 32K*8bit 的存储器芯片构成地址从 A0000H 到 DFFFFH 的内存，至少需要（B）片芯片。

A.4 B.8 C.16 D.32

33.计算机系统的主存主要是由（）构成的。

A.DRAM B.SRAM C.Cache D.EEPROM

解析：主存即内存。RAM是随机存储器，其中SRAM读写速度快，价格昂贵，一般是制作Cache；DRAM读写速度相对较慢，容量大价格低，用于制作主存。

34.以下关于海明码的叙述中，正确的是（A）

A.海明码利用就行进行检错和纠错
B.海明码的码距为 1
C.海明码可以检错但不能纠错
D.海明码中数据为的长度与校验位的长度必须相同

35.浮点数的表示分为阶和尾数两部分。两个浮点数相加时，需要先对阶，即（D）（n 为阶差的绝对值）。

解析：举例：

浮点数 A：阶码为 5，尾数为 0.1101（二进制），实际值为 0.1101×2^5^。
浮点数 B：阶码为 3，尾数为 0.1010（二进制），实际值为 0.1010×2^3^。
对阶过程：
1. 比较阶码：
2. 将小阶向大阶对齐：
  将 B的阶码从 3 调整为 5，同时将其尾数右移 2 位（因为阶差是 2）。
3. 调整尾数：
  B 的尾数原来是 0.1010，右移 22 位后变为 0.001010（注意右移后高位补零）。
4. 调整后的浮点数：
  - A 保持不变：0.1101×2^5^。
  - B 调整为：0.001010×2^5^。
总结：
- 对阶：将小阶向大阶对齐，尾数右移 n 位（n 为阶差）。
- 相加：对齐后直接对尾数相加。

操作系统

操作系统概述

操作系统定义：能有效地组织和管理系统中各种软/硬件资源，合理地组织计算机系统工作流程，控制程序的执行，并且向用户提供一个良好的工作环境和友好的接口
操作系统有两个重要的作用：第一、通过资源管理提高计算机系统的效率；第二、改善人机界面向用户提供友好的工作环境。
操作系统的四个特征：
1. 并发性
2. 共享性
3. 虚拟性
4. 不确定性

操作系统的功能

进程管理。实质上是对处理及的执行“时间”进行管理，采用多道程序等技术将CPU的时间合理地分配给每个任务，主要包括进程控制、进程同步、进程通信和进程调度。
文件管理。主要包括文件存储空间管理、目录管理、文件的读/写管理和存取控制。
存储管理。存储管理是对主存储器“空间”进行管理，主要包括存储分配与回收、存储保护、地址映射（变换）和主存扩充。
设备管理。实质是对硬件设备的管理，包括对输入/输出设备的分配、启动、完成和回收。
作业管理。包括任务、界面管理、人机交互、图形界面、语音控制和虚拟现实等。

操作系统的分类

批处理操作系统：单道批处理和多道批处理（主机与外设可并行）
分时操作系统：一个计算机系统与多个终端设备连接。将CPU的工作时间划分为许多很短的时间片，轮流为各个终端的用户服务。
实时操作系统：实时是指计算机对于外来信息能够以足够快的速度进行处理，并在被控对象允许的时间范围内做出快速反应。实时系统对交互能力要求不高，但要求可靠性有保障。
网络操作系统：是使联网计算机能方便而有效地共享网络资源，为网络用户提供各种服务的软件和有关协议的集合。三种模式：集中模式、客户端/服务器模式、对等模式。
分布式操作系统：分布式计算机系统是由多个分散的计算机经连接而成的计算机系统，系统中的计算机无主次之分，任意两台计算机可以通过通信交换信息。
微型计算机操作系统：简称微机操作系统，常用的由Windows、MacOS、Linux。
嵌入式操作系统主要特点： (1) 微型化。从性能和成本角度考虑，希望占用的资源和系统代码量少，如内存少、字长短、运行速度有限、能源少（用微小型电池） (2) 可定制。从减少成本和缩短研发周期考虑，要求嵌入式操作系统能运行在不同的微处理器平台上，能针对硬件变化进行结构与功能上的配置，以满足不同应用需要。 (3) 实时性。嵌入式操作系统主要应用于过程控制、数据采集、传输通信、多媒体信息及关键要害领域需要迅速响应的场合，所以对实时性要求较高。 (4) 可靠性。系统构件、模块和体系结构必须达到应有的可靠性，对关键要害应用还要提供容错和防故障措施。 (5) 易移植性。为了提高系统的易移植性，通常采用硬件抽象层和板级支撑包的底层设计技术。嵌入式系统初始化过程按照自底向上、从硬件到软件的次序依次为：片级初始化→板级初始化→系统初始化。

进程组成和状态

进程的组成：进程控制块PCB（唯一标志）、程序（描述进程要做什么）、数据（存放进程执行时所需数据）。
进程基础的状态是下左图的三态图。需要熟练掌握左下图的进程三态之间的转换。

【真题】

前趋图

用来表示哪些任务可以并行执行，哪些任务之间有顺序关系，具体如下图：可知，A B C可以并行执行，但是必须A B C都执行完毕后，才可以执行D，这就确定了两点：任务间的并行、任务间的先后顺序。

进程资源图

用来表示进程和资源之间的分配和请求关系，如下图所示： P 代表进程，R 代表资源。R 方框中有几个圆球就表示有几个这种资源，在上图中，R1 指向 P1，表示 R1 有一个资源已经分配给了 P1 ，P1 指向 R2，表示 P1 还需要请求一个 R2 资源才能执行。阻塞节点：某进程所请求的资源已经全部分配完毕，无法获取所需资源，该进程被阻塞了无法继续。如上图中的 P2。非阻塞节点：某进程所请求的资源还有剩余，可以分配给该进程继续运行。如上图中 P1、P3。当一个进程资源图中所有进程都是阻塞节点时，即陷入死锁状态。

【真题】

在如下所示的进程资源图中，（）；该进程资源图是（）。

A. P1、P2、P3都是阻塞节点
B. P1是阻塞节点、P2、P3是非阻塞节点
C. P1、P2是阻塞节点、P3是非阻塞节点
D. P1、P2是非阻塞节点、P3是阻塞节点

【C、B】
P3是非阻塞节点。
可以化简：最后能不能执行完，不进入到死锁状态。唯一能运行的是P3。

进程同步与互斥

临界资源：各进程间需要以互斥方式对其进行访问的资源。
临界区：指进程中对临界资源实施操作的那段程序。本质是一段程序代码。
互斥：某资源（即临界资源）在同一时间内只能由一个任务单独使用，使用时需要加锁，使用完后解锁才能被其他任务使用；如打印机。
同步：多个任务可以并发执行，只不过有速度上的差异，在一定情况停下等待，不存在资源是否单独或共享的问题；如自行车和汽车。
互斥信号量：对临界资源采用互斥访问，使用互斥信号量后其他进程无法访问，初值为1。
同步信号量：对共享资源的访问控制，初值一般是共享资源的数量。
P操作：申请资源，S=S-1，若S>=0，则执行P操作的进程继续执行；若S<0，则置该进程为阻塞状态（因为无可用资源），并将其插入阻塞队列。
V操作：释放资源，S=S+1，若S>0，则执行V操作的进程继续执行；若S<=0，则从阻塞状态唤醒一个进程，并将其插入就绪队列（此时因为缺少资源被操作阻塞的进程可以继续执行），然后执行V操作的进程继续。
经典问题：生产者和消费者的问题三个信号量：互斥信号量S0（仓库独立使用权），同步信号量S1（仓库空闲个数），同步信号量S2（仓库商品个数）。生产者流程：消费者流程：生产一个商品 S P(S0) P(S0) P(S2) P(S1) 取出一个商品将商品放入仓库中 V(S1) V(S2) V(S0) V(S0) 进程P1、P2、P3、P4和P5的前趋图如下图所示：

【真题】

26、A. V(S1)、P(S2)和V(S3)
B. P(S1)、V(S2)和V(S3)
C. V(S1)、V(S2)和V(S3)
D. P(S1)、P(S2)和V(S3)

27、A. P(S2)和P(S4)
B. P(S2)和V(S4)
C. V(S2)和P(S4)
D. V(S2)和V(S4)

28、A. P(S4)和V(S2)、V(S5)
B. V(S5)和P(S4)、P(S5)
C. V(S3)和V(S4)、V(S5)
D. P(S3)和P(S4)、P(S5)

【C、B、B】

【C、B、D】

进程调度

进程调度方式是指当有更高优先级的进程到来时如何分配CPU。分为可剥夺和不可剥夺两种。可剥夺指当有更高优先级进程到来时，强行将正在运行进程的CPU分配给高优先级进程；不可剥夺是指高优先级进程必须等待当前进程自动释放CPU。
在某些操作系统中，一个作业从提交到完成需要经历高、中、低三级调度。 (1) 高级调度。又称为“长调度”“作业调度”“接纳调度”，它决定处于输入池中的哪个后作业可以调入………………（后续只考虑重点知识点、真题）
先来先服务FCFS：先到达的进程优先分配CPU。用于宏观调度。
时间片轮转：
优先级调度：
多级反馈调度：

死锁

当一个进程在等待永远不可能发生的事件时，就会产生死锁，若系统中有多个进程处于死锁状态，就会造成系统死锁。

死锁产生的四个必要条件：资源互斥、每个进程占有资源并等待其他资源、系统不能剥夺进程资源、进程资源图是一个环路。

解决措施

死锁预防
死锁避免银行家算法
死锁检测允许死锁产生，系统定时运行一个检测死锁的程序，若检测到系统中发生死锁，则设法加以解除。
死锁解除死锁发生后的解除办法，如强制剥夺资源，撤销进程等。

死锁资源计算：系统内有n个进程，每个进程都需要R个资源。发生死锁最大资源数 n*(R-1)，其不会发生死锁的最小资源数为 n*(R-1)+1

【真题】

某系统中有3个并发进程竞争资源R，每个进程都需要 5 个R，那么至少有（）个R，才能保证系统不会发生死锁

13个。 n*(R-1)+1= 3*(5-1)+1=13

3，2，1，0，-1，……，-(n-3)

2、0和1

A.P1-P2-P4-P5-P3
B.P5-P2-P4-P3-P1
C.P4-P2-P1-P5-P3
D.P5-P1-P4-P2-P3

【B】

线程

传统的进程有两个属性：可拥有资源的独立单位；可独立调度和分配的基本单位。

分区存储管理

分区存储组织，就是整存，将某个进程运行所需的内存整体一起分配给它，然后再执行。有三种分区方式：

固定分区静态分区方法，将主存分为若干个固定的分区，将要运行的作业装配进去，由于分区固定，大小和作业需要的大小不同，会产生内部碎片。
可变分区动态分区方法，主存空间的分区是在作业转入时划分，正好划分为作业需要的大小，这样就不存在内部碎片，但容易将整片主存空间切割成许多块，会产生外部碎片。
可重定位分区可以解决碎片问题，移动所有已经分配好的区域，使其成为一个连续的区域，这样其他外部细小的分区碎片可以合并为大的分区，满足作业要求。

系统分配内存算法：

首次适应法
最佳适应法
最差适应法
循环首次适应法

分页存储管理

优点：利用率高，碎片小，分配及管理简单。
缺点：增加了系统开销，可能产生抖动现象。

2^20^个页，则页号为20个
4KB=2^12^个，则页内地址为12个

页号	页内地址
31、30、……、11、12 （20个）	11、10、……、1、0 （12个）

页面置换算法

最优算法：OPT，理论上的算法，无法实现，是在进程执行完后进行的最佳效率计算，用来让其他算法比较差距。原理是选择未来最长时间内不被访问的页面置换，这样可以保证未来执行的都是马上要访问的。
先进先出算法：FIFO，先调入内存的页最先被置换淘汰，产生抖动现象，即分配页数越多，缺页率可能越多（即效率越低）
最近最少使用：LRU
淘汰原则：优先淘汰最近未访问的，而后淘汰最近未修改的页面。

快表

快表是将页表存于Cache中；慢表是将页表存于内存上。慢表需要访问两次内存才能取出页，而快表是访问一次Cache和一次内存，因此更快。

【真题】

某计算机系统页面大小为4K，若进程的页面变换表如下所示，逻辑地址为十六进制1D16H。该地址经过变换后，其物理地址应为十六进制（）

页号	物理块号
0	1
1	3
2	4
3	6

3D16H

页号	页帧号	状态位	访问位	修改位
0	6	1	1	1
1	–	0	0	0
2	3	1	1	1
3	2	1	1	0

分段存储管理

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

【真题】

设某进程的段表如下所示，逻辑地址（）可以转换为对应的物理地址。

段号	基地址	段长
0	1598	600
1	486	50
2	90	100
3	1327	2988
4	1952	960

A.(0,1597)、(1,30)和(3,1390)
B.(0,128)、(1,30)和(3,1390)
C.(0,1597)、(2,98)和(3,1390)
D.(0,128)、(2,98)和(4,1066)

【B】
段号0中，128<=600，段号1中，30<=50，段号3中，1390<=2988

段页式存储管理

（从来没考过）

对进程空间先分段后分页

优点：空间浪费小、存储共享容易、存储保护容易、能动态链接。
缺点：由于管理软件的增加，复杂性和开销页增加。

设备管理概述

设备是计算机系统与外界交互的工具，具体负责计算机与外部的输入/输出工作，所以常称为外部设备（简称外设）。

I/O软件

设备管理技术

一台独占设备，在同一时间只能由一个进程使用，其他进程只能等待，且不知道什么时候打印机空闲，此时，极大得浪费了外设的工作效率。

【真题】

以下关于I/O软件的叙述中，正确的是（）

【C】
I/O软件隐藏了底层复杂的实现细节，只提供接口供用户方便地使用。

文件管理的概述

（不怎么考）

文件是具有符号名的、在逻辑上具有完整意义的一组相关信息项的集合。

文件的逻辑结构：有结构的记录式文件；无结构的流式文件。
文件的物理结构是指文件在物理存储设备上的存放方法，包括： (1) 连续结构 (2) 链接结构串联结构，它将逻辑上连续的文件信息（如记录）存放在不连续的物理块上，每个物理块设有一个指针指向下一个物理块。 (3) 索引结构 将逻辑上的连续信息（如记录）存放在不连续的物理块中，系统为每个文件建立一张索引表。索引表记录了文件信息所在的逻辑块号对应的物理块号，并将索引表的起始地址放在与文件对应的文件目录项中。 (4) 多个物理块的索引表在文件创建时由系统自动建立

索引文件结构

如图所示，系统中由13个索引节点，0-9为直接索引，即每个索引节点存放的是内容，假设每个物理盘大小为4KB，共可存4KB*10=40KB数据；

【真题】

A.517
B.1029
C.16513
D.66053

【C、D】
直接索引地址：0-4；一级间接地址索引1KB/4B=256个；二级间接地址索引可以存储1KB/4B=256个一级间接地址索引，即256KB*256KB。

文件目录

文件控制块中包含以下三类信息：基本信息类，存取控制信息类和使用信息类。

文件控制块的有序集合称为文件目录。

相对路径：是从当前路径开始的路径。
绝对路径：是从根目录开始的路径。
全文件名 = 绝对路径+文件名。

【真题】

【D、B】
路径最后一个可以省略。D中“ flash” 前面那个代表根目录，不能乱加。

文件存储空间管理

文件存取方法是指读/写文件存储器上的一个物理块的方法。通常有顺序存取和随机存取两种方法。

文件存储空间的管理：

空闲区表。适用于连续文件结构。将外存空间上的一个连续的未分配区域称为“空闲区”。操作系统为磁盘外存上的所有空闲区建立一张空闲表，每个表项对应一个空闲区。序号第一个空闲块号空闲块数状态 1 18 5 可用 2 29 8 可用 3 105 19 可用 4 — — 未用
位示图。这种方法是在外存上建立一张位示图（Bitmap），记录文件存储器的使用情况。每一位对应文件存储器上的一个物理块，取值 0 和1 分别表示空闲和占用。第 0 字节 1 0 1 0 0 1 …… 0 1 第1字节 0 1 1 1 0 0 …… 1 1 第…字节 0 0 0 0 0 0 …… 0 0
空闲块链。每个空闲物理块中有指向下一个空闲物理块的指针，所有空闲物理块构成一个链表。
成组链接法。例如，在实现时系统将空闲块分成若干组，每100个空闲块为一组，每组的第一个空闲块等级了下一组空闲块的物理盘块号和空闲块总数。假设某个组的第一个空闲块号等于0，意味着该组是最后一组，无下一组空闲块。

【真题】

A. -128
B. 256
C. 512
D. 1024

A. 1200
B. 3200
C. 6400
D. 8000

【C、D】
16385 / 32 = 512……1，所以需要513个字，即0~512号
1000GB / 4MB = 250*2^10^ bit，250*2^10^ bit / 32 bit = 250 * 32 = 8000
即位示图需要 8000个字来表示。

操作系统练习题

项目	最大资金	已用资金	尚需资金
P1	6	2	4
P2	8	3	5
P3	8	2	6
P4	10	3	7

项目	最大资金	已用资金	尚需资金
P1	—	—	—
P2	8	3	5
P3	8	2	6
P4	10	3	7

C.2、4、6、7，可用资金数为2，故资金周转状态是安全的

D.7

D.5、4、6，尚需资金数分别为3、4、4，故资金周转状态是不安全的

【①②：I2I3、③④：C1C2、⑤⑥：P2P3】

假设某分时系统采用简单时间片轮转法，当系统中的用户数为n、时间片为q时，系统对每个用户的相应时间T=（）

n*q

数据库技术基础【重要】

数据

数据：是数据库中存储的基本对象，是描述事物的符号记录。
种类：文本、图像、音频、视频等。

数据库DB：是长期存储在计算机内、有组织、可共享的大量数据的集合。

数据库的基本特征：
数据按一定的数据模型组织、描述和存储；
可为各种用户共享；
冗余度较小；
数据独立性较高；
易扩展。

数据库系统DBS：是一个采用了数据库技术，有组织地、动态地存储大量相关数据，方便多用户访问的计算机系统。

三级模式-两级映像

内模式：管理如何存储物理的数据，对应具体物理存储文件。

模式：概念模式，就是我们常用的基本表，根据应用需求将物理数据划分成一张张表。

外模式：对应数据库中的视图这个级别，将表进行一定的处理后再提供给用户使用

外模式-模式映像：是表和视图之间的映射，存在于概念级和外部级之间，若表中数据发生了修改，只需要修改此映射，而无需修改应用程序。

数据库设计

需求分析：即分析数据存储的要求，产出物有数据流图、数据字典、需求说明书。
概念结构设计：就是设计E-R图，也就是实体-联系图，与物理实现无关，说明有哪些实体，实体有哪些属性。
逻辑结构设计：将E-R图，转换成关系模式，也就是转换成实际的表和表中的列属性。
物理设计：根据生成的表等概念，生成物理数据库。

【真题】

在数据库系统中，数据库的视图、基本表和存储文件的结构分别于（）对应；数据的物理独立性和数据的逻辑独立性是分别通过修改（）来完成的。

外模式、模式、内模式
模式与内模式之间的映像、外模式与模式之间的映像

在数据库逻辑结构设计阶段，需要（）阶段形成的（）作为设计依据

A.需求分析
B.概念结构设计
C.物理结构设计
D.数据库运行和维护

A.需求文档、数据字典和数据流图
B.需求说明文档、程序文档和数据流图
C.需求说明文档、数据字典和数据流图
D.需求说明文档、数据字典和程序文档

【A、C】

数据模型

关系模型是二维表的形式表述的实体-联系模型

概念模型是从用户角度进行建模的，E-R，是现实世界到信息世界的第一抽象。

用E-R图来描述概念数据模型，世界是由一组称为实体的基本对象和这些对象之间的联系构成的。

在E-R模型中，使用椭圆表示属性、长方形表示实体、菱形表示联系，联系的两端要填写联系类型，示例如下：

实体：客观存在并可相互区别的事物。
弱实体和强实体：弱实体依赖于强实体的存在而存在。
实体集：具有相同类型和共享相同属性的实体的集合。
属性：实体所具有的特性。
属性分类：简单属性和复合属性；单值属性和多值属性；NULL属性；派生属性（可以计算出的）。
域：属性的取值范围称为该属性的域。
码（key）：唯一标识实体的属性集。
联系
联系类型：（一对一、一对多、多对多）。
两个以上实体型的联系：
关系模型中数据的逻辑结构是一张二维表，由行列组成。用表格结构表达实体集，用外键标识实体间的联系。如下图：

E-R模型转换为关系模型：每一个实体都对应一个关系模式；联系分三种：

1：1联系中，连续可以放到任意两端实体中，作为一个属性（要保证1：1的两端关联），也可以转换为一个单独的关系模式；

1：N的联系中，联系也可以单独作为一个关系模式，也可以在N端中加入1端实体的主键；

N：N的联系中，联系必须作为一个单独的关系模式，其主键是M和N端的联合主键。

【真题】

A.学生、学院
B.教师、学院
C.学生、课程
D.教师、课程

A.家长、学生
B.学生、教师
C.学生、学院
D.教师、学院

【C、A】

由于员工和项目之间的联系类型为（），所以员工和项目之间的联系需要转换成一个独立的关系模式，该关系模式的主键是（）

【多对多、（项目编号，员工代码）】

关系代数

并：结果是两张表中所有记录数合并，相同记录只显示一次。
交：结果是两张表中相同的记录
差：S1-S2，结果是S1表中有而S2表中没有的那些记录。

投影：实际是按条件选择某关系模式中的某列，列也可以用数字表示。

选择：实际是按条件选择某关系模式中的某条记录。

【真题】

给定关系R（A,B,C,D）和关系S（C,D,E），对其进行自然连接运算R⋈S后的属性列为（）个，与σ~R.B>S.E~（R⋈S）等价的关系代数表达式为（）

A.4
B.5
C.6
D.7

【B、D】

函数依赖

给定一个X，能唯一确定一个Y，就称X确定Y，或者说Y依赖于X，例如Y=X*X函数。

函数依赖又可扩展以下两种规则：

部分函数依赖：A可确定C，（A，B）也可确定C，（A，B）中的一部分（即A）可以确定C，称为部分函数依赖。
传递函数依赖：当A和B不等价时，A可确定B，B可确定C，则A可确定C，是传递函数依赖；若A和B等价，则不存在传递，直接就可确定C。

函数依赖的公理系统（Armstrong）
自反律、增广律、传递律、合并规则、伪传递律、分解规则。

键与约束

超键：能唯一标识此表的属性的组合。
候选键：超键中去掉冗余的属性，剩余的属性就是候选键
主键：任选一个候选键，即可作为主键。
外键：其他表中的主键。
主属性：候选键内的属性为主属性，其他属性为非主属性。
实体完整性约束：即主键约束，主键值不能为空，也不能重复。
参照完整性约束：即外键约束，外键必须是其他表中已经存在的主键的值，或者为空。
用户自定义完整性约束：自定义表达式约束，如设定年龄属性的值必须在0到150之间。

范式

第一范式1NF 关系中的每一个分量必须是一个不可分的数据项。通俗的说，第一范式就说表中不允许有小表的存在。比如，对于如下的员工表，就不属于第一范式：

实例：用一个单一的关系模式学生来描述学校的教务系统：学生（学号，学生姓名，系号，系主任姓名，课程号，成绩）

依赖关系（学号->学生姓名，学号->系号，系号->系主任姓名，学号->课程号，（学号，课程号）->成绩）

联合主键：（学号，课程号）

第二范式如果关系R属于1NF，且每一个非主属性完全函数依赖于任何一个候选码，则R属于2NF 即在1NF基础上，表中的每一个非主属性不会依赖复合主键中的某一个列

按照定义，上面的学生表就不满足2NF，因为学号不能完全确定课程号和成绩（每个学生可以选多门课）。

将学生表分解为：
学生（学号，学生姓名，系编号，系名，系主任）
选课（学号，课程号，成绩）
每张表均属于2NF。

第三范式在满足2NF的基础上，表中不存在非主属性对键的传递依赖。将学生表进一步分解为：学生（学号，学生姓名，系编号）
系（系编号，系名，系主任）
选课（学号，课程号，成绩）每张表都属于3NF。

第一范式：简单说列不能再分

第二范式：简单说建立在第一范式基础上，消除部分依赖

第三范式：简单说建立在第二范式基础上，消除传递依赖。

BC范式在3NF的基础上进一步消除主属性对码的部分函数依赖和传递依赖 简单说在每种情况下，每一个依赖的左边决定因素都必然包含候选键。如下：

上图中，候选键有两种情况：组合键（S，J）或者（S，T），依赖集为{SJ -> T，T -> J}，可知，STJ三个属性都是主属性因此其达到了3NF（无非主属性）。然而第二种情况，即（S，J）为候选键时候，对于依赖T -> J，T在这种情况下不是候选键，也就是左边的决定因素不包含任何候选码，所以上图不是BCNF。

要让上图关系模式转换成BCNF，只需要将 T -> J 改为 TS -> J即可，这样使它左边的决定因素包含了候选键之一。

【真题】

给定关系模式R（U，F），U={A，B，C，D}，F={AB->C，CD->B}。关系R（），且分别有（）。

A.只有1个候选关键字ACB
B.只有1个候选关键字BCD
C.有2个候选关键字ACD和ABD
D.有2个候选关键字ACB和BCD

A.0个非主属性和4个主属性
B.1个非主属性和3个主属性
C.2个非主属性和2个主属性
D.3个非主属性和1个主属性

【C、A】
根据依赖集F={AB->C，CD->B}，找出从未在右边出现过的属性，必然是候选键之一。以该属性为基础，根据依赖集再依次扩展，看能否遍历所有属性，将无法遍历的加入候选键中。在候选键中的属性均为主属性。

设有关系模式R（E，N，M，L，Q），其函数依赖集为F={E->N，EM->Q，M->L}。则关系模式R达到了（）；该关系模式（）。

A.1NF
B.2NF
C.3NF
D.BCNF

A.无需进行分解，因为已经达到了3NF
B.无需进行分解，因为已经达到了BCNF
C.尽管不存在部分函数依赖，但还存在传递依赖，所以需要进行分解
D.需要进行分解，因为存在冗余、修改操作的不一致性、插入和删除异常

【A、D】
不满足2NF

模式分解

范式之间的转换一般是通过拆分属性，即模式分解，将具有部分函数依赖和传递依赖的属性分离出来，来达到一步步优化，一般分为以下两种：

保持函数依赖分解对于关系模式R，有依赖集F，若对R进行分解，分解出来的多个关系模式，保持原来的依赖集不变，则为保持函数依赖的分解。另外，注意要消除掉冗余依赖（如传递依赖）。

实例：设原关系模式R（A，B，C），依赖集F（A->B，B->C，A->C}；将其分解为两个关系模式R1（A，B）和R2（B，C），此时R1中保持依赖A->B，R2保持依赖B->C，说明分解后的R1和R2是保持函数依赖的分解，因为A->C这个函数依赖实际是一个冗余依赖，可以由前两个依赖传递得到，因此不需要管。

保持函数依赖的判断

原理：

如果F上的每一个函数依赖都在其分解后的某一个关系上成立，则这个分解是保持依赖的（这是一个充分条件）。也就是简单方法，看函数每个依赖的左右两边属性是否在同一个分解模式中。
如果上述判断失败，并不能断言分解不是保持依赖的，还要使用下面通用方法来做进一步判断：

无损分解：分解后的关系模式能够还原处原关系模式，就是无损分解，不能还原就是有损。
当分解为两个关系模式，可以通过以下定义判断是否无损分解：定理：如果R的分解为p={R1，R2}，F为R所满足的函数依赖集合，分解p具有无损连接性的充分必要条件是R1∩R2 -> (R1 – R2)或者R1∩R2 -> (R2 – R1)。
当分解为三个及以上关系模式时，可以通过表格法求解，如下：

【真题】

给定关系模式R<U,F>, U={A,B,C,D,E}, F={B->A, D->A, A->E, AC->B }, 则R 的候选键为（），分解 p={R1 (ABCE), R2(CD)} （）。

A.CD
B.ABD
C.ACD
D.ADE

A.具有无损连接性，且保持函数依赖
B.不具有无损连接性，且保持函数依赖
C.具有无损连接性，但不保持函数依赖
D.不具有无损连接性，也不保持函数依赖

【A、D】

并发控制

事物：由一系列操作组成，这些操作，要么全做，要么全部做，拥有四种特性：

原子性
一致性
隔离性
持续性

并发控制存在的问题：

丢失更新：
不可重复读：
读脏数据：

三级封锁协议：

一级封锁协议：事物在修改数据R之前必须对其加 X锁，直到事物结束才释放，可解决丢失更新问题。
二级封锁协议：一级封锁协议的基础上加上事物T读数据R之前必须对其加S锁，读完后即可释放S锁。可解决丢失更新、读脏数据问题。
三级封锁协议：一级封锁协议加上事务T在读取数据R之前先对其加S锁，直到事务结束才释放。可解决丢失更新、读脏数据、数据重复读问题。

【真题】

数据库安全

静态转储：即冷备份。在转储期间不允许对数据库进行任何存取、修改操作；优点是非常快速的备份方法、容易归档。但是只能提供到某一时间点的恢复，不能做其他工作，不能按表或按用户恢复。
动态转储：即热备份。在转储期间允许对数据库进行存取、修改操作，因此，转储和用户事务可并发执行。优点是可在表空间或数据库文件级备份，数据库仍可使用，可达到秒级恢复；缺点是不能出错，否则后果严重，若热备份不成功，所得结果几乎全部无效。
完全备份：备份所有数据。
差量备份：仅备份上一次完全备份之后变化的数据。
增量备份：备份上一次备份之后变化的数据。
日志文件：DBMS把事务开始、事务结束以及对数据库的增删改每一次操作写入日志文件。一旦发生故障，DBMS可恢复数据库。

分布式数据库

局部数据库位于不同物理位置，使用一个全局DBMS将所有局部数据库联网管理，这就是分布式数据库。

分片模式：

水平分片：将表中水平的记录分别存放在不同的地方。
垂直分配：将表中垂直的列值分别存放在不同的地方。

分布透明性：

分片透明性：用户或应用程序不需要知道逻辑上访问的表具体是如何分块存储的。
位置透明性：应用程序不关心数据存储物理位置的改变。
逻辑透明性：用户或应用程序无需知道局部使用的是哪条数据模型。
复制透明性：用户或应用程序不关心复制的数据从何而来。

数据仓库技术

数据仓库是一个面向主题的、集成的、非易失的、且随时间变化的数据集合，用于支持管理决策。

数据源是数据仓库系统的基础，是整个系统的数据源泉。
数据的存储和管理是整个数据仓库系统的核心。
OLAP（联机分析）服务器对分析需要的数据进行有效集成，按多维模型组织，以便进行多角度、多层次的分析，并发现趋势。
前端工具各种报表工具、查询工具、数据分析工具、数据挖掘工具……

商业智能

BI系统主要包括数据预处理、建立数据仓库、数据分析和数据展现四个主要阶段。

反规范化技术

规范化设计后，数据库设计者希望牺牲部分规范化来提高性能。

益处：降低连接操作的需求、降低外码和索引的数目，还可能减少表的数目，能够提高查询效率。

问题：数据的重复存储、可能出现数据的完整性问题，为了保障数据的一致性，增加了数据维护的复杂性，会降低修改速度。

具体方法：

增加冗余列：在多个表中保留相同的列，增加数据冗余以减少或避免查询时的连接操作。
增加派生列：在表中增加可以由本表或其他表中数据计算生成的列，减少查询时的连接操作并避免计算或使用集合函数。
重新组表：如果许多用户需要查看两个表连接出来的结果数据，则把这两个表重新组成一个表来减少连接而提高性能。
水平分割表
垂直分割表

大数据

特点：大量化、多样化、价值密度低、快速化。

【真题】

为了保证数据库中数据的安全可靠和正确有效，系统在进行事务处理，对数据的插入、删除或修改的全部有关内容先写入（）；当系统正常运行时，按一定的时间间隔，把数据库缓冲区内容写入（）；当发生故障时，根据现场数据内容及相关文件来恢复系统状态。

【日志文件、数据文件】

数据仓库中数据（）的特点是指数据一旦进入数据仓库后，将被长期保留并定期加载和刷新，可以进行各种查询操作，但很少对数据进行修改和删除操作。

【相对稳定性】

SQL语言

SQL语言中语法关键字，不区分大小写：

创建表 create table;
指定主键 primary key();
指定外键 foreign key();
修改表 alter table;
删除表 drop table;
索引 index;
视图 view;

数据库查询 select …… from …… where……；
分组查询 group by，分组时要注意 select 后的列名要适应分组，为分组查询附加条件 having select sno,avg(score) from student group by having (avg(score)>60)
更名运算 as: select sno as “学号” from t1
字符串匹配 like、% 匹配多个字符串，_ 匹配任意一个字符串： select * from t1 where sname like ‘a_’
数据库插入 insert into……values(): insert into t1 values(‘a’,66)
数据库删除 delete……from……where: delete t1 where sno=4
数据库修改 update……set……where: update t1 set sname=’aa’ where sno=3
排序 order by，默认为升序，降序要加关键字 DESC： select * from t1 oder by sno desc

DISTINCT：过滤重复的选项，只保留一条记录
UNION：出现在两个SQL语句之间，将两个SQL语句的查询结果取或运算，即值存在于第一句或第二句都会被选出。
INTERSECT：对两个SQL语句的查询结果做与运算，即值同时存在于两个语句才被选出
MIN、AVG、MAX：分组查询时的聚合函数

【真题】

【A、A、D】

【C、A、D、B】

数据库练习题

【B】
在将三个实体之间的多对多联系（m:n:p ）转换为独立的关系模式时，该关系模式的关键字需要唯一标识所有参与实体的组合。根据E-R模型转换规则，此类联系的主键应由所有参与实体的关键字共同组成。

计算机网络

网络功能和分类

计算机网络的功能：数据通信、资源共享、负载均衡、高可靠性

计算机网络按 分布范围和拓扑结构 划分，如下图所示：

总线型（利用率低、干扰大、价格低）、星型（交换机形成的局域网、中央单元负荷大）、环形（流动方向固定、效率低扩充难）、树型（总线型的扩充、分级结构）、分布式（任意节点连接、管理难成本高）

OSI七层模型

局域网和广域网协议

以太网规范 IEEE 802.3 是重要的有线局域网协议，包括：

1	2	3	4
IEEE 802.3	标准以太网	10Mb/s	细同轴电缆
IEEE 802.3u	快速以太网	100Mb/s	双绞线
IEEE 802.3z	千兆以太网	1000Mb/s	光纤或双绞线
IEEE 802.3ae	万兆以太网	10Gb/s	光纤

无线局域网 WLAN 技术标准：IEEE 802.11

广域网协议（不需要）

TCP/IP 协议

网络协议三要素：语法、语义、时序。其中语法部分规定传输数据的格式，语义部分规定所要完成的功能，时序部分规定执行各种操作的条件、顺序关系等。

网络层协议：

IP：网络层最重要的核心协议，在源地址和目标地址之间传输数据报，无连接、不可靠。
ICMP：因特网控制报文协议，用于在 IP主机、路由器之间传递控制消息。控制消息是指网络通不通、主机是否可达、路由是否可用等网络本身的消息。
ARP 和 RARP ：地址解析协议，ARP是将 IP地址转换为物理地址，RARP 是将物理地址转换为 IP地址。
IGMP：网络组管理协议，允许因特网的计算机参加多播，是计算机用作向相邻多目路由器报告多目组成员的协议，支持组播。

传输层协议：

TCP：整个 TCP/IP协议族中最重要的协议之一，在 IP协议提供的不可靠数据基础上，采用了重发技术，为应用程序提供了一个可靠的、面向连接的、全双工的数据传输服务。一般用于传输数据量比较少，且对可靠性要求高的场合。
UDP：是一种不可靠、无连接的协议，有助于提高传输速率，一般用于传输数据量大，对可靠性要求不高，但要求速度快的场合。

TCP：三次握手，四次挥手。

应用层协议：基于 TCP的FTP、HTTP等都是可靠传输。基于 UDP的DHCP、DNS等都是不可靠传输。

TCP ：可靠的文件传输协议，用于因特网的控制文件的双向传输。
HTTP：超文本传输协议，用于从WWW服务器传输超文本到本地浏览器的传输协议。使用SSL加密的网页协议为HTTPS
SMTP 和 POP3：简单邮件传输协议，是一组用于源地址到目标地址传送邮件的规则，邮件报文采用 ASCII格式表示。
Telnet：远程连接协议，是因特网远程登陆服务的标准协议和主要方式。
TFTP：不可靠的、开销不大的小文本传输协议。
SNMP：简单网络管理协议，由一组网络管理的标准协议，包含一个应用层协议、数据库模型和一组资源对象。该协议能够支持网络管理系统。
DHCP：动态主机配置协议，基于UDP，基于C/S模型，为主机动态分配IP地址。三种方式：固定分配、动态分配、自动分配。
DNS：域名解析协议，通过域名解析出IP地址

协议端口号对照表：

【真题】

在 OSI 参考模型中能实现路由选择、拥塞控制与互连功能的层是（）

A.传输层
B.应用层
C.网络层
D.物理层

【C】

在 TCP/IP体系结构中，将IP地址转换为MAC地址的协议是（）

A.RARP
B.ARP
C.ICMP
D.TCP

【B】

下列网络互连设备中，属于物理层的是（）

A.交换机
B.中继器
C.路由器
D.网桥

【B】

传输介质

双绞线：将多根铜线按规则缠绕在一起，能够减少干扰；分为无屏蔽双绞线UTP和屏蔽双绞线STP，都是由一对铜线簇组成。也就是我们常说的网线；双绞线的传输距离在100米以内。

无屏蔽双绞线UTP

屏蔽双绞线STP

网线如下两种安装标准：都是八根不同颜色的网线，按照不同的顺序排序，插入水晶头中，区分在第1、2、3、6根网线的位置不同。

光纤：由纤芯和包层组成，传输的光信号在纤芯中传输，然而从PC端出来的信号都是电信号，要经过光纤传输的话，就必须将电信号转换为光信号。

多模光纤MMF：纤芯半径比较大，因此可同时传输多种不同的信号，光信号在光纤中以全反射的形式传输，采用发光二极管LED为光源，成本低，但是传输的效率和可靠性都较低，适合于短距离传输，其传输距离与传输速率相关，速率为100Mbps时为2KM，速率为1000Mbps时为550m。

单模光纤SMF：纤芯的半径很小，一般只能传输一种信号，采用激光二极管LD作为光源，并只支持激光信号的传播，同样是以全反射形式传播，只不过是反射角很大，看起来像一条直线，成本高，但是传输距离远，可靠性高。传输距离可用到5KM。

通信方式和交换方式

通信方向：数据通信是指发送方发送数据到接收方，这个传输过程可用分类如下：

单工：只能由设备A发给设备B，即数据流只能单向流动
半双工：设备A和设备B可以互相通信，但是同一时刻数据流只能单向流动。
全双工：设备A、B可以在任意时刻通信。

同步方式：

异步传输：发送方每发送一个字符，需要约定一个起始位和停止位插入到字符的起始和结尾位，这样当接收方接收到该字符时能够识别，但是这样会造成资源浪费，传输效率降低。
同步传输：以数据块为单位进行传输，当发送方要发送数据时，先发送一个同步帧，接收方收到后做好接收准备，开始接收数据块，结束后又会有结束帧确认，这样一次传输一个数据块，效率高。
串行传输：只有一根数据线，数据只能1bit挨个排队传送，适合低俗设备、远距离的传送，一般用于广域网中。
并行传输：有多根数据线，可以同时传输多个bit数据，适合高速设备的传送，常用于计算机内部各硬件模块之间。

交换方式：

电路交换：通信一方进行呼叫，另一方接收后，在二者之间会建立一个专用电路。特点为面向连接、实时性高、链路利用率低，一般用于语音视频通信。
报文交换：以报文为单位，存储转发模式，接收到数据后先存储，进行差错校验，没有错误则转发，有错误则丢弃，因此会有延时，但可靠性高，是面向无连接的。
分组交换：以分组为单位，也是存储转发模式，因为分组的长度比报文小，所以时延小于报文交换，可分为三种方式：
- 数据报：是现在主流的交换方式，各个分组携带地址信息，自由选择不同的路由路径传送到接收方，接收方接收到分组后再根据地址信息重新组装成原数据，是面向无连接的，但是不可靠的。
- 虚电路：发送方发送一个分组，接收方收到后二者之间建立了一个虚拟的通信线路，二者之间的分组数据交互都通过这条线路传送，在空闲的时候这条线路也可以传输其他数据，是面向连接的，可靠的。
- 信元交换：异步传输模式ATM采用的交换方式，本质是按照虚电路方式转发，只不过信元是固定长度的分组，共53B，其中5B为头部，48B为数据域，也是面向连接的、可靠的。

【真题】

以下关于光纤的说法中，错误的是（）

A.单模光纤的纤芯直径更细
B.单模光纤才有 LED 作为光源
C.多模光纤比单模光纤的传输距离近
D.多模光纤中广播在光导纤维以多种模式传播

【B】

【D】

IP地址表示

机器中存放的IP地址是32位的二进制代码，每隔8位插入一个空格，可提高可读性，为了便于理解和设置，一般会采用点分十进制方式来表示：将32位二进制代码每八位二进制转换成十进制，就变成了4个十进制数，而后在每个十进制间隔中插入，如下所示，最终为128.11.3.31：

因为每个十进制数都是由8个二进制数转换而来，因此每个十进制数的取值范围为 0-255

分类IP地址：IP地址分为四段，每段八位，共32位二进制数组成。

在逻辑上，这32位IP地址分为网络号和主机号，依据网络号位数不同，可以将IP地址分为以下几类：

无分类编址：即不按照A、B、C类规则，自动规定网络号，无分类编制格式：IP地址/网络号，示例：128.158.0.11/20 表示的IP地址为128.168.0.11，其网络号占20位，因此主机号占32-20=12位，也可以划分子网。

特殊IP地址

公有地址：通过它直接访问因特网。是全网唯一的IP地址。
私有地址：属于非注册地址，专门为组织机构内部使用，不能直接访问因特网，下表为私有地址范围：

其他特殊地址如下表所示：

子网划分

子网划分：一般在公司申请网络时，会直接获得一个范围很大的网络，如一个B类地址，因为主机数之间相差的太大了，不利于分配，我们一般采用子网划分的方法来划分网络，即自定义网络号位数，就能自定义主机号位数，就能根据主机个数来划分出最适合的方法，不会造成资源的浪费。

因此就有子网的概念，一般的IP地址按标准划分为A B C类后，可以进一步再划分，将主机号拿出几位作为子网号，可以划分出多个子网，此时IP地址组成为：网络号+子网号+主机号。

网络号和子网号都为1，主机号都为0，这样的地址为子网掩码。

需要注意的是，子网可以全为0和全为1，主机号不能全为0或全为1，因此，主机数需要-2，而子网数不用。

还可以聚合网络为超网，就是划分子网的逆过程，将网络号取出几位作为主机号，此时，这个网络内的主机数量就变多了，成为了一个更大的网络。

【真题】

把网络117.15.32.0/23划分为117.15.32.0/27，得到的子网是（）个，每个子网中可使用的主机地址是（）个

A.4
B.8
C.16
D.32

A.30
B.31
C.32
D.34

【C、A】

【C、D】

IPv6

主要是为了解决 IPv4地址数不够用的情况而提出的设计方案，IPv6具有以下特性：

IPv6地址长度为128位，地址空间增大了2^96^倍；
灵活的IP报文头部格式，使用一系列固定格式的扩展头部取代了IPv4中可变长度的选项字段。IPv6中选项部分的出现方法也有所变化，使路由器可以简单掠过选项而不做任何处理，加快了报文的处理速度。

IPv4和IPv6过渡期间，主要采用三种基本技术：

（1）双协议栈：主机同时运行IPv4和IPv6两套协议栈，同时支持两套协议，一般来说IPv4和IPv6地址之间存在某种转换关系，比如IPv6的低32位可以直接转换为IPv4地址，实现互相通信。

（2）隧道技术：这种机制用来在IPv4网络之上建立一条能够传输IPv6数据报的隧道。

（3）翻译技术，利用一台专门的翻译设备，在纯IPv4和纯IPv6之间转换。

网络规划与设计

三层模型将网络划分为核心层、汇聚层和接入层，每一层都有特定的作用

核心层 只负责高速的数据转发

汇聚层将网络业务连接到接入层，并实施与安全、流量、负载和路由相关的策略

接入层为用户提供了在本地网段访问应用系统的能力，还要解决相邻用户之间的互访需要，接入层要负责一些用户信息（例如用户IP地址、MAC地址和访问日志等）的收集工作和用户管理功能（包括认证和计费）

建筑物综合布线系统PDS：

【真题】

【B】
核心层：数据高速转发

【B】

廉价磁盘冗余阵列

RAID即磁盘冗余阵列技术，将数据分散存储在不同磁盘中，可并行读取，可冗余存储，提高磁盘访问速度，保障数据安全性。

RAID0将数据分散的存储在不同磁盘中，磁盘利用率100%，访问速度最快，但是没提供冗余和错误修复技术。

RAID1在成对的独立磁盘上产生互为备份的数据，增加存储可靠性，可以纠错，但磁盘利用率只有50%

RAID2 海明码校验

RAID3 奇偶校验

RAID5 在所有磁盘上交叉的存储数据及奇偶校验信息（所有校验信息存储总量为一个磁盘容量，但分布式存储在不同的磁盘上），读/写指针可同时操作。

网络存储技术

1.直接附加存储（DAS）：是指将存储设备通过SCSI接口直接连接到一台服务器上使用，其本身是硬件的堆叠，存储操作依赖于服务器，不带有任何存储操作系统。

存在问题：在传递距离、连接数量、传输速率等方面都受到限制。容量难以扩展升级；数据处理和传输能力降低；服务器异常会波及存储器。

2.网络附加存储（NAS）：通过网络接口与网络直接相连，由用户通过网络访问，有独立的存储系统。

NAS的性能特点是进行小文件级的共享存取，支持即插即用，可以很经济的解决存储容量不足的问题，但难以获得满意的性能。

3.存储区域网（SAN）：SAN是通过专用交换机将磁盘阵列和服务器连接起来的高速专用子网。它没采用文件共享存取方式，而是采用块（block）级的存储。SAN是通过专用高速网将一个或多个网络存储设备和服务器连接起来的专用存储系统。其最大的特点是将存储设备从传统的以太网中分离出来，成为独立的存储区域网络SAN的系统结构。根据数据传输过程采用的协议，其技术划分了FC SAN（光纤通道）、IP SAN（IP网络）和IB SAN（无限带宽）。

其他考点：

NAT 网络地址翻译：公司内有很多电脑，在公司局域网内可以互联通信，但要访问外部因特网时，只提供固定的少量IP地址能够访问因特网，将公司所有电脑这个大的地址集合映射到能够访问因特网的少量IP地址集合的过程就称为NAT。
很明显，使用了NAT后，一个公司只有少量固定IP地址可以上网，大大减少了IP地址的使用量。

默认网关：一台主机可以有多个网关。默认网关的意思是一台主机如果找不到可用的网关，就把数据包发给默认指定的网关，由这个网关来处理数据包。现在主机的网关一般指的是默认网关。默认网关的IP地址必须与本机IP地址在同一个网段内，即同网络号。

虚拟局域网 VLAN：是一组逻辑上的设备和用户，这些设备和用户并不受物理位置的限制，可用根据功能、部门及应用等因素将它们组织起来，相互之间的通信好像它们在同一个网段中一样。

VLAN工作在OSI参考模型的第二层和第三层，一个VLAN就是一个广播域，VLAN之间的通信是通过第三层路由器来完成的。

优点：网络设备的移动、添加和修改的管理开销减少；可用控制广播活动；可提高网络的安全性。

虚拟专用网 VPN：是在公用网络上建立专用网络的技术。其之所以称为虚拟网，主要是因为整个VPN网络的任意两个节点之间的连接并没有传统专网所需的端到端的物理链路，而是架构在公用网络服务商所提供的网络平台，如Internet、ATM（异步传输模式）、Frame Relay（帧中继）等之上的逻辑网络，用户数据在逻辑链路中传输。

冲突域和广播域

路由器可用阻断广播域和冲突域，交换机只能阻断冲突域，因此一个路由器下可用划分多个广播域和多个冲突域；一个交换机下整体就是一个广播域，但是可用划分多个冲突域；而物理层设备集线器下整体作为一个冲突域和一个广播域。

【真题】

一个虚拟局域网是一个（）

A.广播域
B.冲突域
C.组播域
D.物理上隔离的区域

以下关于URL的说法，错误的是（）

A.使用 www.abC.com 和 abC.com 打开的是同一个页面
B.在地址栏中输入 www.abC.com 默认使用 http 协议
C.www.abC.com 中的‘www’是主机名
D.www.abC.com 中的‘abC.com’是域名

【A】
URL：协议：// 域名：端口号 / 路径

计网练习题

在下图所示的网络配置中，发现工作站B无法与服务器A通信。（）故障影响了两者的互通

A.服务器A的IP地址是广播地址
B.工作站B的IP地址是网络地址
C.工作站B与网关不属于同一子网
D.服务器A与网关不属于同一子网

【D】首先，我们需要确定子网的网络地址和广播地址。对于 /27 子网掩码，每个子网有 32 个 IP 地址，其中第一个是网络地址，最后一个是广播地址。

对于 131.1.123.0/27 子网：

网络地址：131.1.123.0
广播地址：131.1.123.31

对于 131.1.123.32/27 子网：

网络地址：131.1.123.32
广播地址：131.1.123.63

以下关于VLAN的叙述中，属于其优点的是（）

A.允许逻辑地划分网段
B.减少了冲突域的数量
C.增加了冲突域的大小
D.减少了广播域的数量

【A】
VLAN（虚拟局域网）的主要优点之一是它允许网络管理员逻辑地划分网段，而不需要物理上的重新布线。这提高了网络的灵活性和管理效率。VLAN 实际上是增加了广播域的数量，因为它们将网络分割成多个广播域。

DHCP协议的功能是（）；FTP使用的传输层协议为（）。

A. WINS 名字解析
B. 静态地址分配
C. DNS名字登录
D. 自动分配IP地址

A. TCP
B. IP
C. UDP
D. HDLC

【D、A】
DHCP（动态主机配置协议）的主要功能是自动分配 IP 地址给网络中的设备，以便它们可以通信
FTP（文件传输协议）使用 TCP（传输控制协议）作为其传输层协议，因为 TCP 提供了可靠的、面向连接的数据传输服务，这对于文件传输非常重要。

集线器与网桥的区别是：（）

A.集线器不能检测发送冲突，而网桥可用检测冲突
B.集线器是物理层设备，而网桥是数据链路层设备
C.网桥只有两个端口，而集线器是一种多端口网桥
D.网桥是物理层设备，而集线器是数据链路层设备

【B】
集线器和中继器是物理层设备，网桥和交换机是数据链路层设备。

POP3 协议采用（）模式，客户端代理与POP3服务器通过建立TCP连接来传送数据。

A. Browser/Server
B. Client/Server
C. Peer to Peer
D. Peer to Seer

【B】
题目已经指出是客户端代理和服务器代理

TCP 使用的流量控制协议是（）

A. 固定大小的滑动窗口协议
B. 后退N帧的ARQ 协议
C. 可变大小的滑动窗口协议
D. 停等协议

【C】

在以下4种路由中，（）路由的子网掩码是 255.255.255.255

A.远程网络
B.静态
C.默认
D.主机

【D】
子网掩码全1，则网络号全1，没主机号，只有主机本身不需要主机号来确定身份

默认情况下，FTP 服务器的控制端口为（），上传文件时的端口为（）

A.大于1024的端口
B.20
C.80
D.21

【D、B】
记忆。FTP 控制端口默认为21，上传文件端口为20

使用 ping 命令可以进行网络检测，在进行一系列检测时，按照由近及远原则，首先执行的是（）

A. ping 默认网关
B. ping 本地IP
C. ping 127.0.0.1
D. ping 远程主机

【C】

某 PC 的 Internet 协议属性参数如下图所示，默认网关的 IP 地址是（）

A. 8.8.8.8
B. 202.117.115.3
C. 192.168.2.254
D. 202.117.115.18

【C】
通常默认网关的 IP 地址与 PC 的 IP 地址在同一子网内。PC 的 IP 地址是 192.168.2.1，子网掩码是 255.255.255.0，因此默认网关的 IP 地址应该在 192.168.2.x 范围内。

在下图的 SNMP 配置中，能够响应 Manager2 的 getRequest 请求的是（）

A. Agent 1
B. Agent 2
C. Agent 3
D. Agent 4

【A】
在简单网络管理协议 SNMP 中，只有作为同一团体成员的代理和管理器才能相互通信。

以下协议中属于应用层协议的是（），该协议的报文封装在（）。

A. SNMP
B. ARP
C. ICMP
D. X.25

A. TCP
B. IP
C. UDP
D. ICMP

【A、C】
SNMP 简单网络管理协议，是基于 UDP 的应用层协议

某公司内部使用 WB.xyz.com.cn 作为访问某服务器的地址，其中 WB 是（）

A. 主机名
B. 协议名
C. 目录名
D. 文件名

【A】

如果路由器收到了多个路由协议转发的关于某个目标的多条路由，那么决定采用哪条路由的策略是（）

A. 选择与自己路由协议相同的
B. 选择路由费用最小的
C. 比较各个路由的管理距离
D. 比较各个路由协议的版本

【C】

与地址 220.112.179.92 匹配的路由表的表项是（）

A. 220.112.145.32/22
B. 220.112.145.64/22
C. 220.112.147.64/22
D. 220.112.177.64/22

【D】

220.112.179.92：1011 0011
220.112.177.64：1011 0001

【C】
UDP 和 TCP 是基于 IP 协议

在异步通信中，每个字符包含 1位起始位、7位数据位和 2位终止位，若每秒传送 500个字符，则有效数据速率位（）

【3500 b/s】

以下路由策略中，依据网络信息经常更新路由的是（）

A. 静态路由
B. 洪泛式
C. 随机路由
D. 自适应路由

【D】

相比于 TCP，UDP的优势为（）

A.可靠传输
B.开销较小
C.拥塞控制
D.流量控制

【B】

若一台服务器只开放了 25和110 两个端口，那么这台服务器可以提高（）服务

A. E-Mail
B. WEB
C. DNS
D. FTP

【A】
25 是 SMTP 端口，110是 POP3 端口。都是提供电子邮件服务的。

SNMP 是一种异步请求/响应协议，采用（）协议进行封装。

A. IP
B. ICMP
C. TCP
D. UDP

【D】
SNMP 是简单网络管理协议，是基于 UDP 的协议。

在一台安装好 TCP / IP 协议的计算机上，当网络连接不可用时，为了测试编写好的网络程序，通常使用的目的主机IP地址为（）

A. 0.0.0.0
B.127.0.0.1
C.10.0.0.1
D.210.225.21.255/24

【B】

测试网络连通性常用的命令是（）

A. Netstat
B. Ping
C. Msconfig
D. Cmd

【B】

下列网络互连设备中，属于物理层的是（）

A.交换机
B.中继器
C.路由器
D.网桥

【B】

在地址 http://www.dailynews.com.cn/channel/welcome.htm 中，www.dailynews.com.cn 表示（），welcome.htm 表示（）

A.协议类型
B.主机
C.网页文件名
D.路径

【B、C】

在Linux中，要修改一个文件的权限设置可使用命令（）

A.attrib
B.modify
C.chmod
D.change

【C】

主域名服务器在接收到域名请求后，首先查询的是（）

A. 本地hosts文件
B.转发域名服务器
C.本地缓存
D.授权域名服务器

【C】
首先查询本地缓存。

信息安全

信息安全和信息系统安全

信息安全系统的体系架构 X轴是“安全机制”，为提供某些安全服务，利用各种安全技术和技巧，所形成的一个较为安全的机构体系。 Y轴是“OSI网络参考模型”。 Z轴是“安全服务”。就是从网络中的各个层次提供给信息应用系统所需要的安全服务支持。由X、Y、Z三个轴形成的信息安全系统三维空间就是信息系统的“安全空间”。
随着网络逐层扩展，这个空间范围逐步加大，安全的内涵也就更丰富，达到具有认证、权限、完整、加密和不可否认五大要素，也叫做“安全空间”的五大属性。

信息安全含义及属性：保护信息的保密性、完整性、可用性，另外也包括其他属性，如：真实性、可核查性、不可否认性和可靠性。

保密性：信息不被泄露给未授权的个人、实体和过程或不被其使用的特性。包括(1) 最小授权原则 (2) 防暴露 (3) 信息加密 (4) 物理保密
完整性：信息未经授权不能改变的特性。 (1) 协议：通过安全协议检测被删除、失效、被修改的字段 (2) 纠错编码方法：校验码的检错和纠错功能 (3) 密码校验和方法 (4) 数字签名：能识别出发送方来源 (5) 公证：请求系统管理或者中介机构证明信息的真实性
可用性：需要时，授权实体可以访问和使用的特性。一般用系统正常使用时间和整个工作时间之比来度量。

其他属性：

真实性：指对信息的来源进行判断
可核查性：系统实体的行为可被独一无二地追溯到该实体的特性
不可否认性：建立有效责任机制，防止用户否认其行为
可靠性：系统在规定的时间和给定条件下，无故障完成规定功能的概率

安全需求：

可划分为物理线路安全、网络安全、系统安全和应用安全；
- 物理线路就是物理设备、物理环境
- 网络安全指网络上的攻击、入侵
- 系统安全指的是操作系统漏洞、补丁
- 应用安全指上层应用软件，包括数据库软件

【真题】

在网络安全管理中，加强内防内控可采取的策略由（）

①控制终端接入数量
②终端访问授权，防止合法终端越权访问
③加强终端的安全检查与策略管理
④加强员工上网行为管理与违规

【1、2、3、4】

在网络设计和实施过程中要采用多种安全措施，其中（）是针对系统安全需求的措施

A.设备防雷击
B.入侵检测
C.漏洞发现与补丁管理
D.流量控制

【C】

信息安全技术

加密技术一个密码系统，由五部分组成： (1) 明文空间 M，它是全体明文的集合 (2) 密文空间 C，它是全体密文的集合 (3) 密钥空间 K，它是全体密钥的集合。
其中每一个密钥 K 均由加密密钥Ke 和解密密钥Kd 组成，
即 K= < Ke，Kd > (4) 加密算法 E，它是一组由 M至C 的加密交换 (5) 解密算法 D，它是一组由 C至M 的解密变换
对于明文空间 M 中的每一个明文 M，加密算法 E 在密钥 Ke 的控制下，将明文 M 加密成密文 C：C = E(M,Ke)

对称加密技术

数据的加密和解密的密钥相同，属于不公开密钥加密算法。其缺点是加密强度不高（因为密钥位数少），且密钥分发困难（因为密钥还需要传输给接收方，也要考虑保密性等问题）。有点事加密速度快，适合加密大数据。

常见的对称密钥加密算法如下：

DES：替换+移位、56位密钥、64位数据块、速度快，密钥易产生。

3DES：三重DES，两个56位密钥K1、K2

加密：K1加密 -> K2解密 -> K1加密

解密：K1解密 -> K2加密 -> K1解密

AES

RC-5

IDEA：128位密钥，64位数据块，比DES的加密性好，对计算机功能要求相对低。

非对称加密技术

数据的加密和解密的密钥是不同的，分为公钥和私钥。是公开密钥加密算法。其缺点是加密速度慢。优点是安全性高，不容易破解。

非对称加密的原理是：发送方发送数据时，使用接收者的公钥作为加密密钥，私钥作为解密密钥，这样只有接收者才能解密密钥得到明文。安全性更高，因为无需传输密钥。但无法保证完整性。如下：

常见的非对称加密算法如下：

RSA：512位或1024位密钥，计算量极大，难破解

ECC（椭圆曲线算法）、背包算法、Rabin、D-H等

相比较可得知，对称加密过程简单，适合加密大量数据，也因此加密强度不高。而非对称密钥算法密钥由1024位，相对于的解密计算量庞大，难以破解，却不适合加密大数据，一般用来加密对称算法的密钥，这样，两个技术组合使用，就是数字信封的原理：

数字信封原理：信是对称加密的密钥，数字信封就是对此密钥进行非对称加密，具体过程：发送方将数据用对称密钥加密传输，而将对称密钥用接收方公钥加密发送给对方。接收方收到数字信封，用自己的私钥解密信封，取出对称密钥解密得原文。
数字信封运用了对称加密技术和非对称加密技术。本质是使用对称密钥加密数据，非对称密钥加密对称密钥，解决了对称密钥的传输问题。

信息摘要：

就是一段数据的特征信息，当数据发生了改变，信息摘要也会发生改变，发送方会将数据和信息摘要一起传给接收方，接收方会根据接收到的数据重新生成一个信息摘要，若此摘要和接收到的摘要相同，则说明数据正确。信息摘要是由哈希函数生成的。

特点：不算数据多长，都会产生固定长度的信息摘要；任何不同的输入数据，都会产生不同的信息摘要；单向性，即只能由数据生成信息摘要，不能由信息摘要还原数据。

信息摘要算法：MD5（产生128位的输出）、SHA-1（安全散列算法，产生160位的输出，安全性更高）。

数字签名：

唯一标识一个发送方。

发送者发送数据时，使用发送者的私钥进行加密，接收者收到数据后，只能使用发送者的公钥进行解密，这样就能唯一确定发送方，这也是数字签名的过程。但无法保证机密性。如下：

公钥基础设施PKI：是以不对称密钥加密技术为基础，以数据机密性、完整性、身份认证和行为不可抵赖性为安全目的，来实施和提供安全服务的具有普适性的安全基础设置。

(1) 数字证书：一个数据结构，是一个可信任的权威机构签署的信息集合。在不同的应用中由不同的整数。

公钥证书主要用于确保公钥及其与用户绑定关系的安全。这个公钥就是证书所标识的那个主体的合法的公钥。任何一个用户只要知道签证机构的公钥，就能检查对证书签名的合法性。如果检查正确，那么用户就可以相信那个证书所携带的公钥是真实的，而且这个公钥就是证书所表示的那个主题的合法的公钥。例如驾照。

(2) 签证机构CA：负责签发证书、管理和撤销证书。是所有注册用户所信赖的权威机构，CA在给用户签发证书时，要加上自己的数字签名，以保证证书信息的真实性。任何机构可以用CA的公钥来验证该证书的合法性。

【真题】

数字签名技术属于信息系统安全管理中保证信息（）的技术

A.保密性
B.可用性
C.完整性
D.可靠性

【C】数字签名是保证信息传输的完整性、发送者的身份认证、防止交易中的抵赖发生

为保障数据的存储和运输安全，防止信息泄露，需要对一些数据进行加密。由于对称密码算法（），所以特别适合对大量的数据进行加密

A.比非对称密码算法更安全
B.比非对称密码算法密钥更长
C.比非对称密码算法效率更高
D.还能同时用于身份认证

【C】

假设A、B之间要进行加密通信，则正确的非对称加密流程是（）

①A和B都要产生一对用于加密和解密的加密密钥和解密密钥
②A将公钥传送给B，将私钥自己保存，B将公钥传送给A，将私钥自己保存
③A发送消息给B时，先用B的公钥对信息进行加密，再将密文发送给B
④B收到A发来的消息时，用自己的私钥解密

【1、2、3、4】

甲向乙发送其数字签名，要验证该签名，乙可使用（）对该签名进行解密

A.甲的私钥
B.甲的公钥
C.乙的私钥
D.乙的公钥

【B】

网络安全技术

防火墙是在内部网络和外部因特网之间增加的一道安全防护措施，分为网络级防火墙和应用级防火墙。

网络级防火墙层次低，但是效率高。

应用级防火墙层次高、效率低。

入侵检测系统IDS

防火墙技术主要是分隔来自外网的威胁，却对来自内网的直接攻击无能为力，此时就要用到入侵检测IDS技术，位于防火墙之后的第二道屏障。

原理：监控当前系统/用户行为

IDS 入侵检测系统是一个监听设备，没有跨接在任何链路上，无需网络流量流经它就可以工作。对其唯一的要求是：IDS应当挂接在所有所关注流量都必须流经的链路上。（1）尽可能靠近攻击源 （2）尽可能靠近受保护资源。

计算机病毒和木马

病毒：编制或者在计算机程序中插入的破坏计算机功能或者破坏数据，影响计算机使用并且能够自我复制的一组计算机指令或者程序代码。
木马：是一种后门程序，常被黑客用作控制远程计算机的工具，隐藏在被控制电脑上的一个小程序，监控电脑一切操作并盗取信息。

【真题】

网络安全协议

SLL协议：安全套接字协议，被设计为加强Web安全传输（HTTP/HTTPS）的协议，端口号为：443

SSH协议：安全外壳协议，被设计为加强Telnet/FTP安全的传输协议

SET协议：安全电子交易协议主要用于B2C模式（电子商务）中保障支付信息的安全性。

Kerberos协议：是一种网络身份认证协议，该协议的基础是基于信任第三方，它提供了在开放型网络中进行身份认证的方法。

PGP协议：使用RSA公钥证书进行身份认证，使用IDEA（128位密钥）进行数据加密，使用MD5进行数据完整性验证。

发送方A有三个密钥：A的私钥、B的公钥、A生成的一次性对称密钥；

接收方B有两个密钥：B的私钥、A的公钥。

【真题】

下面可提供安全电子邮件服务的是（）

A. RSA
B. SSL
C. SET
D. S/MIME

【D】

【B】

网络管理员通过命令行方式对路由器进行管理，要确保 ID、口令和会话内容的保密性，应采用的访问控制是（）

A.控制台
B.AUX
C.TELENT
D.SSH

【D】

知识产权和标准化

知识产权是指公民、法人、非法人单位对自己的创造性智力成果和其他科技成果依法享有的民事权。是智力成果的创造人依法享有的权利和在生产经营活动中标记所有人依法所享有的权利总称。包含著作权、专利权、商标权等。

无体性：知识产权的对象是没有具体形体，是智力创造的成果。
专有性：除了权利人同意或法律规定外，权利人以外的任何人不得享有或使用该项权利。
地域性：知识产权只在授予其权利的国家或确认其权利的国家产生，并且只能在该国范围内受法律保护，而其他国家则不受保护。
时间性：仅在法律规定的期限内受到保护，一旦超过期限，权利自行消灭，相关知识产品即成为整个社会的共同财富，为全人类所共有的。

保护期限

知识产权具有地域限制，保护期限各种情况如下表所示：

商标可以续注

知识产权人的确定

(1) 职务作品

离职、退休或调动工作后1年内，与原单位工作相关，单位享有权利

(2) 委托作品

单位和委托的区别在于，当合同中未规定著作权归属时，著作权默认归于单位，而委托创作中，著作权默认归属于创作方个人。

同时申请：同一天申请。

侵权判定

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

开发软件所用的思想、处理过程、操作方法或者数学概念不受保护。

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

法律、法规、国家机关的决议、决定、命令和其他具有立法、行政、司法性质的文件，及其官方正式译文：时事新闻、历法、通用数表、通用表格和公式

【真题】

关于知识产权的理解，不正确的是（）

A. 知识产权的客体不是有形物，而是知识、信息等抽象物
B. 知识产权具有地域性，即在本国获得成人和保护的知识产权不具有域外效力
C. 对于专利性的域外效力，可以依赖国际公约或者双边协定取得
D. 知识产权具有一定的有效期限，无法永远存续

【C】

李某购买了一张有注册商标的应用软件光盘，则李某享有（）

A. 注册商标专用权
B. 该光盘的所有权
C. 该软件的著作权
D. 该软件的复制权

【B】

根据著作权法规定，当著作权属于公民时，著作权人署名权的保护期为（）

【永久】

甲乙两人分别独立开发处相同主题的阀门，但甲完成在先，乙完成在后。依据专利法规定，（）

A. 甲享有专利申请权，乙不享有
B. 甲不享有专利申请权，乙享有
C. 甲、乙都享有专利申请权
D. 甲、乙都不享有专利申请权

【C】

标准划分

国际标准、国家标准、行业标准、区域/地方标准和企业标准。

国家标准：强制性国家标准GB、推荐性国家标准GB/T、国家标准指导性文件GB/Z，国军标GJB

程序设计语言基础知识

程序设计语言的基本概念

程序设计语言是为了书写计算机程序而人为设计的符号语言，用于对计算过程进行描述、组织和推导。

低级语言：机器语言（计算机硬件只能识别 0和1 的指令序列），汇编语言。
高级语言：功能更强，抽象级别更高，与人们使用的自然语言比较接近。
各程序设计语言特点： Fortran语言：科学计算，执行效率高 Pascal语言：为教学开发，表达能力强 C语言：指针操作能力强，可以开发系统级软件，高效 C++语言：面向对象，高效 Java语言：面向对象，中间代码，跨平台 C#语言：面向对象，中间代码，.Net框架 Python是一种面向对象、解释型计算机程序设计语言 Prolog是逻辑型程序设计语言。

汇编：将汇编语言翻译成目标程序执行

解释和编译：将高级语言翻译执行。不同之处在于编译程序生成独立的可执行文件，直接运行，运行时无法控制源程序，效率高。而解释程序不生成可执行文件，可以逐条解释执行，用于调试模式，可以控制源程序，因为还需要控制程序，因此执行速度慢，效率低。

程序设计语言定义三要素：语法、语义、语用

语法是指由程序设计语言的基本符号组成程序中的各个语法成分（包括程序）的一组规则，其中由基本字符构成的符号（单词）的书写规则称为词法规则，由符号构成语法成分的规则称为语法规则。
语义是程序设计语言中，按语法规则构成的各个语法成分的含义，可分为静态语义和动态语义。静态语义指编译时可以确定的语法成分的含义，而运行时刻才能确定的含义是动态语义。一个程序的执行效果说明了该程序的语义，它取决于构成程序的各个组成部分的语义。
语用表示了构成语言的各个记号和使用者的关系，涉及符号来源、使用和影响。

语言的实现则有个语境问题。语境是指理解和实现程序设计语言的环境，包括编译环境和运行环境。

程序设计语言的分类：

(1) 命令式和结构化程序设计语言

(2) 面向对象程序设计语言

(3) 函数式程序设计语言

(4) 逻辑型程序设计语言

程序设计语言的基本成分

数据成分：指一种程序设计语言的数据和数据类型。数据分为常量（程序运行时不可改变）、变量（程序运行时可以改变）、全局量（存储空间在静态数据区分配）、局部量（存储空间在堆栈区分配）。数据类型有整型、字符型、双精度、单精度浮点型和布尔型等。
运算成分：指明允许使用的运算符号和运算规则。包括算术运算、逻辑运算、关系运算、位运算等。
控制成分：指明语言允许表述的控制结构。包括顺序结构、选择结构、循环结构。如图所示：
传输成分：指明语言允许的数据传输方式。如赋值处理、数据的输入输出等。
函数：C程序有一个或多个函数组成，每个函数都有一个名字，其中有且仅有一个名字为main的函数作为程序运行时的起点。函数的使用设计3个概念：函数定义、函数声明和函数调用。
- 函数的定义包括两部分：函数首部和函数体。函数的定义描述了函数做什么和怎么做。函数定义的一般形式为：
返回值的类型函数名（形式参数表） //函数首部
{ 函数体；
}
- 函数的首部说明了函数返回值的数据类型、函数的名字和函数运行时所需的参数及类型。函数所实现的功能在函数体部分进行描述。
- 函数应该先声明后引用。如果程序中对一个函数的调用在该函数的定义之前进行，则应该在被调用前对被调用函数进行声明。函数原型用于声明函数。函数声明的一般形式为：返回值类型函数名(参数类型表);
- 函数调用的一般形式为：函数名（实参表）；
- 函数调用时实参和形参间交换信息的方法有值调用和引用调用两种
  1. 值调用。若实现函数调用时将实参的值传递给响应的形参，则称为是传值调用。在这种方式下形参不能向实参传递信息。
  在C语言中，要实现被调用函数对实参的修改，必须用指针作为参数。即调用时需要先对实参进行取地址运算，然后将实参的地址传递给指针形参。其本质上仍属于值调用。这种方法实现了间接内存访问。
  1. 引用调用。C++引入的概念，当形式参数为引用类型时，形参名实际上是实参的别名，函数中对形参的访问和修改实际上就是针对相应实参所作的访问和改变。

【真题】

【C】

【A】

【B】

【A】

编译程序的基本原理

编译程序对高级语言源程序进行编译的过程中，要不断收集、记录和使用源程序中一些相关符号的类型和特征等信息，并将其存入符号表中，编译过程如下：

词法分析：是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词（也成单词符号或者符号）。
语法分析：是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短句，如“程序”，“语句”，“表达式”等等。语法分析程序判断源程序在结构上是否正确。
语义分析：是编译过程的一个逻辑阶段。语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查，进行类型审查。如类型匹配、除法除数不为0等。又分为静态语义错误（在编译阶段能够查找出来）和动态语义错误（只能在运行时发现）。
中间代码和目标代码：中间代码是根据语义分析产生的，需要经过优化链接，最终生成可执行的目标代码。引入中间代码的目的是进行与机器无关的代码优化处理。常用的中间代码有后缀式（逆波兰式）、三元式（三地址码）、四元式和树等形式。
需要考虑三个问题：
1. 如何生成较短的目标代码
2. 如何充分利用计算机中的寄存器，减少目标代码访问存储单元的次数
3. 如何充分利用计算机指令系统的特点，以提高目标代码的质量
前缀表达式： +ab
中缀表达式： a+b
后缀表达式： ab+ 主要掌握以上三种表达式即可，其实就是树的三种遍历，一般正常的表达式是中序遍历，即中缀表达式，根据其构造出树，再按题目要求求出前缀或后缀式。
简单求法：后缀表达式是从左到右开始，先把表达式加上括号，再依次把运算符加到本层次的括号后面。

【真题】

表达式 (a-b) * (c+d) 的后缀式（逆波兰式）是（）

A. abcd-+*
B. ab-c+d*
C. abc-d/-*
D. ab-cd+*

【D】

将编译器的工作过程划分为词法分析，语法分析，语义分析，中间代码生成，代码优化和目标代码生成时，语义分析阶段的输入是（）。若程序中的括号不配对，则会在（）阶段检查出错误。

【记号流、语法分析】

以编译方式翻译 C/C++源程序的过程中，（）阶段的主要任务是对各条语句的结构进行合法性分析。

【语法分析】

文法定义

文法G 是一个四元组，可表示为 G=（V,T,P,S），其中：

V：非终结符，不是语言组成部分，不是最终结果，可以推导出其他元素。
T：终结符，是语言的组成部分，是最终结果，不能再推导其他元素。
S：起始符，是语言开始的符号。
P：产生式，用终结符代替非终结符的规则，例如a->b。

乔姆斯基把文法分为4种类型，即0、1、2、3型。

0型文法，即短语文法，其功能相当于图灵机，任何0型语言都是递归可枚举的；反之，递归可枚举集也必定是一个 0型语言。
1型文法，即上下文有关文法，这种文法意味着对非终结符的替换必须考虑上下文，并且一般不允许替换成空串。
2型文法，即上下文无关文法，非终结符的替换无需考虑上下文。程序设计语言中大部分语法都是上下文无关文法，当然语义上是相关的。
3型文法，等价于正规式。

正规式

语言中具有独立含义的最小语法单位是符号（单词），如标识符、无符号常数与界限符等。词法分析的任务是把构成源程序的字符串转换成单词符号序列。

词法规则可用3型文法（正规文法）或正规表达式描述，它产生的集合是语言规定的基本字符集∑（字母表）上的字符串的一个子集，称为正规集。

正规式和正规集：

仅通过有限次地使用上述3个步骤定义的表达式，才是∑上的正规式，其中运算符 “ | ”、“ · ”、“ ”分别称为“或”、“连接”和“闭包”。在正规式的书写中，连接运算符 “ · ”可省略，运算的优先级从高到低的排序为“ ”、“ · ”、“ | ”

设∑={a，b}，如下表：

【真题】

在仅由字符a、b构成的所有字符串中，其中以b结尾的字符串集合可用正规式表述为（）

A. (b | ab)*b
B. (ab*)*b
C. a*b*b
D. (a | b)*b

【D】

由字符a、b构成的字符串中，若每个a 后至少跟一个b，则该字符串集合可用正规式表示为（）

A. (b | ab)*
B. (ab*)*
C. (a*b*)*
D. (a | b)*

【A】

简单算术表达式的结构可以用下面的上下文无关文法进行描述（E 为开始符号），（）是符合该文法的句子。

【B】

有限自动机

有限自动机是一种识别装置的抽象概念，它能准确地识别正规集。有限自动机分为：

【真题】

【A】

语法分析方法（不需要了解太多）

自上而下语法分析：最左推导，从左至右

递归下降思想：原理是利用函数之间的递归调用模拟语法树自上而下的构造过程。

自下而上语法分析：最右推导，从右至左

移进-规约思想：设置一个栈，将输入符号逐个移进栈中，栈顶形成某产生式。

数据结构

线性结构

线性结构：每个元素最多只有一个出度和一个入度，表现为一条线状。线性表按存储方式分为顺序表和链表。
存储结构：顺序存储：用一组地址连续的存储单元一次存储线性表中的数据元素，使得逻辑上相邻的元素物理上也相邻链式存储：存储各数据元素的结点的地址并不要求是连续的，数据元素逻辑上相邻，物理上分开。

顺序存储和链式存储的对比如下图所示：

在空间方面，因为链表还需要存储指针，因此有空间浪费存在。

在时间方面，当需要对元素进行破坏性操作（插入、删除）时，链表效率更高，因为其只需要修改指针指向即可，而顺序表因为地址是连续的，当删除或插入一个元素后，后面的其他节点位置都需要变动。

而当需要对元素进行不改变结构操作时（读取、查找），顺序表效率更高，因为其物理地址是连续的，如同数组一般，只需按索引号就可快速定位，而链表需要从头节点开始，一个个查找下去。

栈和队列：

队列、栈结构如图：

队列是先进先出，分队头和队尾；

栈是先进后出，只有栈顶能进出。

循环队列：

设循环队列Q 的容量为 MAXSIZE，初始时队列为空，且Q.rear 和Q.front 都等于0

元素入队时修改队尾指针，即令 Q.rear = (Q.rear + 1 ) % MAXSIZE

元素出队时修改队头指针，即令 Q.front = (Q.front + 1) % MAXSIZE

根据队列操作的定义，当出队操作导致队列变空时，有Q.rear == Q.front；

若入队操作导致队列满，则Q.rear == Q.front。

在队列空和队列满的情况下，循环队列的队头、队尾指针指向的位置都是相同的，此时仅仅根据Q.rear 和Q.front之间的关系无法断定队列的状态。为了区别队空和队满的情况，可以采用以下两种处理方式：其一是设置一个标志，以区别头、尾指针的值相同时，队列是空还是满；其二是牺牲一个存储单元，约定“以队列的尾指针所指位置的下一个位置是队头指针时”，表示队列满，如图所示，而头、尾指针的值相同时表示队列为空。

【真题】

对于线性表，相对于顺序存储，采用链表存储的缺点是（）

A. 数据元素之间的关系需要占用存储空间，导致存储密度不高
B. 表中结点必须占用地址连续的存储单元，存储密度不高
C. 插入新元素时需要遍历整个链表，运算的时间效率不高
D. 删除元素时需要遍历整个链表，运算的时间效率不高

【A】

若一个栈初始为空，其输入序列是 1，2，3，……，n-1，n，其输出序列的第一个元素为k（1≤k≤[ n/2 ]），则输出序列的最后一个元素是（）

A. 值为n的元素
B. 值为1的元素
C. 值为n-k的元素
D. 不确定的

【D】

某双端队列如下图所示，要求元素进出队列必须在同一端口，即从A端进入的元素必须从A端处，从B端进入的元素必须从B端处，则对于4个元素的序列e1、e2、e3、e4，若要求前两个元素（e1、e2）从A端口按次序全部进入队列，后两个元素（e3、e4）从B端口按次序全部进入队列，则可能得到的出队序列是（）

A. e1、e2、e3、e4
B. e2、e3、e4、e1
C. e3、e4、e1、e2
D. e4、e3、e2、e1

【D】

设循环队列定义中有front 和 size两个域变量，其中Front表示队头元素的指针，SIZE表示队列的长度，如下图所示（队列长度3，队头元素X，队尾元素为Z）。设队列的存储空间容量为M，则队尾元素的指针为（）

函数依赖的公理系统（Armstrong）
自反律、增广律、传递律、合并规则、伪传递律、分解规则。

键与约束

超键：能唯一标识此表的属性的组合。
候选键：超键中去掉冗余的属性，剩余的属性就是候选键
主键：任选一个候选键，即可作为主键。
外键：其他表中的主键。
主属性：候选键内的属性为主属性，其他属性为非主属性。
实体完整性约束：即主键约束，主键值不能为空，也不能重复。
参照完整性约束：即外键约束，外键必须是其他表中已经存在的主键的值，或者为空。
用户自定义完整性约束：自定义表达式约束，如设定年龄属性的值必须在0到150之间。

范式

第一范式1NF 关系中的每一个分量必须是一个不可分的数据项。通俗的说，第一范式就说表中不允许有小表的存在。比如，对于如下的员工表，就不属于第一范式：

实例：用一个单一的关系模式学生来描述学校的教务系统：学生（学号，学生姓名，系号，系主任姓名，课程号，成绩）

依赖关系（学号->学生姓名，学号->系号，系号->系主任姓名，学号->课程号，（学号，课程号）->成绩）

联合主键：（学号，课程号）

第二范式如果关系R属于1NF，且每一个非主属性完全函数依赖于任何一个候选码，则R属于2NF 即在1NF基础上，表中的每一个非主属性不会依赖复合主键中的某一个列

按照定义，上面的学生表就不满足2NF，因为学号不能完全确定课程号和成绩（每个学生可以选多门课）。

将学生表分解为：
学生（学号，学生姓名，系编号，系名，系主任）
选课（学号，课程号，成绩）
每张表均属于2NF。

第三范式在满足2NF的基础上，表中不存在非主属性对键的传递依赖。将学生表进一步分解为：学生（学号，学生姓名，系编号）
系（系编号，系名，系主任）
选课（学号，课程号，成绩）每张表都属于3NF。

第一范式：简单说列不能再分

第二范式：简单说建立在第一范式基础上，消除部分依赖

第三范式：简单说建立在第二范式基础上，消除传递依赖。

BC范式在3NF的基础上进一步消除主属性对码的部分函数依赖和传递依赖 简单说在每种情况下，每一个依赖的左边决定因素都必然包含候选键。如下：

要让上图关系模式转换成BCNF，只需要将 T -> J 改为 TS -> J即可，这样使它左边的决定因素包含了候选键之一。

【真题】

给定关系模式R（U，F），U={A，B，C，D}，F={AB->C，CD->B}。关系R（），且分别有（）。

A.只有1个候选关键字ACB
B.只有1个候选关键字BCD
C.有2个候选关键字ACD和ABD
D.有2个候选关键字ACB和BCD

A.0个非主属性和4个主属性
B.1个非主属性和3个主属性
C.2个非主属性和2个主属性
D.3个非主属性和1个主属性

设有关系模式R（E，N，M，L，Q），其函数依赖集为F={E->N，EM->Q，M->L}。则关系模式R达到了（）；该关系模式（）。

A.1NF
B.2NF
C.3NF
D.BCNF

【A、D】
不满足2NF

模式分解

范式之间的转换一般是通过拆分属性，即模式分解，将具有部分函数依赖和传递依赖的属性分离出来，来达到一步步优化，一般分为以下两种：

保持函数依赖分解对于关系模式R，有依赖集F，若对R进行分解，分解出来的多个关系模式，保持原来的依赖集不变，则为保持函数依赖的分解。另外，注意要消除掉冗余依赖（如传递依赖）。

保持函数依赖的判断

原理：

如果F上的每一个函数依赖都在其分解后的某一个关系上成立，则这个分解是保持依赖的（这是一个充分条件）。也就是简单方法，看函数每个依赖的左右两边属性是否在同一个分解模式中。
如果上述判断失败，并不能断言分解不是保持依赖的，还要使用下面通用方法来做进一步判断：

无损分解：分解后的关系模式能够还原处原关系模式，就是无损分解，不能还原就是有损。
当分解为两个关系模式，可以通过以下定义判断是否无损分解：定理：如果R的分解为p={R1，R2}，F为R所满足的函数依赖集合，分解p具有无损连接性的充分必要条件是R1∩R2 -> (R1 – R2)或者R1∩R2 -> (R2 – R1)。
当分解为三个及以上关系模式时，可以通过表格法求解，如下：

【真题】

给定关系模式R<U,F>, U={A,B,C,D,E}, F={B->A, D->A, A->E, AC->B }, 则R 的候选键为（），分解 p={R1 (ABCE), R2(CD)} （）。

A.CD
B.ABD
C.ACD
D.ADE

【A、D】

并发控制

事物：由一系列操作组成，这些操作，要么全做，要么全部做，拥有四种特性：

原子性
一致性
隔离性
持续性

并发控制存在的问题：

丢失更新：
不可重复读：
读脏数据：

三级封锁协议：

一级封锁协议：事物在修改数据R之前必须对其加 X锁，直到事物结束才释放，可解决丢失更新问题。
二级封锁协议：一级封锁协议的基础上加上事物T读数据R之前必须对其加S锁，读完后即可释放S锁。可解决丢失更新、读脏数据问题。
三级封锁协议：一级封锁协议加上事务T在读取数据R之前先对其加S锁，直到事务结束才释放。可解决丢失更新、读脏数据、数据重复读问题。

【真题】

数据库安全

静态转储：即冷备份。在转储期间不允许对数据库进行任何存取、修改操作；优点是非常快速的备份方法、容易归档。但是只能提供到某一时间点的恢复，不能做其他工作，不能按表或按用户恢复。
动态转储：即热备份。在转储期间允许对数据库进行存取、修改操作，因此，转储和用户事务可并发执行。优点是可在表空间或数据库文件级备份，数据库仍可使用，可达到秒级恢复；缺点是不能出错，否则后果严重，若热备份不成功，所得结果几乎全部无效。
完全备份：备份所有数据。
差量备份：仅备份上一次完全备份之后变化的数据。
增量备份：备份上一次备份之后变化的数据。
日志文件：DBMS把事务开始、事务结束以及对数据库的增删改每一次操作写入日志文件。一旦发生故障，DBMS可恢复数据库。

分布式数据库

局部数据库位于不同物理位置，使用一个全局DBMS将所有局部数据库联网管理，这就是分布式数据库。

分片模式：

水平分片：将表中水平的记录分别存放在不同的地方。
垂直分配：将表中垂直的列值分别存放在不同的地方。

分布透明性：

数据仓库技术

数据仓库是一个面向主题的、集成的、非易失的、且随时间变化的数据集合，用于支持管理决策。

数据源是数据仓库系统的基础，是整个系统的数据源泉。
数据的存储和管理是整个数据仓库系统的核心。
OLAP（联机分析）服务器对分析需要的数据进行有效集成，按多维模型组织，以便进行多角度、多层次的分析，并发现趋势。
前端工具各种报表工具、查询工具、数据分析工具、数据挖掘工具……

商业智能

BI系统主要包括数据预处理、建立数据仓库、数据分析和数据展现四个主要阶段。

反规范化技术

规范化设计后，数据库设计者希望牺牲部分规范化来提高性能。

益处：降低连接操作的需求、降低外码和索引的数目，还可能减少表的数目，能够提高查询效率。

问题：数据的重复存储、可能出现数据的完整性问题，为了保障数据的一致性，增加了数据维护的复杂性，会降低修改速度。

具体方法：

增加冗余列：在多个表中保留相同的列，增加数据冗余以减少或避免查询时的连接操作。
增加派生列：在表中增加可以由本表或其他表中数据计算生成的列，减少查询时的连接操作并避免计算或使用集合函数。
重新组表：如果许多用户需要查看两个表连接出来的结果数据，则把这两个表重新组成一个表来减少连接而提高性能。
水平分割表
垂直分割表

大数据

特点：大量化、多样化、价值密度低、快速化。

【真题】

【日志文件、数据文件】

【相对稳定性】

SQL语言

SQL语言中语法关键字，不区分大小写：

创建表 create table;
指定主键 primary key();
指定外键 foreign key();
修改表 alter table;
删除表 drop table;
索引 index;
视图 view;

数据库查询 select …… from …… where……；
分组查询 group by，分组时要注意 select 后的列名要适应分组，为分组查询附加条件 having select sno,avg(score) from student group by having (avg(score)>60)
更名运算 as: select sno as “学号” from t1
字符串匹配 like、% 匹配多个字符串，_ 匹配任意一个字符串： select * from t1 where sname like ‘a_’
数据库插入 insert into……values(): insert into t1 values(‘a’,66)
数据库删除 delete……from……where: delete t1 where sno=4
数据库修改 update……set……where: update t1 set sname=’aa’ where sno=3
排序 order by，默认为升序，降序要加关键字 DESC： select * from t1 oder by sno desc

DISTINCT：过滤重复的选项，只保留一条记录
UNION：出现在两个SQL语句之间，将两个SQL语句的查询结果取或运算，即值存在于第一句或第二句都会被选出。
INTERSECT：对两个SQL语句的查询结果做与运算，即值同时存在于两个语句才被选出
MIN、AVG、MAX：分组查询时的聚合函数

【真题】

【A、A、D】

【C、A、D、B】

数据库练习题

计算机网络

网络功能和分类

计算机网络的功能：数据通信、资源共享、负载均衡、高可靠性

计算机网络按 分布范围和拓扑结构 划分，如下图所示：

OSI七层模型

局域网和广域网协议

以太网规范 IEEE 802.3 是重要的有线局域网协议，包括：

1	2	3	4
IEEE 802.3	标准以太网	10Mb/s	细同轴电缆
IEEE 802.3u	快速以太网	100Mb/s	双绞线
IEEE 802.3z	千兆以太网	1000Mb/s	光纤或双绞线
IEEE 802.3ae	万兆以太网	10Gb/s	光纤

无线局域网 WLAN 技术标准：IEEE 802.11

广域网协议（不需要）

TCP/IP 协议

网络层协议：

IP：网络层最重要的核心协议，在源地址和目标地址之间传输数据报，无连接、不可靠。
ICMP：因特网控制报文协议，用于在 IP主机、路由器之间传递控制消息。控制消息是指网络通不通、主机是否可达、路由是否可用等网络本身的消息。
ARP 和 RARP ：地址解析协议，ARP是将 IP地址转换为物理地址，RARP 是将物理地址转换为 IP地址。
IGMP：网络组管理协议，允许因特网的计算机参加多播，是计算机用作向相邻多目路由器报告多目组成员的协议，支持组播。

传输层协议：

TCP：整个 TCP/IP协议族中最重要的协议之一，在 IP协议提供的不可靠数据基础上，采用了重发技术，为应用程序提供了一个可靠的、面向连接的、全双工的数据传输服务。一般用于传输数据量比较少，且对可靠性要求高的场合。
UDP：是一种不可靠、无连接的协议，有助于提高传输速率，一般用于传输数据量大，对可靠性要求不高，但要求速度快的场合。

TCP：三次握手，四次挥手。

应用层协议：基于 TCP的FTP、HTTP等都是可靠传输。基于 UDP的DHCP、DNS等都是不可靠传输。

TCP ：可靠的文件传输协议，用于因特网的控制文件的双向传输。
HTTP：超文本传输协议，用于从WWW服务器传输超文本到本地浏览器的传输协议。使用SSL加密的网页协议为HTTPS
SMTP 和 POP3：简单邮件传输协议，是一组用于源地址到目标地址传送邮件的规则，邮件报文采用 ASCII格式表示。
Telnet：远程连接协议，是因特网远程登陆服务的标准协议和主要方式。
TFTP：不可靠的、开销不大的小文本传输协议。
SNMP：简单网络管理协议，由一组网络管理的标准协议，包含一个应用层协议、数据库模型和一组资源对象。该协议能够支持网络管理系统。
DHCP：动态主机配置协议，基于UDP，基于C/S模型，为主机动态分配IP地址。三种方式：固定分配、动态分配、自动分配。
DNS：域名解析协议，通过域名解析出IP地址

协议端口号对照表：

【真题】

在 OSI 参考模型中能实现路由选择、拥塞控制与互连功能的层是（）

A.传输层
B.应用层
C.网络层
D.物理层

【C】

在 TCP/IP体系结构中，将IP地址转换为MAC地址的协议是（）

A.RARP
B.ARP
C.ICMP
D.TCP

【B】

下列网络互连设备中，属于物理层的是（）

A.交换机
B.中继器
C.路由器
D.网桥

【B】

传输介质

无屏蔽双绞线UTP

屏蔽双绞线STP

网线如下两种安装标准：都是八根不同颜色的网线，按照不同的顺序排序，插入水晶头中，区分在第1、2、3、6根网线的位置不同。

光纤：由纤芯和包层组成，传输的光信号在纤芯中传输，然而从PC端出来的信号都是电信号，要经过光纤传输的话，就必须将电信号转换为光信号。

通信方式和交换方式

通信方向：数据通信是指发送方发送数据到接收方，这个传输过程可用分类如下：

单工：只能由设备A发给设备B，即数据流只能单向流动
半双工：设备A和设备B可以互相通信，但是同一时刻数据流只能单向流动。
全双工：设备A、B可以在任意时刻通信。

同步方式：

异步传输：发送方每发送一个字符，需要约定一个起始位和停止位插入到字符的起始和结尾位，这样当接收方接收到该字符时能够识别，但是这样会造成资源浪费，传输效率降低。
同步传输：以数据块为单位进行传输，当发送方要发送数据时，先发送一个同步帧，接收方收到后做好接收准备，开始接收数据块，结束后又会有结束帧确认，这样一次传输一个数据块，效率高。
串行传输：只有一根数据线，数据只能1bit挨个排队传送，适合低俗设备、远距离的传送，一般用于广域网中。
并行传输：有多根数据线，可以同时传输多个bit数据，适合高速设备的传送，常用于计算机内部各硬件模块之间。

交换方式：

电路交换：通信一方进行呼叫，另一方接收后，在二者之间会建立一个专用电路。特点为面向连接、实时性高、链路利用率低，一般用于语音视频通信。
报文交换：以报文为单位，存储转发模式，接收到数据后先存储，进行差错校验，没有错误则转发，有错误则丢弃，因此会有延时，但可靠性高，是面向无连接的。
分组交换：以分组为单位，也是存储转发模式，因为分组的长度比报文小，所以时延小于报文交换，可分为三种方式：
- 数据报：是现在主流的交换方式，各个分组携带地址信息，自由选择不同的路由路径传送到接收方，接收方接收到分组后再根据地址信息重新组装成原数据，是面向无连接的，但是不可靠的。
- 虚电路：发送方发送一个分组，接收方收到后二者之间建立了一个虚拟的通信线路，二者之间的分组数据交互都通过这条线路传送，在空闲的时候这条线路也可以传输其他数据，是面向连接的，可靠的。
- 信元交换：异步传输模式ATM采用的交换方式，本质是按照虚电路方式转发，只不过信元是固定长度的分组，共53B，其中5B为头部，48B为数据域，也是面向连接的、可靠的。

【真题】

以下关于光纤的说法中，错误的是（）

A.单模光纤的纤芯直径更细
B.单模光纤才有 LED 作为光源
C.多模光纤比单模光纤的传输距离近
D.多模光纤中广播在光导纤维以多种模式传播

【B】

【D】

IP地址表示

因为每个十进制数都是由8个二进制数转换而来，因此每个十进制数的取值范围为 0-255

分类IP地址：IP地址分为四段，每段八位，共32位二进制数组成。

在逻辑上，这32位IP地址分为网络号和主机号，依据网络号位数不同，可以将IP地址分为以下几类：

特殊IP地址

其他特殊地址如下表所示：

子网划分

网络号和子网号都为1，主机号都为0，这样的地址为子网掩码。

需要注意的是，子网可以全为0和全为1，主机号不能全为0或全为1，因此，主机数需要-2，而子网数不用。

还可以聚合网络为超网，就是划分子网的逆过程，将网络号取出几位作为主机号，此时，这个网络内的主机数量就变多了，成为了一个更大的网络。

【真题】

把网络117.15.32.0/23划分为117.15.32.0/27，得到的子网是（）个，每个子网中可使用的主机地址是（）个

A.4
B.8
C.16
D.32

A.30
B.31
C.32
D.34

【C、A】

【C、D】

IPv6

主要是为了解决 IPv4地址数不够用的情况而提出的设计方案，IPv6具有以下特性：

IPv6地址长度为128位，地址空间增大了2^96^倍；
灵活的IP报文头部格式，使用一系列固定格式的扩展头部取代了IPv4中可变长度的选项字段。IPv6中选项部分的出现方法也有所变化，使路由器可以简单掠过选项而不做任何处理，加快了报文的处理速度。

IPv4和IPv6过渡期间，主要采用三种基本技术：

（2）隧道技术：这种机制用来在IPv4网络之上建立一条能够传输IPv6数据报的隧道。

（3）翻译技术，利用一台专门的翻译设备，在纯IPv4和纯IPv6之间转换。

网络规划与设计

三层模型将网络划分为核心层、汇聚层和接入层，每一层都有特定的作用

核心层 只负责高速的数据转发

汇聚层将网络业务连接到接入层，并实施与安全、流量、负载和路由相关的策略

建筑物综合布线系统PDS：

【真题】

【B】
核心层：数据高速转发

【B】

廉价磁盘冗余阵列

RAID即磁盘冗余阵列技术，将数据分散存储在不同磁盘中，可并行读取，可冗余存储，提高磁盘访问速度，保障数据安全性。

RAID0将数据分散的存储在不同磁盘中，磁盘利用率100%，访问速度最快，但是没提供冗余和错误修复技术。

RAID1在成对的独立磁盘上产生互为备份的数据，增加存储可靠性，可以纠错，但磁盘利用率只有50%

RAID2 海明码校验

RAID3 奇偶校验

RAID5 在所有磁盘上交叉的存储数据及奇偶校验信息（所有校验信息存储总量为一个磁盘容量，但分布式存储在不同的磁盘上），读/写指针可同时操作。

网络存储技术

存在问题：在传递距离、连接数量、传输速率等方面都受到限制。容量难以扩展升级；数据处理和传输能力降低；服务器异常会波及存储器。

2.网络附加存储（NAS）：通过网络接口与网络直接相连，由用户通过网络访问，有独立的存储系统。

NAS的性能特点是进行小文件级的共享存取，支持即插即用，可以很经济的解决存储容量不足的问题，但难以获得满意的性能。

其他考点：

VLAN工作在OSI参考模型的第二层和第三层，一个VLAN就是一个广播域，VLAN之间的通信是通过第三层路由器来完成的。

优点：网络设备的移动、添加和修改的管理开销减少；可用控制广播活动；可提高网络的安全性。

冲突域和广播域

【真题】

一个虚拟局域网是一个（）

A.广播域
B.冲突域
C.组播域
D.物理上隔离的区域

以下关于URL的说法，错误的是（）

【A】
URL：协议：// 域名：端口号 / 路径

了解翻斗花园小秘密的更多信息

订阅后即可通过电子邮件收到最新文章。

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

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