09年计算机统考精选真题回顾：从基础到高级

09年计算机统考真题包含了多道选择题，涉及了计算机基础、数据结构和算法、存储管理、图论、查找方法、排序算法以及计算机系统基础知识等核心知识点。以下是对部分试题的详细解析： 1. **存储结构的选择**：对于频繁进行存取指定序号元素和尾部操作的情况，顺序表（A）是最合适的选择，因为它支持常数时间复杂度的随机访问。其他数据结构如双链表和循环链表虽然可以实现插入和删除，但在访问特定元素时效率较低。 2. **栈的输出序列**：栈遵循后进先出（LIFO）原则，输入序列123...n按此规则，当输出第一个元素n时，由于是最后一个输入的，所以输出第i个元素应是n减去(i-1)，即n-i+1。 3. **压缩存储的对称矩阵**：10阶对称矩阵存储时，通常会使用压缩存储方式，只存储下三角或上三角部分，对角线上的元素只需存储一次。如果a11是第一行第一列的元素，地址为1，那么对角线上的元素每隔m（矩阵大小）个地址出现一次。a85在第8行第5列，由于对角线，它在a11下方7行，左侧4列，总地址=1+(8-1)*m+4=33。 4. **二叉树与森林的关系**：在二叉树表示的森林中，对应于树的根结点，右子树通常包含所有其他树。所以，如果第一、第二棵树分别对应左子树和右子树，那么右子树上的结点个数等于第二和第三棵树的结点数之和，即M2+M3。 5. **哈夫曼树的性质**：哈夫曼树是一种带权路径长度最短的二叉树，非叶结点（内部结点）的数量比叶结点少一个，因为从根到每个叶子节点恰好经过一个非叶结点。对于度为m的树，非叶结点个数为n-1，其中n是叶结点数，所以答案是B. 6. **表达式树的构建**：表达式(A+B)*((A+B)/A)用有向无环图表示时，至少需要的顶点数取决于操作符的使用。该表达式中，需要五个顶点来表示三个操作符(*)、(/)和括号，以及两个操作数A和B，因此至少需要5个顶点。 7. **拓扑排序的复杂度**：邻接表通常用于稀疏图的表示，拓扑排序算法在此情况下时间复杂度为O(n+e)，其中n是顶点数，e是边数，因为需要遍历每个顶点并处理每条边。 8. **分块查找**：分块查找要求数据被分为若干块，每块内部有序，且每块的最大值或最小值构成索引块，这样可以缩小搜索范围，提高查找效率。 9. **稳定排序算法**：在O(nlog2n)时间内完成排序且保持稳定性的是归并排序（C），因为归并排序在合并过程中保持了相等元素的相对顺序。 10. **小根堆的特性**：小根堆的堆顶元素总是最小的，对于n个关键字，最大的记录可能在堆顶（即根节点）或堆顶元素的下一个位置（即堆顶+1），但具体取决于堆的调整过程，D选项中的D是可能的位置。 11. **硬件与软件的比较**：硬件在逻辑功能上与软件相同，但硬件的优势在于速度（A），因为硬件执行操作的速度远快于软件在处理器上模拟执行。 12. **数据溢出的原因**：数据溢出的根本原因在于数据的位数有限（A），当进行加法或乘法运算时，如果结果超过了数据类型的最大表示范围，就会发生溢出。