2009年计算机考研真题与解析：选择题+应用题

"这是一份计算机考研的真题资料，包含2009年的选择题和综合应用题，以及相应的答案解析。这份word版文档旨在帮助考生复习和准备计算机科学与技术专业的研究生入学考试。" 这份资料涵盖了多个计算机基础知识点，以下是其中一些重点内容的详细解释： 1. **缓冲区**：在计算机系统中，为了处理速度不匹配问题，通常会使用缓冲区，如打印数据缓冲区。这里提到的缓冲区是一个先进先出（FIFO）的数据结构，对应于队列。 2. **栈与队列**：题目中提到了栈和队列的操作。栈是一种后进先出（LIFO）的数据结构，而队列则是先进先出。在题目中，元素出栈后进入队列，顺序变化体现了这两种数据结构的特点。 3. **二叉树遍历**：二叉树遍历有前序、中序、后序和层次遍历四种方式。题目中的遍历序列对应于后序遍历（NLDR）。 4. **平衡二叉树**：平衡二叉树是一种特殊的二叉树，左右子树的高度差不超过1，并且左右子树都是平衡二叉树。题目给出了二叉排序树的图像，要求判断是否满足平衡二叉树的定义。 5. **完全二叉树**：完全二叉树的性质是，除了最后一层外，其他层都被完全填满，最后一层的叶子节点都尽可能地靠左排列。题目中提及了第6层叶节点数量与全树节点数量的关系。 6. **森林转二叉树**：森林转化为二叉树，父子关系、兄弟关系以及通过原森林中结点关系的推断是常见考点。 7. **无向连通图特性**：无向连通图的边是顶点之间的路径，题目中涉及的特性包括顶点度数的奇偶性、边数与顶点数的关系以及存在度为1的顶点。 8. **B树**：B树是一种自平衡的多路查找树，根节点最多有m棵子树，所有叶节点在同一层，且节点内关键字有序。D选项提到的叶节点间通过指针链接不是标准B树的定义。 9. **小根堆**：小根堆是堆数据结构的一种，其中每个父节点的键值都不大于其子节点。插入新元素并调整保持堆性质是堆操作的关键。 10. **排序算法**：题目中提到了排序序列，可能是某种排序算法如插入排序、快速排序等的中间结果。 这些知识点涵盖了数据结构（栈、队列、二叉树、B树、堆）、算法（排序）、图论（无向连通图）等多个计算机科学的基础概念，对于备考计算机考研的学生来说，理解和掌握这些内容至关重要。