2009-2011计算机考研真题与解析

"09-11计算机考研真题，包含09年至11年统考计算机专业课基础综合的历年真题及选择题解析，是计算机考研的重要参考资料。" 以下是对这些考研真题中涉及知识点的详细说明： 1. **缓冲区管理**：在计算机系统中，缓冲区用于解决速度不匹配问题。例如，主机向缓冲区写入数据，而打印机从缓冲区取出数据。这种结构通常使用队列实现，先进先出（FIFO），确保打印机不会因主机速度快而跟不上。 2. **栈与队列的应用**：在题目中提到的元素进出栈再进入队列的情况，反映出栈的后进先出（LIFO）特性与队列的先进先出（FIFO）特性。在本例中，栈的容量至少需要4个单位，使得所有元素都能在打印机取走之前存储。 3. **二叉树遍历**：题目中给出的结点顺序暗示了不同的遍历方式。根据顺序，可以推断这是后根遍历（RLN或RNL）。 4. **平衡二叉树**：平衡二叉树是一种特殊的二叉树，左右子树的高度差不超过1。题目中给出了二叉排序树，平衡二叉树定义要求左右子树高度接近，选项中满足这一条件的树是未给出的。 5. **完全二叉树的性质**：完全二叉树的第i层最多有2^(i-1)个节点。第6层有8个叶节点，说明第5层至少有4个节点。因此，节点总数最多为1+2+4+8+16+31=56，选项中没有这个选项，可能是题目输入错误。 6. **森林与二叉树的转换**：森林转换为二叉树后，原森林中的父子关系、兄弟关系在二叉树中得以体现。选项I和III是可能的关系。 7. **无向连通图的特性**：无向连通图中，所有顶点的度之和等于边数的两倍，因为每条边连接两个顶点，所以度之和为偶数。边数总是等于顶点个数减去连通分量的数量，对于连通图来说是顶点个数减1。但不是所有的顶点度都必须为1，至少有一个顶点的度大于1才能构成连通图。因此，只有I和II正确。 8. **B树的性质**：B树是一种自平衡的查找树，其根节点最多有m棵子树，所有叶结点在同一层，且结点内的关键字是有序的。叶结点间通过指针链接是错误的，因为B树的叶结点不需要通过指针链接。 9. **堆排序**：小根堆（最小堆）是所有父节点的值都不大于其子节点的二叉树。插入新元素3后，需要调整堆以保持堆属性。根据选项，选项C符合小根堆的定义，因为每个父节点的值都不大于其子节点。 10. **排序算法**：第二趟排序后的结果表明，这可能是插入排序或者希尔排序，因为这些排序方法在某些情况下的中间状态可能会出现逆序对。 这些知识点覆盖了数据结构（如栈、队列、二叉树、B树、堆）、图论（无向连通图的特性）以及算法（排序）。对于准备计算机专业考研的学生来说，理解和掌握这些内容至关重要。