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

一、单项选择题

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

A. 前序遍历

B. 中序遍历

C. 后序遍历

【答案】B

【解析】树的后序遍历恰好对应于二叉树的中序遍历。

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

A.TLB 未命中, Cache 未命中, Page 未命中

B.TLB 未命中, Cache 命中, Page 命中

C.TLB 命中, Cache 未命中, Page 命中

D.TLB 命中, Cache 命中, Page 未命中

【答案】D

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

3． 下列选项中, 不能构成折半查找中关键字比较序列的是（ ）。

A.500, 200, 450, 180

B.500, 450, 200, 180

C.180, 500, 200, 450

D.180, 200, 500, 450

【答案】A

【解析】折半查找的过程是:先确定待查找记录所在的范围, 然后逐步缩小范围直到找到或找不到该记录为止。折半查找的关键字序列满足:对每一个关键字, 其后面的所有关键字序列或者都小于等于该关键字或者都大于等于该关键字。A 项错误, 第三次比较的关键字为450, 说明待查关键字位于200〜450间, 所以第四次比较时不会遇到关键字180。

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

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

,

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

A.240ms

第 2 页，共 55 页 操, 计算40ms 若

B.260ms

C.340ms

D.360ms

【答案】B 。

【解析】考查处理系统的性能计算, 由于P2比P1晚5ms 到达, P1先占用CPU , 根据P1和P2的执行过程, 作业运行的甘特图如下所示, 故答案为B 。

图 甘特图

5． 已知广义表LS ＝((a，b ，c) ，(d，e ，f)) ， 用head 和tail 数取出LS 中原子e 的运算是（ ）。

A.head(tail(LS))

B.tail(head(LS))

C.head(tail(head(tail(LS)))

D.head(tail(tail(head(LS))))

【答案】C

【解析】head 操作就是得到广义表中第一个的原子。tail 操作就是得到除第一个原子外剩下元素构成的表。tail(LS)得到((d，e ，f)) ，head(tail(LS))得到(d，e ，f)tail(head(tail(LS)))得到(e，f) ，head(tail(head(tail(LS))) 得到e 。

6． 下列程常段的时间复杂度是（ ）

A.O()

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

【答案】C

【解析】外部循环的退出条件是k>n, 而对于k , 每次循环都执行

内部循环的退出条件是j>n, 对于j , 每次循环都执行

) , 即选C 。 段的时间复杂度为O(

7． 下列选项中, 不可能是快速排序第2趟排序结果的是（ ）

A.2, 3, 5, 4, 6, 7, 9

B.2, 7, 5, 6, 4, 3, 9

C.3, 2, 5, 4, 7, 6, 9

第 3 页，共 55 页 , 所以循环次数为; , 所以每次循环次数为n 次。所以此程序

D.4, 23, 5, 7, 6, 9

【答案】C

【解析】对于快速排序, 每一趟都会使一个元素位于有序时的位置, 而有序序列为2, 3, 4, 5, 6, 7, 9, 与C 进行对比, 只有9位于它有序的时候的位置, 显然不是第二趟快速排序的结果

8． 在虚拟存储管理中, 地址变换机构将逻辑地址变换为物理地址, 形成该逻辑地址的阶段是（ ）。

A. 编辑

B. 编译

C. 链接

D. 装载

【答案】B

【解析】程序的编辑阶段一般都是程序员能够识别的高级语言或低级语言的文本, 不涉及到任何与计算机运行相关的事; 编译是由编译程序将用户源代码编译成若干个目标模块, 源地址编译成目标程序时, 会形成逻辑地址; 链接是由链接程序将编译后形成的一组目标模块, 以及所需库函数链接, 形成完整的装入模块; 装入是由装入程序将装入模块装入内存。

9． 在页式存储管理系统中, 采用某些页面置换算法, 会出现Belady 异常现象, 即进程的缺页次数会随着分配给该进程的页框个数的增加而增加。下列算法中, 可能出现Belady 异常现象的是（ ）

Ⅰ.LRU 算法

Ⅱ.FIFO 算法

Ⅲ.OPT 算法

A. 仅Ⅱ

B. 仅Ⅰ Ⅱ

C. 仅Ⅰ Ⅲ

D. 仅Ⅱ Ⅲ

【答案】A

【解析】Belady 现象只有FIFO 算法才会出现

10．如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用下列哪一种查找方法（ ）。

A. 分块

B. 顺序

C. 折半

D. 哈希

第 4 页，共 55 页