数组与广义表的压缩存储及地址计算

"本章主要讨论了数组和广义表这两种数据结构，涵盖了它们在存储和访问方面的基础知识。数组是相同类型元素的有序集合，而广义表则是一种更通用的数据结构，可以包含不同类型的数据。这里主要关注的是数组的压缩存储、二维数组的存储布局以及不同存储方式对元素地址的影响。" 1. 对于一个10阶的对称矩阵A，以行序为主存储，a11为第一元素，存储地址为1，由于是对称矩阵，所以a85的位置可以通过对称性计算得出。对称矩阵的下三角部分（包括主对角线）的元素和上三角部分是对称的。a85位于第8行第5列，与a58是对称的，而a58是第5行第8列的元素。由于是10阶矩阵，第8行的元素在压缩存储中从第1行开始算起是第8行，即1 + (8-1)*10 = 1 + 7*10 = 1 + 70 = 71。因此，a85的地址为1 + 70 = 71，但题目要求考虑每个元素占一个地址空间，所以答案是71 + 1 = 72，选项C。 2. 二维数组A[1:6,0:7]，每个元素占用6个字节，总字节数为(6+1)*6*(7+1)=12*8=96，所以①选D，共96个字节。按行存储，最后一行的开始地址为0 + 96 - 6 = 90，所以最后一个元素地址是90 + 5 = 95，即②选L，288。按列存储，最后一列的开始地址为0 + 6*6 = 36，所以A[5,7]的第一个字节的地址是36 + (7-1)*6 + 4 = 36 + 6*6 + 4 = 36 + 36 + 4 = 76，即④选H，234。一般情况下，当行数和列数相同时，按行存储的A[I, J]地址与按列存储的A[J, I]地址相等，因为此时元素个数相同，所以⑤选D。 3. 数组A[i, j]，每个元素3字节，i从1到8，j从1到10，以列为主存放时，A[5, 8]位于第5行第8列。行地址计算为(5-1)*3*10 = 4*30 = 120，列地址为(8-1)*3 = 21，所以A[5, 8]的存储首地址为BA + 120 + 21 = BA + 141，选A。 4. 二维数组A[1..100,1..100]，行序为主序，每个元素2个存储单元，基地址10。LOC[5,5]即为第5行第5列的地址，前4行共占用4*100*2 = 800个存储单元，再加上第5行前4列的8个存储单元，得LOC[5,5] = 10 + 800 + 2*4 = 818，选B。 5. 数组A[0..5,0..6]，每个元素5字节，按列优先次序存储，A[5,5]是第6列的第6个元素。前5列共占用5*(6+1) = 35个元素，即175字节，前5行的第6列共占用5*5 = 25个元素，即125字节。所以A[5,5]的地址是1000 + 175 + 125 = 1200，选C。 6. 二维数组A[0:8,1:5]，每个元素4字节，A[0,1]地址为0，按行存储，A[5,3]在第5行第3列，地址为0 + (5-1)*4*5 + (3-1)*4 = 0 + 20*4 + 2*4 = 80 + 8 = 88。A[3,5]在第3行第5列，地址为0 + (3-1)*4*5 + (5-1)*4 = 0 + 2*4*5 + 4*4 = 40 + 16 = 56。因此，存储数组A的最后一个元素A[5,3]的第一个字节的地址是88，选项B。 这些题目涉及到的主要知识点包括：对称矩阵的压缩存储、二维数组的存储布局（按行优先和按列优先）、地址计算以及元素个数的计算。理解这些概念对于理解和操作数组数据结构至关重要。