2018年辽宁大学信息学院903计算机专业基础[专业硕士]之数据结构考研强化五套模拟题
● 摘要
一、单项选择题
1． 元素a , b , c , d , e 依次进入初始为空的栈中, 若元素进栈后可停留、可出栈, 直到所有元素都出栈, 则在所有可能的出栈序列中, 以元素d 开头的序列个数是（ ）。
A.3 B.4 C.5 D.6
【答案】B
【解析】d 首先出栈后的状态如下图所示。
此时可有以下4种操作:
(1)e进栈后出栈, 出栈序列为decba 。 (2)c出栈, e 进栈后出栈, 出栈序列为dceba 。 (3)cb出栈, e 进栈后出栈, 出栈序列为dcbea 。
(4)cba出栈, e 进栈后出栈, 出栈序列为dcbae 。
2． 若一棵二叉树的前序遍历序列和后序遍历序列分别为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 的中序序列不会出现。
3． 已知关键字序列5，8，12，19，28，20，15，22是小根堆(最小堆) ，插入关键字3，调整后的小根堆是（ ）.
A.3， 5， 12， 8， 28， 20， 15， 22， 19 B.3， 5， 12， 19， 20， 15， 22， 8， 28 C.3， 8， 12， 5， 20， 15， 22， 28， 19 D.3， 12， 5， 8， 28， 20， 15， 22， 19
【答案】A
【解析】在堆中插入或删除一个元素后，将不再满足堆的性质. 为了使其成为新堆，在输出堆顶元素后，需要调整剩余元素. 具体过程如图(1)〜(5)所示，(1)为原堆，(2)为插入3后，(3)、(4)为调整过程，(5)为调整后的小根堆
.
(3)
(4)
(5)
4． 用海明码对长度为8位的数据进行检/纠错时, 若能纠正一位错, 则校验位数至少为（ ）
A.2 B.3 C.4 D.5
【答案】C
【解析】设校验位的位数为k , 数据位的位数为n , 根据海明码编码k 和n 应满足下述关系。
。
n=8, 当k=4时, , 符合要求, 校验位至少是4位, 故答案为C 。
5． 当系统发生抖动(thrashing)时, 可以采取的有效措施是（ ）。
Ⅰ. 撤销部分进程 Ⅱ. 增加磁盘交换区的容量 Ⅲ. 提高用户进程的优先级 A. 仅Ⅰ B. 仅Ⅱ C. 仅Ⅲ D. 仅Ⅰ、Ⅱ 【答案】A
【解析】“抖动”现象是指刚刚被换出的页很快又要被访问, 为此, 又要换出其他页, 而该页又