2009计算机考研真题详解：算法与数据结构

2009年计算机考研真题包含了一系列的计算机科学基础知识题目，涉及数据结构、操作系统、算法以及计算机组成原理等多个方面。以下是详细解析： 1. 数据结构题：第一个问题是关于计算机通信中的数据缓冲区设计，通常选择队列（B）来解决速度不匹配问题，因为队列遵循先进先出（FIFO）原则，适合按顺序处理任务。 2. 栈和队列：第二个问题是关于栈和队列的使用。根据题目描述，元素先入栈后入队，且出队顺序为bdcfeag，这意味着栈S必须能保留至少三个元素，即至少需要3个节点，因此答案是B.3。 3. 树的遍历：第三个问题是关于二叉树的遍历，给出的结点序列为3,1,7,5,6,2,4，对应的是前序遍历（NLR），即根节点-左子树-右子树。 4. 平衡二叉树：第四个选项要求选择满足平衡二叉树定义的二叉排序树，平衡二叉树的特点是左右子树高度差不超过1，所以在这四个选项中，C通常是平衡的，因为它是完全二叉树。 5. 完全二叉树：第五题考察完全二叉树的性质，根据第六层有8个叶节点，推算出满二叉树的最大节点数。对于完全二叉树，最后一层的叶节点都是满的，最左边的非叶节点距离叶子节点数量为层数-1，所以总节点数最多是(8+7+6+5+4+3+2+1)/2 = 111。 6. 森林与二叉树：第六题问在森林转化为二叉树的过程中，结点u和v的关系。选项I表示父子关系，II表示兄弟关系，III表示u和v的父节点可能是兄弟关系。由于二叉树中结点u是v的父结点的父结点，这在森林中可能意味着u和v要么是父子关系，要么他们的共同父节点是同一个，所以选项D包括了所有可能。 7. 连通图特性：第七题考察无向连通图的基本性质，正确的选项是I和II，所有顶点的度之和为偶数（因为每个边贡献了两个度）且边数大于等于顶点个数减一，保证图是连通的。 8. B树特性：第八题关于m阶B树，不符合定义要求的是叶节点都在同一层上，因为B树的叶子节点可以分布在多层。 9. 小根堆：第九题考查堆数据结构，插入关键字3后，由于3小于堆顶5，需要进行下沉操作，调整后的堆会保持小根堆性质，答案是B，因为调整后19将移动到末尾。 10. 排序算法：第十题是关于排序算法的识别，根据第二趟排序的结果，可以看到相邻元素的交换，这符合冒泡排序的特点，答案是A. 11. 冯·诺依曼计算机：最后一个问题，冯·诺依曼机区分指令和数据主要依据指令操作码，操作码决定了CPU如何执行操作，而数据则是指令作用的对象，两者在存储器中以二进制形式存在，但通过译码结果不同来区分。 这些题目覆盖了计算机科学的基础概念，包括数据结构（队列、栈、二叉树）、图论、操作系统（进程通信）、算法（排序、B树）、以及计算机组成原理（冯·诺依曼体系结构）。理解和掌握这些知识点对于准备考研的学生来说至关重要。