资源描述：
《数据结构(本科)期末综合练习三(运算题)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、数据结构(本科)期末综合练习三(运算题)1.对于一个nxn的矩阵A的任意矩阵元素a[i][j]，按行存储时和按列存储时的地址之差是多少。(设两种存储时的开始存储地址均为LOC(O，0)，元素所占存储单元数均为d)按行存储时与按列存储时，计算A[i][j]地址的公式分别为LOC(i,j)=L0C(0,0)+(i*n+j)*d及LOC，(i,j)=LOC(0,0)+(j*n+i)*d两者相减，得L0C(i,j)-L0C’(i,j)=LOC(0,0)+(i*n+j)*d-LOC(0,0)-(j*n+i
2、)*d=(i-j)*(n-l)*d//2分设有一个二维数组A[10][20],按行存放于一个连续的存储空间中，A[0][0]的存储地址是200,每个数组元素占1个存储字，则A[6][2]的地址是多少。按行存储时，计算A[i][j]地址的公式为L0C(i,j)=L0C(0,0)+(i*n+j)*d其中首地址LOC(0,0)=200,每个数组元素的存储占用数d=1,二维数组的列数n=20,根据题意，元素A[6][2]的存储地址为L0C(6,2)=200+(6*20+2)*1=322.3.设有一个二维
3、数组A[10][20],按列存放于一个连续的存储空间中，A[0][0]的存储地址是200,每个数组元素占1个存储字，则A[6][2]的地址是多少。按列存储时，计算A[i][j]地址的公式为LOC(i,j)=LOC(0,0)+(j*m+i)*d其巾首地址LOC(O,0)=200,每个数组元素的存储占用数d=1，二维数组的行数m=10,则数组元素A[6][2]的存储地址为L0C(6，2)=200+(2*10+6)*1=226。4.设有一个10x10的矩阵A,将其下三角部分按行存放在一个一维数组B中，
4、A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。根据题意，矩阵A屮当元素下标I与J满足I彡J时，任意元素A[I][J]在一维数组B中的存放位置为IMl+1)/2+J,因此，A[8][5]在数组B中位置为8*(8+1)/2+5=4U5.设有一个10x10的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。根据题意，矩阵A中当元素下标I与J满足ISJ时，任意元素A[I][J]在一维数组B中的存放位罝为(2
5、*n-I-1)*I/2+Jo但当I〉J时，需要计算其对称元素A[J][I]在B中的存放位置(2*n-J-1)*J/2+I，因此，A[8][5]在数组B屮对称元素A[J][1]的位置为(2*10-5-1)*5/2+8=43o3.设有一个二维数组A[m][n]采用按行存储，假设A[0][0]存放位罝在644⑽，A[2][2]存放位置在676⑽，每个元素占一个存储字，则A[4][4]存放在什么位置。根据二维数组地址计算公式：L0C(i,j)=L0C(0,0)+(i*n+j)*d根据题意,L0C(0,0
6、)=644,L0C(2,2)=676,d=1,有676=644+(2*n+2)解得n=15。代入LOC(i，j)=L0C(0,0)+(i*n+j)*d,得L0C(4,4)=644+4*15+4=7084.设有一个二维数组A[ll][6],按行存放于一个连续的存储空间中，A[0][0]的存储地址是1000，每个数组元素占4个存储字，则A[8][4]的地址在什么地方。对于二维数组，若第一、第二维的元素个数为m和n,每个元素所片存储字数为d,首地址为LOC(0，0)，则对于任一•数组元素A[i][j]
7、,它的存储地址为：LOC(i,j)=LOC(0,0)+(i*n+j)*d根据题意，LOC(8,4)=LOC(O,0)+(8*6+4)*4二1000+52*4=1208。5.设有一个三维数组A[10][20][15],按页/行/列存放于一个连续的存储空间屮，每个数组元素占4个存储字，首元素A[0][0][0]的存储地址是1000,则A[8][4][10]存放于什么地方。对于三维数组，若第一、第二、第三维的元素个数为mi、m2、rn3,每个元素所占存储字数为d,首地址为LOC(0,0,0)，则对于任
8、一数组元素A[i][j][k]，它的存储地址为：LOC(i,j,k)=LOC(0,0,0)+(i*此*nb+j*nu+k)*d根裾题意，nn=10,m2=20,m:5=15,d=4,LOC(O,0，0)=1000，则有LOC(8,4,10)=LOC(0,0,0)+(8*20*15+4*15+10)*4=1000+2470*4=108806.假定一棵二叉树广义表表示为a(b(c)，d(e，f))，分别写出对它进行中序、后序、按层遍历的结果。宇序e+/后按:c,b,a,e,d,f:c,b,e,f,d
