2009年考研计算机数据结构真题解析及答案

本文档包含了计算机数据结构方面的考研真题及其部分答案，涵盖了数据结构基础理论和实际应用。以下是部分题目解析： 1. 问题涉及了计算机系统中的数据流管理，通过设置打印数据缓冲区来解决速度不匹配问题。这里提到的逻辑结构应当是栈，因为栈的特点是后进先出（LIFO），符合主机写入、打印机读取的顺序需求。 2. 栈S中元素的进出顺序是先进后出，而行列Q遵循先进先出（FIFO）。根据题目描述，abcdefg出栈后按bdcfeag顺序进入行列Q，意味着至少要有三个元素能够存放b、d和c，因为它们是最先出栈的，因此栈S的容量至少是3。 3. 题目中给出的二叉树遍历结点序列是3, 1, 7, 5, 6, 2, 4，结合二叉树的遍历方式（前序、中序、后序），LRN表示从左子树开始，然后根节点，最后右子树，这对应的是中序遍历，所以答案是B。 4. 问题询问的是满足均衡二叉树定义的二叉排序树。均衡二叉树的特点是左右子树的高度差不超过1，从图中判断，没有给出具体的树形结构，但了解这一概念后，考生需要分析哪些选项中的二叉树符合这个特性。 5. 完好二叉树的叶子结点在第6层有8个，根据完全二叉树性质，叶子结点总是集中在最后一层，且从左向右均匀分布。第6层有8个叶子，说明第5层叶子结点可能是最大，假设第5层也是满的，那么叶子结点总数最多。对于任意完全二叉树，如果第k层有2^k个节点，那么结点个数最多是2^(k+1)-1。所以，第5层有2^5=32个，加上第6层的8个，共40个，加上根节点，总数最多是41，选项中不符合的是A、B和C。 6. 在二叉树与丛林的关系中，如果二叉树中的某个结点没有父结点，那么在丛林中，这表明该结点可能是多个结点的祖先，即可能有u和v的父结点是兄弟关系，或者u是v的祖先（包括u就是v的情况），选项I和II都正确。 7. 问题涉及到m阶B树的定义，m阶B树的规则包括根节点最多有m棵子树、所有叶结点都在同一层、各结点内关键字升序或降序排列以及叶结点间通过指针链接。选项中不切合要求的是C，因为B树的平衡性要求子树内部的关键字有序，但不一定要求递增或递减。 8. 小根堆是一种特殊的完全二叉树，插入一个新元素后，需要进行堆调整以保持堆的性质。在给定的小根堆中，插入3后，首先会将3放在堆顶，然后依次比较与较大孩子的大小，最终调整后的堆应该是最小堆，因此调整后的堆是A。 9. 最后一个问题考查的是排序算法的特征。给出的序列是排序后的结果，观察相邻元素的变化，可以看出第一趟排序后，11和12之间有交换，符合插入排序的特点，因为插入排序在每轮中将元素插入到已排序的部分，直到达到有序。所以答案是B。 至于最短路径算法，题目中描述的是Dijkstra算法的步骤，该方法确实可以求得最短路径，因为它通过逐步添加距离当前极点最近的未访问点，直至达到目标极点，保证了每一步都是当前最优解。