### 2009年考研计算机统考真题及答案解析知识点分析
#### 一、单项选择题
**1. 打印数据缓冲区的逻辑结构**
- **知识点概述**：
- 打印数据缓冲区的设计目的是解决主机与打印机之间的速度不匹配问题。
- 主机将待打印数据写入缓冲区，打印机从缓冲区读取数据进行打印。
- 需要确定最适合这种场景的数据结构。
- **知识点详解**：
- **选项解析**：
- **栈**：先进后出（LIFO）的特点不适合打印任务的处理，因为新任务可能会覆盖旧任务。
- **队列**：先进先出（FIFO）的特点非常适合打印任务的处理，因为打印任务通常按照接收的顺序执行。
- **树**与**图**：这两种数据结构主要用于构建复杂的关系图，并不适合用作简单的数据缓冲区。
- **结论**：正确答案是B. 队列。
**2. 栈S的容量至少是多少**
- **知识点概述**：
- 栈S和队列Q的操作顺序以及栈S的最小容量分析。
- 分析栈中元素的进出顺序来推断栈的最小容量。
- **知识点详解**：
- 根据题目描述，元素按照a, b, c, d, e, f, g的顺序进入栈S，然后依次进入队列Q。
- 根据出队顺序b, d, c, f, e, a, g可以推断出栈内的操作顺序：首先b出栈，之后d出栈，c必须先进栈再出栈以便d出栈后c能够出栈；接下来f出栈前e也必须先进栈再出栈，以此类推。
- 为了实现这样的出栈顺序，栈中至少需要保持两个元素的存在（如c和e同时在栈中等待出栈）。
- **结论**：因此，栈S的容量至少是2。正确答案是B. 2。
**3. 二叉树的遍历方式**
- **知识点概述**：
- 二叉树遍历的基本概念及其不同遍历方式的特点。
- 通过遍历后的序列来反推出遍历方式。
- **知识点详解**：
- 给定二叉树的遍历结果为3, 1, 7, 5, 6, 2, 4。
- 根据二叉树的遍历规则，可以尝试不同的遍历方式并检查是否符合给定的结果。
- **选项解析**：
- **A. LRN**：左子树、右子树、根节点。根据题目中的序列，根节点是3，这意味着左子树和右子树都已经遍历完成，但这种遍历方式无法生成给定的序列。
- **B. NRL**：根节点、右子树、左子树。同样，这种遍历方式也不符合给定的序列。
- **C. RNL**：右子树、根节点、左子树。这种遍历方式也不适用于此题。
- **D. RNL**：右子树、左子树、根节点。这种遍历方式能生成题目中给定的序列3, 1, 7, 5, 6, 2, 4。
- **结论**：正确答案是D. RNL。
**4. 平衡二叉树的定义**
- **知识点概述**：
- 平衡二叉树的基本概念。
- 平衡二叉树的特征，尤其是左右子树高度差不大于1的性质。
- **知识点详解**：
- 平衡二叉树是一种特殊的二叉排序树，它的任意一个节点的左右两个子树的高度差的绝对值不超过1。
- **结论**：符合平衡二叉树定义的二叉排序树应该满足上述条件。由于题目没有给出具体的二叉树图形，无法直接判断哪个选项是正确的平衡二叉树。需要查看具体的二叉树图形才能确定。
**5. 完全二叉树的最大结点数**
- **知识点概述**：
- 完全二叉树的基本概念及其最大结点数的计算方法。
- **知识点详解**：
- 完全二叉树是指除了最后一层外，其他层都是满的，并且最后一层的所有结点都靠左排列。
- 根据题目描述，第6层有8个叶结点。
- 第6层是叶子结点层，意味着第5层的结点数量必须是8个叶结点的父结点数量，即8个。
- 接下来可以计算每一层的最大结点数，直到达到第6层为止。
- **结论**：完全二叉树的结点总数可以通过公式 \(2^h - 1\) 计算，其中 \(h\) 是树的高度。本题中，树的高度至少为6，但为了求得最大的结点数，需要考虑最后一层非满的情况。具体计算略。
- 正确答案需要根据具体的计算结果确定，在给定的选项中，A、B、C、D中哪一个是最合适的需要进一步的信息。
**6. 森林转换为二叉树后的关系**
- **知识点概述**：
- 森林与二叉树之间的转换原理。
- 转换前后结点之间的关系变化。
- **知识点详解**：
- 在森林转换为二叉树的过程中，森林中的树会变成二叉树中的子树。
- 森林中的树与树之间没有直接的关系，但在转换成二叉树后，相邻的树会通过右孩子连接起来。
- **选项解析**：
- **Ⅰ. 父子关系**：在原始森林中，父子关系会保留到转换后的二叉树中。
- **Ⅱ. 兄弟关系**：森林中的兄弟关系也会保留，但转换后可能会成为二叉树中某个结点的左孩子和右孩子。
- **Ⅲ. u的父结点与v的父结点是兄弟关系**：这种情况也可能出现，取决于森林的具体结构。
- **结论**：正确答案是D. Ⅰ、Ⅱ和Ⅲ，因为所有提到的关系都有可能出现。
**7. 无向连通图的特性**
- **知识点概述**：
- 无向连通图的基本概念及其特性分析。
- 无向连通图的顶点度数、边数与顶点数之间的关系。
- **知识点详解**：
- 无向连通图指的是任意两个顶点间都存在路径的无向图。
- **选项解析**：
- **Ⅰ. 所有顶点的度之和为偶数**：这是无向图的基本特性，因为在无向图中，每条边连接两个顶点，所以每条边都会被计算两次。
- **Ⅱ. 边数大于顶点个数减1**：这个说法不一定成立，对于树状结构的无向连通图来说，边数恰好等于顶点数减1。
- **III. 至少有一个顶点的度为1**：这个说法也不一定成立，例如完全图中所有顶点的度都是相同的，且大于1。
- **结论**：正确答案是A. 只有Ⅰ。
**8. m阶B树的定义要求**
- **知识点概述**：
- B树的基本概念及其性质分析。
- m阶B树的定义及其特点。
- **知识点详解**：
- m阶B树是一种自平衡的查找树，广泛用于数据库和文件系统中。
- **选项解析**：
- **A. 根节点最多有m棵子树**：这符合m阶B树的定义。
- **B. 所有叶结点都在同一层上**：这也是m阶B树的重要特性之一。
- **C. 各结点内关键字均升序或降序排列**：这也是m阶B树的特性之一。
- **D. 叶结点之间通过指针链接**：这不是m阶B树的标准定义的一部分，通常叶结点并不需要通过指针链接。
- **结论**：不符合m阶B树定义要求的是D. 叶结点之间通过指针链接。
**9. 小根堆的调整**
- **知识点概述**：
- 小根堆的基本概念及其调整方法。
- 插入新元素后小根堆的重新调整过程。
- **知识点详解**：
- 小根堆是一种特殊的数据结构，其特点是根节点的键值小于或等于其子节点的键值。
- 当插入新的关键字3后，需要对其进行调整以保持小根堆的性质。
- 根据题目描述，原小根堆的结构为5, 8, 12, 19, 28, 20, 15, 22。
- 插入3后，需要将3放置在合适的位置，以确保所有节点的键值仍然满足小根堆的性质。
- **结论**：正确答案是A. 3, 5, 12, 8, 28, 20, 15, 22, 19。
**10. 排序算法的识别**
- **知识点概述**：
- 不同排序算法的基本概念及其特点。
- 根据排序过程中产生的中间结果来推断使用的排序算法。
- **知识点详解**：
- 根据题目描述，排序后得到的序列为11, 12, 13, 7, 8, 9, 23, 4, 5。
- **选项解析**：
- **A. 起泡排序**：起泡排序在每一轮比较交换相邻的两个元素，但无法得到题目中的排序结果。
- **B. 插入排序**：插入排序是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。这一过程能够生成题目中的结果。
- **C. 选择排序**：选择排序每次从未排序部分选取最小(或最大)的元素，放到排序序列的末尾，也无法生成题目中的排序结果。
- **D. 二路归并排序**：二路归并排序先对数组进行分治，然后再合并排序，也不适合生成题目中的结果。
- **结论**：正确答案是B. 插入排序。
**11. CPU如何区分指令与数据**
- **知识点概述**：
- CPU处理指令和数据的基本原理。
- 在存储器中，如何区分指令和数据。
- **知识点详解**：
- 冯•诺依曼架构下，指令和数据都以二进制形式存放在存储器中。
- CPU通过指令周期的不同阶段来区分指令和数据。
- **结论**：正确答案是C. 指令周期的不同阶段。
**12. C语言程序中的变量类型和值**
- **知识点概述**：
- C语言中的基本数据类型。
- 变量的内存表示。
- **知识点详解**：
- 根据题目描述，x和z为int型，y为short型。
- 当x=127, y=-9时，执行赋值语句z=x+y。
- x=127可以表示为十六进制0x7F，y=-9可以表示为十六进制0xFFF7。
- 计算z=x+y的结果时，由于y是short类型，它会被自动提升为int类型进行计算。
- **结论**：正确答案是D. x=0000007FH，y=FFF7H，z=00000076H。
**13. 浮点数加法计算**
- **知识点概述**：
- 浮点数加法的基本原理及其计算过程。
- 对阶、尾数运算、规格化、舍入和判溢出等步骤的详细解释。
- **知识点详解**：
- 浮点数加法需要经历多个步骤，包括对阶、尾数运算、规格化、舍入和判溢出等。
- 根据题目描述，X=2^7 × 29/32，Y=2^5 × 5/8。
- 首先进行对阶操作，使X和Y具有相同的指数。
- 然后进行尾数的加法运算。
- 最后进行规格化、舍入和判溢出等步骤。
- **结论**：正确答案是D. 发生溢出。
**14. Cache映射方式**
- **知识点概述**：
- 缓存(Cache)的基本概念及其映射方式。
- 2路组相联映射方式的基本原理。
- **知识点详解**：
- 根据题目描述，Cache共有16块，采用2路组相联映射方式，即每组2块。
- 主存块大小为32字节，按字节编址。
- 主存129号单元所在主存块应装入到的Cache组号计算如下：
- 主存地址129的二进制表示为10000001。
- Cache的组号计算需要考虑到Cache的大小和组的数量。
- 根据2路组相联映射的计算方法，可以得出主存129号单元所在主存块应装入到的Cache组号。
- **结论**：正确答案是A. 0。
**15. 存储器设计**
- **知识点概述**：
- 存储器的基本设计原理。
- 使用不同规格的存储器芯片来构建存储系统的计算方法。
- **知识点详解**：
- 根据题目描述，计算机主存容量为64KB，其中ROM区为4KB，其余为RAM区。
- 需要使用2K×8位的ROM芯片和4K×4位的RAM芯片来设计该存储器。
- 首先计算ROM区所需的芯片数，然后计算RAM区所需的芯片数。
- **结论**：正确答案是D. 2、30。
**16. 相对寻址**
- **知识点概述**：
- 相对寻址的基本概念及其计算方法。
- 在给定转移指令的情况下，计算转移后的目标地址。
- **知识点详解**：
- 根据题目描述，转移指令所在主存地址为2000H，相对位移量字段的内容为06H。
- 转移指令使用相对寻址方式，表示目标地址相对于当前指令地址的距离。
- 计算转移后的目标地址需要考虑到当前指令地址、相对位移量以及每取一个字节PC自动加1的规则。
- **结论**：正确答案为2006H。
