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

"408计算机综合2017年真题及答案，涵盖计算机科学与技术学科的基础知识，包括算法时间复杂度、栈、稀疏矩阵的存储、二叉树遍历、哈夫曼编码、图论、二叉查找树、排序算法等核心概念。" 在2017年的408计算机综合考试中，试题涵盖了多个关键知识点，以下是这些知识点的详细解释： 1. 时间复杂度：题目中提到的`func`函数，通过分析可以得知该函数实现了一个累加的过程，直到`sum`大于等于`n`。每次循环，`sum`增加1，`i`增加1，因此时间复杂度是线性的，即O(n)。正确答案是C。 2. 栈的性质：栈是一种后进先出（LIFO）的数据结构，通常用于递归和函数调用。选项中，Ⅰ错误，因为非递归方式重写递归程序并不一定需要栈；Ⅱ正确，函数调用时确实会用到栈来保存状态；Ⅲ错误，栈的出栈次序取决于入栈次序，但并非唯一的；Ⅳ正确，栈是受限的线性表，允许在一端进行操作。所以答案是A。 3. 稀疏矩阵的存储：稀疏矩阵是指大部分元素为零的矩阵，适合使用三元组表或十字链表来压缩存储，减少空间开销。答案是A。 4. 先序与中序遍历相同的二叉树：如果一棵二叉树的先序和中序遍历结果相同，那么树的形状必须是每个非叶子节点只有右子节点，因为先序遍历根-左-右，中序遍历左-根-右，所以根节点的左子树为空。答案是B。 5. 二叉树的后序遍历：根据后序遍历的规律，结点a的后继结点是与其在同一层的最左边的结点，所以结点a同层的结点是c。答案是A。 6. 哈夫曼编码的译码：哈夫曼编码是一种最优前缀编码，根据编码规则解码，得出的字符序列是C. afbeagd。 7. 无向图的顶点数：根据握手定理，度数之和等于边数的两倍。已知总边数为16，度为4的顶点有3个，贡献12条边，度为3的顶点有4个，贡献12条边，剩余边数为2，至少需要2个度为2的顶点。所以顶点总数至少是3 + 4 + 2 = 9，但题目中提到其他顶点的度均小于3，所以至少还需要一个度为1的顶点，使得总边数达到16。因此，顶点数至少是11。答案是B。 8. 折半查找判定树：折半查找判定树的形状类似于完全二叉树，因此可能的二叉树形状应该接近完全二叉树。具体形状无法给出，但需要具备这个特征。 9. B+树的应用：B+树是一种适合大量数据存储和查找的数据结构，常用于数据库索引。B. 关系数据库系统中的索引是正确选项。 10. 归并排序与插入排序：归并排序的时间复杂度为O(n log n)，插入排序在最坏情况下为O(n^2)。选择归并排序可能是由于其效率更高，而非代码长度或空间占用。答案是B。 11. 排序方法：对于内部排序，选择归并排序而不是插入排序可能是因为归并排序的稳定性（保持相等元素的相对顺序不变）和更高效的平均性能。在顺序存储结构上，插入排序可能会导致大量的元素移动，而归并排序则避免了这个问题。答案是B。 以上是对2017年408计算机综合试题部分知识点的详细解释，这些知识点体现了计算机科学与技术基础的重要概念。