第四章 多维数组和广义表

一 多维数组和运算

填空题

当数组维数为1时，数组是一种元素个数固定的线性表，而维数大于1时，称为多维数组，它可以看成是线性表的推广。

单选题，解答题

二维数组Amxn元素之间的关系除了边界元素外，每个元素aij都恰好有两个直接前趋和两个直接后继：行向量上的直接前趋是aij-1和直接后继aij+1，列向量上的直接前趋是ai-1j和直接后继ai+1j。并且二维数组也只有一个开始结点a00，它没有前趋；仅有一个终端结点am-1n-1，它没有后继。

单选题，填空题

二维数组Amxn按行优先顺序存储在内存中，假设每个元素占d个存储单元，数组元素aij（i=0,1,…,m-1; j=0, 1,…n-1）位于第i行，第j列，前面i行共有ixn个元素，第i行上的aij前面又有j个元素，因此它的前面一共有ixn+j个元素，所以在C语言中的数组元素aij的地址计算函数为：LOC(aij)=LOC(a00)+(ixn+j)xd。

二 矩阵的压缩存储

单选题，填空题

若n阶方阵A中的元素满足下述性质：aij = aji（0<=i, j<=n-1）,则称A为n阶的对称矩阵。对称矩阵中的元素是关于主对角线对称的，所以只需要存储矩阵上三角或者下三角的元素即可，让两个对称的元素共享一个存储空间。

填空题

在矩阵中，其中有s个非零元素，而s远远小于矩阵元素的总数，通常把这种矩阵称为稀疏矩阵。

单选题

1 对称矩阵

以一维数组sa[n(n+1)/2]作为n阶对称矩阵A的存储结构，每个数组元素占用d个存储单元。aij的存储地址可用下面的公式计算：LOC（aij）=LOC（sa[k]）= LOC(sa[0]) + kxd，其中

k = $\begin{cases} i*(i+1)/2 + j (i>=j) \\ j*(j+1)/2 + i (i< j)\\ 0<=k<=n*(n+1)/2-1 \end{cases}$

2 三角矩阵

上三角矩阵中的下三角区的所有元素均为同一常数c，只需存放主对角线，上三角区上的元素和常数c。sa[k]和aij的对应关系如下：

k = $\begin {cases} i * (2n-i+1)/2+j-i (当i<=j) \\ n * (n + 1)/2 (当i>j)\\ \end {cases}$

反之，下三角矩阵中上三角区的所有元素均为同一常数c，只需要存放下三角区，主对角线上的元素和常数c。sa[k]和aij的对应关系如下：

k = $\begin {cases} i*(i+1)/2 + j (当i>=j) \\ n*(n+1)/2 (当i < j) \\ \end {cases}$

填空题

1. 稀疏矩阵在存储非零元素时，除了存储非零元素的值之外，还必须同时存储该元素的行列位置（即下标），所以可用一个称为**三元组（i，j，aij）**来唯一确定一个非零元素。
2. 如果将表示稀疏矩阵非零的元素的三元组按行优先的顺序排列，则可得到一个其结点均为三元组的线性表，将这种线性表的顺序存储结构称为三元组表。

三 广义表基础

填空题

1. 广义表是n（n>=0）个元素a1,a2,…,an的有限序列，其中ai或者是原子项，或者是广义表，通常记作LS=(a1,a2,…,an)。LS是广义表的名字，n为它的长度。若ai又是广义表，则称它为LS的子表。
2. 一个广义表的深度是指广义表展开后所含括号的层数。
3. 当广义表LS非空时，称第一个元素a1是LS的表头，其余元素组成的表（a2,…,an）称为LS的表尾。