2013考研计算机统考408真题解析

"2013年考研计算机统考408真题包含了计算机科学与技术专业研究生入学考试的多项选择题，涵盖了数据结构、算法、操作系统、计算机网络等多个基础知识点。" 1. 题目涉及到链表操作的时间复杂度问题。在合并两个已排序的链表时，最坏的情况是每次都需要比较两个链表的头节点，直到其中一个链表为空，因此时间复杂度是O(m+n)，答案是D。 2. 栈的特性是后进先出（LIFO）。如果入栈序列为1到n，而出栈序列中p2等于3，说明3是在2之前出栈的，但3之后的元素可能在2之前或之后出栈，所以p3可能的取值范围是除了2和3之外的所有数字，即n-2个，答案是B。 3. 平衡二叉树是一种特殊的二叉树，每个节点的左右子树高度差不超过1。在给定的关键字序列1到7中，插入过程可能导致平衡因子为0的分支节点有3个：根节点、插入5和6后形成的平衡节点。答案是D。 4. 在二叉树中，带权外部路径长度是指树中所有叶节点的权值乘以其到根节点的路径长度之和。为了使带权外部路径长度最小，应尽可能让权重小的节点靠左。题目中6个叶结点的权分别是2,3,4,5,6,7，最优化的情况下，最小带权外部路径长度为2+3+4+5+6+7=27，答案是A。 5. 后序线索二叉树是一种支持后序遍历的二叉树，右线索指向后序遍历的下一个节点。如果叶节点X有左兄弟Y，根据后序线索的定义，X的右线索应指向以Y为根的子树的最左下结点，答案是B。 6. 删除非叶节点和叶节点会影响二叉排序树的结构。如果v是叶节点，删除后再插入，树结构不变，所以II正确；如果v不是叶节点，删除后再插入可能导致结构变化，III正确。答案是C。 7. 图的邻接矩阵展示了顶点之间的连接关系，计算度就是统计每行或每列非零元素的数量。根据给出的矩阵，顶点的度分别是2,4,2,2，答案是B。 8. 广度优先遍历（BFS）是从根节点开始，逐层访问所有节点。给定的无向图和遍历序列，B选项不是按照BFS顺序，因为e应在a之前访问。答案是B。 9. 在AOE网（Activity On Edge，边表示活动）中，关键路径决定了工程的最短工期。若要缩短工期，需加快关键活动的进度。根据图中边的依赖关系，c和e是关键路径的一部分，加快它们的进度可缩短工期，答案是A。 10. 5阶B树的高度为2，意味着每个节点最多有5个子节点，最少有2个。在高度为2的5阶B树中，关键字的个数最少情况是根节点包含2个关键字，每个子节点也包含2个关键字，因此总共至少包含5个关键字。 这些题目覆盖了数据结构（链表、二叉树、图）、算法（排序、遍历）以及计算机系统的基础概念，是计算机科学学习的重要组成部分。对于准备考研的学生来说，理解和掌握这些知识点至关重要。