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

一、单项选择题

1． 假设磁头当前位于第105道，正在向磁道序号增加的方向移动. 现有一个磁道访问请求，序列为35，45，12，68，110，180，170，195，采用SCAN 调度(电梯调度) 算法得到的磁道访问序列是（ ）.

A.110， 170， 180， 195， 68， 45， 35， 12

B.110， 68， 45， 35， 12， 170， 180， 195

C.110， 170， 180， 195， 12， 35， 45， 68

D.12， 31， 45， 68， 110， 170， 180， 195

【答案】A

【解析】SCAN 算法类似电梯工作原理，即朝一个固定方向前进，经过的磁道有访问请求则马上服务，直至到达一端顶点，再掉头往回移动以服务经过的磁道，并这样在两端之间往返. 因此，当磁头从105道向序号增加的方向移动时，便会服务所有大于105的磁道号(从小到大的顺序) ；往回返时又会按照从大到小的顺序进行服务. 注意与循环扫描算法的区别，所以SCAN 算法的访问序列是：110， 170， 180， 195， 68， 45， 35， 12

2． 下列排序算法中，占用辅助空间最多的是（ ）。

A. 归并排序

B. 快速排序

C. 希尔排序

D. 堆排序

【答案】A

【解析】归并排序的辅助空间为O(n)，快速排序所占用的辅助空间为，堆排序所占用的辅助空间为O(1)。

3． 若对如下的二叉树进行中序线索化, 则结点x 的左、右线索指向的结点分别是（ ）

A.e , c

B.e , a

C.d , c

D.b , a

【答案】D

【解析】此二叉树的中序遍历序列为:debxac , 由于节点x 左右孩子都为空, 所有进行中序线索化时, 它的左右孩子指针分别指向它的中序遍历序列的直接前驱结点b 和直接后继结点a , 所以选D

4． 计算机开后, 操作系统最终被加载到（ ）

A.BIOS

B.ROM

C.EPROM

D.RAM

【答案】D

【解析】系统开机后, 操作系统的程序会被自动加载到内存中的系统区, 这段区城是RAM , 故答案选D 。

5． 对于下列关键字序列, 不可能构成某二叉排序树中一条查找路径的序列是（ ）。

A.95, 22, 91, 24, 94, 71

B.92, 20, 91, 34, 88, 35

C.21, 89, 77, 29, 36, 38

D.12, 25, 71, 68, 33, 34

【答案】A

【解析】各选项对应的查找过程如下图所示, 从中看到选项B 、C 、D 对应的查找树都是二叉排序树, 只有选项A 对应的查找树不是一棵二叉排序树, 因为在以91为根的左子树中出现了比91大的结点94。

6． 就平均性能而言，目前最好的内排序方法是（ ）排序法。

A. 起泡

B. 希尔插入

C. 交换

D. 快速

【答案】D

【解析】快速排序的平均时间复杂度是nlogn 所需要的辅助存储为

间复杂度也是

注意仅仅表示的是一个量级，比如和的量级都为，虽然堆排序的时。之所以说，所需要的辅助存储为O(1)，看似堆排序比快速排序的性能好，但是需要快排最好，是在综合考虑的情况下。

7． 某文件占10个磁盘块, 现要把该文件磁盘块逐个读入主存缓冲区, 并送用户区进行分析。假设一个缓冲区与一个磁盘块大小相同,

把一个磁盘块读人缓冲区的时间为

送到用户区的时间是, CPU

对一块数据进行分析的时间为

下, 读人并分析完该文件的时间分别是（ ）。 A. B. C. D.

【答案】B

【解析】这是一个简单的缓冲区的问题。由于缓冲区的访问是互斥的, 所以对单一缓冲区, 从磁盘写入和读出到用户区的操作必须串行执行, 也就是要保证互斥操作。而CPU 对数据的分析与从用户区读数据也是需要互斥操作, 但是CPU 分析与从磁盘写入缓冲区的操作可以并行。从本题看, 由于分析所用的时间小于从磁盘写入缓冲区的时间, 因此, CPU 会空闲。

单缓冲区的总时间=(磁盘写入缓冲区时间+缓冲区读出时间)

间=(100+50)X10+50=1550ns。

当采用双缓冲区时, 每块缓冲区的操作也必须满足互斥操作, 但是, 对两块缓冲区的操作却可

, 将缓冲区的数据传

。在单缓冲区和双缓冲区结构处理最后一块数据的时