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

一、选择题

1． 下列二叉排序树中，满足平衡二叉树定义的是（ ）。

【答案】B

【解析】平衡二叉树是指左右子树高度差（平衡因子）的绝对值不超过1的二叉树。A 项中根结点的平衡因子是2; B 项中每个结点的平衡因子的绝对值均不超过1; C 项中根结点的平衡因子是-2; D 项中根结点的平衡因子是3。

2． 对于循环队列（ ）。

A. 无法判断队列是否为空

B. 无法判断队列是否为满

C. 队列不可能满

D. 以上说法都不是

【答案】D

【解析】循环队列也会出现队列满的情况，并且循环队列也可以判断是否为空或满。至少可以通过两种方法进行判断：①另设一个布尔变量来区别队列是空还是满；②队满时，（rear+1）==font。

3． 当系统发生抖动（thrashing ）时，可以采取的有效措施是（ ）。

I. 撤销部分进程

II. 增加磁盘交换区的容量

III. 提高用户进程的优先级

A. 仅I

B. 仅 II

C. 仅III

D. 仅 I 、II

【答案】A

【解析】“抖动”现象是指刚刚被换出的页很快又要被访问，为此，又要换出其他页，而该页

必须换入，又很快被访问，如此频繁地置换页面，以致操作系统的大部分时间都花在页面置换上，

引起系统性能下降甚至崩溃。 引起系统抖动现象的原因是对换的信息量过大，内存容量不足，置换算法选择不当。所以解决的办法就是降低交 换页面数量，加大内存容量，改变置换选择算法。但是降低交换页面数量和改变置换选择算法对于一个应用系统 来讲是不可能的，只能增加内存容量。増加内存容量可以是直接添加物理内存（大型计算机都可以在不关机的情 况下增加物理内存

，或者，降低进程数量，相对地增加内存。而増加交换区容量并不能解决物理内存不足的 问条）

题，提高用户进程的优先级会使系统的状态更加恶化。

4． 下列关于RISC 的叙述中，错误的是（ ）。

A.RISC 普遍采用微程序控制器

B.RISC 大多数指令在一个时钟周期内完成

C.RISC 的内部通用寄存器数量相对CISC 多

D.RISC 的指令数、寻址方式和指令格式种类相对CISC 少

【答案】A

【解析】B 项、C 项、D 项都是RISC 的特点之一，所以它们都是正确的，只有A 项是CISC 的特点，因为RISC 的速度快，所以普遍采用硬布线控制器，而非微程序控制器。

5． 若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的是（ ）

I. 处理越界错 II. 置换页 III. 分配内存

A. 仅I 、II

B .仅II 、III

C. 仅I 、III

D.I 、II 、和III

【答案】B

【解析】用户进程访问内存时缺页会发生缺页中断。发生缺页中断，系统地执行的操作可能是置换页面或分配内存。系统内没有越界的错误，不会进行越界出错处理。

6． 为提高散列（Hash ）表的查找效率，可以采用的正确措施是（ ）。

I .增大装填（载）因子

II. 设计冲突（碰撞）少的散列函数

III. 处理冲突（碰撞）时避免产生聚集（堆积）现象

A. 仅I B. 仅 II C. 仅 I 、II D. 仅 II 、III

【答案】D

【解析】散列表的查找效率（比较次数）取决于：散列函数、处理冲突的方法和散列表的装

填因子a 。CX 标 志着散列表的装满程度，通常情况下，（X 越小，发生冲突的可能性越小；反之，a 越大，表示已填入的记录越多， 再填入记录时，发生冲突的可能性越大。因此选项I 错误，越是增大装填因子，发生冲突的可能性就越大，查找 效率也越低。选项II 正确。选项III 正确。采用合适的处理冲突的方法避免产生聚集现象，也将提高查找效率。例如，用拉链法解决冲突时不存在聚集现象，用线性探测法解决冲突时易引起聚集现象。

7． 已知小根堆为8，15，10，21，34， 16，12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较数是（ ）。

A.1

B.2

C.3

D.4

【答案】C

【解析】堆排序中，依次输出堆顶的最小值，然后重新调整堆，如此反复执行，便得到一个有序序列。本题中，删除堆顶元素8后将最后一个元素12置于堆顶，然后调整堆：首先与15比较，12小于15, 所以不用交换；然后与10比较，因为10小于12，所以交换10和12的位置；调

整后12再与16比较，12小于16，调整堆过程结束。因此12共与15、10、16进行了三次比较。

8． 若元素a ，b , c, d, e，f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（ ）。

A.d ，c ，e ，b ，f ，a

B.c ，b ，d ，a ，e ，f

C.b ，c ，a ，e ，f ，d

D.a ，f ，e ，d ，c ，b

【答案】D

【解析】4个选项所给序列的进、出栈操作序列分别为：

选项A.Push , Push , Push ，Push , Pop, Pop, Push，Pop , Pop, Push , Pop ，Pop

选项B.Push , Push , Push , Pop , Pop , Push, Pop, Pop, Push, Pop , Push, Pop

选项C.Push , Push , Pop , Push , Pop , Pop, Push, Push, Pop, Push , Pop , Pop

选项D.Push , Pop , Push, Push , Push , Push, Push, Pop, Pop，Pop , Pop , Pop

按照题目要求，不允许连续三次进行退栈操作，所以选项D 所给序列为不可能得到的出栈顺序。

9． 在有向图的邻接表存储结构中，顶点V 在链表中出现的次数是（ ）。

A. 顶点V 的度 B. 顶点V 的出度 C. 顶点V 的入度 D. 依附于顶点V 的边数

【答案】B

【解析】在有向图中，第j 个链表中的结点个数只是顶点Vi 的出度，为求入度，必须遍历整个邻接表。因此顶点V 在链表中出现的次数是顶点V 的出度。