数据结构复习题-第5章答案-6-16

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.100C.240D.2703.假设有60行70列的二维数组a160,170以列序为主序顺序存储，其基地址为 10000，每个元素占232行第58列的元素a32,58的存储地址为（ C 0行第0列元素）A.16902 B.1690

2、4B, C均不对C.14454D.答案A,4.将一个A1.100，1.100的三对角矩阵，按行优先存入一维数组中元素元素下标 B 数组中的位置 K 为（ A A. 198B. 195C. 197D.196_5.数组列优先次序存储在起始地址为 1000 的内存单元中，则元素A5，5的地址是（ A A. 11751210B. 1180C. 1205D.6.假设以行序为主序存储二维数组A=array1.100，1.100，设每个数据元素占 2个存储单元，基地址为10，则LOC5，5= （ B A. 8081020B. 818C. 1010D.7. 设有数组3字节，i的值为1到8，j的值为1到10，数

3、组从内存首地址BAA5，8的存储首地址为（ B A. BA+141D. BA+225B. BA+180C. BA+2228.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，a85 B A、13B、33C、18D、409. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,8,列下标j=1,2,10。若A按_A8,5的起始地址与当A按列先存储时的元素（ B ）的起始地址相同。设每个字符占一个字节。A、A8,5D、A0,9B、A3,10C、A5,810.若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素 )依次存

4、放于一维数组B1.(n(n+1)/2中，则在B中确定aij（inextD、j=rj- next13. 数组A0.4,-3.-1,5.7中含有元素的个数为（ B _A、55B、45C、36D、1614.有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ B A、60B、66C、18000D、3315.设二维数组A1.m，1.n（即m行n列）按行存储在数组 B1.m*n中，则二维数组元素 Ai，j在一维数组B中的下标为（ A D、j*m+i-1C、i*（j-1）16.AN，N是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组 TN（

5、N+1）/2中，则对任一上三角元素aij对应Tk的下标k是（ B B. C./2+1 D.j（i-1）/2+117.设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组且ij)在B中的位置为（ B A、i(i-l)/2+jj(j-l)/2+i-1B、j(j-l)/2+IC、D、i(i-l)/2+j-1_18.对于以行为主序的存储结构来说在数组Ac1.d1,c2.d2中，c1和d1分别为数组A的第一和d2分别为第二维下标的下、上界每个数据元素占k个存储单元，二维数组中任一元素ai,j的存储位置可由（ B ）确定。A、Loci,j=(d2-c2+1)(i-c1)+(j

6、-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是一个对称矩阵，为了节省存储，将其下三角部分 (如下图所示 )按行序存放在一维数组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、二维数组和三维数

7、组 B、三元组和散列表_C、三元组和十字链表D、散列表和十字链表参考题：21.数组 B A、88 B、99 C、80 D、9022.二维数组A的每个元素是由6个字符组成的串，其行下标 若A按行先存储，元素A8，5的起始地址与当A按列先存储时的元素（ B ）的起始地址相同。设每个字符占一个字节。A、A8，5B、A3，10C、A5，8 D、A0，923.设有一个10阶的对称矩阵A，采用压缩破除计方为第一个元素，其存储地址为1a8,5的地址为（ B A、13B、33C、18D、4024. 稀疏矩阵进行压缩存储目的是（ C A、便于进行矩阵运算输出B、便于输入和C、节省存储空间时间复杂度D、降低运算的

8、_25.用数组rnext域指向后继，工作指针 j 指向链中结点，使 沿链移动的操作为（ A A、j=rj.nextj=j-nextB 、 j=j+1C 、D、j=rj- next26.数组的基本操作主要包括（ C ）A、建立与删除问与修改B、索引与修改D、访问与索引C、访27.设矩阵 A是一个对称矩阵，为了节省空间，将其下三角矩阵按行序存放在一维数组中，对下三角部分中任一元素B中下标k的值是（ B A、i（i-1）/2+j-1C、i（i+1）/2+j-1B、i（i-1）/2+jD、i（i+1）/2+j8.设有数组Ai,j，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存

9、首地址BAA8，5的存储首地址为（ B A、 BA+141D、BA+225B、 BA+180C、 BA+222数组A中，每个元素的长度为3个字节，行下标i从1到j从1到SA开始连续存_放的存储器内，该数组按行存放，元素 A85的起始地址为 C。A SA141 B SA144D SA225C SA222二、判断题（每小题1分，共10分）1.一个稀疏矩阵 Am*n 采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n ）2.二维以上的数组其实是一种特殊的广义表。（ ）3.数组可看成线性结构的一种推广，因此与线性表一 ）4.稀疏矩阵压缩存储后，必会失去随

10、机存取功能。（ ）5.所谓取广义表的表尾就是返回广义表中最后一个 ）6.广义表是由零或多个原予或子表所组成的有限序列，所以广义表可能为空表。( )7.广义表中的元素或者是一个不可分割的原子，或者 ）_8.线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，则广义表便成为线性表。( )9.若一个广义表的表头为空表，则此广义表亦为空 ） )11.数组是一种复杂的数据结构：数组元素之间的关系既不是线性的，也不是树形的( )维数组的每个元素均属于n个 ）13.二维数组是其数据元素为线性表的线性表（ ） ）三、填空题（每空1分，共10分）1.已知二维数组按“行优先顺序”存储在内存中，a11的存

11、储地址为 a 的存储地址为LOC11 ij（a ）=ij 2个存储单元，1in,1jm）答案：Loc(a )+(i-1)*m+j-1)*2112.二维数组A44(即A0.30.3)的元素起始地址是 loc(A00)=1000,元素的长度为 2,则LOC(A22)的地址为。答案：1020_3.设有一个二维数组A1020，按行存放于一个连组元素占 1 个存储字，则 A62的存储字地址是_。答案：3224.二维数组0有4*5*6 2，则a234的地址是 1164 。(设a000的地址是1000,数据以行为主方式存储)解释:LOC(aijk)=LOC(a000)+v2*v3*(i-c1)+v3*(j-

12、c2)+(k-c3)*l (l为每个元素所占单元数)5.对矩阵压缩是为了 节省存储空间 。6.所谓稀疏矩阵指的是 非零元很少(tm*n)且分布没有规律 。7.设有一个10阶对称矩阵A采用压缩存储方式（以 a85 的地址为 33 。解释:(k=i(i-1)/2+j) (1=i,j=n)8.己知三对角矩阵A1.9,1.9的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中，则元素A7,8的地址为 1038 。(1=i,jj,aij=t i(i-1)/2+j ,ij,aij=t j(j-1)/2+i (1=i,j=n) 。10.设n 行 n 列的下三角矩阵 A

13、 已压缩到一维数组Ai,j对 应 的 B 中 存 储 位 置 为(1=i,j=n) 。i(i-1)/2+j10.设数组A0.8,1.10,数组中任一元素Ai,j均占内存48个二进制位，从首地址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,