计算机考研真题及答案：选择题解析+二叉树重点

"2009-2010计算机考研真题及答案(含选择题解析)WORD高清晰版" 这些题目涵盖了计算机科学的基础知识，包括数据结构、算法、操作系统、计算机网络等多个方面。以下是对这些知识点的详细解释： 1. **缓冲区**：在计算机系统中，缓冲区用于解决速度不匹配问题。在这个问题中，缓冲区作为一个队列，主机将数据写入，打印机按顺序读取，确保数据传输的顺畅。 2. **栈和队列**：栈遵循“后进先出”（LIFO）原则，而队列遵循“先进先出”（FIFO）原则。题目中，元素出栈后立即进入队列，说明栈的容量至少需要能容纳两次入栈操作，即2个元素。 3. **二叉树遍历**：题目中的遍历序列3, 1, 7, 5, 6, 2, 4，对应于前序遍历（NLDR）、中序遍历（LNRD）或后序遍历（LRDN）。 4. **平衡二叉树**：平衡二叉树是一种特殊的二叉树，左右子树的高度差不超过1，且左右子树都是平衡二叉树。题目中的选项需要根据具体图形来判断，平衡二叉树的定义要求左右子树高度差不超过1，且所有节点的左右子树都是平衡的。 5. **完全二叉树**：对于完全二叉树，如果第i层有k个节点，那么总节点数最多是1+2+...+(k-1)+k = k(k+1)/2。第6层有8个叶节点，意味着第5层至少有9个节点，因此总节点数最多是45+8=53，选项B（52）是最接近但不超过53的值。 6. **森林转换为二叉树**：森林转换成二叉树的规则是，每个树变成一个结点，原树的父子关系变成二叉树的父子关系，兄弟关系变成父结点的左右子结点关系。所以u可能是v的祖父，也可能是v的伯父或叔父。 7. **无向连通图特性**：无向图中所有顶点的度之和等于边的数量的两倍，因为每条边连接两个顶点，所以度之和为偶数（I正确）。连通图的边数至少是顶点数减1（II错误）。至少有一个顶点的度为1（III正确），这是最小生成树的Kruskal算法中的剪枝条件。 8. **B树**：m阶B树的根节点最多有m-1个关键字，每个节点最多有2m-1个子节点（A错误）。所有叶节点都在同一层上（B正确），且节点内的关键字升序或降序排列（C正确）。叶节点之间通过指针链接（D错误，叶节点之间不必通过指针链接，但B树通常为了效率会这么设计）。 9. **堆**：小根堆（最小堆）中，每个父节点的值都小于或等于其子节点的值。插入新元素3，需要调整以保持堆性质。调整后的小根堆是C选项，因为3应该成为新的根节点，然后是5，接着是12，以此类推。 10. **排序**：23是原序列中最大的数，插入3后，需要向下调整以保持堆性质。调整后的小根堆是B选项，因为3成为新根，然后是5，接着是12，以此类推。 这些题目考察了计算机科学的基本概念和理论，是考研准备的重要部分。理解并掌握这些知识点对深入学习计算机科学至关重要。