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

一、选择题

1．

对

（ ）。

A. 该树一定是一棵完全二叉树

B. 树中一定没有度为1的结点

C. 树中两个权值最小的结点一定是兄弟结点

D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值

【答案】A

【解析】哈夫曼树为带权路径长度最小的二叉树，但不一定是完全二叉树，选项A 错误；哈夫曼树中没有度为1的结点，选项B 正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树，C 正确；哈夫曼树中任一非叶结点P 的权值为其左右子树根结点权值之和，其权值不小于其左右子树根结点的权值，在与结点P 的左右子树根结点处于同一层的结点中，若存在权值大于结点P 权值的结点Q ，那么结点Q 与其兄弟结点中权值较小的一个应该与结点P 作为左右子树构造新的二叉树，由此可知，哈夫曼树中任一非叶结 点的权值一定不小于下一层任一结点的权值。

2． 对同一待排序列分别进行折半插入排序和直接插入排序， 两者之间可能的不同之处是（ ）。

A. 排序的总趟数

B. 元素的移动次数

C. 使用辅助空间的数量

D. 元素之间的比较次数

【答案】D 。

【解析】折半插入排序所需附加存储空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，

而记录的移动次数不变。折半插入排序的时间复杂度仍为

所以两者之间的不同只可能是元素之间的比较次数。

3． 操作系统的

A. 用户级

B. 用户级

C. 用户级

D. 用户级子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口。其合理软件、设备无关软件、设备驱动程序、中断处理程序 软件、设备无关软件、中断处理程序、设备驱动程序 软件、设备驱动程序、设备无关软件、中断处理程序 软件、中断处理程序、设备无关软件、设备驱动程序

个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是的层次组织排列顺序是（ ）。

【解析】对于一次设备的调用，操作系统为用户准备了系统调用的接口，当用户使用设备时，首先在用户程序中发起一次系统调用，操作系统的设备无关层软件接到该调用请求后调用处理程序进行处理，根据调用格式和形参，再转到相应的设备驱动程序去处理；大部分设备在运行时是需要时间的，所以设备驱动程序会以中断方式驱动设备，即设置好控制寄存器参数和中断向量等参数后阻塞自己；当设备准备好或所需数据到达后设备硬件发出中断，设备驱动程序唤醒，将数据按上述调用顺序逆向回传到用户程序中，或继续驱动设备执行下一条指令。 因此，软件从上到下分为四个层次：用户层、与设备无关的软件层、设备驱动程序以及中断处理程序。

4． 下列选项中，能引起外部中断的事件是（ ）。

A. 键盘输入

B. 除数为0

C. 浮点运算下溢

D. 访存缺页

【答案】A

【解析】所谓外部中断是指由外部事件引起的中断，在这4个选项中，只有键盘输入是真正由外部事件引起的中断。

5． 用户程序发出磁盘I/O请求后，系统的正确处理流程是（ ）。

A. 用户程序—系统调用处理程序—中断处理程序—设备驱动程序

B. 用户程序—系统调用处理程序—设备驱动程序—中断处理程序

C. 用户程序—设备驱动程序—系统调用处理程序—中断处理程序

D. 用户程序—设备驱动程序—中断处理程序—系统调用处理程序

【答案】B

【解析】对于一次设备的调用，操作系统为用户准备了系统调用的接口，当用户使用设备时，首先在用户程 序中发起一次系统调用，操作系统的内核接到该调用请求后调用处理程序进行处理，根据调用格式和形参，再转到相应的设备驱动程序去处理；大部分设备在运行时是需要时间的，所以设备驱动程序会以中断方式驱动设备， 即设置好控制寄存器参数和中断向量等参数后阻塞自己；当设备准备好或所需数据到达后设备硬件发出中断，设备驱动程序唤醒，将数据按上述调用顺序逆向回传到用户程序中，或继续驱动设备执行下一条指令。因此，正确的顺序应该是用户到系统调用到驱动到中断处理。中断处理处于最底层。

6． 若磁盘转速为7200转/分，平均寻道时间为8ms , 每个磁道包含1000个扇区，则访问一个扇区的平均存取时间大约是（ ）。 A. B. C. D.

【解析】磁盘的平均寻址时间包括平均寻道时间和平均等待时间。平均寻道时间为8ms , 平均等待时间与磁盘转速有关，

为

因此总的时间为：磁盘的存取一个扇区的时间

为

7． 假设某系统总线在一个总线周期中并行传输4字节信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz , 则总线带宽是（ ）。

A.lOMB/s

B.20MB/S

C.40MB/S

D.80MB/S

【答案】B

【解析】因为一个总线周期占用2个时钟周期，完成一个32位数据的传送。总线时钟频率为10MHz , 时钟周期为0.1押，总线周期占用2个时钟周期，为0.2两。一个总线周期中并行传输4

=20MB/s。 字节信息, 则总线带宽是4B ÷

8． 下列给出的指令系统特点中，有利于实现指令流水线的是（ ）。

I. 指令格式规整且长度一致

II. 指令和数据按边界对齐存放

III. 只有Load / Store指令才能对操作数进行存储访问

A. 仅

B. 仅

C. 仅 D.

【答案】D

【解析】特点I 和III 都是RISC 机的特征，而特点II 则有利于指令和数据的存放，所以以上三个特点都有利于实现指令流水线。

9． 对任意一棵树，设它有n 个结点，这n 个结点的度数之和为（ ）。

A.n B. C. D.

【答案】C

【解析】每个结点（除根节点外）都是一个分支，即所有结点的度数之和等于分支个数等于总的结点数减一，即n-1。

10．将一棵树t 转换为孩子兄弟链表表示的二叉树h ，则t 的后序遍历是h 的（ ）。

A. 前序遍历

B. 中序遍历