第一部分计算机组成原理
一、浮点数
浮点表示法就是小数点在数中的位置是浮动的。在以数值计算为主要任务的计算机中，由于定点表示法所能表示的数的范围太窄，不能满足计算问题的需要，因此就要采用浮点表示法。在同样字长的情况下，浮点表示法能表示的数的范围扩大了。计算机中的浮点表示法包括两个部分：一部分是阶码（表示指数，记作E）；另一部分是尾数（表示有效数字，记作M）。设任意一个数N 可以表示为N=M×其中，2 为基数；E 为阶码；M 为尾数。浮点数在机器中的表示方法如下：
阶符E数符M
阶码部分 尾数部分
由尾数部分隐含的小数点位置可知，尾数总是小于1 的数字，它给出该浮点数的
有效数字。尾数部分的符号位确定该浮点数的正负。阶码给出的总是整数，它确定小数点浮动的位数。浮点数表示法对尾数有如下规定：
0.5 ≤M＜l即要求尾数中第一位数不为零，这样的浮点数称为规格化数。
在浮点数表示和运算中，当一个数的阶码大于机器所能表示的最大阶码时，产生“上溢”，如图2-1 所示。上溢时机器一般不再继续运算而转入“溢出”处理。当一个数的阶码小于机器所能表示的最小阶码时，产生“下溢”，此时溢出的数绝对值很小，通常将尾数各位置为0，按机器零来处理，此时计算机可以继续运行。
三、指令寻址
（一）立即寻址在取指令时，操作码和操作数被同时取出，不必再次访问存储器，从而提高了指令的执行速度，如图1-2 所示。立即寻址的特点是操作数本身设在指令字内，即形式地址A 不是操作数的地址，而是操作数本身，也称立即数。由于操作数是指令的一部分，故立即数的大小将受到指令长度的限制。
（二）直接寻址
指令中地址码字段给出的地址A 就是操作数的有效地址：EA=A，如图1-3 所示。直接寻址的缺点在于A 的位数限制了操作数的寻址范围，且必须修改A 的值，才能修改操作数的地址。
（三）间接寻址
指令中给出的地址A 不是操作数的地址，而是存放操作数地址的地址：EA=（A），如图1-4 所示。间接寻址要比直接寻址灵活得多，它的主要优点为：一是扩大了寻址范围，可用指令的短地址访问大的主存空间，二是可将主存单元作为程序的地址指针，用以指示操作数在主存中的位置。当操作数的地址需要改变时，不必修改指令，只需修改存放有效地址的那个主存单元（间接地址单元）的内容就可以了。
除去一级间接寻址外，还有多级间接寻址。多级间接寻址为取得操作数需要多次访问主存，即使在找到操作数有效地址后，还需再访问一次主存才可得到真正的操作数。若指令字长和存储字长均为16 位，A 为8 位，则直接寻址范围为28，一级间接寻址的寻址范围可达216。当多级间接寻址时，可用存储字的首位来标志间接寻址是否结束。如图3-3（b）中，当存储字首位为“l”时，标明还需继续访存寻址；当存储字首位为“0”时，标明该存储字即为EA。由此可见，存储字首位不能作为EA 的组成部分，因此，它的寻址范围为215。
（四）寄存器寻址
指令中地址码部分给出某一通用寄存器的编号，所指定的寄存器中存放着操作数，如图1-5 所示。它有两个明显的优点：一是从寄存器存取数据比主存快得多；二是由于寄存器的数量较少，其地址码字段比主存单元地址字段短得多。
（五）寄存器间接寻址
指令中的地址码给出某一通用寄存器的编号，被指定的寄存器中存放操作数的有效地址，而操作数则存放在主存单元中，如图1-6 所示。这种寻址方式的指令较短，并且在取指后只需一次访存便可得到操作数。
（六）隐含寻址
隐含寻址是指指令字中不明显地给出操作数的地址，其操作数的地址隐含在操作码或某个寄存器中。如一地址指令格式，只给出一个操作数的地址，另一个操作数隐含在累加器ACC 中，故累加器ACC 对一地址指令格式来说是隐含地址，如图1-7 所示。
（七）堆栈寻址
在堆栈寻址的指令字中没有形式地址码字段，它是一种零地址指令。堆栈寻址要求计算机中设有堆栈。堆栈既可用寄存器组来实现，也可利用主存的一部分空间作堆栈，前者称为硬堆栈，后者称为软堆栈。
第二部分计算机操作系统
一、线程和进程的比较
（一）调度
传统的操作系统中，作为拥有资源的基本单位和独立调度、分派的基本单位都是
进程。引入线程的操作系统中，则把线程作为调度和分派的基本单位，而进程作为资源拥有的基本单位，线程基本上不拥有资源。
（二）并发
在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间也可并发执行。
（三）资源
进程是系统中拥有资源的一个基本单位。一般线程自己不拥有系统资源（也有一点必不可少的资源），但它可以访问其隶属进程的资源，即一个进程的代码段、数据段及所拥有的系统资源。
（四）系统开销
在创建或撤消进程时，操作系统所付出的开销明显大于线程创建或撤消时的开销。
二、死锁
（一）死锁产生的原因产生死锁的原因可归结为如下两点：
1.竞争资源
当系统中供多个进程共享的资源如打印机、公用队列等，其数目不足以满足诸进
程的需要时，会引起诸进程对资源的竞争而产生死锁。
2.进程间推进顺序非法
进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。（二）死锁产生的必要条件
死锁的发生必须具备下列四个必要条件：
1.互斥条件
指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求该资源，则请求者只能等待，直至占有该资源的进程用毕释放。
2.请求和保持条件
指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
3.不剥夺条件指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
4.环路等待条件
指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，…，Pn}中的P0 正在等待一个P1 占用的资源；P1 正在等待P2 占用的资源，……，Pn 正在等待已被P0 占用的资源。
（三）死锁的处理
为保证系统中各进程的正常运行，应事先采取必要的措施，来预防发生死锁。系统已经出现死锁后，则应及时检测到死锁的发生，并采取适当措施来解除死锁。目前，处理死锁的方法可归结为以下四种：
1.预防死锁
这是一种较简单和直观的事先预防的方法。该方法是通过设置某些限制条件，破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。
2.避免死锁
该方法同样是属于事先预防的策略，但它并不须事先采取各种限制措施去破坏产生死锁的四个必要条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。
3.检测死锁
这种方法并不须事先采取任何限制性措施，也不必检查系统是否已经进入不安全区，而是允许系统在运行过程中发生死锁。但可通过系统所设置的检测机制，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源；然后，采取适当措施，从系统中将已发生的死锁清除掉。
4.解除死锁
这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。常用的实施方法是撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。
三、调度算法
（一）先来先服务调度算法先来先服务（First Come First Served，FCFS）调度算法总是把当前处于就绪队列之首的那个进程调度到运行状态。
优缺点：
有利于长作业（进程）而不利于短作业（进程）；
有利于CPU 繁忙型作业（进程）而不利于I/O 繁忙型作业（进程）。
（二）短作业/进程优先调度算法
短进程优先调度算法（Shortest Job/Process First，SJ/PF）中，每次选择的是已进入系统的、要求服务时间最短的进程。是对FCFS 算法的改进，其目标是减少平均周转时间。
优点：
比FCFS 改善平均周转时间和平均带权周转时间，缩短作业的等待时间；提高系统的吞吐量；
缺点：
对长作业非常不利，可能长时间得不到执行；未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业（进程）的执行时间，从而影响调度性能。
（三）高优先权优先调度算法
优先权调度算法可分为：非抢占式优先权算法、抢占式优先权调度算法。优先权可分为：
静态优先权：在创建进程时确定，且在进程的整个运行期间保持不变。
动态优先权：是指在创建进程时所赋予的优先权，根据就绪进程等待CPU 的时间长短来决定。
动态优先权的变化规律可描述为：
优先权=（等待时间+要求服务时间）/要求服务时间
= 响应时间/要求服务时间
= 响应比
这种算法即为高响应比优先调度算法（Highest Response-ratio Next，HRN），它既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务。因此实现了一种较好的折衷。
由于每次调度前要计算响应比，系统开销也要相应增加。
四、基本的分页存储管理
在分页存储管理方式中，如果不具备页面对换功能，则称为基本的分页存储管理方式，它不具有支持实现虚拟存储器的功能，它要求把每个作业全部装入内存后方能运行。
（一）页面与页表
基本的分页存储管理方式中，系统将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页。相应地，将内存空间分成若干个与页面同样大小的块，称为物理块或页框。内存的分配以块为单位，并允许将一个进程的若干页分别装入到多个不相邻的物理块中。
为了地址映射的方便，页面的大小通常设置成2 的幂。如果页面的大小为2k 字节，逻辑地址的长度为n 位，则分页系统的地址结构如图2-1 所示，可将线性的逻辑地址分成两部分：右边的k 位为页内位移量（即页内地址）W，左边的n-k 位为页号P。
（二）地址变换机构
页式存储管理系统中，逻辑地址到物理地址的转换是在进程执行的过程中，由硬件地址变换机构借助于页表自动进行的。
【例题】在一个页式存储管理系统中，页表内容如下所示：
若页的大小为1K，则地址转换机构将逻辑地址100 转换成的物理地址是多少。
【解析】页的大小为4K，逻辑地址为100，易知所在页号为0，页内偏移量为100，由页表可知页号0 所对应的块号为2，则其对应的物理地址为4K×2+100=8292。
第三部分计算机网络
一、网络协议
（一）协议的定义简称为协议，是为进行网络中的数据交换而建立的规则、标准或约定。
（二）协议的三要素
语法：数据与控制信息的结构或格式。
语义：需要发出何种控制信息，完成何种动作以及做出何种响应。
同步：事件实现顺序的详细说明。
二、OSI 参考模型
（一）分层的好处
各层之间是独立的、灵活性好、结构上可分割开、易于实现和维护、能促进标准化工作。
（二）分层的原则
若层数太少，就会使每一层的协议太复杂。
层数太多又会在描述和综合各层功能的系统工程任务时遇到较多的困难。
（三）OSI 层次
1977 年，开放系统互联参考模型OSI/RM（Open System Interconnection，OSI）。
表3-1
表3-1
三、IPV4 地址的特点
（一）唯一性在Internet 上的计算机所拥有的IP 地址是不同的，即网络中不能有两台主机同时使用同一个IP 地址。
（二）固定长度
IPV4 地址是由 32 位二进制表示的，在 IPV4 地址中理论可以放232个 IP 地址，当然去掉一部分特殊的IP 地址后，使得IP 地址的总数量会减少。
（三）点分十进制
由于32 位二进制不容易记忆和书写，所以在书写IP 地址的时候，需要用到点分十进制书写，即把32 位二进制平均分成4 个字节，然后把二进制数转化为十进制书写，中间用点号隔开。转化后十进制数值不大于255。
（四）可变性
当计算机所在的网络发生变化后，其IP 地址也要跟着发生变化。注意这里的变化指的是网络发生变化不是计算机的位置变化。
注意：逻辑（IP）地址可变，但是物理（MAC）地址不可变。
（五）组成
IP 地址由两部分组成：{<网络号>，<主机号>}
网络号：表示计算机所在的网络，路由器在进行路由选择的时候使用的。
主机号：表示网络中的某台主机，是计算机在某个网络中的唯一标识。
网络号相同的计算机可以不经过路由器的转发就可以直接通信。
四、子网划分
（一）划分子网划分的好处节约IP 地址，避免浪费，使得大网络划分成小的网络，这样可以分配给公司使用，能很好的解决IP 地址紧缺的问题。
限定广播的传播，可以把计算机网络中的广播限制在一个小的广播域。
保证网络的安全，有助于覆盖大型地理区域。
（二）子网数量计算
形成子网的数量计算：从主机位借位当网络位来使用。
（三）子网划分例题
C 类地址例子：网络地址202.168.10.0；子网掩码255.255.255.192 或26。第一步：子网数= 22 ? 4（原来 C 类默认是 24 位子网掩码，现在有 26 位子网掩
码，借了2 位）第二步：主机数= 26 =64（计算机网络可用主机的数量是 64-2=62 个）
五、网络设备
（一）中继器REPEATER
中继器是对信号进行再生和还原的网络设备。物理层设备。
缺点：增加了延时。
（二）集线器
集线器的英文称为“Hub”，扩大网络的传输距离，多端口中继器。
工作在计算机物理层设备；多口网络设备；信号的放大再生功能；半双工通信；广播式数据传输；本身是一个冲突域；形成共享式以太网。物理层设备。
（三）网桥
网桥是用于连接两个相同类型的局域网。数据链路层设备。
（四）交换机
工作在计算机数据链路层设备；多口网络设备；信号的放大再生功能；全双工通信；根据帧里数据的MAC 地址和缓存中的路由表转发数据；隔绝广播风暴，形成交换式以太网。数据链路层设备。
（五）网卡
网卡是工作在链路层的网络组件，是局域网中连接计算机和传输介质的接口。
（六）路由器
路由器（Router），是连接因特网中各局域网、广域网的设备，它会根据信道的情况自动选择和设定路由，以最佳路径，按前后顺序发送信号。
工作在网络层的设备；用于连接局域网和广域网、广域网与广域网的设备；连接不同类型和不同协议的网络；路径选择功能（知道从原点倒目的节点的完整路径）；数据过滤功能（类是于防火墙）；网络管理功能（子网划分技术）；隔绝IP 地址引起的广播风暴。
第四部分计算机数据结构
一、栈
（一）栈的定义
1.栈的定义
栈是一种只能在一端进行插入或删除操作的线性表。栈中的数据元素是线性关系。
栈顶：允许进行插入或删除操作的一端。
栈底：不允许进行插入和删除操作，固定不变的一端。
入栈：栈的插入操作。
出栈：栈的删除操作。
2.栈的特点
先进后出（first in last out，简称FILO）、后进先出（last in first out，简称LIFO）。
例：若已知栈的输入序列为1、2、3，则输出序列应该有多少种？
【答案】输出序列共有5 种，分别是123、132、213、231、321。
3.栈的存储结构
（1）顺序栈
使用顺序存储结构存储栈
（2）链式栈
使用链式存储结构存储栈
（二）栈的顺序存储结构和实现
1.初始化栈
初始化一个栈S，只需将栈顶指针置为-1 即可，代码如下：
void InitStack(Sqstack &S)
{
S.top = -1;
}
2.入栈
int Push(SqStack &S,int x) //变量x 内存储的是入栈的元素
{
if(S.top == MAXSIZE-1) //进栈时必须判断是否栈满,若栈满，则不能进栈
return 0;
++(S.top); //移动指针
S.data[st.top] = x; //将元素入栈
return 1;
}
3.出栈
int Pop(SqStack &S,int &x) //取出的元素存入x
{
if(S.top==-1) //如果栈空，不能出栈
return 0;
x=S.data[S.top]; //取出元素
--(S.top); //移动栈顶指针
return 1; //出栈成功
}
二、队列
（一）队列的定义
1.队列的定义
队列是一种运算受限制的线性表，元素的添加在表的一端进行，而元素的删除在表的另一端进行。
队头：允许删除元素的一端
队尾：允许添加元素的一端
入队：向队列添加元素
出队：从队列中删除元素
2.队列的特点
先进先出（FIFO）（先入队的元素先出队，后入队的元素后出队）。
3.存储结构
顺序队：使用顺序存储结构的队列
链队：使用链式存储结构的队列
（二）队列的表示和实现
1.链队列（队列的链式表示）
（1）链队列的结构
链队列一般需要两个指针，分别是队首指针和队尾指针，其中队首指针front 指向链表的表头，队尾指针rear 指向链表的表尾，如下图所示：
（2）循环队列空状态和满状态的判别
①设一个标志用来标记队列是空还是满
比如，定义一个变量count 用来记录队列中元素个数，当count==0 时队列为空，当count= MAXSIZE（MAXSIZE 为已定义的常量，用来表示队满时元素的个数）时队列为满。
②常用的判满、判空条件
队满条件为：(s.rear+1) mod maxsize==s.front
队空条件为：s.rear==s.front
三、时间复杂度总结
第五部分数据库技术
一、关系模型
（一）关系
—个关系就是一张二维表，每个关系有一个关系名。Access 中，一个关系存储为一个表，具有一个表名。
（二）域
属性的取值范围称为该属性的域。
（三）属性
关系中的每一列即为一个属性，每一个属性起一个名称即属性名。
（四）候选码
也称为候选关键字，是指表中能够唯一标识一个元祖的属性或属性组合。
（五）主码
也称主关键字、主键。若有一个表中有多个候选码，可以指定其中一个为主码。
（六）外码
也称外部关键字、外键。如果表中的某个属性不是表的主码，而是另一个表的主
码，则该属性称作外码。
（七）元组
关系中的一行数据总称为一个元组。一个元组即为一个实体的所有属性值的总称。一个关系中不允许有两个完全相同的元组。
（八）关系模式
1.描述
关系名（属性1，属性2，……，属性n）
2.实例
学生（学号，姓名，年龄，性别，系名，年级）
二、关系的完整性
（一）实体完整性
实体完整性规定，任一候选码的任何属性都不能为空，而不仅仅是候选码整体不能为空。
（二）参照完整性
参照完整性是对关系之间引用数据的一种限制，要求关系中不允许引用不存在的实体。
（三）用户定义的完整性
除上述两类完整性约束外，任何数据库系统都会有一些自己特殊的约束要求，例如年龄不能大于60，夫妻的性别不能相同等。
三、范式
（一）第一范式（1NF）
在关系R 中，要求每个属性值都是不可再分的，则该关系满足第一范式，记作：R∈1NF。
（二）第二范式（2NF）
如果某关系R 满足第一范式，而且它的所有非关键字属性都完全依赖于整个主关键字（不存在部分依赖），则该关系满足第二范式，记作R∈2NF。
（三）第三范式（3NF）
如果某关系模式R 满足第二范式，而且它的任何一个非主属性都不传递依赖于任何关键字，则满足第三范式，记作R∈3NF。
（四）BCNF
关系模式R∈1NF，若F 的任一函数依赖X→Y（Y ? X）中包含了R 的一个码，则称R∈BCNF。
（五）第四范式（4NF）
如果关系模式R∈1NF，对于R 的每个非平凡的多值依赖X→→Y（Y ? X），X 都含有码，则称R 是第四范式，即R∈4NF。第六部分信息新技术
一、大数据
（一）大数据的概念
最早提出“大数据”时代的是全球知名咨询公司麦肯锡，麦肯锡全球研究所给出的定义是：大数据（Big Data）指的是大小超出常规的数据库工具获取、存储、管理和分析能力的数据集。
大数据技术的战略意义不在于掌握庞大的数据信息，而在于对这些含有意义的数据进行专业化处理。
（二）大数据的特征
大数据带给我们的三个颠覆性观念转变：是全部数据，而不是随机采样；是大体方向，而不是精确制导；是相关关系，而不是因果关系。大数据有5 个特征，分别是：
1.数据量大（Volume）
收集和分析的数据量非常大，从TB 级别，跃升到PB 级别。
2.数据类型繁多（Variety）
大数据来自多种数据源，数据种类和格式日渐丰富，如网络日志、视频、图片、地理位置信息等，多类型的数据对数据的处理能力提出了更高的要求。
3.数据价值密度低（Value）
随着物联网的广泛应用，信息感知无处不在，信息海量，但价值密度较低，如何通过强大的机器算法更迅速地完成数据的价值“提纯”，是大数据时代亟待解决的难题。
4.数据处理速度快（Velocity）
这是大数据区别于传统数据挖掘的显著特征，需要对数据进行实时的分析。
5.数据真实性（Veracity）
大数据中的内容与真实世界中的发生的事件息息相关，研究大数据就是从庞大的网络数据中提取出能够解释和预测现实事件的过程。
（三）大数据的结构类型
大数据包括结构化、半结构化和非结构化数据，非结构化数据越来越成为数据的主要部分。据IDC（互联网内容提供商）的调查报告显示，企业中80%的数据都是非结构化数据。
1.结构化数据
包括预定义的数据类型、格式和结构的数据。如：关系数据库中的数据。
2.半结构化数据
具有可识别的模式并可以解析的文本数据文件。如：XML 数据格式文件。
3.非结构化数据
没有固定的数据结构，通常用于保存不同类型的文件。如：图片、音频和视频。
二、云计算
（一）云计算的特点
超大规模、虚拟化、高可靠性、通用性、高可扩展性、按需服务、极其廉价、潜在的危险性。
（二）云计算的服务形式
1.基础设施即服务（IaaS）
将计算和存储以授权服务形式提供，核心是将某一或某几个数据中心的计算/存储资源虚拟化，以灵活划分资源。
2.平台即服务（PaaS）
把开发环境作为服务来提供，使开发者不用关心后台大规模服务器的工作细节，给开发者提供一个透明安全、功能强大的运行环境和开发环境。
3.软件即服务（SaaS）
它是一种通过Internet 提供软件的模式，用户无需购买软件，而是向提供商租用基于Web 的软件，来管理企业经营活动。
三、物联网
物联网（Internet of Things）将人类生存的物理世界网络化、信息化，将分离的物理世界和信息空间有效互连，代表了未来网络的发展趋势与方向，是现代信息技术发展到一定阶段后出现的一种聚合性应用与技术提升。
物联网的最终目的，是为人类提供更好的智能服务，满足人们的各种需求，让人们享受美好的生活。
物联网包括物联网感知层、物联网网络层、物联网应用层，
（1）感知层
数据采集与感知主要用于采集物理世界中发生的物理事件和数据，包括各类物理量、标识、音频、视频数据。物联网的数据采集涉及传感器、RFID、多媒体信息采集、二维码和实时定位等技术。
（2）网络层
实现更加广泛的互联功能，能够把感知到的信息无障碍、高可靠性、高安全性地进行传送，需要传感器网络与移动通信技术、互联网技术相融合。经过十余年的快速发展，移动通信、互联网等技术已比较成熟，基本能够满足物联网数据传输的需要。
（3）应用层
应用层主要包含应用支撑平台子层和应用服务子层。其中应用支撑平台子层用于支撑跨行业、跨应用、跨系统之间的信息协同、共享、互通的功能。应用服务子层包括智能交通、智能医疗、智能家居、智能物流、智能电力等行业应用。
（4）公共技术
公共技术不属于物联网技术的某个特定层面，而是与物联网技术架构的三层都有关系，它包括标识与解析、安全技术、网络管理和服务质量（QoS）管理。
