当前位置：问答库＞考研试题

一、综合题

1． 证明若二叉排序树中的一个结点存在两个孩子，则它的中序后继结点没有左孩子，则它的中序前驱结点没有右孩子。

【答案】证明:根据中序遍历的定义，该结点的中序后继是其右子树上按中序遍历的第一个结点:叶结点或仅有右子树的结点；而其中序前驱是其左子树上按中序遍历的最后个结点:叶结点或仅有左子树的结点。命题得证。

2． 假设计算机系统采用CSCAN(循环扫描）磁盘调度策略. 使用2KB 的内存空间记录16384个磁盘块的空闲状态.

(1)请说明在上述条件下如何进行磁盘空闲状态的管理.

(2)设某单面磁盘旋转速度为每分钟6000转，每个磁道有100个扇区，相邻磁道间的平均移动时间为lms. 若在某时刻，磁头位于100号磁道处，并沿着磁道号增大的方向移动(如下图所示) ，磁道号请求队列为50，90，30，120，对请求队列中的每个磁道需要读取1个随机分布的扇区，则读完这4个扇区总共需要多少时间? 要求给出计算过程

.

图

(3)如果将磁盘替换为随机访问的Flash 半导体存储器(如U 盘、SSD 等) ，是否有比CSCAN 更高效的磁盘调度策略? 若有，给出磁盘调度策略的名称并说明理由；若无，说明理由.

【答案】(1)采用位示图法管理磁盘空闲块，每一位表示一个磁盘块的状态，共需要16384/32＝512个字节即2KB 的空间，正好可放在系统提供的内存中.

(2)采用CSCAN 调度算法，访问磁道的顺序和移动的磁道数如下表所示:

表

故移动的磁道数为20＋90＋20＋40＝170，所花的时间为170ms. 由于转速为6000r/min，则平均旋转延迟为5ms ，总的旋转延迟时间为20ms ，读取一个扇区的平均时间为

区所花的时间为. 综上所述，读取磁道上所有扇区所花的总时间为故读取4个扇

(3)采用先来先服务(FCFS)调度策略更高效，因为Flash 半导体存储器的物理结构不需要考虑寻道时间和旋转延迟，可直接按I/O请求的先后顺序服务.

3． 已知一棵二叉树的后序遍历序列为EICBGAHDF , 同时知道该二叉树的中序遍历序列为CEIFGBADH , 试画出该二叉树。

【答案】该二叉树如图所示:

图

4． 三维数组

7]的存储首地址。

【答案】数组占的存储字节数＝10*9*7*4＝2520；A[5，0，7]的存储地址＝100＋[4*9*7＋2*7＋5]*4＝1184

5． 某计算机的CPU 主频为500MHz ，CPI 为5(即执行每条指令平均需要5个时钟周期) 。假定某外设的数据传输率为0.5MB/s，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请回答下列问题，要求给出计算过程。

(1)在中断方式下，CPU 用于该外设I/O的时间占整个CPU 时间的百分比是多少？

(2)当该外设的数据传输率达到5MB/S时，改用DMA 方式传送数据。假定每次DMA 传送块大小为5000B ，且DMA 预处理和后处理的总开销为500个时钟周期，则CPU 用于该外设I/0时

的每个元素的长度为4个字节，试问该数组要占多少个字节0，的存储空间? 如果数组元素以行优先的顺序存储，设第一个元素的首地址是100，试求元素A[5，

间占整个CPU 时间的百分比是多少？(假设DMA 与CPU 之间没有访存冲突)

【答案】(1)已知主频为500MHz , 则时钟周期＝1÷500MHz ＝2ns , 因为CPI ＝5, 所以每条指令平均5×2＝10ns 。又已知每中断一次传送32位(4个字节) ，数据传输率为

CPU 用于

该外设I/0共需20条指令(中断服务程序包括18条指令＋其他开销折合2条指令) ，花费时间＝20×l0＝200ns 。

CPU 用于该外设I/O的时间占整个CPU

时间的百分比

预处理和后处理的总开销时间 (2)改用DMA 方式传送数据，数据传输率为5MB/S，传送5000B 的时间＝5000B ÷5MB/s＝lms 。CPU 用于该外设I/O时间占整个CPU 时间的百分比

＝预处理和后处理的总开销时间+传送数据的时间

6． 有A 、B 两人通过邮箱进行辩论, 每人都从自己的信箱中取得对方的问题。将答案和向对方提出的新问题组成一个邮件放入对方的邮箱中, 设A 的信箱最多放M 个邮件, B 的信箱最多放N 个邮件。初始时A 的信箱有x 个邮件(0

A 、B 两人操作过程:

当信箱不为空时, 辩论者才能从信箱中取邮件, 否则等待。

当信箱不满时, 辩论者才能将新邮件放入信箱, 否则等待。

请添加必要的信号量和P 、V(或wait signed)操作以实现上述过程的同步, 要求写出完整过程, 并说明信号量的含义和初值。

【答案】首先定义两个互斥信号量:mutexA 和mutexB , 初始时为1, 分别用来实现对A 的邮箱和B 的邮箱的互斥使用; 然后针对A 的邮箱再定义两个信号量emptyA 和fullA , 初值分别为M-x 和x , 分别表示信箱中仍能存放信的数量和已经存放的信的数量, 同理设置emptyB 和fullB , 初值为N-y 和y 。

所以传送时间