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

一、单项选择题

1． 某时刻进程的资源使用情况如下表所示

此时的安全序列是（ ）。

A.P1, P2, P3, P4

B.P1, P3, P2, P4

C.P1, P4, P3, P2

D. 不存在

【答案】D

【解析】典型的死锁避免算法, 银行家算法的应用。银行家算法是操作系统中的一个重点知识单元, 考生对此应该非常熟悉, 本题并无难点。分析一下下表, 可以看到, 经过P1, P4的运行以后, 可用资源是2, 2, 1, 而P2, P3所需资源分别是1, 3, 2和1, 3, 1。所以剩余资源已经不够P2或P3的

分配, 亦即找不到能够安全运行的序列, 因此此时是处于不安全状态, 所以不存在这样的安全序列。

2． 数据序列(8，9，10，4，5，6，20，1，2) 只能是下列排序算法中的（ ）的两趟排序后的结果。

A. 选择排序

B. 起泡排序

C. 插入排序

D. 堆排序

【答案】C

【解析】选择排序、起泡排序和堆排序两趟排序后，在序列的某一端应该有序列的两个最大值或者最小值。

3． n 个顶点的无向图的邻接表最多有（ ）个表结点。

A.n 2

B.n(n－1)

C.n(n+1) D.

【答案】B

【解析】当n 个顶点构成的无向图是无向完全图时，则每一个结点都会和其余的n －1个结点连接，从而会产生n(n－1) 个表结点。

4． 线性表是具有n 个（ ）的有限序列(n＞0) 。

A. 表元素

B. 字符

C. 数据元素

D. 数据项

E. 信息项

【答案】C

【解析】一个线性表是n 个数据元素的有限序列。至于每个数据元素的具体含义，在不同的情况下各不相同。

5． 某设备中断请求的相应和处理时间为100ns , 每400ns 发出一次中断请求, 中断相应所容许的最长延迟时间为50ns , 则在该设备持续工作过程中CPU 用于该设备的

分比至少是（ ） A. B. C. D.

【答案】B

【解析】每400ns 响应一次中断并且用100ns 进行处理, 所以该设备的时间占用CPU 时间百分比为100/400=25%, 中断响应容许的延迟时间对此没有影响, 属于干扰条件。

6． 假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入哈希表中，至少要进行多少次探测？（ ）

A.k －1次

B.k 次

C.k+1次 D. 次

时间占整个CPU 时间百

【答案】D

【解析】至少探测次数。

7． 直接插入排序在最好情况下的时间复杂度为（ ）。 A.

B.O(n) C. 2D.O(n)

【答案】B

【解析】当序列是按照直接插入排序的顺序有序时，此时进行插入时，每次都只需要和末尾的一个元素进行比较，此时的时间复杂度最好，为O(n)。

8． 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A ，并已知A 的左孩子的平衡因子为0, 右孩子的平衡因子为1，则应作（ ）型调整以使其平衡

A.LL

B.LR

C.RL

D.RR

【答案】C

【解析】A 的平衡因子此时为-1，要使插入结点不平衡，必须插在右孩子的左子树上，A 平衡因子变成了-2. 则需要进行两次旋转(先右旋后左旋) 。

9． 下列措施中, 能加快虚实地址转换的是1增大快表(TLB)2让页表常驻内存3增大交换区（ ）

A. 仅1

B. 仅2

C. 仅1, 2

D. 仅2, 3

【答案】C

【解析】加大快表能增加快表的命中率, 即减少了访问内存的次数; 让页表常驻内存能够使cpu 不用访问内存找页表, 从也加快了虚实地址转换。而增大交换区只是对内存的一种扩充作用, 对虚实地址转换并无影响

10．有n(n＞0) 个分支结点的满二叉树的深度是（ ）。

A.n 2﹣l

B.log 2(n＋1) ＋1

C.log 2(n＋1)

D.log 2(n—1)

【答案】C