《数据结构第4章 数组和广义表》由会员分享，可在线阅读，更多相关《数据结构第4章 数组和广义表（4页珍藏版）》请在金锄头文库上搜索。
1、第4章数组和广义表【例4-1】二维数组A的每一个元素是由6个字符组成的串，其行下标i=0, 1，8,列 下标j=1，2，10。若A以行为主序存储元素，A85的物理地址与当A按列为主序存 储时的元素()的物理地址相同。设每个字符占一个字节。A. A85 B. A310 C. A58 D. A09解： 二维数A是一个9行10列的矩阵，即A910。按行存储时，A85是第85 个元素存储的元素。而按列存储时，第85个存储的元素是A310。即正确答案为B。【例4-2】若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所 有元素)依次存放于一维数组Bn (n+1) /2中，则在B中确定的
2、位置k的关系为()。，*(，+ 1) * jj *( j +1) + 2D.2，i *(i-1) + jj *( j-1) + A.2 B.2，c.解： 如果aij按行存储，那么它的前面有i-1行，其有元素个数为：1+2+3+ (i-1) =i (i-1) /2。同时它又是所在行的第j歹L因此它排列的顺序还得加i *(i -1).+ j上j，一维数组Bn (n+1)/2中的位置k与其下标的关系是：2因此答案为A。【例4-3】已知n阶下三角矩阵A，按照压缩存储的思想，可以将其主对角线以下所有元素(包括主对角线上元素)依次存放于一维数组B中。请写出从第一列开始以列序为主序分配方式时在B中确定元素a
3、 ij的存放位置的公式。解：如果a j按列存储，那么它的前面有j-1列，共有元素：n+(n-1)+(n-2)+ *+n-(j-2)(j-2)( j-1)=(j-1)*n-2而它又是所在列的第i行，因此在它前的元素个数还得加上i。因此它在一维数组B中 的存储顺序为：(j-2)( j-1)(j-1)*n-2 +i【例4-4】已知广义表L=(x,y,z),a,(u,t,w),从L表中取出的原子项ASCII码最大的运算是 ()。A. head(tail(tail(L)B. tail(head(head(tail(L)C. head(tail(tail(head(L)D. head(tail(tail(
4、tail(L)解：选项A的结果是字符串“u”；选项B的结果是空表，无字符；选项C的结果是字符 “z”；选项D的结果是字符“t”。从所有选项的结果可以看出，ASCII码最大的是字符“z”。因 此正确答案是C。习题4一、单项选择题1. 设二维数组A0m-10n-1按行优先顺序存储在内存中，第一个元素的地址为p， 每个元素占k个字节，则元素气的地址为(1. A)。A. p +i*n+j-1*kB.p+(i-1)*n+j-1*kC.p+(jT)*n+iT*kD.p+j*n+i-1*k2. 已知二维数组A10x10中，元素a20的地址为560，每个元素占4个字节，则元素a10的地址为(2. A)。XA.
5、 520B. 522C. 524D. 5183. 若数组A0m0n按列优先顺序存储，则a地址为(3. A )。A.LOC(aoo)+ j*m+iB. LOC(ao)+ j*n+iC.LOC(aoo)+ (j-1)*n+i-1D. LOC(aoo)+ (j-1)*m+i-14. 若下三角矩阵A祢，按列顺序压缩存储在数组Sa0(n+1)n/2忡，则非零元素a/勺地址为(4. B)。(设每个元素占d个字节)“(厂 2)( j-1)A. (j-1)*n-2+i-1*d(j-2)( j-1)B. (j-1)*n-2+i*d(j-2)( j-1)C. (j-1)*n-2+i+1*d(J - 2)( j -
6、1)D. (j-1)*n-2+i-2*d5. 设有广义表D=(a,b,D)，其长度为(B )，深度为(A )。A.无穷大B. 3C. 2D. 56. 广义表A= (a)，则表尾为(6. C )。A.aB.( )C.空表D.(a)7. 广义表 A=(x,(a,B),(x,(a,B),y)，则运算 head(head(tail(A)的结果为(7. A )。A.xB.(a,B)C.(x,(a,B)D.A8. 下列广义表用图来表示时，分支结点最多的是(8. A)。A.L=(x,(a,B),(x,(a,B),y)B.A=(s,(a,B)C.B=(x,(a,B),y)D.D=(a,B),(c,(a,B),
7、D)9. 通常对数组进行的两种基本操作是(9. C)。A.建立与删除B.索引和修改C.查找和修改D.查找与索引10. 假定在数组A中，每个元素的长度为3个字节，行下标i从1到8,列下标j从1 到10,从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数为（10. C）。A. 80B. 100C. 240D. 27011. 数组A中，每个元素的长度为3个字节，行下标i从1到8,列下标j从1到10， 从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A85的起始地址为（11. C）。A. SA+141B. SA+144 C. SA+222 D. SA+22512. 稀疏矩阵一般的
8、压缩存储方法有两种，即（12. C）。A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表13. 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就 完成了对该矩阵的转置运算，这种观点（13. B ）。A.正确B.不正确14. 一个广义表的表头总是一个（14. D）。A.广义表B.元素C.空表D.元素或广义表15. 一个广义表的表尾总是一个（15.A）。A.广义表B.元素C.空表D.元素或广义表16. 数组就是矩阵，矩阵就是数组，这种说法（16.B）。A.正确B.错误C.前句对，后句错D.后句对二、填空题1. 一维数组的逻辑结构是，存储结构是；对于
9、二维或多维数组，分为 和 两种不同的存储方式。1.线性结构，顺序结构，以行为主序，以列为主序2. 对于一个二维数组Amn，若按行序为主序存储，则任一元素Aij相对于A00的地 址为。2. iXn+j个元素位置3. 一个广义表为（a,（a,b）,d,e,（i,j）,k），则该广义表的长度为，深度为。3. 5, 34. 一个稀疏矩阵为，则对应的三元组线性表为。4. （0，2， 2）， （1， 0， 3）， （2， 2， -1）， （2， 3， 5）0020300000 -1500005. 一个n X n的对称矩阵，如果以行为主序或以列为主序存入内存，则其容量为。5. nX （n+1）/26. 已知
10、广义表 A=（a,b,c）,（d,e,f），则运算 head（tail（tail（A）=。6. e7. 设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a85的地址为。7.418. 已知广义表Ls=（a,（b,c,d）,e）,运用head和tail函数取出Ls中的原子b的运算是。 8. head（head（tail（Ls）9. 三维数组Rc *d ,c *d ,c *d 共含有个元素。（其中：c Wd ,c Wd ,c112233 11223Wd3） 9. （di-ci +1）X（d2 _c2 +1）X（d3_c
11、3 +1）10. 数组A110, -2-6, 2-8以行优先的顺序存储，设第一个元素的首地址是100,每个元素占3个存储长度的存储空间，则元素A5, 0, 7的存储地址为。10. 913三、判断题1.数组可看作基本线性表的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。（1.x）2. 多维数组可以看作数据元素也是基本线性表的基本线性表。（2.小3. 以行为主序或以列为主序对于多维数组的存储没有影响。（3W）4. 对于不同的特殊矩阵应该采用不同的存储方式。（4W ）5. 采用压缩存储之后，下三角矩阵的存储空间可以节约一半。（5.x）6. 在一般情况下，采用压缩存储之后，对称矩阵是所有特殊矩阵中存储空间节约最多的。（6.x）7. 矩阵不仅是表示多维数组，而且是表示图的重要工具。（7.V）8. 距阵中的数据元素可以是不同的数据类型。（8.x）9. 矩阵中的行列数往往是不相等的。（9.x）10. 广义表的表头可以是广义表，也可以是单个元素。（10.小11. 广义表的表尾一定是一个广义表。（11W）12. 广义表的元素可以是子表，也可以是单元素。（12.V）13. 广义表不能递归定义。（13.x ）14. 广义表实际上是基本线性表的推广。（14.小15. 广义表的组成元素可以是不同形式的元素。（15.7 ）
