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

一、单项选择题

1． 将森林F 转换为对应的二叉树T , F 中叶结点的个数等于（ ）

A.T 中叶结点的个数

B.T 中度为1的结点个数

C.T 中左孩子指针为空的结点个数

D.T 中右孩子指针为空的结点个数

【答案】C

【解析】森林转化为对应的二叉树是‘孩子-兄弟’存储的, 即左孩子指针指向当前节点的孩子节点, 右孩子指针指向当前节点的兄弟节点, 所以在T 中左孩子指针为空则代表它在森林中并没有孩子即为叶结点。所以选C

2． 某计算机有16个通用寄存器, 采用32位定长指令字操作码字段(含寻址方式位) 为8位, Store 指令的源操作数和目的操作数分别采用寄存器直接寻址和基址寻址方式, 若基址寄存器可使用任一通用寄存器, 且偏移量用补码表示, 则Store 指令中偏移量的取值范围是（ ） A. B. C. D.

【答案】A

【解析】寄存器个数

指令编址方式如下所示:

16位补码取值范围为 , 所以偏移量取值范围为

3． —个多道批处理系统中仅有P1和P2两个作业, P2比P1晚5ms 到达。它们的计算和作顺序如下:P1:计算60ms

, , 计算20ms ; P2:计算120ms

,

不考虑调度和切换时间, 则完成两个作业需要的时间最少是（ ）。

A.240ms

B.260ms

C.340ms

D.360ms

【答案】B 。

【解析】考查处理系统的性能计算, 由于P2比P1晚5ms 到达, P1先占用CPU , 根据P1和P2

偏移量有32-8-4-4=16位 操, 计算40ms 若

的执行过程, 作业运行的甘特图如下所示, 故答案为B 。

图 甘特图

4． 某同步总线采用数据线和地址线复用方式。其中地址数据线有8根, 总线时钟频率为66MHZ , 每个时钟同期传送两次数据。(上升沿和下降沿各传送一次数据) 该总线的最大数据传输率是(总线带宽) :（ ）

A.132MB/S

B.264MB/S

C.528MB/S

D.1056MB/S

【答案】C

【解析】总线带宽=总线工作频率X(总线宽度/8), 由于地址线与数据线复用, 所以在两次数据

, 所以选C 传输过程中总线上数据一共传输了8次, 那么总线带宽为

5． 采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中, 正确的是（ ）。

A. 递归次数与初始数据的排列次序无关

B. 每次划分后, 先处理较长的分区可以减少递归次数

C. 每次划分后, 先处理较短的分区可以减少递归次数

D. 递归次数与每次划分后得到的分区的处理顺序无关

【答案】D

【解析】快速排序是递归的, 递归过程可用一棵二叉树给出, 递归调用层次数与二叉树的深度一致。例如:待排序列{48, 62, 35, 77, 55, 14, 35, 98) , 采用快速排序方法, 其对应递归调用过程的二叉树如下图所示。

图

在最坏情况下, 若初始序列按关键码有序或基本有序时, 快速排序反而蜕化为冒泡排序。即其对应递归调用过程的二叉树是一棵单支树。因此快速排序的递归次数与初始数据的排列次序有关。但快速排序的递归次数与每次划分后得到的分区处理顺序无关, 即先处理较长的分区或先处理较

短的分区都不影响递归次数。

6． 下列排序算法中，其中（ ）是稳定的。

A. 堆排序，起泡排序

B. 快速排序，堆排序

C. 直接选择排序，归并排序

D. 归并排序，起泡排序

【答案】D

7． 下列关于银行家算法的叙述中, 正确的是（ ）

A. 银行家算法可以预防死锁

B. 当系统处于安全状态时, 系统中一定无死锁进程

C. 当系统处于不安全状态时, 系统中一定会出现死锁进程

D. 银行家算法破坏了死锁必要条件中的“请求和保持”条件

【答案】B

【解析】银行家算法是避免死锁的方法。利用银行家算法, 系统处于安全状态时没有死锁进程, 故答案选B 。

8． 某计算机处理器主频为50MHz , 采用定时查询方式控制设备A 的

则CPU 用于设备A 的

A. B. C. D.

【答案】C , 查询程序运行一次所用的时钟周期数至少为500。在设备A 工作期间, 为保证数据不丢失, 每秒需对其查询至少200次, 的时间占整个CPU 时间的百分比至少是（ ）。 【解析】对于设备A , 每秒中查询至少200次, 每次查询至少500个时钟周期, 总的时钟周期数为100000, 又因为处理器主频为50MHz 。所以CPU 用于设备A 的的时间占整个CPU 时间的百分比至少为100000/50。

9． 下列选项中, 满足短任务优先且不会发生饥饿现象的调度算法是（ ）。

A. 先来先服务

B. 高响应比优先

C. 时间片轮转

D. 非抢占式短任务优先

【答案】B

【解析】分析该题目可以看到, 本题所提到的问题是涉及短任务调度也就是属于作业调度, 因此首先排除时间片轮转算法; 因为作业调度算法中没有时间片轮转的算法。其次, 因为问题提到短