2017年计算机统考408试题解析：栈、矩阵压缩存储与二叉树

本文是关于2017年计算机统考408试题的部分内容，包含多项选择题，涉及数据结构、算法复杂度分析、栈、矩阵存储、二叉树遍历等多个计算机科学基础知识点。 1. 函数的时间复杂度分析： 题目中给出的函数`func(int n)`是一个求累加和的循环，它通过迭代找到使`sum >= n`的最小`i`值。每次迭代，`sum`增加`i`，因此时间复杂度随着`n`的增大而线性增长，选项C正确，时间复杂度是O(n)。 2. 栈的性质与应用： 栈是一种后进先出（LIFO）的数据结构。Ⅰ选项错误，非递归方式重写递归程序不一定必须使用栈，但通常会用到；Ⅱ选项正确，函数调用时确实需要栈来保存返回地址和局部变量等信息；Ⅲ选项错误，栈的出栈顺序取决于入栈顺序，但不是唯一决定因素；Ⅳ选项错误，栈是只允许在一端（栈顶）进行插入和删除的线性表。因此，错误的选项是B（仅I、Ⅱ、Ⅲ）。 3. 稀疏矩阵的存储结构： 稀疏矩阵是指非零元素很少的矩阵，通常使用三元组表（每个非零元素存储行号、列号和值）和十字链表（存储行和列的位置以及指向相邻非零元素的链接）来压缩存储，选项A正确。 4. 先序与中序序列相同的二叉树： 在二叉树的先序遍历和中序遍历中，如果两者相同，意味着树的所有非叶节点都没有左孩子，即它们只有右子树，选项B正确。 5. 二叉树的层次遍历： 后序序列为e,a,c,b,d,g,f，说明a是根节点，其同层结点是其父节点的兄弟节点，因此与a同层的是其父节点的兄弟节点，没有直接给出父节点，但可以推断a的同层结点可能是d，因为b、c是a的子节点，而e是a的父节点，g和f分别是d的子节点，所以选项B正确。 6. 哈夫曼编码的译码： 根据哈夫曼编码，可以逐位解码得到对应的字符，编码序列0100011001001011110101对应的是字符acgabfh，选项A正确。 7. 无向图的顶点数量： 由图论的握手定理，所有顶点的度数之和等于边数的两倍。设图G的顶点个数为n，度为4的顶点贡献为12，度为3的顶点贡献为12，其他顶点的度小于3，至少为2，因此最小顶点数n=3+4+2=9，但题目中还有一条边未被计算，所以n至少为10，选项A正确。 8. 折半查找判定树： 折半查找判定树是一棵完全二叉树，选项中的图需要是完全二叉树形式才可能成为折半查找判定树，但具体哪个是，题目中没有提供足够的信息来判断。 9. B+树的应用场景： B+树是一种适合大量数据检索的数据结构，常用于数据库索引，选项B正确。 10. 归并排序与插入排序的选择： 归并排序相比插入排序在处理大数据量时效率更高，因为归并排序的时间复杂度为O(n log n)，而插入排序在最坏情况下是O(n^2)，因此在处理大数据时，归并排序可能是更好的选择，选项Ⅰ正确。 这些题目覆盖了计算机科学中的基本概念和原理，对于准备计算机科学相关考试的学生来说具有很高的参考价值。