2017计算机考研408真题（仅真题）无水印.pdf

### 重要知识点解析 #### 1. 时间复杂度分析 - **题目背景**: 在计算机科学领域，算法的时间复杂度是用来衡量算法执行效率的一个重要指标。本题考察的是一个典型的求解时间复杂度的问题。 - **题目解析**: - 给定函数 `func(int n)` 实现了一个累加的过程，通过不断累加整数直到累加和超过或等于n，返回此时累加到的整数个数。 - 函数的核心部分是`while(sum < n) sum += ++i;`，这是一个典型的求平方根问题的变体。该循环会在`sum`小于`n`的情况下持续增加`i`的值，直到`sum >= n`。 - 对于一个特定的`n`，循环的次数取决于`n`的大小，大约是`sqrt(2*n)`左右，因此该函数的时间复杂度是`O(sqrt(n))`，即选项**B**。 #### 2. 栈的基本概念 - **题目背景**: 栈是一种特殊的线性数据结构，只允许在一端进行插入和删除操作。 - **题目解析**: - **Ⅰ** 选项认为“采用非递归方式重写递归程序时必须使用栈”是错误的，因为非递归转换不一定需要栈，也可以使用循环和其他数据结构实现。 - **Ⅱ** 选项指出“函数调用时，系统要用栈保存必要的信息”，这是正确的，因为在函数调用时确实需要使用栈来保存函数的局部变量、参数和返回地址等信息。 - **Ⅲ** 选项表示“只要确定了入栈次序，即可确定出栈次序”，这个说法是错误的，因为栈遵循的是“后进先出”（LIFO）原则，即使知道了入栈次序，也不能唯一确定出栈次序。 - **Ⅳ** 选项提到“栈是一种受限的线性表，允许在其两端进行操作”，这是不准确的，因为栈实际上只允许在一端进行插入和删除操作。 - 因此，根据以上分析，错误的说法包括**Ⅰ**、**Ⅲ** 和 **Ⅳ**，选项**C** 是正确的。 #### 3. 稀疏矩阵的存储结构 - **题目背景**: 稀疏矩阵是指绝大多数元素为零的矩阵，为了节省存储空间，通常会使用特殊的数据结构来存储稀疏矩阵。 - **题目解析**: - **三元组表**可以用来存储稀疏矩阵，它是由行号、列号和非零元素值组成的三元组构成的列表。 - **十字链表**也是一种常用的稀疏矩阵存储方式，它结合了链表的特点，能够高效地存储和访问稀疏矩阵的非零元素。 - 因此，选项**A**是正确的。 #### 4. 二叉树的遍历顺序 - **题目背景**: 二叉树的遍历顺序包括先序、中序和后序三种。 - **题目解析**: - 如果一棵非空二叉树的先序序列与中序序列相同，那么这棵树的每个非叶子节点都只能有一个孩子节点，即**只有右子树**。这是因为先序遍历的顺序是“根-左-右”，而中序遍历的顺序是“左-根-右”。当这两个序列相同时，意味着没有左子树的存在。 - 所以正确答案是**B**。 #### 5. 二叉树层次遍历 - **题目背景**: 本题考查二叉树的层次遍历。 - **题目解析**: - 通过给定的后序遍历序列可以推断出二叉树的大致结构。 - 要确定与结点a同层的结点，首先需要了解二叉树的结构。根据题目描述的后序序列和树形图，结点a的同层结点是结点**d**。 - 因此，正确答案是**B**。 #### 6. 哈夫曼编码的译码 - **题目背景**: 哈夫曼编码是一种基于频率的前缀编码方法，广泛应用于数据压缩领域。 - **题目解析**: - 根据题目中给出的哈夫曼编码规则，可以将编码序列“0100011001001011110101”逐个字符翻译。 - 解码后的结果是“a f e e f g d”，因此正确答案是**D**。 #### 7. 图的顶点数量 - **题目背景**: 本题考查图论中的基本概念。 - **题目解析**: - 已知图中有16条边，且图中含有3个度为4的顶点和4个度为3的顶点。 - 使用握手定理计算顶点数量。握手定理指出，所有顶点的度数之和等于边的数量的两倍。 - 设未知顶点数量为`x`，则有\(3 \times 4 + 4 \times 3 + x \times 2 = 2 \times 16\)，解得\(x = 4\)。 - 因此，图G所含的顶点个数至少是\(3 + 4 + 4 = 11\)个，所以正确答案是**B**。 #### 8. 折半查找判定树 - **题目背景**: 折半查找也称作二分查找，是一种在有序数组中查找特定元素的高效算法。 - **题目解析**: - 折半查找判定树是一种特殊的二叉搜索树，其中每一个结点代表数组中的一个元素。 - 题目未给出具体选项，但折半查找判定树的特点是每个结点都有两个孩子结点，左子结点的值小于当前结点，右子结点的值大于当前结点。 - 因此，正确的折半查找判定树应该是一棵完全二叉树或接近完全二叉树的结构。 #### 9. B+树的应用 - **题目背景**: B+树是一种自平衡的树数据结构，常用于数据库索引和文件系统中。 - **题目解析**: - **A** 选项，“编译器中的词法分析”通常不会使用B+树，而是使用状态机或其他数据结构。 - **B** 选项，“关系数据库系统中的索引”经常使用B+树来提高查找效率，因为B+树能够有效地支持范围查询。 - **C** 选项，“网络中的路由表快速查找”一般使用专门的数据结构如Trie树等。 - **D** 选项，“操作系统的磁盘空闲块管理”通常使用链表或其他简单的数据结构。 - 因此，正确答案是**B**。 #### 10. 内部排序算法的选择 - **题目背景**: 排序算法的选择依据是数据规模、数据特点以及对时间和空间的要求。 - **题目解析**: - 归并排序的时间复杂度稳定为O(n log n)，占用的空间较多。 - 插入排序的时间复杂度最好情况下为O(n)，最坏情况下为O(n^2)，但占用的空间较少。 - 当数据量较大时，归并排序通常比插入排序更为高效。 - 因此，选择归并排序而不是插入排序的原因是归并排序的运行效率更高，选项**B**是正确的。 #### 11. 排序算法的时间效率 - **题目背景**: 排序算法的时间效率受到存储结构的影响。 - **题目解析**: - **插入排序**在链式存储结构下效率不变，仍然保持O(n^2)。 - **选择排序**在链式存储结构下效率降低，因为需要多次遍历来找到最小元素，每次遍历都需要从头到尾扫描整个链表，效率下降到O(n^2)。 - **起泡排序**在链式存储结构下效率也降低，因为它需要多次交换元素的位置。 - **希尔排序**和**堆排序**在链式存储结构下效率变化不大。 - 因此，正确答案是**B**。 #### 12. 计算机性能评估 - **题目背景**: 计算机性能评估是计算机体系结构的重要组成部分。 - **题目解析**: - **CPⅠ**（Clock Cycles Per Instruction）是指执行一条指令所需的时钟周期数。 - 计算机M1和M2上的程序P的运行时间比可以通过计算公式得到：\(\frac{T_{M1}}{T_{M2}} = \frac{CPⅠ_{M1} \cdot Clock_{M1}}{CPⅠ_{M2} \cdot Clock_{M2}} = \frac{2 \cdot 1.5}{1 \cdot 1.2} = 2.5\)。 - 因此，正确答案是**D**。 #### 13. 主存寻址 - **题目背景**: 主存寻址涉及到计算机硬件结构中的主存组织方式。 - **题目解析**: - 根据题目描述，主存每次最多读写32位数据。 - 变量x的地址为804 001AH，由于主存按字节编址，双精度变量x占用8个字节，即跨越两个32位边界。 - 因此，读取x需要两次存储周期，选项**B**是正确的。 #### 14. 存储局部性 - **题目背景**: 存储局部性是指程序访问存储器时倾向于重复访问某些区域的特性。 - **题目解析**: - 在给定的程序段中，数组a的访问模式既有时间局部性也有空间局部性。 - 时间局部性体现在数组a的元素被重复访问。 - 空间局部性体现在数组a的元素是连续访问的。 - 因此，正确答案是**A**。 #### 15. 寻址方式 - **题目背景**: 寻址方式决定了处理器如何计算有效地址。 - **题目解析**: - **变址寻址**是适合按顺序访问数组元素的方式之一。 - 在变址寻址方式下，处理器使用基址寄存器加上偏移量来计算有效地址，非常适合按照一定的步长访问数组元素。 - 因此，正确答案是**D**。 #### 16. 指令格式设计 - **题目背景**: 指令格式设计涉及计算机体系结构中的指令集设计。 - **题目解析**: - 指令字长至少应包含足够的位来表示所有的指令类型和地址字段。 - 三地址指令需要3个6位地址字段和指令操作码，二地址指令同样需要2个6位地址字段和指令操作码。 - 为了表示29种三地址指令和107种二地址指令，操作码至少需要8位。 - 因此，指令字长至少应该是\(8 + 3 \times 6 = 26\)位，选项**B**是正确的。