数据结构复习题第5章2022616

第5章数组与广义表一、选择题（每题1分，共10分）.一个向量第一个元素的储存地址是100,每一个元素的长度为2,则第5个元素的地址是（A）o.在数组A中，每一个数组元素A用[占]用3个储存字节，行下标i从1到8,列下标j从1到10。全部数组元素接踵存放于一个连续的储存空间中，则存放该数组至少需要的储存字节数是（Oo.假设有60行70列的二维数组a[l60,1以0列]序为主序次序储存，其基地址为10000,每一个元素占2个储存单元，那末第32行第58列的元素a[32,58]的储存地址为（C）o（无第。行第0列元素）C.14454D.答案A,B,C均不对.将一个A[1..100,1..100]的三对角矩阵，按行优先存入一维数组 B[l・・298]中，A中元素A6665（即该元素下标i=66,j=65）,在B数组中的地点长为（A）。.数组A[0..5,0..6]的每一个元素占五个字节，将其按列优先次序储存在初步地址为1000的内存单元中，则元素A[5,5]的地址是（A）o.假设以行序为主序储存二维数组 A=array[1..100,1..100],设每一个数据元素占2个储存单元，基地址为10,则LOC[5,5]=（B）o.设有数组A[i,j],数组的每一个元素长度为3字节，i的值为1到8,j的值为1到10,数组从内存首地址BA开始次序存放，当用以列为主存放时，元素A[5,8]的存储首地址为(B)oA.BA+141B.BA+180 C.BA+222D.BA+225.设有一个10阶的对称矩阵A,采用压缩储存方式，以行序为主储存，all为第一元素，其储存地址为1,每一个元素占一个地址空间，则a85的地址为(B)oA、13B、33C、18D、40.二维数组A的每一个元素是由6个字符构成的串，其行下标i=0,l,冽，下标>1,2,,10o若A按行先储存，元素A[8,5]的初步地址与当A按列先储存时的元素(B)的初步地址相同。设每一个字符占一个字节。A、A[8,5]B、A[3,10]C>A[5,8]D、A[0,9].若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包含主对角线上全部元素)挨次存放于一维数组B[l..(n(n+l))/]2中，则在B中确立aij(ivj)的地点k的关系为(B)oA、i*(i-l)/2+jB、j*(j-l)/2+IC、i*(i+l)/2+jD、j*(j+l)/2+i.对希少矩阵进行压缩储存目的是(OoA、便于进行矩阵运算B、便于输入和输出C、节约储存空间D、降低运算的时间复杂度.数组r储存静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链挪动的操作为(A)oA、j=r[j].nextB、j=j+lC、j=j->nextD、j=r[j]->next.数组A[0・.4,-3.・-l,5・・7]中含有元素的个数为(B)o精心整理A、55B、45C、36D、16.有一个100*90的希少矩阵，非0元素有10个，设每一个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是(B)oA、60B、66C、18000D、33.设二维数组l..n](即m行n列)按行储存在数组中，则二维数组元素A[i,j]在一维数组B中的下标为(A)oA、(i-1)*n+jB、(i-1)*n+j-lC、i*(j-1)D、j*m+i-l.A[N,N]是对称矩阵，将下边三角(包含对角线)以行序储存到一维数组 T[N(N+1)/2]中，则对任一上三角元素对应T[k]的下标k是(B)。A.i(i-1) (j-1) (j-i) (i-1)/2+1.设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[l..n(n+l)/2中],对上述任一元素aij(Wli,jWn,且iWj)在B中的地点为(B)oA、i(i-l)/2+jB、j(j-l)/2+IC、j(j-l)/2+i-lD、i(i-l)/2+j-l.对于以行为主序的储存结构来说.在数组A[cLdl,c2..d2]中，cl和dl分别为数组A的第一维下标的下、上界，c2和d2分别为第二维下标的下、上界.每一个数据元素占k个储存单元，二维数组中任一元素a[i,的]储存地点可由(B)确立。A、Loc[i,j]=[(d2-c2+l)(i-cl)+(j-c2)]XkB、Loc[i,j]=[Loc[cl,c2]+[(d2-c2+l)(i-cl)+(j-c2)]XkC、Loc[i,j]=A[cl,c2]+[(d2-c2+l)(i-cl)+(j-c2)]XkD、Loc[i,j]=Loc[0,0]+[(d2-c2+l)(i-cl)+(j-c2)]Xk精心整理.设矩阵A是一个对称矩阵，为了节约储存，将其下三角部份 以（以下图所示）按行序存放在一维数组B[Lm（n-l）/2]|中，对下三角部份中任一元素 （i〉=j）在一维数组B的下标地点k值是（B）。A、i（i-l）/2+j-lB>i（i-l）/2+jC、i（i+l）/2+j-lD、i（i+l）/2+j.希少矩阵普通的压缩储存方法有（C）两种。A、二维数组和三维数组B、三元组和散列表C、三元组和十字链表D、散列表和十字链表参照题：.数组SZ[-3,5010]含有元素数量为（B）oA、88B、99C、80D、90.二维数组A的每一个元素是由6个字符构成的串，其行下标i=0、1、 、 8.列下标i=l、2、 、 10o若A按行先储存，元素A[8,5]的初步地址与当A按列先储存时的元素（B）的初步地址相同。设每一个字符占一个字节。A、A[8,5]B、A[3,10]C>A[5,8]D、A[0,9].设有一个10阶的对称矩阵A,采用压缩破除计方式，以行序为主储存，al,1为第一个元素，其储存地址为1,每一个元素占1个地址空间，则a8,5的地址为（B）oA、13B、33C、18D、40.希少矩阵进行压缩储存目的是（C）oA、便于进行矩阵运算B、便于输入和输出C、节约储存空间D、降低运算的时间复杂度25用数组r储存静态链表，结点的next域指向后继，工作指针j指向链中结点，使沿链挪动的操作为（A）oA、j=r[j].nextB、j=j+lC、j^j->nextD、j=r[j]->next精心整理.数组的基本操作主要包含（C）A、建立与删除B、索引与更正C、接见与更正D、接见与索引.设矩阵A是一个对称矩阵，为了节约空间，将其下三角矩阵按行序存放在一维数组B[l,n（n+1）/2]中，对下三角部份中任一元素 aij（i》j）,在一维数B中下标k的值是（B）oA、i（i-1）/2+j-lB、i（i-1）/2+jC、i（i+l）/2+j-lD、i（i+1）/2+j8.设有数组A[i,j],数组的每一个元素长度为3字节，i的值为1到8,j的值为1到10,数组从内存首地址BA开始次序存放，当用以列为主存放时，元素A[8,5]的存储首地址为（B）oA、BA+141B、BA+180C、BA+222D、BA+225数组A中，每一个元素的长度为3个字节，行下标i从1到8,列下标j从1到10,从首地址SA开始连续存放的储存器内，该数组按行存放，元素A[8][5]的初步地址为CoA.SA+141B.SA+144C.SA+222D.SA+225二、判断题（每题1分，共10分）.一个希少矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成为了Am*n的转置运算。（X）.二维以上的数组实际上是一种特殊的广义表。（V）.数组可看做线性结构的一种推行，所以与线性表相同，可以对它进行插入，删除等操作。（X）.希少矩阵压缩储存后，必会失掉随机存取功能。（V）.所谓取广义表的表尾就是返回广义表中最后一个元素。（X）6广义表是由零或者多个原予或者子表所构成的有限序列， 所以广义表可能为空表。（V）.广义表中的元素也许是一个不行切割的原子，也许是一个非空的广义表。（X）.线性表可以看做是广义表的特例，假如广义表中的每一个元素都是原子，则广义表便成为线性表。（V）.若一个广义表的表头为空表，则此广义表亦为空表。（X）.数组元素的下标值越大，存取时间越长。 X（）.数组是一种复杂的数据结构：数组元素之间的关系既不是线性的，也不是树形的（J）.从逻辑结构上看，n维数组的每一个元素均属于n个向量。（V）.二维数组是其数据元素为线性表的线性表（V）.数组是同种类值的会集。（X）三、填空题（每空1分，共10分）.已知二维数组按“行优先次序”储存在内存中，a的储存地址为LOC（a）,则元1111素a.的储存地址为LOC（a）=o（假设每一个元素占2个储存单元，ij ijWm）答案：Loc（a）+（（i-l）*m+j-l）*2.二维数组A[4][4]（即A[O..3][O..3]）的元素初步地址是loc（A[0][0]）=1000,元素的长度为2,则LOC（A[2][2]）的地址为。答案：1020.设有一个二维数组A[10][20]按行存放于一个连续的储存空间中，A[0]⑼的储存地址是200,每一个数组元素占1个储存字，则A⑹⑵的储存字地址是。答案：322.二维数组a[4][5][6]（下标从。开始计，a有4*5*6个元素），每一个元素的长度是2,则a⑵⑶[4]的地址是1164o（设a⑼⑼⑼的地址是1000,数据以行为主方式储存精心整理解说:LOC(aijk)=LOC(aOOO)+[v2*v3*(i-cl)+v3*(j-c2)+(k-c3)]*l(l为每一个元素所占单元数).对矩阵压缩是为了节约储存空间。.所谓希少矩阵指的是非零元极少(t«m*n)且分布没有规律。.设有一个10阶对称矩阵A采用压缩储存方式(以行为主序储存： all=l),则a85的地址为33o解说:(k=i(i-l)/2+j)(l<=i,j<=n).己知三对角矩阵A[1..9,L.的]每一个元素占2个单元，现将其三条对角线上的元素逐行储存在初步地址为1000的连续的内存单元中，则元素A[7,8]的地址为1038。解说：三对角矩阵按行储存： k=2(i-l)+j(l<=i,j<=n)阶对称矩阵a满足a[i][j]=a|j][i],i,j=l..n,,用一维数组t储存时，t的长度为n(n+l)/2,当i=j,a[i][j]=t[i(i+l)/2(或者j(j+l)/2)],i>j,a[i皿=t[i(i-l)/2+j],i<j,a[i皿=t[j(j-l)/2+i(l<=i,jv=n)]°10.设n行n列的下三角矩阵A已压缩到一维数组B"..n*(n+1)⑵中，若按行为主序储存，则A[i,j]对应的B中储存地点为i(i-l)/2+j(l<=i,j<=n)。.设数组数组中任一元素A[i,j]均占内存48个二进制位,从首地址2000开始连续存放在主内存里，主内存字长为 16位,那末⑴存放该数组至少需要的单元数是 270;(2)存放数组的第8列的全部元素至少需要的单元数是 27;(3)数组按列储存时，元素A[5,8]的初步地址是2204o.用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j](lWiWn,i-2WjWi+2),B中的第8个元素是A中的第1行，第3列的元素。.设数组a[1..5O,L.8O的]基地址为2000,每