1、第 5 章 数组与广义表一、选择题（每小题 1 分，共 10 分）1.一个向量第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地址是（ A ） 。A.110 B.108 C.100 D.1202.在数组 A 中，每一个数组元素 Aij占用 3 个存储字节，行下标 i 从 1 到 8，列下标 j从 1 到 10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字节数是（ C ） 。A.80 B.100 C.240 D.2703.假设有 60 行 70 列的二维数组 a160, 170以列序为主序顺序存储，其基地址为10000，每个元素占 2 个存储单
2、元，那么第 32 行第 58 列的元素 a32,58的存储地址为（ C ） 。 （无第 0 行第 0 列元素）A.16902 B.16904 C.14454 D.答案 A, B, C 均不对4.将一个 A1.100，1.100的三对角矩阵，按行优先存入一维数组 B1298中，A 中元素 A6665（即该元素下标 i=66，j=65） ，在 B 数组中的位置 K 为（ A ） 。A. 198 B. 195 C. 197 D.1965.数组 A0.5,0.6的每个元素占五个字节，将其按列优先次序存储在起始地址为 1000的内存单元中，则元素 A5，5的地址是（ A ） 。A. 1175 B. 11
3、80 C. 1205 D. 12106.假设以行序为主序存储二维数组 A=array1.100，1.100，设每个数据元素占 2 个存储单元，基地址为 10，则 LOC5，5= （ B ） 。A. 808 B. 818 C. 1010 D. 10207. 设有数组 Ai,j，数组的每个元素长度为 3 字节，i 的值为 1 到 8，j 的值为 1 到 10，数组从内存首地址 BA 开始顺序存放，当用以列为主存放时，元素 A5，8的存储首地址为（ B ） 。A. BA+141 B. BA+180 C. BA+222 D. BA+2258.设有一个 10 阶的对称矩阵 A，采用压缩存储方式，以行序为
4、主存储，a11 为第一元素，其存储地址为 1，每个元素占一个地址空间，则 a85 的地址为（ B ） 。A、 13 B、 33 C、 18 D、 409. 二维数组 A 的每个元素是由 6 个字符组成的串，其行下标 i=0,1,8,列下标j=1,2,10。若 A 按行先存储，元素 A8,5的起始地址与当 A 按列先存储时的元素（ B ）的起始地址相同。设每个字符占一个字节。A、 A8,5 B、 A3,10 C、 A5,8 D、 A0,910.若对 n 阶对称矩阵 A 以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组 B1.(n(n+1)/2中，则在 B 中确定 a
5、ij（inext D、 j=rj- next 13. 数组 A0.4,-3.-1,5.7中含有元素的个数为（ B ） 。A、 55 B、 45 C、 36 D、 16 14.有一个 100*90 的稀疏矩阵，非 0 元素有 10 个，设每个整型数占 2 字节，则用三元组表示该矩阵时，所需的字节数是（ B ） 。A、 60 B、 66 C、 18000 D、 33 15.设二维数组 A1. m，1. n（即 m 行 n 列）按行存储在数组 B1.m*n中，则二维数组元素 Ai，j在一维数组 B 中的下标为（ A ） 。A、 （i-1）*n+j B、 （i-1）*n+j-1 C、 i*（j-1）
6、D、 j*m+i-1 16.AN，N是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组 TN（N+1）/2中，则对任一上三角元素 aij对应 Tk的下标 k 是（ B ） 。A.i（i-1）/2+j B. j（j-1）/2+I C. i（j-i）/2+1 D.j（i-1）/2+117.设 A 是 n*n 的对称矩阵，将 A 的对角线及对角线上方的元素以列为主的次序存放在一维数组 B1.n(n+1)/2中，对上述任一元素 aij(1i，jn，且 ij)在 B 中的位置为（ B ） 。A、i(i-l)/2+j B、j(j-l)/2+I C、 j(j-l)/2+i-1 D、i(i-l)/2+j
7、-1 18.对于以行为主序的存储结构来说在数组 Ac1.d1,c2.d2中，c1 和 d1 分别为数组 A的第一维下标的下、上界，c2 和 d2 分别为第二维下标的下、上界每个数据元素占 k 个存储单元，二维数组中任一元素 ai,j的存储位置可由（ B ）确定。A、 Loci,j=(d2-c2+1)(i-c1)+(j-c2)kB、 Loci,j=Locc1,c2+(d2-c2+1)(i-c1)+(j-c2)kC、 Loci,j=Ac1,c2+(d2-c2+1)(i-c1)+(j-c2)kD、 Loci,j=Loc0,0+(d2-c2+1)(i-c1)+(j-c2)k19. 设矩阵 A 是一个对
8、称矩阵，为了节省存储，将其下三角部分(如下图所示)按行序存放在一维数组 B1.n(n-1)/2|中，对下三角部分中任一元素 （i=j）在一维数组 B 的下标位置 k 值是（ B ） 。A、 i(i-1)/2+j-l B、 i(i-1)2+j C、 i(i+1)/2+j-1 D、 i(i+1)2+j20.稀疏矩阵一般的压缩存储方法有( C )两种。A、二维数组和三维数组 B、三元组和散列表C、三元组和十字链表 D、散列表和十字链表参考题：21.数组 SZ-35，O 10含有元素数目为（ B ） 。A、88 B、 99 C、 80 D、 9022.二维数组 A 的每个元素是由 6 个字符组成的串，
9、其行下标 i=0、1、8列下标i=1、2、 、10。若 A 按行先存储，元素 A8，5的起始地址与当 A 按列先存储时的元素（ B ）的起始地址相同。设每个字符占一个字节。A、 A8，5 B、 A3，10 C、 A5，8 D、 A0，9 23.设有一个 10 阶的对称矩阵 A，采用压缩破除计方式，以行序为主存储，a1,1 为第一个元素，其存储地址为 1，每个元素占 1 个地址空间，则 a8,5 的地址为（ B ） 。A、13 B、33 C、18 D、40 24. 稀疏矩阵进行压缩存储目的是（ C ） 。A、便于进行矩阵运算 B、便于输入和输出C、节省存储空间 D、降低运算的时间复杂度25.用数
10、组 r 存储静态链表，结点的 next 域指向后继，工作指针 j 指向链中结点，使 沿链移动的操作为（ A ） 。A、j=rj.next B、 j=j+1 C、 j=j-next D、 j=rj- next 26.数组的基本操作主要包括（ C ）A、 建立与删除 B、 索引与修改 C、 访问与修改 D、 访问与索引27.设矩阵 A 是一个对称矩阵，为了节省空间，将其下三角矩阵按行序存放在一维数组B1，n（n+1）/2中，对下三角部分中任一元素 aij（ij） ，在一维数 B 中下标 k 的值是（ B ） 。A、 i（i-1）/2+j-1 B、 i（i-1）/2+jC、 i（i+1）/2+j-1
11、 D、 i（i+1）/2+j 8.设有数组 Ai,j，数组的每个元素长度为 3 字节，i 的值为 1 到 8，j 的值为 1 到 10，数组从内存首地址 BA 开始顺序存放，当用以列为主存放时，元素 A8，5的存储首地址为（ B ） 。A、 BA+141 B、 BA+180 C、 BA+222 D、 BA+225数组 A 中，每个元素的长度为 3 个字节，行下标 i 从 1 到 8，列下标 j 从 1 到 10，从首地址 SA 开始连续存放的存储器内，该数组按行存放，元素 A85的起始地址为 C 。A SA141 B SA144 CSA222 D SA225二、判断题（每小题 1 分，共 10
12、 分）1.一个稀疏矩阵 Am*n 采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把 m 和 n 的值互换，则就完成了 Am*n 的转置运算。 （ ）2.二维以上的数组其实是一种特殊的广义表。 （ ）3.数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ ）4.稀疏矩阵压缩存储后，必会失去随机存取功能。 （ ）5.所谓取广义表的表尾就是返回广义表中最后一个元素。 （ ）6.广义表是由零或多个原予或子表所组成的有限序列，所以广义表可能为空表。( )7.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。 （ ）8.线性表可以看成是广义表的特
13、例，如果广义表中的每个元素都是原子，则广义表便成为线性表。( )9.若一个广义表的表头为空表，则此广义表亦为空表。 （ ）10.数组元素的下标值越大，存取时间越长。( )11.数组是一种复杂的数据结构：数组元素之间的关系既不是线性的，也不是树形的( )12.从逻辑结构上看，n 维数组的每个元素均属于 n 个向量。 （ ）13.二维数组是其数据元素为线性表的线性表 （ ）14.数组是同类型值的集合。 （ ）三、填空题（每空 1 分，共 10 分）1.已知二维数组按“行优先顺序”存储在内存中，a 11 的存储地址为 LOC（a 11） ，则元素 aij的存储地址为 LOC（a ij）= 。 （假定
14、每一个元素占 2 个存储单元，1in,1jm） 答案： Loc(a11)+(i-1)*m+j-1)*2 2.二维数组 A44(即 A0.30.3)的元素起始地址是 loc(A00)=1000,元素的长度为 2,则LOC(A22)的地址为 。答案：1020 3.设有一个二维数组 A1020，按行存放于一个连续的存储空间中，A00的存储地址是200，每个数组元素占 1 个存储字，则 A62的存储字地址是_。答案：3224.二维数组 a456（下标从 0 开始计，a 有 4*5*6 个元素） ，每个元素的长度是 2，则 a234的地址是 1164 。(设 a000的地址是 1000,数据以行为主方式
15、存储) 解释:LOC(aijk)=LOC(a000)+v2*v3*(i-c1)+v3*(j-c2)+(k-c3)*l (l 为每个元素所占单元数)5.对矩阵压缩是为了 节省存储空间 。6.所谓稀疏矩阵指的是 非零元很少(tj,aij=t i(i-1)/2+j ,ij,aij=t j(j-1)/2+i (1=i,j=n) 。10.设 n 行 n 列的下三角矩阵 A 已压缩到一维数组 B1.n*（n+1）/2中，若按行为主序存储，则 Ai,j对应的 B 中存储位置为 i(i-1)/2+j (1=i,j=n) 。10.设数组 A0.8,1.10,数组中任一元素 Ai,j均占内存 48 个二进制位，从
16、首地址 2000 开始连续存放在主内存里，主内存字长为 16 位，那么（l） 存放该数组至少需要的单元数是 270 ;（2） 存放数组的第 8 列的所有元素至少需要的单元数是 27 ;（3） 数组按列存储时，元素 A5,8的起始地址是 2204 。11.用一维数组 B 与列优先存放带状矩阵 A 中的非零元素 Ai,j (1in,i-2ji+2),B 中的第 8 个元素是 A 中的第 1 行，第 3 列的元素。12. 设数组 a1.50,1.80的基地址为 2000，每个元素占 2 个存储单元，若以行序为主序顺序存储，则元素 a45,68的存储地址为 9174 ；若以列序为主序顺序存储，则元素a45,68的存储地址为 8788 。13. 一维数组的逻辑结构是 线性结构 ，存储结构是 顺序结构 ，对二维或多维数组，分为按 以行序为主序 和 以列为主序 两种不同的存储方式。14. 广义表(a)的表头是 (a) ，表尾是 ( ) 。15. 对于元素是整数（占 2 个字节）的对称矩阵 A，采用以行序为主的压缩存储方式存储（下三角） ，若 A00的地址是 400，则元素 A85的的存储地址是 482 。
