第五章数组和广义表

第五章数组与广义表一．选择题1．下面的说法不正确的是____________。A．数组是一种线性结构B．数组是一种定长的线性表结构C．除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等D．数组的基本操作有存取、修改、检索和排序等，没有插入和删除操作分析：数组的主要操作是存取、修改、检索和排序。数组没有插入和修改错误。答案应选择C。2．一维数组A采用顺序存储结构，每个元素占用6个字节，第6个元素的起始地址为100，则该数组的首地址是。A．64B．28C．70D．90分析：设数组元素的首地址为x，则存在关系x+5*6=100，因此x为70，答案应选择C。3．稀疏矩阵采用压缩存储的目的主要是______________。A．表达变得简单B．对矩阵元素的存取变得简单C．去掉矩阵中的多余元素D．减少不必要的存储空间的开销分析：答案应选择D。4．若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij(ij)的位置k的关系为______。A.i*(i+1)/2+jB.j*(j+1)/2+iC.i*(i+1)/2+j+1D.分析：设以行为主序放对称矩阵的下三角元素，其存储结构如5.4所示，a00存储在B[1],a10存储在B[2],……an-1n-1存储在B[n(n+1)/2]，则对称矩阵k与(i，j)的对应关系为：故答案应选择B。B[]123456…k…(n(n+1))/2-1(n(n+1))/2Aa00a10a11a20a21a22…aij…a(n-1)(n-2)a(n-1)(n-1)图5.4对称矩阵的存储示意图5．已知广义表LS=((a,b,c),(d,e,f))，运用GetHead和GetTail运算取出LS中的元素e的运算是。A．GetHead(GetTail(LS))B．GetHead(GetTail(GetTail(GetHead(LS))))C．GetTail(GetHead(LS))D．GetHead(GetTail(GetHead(GetTail(LS))))分析：本题的解答过程要应用排除法，分别对A、B、C、D选项进行计算并判断。根据选项D可知：GetHead(GetTail(GetHead(GetTail(LS))))＝GetHead(GetTail(GetHead((d,e,f))))=GetHead(GetTail(d,e,f))=GetHead((e,f))=e。答案应选择D。6.设广义表L=((a,b,c))，则L的长度和深度分别为。A.1和1B.1和3C.1和2D.2和3i(i+1)/2+j+1ijk=j(j+1)/2+i+1ij分析：该题目主要考查广义表的长度和深度的基本概念，广义表的长度是广义表中层次为1的元素个数，而广义表的深度是指广义表展开后所含括号的层数。因此本题中的L的长度为1，L的深度为2。答案应选择C。7.一个100*90的稀疏矩阵，非0元素有10个整型数，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是_____________。A.60B.66C.18000D.33分析：三元组表结构为(行，列，元素值)，用三元组表表示稀疏矩阵时，还需记录稀疏矩阵的行数、列数以及非零元素个数，本题中所需的字节数应为10*(1+1+1)*2+3*2＝66。答案应选择D。二判断题1．稀疏矩阵压缩后，必会失去随机存取功能。正确分析：具有存取任一个元素的时间相等这一特点的存储结构称为随机存取结构。对稀疏矩阵压缩存储所用的存储结构是三元组表或十字链表。十字链表因其链表结构而不能随机存取；而使用三元组表存储矩阵时，若要访问元素aij，则必须扫描三元组表，显然查找三元组表中前后元素所消耗的时间不同。2．线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，则广义表便成为线性表。正确3．广义表中的元素可以是一个不可分割的原子，或者是一个非空的广义表。错误。分析：该题目主要考查广义表的定义，广义表中元素可以是原子，也可以是表(包括空表和非空表)。4．广义表中原子个数即为广义表的长度。错误分析：该题目主要考查广义表长度的定义，广义表的长度是广义表中层次为1的元素个数。因此本题说法是片面的。5．数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。错误分析：数组可以看成一种特殊的线性表，数组在维数和上下界确定后，其元素个数已经确定，不能进行插入和删除运算。但线性表可以插入删除。二．填空题1．需要压缩存储的矩阵可分为矩阵和矩阵两种。答案：特殊矩阵稀疏矩阵分析：关于矩阵的压缩存储方法，根据矩阵的特点分为特殊矩阵和稀疏矩阵。特殊矩阵要求进行压缩存储时保持其随机存取特性不变，而稀疏矩阵则会失去随机存取功能。2．设数组A[0..8,1..10],数组中任一元素A[i,j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么(1)存放该数组至少需要的单元数是(1)；(2)存放数组的第8列的所有元素至少需要的单元数是(2)；(3)数组按列优先存储时，元素A[5,8]的起始地址是(3)。答案：(1)270(2)27(3)2204分析：(1)数组A[0..8,1..10]的数组元素个数为9*10＝90，因此存放该数组的单元个数为90*48/16＝270，其中每个单元占据48/16=3个字长。(2)存放数组的第8列的所有元素应为9*48/16＝27。(3)若数组按列优先存储，元素A[5,8]的起始地址为2000+(7*9+5)*3＝2204。3．设数组A[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素A[45,68]的存储地址为(1);若以列序为主序顺序存储，则元素A[45,68]的存储地址为(2)。答案：(1)9174(2)8878分析：本题主要考查计算某元素的存储地址，注意区分按行为主序和以列为主序的存储方式。(1)A[45,68]的存储地址=2000+((45-1)*80+67)*2＝9174；(2)A[45,68]的存储地址=2000+((68-1)*50+44)*2＝8788。4．设广义表L=(()，())，则GetHead(L)是；GetTail(L)是；L的长度是；L的深度是。答案：()(())22分析：对于广义表LS=(a1,a2,a3,…,an)，各个运算如下：表头：GetHead(LS)=a1表尾：GetTail(LS)=(a2,a3,…,an)长度：Length(LS)=n深度：故答案为：GetHead(L)=()；GetTail(L)=(())；L的长度为2；L的深度为2。5．广义表中的元素，可以是(1)，所以其描述宜采用程序1LS()0LS1+MAX{Depth(ai)|i=1,2,...,n}LS当为空表当为原子当为子表设计语言的(2)来表示。答案：(1)原子元素或广义表(2)联合或共同体分析：根据广义表定义，广义表中的元素，即可以是原子元素，也可以是广义表。因此其描述应采用程序设计语言的联合或共同体来表示。6．设某广义表H=(A,(a,b,c))，运用GetHead函数和GetTail函数求出广义表H中某元素b的运算式______________。答案：GetHead(GetTail(GetHead(GetTail(H))))分析：本题的解题思路可参见5.2.1节第5题，获得元素b操作的运算式为GetHead(GetTail(GetHead(GetTail(H))))。具体过程如下：（1）GetTail(H)=((a,b,c))（2）GetHead(((a,b,c)))＝(a,b,c)（3）GetTail((a,b,c))＝(b,c)（4）GetHead((b,c))=b（5）b＝GetHead(GetTail(GetHead(GetTail(H))))四．应用题1．设有三对角矩阵An×n，将其三条对角线上的元素按行优先顺序存储到向量B[0..3n-3]中，使得B[k]=aij，求：(1)用i,j表示k的下标变换公式；(2)用k表示i,j的下标变换公式；分析与解答：三对角矩阵为A为1011122,32,22,11,21,1nnnnnnnnnnaaaaaaaa将其按行存储到向量B中，得到的存储形式如下：LOC(B[0])……LOC(B[3n-3])a00a01a10a11a12……an-2,n-3an-2,n-2an-2,n-1an-1,n-2an-1,n-1第0行第1行第n-2行第n-1行(1)元素的二维下标(i,j)与一维向量中的位置k的对应关系为：k=3*i-1+j-i+1=2*i+j(2)一维向量中的位置k与元素的二维下标(i,j)的对应关系为：i=int((k+2)/3),j=k-2*i2．假设一个准对角矩阵：a11a12a21a22a33a34a43a44….aija2m-1,2m-1a2m-1,2ma2m,2m-1a2m,2m按以下方式存储于一维数组B[4m]中:0123456…k…4m-14ma11a12a21a22a33a34a43…aij…a2m-1,2ma2m,2m-1a2m,2m写出由一对下标(i,j)求k的转换公式。分析与解答：将准对角矩阵看成是对角线元素为矩阵的对角矩阵。1100mmAA首先计算出aij所处在对角矩阵Amm中的位置，计算公式为int((i-1)/2)，int()为取整操作。则int((i-1)/2)*4为对角矩阵所处在一维数组B中的位置。其次计算aij的所处在的对角矩阵Amm中的相对位置。具体转换公式如下：k=int((i-1)/2)*4+(i-1)%2*2+1当ij或当i=j且i为偶数k=int((i-1)/2)*4+(i-1)%2*2当ij或当i=j且i为奇数3．设稀疏矩阵0-3100000100-1000000002000000040000000A(1)画出其三元组表形成的压缩存储表。(2)画出其十字链表形成的压缩存储表。分析与解答：稀疏矩阵的三元组表为：s=((1,2,-3),(1,3,1),(2,3,1),(2,6,-1),(4,3,2),(5,5,4)，其中三元组分别表示非零元素行号、列号以及元素值。其顺序存储结构如图5.5所示。123012-311312231326-1443255546稀疏矩阵行数6稀疏矩阵列数6稀疏矩阵非零元素个数图5.5稀疏矩阵A的三元组表(2)十字链表法实际上是采用链式存储结构表示三元组表。在链表中，每个非零元可用一个含有五个域的结点表示。其存储结构定义如图5.2所示。稀疏矩阵A所对应的十字链表存储结构如图5.6所示。图5.6稀疏矩阵A的十字链表4．画出下列广义表的图形表示。(1)A(a,B(b,d),C(e,B(b,d),L(f,g,h)))(2)A(a,B(b,A))分析与解答：（1）A(a,B(b,d),C(e,B(b,d),L(f,g,h)))的图形表示如图5.7(a)所示。（2）A(a,B(b,A))的图形表示如图5.7(b)所示。(a)(b)图5.712-313123126-1432554000000000066000000000000H2H4H5H6H3H1H400H3H5H6HeadH1H2．画出下列广义表的存储结构图，并利用Head和Tail操作分离出原子e。(1)L=(((a)),(b),c,(a),(((d,e))))(2)L=((x,a),(x,a,(b,e)),y)(3)L=(a,((),b),(((e))))分析与解答：由于广义表中的数据元素既可能是列表也可能是单元素，相应结点的结构形式有两种：一种是表结点，用以表示列表；另一种是元素结点，用以表示单元素。在表结点中应该包括一个指向表头的指针和指向表尾的指针；而在元素结点中应该包括所表示单元素的元素值。为了区分这两类结点，在结点中还要设置一个标志域，如果标志为1，则表示该结点为表结点；如果标志为0，则