2017年计算机408考研统考真题详解：时间复杂度与数据结构

2017年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题涵盖了计算机基础知识和算法理解等多个方面。以下是从部分题目中提炼出的知识点： 1. 时间复杂度分析：题目1询问一个函数的时间复杂度，其中提到的`fun6`函数通过循环累加`i`直到`sum`达到`n`，这表明时间复杂度与`n`的大小直接相关，因此函数的时间复杂度为`O(n)`，因为循环执行次数与`n`成正比。 2. 栈和递归：题目2涉及栈的概念，选项指出错误的说法。选项I认为非递归方式重写递归程序必须使用栈，这是正确的，因为非递归程序通常通过递归调用的堆栈来实现控制流程。选项II正确地阐述了函数调用时系统使用栈保存信息，如局部变量和返回地址。选项III错误，因为栈的入栈和出栈次序并非总是按照特定顺序，而是依赖于程序逻辑。选项IV描述了栈的基本特性，允许在一端添加和删除元素，但并不意味着确定入栈次序就能确定出栈次序，所以III是错误的。 3. 稀疏矩阵压缩存储：题目3讨论了适合压缩存储稀疏矩阵的数据结构。选项A中的三元组表和十字链表是常用的稀疏矩阵存储方法，因为它们能有效地节省空间，只存储非零元素及其索引，而邻接矩阵会浪费大量空间。因此，正确答案是A。 4. 二叉树性质：题目4关注二叉树的先序和中序遍历，要使得先序序列与中序序列相同，这意味着树应该是完全二叉树且每个节点的左右子树高度差不超过1，这样非叶子节点的左子树必然为空或恰好有一个节点，选项D符合这个条件。 5. B+树的应用：题目中没有直接给出答案，但提及B+树，这是一种平衡查找树，常用于数据库系统中，特别是磁盘存储优化，因为它能够减少磁盘I/O次数。选项B的关系数据库系统就是适合使用B+树的场景，因为B+树支持范围查询，适合大型数据存储和检索。 2017年计算机408统考真题涵盖了数据结构、算法复杂度分析、栈与递归、稀疏矩阵存储以及数据库索引结构等知识点，测试了考生对计算机基础理论的理解和应用能力。