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

一、填空题

1． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。

【答案】O （eloge ）; 边稀疏

2． 二进制地址为011011110000，大小为

【答案】011011110100；011011100000

011011110000是块的起始地址，

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

当大小为4时，起始地址

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

：

3． 在有n 个顶点的有向图中，每个顶点的度最大可达。

【答案】2（n-l ）

【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。

4． 高度为h 的堆中，最多有_____元素，最少有_____个元素。

【答案】

当最后一层只有

【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为 一个元素时，此时堆的元素个数最少，元素个数为

5． 表达式的后缀表达式是_____。

【答案】

6． 在基于关键字比较且时间为O （nl 〇g2n ）的排序中，若要求排序是稳定的，则可选用_____，则可选用_____排序。 排序；若要求就地排序（及辅助空间为0（1））

【答案】归并；堆

7． 设有个结点的完全二叉树顺序存放在向量

【答案】

中，其下标值最大的分支结点为_____。

和

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

和

块的伙伴地址分别为：_____

【解析】最大的分支结点是最后一个叶子结点的父结点。

8． 二叉树由_____，_____，_____三个基本单元组成。

【答案】根结点；左子树；右子树

9． —个字符串中_____称为该串的子串。

【答案】任意个连续的字符组成的子序列

10．从用户的观点看，文件的逻辑结构通常可以区分为两类：一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件:另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____，_____和_____。B+树适用于组织_____的索引结构，m

阶个关键码。

【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；

树每个结点至多有_____个儿子，除

根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____

二、选择题

11．下面关于B 和B+树的叙述中，不正确的是（ ）

A.B 树和B+树都是平衡的多叉树 B.B 树和B+树都可用于文件的索引结构 C.B 树和B+树都能有效地支持顺序检索 D.B 树和B+树都能有效地支持随机检索 【答案】C

【解析】B 树是一种平衡的多分树，通常我们说m 阶的B 树，它必须满足如下条件：①每个结点至多有m 个子结点；②除根结点和叶结点外，其它每个结点至少有个子结点；③若根结点不是叶子结点，则至少有两个子结点；④所有的叶结点在同一层；⑤有k 个子结点的非根结点恰好包含k-1个关键码。B+树是B 树的一种变形树，它与B 树的差异在于：有k 个子结点的结点必然有k 个关键码；非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。其中B 树适合与随即检索，不适合于顺序检索，所以C 项错误。

12．某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，元素a , b , c , d , e 依次入此队列后再进行出队操作，则不可能得到的出队序列是（ ）。

A.b ，a , c , d ，e B.d ，b , a , c ，e C.d ，b , c , a ，e D.e ，c ，b , a ，d

【答案】C

【解析】根据题意，队列两端都可以输入数据元素，但是只能在一端输出数据元素，这种队列为输出受限的双端队列。本题解题方法分别判断每个选项如何入队和出队，从而得出不可能的

情况。

假设L 代表从左端入队，R 代表从右端入队，出队都是从左端L 出。四个选项所给序列的进队操作序列分别为：

选项 A. aL （或 aR ）, bL, cR, dR, eR 选项 B. aL （或 aR ）, bL, cR，dL , eR 选项C. 不可能出现 选项 D. aL （或 aR ）, bL, cL, dR, eL

13．下列调整中，不可能导致饥饿现象的是（ ）

A. 时间片转移 B. 静态优先及调度 C. 非抢占式作业优先 D. 抢占式短作业优先 【答案】A

【解析】时间片转移方法能在一个周期内使每个进程都得到一个时间片的CPU 使用时间，不会产生饥饿的现象，其余三个都会产生饥饿。

14．用海明码对长度为8位的数据进行检/纠错时，若能纠正一位错，则校验位数至少为（ ）

A.2 B.3 C.4 D.5

【答案】C

【解析】设校验位的位数为k ，数据位的位数为n ，根据海明码编码k 和n

应满足下述关系。

当k=4时，

符合要求，校验位至少是4位，故答案为C 。

15．对{05，46，13，55，94，17，42}进行基数排序，一趟排序的结果是:（ ）

A.05，46，13，55，94，17，42 B.05，13，17，42，46，55.94 C.42，13，94，05，55，46，17 D.05，13，46，55，17，42，94

【答案】C

【解析】基数排序有两种：最低位优先和最高位优先。

最低位优先的过程

先按最低位的值对记录进行排序，在此基础上，再按次低位进行排序，依此类推。由低位向高位，每趟都是根据关键字的一位并在前一趟的基础上对所有记录进行排序，直至最高位，则完成了基数排序的整个过程。

以r 为基数的最低位优先排序的过程 假设线性表由结点序列组成，

其中

构成，每个结点aj 的关键字由d 元组（k ，k... ，k ，k ）在排序过程中，使用r 个队列

排序过程就是

对i=0，1，... ，d-1，依次做一次“分配”和“收集”。