9月28日复习

1.线索二叉树：主要是为了加快查找结点的前驱和后继
结点没有左子树，就指向前驱，没有右子树就指向后继

2.后序线索二叉树找后继？

• 如果是根结点，那么无后继
• 如果结点是双亲的左孩子，并且有右孩子，那么后继是双亲右右子树按后续遍历的第一个结点
• 如果结点是双亲的右孩子，或者是双亲的左孩子，没有右孩子，那么后继就是双亲。

3.负数的反码：将负数的原码写出来，保持符号位不变，其余各位取反

4.n位补码表示的小数范围：-1 ~ 1-2^-n+1
也就是1.00000……000 ~ 0.111111……11111

5.异步通信方式：使用握手协议协调数据的收发
非互锁：发送方将数据放到数据总线上，发出DATA RDY信号，接收方发出ACK，发送方受到接收方的ACK信号就撤销DATA RDY信号
全互锁：与上面不同的在于，在发送方接收到ACK后会复位数据就绪（DATA RDY）信号，接收方在发送方复位数据就绪后才复位ACK，发送四个握手信息，不利于提高传输速度

6.DMA与通道控制方式的异同
同：

• 都能在不需要cpu干预下完成外设和主存间的数据交换

异：

• DMA没有自己独立的指令系统，是通过专门设计的硬件控制器逻辑来实现对数据传输的控制，而通道控制下io设备有自己的指令系统，是一个有特殊功能的处理器；
• DMA只能控制一台或者几台同类设备，通道可以多台和不同类设备

7.在单处理机总线中，相对于cpu而言，地址线一般位单向信号线，数据线位双向信号线

8.多重中断：中断嵌套，cpu在响应低级别的中断请求时，如果有高级别的中断请求，cpu就转去执行高级别的中断请求

9.在半互锁的异步通信方式下，请求信号的撤销取决于回答信号的来到，而回答信号的撤销由从设备自己决定

10.系统总线是连接计算机内部cpu，主存，io接口等各种功能模块的公共连接线。

11.磁盘的平均访问时间：平均寻道时间+平均等待时间+数据传输时间

• 平均寻道时间：磁头转到目标磁道的时间，平均寻道时间由存储器的性能决定
• 平均等待时间，又称旋转延迟时间，读写扇区转到磁头下方的所用时间，一般选用磁盘旋转一周所用时间的一半作为平均等待时间
• 数据传输时间：读写一个扇区的时间，与磁盘的转速相关。

12.单总线结构中，访存和访问外设主要是通过地址来划分的