2017考研计算机408真题解析与复习指南

"2017年考研计算机408真题讲义，包含了计算机科学与技术学科联考的计算机学科专业基础综合试题，包括单项选择题，涉及数据结构、算法复杂度、栈、二叉树、哈夫曼编码、图论、数据库索引等知识点。" 这份讲义主要涵盖了计算机科学的基础知识，对于准备考研408科目的考生来说是非常有价值的复习资料。下面将详细解析部分题目涉及的知识点： 1. 题目涉及的时间复杂度分析，这是算法效率评估的重要指标。在给定的代码中，`while`循环的终止条件是`sum >= n`，每次循环`sum`增加1，因此循环次数大约是`n`，所以时间复杂度是O(n)。 2. 栈的相关知识，栈是一种后进先出（LIFO）的数据结构，常用于函数调用、递归等场景。题目中提到的错误观点是栈只能通过递归使用、确定入栈次序即可确定出栈次序以及栈可以两端操作，正确的理解是栈是一种受限的线性表，通常只允许在一端（栈顶）进行操作。 3. 存储稀疏矩阵的方法，稀疏矩阵是指大量元素为0的矩阵，为了节省存储空间，通常采用三元组表和十字链表，而不是邻接矩阵，因为邻接矩阵会浪费大量空间存储0。 4. 二叉树的性质，如果一个非空二叉树的先序遍历和中序遍历相同，那么该树的所有非叶节点必须只有一个孩子，即要么只有左子树，要么只有右子树。题目中提到的条件是结点的度均为1，这将确保先序和中序遍历结果相同。 5. 二叉树的后序遍历，根据后序遍历序列，可以推断出树的结构。结点a的后序遍历在结点d之后，说明a在d的上一层，因此与a同层的结点是c。 6. 哈夫曼编码的解码，哈夫曼编码是一种最优前缀编码，通过编码序列可以还原原始数据。根据给定的哈夫曼编码和编码序列，可以得出解码结果是`afeefgd`。 7. 图论中的顶点度数问题，无向图的边数等于所有顶点度数之和的一半。根据题目中给出的度数分布，可以计算出至少有多少个顶点。 8. 折半查找判定树是二叉搜索树的一种特殊情况，题目要求判断哪个二叉树可能是折半查找判定树。 9. B+树是一种适用于数据库索引的高效数据结构，它支持快速的范围查询和顺序访问。题目中适合使用B+树的是关系数据库系统中的索引。 10. 插入排序和归并排序都是内部排序算法，归并排序的平均和最坏情况时间复杂度都是O(n log n)，而插入排序在最坏情况下是O(n^2)，因此在数据量大或无序程度高的情况下，选择归并排序更优。 以上是讲义中部分内容的解析，这些知识点覆盖了计算机科学的基础领域，对于准备考研的考生来说，理解和掌握这些内容是至关重要的。