2017考研计算机统考408真题与解析

"2017年计算机统考408真题包含了计算机科学与技术学科的基础知识，涉及数据结构、算法、操作系统、计算机组成原理等多个方面。试题以选择题形式出现，每题2分，共计80分。" 1. 时间复杂度是衡量算法执行效率的重要指标。题目中给出的`func`函数通过累加求和的方式找到满足`sum < n`条件的最小整数`i`，其时间复杂度为线性，即`O(n)`。选项C正确。这涉及到计算机科学中的大O符号表示法，用来描述算法的渐进行为。 2. 栈是一种后进先出（LIFO）的数据结构，常用于递归、函数调用等场景。选项分析： - Ⅰ：非递归方式重写递归程序时可以使用栈，但不是必须的，故错误； - Ⅱ：函数调用时确实需要栈来保存返回地址和局部变量，正确； - Ⅲ：栈的出栈顺序由入栈顺序决定，但并不唯一，例如相同的入栈顺序可以有不同的出栈方式，故错误； - Ⅳ：栈是一种受限的线性表，只允许在一端（栈顶）进行插入和删除操作，故错误。 因此，错误的选项是I、Ⅲ、Ⅳ，选项C正确。 3. 稀疏矩阵是指大部分元素为0的矩阵，为了节省存储空间，通常使用三元组表和十字链表这两种压缩存储结构。选项A正确。 4. 在二叉树中，如果先序序列与中序序列相同，那么该树必定是单支树，即除了叶子节点外，所有非叶节点都只有一个子节点。选项A表示只有左子树，B表示只有右子树，C表示度均为1，这三个选项都可能导致先序和中序序列相同；D表示度均为2，这会导致先序和中序序列不同，因为中序遍历会先访问左子树，所以D是错误选项。 5. 后序遍历的特点是：根节点位于左右子树遍历之后。根据题目中给出的后序序列，结点a是在b和c之后，因此与结点a同层的结点是c。选项A正确。 6. 哈夫曼编码是一种最优前缀编码，用于数据压缩。根据编码规则，解码序列0100011001001011110101对应的结果是`acgabfh`。选项A正确。 7. 在无向图中，边的数量是顶点数量的两倍减去顶点的度之和。题目中提到度为4的顶点有3个，贡献12条边；度为3的顶点有4个，贡献12条边。其他顶点的度均小于3，因此至少还有1个度为2的顶点，贡献2条边，使得总边数达到16。所以最少的顶点数量是3（度为4）+ 4（度为3）+ 1（度为2）= 8。但是，题目中还提到至少这个条件，这意味着可能有度为1的顶点存在，以减少边的数量。所以至少的顶点数量可能是9或10。根据选项，最少是10个顶点。选项B正确。 8. 折半查找判定树是一种特殊的二叉搜索树，其形状取决于待查关键字序列。题目中并未给出具体图形，无法直接判断。 9. B+树是一种适合大量数据检索的索引结构，尤其在数据库系统中广泛使用。选项B正确，关系数据库系统中的索引通常使用B+树实现。 10. 归并排序相比于插入排序，其主要优势在于对大规模数据的高效处理能力，尤其是在外部排序和数据量大的情况下。选项Ⅲ归并排序的运行效率更高，是选择归并排序而非插入排序的一个重要原因。其他选项如代码长度、空间占用并不是选择排序算法的主要考虑因素。