2013年计算机考研真题解析：数据结构与算法专项

"计算机考研真题，包括多项选择题，涉及数据结构、算法、计算机组成原理、操作系统等多个计算机科学核心领域。" 计算机考研真题涵盖了计算机科学与技术学科的基础知识，这些题目旨在测试考生对计算机专业知识的理解和应用能力。以下是部分题目解析及相关知识点： 1. 题目讨论了两个升序链表合并为降序链表的时间复杂度问题。在最坏情况下，需要比较所有元素，因此时间复杂度为O(m+n)。 2. 栈的特性决定了出栈序列，本题考察栈的性质和操作。由于2是第一个出栈的元素，且p=2，所以3的出栈位置不确定，可能在2之后的任何位置，答案为B，2*(n-1)种可能性。 3. 平衡二叉树是高度平衡的二叉搜索树，每个结点的左右子树高度差不超过1。题目中提到的是平衡因子为0的结点，这意味着这些结点的左右子树高度相等。在初始插入过程中，最坏情况下所有结点都是右孩子，因此平衡因子为0的结点个数为1。 4. 权值最小的三叉树问题涉及树的优化。要使带权路径长度最小，应该尽可能地将权重较小的叶子结点放在较低层次，答案是C，54。 5. 后序线索二叉树用于方便后序遍历。如果叶结点X有左兄弟结点Y，X的右线索应指向以Y为根的子树的最左下结点，以便于后序遍历。 6. 二叉排序树删除和插入操作考察树的性质。如果v是叶结点，删除后重新插入会保持相同的结构；如果不是叶结点，结构可能会改变。所以正确的选项是B，仅I、IV。 7. 图的邻接矩阵表示边的存在。计算度数时，每行或每列的和代表一个顶点的度。根据矩阵，顶点的度依次是2，2，1，2，所以答案是B，2，2，1，1。 8. 广度优先遍历（BFS）按照从起点出发的层次顺序访问所有节点。D选项违反了BFS的原则，因为相邻的节点d和h没有按照先访问h再访问d的顺序遍历。 9. 有向无环图（DAG）的活动最早开始时间（AES）和最晚开始时间（LES）的计算可以用来优化项目进度。加快活动进度意味着缩短关键路径，从而缩短整个项目的工期。 这些题目涉及到的数据结构包括链表、栈、树（二叉树、平衡二叉树、线索二叉树、三叉树），图的遍历方法（广度优先搜索），以及算法（排序、查找）。这些知识点是计算机科学基础教育的重要组成部分，也是研究生入学考试的常见考点。