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

一、单项选择题

1． 若一棵二叉树的前序遍历序列和后序遍历序列分别为1, 2, 3, 4和4, 3, 2, 1, 则该二叉树的中序遍历序列不会是（ ）。

A.1, 2, 3, 4

B.2, 3, 4, 1

C.3, 2, 4, 1

D.4, 3, 2, 1

【答案】C

【解析】题目中的二叉树的先序序列和后序序列正好相反, 这样的二叉树每层只有一个结点。该二叉树的形态如下图所示。

从左至右, 这8棵二叉树的中序序列分别为:

(1)4, 3, 2, 1,

(2)3, 4, 2, 1

(3)2, 4, 3, 1

(4)2, 3, 4, 1

(5)1, 4, 3, 2

(6)1, 3, 4, 2

(7)1, 2, 4, 3

(8)1, 2, 3, 4

显然选项C 的中序序列不会出现。

2． 从堆中删除一个元素的时间复杂度为（ ）。

A.O(1) B.

C.O(n) D.

【答案】B

【解析】堆中删除一个元素，需要重新调整堆，其时间复杂度为

第 2 页，共 58 页 。

3． 循环队列A[0..m﹣1]存放其元素值，用front 和rear 分别表示队头和队尾，则当前队列中的元素数是（ ）。

A.(rear﹣front ＋m)%m

B.rear ﹣front ＋1

C.rear ﹣front ﹣1

D.rear ﹣front

【答案】A

【解析】对于循环队列，需要深刻理解队头(font)和队尾(rear)的概念，在队头进行出队操作，在队尾进行进队操作。rear-front 可能为正也可能为负，为正时元素个数＝(rear-front)；如果为负则元素的个数＝(rear-front+m)，所以统一的公式就是(rear-front+m)%m。

4． 执行完下列语句段后，f 值为（ ）。

A.2

B.4

C.8

D. 无限递归

【答案】B

【解析】该程序使用了递归调用，由题知，:f(0)＝2；f(l)＝l*f(0)＝2；f(2)＝2*f(l)＝4；所以结果为4。

5． 某时刻进程的资源使用情况如下表所示

此时的安全序列是（ ）。

A.P1, P2, P3, P4

B.P1, P3, P2, P4

C.P1, P4, P3, P2

D. 不存在

【答案】D

【解析】典型的死锁避免算法, 银行家算法的应用。银行家算法是操作系统中的一个重点知识

第 3 页，共 58 页

单元, 考生对此应该非常熟悉, 本题并无难点。分析一下下表, 可以看到, 经过P1, P4的运行以后, 可用资源是2, 2, 1, 而P2, P3所需资源分别是1, 3, 2和1, 3, 1。所以剩余资源已经不够P2或P3的

分配, 亦即找不到能够安全运行的序列, 因此此时是处于不安全状态, 所以不存在这样的安全序列。

6． 循环两列放在一维数组 中, end1指向队头元素, end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作, 队列中最多能容纳M-1个元素。初始时为空, 下列判断队空和队满的条件中, 正确的是（ ）

A. 队空:endl==end2; 队满:endl==(end2+l)modM

B. 队空Gendl==end2; 队满:Gend2==(endl+1)mod(M-1)

C. 队空Gend2==(endl+1)modM; 队满:Gendl==(end2+l)modM

D. 队空:

【答案】A

【解析】在循环队列中, 在少用一个元素空间的前提下, 可约定入队前, 测试尾指针在循环意义下加1后是否等于头指针, 若相等, 则队满。而队空的条件还是首尾指针是否相等。

7． 下列有关浮点数加减运算的叙述中, 正确的是（ ）。

Ⅰ. 对阶操作不会引起阶码上溢或下溢

Ⅱ. 右规和尾数舍入都可能引起阶码上溢

Ⅲ. 左规时可能引起阶码下溢

Ⅳ. 尾数溢出时结果不一定溢出

A. 仅Ⅱ Ⅲ

B. 仅Ⅰ Ⅱ Ⅳ

C. 仅Ⅰ Ⅲ Ⅳ

D. Ⅰ Ⅱ ⅢⅣ

【答案】D

【解析】浮点数的加减运算步骤包括:①对阶, 使两个操作数的小数点位置对齐, 阶码小的尾数右移, 可能产生溢出, 但是阶码不会溢出; ②尾数求和, 将对阶后的尾数按定点数加(减) 运算规则运算; ③规格化, 包括左规和右规, 左规时阶码减少, 可能出现阶码下溢, 而右规时, 阶码增加可能出现阶码上溢; ④舍入, 该过程可能需要右规调整, 因此可能出现阶码上溢; ⑤溢出判断, 浮点数的溢出与否是由阶码的符号决定的, 而不是由尾数溢出判断的, 因此尾数溢出时结果不一定溢出。因此Ⅰ

第 4 页，共 58 页 队满: