一、数据结构

二叉树的确定

前序遍历和中序遍历、中序遍历和后序遍历可以唯一确定一棵二叉树。但前序遍历和后序遍历可能会有多颗二叉树与之对应。
前序序列和中序序列的关系：以前序序列为入栈次序，以后序序列为出栈次序。对于n个不同的元素进栈，出栈序列的个数为 C 2 nn/ ( n + 1 )C^n_{2n}/(n+1)C2nn​/(n+1)。
所以对于一个有n个节点二叉树的前序遍历序列，可以产生 C 2nn/(n+1)C^n_{2n}/(n+1) C2nn​/(n+1)棵不同的二叉树（1个前序序列对应 C 2nn/(n+1)C^n_{2n}/(n+1) C2nn​/(n+1)个中序序列）

堆排序—-堆的删除

删除某个关键字重新建堆，将最后的叶子结点放到被删除位置，后再对该结点进行“下落”
【例题】 已知小根堆为8，15，10，21，34，16，12，删除关键字8之后需重新建堆，在此过程中，关键字之间的比较次数是 3
【分析】 删除过程如下图所示，下落过程需要分别与左右子树比较再下落。

二、计算机组成原理

浮点数的加减法运算（二）—-继2009

规格化

左规一次相当于乘2，右规一次相当于除2；右规只进行一次。
左规、右规时不考虑符号，为逻辑移位。
IEEE 754规格化尾数的形式为±1.xx···x（1是隐含的，尾数存储从.后）
1）右规：当结果为±1x.xx···x时。进行右规，尾数右移1位，阶码+1。最高位1在小数点前作为隐藏位，最后一位移出时考虑舍入。
2）左规：当结果为±0.0···01xxx时，进行若干次左规，直至尾数格式为±1.xx···x。每次左规尾数左移1位，阶码-1。
注：右规和尾数舍入可能引起上溢（阶码+1），左规可能引起下溢（阶码-1）。

溢出判断—-指数溢出判断

当一个正指数超过了最大允许值（127或1023）时发生指数上溢。
当一个负指数超过了最小允许值（-128或-1024）时发生指数下溢。

三、操作系统

异常和中断


内中断（内部异常）是来自CPU和内存产生的中断。响应于指令执行过程中。在特殊情况（除数为0和自行中断）都会自动跳过中断指令，不会返回到发生异常的指令继续执行。
外部中断响应于指令周期末尾的中断周期。

死锁避免

死锁避免通常采用银行家算法进行检测，提出了安全状态这一概念。
在计算机处于安全状态时，计算机不可能发生死锁。但计算机若处于不安全状态，但也不一定会发生死锁。在进程请求资源时进行“预分配”，判断分配后是否处于安全状态。若找得到安全系列则仍处于安全状态，分配资源；反之拒绝资源分配。
★死锁避免只是会驳回资源的申请，并不限制用户资源申请的顺序（死锁预防中破坏循环等待条件才限制用户申请资源的顺序）★

磁盘缓冲区


磁盘缓冲区位于内存，主要用于缓和内存与磁盘读写速度的差异，能在磁盘缓冲区查到的数据无需启动磁盘，减少了磁盘I/O的次数。

四、计算机网络

常用的数字数据编码（基带传输）

非归零编码（NRZ）

高电平表示1，低电平表示0。无法传递时钟信号，难以同步。若需要传输高速同步数据需要带有时钟线（没有检错，难以同步）

曼彻斯特编码

先高后低表示1，先低后高表示0。把一个码元分成了两个相等的时间间隔。传一个数据等于传两个码元→ 2 ∗ 比特率 = 波特率2*比特率=波特率2∗比特率=波特率

差分曼彻斯特编码

常用于局域网传输，可以实现自同步，抗干扰性较好。前半码元与上一码元的后半码原电平相同为1，不同为0（从第二条虚线处开始，跳变右为0，不变右为1，第一段从高电平开始为1，低电平开始为0）

计算机网络的设备

物理层设备—-中继器和集线器（不隔离冲突域）

中继器

放大数字信号（信号再生），中继器两端的网络部分是网段，不能连接两个速率不同的网段。

集线器（多口中继器）

共享设备，半双工状态工作，所有集线器的端口属于同一个冲突域。集线器中若同时多台计算机同时使用网络将会平分带宽。

链路层设备—-网桥和交换机（隔离冲突域，不隔离广播域）

网桥（考纲已删除）

根据MAC帧的目的地址对帧进行转发和过滤。使得不同冲突域间可以同时发生通信，增大吞吐量。

局域网交换机（多端口网桥）

将网络分成小的冲突域，为每个工作站提供更更高的带宽（不同冲突域的设备不共享带宽）。

网络层设备—-路由器（隔离广播域）

路由器用于连接不同网络并完成路由转发，是一种存储转发设备。
若源主机与目标主机位于同一个网络，直接交付无需经过路由器。
当源主机与目标主机位于不同网络时，路由器按照转发表(路由表) 指出路由将数据报转发给下一个路由器。称为间接交付。

动态主机配置协议（DHCP）—-应用层协议，基于UDP

DHCP协议用于动态分配IP地址，提供即插即用的联网机制。

DHCP服务器和DHCP客户端的交换过程—-全程通过广播交互

1）DHCP客户机广播“DHCP发现”消息，源地址为0.0.0.0，目的地址为255.255.255.255。
2）DHCP服务器收到“DHCP发现”消息，广播“DHCP提供”消息，包含提供给客户机的IP地址，源地址为DHCP服务器地址，目的地址为255.255.255.255。
3）DHCP客户机收到“DHCP提供”消息，若接受该IP地址，则广播DHCP请求，源地址为0.0.0.0，目的地址为255.255.255.255。
4）DHCP服务器广播“DHCP确认”消息，将IP地址分配给DHCP客户机，源地址为DHCP服务器地址，目的地址为255.255.255.255。（至此正式分配IP地址）