数据结构练习第五章数组和广义表

1数据结构练习第五章数组和广义表一、选择题1．设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。A．688B．678C．692D．6962．设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（）。A.10B.19C.28D.553．在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（）。A．行号B．列号C．元素值D．地址4．设有50行60列的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为（）。A．3700B．4376C．3900D．46205．数组A［0..5］［0..5］的每个元素占5个字节，将其以列为主序存储在起始地址为1000的内存单元中，则元素A［5］［5］的地址是（）A.1175B.1180C.1205D.12106.设有二维数组A［n］［n］表示如下：653421，则A［i］［i］（0≤i≤n-1）的值为（）A．i*(i-1)/2B.i*(i+1)/2C.(i+2)*(i+1)/2D.i2/27．二维数组A［10］［20］采用按行为主序的存储方式，每个元素占4个存储单元，若A［0］［0］的存储地址为300，则A［10］［10］的地址为（）A.700B.1120C.1180D.11408．设有一5阶上三角矩阵A［1..5，1..5］，现将其上三角中的元素按列优先顺序存放在一堆数组B［1..15］中。已知B［1］的地址为100，每个元素占用2个存储单元，则A［3，4］的地址为（）A．116B．118C．120D．1229．在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（）。A.行号B.列号C.元素值D.地址10．设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为（）。A.O(1)B.O(n)C.O(n2)D.O(log2n)11．设有一个10阶的对称矩阵A[10][10]，采用压缩存储方式按行将矩阵中下2三角部分的元素存入一维数组B[]中，A[0][0]存入B[0]中，则A[8][5]在B[]中（）位置。A．32B．33C．41D．6512．设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为(B)。A.13B.33C.18D.4013．数组通常具有的两种基本操作是（A）。A.查找和修改B.查找和索引C.索引和修改D.建立和删除14．数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是(A)。A.1175B.1180C.1205D.121015．若6行5列的数组以列序为主序顺序存储，基地址为1000，每个元素占2个存储单元，则第3行第4列的元素（假定无第0行第0列）的地址是(A)。A.1040B.1042C.1026D.备选答案A，B，C都不对16．稀疏矩阵一般的压缩存储方法有两种，即(C)。A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表17．若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（ij）的位置k的关系为(B)。A.i*(i-1)/2+jB.j*(j-1)/2+iC.i*(i+1)/2+jD.j*(j+1)/2+i18．A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N(N+1)/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（B）。A.i（i-1）/2+jB.j（j-1）/2+iC.i（j-i）/2+1D.j（i-1）/2+119．设有一个n行n列的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中(A)处。A.(i+3)*i/2B.(i+1)*i/2C.(2n-i+1)*i/2D.(2n-i-1)*i/220．用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为(A)。A.j=r[j].nextB.j=j+1C.j=j-nextD.j=r[j]-next21．对矩阵压缩存储是为了(D)。A.方便运算B.方便存储C.提高运算速度D.减少存储空间22．一个非空广义表的表尾(B)。A.不能是子表B.只能是子表C.只能是原子D.是原子或子表23．某字符串满足：concat(head(s),head(tail(tail(s))))=“ac”,(head,tail的定义同广义表),则S=(C)。A.aabcB.acbaC.acccD.acac24．将线性表的数据元素进行扩充，允许是带结构的线性表是(C）。A.串B.树C.广义表D.栈25．广义表（（a,b,c,d））的表头是(C)，表尾是(B)。A.aB.（）C.（a,b,c,d）D.（b,c,d）26．已知Head(Tail([Head(S),Head(Tail(Tail(S)))]))=[a]，广义表S满足上3式，则S为(F)(其中，方括号表示广义表，圆括号表示函数，如[a,b]表示由a,b构成的广义表，而Head()表示取广义表的头部）。A.[[a,b],b,a]B.[[b,a],[a],[b]]C.[[a],[a,b],[b]]D.[b,[a],[a,b]]E.[[a],[b],[b,a]]F.[[b],[b,a],[a]]27．下面说法不正确的是(A)。A.广义表的表头总是一个广义表B.广义表的表尾总是一个广义表C.广义表难以用顺序存储结构D.广义表可以是一个多层次的结构28．广义表（（））的表头是(A)，表尾是(A)。A.（）B.NILC.（（））D.（（（）））29．将一个A[1..100][1..100]的三对角矩阵，按行优先存入一维数组B[1..298]中，A中元素a66,65（即该元素下标i=66，j=65）在B数组中的位置K为（A）A195B196C197D19830．广义表((a))的表尾是（C）A、aB、(a)C、()D、((a))31．已知广义表:A=(a,b),B=(A,A),C=(a,(b,A),B),求下列运算的结果:tail(head(tail(C)))=(F)。A.（a）B.AC.aD.(b)E.bF.(A)32．设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为(B)。A.i(i-l)/2+jB.j(j-l)/2+iC.j(j-l)/2+i-1D.i(i-l)/2+j-133.对矩阵压缩存储是为了（D）。A.方便运算B.方便存储C.提高运算速度D.减少存储空间34.下面说法不正确的是:（）A.广义表的表头总是一个广义表B.广义表的表尾总是一个广义表C.广义表难以用顺序存储结构D.广义表可以是一个多层次的结构【解答】A二、填空题1．设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。i(i+1)/2+j-12．从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为________，输出一个二维数组b[m][n]中所有元素值的时间复杂度为________。O(n)、O(m*n)3．在稀疏距阵所对应的三元组线形表中，每个三元组元素按____________为主序，__________为辅序的次序排列。行号，列号4．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为________________域和______________域。值（或data），子表指针（或sublist）5．对稀疏矩阵进行压缩存储的目的是节省______存储空间______。6．设数组A［0..8］［0..8］的起始元素位置为a，每个元素占2L个存储单元，4按行序为主序存储。若元素A［i］［j］的存储位置为a+66L，则元素A［j］［i］的存储位置为a+120L_______。7．二维数组在机器级的具体实现，通常均采用__顺序和二叉链表___存储结构。8．在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的________、________和________三项。行号、列号、元素值9．在稀疏矩阵所对应的三元组线性表中，每个三元组元素按________为主序、________为辅序的次序排列。行号、列号10．在稀疏矩阵的顺序存储中，利用一个数组来存储非零元素，该数组的长度应________对应三元组线性表的长度。等于11．在稀疏矩阵的带行指针向量的链接存储中，每个结点包含有________个域，在相应的十字链接存储中，每个结点包含有________个域。4、512．在稀疏矩阵的十字链接存储中，每个结点的down指针域指向________相同的下一个结点，right指针域指向________相同的下一个结点。列号、行号13．一个广义表中的元素分为________元素和________元素两类。单、表14．一个广义表的深度等于________嵌套的最大层数。括号15．在广义表的存储结构中，每个结点均包含有________个域。316．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为________域和________域。元素值、子表指针17．若把整个广义表也看为一个表结点，则该结点的tag域的值为________，next域的值为________。true、NULL18．设二维数组A的行和列的下标范围分别为[0：8]和[0：10]，每个元素占2个单元，按行优先顺序存储，第一个元素的存储起始位置为b，则存储位置为b+50处的元素为。A[2][3]19．设数组a[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址为_（1）_;若以列序为主序顺序存储，则元素a[45,68]的存储地址为_（2）_。（1）9174（2）878820．三维数组a[4][5][6]（下标从0开始计，a有4*5*6个元素），每个元素的长度是2，则a[2][3][4]的地址是____。(设a[0][0][0]的地址是1000,数据以行为主方式存储)1164公式：LOC(aijk)=LOC(a000)+[v2*v3*(i-c1)+v3*(j-c2)+(k-c3)]*l(其中，l为每个元素所占单元数,vi是第i维的元素个数=(di-ci+1)，ci和di分别是第i维的界偶。)21．已知二维数组A[1..10，0..9]中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5，9]的地址是：_______。119622．用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j](1≤i≤n,i-2≤j≤i+2),B中的第8个元素是A中的第（1）_行，第（2）_列的元素。第1行第3列，这是一个五对角矩阵。23．设数组A[0..8,1..10],数组中任一元素A[i,j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么（l）存放该数组至少需要的单元数是_______;（2）存放数组的第8列的所有元素至少需要的单元数是_______;（3）数组按列存储