考研计算机真题解析：栈队列操作与二叉树问题

"2009年考研计算机专业基础综合真题及参考答案，涵盖计算机组成原理、数据结构、操作系统等多个领域。" 1. 缓冲区管理：计算机主机与打印机速度不匹配时，通常使用队列作为打印数据缓冲区。主机连续写入，打印机按顺序读取，体现了先进先出（FIFO）的原则，因此答案是B队列。 2. 栈与队列的应用：此题考察栈和队列的操作。元素入栈后再出栈进入队列，如果出队顺序是b，d，c，f，e，a，g，意味着元素出栈后并不立即出队，而是等待其他元素。c要在d之后出队，表明d在c之前入栈，即c不能立即出栈，需要至少两个空位（c和d），加上b已经出栈，所以栈的容量至少是3，答案C。 3. 二叉树遍历：根据给定的结点序列，可以推断出这是后序遍历（LRN），因为根节点在左右子树之后，答案是D。 4. 平衡二叉树：平衡二叉树是一种特殊的二叉搜索树，左右子树的高度差不超过1。图中，B选项的树左右子树高度差为1，符合平衡二叉树定义。 5. 完全二叉树的性质：第6层有8个叶结点，完全二叉树的节点总数计算公式为(2^(h+1)) - 1，其中h为高度。第六层高度为5，所以节点总数最多为(2^(6+1)) - 1 = 127 - 1 = 126，但题目问最多是多少，考虑根节点也为叶结点的情况，答案是C。 6. 森林转化为二叉树：森林转二叉树规则中，若u是v的祖父结点，则在原森林中，u和v可能是兄弟关系，或者u是v的父结点的父结点。答案B。 7. 无向连通图特性：无向图中所有顶点的度之和一定是边数的两倍，因为每条边连接两个顶点，贡献2度。所以度之和为偶数，I正确。连通图的边数至少等于顶点数减1，但不一定是大于，Ⅱ错误。无向图中可能存在度为0的顶点，III错误。答案是A。 8. B树定义：B树是一种自平衡的查找树，所有叶子节点都在同一层，根节点最多有m棵子树，各节点内的关键字升序或降序排列。叶节点之间通过指针链接是B+树的特性而不是B树，所以D不符合B树定义。 9. 小根堆：小根堆是所有节点的关键字都不大于其子节点的关键字的二叉堆。插入3后，需要调整以保持小根堆性质。根据选项，A选项符合小根堆性质，3成为新的最小值位于根位置。 10. 排序算法识别：根据第二趟排序后的结果，可以推断排序方法。如果序列11，12，13，7，8，9，23，4，5是第二趟的结果，这意味着第一趟结束后，11，12，13已经在正确位置，而7，8，9，23，4，5发生了变化，这符合插入排序的特点，每次将一个元素插入到已排序的部分，答案是B。 以上解析涵盖了计算机科学中的数据结构、算法、树形结构和排序等基本概念，这些都是计算机科学考研中的常见考点。