2012计算机考研模拟试题解析

"2012计算机考研模拟试题" 这篇资源主要涵盖了计算机专业考研的一些核心知识点，涉及了数据结构、算法、操作系统、计算机网络等多个领域。以下是相关知识点的详细解释： 1. **栈**：栈是一种后进先出（LIFO）的数据结构。问题中提到的栈的输入序列为123…n，输出序列的第一个元素是n，说明栈的弹出顺序是逆序的。因此，栈顶元素是最后入栈的n，要输出第i个元素，需要先弹出n-i+1个元素，所以答案是B.n-i+1。 2. **线性表**：线性表是最基础的数据结构之一，这里讨论的是在不同存储方式下的效率。题目指出最常用的操作是存取指定序号的元素和在末尾进行插入和删除，顺序表在这种场景下最高效，因为它可以直接通过下标访问元素，末尾插入和删除也相对简单，所以答案是A.顺序表。 3. **对称矩阵的压缩存储**：对称矩阵只存储下三角或上三角部分即可，因为其余部分是对称的。对于10阶对称矩阵，a11是第一个元素，存储地址为1，按行优先存储，a85在第8行第5列，需要计算其相对于a11的偏移量。10阶对称矩阵共45个元素，前7行共35个元素，因此a85的地址为1 + 35 + 5 = 41，选项中没有41，但最接近的是C.18，可能是题目有误。 4. **哈夫曼树**：哈夫曼树是一种带权路径长度最短的二叉树。题目中叶结点个数为n，非叶结点的个数可以通过公式n - 1得到，因为除了根节点外，每个叶结点都有一个对应的非叶结点连接，所以答案是A.n-1。 5. **森林与二叉树的对应关系**：森林中的每一棵树都对应二叉树的左子树，森林中最后一棵树的根结点对应二叉树的根结点的右子树。因此，第三棵树的结点个数M3对应二叉树根结点的右子树结点个数，答案是C.M3。 6. **有向无环图（DAG）表示表达式**：表达式(A+B)*((A+B)/A)转换为DAG，至少需要6个顶点，包括乘法、加法、除法操作节点以及括号，所以答案是B.6。 7. **拓扑排序**：拓扑排序是无环有向图的一种排序方法，其时间复杂度为O(n+e)，其中n是顶点数，e是边数。答案是B.O(n+e)。 8. **分块查找**：分块查找要求每块内部有序，但块间只需要块头有序，即每块的最大（或最小）值组成索引块，便于快速定位。答案是B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块。 9. **排序算法**：稳定排序是指相等的元素在排序后的相对位置不会改变。O(nlog2n)时间复杂度且稳定的排序方法是归并排序，答案是C.归并排序。 10. **堆**：小根堆中，堆顶元素是最小的。要找到最大关键字，它可能在最后一个位置，也就是n/2的位置，因为堆的大小是n，且是完全二叉树。但题目问的是“最大记录可能存储在哪个位置”，不是一定，所以是n/2+1，答案是D.ën/2û+2。 11. **硬件与软件比较**：硬件实现的逻辑功能与软件相同，但硬件通常提供更快的速度，而软件则更灵活，成本相对较低，但硬件成本高且不易修改。 以上是根据题目内容解析的相关计算机科学知识点，它们涵盖了数据结构、算法、存储优化等多个方面，对准备计算机考研的学生来说是非常重要的复习资料。