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

一、单项选择题

1． 由3个结点可以构造出多少种不同的有向树？（ ）

A.2

B.3

C.4

D.5

【答案】A

【解析】满足以下条件的有向图称为有向树:①有且仅有一个结点的入度为0；②除树根外结点的入度为1；③从树根到任一结点有一有向通路。

2． 若一棵完全二叉树有768个结点, 则该二叉树中叶结点的个数是（ ）。

A.257

B.258

C.384

D.385

【答案】C

【解析】由

和可知, , 即, 显然

则384, 所以二叉树的叶结点个数是384。

还可以根据完全二叉树的另一个性质:

最后一个分支结点的序号为, 故非叶子结点数为384, 而叶子结点的个数为) 。 。(表示不大于x 的最大整数, 比如

3． 某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为字节，页表项大小为2字节，逻辑地址结构为:

逻辑地址空间大小为

（ ）.

A.64

B.128

C.256

D.512

【答案】B

【解析】地址空间分为逻辑地址空间和物理地址空间. 页的大小为

采用二级页表，

一页可存放

个页面来保存页表项，故本题答案为B.

第 2 页，共 67 页 页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是字节，页表项大小为2B ，字节，

故最少需要个页表项，本题中逻辑地址空间大小为

4． 在一棵具有15个关键字的4阶B 树中, 含关键字的结点数最多是（ ）

A.5 B.6 C.10 D.15

【答案】D

【解析】M 阶B 树非根结点含关键字个数

键字, 一共有15个关键字那么最多有15个含有关键字的结点

5． 排序算法的稳定性是指（ ）。

A. 经过排序之后，能使值相同的数据保持原顺序中的相对位置不变

B. 经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变

C. 算法的排序性能与被排序元素的数量关系不大

D. 算法的排序性能与被排序元素的数量关系密切

【答案】A

【解析】假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=tj，且ri 在ij 之前，而在排序后的序列中，ri 仍在rj 之前，则称这种排序算法是稳定的；否则称为不稳定的。

6． 将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度为（ ）。

A.4

B.5

C.6

D.7

【答案】C

【解析】若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。具有n 个(n＞0) 结点的完全二叉树的高度为或由完全二叉树类推到完全三叉树可知，n 个结点的完全三叉树的高度为

或》

7． 假设某计算机的存储系统由Cache 和主存组成. 某程序执行过程中访存1000次，其中访问Cache 缺失(未命中)50次，则Cache 的命中率是（ ）.

A.5% B.

C.50%

D.95%

【答案】D

【解析】Cache 的命中率H ＝N 1(N1＋N 2) ，其中N 1为访问Cache 的次数，N 2为访存主存的次

第 3 页，共 67 页 。 4阶B 树非根结点含关键字1~3个, 所以要使关键字结点数量最多, 那么每个结点只有一个关

数，程序总访存次数为N 1＋N 2，程序访存次数减去失效次数就是访问Cache 的次数队. 所以根据公式可得：H ＝(1000﹣50) /100＝95%.

8． 系统为某进程分配了4个页框, 该进程已访问的页号序列为2, 0, 2, 9, 3, 4, 2, 8, 2, 3, 8, 4, 5, 若进程要访问的下一页的页号为7, 依据LRU 算法, 应淘汰页的页号是（ ）。

A.2

B.3

C.4

D.8

【答案】B

【解析】LRU 置换算法是选择最近最久未使用的页面予以淘汰。进程有4个页框, 题中访问过程中页框的变化如下:

访问页号为7的页时, 内存中存在的页的页号是:3、8、4和5, 根据LRU 定义应淘汰的是3。

9． 某机器字长16位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第1字节为操作码字段，第2字节为相对位移量字段. 假定取指令时，每取一个字节PC 自动加1. 若某转移指令所在主存地址为2000H ，相对位移量字段的内容为06H ，则该转移指令成功转移后的目标地址是（ ）.

A.2006H

B.2007H

C.2008H

D.2009H

【答案】C

【解析】相对寻址方式的有效地址EA ＝(PC)＋D ，其中PC 为程序计数器，D 为相对偏移量. 主存按字节编址，取指令时，每取一个字节PC 值自动加1. 由于转移指令由两个字节组成，取出这条转移指令之后的PC 值自动加2，为2002H ，故转移的目标地址为2002H ＋06H ＝2008H.

10．若一个用户进程通过read 系统调用读取一个磁盘文件中的数据, 则下列关于此过程的叙述中, 正确的是（ ）。

Ⅰ. 若该文件的数据不在内存, 则该进程进入睡眠等待状态;

Ⅱ. 请求read 系统调用会导致CPU 从用户态切换到核心态;

Ⅲ.read 系统调用的参数应包含文件的名称

A. 仅Ⅰ、Ⅱ

B. 仅Ⅰ、Ⅲ

C. 仅Ⅱ、Ⅲ

第 4 页，共 67 页