考研计算机数据结构：存储选择与基本概念题解

1. **线性表操作优化** 在选择数据结构时，如果线性表主要的操作是存取指定序号的元素以及在末尾进行插入和删除，那么考虑时间效率，顺序表是最合适的选择（A）。顺序表通过连续的内存空间实现，存取特定元素的时间复杂度为O(1)，而链表则需要遍历查找，效率较低。 2. **栈的输出序列** 栈遵循后进先出（LIFO）原则，所以输入序列123…n的输出序列的第一个元素是最后一个元素n，输出第i个元素（1 <= i <= n）将是n - (i-1)，即n-i+1。 3. **压缩存储与矩阵地址计算** 对于10阶对称矩阵，采用压缩存储方式（上三角或下三角），地址计算基于行序，已知a11地址为1，每行长度为m，a85即第8行第5列，由于它是对称矩阵，实际只需存储下三角，因此地址为1 + (8-1)*m + (5-1) = 1 + 7m = 13（假设m=1），选A。 4. **森林与二叉树的对应关系** 对应于森林F中的三棵树，二叉树的右子树对应的是前两棵树的节点，所以右子树上的节点个数为M1 + M2。 5. **哈夫曼树的非叶结点数量** 哈夫曼树的性质是满二叉树，度为m的哈夫曼树的叶结点数为n，非叶结点数比叶结点少1，即n-1。 6. **表达式图的顶点数** 表达式(A+B)*((A+B)/A)可以转换为A -> B -> (A+B) -> ((A+B)/A)，至少需要5个顶点来表示：A, B, (A+B), ((A+B)/A)和可能的括号连接点。 7. **邻接表表示图的拓扑排序** 邻接表用于表示稀疏图，拓扑排序通过广度优先搜索(BFS)或深度优先搜索(DFS)实现，时间复杂度为O(n+e)，其中n是顶点数，e是边数。 8. **分块查找** 分块查找适用于部分有序的数据，块间有序，但块内部无需有序，且通过索引块找到目标块后在块内查找，选B。 9. **稳定排序算法** 要求排序稳定且时间复杂度为O(nlog2n)，可以选择归并排序，因为归并排序在合并过程中能保持相同元素的相对顺序。 10. **小根堆特性** 小根堆的堆顶元素总是最小的，关键字最大的记录可能位于堆顶（位置1），但在其他位置也有可能，具体取决于堆的构建过程。 11. **硬件与软件的比较** 硬件在速度上有优势，可以直接执行机器语言级别的指令，而软件则是通过解释或翻译来运行，成本和容量可能受硬件限制，灵活性较差。 12. **数据溢出原因** 数据溢出的根本原因是数据类型大小不足以存储某个值，或者计算结果超出该类型的最大范围，导致超出存储空间。