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

一、填空题

1． 设有两个算法在同一机器上运行，其执行时闻分别为100n 2和2n ，要使前者快于后者，n 至少为_____。

【答案】15

2n 【解析】当时，100n2>2n，而，时，100n ＜2

2． 高度为4的3阶B-树中，最多有_____个关键字。

【答案】26

【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。

3． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。

【答案】模式匹配；模式串

4． 当广义表中的每个元素都是原子时，广义表便成了_____。

【答案】线性表

【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。

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

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

6． 深度为H 的完全二叉树至少有_____个结点:至多有_____个结点; H 和结点总数N 之间的关系是_____。 【答案】

7． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度____；深度优先遍历图的时间复杂度_____，两者不同之处在于_____，反映在数据结构上的差别是_____。

【答案】查找顶点的邻接点的过程；0(n+e)；0(n+e)；访问顶点的顺序不同；队列和栈

【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。

8． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关，即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。

【答案】逻辑特性；在计算机内部如何表示和实现；数学特性

9． 已知一循环队列的存储空间为

则此循环队列判满的条件是_____ 【答案】

10．表达式23＋((12*3﹣2)/4＋34，5/7) ＋108/9的后缀表达式是_____。 【答案】

(表达式中的点(.)是数分隔符，如是三个数) ，其中n ＞m ，队头和队尾指针分别为front 和rear ，

二、单项选择题

11．直接插入排序在最好情况下的时间复杂度为（ ）。 A.

B.O(n) C. 2D.O(n)

【答案】B

【解析】当序列是按照直接插入排序的顺序有序时，此时进行插入时，每次都只需要和末尾的一个元素进行比较，此时的时间复杂度最好，为O(n)。

12．哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（ ）方法是哈希文件的关键。

A. 哈希函数

B. 除余法中的质数

C. 冲突处理

D. 哈希函数和冲突处理

【答案】D

【解析】哈希表是根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上。

13．有两个并发执行的进程P1和P2, 共享初值为1的变量x 。P1对x 加1, P2对x 减1。加1和减1操作的指令序列分别如下所示。

两个操作完成后, 2的值（ ）。

A. 可能为-1或3

B. 只能为1

C. 可能为0、1或2

D. 可能为-1、0、1或2

【答案】C

【解析】这是在数据库中常有的操作。为保证数据的正确, 避免产生错误, 系统必须保证数据的同步。而保证数据的同步一般采取加锁的方法, 让进程P1和P2互斥访问共享变量X 。当然用信号量和P 、V 操作也是可以保证互斥操作, 达到数据同步的。

本例中, 由于没有采取保证数据同步的相应措施, 则最后结果就会出现差错。例如, 当正常情况下, 进程P1和P2先后对x 操作, 可以看到x 值的变化为初始

则x 值的变化为初始的过程, 若P2, P1先后操作, , 这是正确的。若考虑一种并发的情况, 进程P1和P2先后执行了取数load 的操作, 它们得到的x 值均为1, 运算后, P1和P2的x 值分别为2和0, 此时要看哪个进程后执行存数store 的操作了, 哪个进程后操作, 结果就是那个进程的x 值, 所以可能的结果为0或2, 加上前面正确的x 值1, 则可能的结果就有3种了。

14．

对个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中, 错误的是（ ）。

A. 该树一定是一棵完全二叉树

B. 树中一定没有度为1的结点

C. 树中两个权值最小的结点一定是兄弟结点

D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值

【答案】A

【解析】哈夫曼树为带权路径长度最小的二叉树, 但不一定是完全二叉树, 选项A 错误; 哈夫曼树中没有度为1的结点, 选项B 正确; 构造哈夫曼树时, 最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树, C 正确; 哈夫曼树中任一非叶结点P 的权值为其左右子树根结点权值之和, 其权值不小于其左右子树根结点的权值, 在与结点P 的左右子树根结点处于同一层的结点中, 若存在权值大于结点P 权值的结点Q , 那么结点Q 与其兄弟结点中权值较小的一个应该与结点P 作为左右子树构造新的二叉树, 由此可知, 哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。

15．由3个“1”和5个“0”组成的8位二进制补码, 能表示的最小整数是（ ）。

A.-126

B.-125

C.-32

D.-3

【答案】B

【解析】能表示的最小整数一定是负数, 符号位占用1个“1”; 负数的补码和原码的转化是:原码符号位不变, 数值部分按位取反, 末位加“1”。