安徽大学2011数据结构A卷：关键知识点与填空解答

在2011年安徽大学数据结构A卷考试中，涉及了多个关键知识点，以下是对其中几个问题的详细解析： 1. **循环队列满的判断**： 循环队列满的条件是当队列的尾指针（rear）达到空间大小M减一的位置时，因为循环队列的特点是尾指针会“环绕”回到头指针之前，所以只有当尾指针再次等于头指针时（front = rear + 1），才表明队列已满。相应的判断语句可以写为：`if (rear + 1 == front)` 或 `if (rear == (front + M - 1) % M)`。 2. **连通图的边数**： 对于n个顶点的连通图，根据图论的基本定理，任何连通图中任意两个顶点间都存在路径。这意味着最简单的连通图是树形结构，其中任意两个顶点之间有一条唯一的路径。因此，最少的边数是连接所有顶点形成一棵树，即边的数量为`n-1`。 3. **时间复杂度分析**： 给出的程序段是一个嵌套循环，外层循环遍历从2到n的整数，内层循环遍历从2到当前外层循环变量的值减1的整数。每次外层循环，内层循环会执行`i-2`次。所以，总的操作次数是所有`i`值下内层循环次数之和，即`∑(i-2)`，这是一个等差数列求和的问题。等差数列前n项和公式为`S_n = n/2 * (a_1 + a_n)`，这里`a_1 = 0`（因为j的起始值是2），`a_n = i-1`。因此，时间复杂度为`O(n^2)`。 4. **广义表操作**： Head(L)通常表示广义表头部的操作，对于`(a, b), (c)`这样的广义表，执行Head操作后返回的是第一个元素，即'a'，因为括号内的元素视为一个整体。 5. **哈夫曼树计算**： 题目要求计算由带权为7、5、2、4的四个叶子结点构造的哈夫曼树的带权路径长度。哈夫曼树的带权路径长度是所有边权之和，由于题目没有给出具体的构建过程，我们无法直接计算，但通常需要先通过贪心算法构建哈夫曼树，再计算其路径长度。 6. **栈操作**： 在栈中，删除栈顶元素（出栈）的函数通常是`pop()`，它会将栈顶元素移除并返回该元素。 7. **数据结构表示**： 数据结构在计算机中的表示主要涉及数据的物理存储方式，如顺序存储（连续内存）、链式存储等。 8. **邻接表的特性**： 在无向图的邻接表表示中，表结点的数量等于顶点的数量，每条边对应一个表结点，因此表结点的个数是边数的两倍。 9. **二维数组地址计算**： 根据题目，给定的二维数组A以行序为主序存储，存储地址递增。A[4][5]的地址可以通过行索引乘以每个元素占用的存储单元数再加上初始地址得到，即`(4 * 2) + (5 * 2 - 1)`，因为A[0][0]的地址是30，那么A[4][5]的地址为`30 + (2*4 + 2*5 - 2)`。 10. **二叉树结点数**： 深度为5的二叉树，如果是满二叉树，那么至多有`2^5 - 1 = 31`个结点，如果不是满二叉树，则最多结点数可能少于这个值。 11. **子串查找**： 在主串s=’HelloWorld’中查找子串p=’or’，需要确定子串在主串中的具体位置，但没有提供具体结果，这通常涉及到字符串搜索算法如KMP、Boyer-Moore等。 12. **树的边数**： 对于含有n个结点的树，边数总是比结点数少1，即`n-1`。 13. **二分查找的深度**： 有序表有11个元素，二分查找时，每次查找都能排除掉一半的元素，所以查找次数为log2(11)，即深度为`log2(11)`。 14. **树的术语**： 在树中，一个节点的直接孩子结点的个数被称为该节点的**度**。 15. **顺序存储表操作**： 顺序存储的线性表中，插入或删除操作通常效率较低，特别是删除，可能需要移动大量元素，具体移动次数取决于删除位置，可能是0（如果删除的是最后一个元素）到n-1（如果删除的是第一个元素）。 以上是针对给定的题目部分知识点的详细解释，完整解答这些题目需要更多上下文信息，但这部分内容已经涵盖了主要概念和计算步骤。