2017年计算机考研真题详解及答案深度解析

2017年计算机考研真题及答案完整版提供了当年全国硕士研究生招生考试计算机科学与技术学科联考的计算机学科专业基础综合试题。这份试题涵盖了多个关键知识点，包括时间复杂度分析、数据结构（如栈和哈夫曼编码）、图论（无向图的度数计算）、数据结构设计（折半查找判定树和B+树的应用）、以及排序算法的比较（归并排序与插入排序的选择）。以下是对部分试题的详细解析： 1. 题目1考查了函数的时间复杂度，涉及的是常见复杂度分析的基本概念。选项C（O(n)）最符合题目要求，因为while循环会一直执行直到sum达到n，所以循环次数是线性的。 2. 在栈的叙述中，Ⅰ错误，非递归方式重写递归程序时，虽然也需要使用栈来保存局部变量和递归调用的状态，但并不是必须的；Ⅱ正确，函数调用时，系统确实使用栈来保存调用堆栈信息；Ⅲ错误，入栈和出栈次序不一定能通过简单的入栈次序确定，取决于具体实现；Ⅳ正确，栈是一种后进先出（LIFO）的数据结构，允许在两端进行操作。因此，答案是B，只包含Ⅰ、Ⅲ、Ⅳ。 3. 压缩存储稀疏矩阵的两种有效方法是三元组表（用于存储非零元素及其坐标）和十字链表（节省空间，只存储非零元素），答案是A。 4. 二叉树的先序序列与中序序列相同，意味着这是一棵完全二叉树，所有非叶节点的度为2，因为只有这样，它们的左右子树才能对应先序和中序的相同序列。答案是D。 5. 后序遍历的顺序揭示了节点的访问顺序，根据后序序列e, a, c, b, d, g, f，结点a在c、b、g之前，且f在g之后，可推断a位于g的左边，故树中与a同层的节点是C．f。 6. 哈夫曼编码是为每个字符分配的最优二进制编码，通过前缀编码的特性，我们可以逆向重建字符。根据编码，译码结果是afbeagd。 7. 图G的顶点度数分布为4个4度顶点，4个3度顶点，其余顶点度数小于3。为了保证图至少有16条边，每个4度顶点至少连接4个其他顶点，加上3度顶点至少需要4×4 + 4×3 = 28条边。剩下的8条边至少分布在两个3度顶点和剩余顶点上，考虑到3度顶点的最低要求，至少需要一个3度顶点连接2条边，这样图最少有11个顶点。答案是B。 8. 折半查找判定树要求二叉搜索树，排除了有外部节点的情况，所以需要平衡的二叉搜索树，答案可能是平衡的二叉搜索树或其变种。 9. B+树适合大量数据的存储和快速查找，例如在关系数据库系统中的索引，因为它的优点是减少磁盘I/O次数，答案是B。 10. 归并排序相对于插入排序，主要优势在于处理大规模数据时效率更高（运行效率）和稳定性，而选项Ⅰ的代码长度不是主要考虑因素，选项Ⅱ空间占用在归并排序中可能会增加。因此，答案是B，仅Ⅲ。 11. 排序方法的对比中，归并排序通常优于插入排序，尤其是在数据量较大时，因为归并排序的时间复杂度稳定在O(n log n)，而插入排序在最坏情况下时间复杂度为O(n^2)。因此，选择归并排序是因为其更高的运行效率，答案是B，仅Ⅲ。 以上是对部分试题知识点的详细解读，完整的试题和答案有助于考生复习和理解计算机考研中基础理论的部分。