第五章 数组和广义表
一．选择题
1．在二维数组A 中引用A[i,j]的时间_________。 A．与i、j的大小有关 B．与i、j的大小无关
C．与i的大小有关，与j的大小无关 D．与i的大小无关，与j的大小有关
2．在稀疏矩阵的带行指针向量的链接存储中，每一行单链表中的结点都具有相同的________。
A．行号 B．列号 C．元素值 D.地址
3．二维数组A 按行顺序存储，其中每个元素占1个存储单元。若 A[1][1]的存储地址为420， A[3][3]的存储地址为446，则A[5][5]的存储地址为_______。 A．470 B．471 C．472 D. 473
4．在稀疏矩阵的十字链接存储中，每个列单链表中的结点都具有相同的_____。 A．行号 B．列号 C．元素值 D.地址 5．下面的说法中，不正确的是________。
A．对称矩阵中只须存放包括主对角线元素在内的下(或上)三角部分的元素即可 B．对角矩阵中只须存放的非零元素即可
C．稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储
D．稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储 6．对一些特殊矩阵采用压缩存储的目的主要是为了________。 A．表达变得简单 B．对矩阵元素的存取变得简单 C．去掉矩阵中的多余元素 D．减少不必要的存储空间的开销
7．若将n 阶对称矩阵 A 按照行序为主序方式将包括主对角线元素在内的下三角形的所有元素依次存放在一个一维数组 B 中，则该对称矩阵在B 中占用了________个数组元素。
A．n2 B．n*(n-1) C．n*(n+1)／2 D．n*(n-1) 8. 稀疏矩阵的三元组顺序表表示的一个三元组中不包括________。 A. 行号 B.列号 C.元素值 D.元素总数 9．稀疏矩阵一般的压缩存储方法有两种，即________。 A．二维数组和三维数组 B．三元组和散列 C. 三元组和十字链表 D．散列和十字链表
10．有一个 10 阶对称矩阵 A，采用压缩存储方式(以行序为主存储，且A[0 Ⅱ0]=1)，则A[8][5]的地址是________。
A．52 B．48 C．54 D．53 11.数组通常具有的两种基本操作是________。
A．建立与删除 B．索引和修改 C．查找和修改 D．查找与索引 12．二维数组M 的成员是 6 个字符(每个字符占一个存储单元)组成的串，行下标 i 的范围从0 到 8，列下标j 的范围从1到10，则存放M 至少需要________个字节。
A．90 B．180 C．240 D．540
13．二维数组M 的元素是4 个字符(每个字符占一个存储单元)组成的串，行下标 i 的范围从0 到 4 ，列下标j 的范围从0 到 5,M 按行存储时元素 M[3 Ⅱ5]的起始地址与M 按列存储时元素________的起始地址相同。
A．M[2][4] B．M[3][4] C．M[3][5] D.M[4][4] 14．下面的说法中，不正确的是________。 A．数组是一种线性表结构
B．数组是一种定长的线性表结构，
C．除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等 D．数组的基本操作有存取、修改、检索和排序等，没有插入与删除操作 15．数组的逻辑结构不同于下列________的逻辑结构。 A．线性表 B．栈 C．队列 D.树 16．设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为________。
A．10 B．19 C．28 D.55
17．将10阶对称矩阵压缩存储到一维数组A中，则数组 A的长度最少为________。
A．100 B．40 C．55 D.80
18．设矩阵A是一个对称矩阵，为了节省存储空间，将其下三角部分按行序放在一维数组B[1，n(n+1)/2]中。下三角部分中任一元素 Aij (i>=j),在一维数组 B 中的下标位置是 ________。
A．i(i-1)/2+j-1 B．i(i-1)/2+j C．i(i+1)/2+j-1 D. i(i+1)/2+j
19.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A[3][4][5]的存储地址为________。
A．356 B．358 C．360 D.362
20.二维数组 Amn 按行序为主序存放在内 ,每个数组元素占 1 个存储单元 , 则元素Aij的地址计算公式是:________。 A．loc(Aij)=loc(A11)+[(i-1)*m+(j-1)] B．loc(Aij)=loc(A11)+[(j-1)*m+(i-1)] C．loc(Aij)=loc(A11)+[(i-1)*n+(j-1)] D. loc(Aij)=loc(A11)+[(j-1)*n+(i-1)] 21.广义表(a,b,c,d)的表头是________。.
A．a B．(a) C．a,b,c D. (a,b,c) 22.若广义表K满足head(K)=tail(K),则K为 ________。
A.( ) B.( ( ) ) C.(()),(()) D. ((),(),())
23.设一个广义表中结点的个数为n,则广义表深度算法的时间复杂度为________ 。
A.O(1) B.O(n) C. O(n2) D. O(log2n) 24.下列广义表中，深度为 2的有________。 A.(a，b) B.((c，(a，b))，d)
C.(c，(a，b)) D.((a，b)，(c，(a，b)))
25.广义表 A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A )))))的值为________。
A. (g) B.(d) C.c D. d
二.填空题
1. 设有一个n 阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)/2个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。 2．数组A 中，每个元素A 的长度为3 个字节，行下标i 从1 到8，列下标j 从1 到10，从首地址100 开始连续存放在存储器内，该数组若按行主序存放时，元素A[8][5]的起始地址为 ________；该数组若按列主序存放时，元素A[8][5]的起始地址为__________ 。
3. 假设有二维数组A[6][8]，每个元素用相邻的6 个字节存储，存储器按字节编址。已知A 的起始存储位置（基地址）为1000，则数组A 的体积（存储量）为________ ；末尾元素A57 的第一个字节地址为________；若按行存储时，元素A14 的第一个字节地址为_________ ；若按列存储时，元素A47 的第一个字节地址为__________ 。
4. 若一个n 阶矩阵A 中的元素满足：Aij=Aji (0<=i ,j<=n-1)则称A 为________矩阵；若主对角线上方(或下方)的所有元素均为零时，称该矩阵为__________。 5. 已知广义表A=((a,b,c),(d,e,f)),则运算 head(head (tail(A)))=________。
6. 一个广义表中的元素分为________元素和________元素两类。 7. 稀疏矩阵中第2 行3 列的元素值是5，它的三元组是 ________。
8. 在稀疏矩阵所对应的三元组线性表中，每个三元组元素按_________为主序、_________为辅序的次序排列。
9. 广义表A= (a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。
10．设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为 ____________。
11．设一个具有t个非零元素的m*n 大小的稀疏矩阵采用顺序存储，求其转置矩阵的普通转置算法的时间复杂度为___________ 。
12.二维数组在内存中存储可以有两种存储方式，一种是_____优先存储，一种是 ________优先存储。 13.设广义表L＝(（），（），（（））)。则head(L)是________；tail(L)是________；L的长度是________；L的深度是________。 14.设广义表L＝(（a），（b），（（c））)则head(L)是______；tail(L)是___。 三.判断题
1.在C语言中，多维数组的存储采取的是行优先的方式。（ ） 2.广义表在本质上也是线性表。（ ）
3.可以用三元组存储法来压缩存储稀疏矩阵。（ ）
4.已知广义表A=((a,b,c),(d,e,f)),从A中取出原子e的运算是head(tail(head(tail(A))))。 （ ） 5. 二维数组和多维数组均不是特殊的线性结构。（ ）
6. 数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。（ ）
7. 多维数组元素之间的关系是线性的。（ ） 8. 数组可以看作是二元组<下标，值>的一个集合。（ ）
9. 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0 元素。