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

一、单项选择题

1． 下列命中组合情况中, 一次访存过程中不可能发生的是（ ）。

A.TLB 未命中, Cache 未命中, Page 未命中 B.TLB 未命中, Cache 命中, Page 命中 C.TLB 命中, Cache 未命中, Page 命中 D.TLB 命中, Cache 命中, Page 未命中 【答案】D

【解析】TLB(快表) 和慢表(页表, Page) 构成二级存储系统, 若TLB 命中, 则Page 必命中。因此不可能发生的是D 选项。

2． 假定编译器规定int 和short 类型长度分别为32位和16位, 执行下列C 语言语句:

;

A.00007FFAH B.0000FFFAH C.FFFF7FFAH D.FFFFFFFAH 【答案】B 。

X 和y 均为无符号数, 其中X 为16位, y 为32位, 将16位无符号数转化成32位无符【解析】

号数, 前面要补零。因为X=65530=FFFAH, 所以y=0000FFFAH。

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

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

B. 当系统处于安全状态时, 系统中一定无死锁进程 C. 当系统处于不安全状态时, 系统中一定会出现死锁进程 D. 银行家算法破坏了死锁必要条件中的“请求和保持”条件 【答案】B

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

4． 有两个并发执行的进程P1和P2, 共享初值为1的变量x 。P1对x 加1, P2对x 减1。加1和减1操作的指令序列分别如下所示。

第 2 页，共 51 页

:得到y 的机器数为（ ）。

两个操作完成后, 2的值（ ）。 A. 可能为-1或3 B. 只能为1 C. 可能为0、1或2 D. 可能为-1、0、1或2 【答案】C

【解析】这是在数据库中常有的操作。为保证数据的正确, 避免产生错误, 系统必须保证数据的同步。而保证数据的同步一般采取加锁的方法, 让进程P1和P2互斥访问共享变量X 。当然用信号量和P 、V 操作也是可以保证互斥操作, 达到数据同步的。

本例中, 由于没有采取保证数据同步的相应措施, 则最后结果就会出现差错。例如, 当正常情况下, 进程P1和P2先后对x 操作, 可以看到x 值的变化为初始则x 值的变化为初始

的过程, 若P2, P1先后操作,

, 这是正确的。若考虑一种并发的情况, 进程P1和P2先后执行了取数

load 的操作, 它们得到的x 值均为1, 运算后, P1和P2的x 值分别为2和0, 此时要看哪个进程后执行存数store 的操作了, 哪个进程后操作, 结果就是那个进程的x 值, 所以可能的结果为0或2, 加上前面正确的x 值1, 则可能的结果就有3种了。

5． 求整数阶乘的算法如下, 其时间复杂度是（ ）。

A. B.0(n) C.

2

D.O(n)

【答案】B 。

【解析】设fact(n)的运行时间函数是T(n)。

该函数中语句①的运行时间是0(1), 语句②的运行时间是算的时间。

因此, 当则,

时

,

;

。

第 3 页，共 51 页

, 其中O(1)为乘法运

当11>1时,

即fact(n)的时间复杂度为O(n)。

通过上表可以看出, 显然转换过程中同时保存在栈中的操作符的最大个数是5。

6． 若X 是二叉中序线索树中一个有左孩子的结点，且X 不为根，则X 的前驱为（ ）。

A.X 的双亲

B.X 的右子树中最左的结点 C.X 的左子树中最右的结点 D.X 的左子树中最右的叶结点 【答案】C

【解析】中序线索，只有把其左子树最右结点遍历完后，才会遍历自己，所以X 的前驱为X

第 4 页，共 51 页