资源预览内容
第1页 / 共4页
第2页 / 共4页
第3页 / 共4页
第4页 / 共4页
亲,该文档总共4页全部预览完了,如果喜欢就下载吧!
资源描述
第5章 数组与广义表一、 选择题1. 在以下讲述中,正确的是( B )。A、线性表的线性存储结构优于链表存储结构 B、二维数组是其数据元素为线性表的线性表 C、栈的操作方式是先进先出 D、队列的操作方式是先进后出2. 若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算,这种观点( A )。A、正确 B、错误3. 二维数组SA 中,每个元素的长度为3 个字节,行下标I 从0 到7,列下标J 从0 到9,从首地址SA 开始连续存放在存储器内,该数组按列存放时,元素A47的起始地址为( B)。A、SA+141 B、SA+180 C、SA+222 D、SA+2254. 数组SA 中,每个元素的长度为3 个字节,行下标I 从0 到7,列下标J 从0 到9,从首地址SA 开始连续存放在存储器内,存放该数组至少需要的字节数是( C )。A、80 B、100 C、240 D、2705. 常对数组进行的两种基本操作是( B )。A、建立与删除 B、索引和修改C、查找和修改 D、查找和索引6. 将一个A1515的下三角矩阵(第一个元素为A00),按行优先存入一维数组B120中,A 中元素A65在B 数组中的位置K 为( B )。A、19 B、26 C、21 D、157. 若广义表A 满足Head(A)=Tail(A),则A 为( B )。A、() B、() C、(),() D、(),(),()8. 广义表(a),a)的表头是( C ),表尾是(C )。A、a B、b C、(a) D、(a)9. 广义表(a,b),c,d)的表头是( C ),表尾是( D )。A、a B、b C、(a,b) D、(c,d)10. 广义表(a)的表头是( B ),表尾是(C )。A、a B、(a) C、() D、(a)11. 广义表(a,b,c,d)的表头是( A ),表尾是( D )。A、a B、(a) C、(a,b) D、(b,c,d)12. 广义表(a,b,c,d)的表头是( C ),表尾是( B )。A、a B、() C、(a,b,c,d) D、(a,b,c,d)13. 下面结论正确的是( BC )。A、一个广义表的表头肯定不是一个广义表 B、一个广义表的表尾肯定是一个广义表C、广义表L=(),(A,B)的表头为空表 D、广义表中原子个数即为广义表的长度14. 广义表A=(A,B,(C,D),(E,(F,G)),则head(tail(head(tail(tail(A)=( D )A、(G) B、(D) C、C D、 D15. 已知广义表L=(x,y,z),a,(u,t,w),从L 表中取出原子项t 的操作是( D )。A 、Head(Head(Tail(Tail(L) B 、Tail(Head(Head(Tail(L) C 、Head(Tail(Head(Tail(L) D 、Head(Tail(Head(Tail(Tail(L)16. 16、设A=(a,b,(c,d),(e,(f,g),则Head(Tail(Head(Tail(Tail(A)=( D )A. (g) B.(d) C.c D.d17. 对矩阵压缩存储是为了( B )A、方便运算 B、节省空间 C、方便存储 D、提高运算速度18. 稀疏矩阵一般的压缩存储方法有两种,即( C )A、二元数组和三元数组 B、三元组和散列C、三元组和十字链表 D、散列和十字链表二、 判断题(F/T)1. 数组是同类型值的集合。(T)2. 数组的存储结构是一组连续的内存单元。(T)3. 数组是一种复杂的数据结构,数组元素之间的关系,即不是线性的也不是树形的。(T)4. 插入和删除操作是数据结构中最基本的两种操作,所以这两种操作在数组中也会经常使用。(F)5. 使用三元组表表示稀疏矩阵的元素,有时并不能节省存储空间。(F)6. 广义表是由零个或多个原子或子表所组成的有限序列,所以广义表可能为空表。(T)7. 线性表可以看成是广义表的特例,如果广义表中的每个元素是原子,则广义表便成为线性表。()8. 广义表中原子个数即为广义表的长度。(F)9. 广义表中元素的个数即为广义表的深度。(F)三、 填空题1. 设a 是含有N 个分量的整数数组,则求该数组中最大整数的递归定义为( ),最小整数的递归定义为( )。2. 二维数组A105采用行序为主方式存储,每个元素占4 个存储单元,并且A53的存储地址是1000,则A82的地址是( 1056 )。3. 二维数组Amn采用行序为主方式存储,每个元素占k 个存储单元,并且第一个元素的存储地址是Loc(A00),则Aij的地址是(Loc(A00+(i*n+m)*k )。4. 广义表的(深度 )定义为广义表中括弧的重数。5. 设广义表L=(),(),则Head(L)=( () );Tail(L)=(() );L 的长度是( 2 );L 的深度是( 2 )。6. 广义表中的元素可以是( 原子和字表),其描述宜采用程序设计语言中的(LISP语言 )表示。7. 广义表(a)的表头是( (a) ),表尾是(() )。8. 广义表(a),(b),c),(d)的表头是( (a) ),表尾是((b),c),(d) )。9. 设广义表A=(x,(a,b),c,d),则Head(Head(Tail(A)=( a )。10. 设广义表A=(a,b,c),B=(A,(c,d),C=(a,(B,A),(e,f),则(1)Head(A)=( a ) (2) Tail(B)=( (C,d) )(3)Head(Head(Head(Tail(C)=( (a,b,c) )11. 下三角矩阵A1.N,1.N的下三角元素已压缩到一维数组S1.N*(N+1)/2+1中,若按行序为主序存储,则AI,j对应的S 中的存储位置是 ( )。12. 已知一个稀疏矩阵为,则对应的三元组表表示为( (1,3,2) ,(2,1,3),(3,3,-1),(3,4,5) ) 。13. 一个n*n 的对称矩阵,如果以行或列为主序存入内存,则其容量为 (n*(n+1)/2 )。14. 三维数组Ac1.d1,c2.d2.,c3.d3共有( (d1-c1+1)*(d2-c2+1)*(d3-c3+1) )个元素。15. 数组A1.10,-2.6,2.8以行优先顺序存储,设基地址为100,每个元素占3 个存储单元,则元素A5,0,7的存储地址是( 913 )。=100+(4*7*9+2*7+5)*316. 将一个下三角矩阵A1.100,1.100按行优先存入一维数组B1.n中,A 中元素A66,65在B 数组中的位置为( 2276 )。四、 计算题1. 数组 A869以行主序存储,设第一个元素的首地址是54,每个元素的长度为5,求元素A245的存储地址。答:LOCA245=54+(2*6*9+4*9+5)*5=7992. 假设二维数组 A6x8,每个元素用相邻的6 个字节存储,存储器按字节编址,已知A 的基地址为1000,计算:(1)数组A 的体积(存储量) (2)A 的最后一个元素第一个字节的地址(3)按行存储时,a14 的第一个字节的地址(4)按列存储时,a47 的第一个字节的地址。答:(1)数组A 的体积V=6*8*6=288(2)1000+288-6=1282(3)1000+(4+1*8)*6=1072(4)1000+(4+7*6)*6=12763. 假设按低下标优先存储整数数组 A9x3x5x8 时,第一个元素的字节地址是100,每个整数占4 个字节。问下列元素的存储地址是什么?(1)a0000 =100(2) a1111 =100+(1*3*5*8+1*5*8+1*8+1)*4(3) a3125 =100+(3*3*5*8+1*5*8+2*8+5)*4(4)a8247=100+(8*3*5*8+2*5*8+4*8+7)*44. 按行优先顺序和按列优先顺序分别列出四维数组 A2222所有元素在内存中的存储顺序。答:行优先顺序:A0000, A0100, A1000, A1100, A0010, A0110, A1010, A1110, A0001, A0101, A1001, A1101, A0011, A0111, A1011, A1111列优先顺序:A0000,A1000,A0100,A1100,A0010,A1010,A0110,A1110,A0001,A1001,A0101,A1101,A0011,A1011,A0111,A11115. 一个 n 阶对称矩阵A 采用一维数组S 按行序为主序存放其上三角各元素,写出Sk与Ai,j的关系公式。设A1,1存于S1中。6. 写出下面稀疏矩阵对应的三元组表示,并画出十字链表表示法。A=(0,0,2,0),(3,0,0,0),(0,0,-1,5),(0,0,0,0)答:三元组表示:(0,2,2),(1,0,3),(2,2,-1),(2,3,5)十字链表表示法:五、 简答题1. 什么是广义表,简述广义表与线性表的主要区别? 广义表是一种非线性的数据结构,顾名思义,它也是线性表的一种推广 广义表是线性表的推广,线性表是广义表的特例。当广义表中的元素都是原子时,即为线性表2. 利用广义表的 Head 和Tail 运算把原子student 从下列广义表中分离出来。(1) L1=(soldier,teacher,student,worker,farmer)(2) L2=(soldier,(teacher,student),(worker,farmer))3. 画出下列广义表的存储结构图,并求它的深度。(1)( ),a,(b,c),(d) (2)(
收藏 下载该资源
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号