地址为______。
1038 三对角矩阵按行序存储的地址公式：k=2(i-1)+j (1<=i,j<=n) 25．所谓稀疏矩阵指的是_______。非零元很少(t< 27．设广义表L=((),()), 则head(L)是(1)___；tail(L)是(2)____；L的长度是(3)___；深度是 (4)__。（1）（） （2）（（）） （3）2 （4）2 28．广义表(a,(a,b),d,e,((i,j),k))的长度是（1）_，深度是（2）_。 （1）5 （2）3 29．设有广义表Ａ＝(((a,b), x), ((a),(b)),(c,(d, (y))))，得到 y的对广义表Ａ的操作序列是_____。head(head(tail(head(tail(head(tail(tail(A)))))))) 30．Tail[Tail[Head[(((a,b),((c))),(d),((e,f)))]]]的运算结果是______，其中“[]”是函数的符号；() 31．已知广义表A=（（（a，b），（c），（d，e））），head（tail（tail（head（A））））的结果是_______。(d,e) 32. 广义表((a,b),c,d)的表头是 ,表尾是 。(a,b) 、 (c,d) 三、判断题 1．（ ）二维数组和多维数组均不是特殊的线性结构。F 2．（ ）稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。T 3．（ ）从逻辑结构上看，n维数组的每个元素均属于n个向量。√ 4．（ ）数组是同类型值的集合。× 5．( )二维以上的数组其实是一种特殊的广义表。√ 6．（ ）广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。× 7．（ ）所谓取广义表的表尾就是返回广义表中最后一个元素。× 8．（ ）广义表的同级元素（直属于同一个表中的各元素）具有线性关系。√ 9．（ ）对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。√ 10．（ ）一个广义表可以为其它广义表所共享。√ 11．（ ）数组是一种线性结构，因此只能用来存储线性表。× 12．（ ）广义表（（（a,b,c）,d,e,f））的长度是4。× 13．( ) 广义表的深度是指其中所含的不同原子的个数。X 14．（ ）若一个广义表的表头为空表，则此广义表亦为空表。× 15．（ ）稀疏矩阵压缩存储后，必会失去随机存取功能。√ 四、简答题 1．数组A[0..8, 1..10] 的元素是6 个字符组成的串，则存放A至少需要多少个字节？ A 的第8列和第5行共占多少个字节 ？若A 按行优先方式存储，元素A[8,5]的起始地址与当A按列优先方式存储时的哪个元素的起始地址一致？ 【厦门大学 2000 五.3（14%/3分）】 （1）540 （2）108 （3）i=3,j=10，即A[3,10] 2．设有三对角矩阵(aij)n*n，将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]=aij，求： 5 （1）用i,j表示k的下标变换公式； （2）用k表示i,j的下标变化公式。 【山东科技大学 2001 一.6 （6分）】【长沙铁道学院 1997 五.1(10分)】 【东北大学2002一(4分)】【北京工业大学2000二.1((9分)】【南京航空航天大学2000 四】 三对角矩阵第一行和最后一行各有两个非零元素，其余每行均有三个非零元素，所以共有3n-2个元素。 （1）主对角线左下对角线上的元素下标间有i=j+1关系，k与i和j的关系为k=3(i-1);主对角线上元素下标间有关系i=j，k与i和j的关系为k=3(i-1)+1; 主对角线右上那条对角线上元素下标间有关系i=j-1，k与i和j的关系为k=3(i-1)+2。综合以上三等式，有k=2(i-1)+j (1<=i,j<=n, |i-j|<=1) （2）i=k/3+1；（1≤k≤3n-2） ∥ k/3取小于k/3的最大整数。下同 j=k-2(i-1)=k-2(k/3)=k%3+k/3 3．现有算法及正整数n和数组A如下，求数组C的值。【北京邮电大学2002五.1(10分）】 VAR A,B,C:Array[1..100] of integer; FUNC AAA(s,t:integer):integer; IF s=t THEN IF B[s]=0 THEN AAA:=S ELSE AAA:=-s ELSE BEGIN l:=AAA(s,(s+t) DIV 2); r:=AAA((s+t) DIV 2+1,t); IF l>0 THEN AAA:=l ELSE AAA:=r; IF (r>0) AND (A[l]>A[r]) THEN AAA:=r END ENDF; PROC BBB; FOR i:=1 TO n DO B[i]:=0; FOR i:=1 TO n DO B[AAA(1,n)]:=i; FOR i:=1 TO n DO C[B[i]]:=A[i]; ENDP; 初始值：n=10,A={121,22,323,212,636,939,828,424,55,262}; 这是一个排序程序。运行后B数组存放A数组各数在排序后的位置。结果是： A={121,22,323,212,636,939,828,424,55,262} B={3,1,6,4,8,10,9,7,2,5} C={22,55,121,212,262,323,424,639,828,939} ?213???4．设矩阵A为331 ????121??（1）执行语句 For i:=1 to 3 do For j:=1 to 3 do ① C[i,j]=A[A[i,j],A[j,i]] 6 结果C矩阵的值是什么？ （2）所选择的下标i，j的次序有关系吗？ （3）在语句①中，用A代替C，A的结果值是什么？ （4）对i，j这对下标取反序，即（3,3），（3,2），（3,1），?，（1,3），（1,2），（1,1） 重复执行（3），把所得结果与（3）中所得结果作比较。 （1）同上面22题（1） （2）对c数组的赋值同所选择的下标i和j的次序（指外层循环用j内层用i）没有关系 （3）同上题22（2） （4）对i,j下标取反序后，重复执行第（3）步，A数组所有元素均变为2。（在机器上验证，反复循环3次后，所有元素均变为2） 5．什么是广义表？请简述广义表和线性表的主要区别。 【解答】广义表是零至多个元素的有限序列，广义表中的元素可以是原子，也可以是子表。从“元素的有限序列”角度看，广义表满足线性结构的特性：在非空线性结构中，只有一个称为“第一个”的元素，只有一个称为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于线性结构。当广义表中的元素都是原子时，广义表就蜕变为线性表。 6．求广义表D=(a，(b，()，c)，((d)，e))的长度和深度。 【解答】3和3 7．下列广义表，可以唯一对应一棵二叉树的有 ( )。 并归纳出唯一对应的条件。 （1）（A（B（D，E），C（F））） （2）（A（B（D，E），C）） （3）（A） （4）（A（B（C，D（E）））） （5）（） 【解答】唯一对应一棵二叉树的有(2)、(3)和(5)。 唯一对应的条件：空表，或只有一个元素的表，或每个子表个数是零或是2的表。 8. 有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，A[1][1]为第一元素，其存储地址为1，每个元素占一个地址空间，求A[7][5]和A[5][6]的地址。 【解答】按照公式： LOC(A[7][5])=7(7-1)/2＋5 = 26 LOC(A[5][6])=LOC(A[6][5])=6(6-1)/2+5=20 9. 设有一个二维数组A[m][n]，设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]存放在什么位置？ 【解答】因为A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，说明一行有15个元素（算法：（676－2－644）/2）。A[3][3]存放位置是692。 10. 二维数组A[9][10]的元素都是6个字符组成的串，请回答下列问题： 7 （1）存放A至少需要( )个字节； （2）A的第7列和第4行共占( )个字节； （3）若A按行存放，元素A[7][4]的起始地址与A按列存放时哪一个元素的起始地址一致。 【解答】按照题5.1给出的公式： （1）存放A需要9*10*6=540个字节 （2）A的第7列和第4行共占(9+10-1)*6=108个字节 （3）LOC(A[7][4])= LOC(A[0][0])+[7*10+4]*L (按行序存储) LOC(A[i][j])= LOC(A[0][0])+[j*9+i]*L（按列序存储，0<=i<=8,0<=j<=9)所以,i=2,j=8。 即元素A[7][4]的起始地址与A按列存放时A[2][8]的起始地址一致。 五、应用题 1.画出广义表LS=(( ) , (e) , (a , (b , c , d )))的头尾链表存储结构。 【解答】 2．已知一个稀疏矩阵如下图所示： 0 4 0 0 0 0 0 0 0 0 -3 0 0 1 8 0 0 0 0 0 0 0 0 0 5 0 0 0 0 -7 0 0 0 2 0 0 0 0 6 0 0 0 具有6行×7列的一个稀疏矩阵 (1)写出它的三元组线性表； (2) 给出它的顺序存储表示； (3) 给出它的转置矩阵的三元组线性表和顺序存储表示； 【解答】 (1) ( (1,2,4),(2,4,-3),(2,7,1),(3,1,8),(4,4,5),(5,2,-7),(5,6,2),(6,4,6) ) 1 2 2 3 4 5 5 6 8
