第五章 数组与广义表

一、基础知识题

5.1 【答案】请按行及按列优先顺序列出四维数组A_2*3*2*3的所有元素在内存中的存储次序，开始结点为a₀₀₀₀ 。 

5.2 【答案】给出C语言的三维数组地址计算公式。

5.3 【答案】设有三对角矩阵 A_n*n，将其三条对角线上的元素逐行地存储到向量B[0...3n-3]中，使得B[k]=a_ij,求：
  　(1)用i , j 表示k的下标变换公式。
　　(2)用 k 表示 i,j 的下标变换公式。

5.4 【答案】设二维数组A_5*6的每个元素占4个字节，已知Loc(a₀₀)=1000，A共占多少个字节? A的终端结点a₄₅的起始地位为何?按行和按列优先存储时，a₂₅的起始地址分别为何?

5.5 【答案】特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存取的功能?为什么?

5.6 【答案】简述广义表和线性表的区别与联系。

5.7 【答案】画出下列广义表的图形表示：
　　(1) A(a,B(b,d),C(e,B(b,d),L(f,g))) 
　　(2) A(a,B(b,A))

5.8 【答案】设广义表L=((),()),试问head(L),tail(L),L的长度，深度各为多少?

5.9 【答案】求下列广义表运算的结果：
　　(1)head((p,h,w)); (2)tail((b,k,p,h)); (3) head(((a,b),(c,d)));
　　(4)tail(((a,b),(c,d))); (5)head(tail(((a,b),(c,d))));
　　(6)tailhead)(((a,b),(c,d)))).

二、算法设计题 

5.10 【答案】当三角矩阵采用题5.3所述的压缩存储时，写一算法求三对角矩阵在这种压缩存储表示下的转置矩阵。

5.11 【答案】当稀疏矩阵A和B均以三元组表作为存储结构时，试写出矩阵相加的算法，其结果存放在三元组表C中。