一、数据结构

折半查找与二叉搜索树

【例题】 下列二叉树中，可能成为折半查找判定树的是 A
【分析】 ★折半查找判定树本质上是二叉搜索树，故满足中序遍历元素有序的性质★
将所有结点按照中序遍历标号，结果如下图所示。

A：共有10个元素，存于一维数组范围为a[1]~a[10]。
①$\lceil (1+10)/2\rceil =6$可知，采用向上取整方式进行折半查找。
②对根节点6：
左子树：$\lceil (1+5)/2\rceil =3$，满足。
右子树：$\lceil (7+10)/2\rceil =9$，满足。
③对非叶结点3：
左子树：$\lceil (1+2)/2\rceil =2$，满足。
无右子树。
④对非叶结点9：
左子树：$\lceil (7+8)/2\rceil =8$，满足。
右子树：叶子节点，满足。
⑤对非叶结点2、5、8：
左子树：叶子节点，满足。
无右子树。
综上，A满足折半查找判定树的性质。
B：①$(1+11)/2=6$，根结点满足，无法判定向上取整或向下取整。
对非叶结点3的左子树：$\lceil (1+2)/2\rceil =2$，采用向上取整方式。
对非叶结点9的左子树：$\lfloor (7+8)/2\rfloor =8$，采用向下取整方式。
判定方式不同，B不满足。
C：①$(1+9)/2=5$，根结点满足，无法判定向上取整或向下取整。
对根节点5的左子树：$\lfloor (1+4)/2\rfloor =2$，采用向下取整方式。
对根节点5的右子树：$\lceil (6+9)/2\rceil =8$，采用向上取整方式。
判定方式不同，C不满足。
D：①$\lfloor (1+10)/2\rfloor =5$，可知，采用向下取整方式进行折半查找。
对根节点5的左子树：$\lceil (1+4)/2\rceil =3$，采用向上取整方式。
判定方式不同，D不满足。

排序

堆排序和希尔排序利用了顺序存储方式随机访问的特性优化算法，而链式存储不支持这种性质，所以堆排序和希尔排序用链式方式存储会增大时间复杂度。
快速排序基于交换，枢轴最终位置的选择以及交换过程也与随机访问无关，故用快速排序使用链式方式存储不会增大时间复杂度。

二、计算机组成原理

存储器的组成和设计—-继2010

多模块存储器—-多体并行存储器

高位交叉编址（顺序方式）

地址格式如下

该编址方式只是单纯扩容，各模块不能并行访问。通常在对存储器芯片的字扩展（扩容）中使用该种编制方式。

低位交叉编址（交叉方式）

地址格式如下

该编址方式可实现流水线存取，高效、高灵活，各模块间可以并行访问。
设模块数为m，r为启动下一个模块的延迟（总线传送周期），T为模块存取一个字的存取周期。
连续存取m个字所需的时间 t1= T + ( m − 1 ) rt_1=T+(m-1)rt1​=T+(m−1)r

三、操作系统

多道程序系统

通过组织作业使CPU总有一个作业可执行，提高了CPU利用率、系统吞吐量和I/O设备利用率。

磁盘管理

磁盘初始化

物理格式化（低级格式化）：分扇区使得磁盘控制器可以读和写。

分区—-柱面为单位

第一步：将磁盘分为由一个或多个柱面组成的分区。
☆分区操作在逻辑格式化之前完成☆
第二步：进行逻辑格式化（创建文件系统）
①建立文件系统的根目录
②对保存空闲磁盘块信息的数据结构进行初始化

I/O控制方式—-DMA控制方式

DMA控制方式由DMA控制器代替CPU控制中断过程。
CPU仅做出数据处理。故DMA控制器发出中断请求时已完成了数据的传输。
处理顺序：初始化DMA控制器并启动磁盘→从磁盘传输一块数据到内存缓冲区→DMA控制器发出中断请求→执行“DMA结束”中断服务程序。

四、计算机网络

路由协议

路由信息协议（RIP）—-应用层协议（使用UDP）

RIP协议是内部网关协议(IGP) 中最先得到广泛应用的协议。维护从它自身到其他每个目的网络的距离记录。
①选择最小距离路由。
②距离为16时表示网络不可达。
③动态维护路由表（每30s广播一次RIP路由更新信息）。
④RIP不支持子网掩码的RIP广播，RIP中每个网络的子网掩码必须相同

开放最短路径优先协议（OSPF）—-网络层协议（使用IP数据报）

OSPF协议是使用分布式链路状态路由算法的典型代表。也是内部网关协议(IGP) 的一种。
①使用洪范法向自治系统中所有路由器发送信息
②仅当链路状态发生变化时更新
③可根据不同类型业务计算出不同路由
④有多条相同代价的路径时，可以将通讯两分配给这几条路径。（多路径间的负载平衡）
⑤分组具有鉴别功能，仅在可信赖的路由器之间交换链路信息。
⑥每个链路状态都带有一个32位的序号，序号越大状态越新。

五种分组类型

①问候分组（HELLO）：发现、维持与邻站的可达性、
②数据库描述分组（DD）：向邻站给出自己的所有链路状态项目的摘要信息。
③链路状态请求分组（LSR）：请求对方发送链路状态项目的详细信息。
④链路状态更新分组（LSU）：用洪范法对全网更新链路状态。
⑤链路状态确认分组（LSAck）：对链路更新分组进行确认。

边界网关协议（BGP）—-应用层协议（使用TCP）

BGP协议是不同自治系统的路由器之间交换路由信息的协议，是外部网关协议。只要求找到可达且比较好的路由。
首次运行时，BGP邻站交换整个BGP路由表，后续只在发生变化时更新有变化的部分。
每个自治系统至少有一个BGP发言人（边界路由器），由BGP发言人负责与其他自治系统通信。

BGP-4使用的四种报文

①打开报文（Open）：与相邻的另一个BGP发言人建立关系。
②更新报文（Update）：发送某一路由的信息。
③保活报文（Keepalive）：确认打开报文并周期性证实邻站关系。
④通知报文（Notification）：发送检测到的差错。

三种路由协议的比较