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

一、单项选择题

1． 已知一个长度为16的顺序表L , 其元素按关键字有序排列。若采用折半查找法查找一个L 中不存在的元素, 则关键字的比较次数最多是（ ）。

A.4

B.5

C.6

D.7

【答案】B

【解析】

折半查找法在查找不成功时和给定值进行比较的关键字个数最多为, 在本题中, n=16, 故比较次数最多为5。

2． 用户程序发出磁盘请求后, 系统的处理系统的处理流程是:用户程序一系统调用处理程序—设备骆动程序一中断处理程序。其中, 计算数据所在磁盘的柱面号、磁头号、扇区号的程序是（ ）

A. 用户程序

B. 系统调用处理程序

C. 设备驱动程序

D. 中断处理程序

【答案】C

【解析】计算磁盘号、磁头号和扇区号的工作是由设备驱动程序完成的, 所以答案选C 。

3． 对进行基数排序，一趟排序的结果是:（ ）

A. 05， 46， 13， 55， 94， 17， 42 B.

C. 42，13， 94，05， 55， 46，17

D. 05，13， 46，55，17，42，94

【答案】C

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

①最低位优先的过程

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

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

成，

其中

分配:开始时，把

收集:把构成，每个结点的关键字由d 元组。在排序过程中，使用r 个队列组。排序过程就是对i=0， 1，... ，d －1，依次做一次“分配”和“收集”。 各个队列置成空队列，然后依次考察线性:

表中的每一个结点各个队列中的结点依次首尾相接，得到新的结点序列，从而组成新的。如果的关键字k=k，就把放进Q k 队列中。

线性表。

4． 假设栈初始为空, 将中缀表达式

当扫描到f 时, 栈中的元素依次是（ ） A.

B.

C.

D.

【答案】B

【解析】中缀表达式转后缀表达式遵循以下原则:

(1)遇到操作数, 直接输出;

(2)栈为空时, 遇到运算符, 入栈;

(3)遇到左括号, 将其入栈;

(4)遇到右括号, 执行出栈操作, 并将出栈的元素输出, 直到弹出栈的是左括号, 左括号不输出;

(5)遇到其他运算符

符入栈;

(6)最终将栈中的元素依次出桟, 输出。

所以扫描到‟/‟, 入栈„描到‟+‟, 由于‟+‟优先级比‟/'低, 所以将‟/‟弹出, ‟+‟入栈; 扫描到‟*,, 优先级比‟+‟高, 入栈; 扫描到‟(„, 入栈; 扫描到‟一„, 将栈中优先级更高的‟*‟弹出, „一, 入栈; 扫描到‟*‟, 优先级比‟一„高, 入栈。所以扫描至“f的时候, 栈中元素为:+(一*

5． 下面关于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 项错误。

6． 数组中含有元素的个数（ ）。

A.55

B.45

C.36

D.16

【答案】B

【解析】该数组为三维数组。其个数为5*3*3＝45。

7． 若X 是后序线索二叉树中的叶结点, 且X 存在左兄弟结点Y , 则X 的右线索指向的是 （ ）

A.X 的父结点

B. 以Y 为根的子树的最左下结点

C.X 的左兄弟结点Y

D. 以Y 为根的子树的最右下结点

【答案】A

【解析】根据后续线索二叉树的定义, X 结点为叶子结点且有左兄弟, 那么这个结点为右孩子结点, 利用后续遍历的方式可知X 结点的后继是其父结点, 即其右线索指向的是父结点。

8． 设有向图G=(V, E) , 顶点集,

边集,

若从顶点V0开始对图进行深度优先遍历, 则可能得到的不同遍历序列个数是（ ）。

A.2

B.3

C.4

D.5

【答案】D

【解析】根据题意知有向图的结构如图所示。深度优先遍历的特点是尽可能先对纵深方向进行搜索, 所以可能得到的不同遍历序列分别是: ①

④

' ; ②; ⑤; ③。

;