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

一、填空题

1． 已知一循环队列的存储空间为环队列判满的条件是（ ） 【答案】

2． 循环队列的引入，目的是为了克服_____。

【答案】假溢出时大量移动数据元素

【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。

3． VSAM 系统是由_____、_____、_____构成的。

【答案】索引集；顺序集；数据集

4． 属于不稳定排序的有_____。

【答案】希尔排序、简单选择排序、快速排序、堆排序等

5． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。

【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储

6． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。 【答案】

要加“虚结点”。

设编号为

和

的结点在顺序存储中的下标为

和

。

7． 二进制地址为011011110000，大小为【答案】011011110100；011011100000

其中队头和队尾指针分别为front 和rear , 则此循 【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，，

则结点

和

在同一层上的条件是和块的伙伴地址分别为：_____

011011110000是块的起始地址，

【解析】大小分别为式如下：

和其伙伴块的起始地址计算公

当大小为4时，起始地址

为当大小为16时，起始地址为

：

8． 关键码序列（Q ，H ，C ，Y ，Q ，A ，M ，S ，R ，D ，F ，X ），要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是_____; 若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是_____。

【答案】（Q ，A ，C ，S ，Q ，D ，F ，×，R ，H ，M ，Y ）; （F ，H ，C ，D ，a ，A ，M ，Q ，R ，S ，Y ，X ）

【解析】希尔排序的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

快速排序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

9． 一个有2001个结点的完全二叉树的高度是_____。

【答案】11

【解析】

完全二叉树的高度

10．线性表用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____。

【答案】（n －1）/2

【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平均次数为

二、选择题

11．对于栈操作数据的原则是（ ）。

A. 先进先出

B. 后进先出

C. 后进后出

D. 不分顺序

【答案】B

【解析】先进先出是队列操作数据的原则。先进后出是栈操作数据的原则，栈限定在表尾进行插入和删除。

12．知一棵二叉树的前序遍历结果为ABCDEF ，中序遍历结果为CBAEDF ，则后序遍历结果为（ ）。

A.CBEFDA

B.FEDCBA

C.CBEDFA

D. 不定

【答案】A

【解析】由前序结果可知A 为根节点，再由中序遍历结果知BC 为A 的左孩子，且C 为B 的左孩子结点，到此可排除B 项，按照这种逻辑依次推理，便可得出结果对于该类型题目，可以先根据前序遍历结果和中序遍历结果画出二叉树，然后后序遍历二叉树得到后序遍历序列。

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

A.4

B.5

C.6

D.7

【答案】C

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

全二叉树的高度为

或结点的完由完全二叉树类推到完全三叉树可知，n 个结点的完全三 叉树的高度为

或

14．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（ ）。

A. 选择排序法B. 插入排序法C. 快速排序法D. 堆排序法

【答案】A

【解析】选择排序的基本思想是：

第i 趟排序开始时，当前有序区和无序区分别为则是从当前无序区中选出关键字最小的记录

和分别变为新的有序区和新的无序区。 和该趟排序交换，使

将它与无序区的第1个记录

15．设与某资源相关联的信号量初值为3, 当前为1，若M 表示该资源的可用个数，N 表示等待该资源的进程数，则M ，N 分别是（ ）。

A.0、1

B.1、0

C.1、2

D.2、0

【答案】B

【解析】信号量初值是3表示资源数有3个，当前为1表示已经用掉2个，剩余可用的资源