中国矿业大学数据结构历年考题详解：地址计算与二叉树分析

在《数据结构》这门课程的学习中，中国矿业大学2011-2012学年的A卷考试包含了一系列关于数据结构基础概念和实践操作的问题。以下是部分题目详解： 1. **二维数组存储地址计算**： - 题目涉及二维数组A，其中每个元素占用6个字节，以字节编址。在行优先存储方式下，数组的地址计算遵循从左到右、自上而下的顺序，所以起始地址为1000的A[5,5]位于第5行第5列，由于每行元素连续存储，其地址是1000加上前4行元素所占的字节数（即4行×8列×6字节/元素），计算结果是1000 + (5-1) * 8 * 6 = 1270字节。 - 在列优先存储方式下，地址计算是从左列开始逐列向下，所以A[5,5]的地址是1000加上前4列元素（包括自身）的字节数，即1000 + (5*6) = 1210字节。 2. **字符串操作**： - 函数StrLength()用于计算字符串长度，对于字符串t="child"，其长度为5。 - 函数Concat()通过子串拼接，给定s="cake"，取s的子串SubString(s,3,1)="a"和t的子串SubString(t,2,2)="il"，拼接后得到"ail"，所以结果是"ail"。 3. **队列操作**： - 题目提到一个队列Q的操作，如Q.front和Q.rear，表示队首和队尾元素，当Q为空时，Q.front == Q.rear。在某个特定操作后，Q.front可能等于(Q.rear+1)%10，这意味着队列可能不是空的，但元素数量可能是奇数。 4. **图的完全图边数**： - 对于无向完全图，每对顶点之间都有一条边。如果有n个结点，则边数计算公式是n*(n-1)/2，对于n个结点的图，边数为10. 5. **哈希表存储状态**： - 使用哈希函数H(key)=key mod 13将数据表存入长度为13的哈希表，线性探测冲突解决策略要求当探测到冲突时，依次查找下一个位置直到找到空闲槽。根据哈希函数，哈希地址会重复，具体存放状态需要根据具体的键值来绘制，但这里没有给出具体的键值和哈希碰撞情况。 6. **二叉树性质**： - 二叉树的程序题考察了判断一个二叉树是否为完全二叉树的算法，涉及到工作队列（队列EnQueue）操作，判断条件是所有非叶子节点的子树都是完全二叉树。 这些题目涵盖了数据结构中的基本概念，如数组和字符串操作、队列和哈希表的使用、图论的基本知识以及二叉树的特性，都是衡量学生理解和掌握数据结构核心概念的重要测试点。通过解答这些问题，学生能够加深对数据结构的理解，并提高实际问题求解的能力。