第五章数组和广义表一．选择题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. 4734．在稀疏矩阵的十字链接存储中，每个列单链表中的结点都具有相同的_____。
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．5311.数组通常具有的两种基本操作是________。
A．建立与删除 B．索引和修改 C．查找和修改 D．查找与索引12．二维数组M 的成员是 6 个字符(每个字符占一个存储单元)组成的串，行下标 i 的范围从0 到 8，列下标j 的范围从1到10，则存放M 至少需要________个字节。
A．90 B．180 C．240 D．54013．二维数组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.5517．将10阶对称矩阵压缩存储到一维数组A中，则数组 A的长度最少为________。
A．100 B．40 C．55 D.8018．设矩阵A是一个对称矩阵，为了节省存储空间，将其下三角部分按行序放在一维数组B[1，n(n+1)/2]中。
下三角部分中任一元素 Aij(i>=j),在一维数组 B 中的下标位置是 ________。
A．i(i-1)/2+j-1 B．i(i-1)/2+jC．i(i+1)/2+j-1 D. i(i+1)/2+j19.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A[3][4][5]的存储地址为________。
A．356 B．358 C．360 D.36220.二维数组 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.cD. 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 元素。
（）10. 一个广义表的表尾总是一个广义表。
（）四.简答题1．什么叫二维数组的行序优先存储？什么叫二维数组的列序优先存储？2．什么样的矩阵叫特殊矩阵？特殊矩阵压缩存储的基本思想是什么？3．什么样的矩阵叫稀疏矩阵？稀疏矩阵压缩存储的基本思想是什么？4．已知稀疏矩阵如下：请写出该稀疏矩阵三元组表示。
5.请写出下面链表表示的广义表。
6.画出广义表list=(5,(3,2,(14,9,3),( ),4),2,(6,3,10))的链表表示。
五.程序设计题1.设计一个算法求广义表的深度。
是第i行中的最小值，同时又是第j列中的2.若矩阵A[m][n]中的某个元素aij最大值，则称此元素为该矩阵中的一个鞍点。
假设以二维数组存储矩阵，试编写算法求出矩阵中的所有鞍点。
3．对于二维数组A[m][n]，其中m<=50，n<=50，先读入m和n ，然后读该数组的全部元素，对如下三种情况分别编写相应函数：（1）求数组A靠边元素之和；（2）求从A[0][0]开始的互不相邻的各元素之和；（3）当m==n时，分别求两条对角线上的元素之和，否则打印出m!=n的信息。