2017考研计算机408真题解析：时间复杂度、栈与树结构等关键知识点

2017年考研计算机统考408真题涉及了多项知识点，包括算法复杂度分析、数据结构、图论、哈夫曼编码、二叉树、搜索算法、数据库索引和排序算法等。以下是对部分题目详解： 1. 题目考查算法时间复杂度：函数`func`的时间复杂度是O(n)，因为循环条件是`sum<n`，随着n的增长，循环体内的操作执行次数会线性增加。正确答案是C。 2. 本题考查栈的应用：I错误，非递归方式重写递归程序并不一定需要栈，可以使用其他数据结构如队列；II正确，函数调用时确实需要栈来保存局部变量和返回地址；III错误，栈的出栈次序通常与入栈次序相反，但不是绝对的；IV正确，栈是一种后进先出（LIFO）的数据结构。答案是B。 3. 压缩存储稀疏矩阵通常使用三元组表（表示非零元素及其位置）和邻接矩阵（对于稀疏矩阵，大部分元素为0，用0填充节省空间），正确答案是B。 4. 为了使二叉树的先序序列与中序序列相同，说明这是一棵完全二叉树，且所有非叶节点都只有一个子节点。因此，正确答案是A。 5. 根据后序遍历(e, a, c, b, d, g, f)以及给出的树形结构，可以看出a的父节点可能是f或g，由于后序遍历中c和b在a之后，所以a不可能比c和b高，只能在g的同一层。答案是C。 6. 哈夫曼编码中，通过编码的长度来确定字符，10101解码后对应最短的编码为0100（a）、01（b）、0000（h）和0101（e）。将它们连接起来得到的结果是abeiha，选项B正确。 7. 图G中，度为4的顶点有3个，度为3的有4个，剩余顶点度数小于3。根据握手定理，所有顶点度数之和等于边数的两倍。设总顶点数为n，则4×3 + 3×4 + (n-3-4) < 2×16，解得n > 11。因为度数为4和3的顶点数量之和已超过16的一半，加上其他顶点，最少需要11个顶点。答案是B。 8. 折半查找判定树要求树是平衡的，排除A和C，因为它们不是完全二叉树；B项是完全二叉树，而D项虽然形状像折半查找树，但存在左孩子的结点度数大于2的情况，不满足条件。因此，可能成为折半查找判定树的是B。 9. B+树常用于数据库系统中的索引，因为它能高效地处理大量数据，并支持范围查询。答案是B。 10. 归并排序相对于插入排序的优点在于运行效率更高，尤其是在大数据量的情况下，归并排序的平均和最坏情况时间复杂度都是O(n log n)，而插入排序在最坏情况下是O(n^2)。所以，如果选择了归并排序，可能的理由是III。答案是B。 以上就是2017年考研计算机统考408真题中部分知识点的解析。