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

"这是一份2013年考研计算机统考408科目的真题试卷，包含了多项选择题，涉及数据结构、算法、计算机组成原理、操作系统等多个方面的知识点。" 1. **链表合并**：题目提到将两个升序链表合并成一个降序链表，最坏情况下的时间复杂度是O(max(m, n))，这意味着在合并过程中，我们需要遍历两个链表的所有元素，以确保合并后的顺序。 2. **栈的性质**：栈是一种后进先出（LIFO）的数据结构。如果p2=3，表示出栈的第二个元素是3，那么p3可能是除了1和3之外的任意一个在栈内的元素，因此它的可能取值个数为n-2。 3. **平衡二叉树**：平衡二叉树是一种左右子树高度差不超过1的二叉搜索树。当插入关键字时，如果保持平衡，平衡因子为0的分支结点个数会增加。题目中7个节点插入后，有3个平衡因子为0的结点。 4. **带权路径长度**：在二叉树中，带权路径长度是指所有叶结点的权值与其路径长度之积的总和。题目要求最小带权路径长度，可以通过调整树形结构达到最小化。 5. **后序线索二叉树**：后序线索二叉树用于帮助进行后序遍历。如果X是叶结点，且存在左兄弟Y，X的右线索指向以Y为根的子树的最左下结点。 6. **二叉排序树操作**：在二叉排序树中，删除叶结点后插入同结点不会改变树的结构，但删除非叶结点后插入可能会改变结构。 7. **图的邻接矩阵**：邻接矩阵用于表示图中顶点之间的连接关系。度表示一个顶点的边数，题目中给出的矩阵对应的度依次为2, 2, 1, 1。 8. **广度优先遍历**：广度优先遍历（BFS）从起点开始，按层次访问所有节点。选项中，d和c之间没有边，因此d不能在c之前，所以d,b,c,a,h,e,f,g不是正确的遍历序列。 9. **AOE网与关键路径**：关键路径是决定项目最短完成时间的路径。在AOE网中，加快某些活动可以缩短工期，例如c和e，因为它们都在关键路径上。 10. **B树性质**：5阶B树的每个结点最多有5个孩子，至少有2个孩子。高度为2的5阶B树中，最少包含的关键字个数是5个（一个满结点和一个有两个孩子的结点）。 11. **基数排序**：基数排序是一种非比较型整数排序算法，根据数字的位数从低位到高位进行分配和收集。第2趟分配收集后，关键字序列应保持按中间位的大小排序。 以上是根据题目内容解析的相关知识点，涵盖了数据结构、算法和图论等多个计算机科学的基础概念。