2009年计算机考研408真题及答案解析

在处理主机与打印机之间速度不匹配的问题时，通常会设置一个打印数据缓冲区。主机将待输出的数据逐个写入该缓冲区，而打印机则按顺序从中读取并打印。从逻辑结构上看，这种先进先出的数据组织方式应采用以下哪种结构？

A. 栈

B. 队列

C. 树

D. 图

假设栈 S 与队列 Q 初始状态均为空，元素 a, b, c, d, e, f, g 按照顺序依次压入栈 S。每个元素出栈后立即进入队列 Q。若最终从队列中出队的元素顺序为 b, d, c, f, e, a, g，则可以推断出栈 S 在运行过程中所需的最小容量是多少？

A. 1

B. 2

C. 3

D. 4

已知一棵完全二叉树的第6层（以根节点为第1层）有8个叶子节点，那么这棵完全二叉树最多可能包含多少个节点？

A．39

B．52

C．111

D．119

将森林转换成对应的二叉树后，若在该二叉树中，结点 u 是结点 v 的祖父节点（即 u 是 v 父亲的父亲），则在原始森林中，u 与 v 之间可能存在下列哪些关系？

I. 父子关系

II. 兄弟关系

III. u 的父节点与 v 的父节点是兄弟关系

A. 只有II

B. I和II

C. I和III

D. I、II和III

关于无向连通图的特性，下列叙述正确的是：

Ⅰ. 所有顶点的度数之和为偶数

Ⅱ. 边的数量大于顶点数量

Ⅲ. 至少存在一个度数为1的顶点

A. 只有Ⅰ

B. 只有Ⅱ

C. Ⅰ和Ⅱ

D. Ⅰ和Ⅲ

下列描述中，哪一项不符合 m 阶 B 树的定义要求？

A．根节点最多拥有 m 棵子树

B．所有叶节点都位于同一层次

C．各节点内的关键字必须按升序或降序排列

D．叶节点之间通过指针相互链接

已知关键字序列 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

如果某排序算法执行到第二趟时，得到的关键字序列为 11，12，13，7，8，9，23，4，5，那么该算法只可能是以下哪一种？

A．起泡排序

B．插入排序

C．选择排序

D．二路归并排序

在冯·诺依曼体系结构的计算机中，指令和数据均以二进制形式存储于内存中。CPU 区分它们的主要依据是什么？

A．指令操作码的译码结果

B．指令和数据的寻址方式

C．指令周期的不同阶段

D．指令和数据所在的存储单元地址

一段C语言程序运行于32位系统上，定义了三个变量 x、y 和 z，其中 x 和 z 为 int 类型，y 为 short 类型。初始时 x = 127，y = -9，执行赋值语句 z = x + y 后，x、y、z 的十六进制表示分别为多少？

A. x=0000007FH , y=FFF9H , z=00000076H

B. x=0000007FH , y=FFF9H , z=FFFF0076H

C. x=0000007FH , y=FFF7H , z=FFFF0076H

D. x=0000007FH , y=FFF7H , z=00000076H