济南大学信息科学与工程学院数据结构课件 第四章.ppt

1 . 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为0 到7 ，j的值为0 到9，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[4，7]的存储首地址为( )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 2. 假设以行序为主序存储二维数组A=array[0..99，0..99]，设每个数据元素占2个存储单元，基地址为10，则LOC[4，4]=（ ）。【福州大学 (2分)】 A. 808 B. 818 C. 1010 D. 1020 3. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。南京理工大学 A. 1175 B. 1180 C. 1205 D. 1210 例 对称矩阵 n = 5, 1+2+3+4+5 = 5*(5+1)/2 = 15 一维数组SA[0..14]作为数组A的存储结构: SA=(4 5 2 3 1 3 2 5 2 8 1 6 7 9 5) 如: a[4,2] = a[2,4] = 7 k = i(i+1)/2 + j = 4(4+1)/2 + 2 = 12 故:sa[12] = 7 例5.4 下三角矩阵 4 0 0 0 0 5 2 0 0 0 A = 3 1 3 0 0 2 5 2 8 0 1 6 7 9 5 如: a[4,2] = 7 但 a[2,4] = 0 k = 4(4+1)/2 + 2 = 12 故:sa[12] = 7 三对角矩阵:  当|i-j| 1时, aij = 0, (1=i,j=n) a11 a12 0 0 ... 0 a21 a22 a23 0 ... 0 Anxn = 0 a32 a33 a34 ... 0 0 0 0 ... ann-1 ann 一维数组SA[0..3*n-2]作为数组A下三角元素的存储结构: SA[k]=[a11,a12,a21,a22,a23,a32,a33,a34,...,ann-1,ann] k = 0 1 2 3 4 5 6 7 3n-4 3n-3 sa[k]和a[i, j]的一一对应关系: sa[k], k = 3*(i-1) + j-i , a[i, j] = { 当 |i - j|=1 0 当 |i - j|1 例5.5 三对角矩阵 4 3 0 0 0 5 2 2 0 0 A = 0 1 0 4 0 0 0 2 8 7 0 0 0 9 5 一维数组SA[0..3*5-3]作为数组A的存储结构: SA=(4 3 5 2 2 1 0 4 2 8 7 9 5) 如: a[5,4] = 9 k = 3*(5-1) + 4-5 = 11 故:sa[11] = 9 1.设 有一个10阶对称矩阵A[10][10]以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B 中， A[0][0]存于B[0]中，则A[8][5]在B 的位置 为( )。 A. 32 B. 33 C. 41 D. 65 分析：第0行存一个元素，第1行存2个元素，。。。第i-1行存i个元素，矩阵A[i][j](i=j)前面总共有1+2+（i-1）+j=i ×(i-1)/2+j个元素，可得 LOC（8，5）=8×（8-1）/2+5=33 稀疏因子: 设 m×n 的矩阵A，有 t 个非零元素 令 m×n t δ = ，称δ为矩阵的稀疏因子。 通常， δ ≤ 0.05 时称为稀疏矩阵 §4.3 稀疏