2020考研计算机408真题解析：基础综合与算法要点回顾

本资源是一份针对2020年全国硕士研究生招生考试计算机科学与技术学科联考的真题试卷，涵盖了计算机学科专业基础综合的知识点。以下是部分题目解析： 1. 关于矩阵存储：第1题考查了矩阵对角线存储的索引计算。一个10x10对称矩阵的上三角部分，由于对称性，只需存储下三角。按照列优先顺序，对于第7行（行号i=7），元素m7,2位于对角线上，因为是下三角，所以其下标j=2+（7-2）=6。由于数组是从0开始计数的，所以m7,2在N中的下标是15（0-based indexing）。 2. 栈操作题：第2题测试了栈的基本操作。入栈序列a, b, c, d, e经过一系列Push和Pop操作后，最后剩余的元素是b和d。因为每次Pop操作都会移除栈顶元素，所以出栈序列是b（第一次Pop），a（第二次Pop），c（第三次Push但随后被下一个Pop移除），d（第三次Push并保持在栈顶），最后两次Push覆盖了前面的元素，因此出栈序列是b, a, d。 3. 二叉树存储：第3题涉及二叉树的存储空间需求。对于一棵高度为5且有10个节点的二叉树，即使是最小的形态（完全二叉树），除了最后一个层次可能不满外，其他层次都是满的。这样，前4层会有4×2^(4-1) = 16个节点，第五层有10 - 16 = -6个节点（实际不可能，这里考虑的是最坏情况）。所以，总共的存储单元数量至少是16个节点（不包括根节点）。 4. 森林与二叉树遍历：第4题涉及二叉树的遍历顺序。给定森林F的先根和后根遍历序列，后根遍历是倒序的先根遍历，所以对应二叉树T的后序遍历序列应该是先根遍历的反序，即f, e, d, c, b, a。 5. 二叉排序树构建：第5题要求选择不能生成特定二叉排序树的输入序列。选项C中，4, 2, 5, 3, 1的排序不符合二叉排序树的性质，因为5应该在2和4之间，形成左子树，而不是在3之前。 6. 图的深度优先搜索：第6题提到修改深度优先搜索算法，确保访问所有顶点后立即退出递归。这种情况下，由于DFS保证了顶点的深度优先访问，如果遍历了所有顶点，那么输出的序列就是拓扑排序的前缀，因为拓扑排序正是由深度优先搜索产生的。 7. 最小生成树算法：第7题展示了克鲁斯卡尔算法的应用。根据图G的结构，应该首先添加边(b, f)，然后(b, d)，接着(a, e)，之后(c, e)，最后连接孤立的顶点(b, e)。 8. 最后几个问题涉及图的搜索算法（DFS和最小生成树）、二叉树遍历以及图的特殊性质等，这些知识点展示了计算机科学的基础理论在实际问题中的应用。 总结来说，这份试卷涵盖了数据结构（矩阵存储、栈、二叉树、排序）、算法（DFS、拓扑排序、最小生成树算法）、以及图形理论等多个方面的内容，适合考研考生复习计算机基础和算法知识。