数据结构 数组与广义表习题

1、以行序优先顺序存储数组A[5][5]；假定A[0][0]的地址为1000, 每个元素占4个字节，下标变量A[4][3]的地址是____。

A.1069B.1092C.1023D.1046正确答案：B2、数组a[1．．6][1．．5] （无0行0列）以列序优先顺序存储，第一个元素a[1][1]的地址为1000，每个元素占2个存储单元，则a[3][4]的地址是____。

A.1040B.1026C.1046D.1038正确答案：A3、设有一个5行4列的矩阵A，采用行序优先存储方式，A[0][0]为第一个元素，其存储地址为1000，A[2][2]的地址为1040，则A[3][0]的地址为_________。

A.1048B.1024C.1096D.1060正确答案：A4、设有一个10行10列的矩阵A，采用行序优先存储方式，存储全部数据需要400个字节的空间。

如果A[0][0]为第一个元素，其存储地址为1000，则A[3][6]的地址为_________。

A.1036B.1144C.1014D.10565、设有一个10行10列的矩阵A，采用行序优先存储方式。

如果A[0][0]为第一个元素，其存储地址为1000，A[2][3]的存储地址为1069，则存储一个元素需要的单元数是_________。

A.4B.1C.2D.3正确答案：D6、不能够对数据元素进行随机访问的物理结构是_________。

A.三元组顺序表B.对称矩阵的压缩存储C.三对角矩阵的压缩存储D.数组的顺序存储正确答案：A7、对特殊矩阵采用压缩存储的目的主要是_________。

A.表达变得简单B.去掉矩阵中的多余元素C.对矩阵元素的存储变得简单D.减少不必要的存储空间正确答案：D8、对n*n的对称矩阵进行压缩存储，需要保存的数据元素的个数是_________。

A.nB.n(n+1)/2C.n2D.n(n+1)9、设10*10的对称矩阵下三角保存SA[1．．55]中，其中A[1][1]保存在SA[1]中，A[5][3] 保存在SA[k]中，这里k等于_________。

第4章数组和广义表【例4-1】二维数组A的每一个元素是由6个字符组成的串，其行下标i=0，1，…，8，列下标j=1，2，…，10。

若A以行为主序存储元素，A[8][5]的物理地址与当A按列为主序存储时的元素（）的物理地址相同。

设每个字符占一个字节。

A．A[8][5] B．A[3][10] C．A[5][8] D．A[0][9]解：二维数A是一个9行10列的矩阵，即A[9][10]。

按行存储时，A[8][5]是第85个元素存储的元素。

而按列存储时，第85个存储的元素是A[3][10]。

即正确答案为B。

【例4-2】若对n阶对称矩阵A以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组B[n（n+1）/2]中，则在B中确定的位置k的关系为（）。

A．jii+-2)1(*B．ijj+-2)1(*C．jii++2)1(*D．ijj++2)1(*解：如果a ij按行存储，那么它的前面有i-1行，其有元素个数为：1+2+3+…+（i-1）=i（i-1）/2。

同时它又是所在行的第j列，因此它排列的顺序还得加上j，一维数组B[n(n+1)/2]中的位置k与其下标的关系是：jii+-2)1(*。

因此答案为A。

【例4-3】已知n阶下三角矩阵A，按照压缩存储的思想，可以将其主对角线以下所有元素（包括主对角线上元素）依次存放于一维数组B中。

请写出从第一列开始以列序为主序分配方式时在B中确定元素a ij的存放位置的公式。

解：如果a ij按列存储，那么它的前面有j-1列，共有元素：n+(n-1)+(n-2)+ …+[n-(j-2)]=(j-1)*n-2)1)(2(--jj而它又是所在列的第i行，因此在它前的元素个数还得加上i。

因此它在一维数组B中的存储顺序为：(j-1)*n-2)1)(2(--jj+i【例4-4】已知广义表L=((x,y,z),a,(u,t,w))，从L表中取出的原子项ASCII码最大的运算是（）。

第4 章广义线性表——多维数组和广义表课后习题讲解1. 填空⑴ 数组通常只有两种运算：（）和（），这决定了数组通常采用（）结构来实现存储。

【解答】存取，修改，顺序存储【分析】数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。

除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。

⑵ 二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A[10][5]的存储地址是1000，则元素A[15][10]的存储地址是（）。

【解答】1140【分析】数组A中每行共有6个元素，元素A[15][10]的前面共存储了(15-10)×6+5个元素，每个元素占4个存储单元，所以，其存储地址是1000+140=1140。

⑶ 设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个存储单元，则元素A[8][5]的存储地址为（）。

【解答】d+41【分析】元素A[8][5]的前面共存储了(1+2+…+8)+5=41个元素。

⑷ 稀疏矩阵一般压缩存储方法有两种，分别是（）和（）。

【解答】三元组顺序表，十字链表A 数组是一种线性结构B 数组是一种定长的线性结构C 除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等D 数组的基本操作有存取、修改、检索和排序等，没有插入与删除操【解答】C【分析】数组属于广义线性表，数组被创建以后，其维数和每维中的元素个数是确定的，所以，数组通常没有插入和删除操作。

⑷ 对特殊矩阵采用压缩存储的目的主要是为了（）A 表达变得简单B 对矩阵元素的存取变得简单C 去掉矩阵中的多余元素D 减少不必要的存储空间【解答】D【分析】在特殊矩阵中，有很多值相同的元素并且他们的分布有规律，没有必要为值相同的元素重复存储。

⑸ 下面（）不属于特殊矩阵。

A 对角矩阵B 三角矩阵C 稀疏矩阵D 对称矩阵【解答】C⑹ 若广义表A满足Head(A)=Tail(A)，则A为（）A ( )B (( ))C (( ),( )) D(( ),( ),( ))【解答】BA 广义表是一种多层次的结构B 广义表是一种非线性结构C 广义表是一种共享结构D 广义表是一种递归【解答】B【分析】从各层元素各自具有的线性关系讲，广义表属于线性结构。

第四、五章串、数组和广义表练习题答案一．填空题1. 不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。

2. 设S=“A;/document/Mary.doc”，则strlen(s)= 20 , “/”的字符定位的位置为3。

3. 子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。

4. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 6 次匹配成功。

5. 若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m。

6. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。

已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为288 B ；末尾元素A57的第一个字节地址为1282 ；若按行存储时，元素A14的第一个字节地址为(8+4)×6+1000=1072 ；若按列存储时，元素A47的第一个字节地址为(6×7＋4)×6＋1000）＝1276 。

(注：数组是从0行0列还是从1行1列计算起呢？由末单元为A57可知，是从0行0列开始！)7. 〖00年计算机系考研题〗设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为8950 。

答：不考虑0行0列，利用列优先公式：LOC(a ij)=LOC(a c1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L 得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝89508. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的行下标、列下标和元素值。

9.求下列广义表操作的结果：（1）GetHead【((a,b),(c,d))】=== (a, b) ; //头元素不必加括号（2）GetHead【GetTail【((a,b),(c,d))】】=== (c,d) ;（3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== b ;（4）GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== （d）;10．C语言规定，字符串常量按_字符数组_____处理，它的值在程序的执行过程中是不能改变的。

一、选择题1、设二维数组A[0..m-1][0..n-1]按行优先顺序存储在内存中，每个元素a ij占d个字节，则元素a ij的地址为（）A、LOC(a00)+(i*n+j)*dB、LOC(a00)+((i-1)*n+j-1)*dC、LOC(a00)+((j-1)*n+i-1)*dD、LOC(a00)+(j*n+i-1)*d2、已知二维数组A8*10中，元素a12的地址为1000，每个元素占2个字节，则元素a00的地址为（）A、972B、974C、976D、9783、若数组A[0..m-1][0..n-1]按列优先顺序存储，则a ij地址为（）A、LOC(a00)+j*m+iB、LOC(a00)+j*n+IC、LOC(a00)+(j-1)*n+i-1D、LOC(a00)+(j-1)*m+I-14、若下三角矩阵A n*n，按行顺序压缩存储在数组a[0..(n+1)n/2]中，则非零元素a ij的地址为（）（设每个元素占d个字节）A、LOC(a00)+((j-1)j/2+i)*dB、LOC(a00)+((i+1)i/2+j)*dC、LOC(a00)+((i-1)i/2+i-1)*dD、LOC(a00)+((i-1)i/2+j-1)*d5、设有广义表D=（a,b,D），其长度为（B），深度为（A）A、∞B、3C、2D、56、广义表A=（a），则表尾为（）A、aB、（（））C、空表D、（a）7、广义表A=((x,(a,b)),((x,(a,b)),y))，则运算head(head(tail(A)))为（）A、xB、(a,b)C、(x,(a,b))D、A8、数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址a开始连续存放在存储器内，存放该数组至少需要的单元数为（）A、80B、100C、240D、2709、数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址a开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（）A、a+141B、a+144C、a+222D、a+22510、稀疏矩阵一般的压缩存储方法有两种，即（）A、二维数组和三维数组B、三元组和散列C、三元组和十字链表D、散列和十字链表11、一个广义表的表头总是一个（）A、广义表B、元素C、空表D、元素或广义表12、数组就是矩阵，矩阵就是数组，这种说法（）A、正确B、错误C、前一句对，后一句错D、后一句对二、填空题1、广义表LS=（），其长度为（0）；深度为（0）。

计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编3(总分：66.00，做题时间：90分钟)一、综合题(总题数：20，分数：48.00)1.数组A[1．．8，一2．．6，0．．6]以行为主序存储，设第一个元素的首地址是78，每个元素的长度为4，试求元素A[4，2，3]的存储首地址。

【厦门大学1998五、1(5分)】__________________________________________________________________________________________ 正确答案：(正确答案：元素A[4，2，3]的存储首地址为958。

三维数组以行为主序存储，其元素地址公式为：LOC(A ijk )=LOC(A c1c2c3 )=(3A c1c2c3 )+[(i-c 1 )V 2 V 3 +(j—c 2 )V 3 +(k-c 3 )]*L其中，c i，d i 是各维的下界和上界，V i =d i一c i +1是各维元素个数，L是一个元素所占的存储单元数。

)2.数组A中，每个元素A[i，f]的长度均为32个二进位，行下标从一1到9，列下标从1到11，从首地址S开始连续存放在主存储器中，主存储器字长为16位。

求：(1)存放该数组所需多少单元?(2)存放数组第4列所有元素至少需多少单元?(3)数组按行存放时，元素A[7，4]的起始地址是多少?(4)数组按列存放时，元素A[4，7]的起始地址是多少?【大连海事大学1996四、1(6分)】__________________________________________________________________________________________ 正确答案：(正确答案：每个元素32个二进制位，主存字长16位，故每个元素占2个字长，行下标可平移至1到11。

(1)242 (2)22 (3)S+182 (4)S+142)3.假设按低下标优先存储整型数组A(一3：8，3：5，一4：0，0：7)时，第一个元素的字节存储地址是100，每个整数占4字节，问A(0，4，一2，5)的存储地址是什么? 【清华大学1996三】__________________________________________________________________________________________ 正确答案：(正确答案：1784 (公式：Loc(A ijkl )=100(基地址)+[(i-c 1 )v 2 v 3 v 4 +一c 2 )v 3 v 4 +(k-c3 )v4 +(l一c 4 )]*4))4.设有五对角矩阵A=(a ij ) 20*20，按特殊矩阵压缩存储的方式将其五条对角线上的元素存于数组A[-10：m]中，计算元素A[15，16]的存储位置。

B(2.0) D(2.0) D(2.0) D(2.0) D(2.0) A(2.0) B(2.0) B(2.0) D(2.0) C(2.0) D(2.0) D(2.0)2-1广义表是一种（B）数据结构。

(2分)1.非递归的2.递归的3.树型4.图状作者: 严冰单位: 浙江大学城市学院2-2一个广义表为( a, (b, c), d, (), ((f, g), h) )，则该广义表的长度与深度分别为（D）。

(2分)1.4和62.6和33.3和54.5和3作者: 严冰单位: 浙江大学城市学院2-3稀疏矩阵的快速转置算法的时间复杂度是（D）。

(2分)1.三次方时间2.二次方时间3.对数时间4.线性时间作者: 严冰单位: 浙江大学城市学院2-4在定义稀疏矩阵的十字链接存储结构时，每个结点结构需包含（D）个域。

(2分)1. 42. 33. 64. 5作者: 严冰单位: 浙江大学城市学院2-5广义表与稀疏矩阵都是线性表的扩展，它们的共同点为（D）。

(2分)1.都可以用链接结构与顺序结构存储2.无共同点3.都是递归结构4.数据元素本身是一个数据结构作者: 严冰单位: 浙江大学城市学院2-6(neuDS_C++)以下叙述中正确的是(A )。

(2分)1.串是一种特殊的线性表2.串的长度必须大于零3.串中元素只能是字母4.空串就是空白串作者: 姚志军单位: 广东东软学院2-7(neuDS_C++)串是一种特殊的线性表，其特殊性体现在(B )。

(2分)1.可以顺序存储2.数据元素是一个字符3.可以链接存储4.数据元素可以是多个字符作者: 姚志军单位: 浙江大学2-8(neuDS_C++)设有两个串p和q，求q在p中首次出现的位置的运算称作( B)。

(2分)1.连接2.模式匹配3.求子串4.求串长作者: 姚志军单位: 广东东软学院2-9(neuDS_C++)设串s1=’ABCDEFG’，s2=’PQRST’，函数con (x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con (subs (s1,2,len (s2)), subs (s1,len (s2),2))的结果串是(D )。

计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编4(总分：60.00，做题时间：90分钟)一、综合题(总题数：13，分数：26.00)1.简述广义表属于线性结构的理由。

【西北大学2000一、5(3分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：广义表是元素为原子或子表的有限序列，满足线性结构的特性：在非空线性结构中，只有一个称为“第一个”的元素，只有一个称为“最后一个”的元素，第一个元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。

从这个意义上说，广义表属于线性结构，只是元素可以是原子，也可以是子表。

)解析：2.数组、广义表与线性表之间有什么样的关系?【西北工业大学1998一、2(4分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：数组是具有相同性质的数据元素的集合，同时每个元素又由唯一下标限定，可以说数组是值和下标偶对的有限集合。

n维数组中的每个元素，处于n个关系之中，每个关系都是线性的，且n 维数组可以看作其元素是n一1维数组的一个线性表。

而广义表与线性表的关系，见上面21题的解释。

) 解析：3.什么是广义表?请简述广义表和线性表的主要区别。

【北京大学1997二、2(5分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：线性表中的元素可以是各种各样的，但必须具有相同性质，属于同一数据对象。

第五章数组和广义表一、选择题部分答案解释如下。

1. 错误。

对于完全二叉树，用一维数组作存储结构是效率高的（存储密度大）。

4. 错误。

数组是具有相同性质的数据元素的集合，数据元素不仅有值，还有下标。

因此，可以说数祖是元素值和下标构成的偶对的有穷集合。

5. 错误。

数组在维数和界偶确定后，其元素个数已经确定，不能进行插入和删除运算。

6. 错误。

稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三元组中的位置。

8. 错误。

广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的表，不可能是原子。

9. 错误。

广义表的表头就是广义表的第一个元素。

只有非空广义表才能取表头。

10. 错误。

广义表中元素可以是原子，也可以是表（包括空表和非空表）。

11. 错误。

广义表的表尾，指去掉表头元素后，剩余元素所组成的表。

三、填空题1. 顺序存储结构2.（1）9572（2）12283.（1）9174（2）87884. 11005. 1164 公式：LOC(a ijk)=LOC(a000)+[v2*v3*(i-c1)+v3*(j-c2)+(k-c3)]*l (l为每个元素所占单元数)6. 2327. 13408. 11969. 第1行第3列10. (1)270 (2)27 (3)2204 11. i(i-1)/2+j (1<=i,j<=n)12. (1)n(n+1)/2 (2)i(i+1)/2 (或j(j+1)/2) (3)i(i-1)/2+j (4)j(j-1)/2+i (1<=i,j<=n)13. 1038 三对角矩阵按行存储：k=2(i-1)+j (1<=i,j<=n)14. 33 (k=i(i-1)/2+j) (1<=i,j<=n)15. 非零元很少(t<<m*n)且分布没有规律 16. 节省存储空间。

17. 上三角矩阵中，主对角线上第r(1≤r≤n) 行有n-r+1个元素，a ij所在行的元素数是j-i+1。

第5章数组与广义表一、选择题1.在以下讲述中，正确的是（B ）。

A、线性表的线性存储结构优于链表存储结构B、二维数组是其数据元素为线性表的线性表C、栈的操作方式是先进先出D、队列的操作方式是先进后出2.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（A ）。

A、正确B、错误3.二维数组SA 中，每个元素的长度为3 个字节，行下标I 从0 到7，列下标J 从0 到9，从首地址SA 开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为（B）。

A、SA+141B、SA+180C、SA+222D、SA+2254.数组SA 中，每个元素的长度为3 个字节，行下标I 从0 到7，列下标J 从0 到9，从首地址SA 开始连续存放在存储器内，存放该数组至少需要的字节数是（ C ）。

A、80B、100C、240D、2705.常对数组进行的两种基本操作是（B ）。

A、建立与删除B、索引和修改C、查找和修改D、查找和索引6.将一个A[15][15]的下三角矩阵（第一个元素为A[0][0]），按行优先存入一维数组B[120]中，A 中元素A[6][5]在B 数组中的位置K 为（ B ）。

A、19B、26C、21D、157.若广义表A 满足Head(A)=Tail(A)，则A 为（B ）。

A、（）B、（（））C、（（），（））D、（（），（），（））8.广义表（（a）,a）的表头是（ C ），表尾是（C ）。

A、aB、bC、(a)D、((a))9.广义表（（a,b）,c,d）的表头是（ C ），表尾是（D ）。

A、aB、bC、(a,b)D、(c,d)10.广义表（（a））的表头是（ B ），表尾是（C ）。

A、aB、(a)C、()D、((a))11.广义表（a,b,c,d）的表头是（A ），表尾是（D ）。

A、aB、(a)C、(a,b)D、(b,c,d)12.广义表（（a,b,c,d））的表头是（C ），表尾是（B ）。

【课后习题】第4章 串 第5章 数组和广义表网络工程2010级（ ）班 学号： 姓名：题 号 一 二 三 四 总分 得 分一、填空题（每空1分，共30分）1. 串有三种机内表示方法： 、 和 ，其中前两种属于顺序存储结构，第三种属于 。

2. 若n 为主串长度，m 为子串长度，则串的BF （朴素）匹配算法最坏的情况下需要比较字符的总次数为 ,T(n)= 。

3. 是任意串的子串；任意串S 都是S 本身的子串，除S 本身外，S 的其他子串称为S 的 。

4. 设数组a[1…50, 1…60]的基地址为1000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[32,58]的存储地址为 。

5. 对于数组，比较适于采用 结构够进行存储。

6. 广义表的深度是指_______。

7. 将一个100100 A 的三对角矩阵，按行优先存入一维数组B[297]中，A 中元素66,66A 在B 数组中的位置k 为 。

8. 注意：a i,j 的k 为 2(i-1)+j-1,(i=1时j=1,2;1<i<=n 时,j=i-1,i,i+1) 。

9. 称为空串； 称为空白串。

10. 求串T 在主串S 中首次出现的位置的操作是 ，其中 称为目标串， 称为模式。

11. 对称矩阵的下三角元素a[i,j]，存放在一维数组V 的元素V[k]中（下标都是从0开始）， 12. k 与i ，j 的关系是：k= 。

13. 在n 维数组中每个元素都受到 个条件的约束。

14. 同一数组中的各元素的长度 。

15. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 、 和 。

16.稀疏矩阵中有n个非零元素，则其三元组有行。

17.求下列广义表操作的结果：18.（1）GetHead【((a,b),(c,d))】=== ;19.（2）GetHead【GetTail【((a,b),(c,d))】】=== ;20.（3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== ;21.（4）GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== ;22.广义表E=(a,(b,E)),则E的长度= ，深度= ；二、判断题（如果正确，在下表对应位置打“√”，否则打“⨯”。

第五章数组和广义表：习题习题一、选择题1．假设以行序为主序存储二维数组A[1．．100,1．．100]，设每个数据元素占两个存储单元，基地址为10，则LOC(A[5，5])=( )。

A. 808B. 818C. 1010D. 10202．同一数组中的元素( )。

A. 长度可以不同 B．不限 C．类型相同 D. 长度不限3．二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。

从供选择的答案中选出应填入下列关于数组存储叙述中( )内的正确答案。

(1)存放A至少需要( )个字节。

(2)A的第8列和第5行共占( )个字节。

(3)若A按行存放，元素A[8]【5]的起始地址与A按列存放时的元素( )的起始地址一致。

供选择的答案：(1)A. 90 B. 180 C. 240 D. 270(2) A. 108 B. 114 C. 54 D. 60(3)[8][5] B. A[3][10] [5][8] [O][9]4.数组与一般线性表的区别主要是( )。

A.存储方面B.元素类型方面C.逻辑结构方面D.不能进行插入和删除运算5．设二维数组A[1．．m，1．．n]按行存储在数组B[1．．m×n]中，则二维数组元素A[i，j]在一维数组B中的下标为( )。

A. (i-l)×n+jB. (i-l)×n+j-lC．i×(j-l) D. j×m+i-l6．所谓稀疏矩阵指的是( )。

A.零元素个数较多的矩阵B.零元素个数占矩阵元素中总个数一半的矩阵C.零元素个数远远多于非零元素个数且分布没有规律的矩阵D.包含有零元素的矩阵7．对稀疏矩阵进行压缩存储的目的是( )。

A.便于进行矩阵运算B.便于输入和输出C.节省存储空间D. 降低运算的时间复杂度8．稀疏矩阵一般的压缩存储方法有两种，即( )。

A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表9．有一个100×90的稀疏矩阵，非0元素有10个，设每个整型数占两字节，则用三元组表示该矩阵时，所需的字节数是( )。

第五章 数组和广义表一、选择题1、设广义表L=((a ，b ，c))，则L 的长度和深度分别为（ ）。

A. 1和1B. 1和3C. 1和2D. 2和32、广义表((a),a)的表尾是（ ）。

A. aB. (a)C. ()D. ((a))3、设有一个10阶的对称矩阵A ，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（ ）。

A. 13B. 33C. 18D. 404、一个非空广义表的表头（ ）。

A. 不可能是子表B. 只能是子表C. 只能是原子D. 可以是子表或原子5、设矩阵A 是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中，对下三角部分中任一元素ai,j(i>=j)，在一维数组B 的下标位置k 的值是（ ）。

A. i(i-1)/2+j-1B. i(i-1)/2+jC. i(i+1)/2+j-1D. i(i+1)/2+j6、广义表G=(a,b(c,d,(e,f)),g)的长度是（ ）。

A. 3B. 4C. 7D. 87、采用稀疏矩阵的三元组表形式进行压缩存储，若要完成对三元组表进行转置，只要将行和列对换，这种说法（ ）。

A. 正确B. 错误C. 无法确定D. 以上均不对8、常对数组进行两种基本操作是（ ）。

A. 建立和删除B. 索引和修改C. 查找和修改D. 查找与索引9、对一些特殊矩阵采用压缩存储的目的主要是为了（ ）。

A. 表达变得简单B. 对矩阵元素的存取变得简单C. 去掉矩阵中的多余元素D. 减少不必要的存储空间的开销 10、假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（ ）。

A. ⎪⎪⎪⎪⎪⎭⎫ ⎝⎛--00405000000000706080 B. ⎪⎪⎪⎪⎪⎭⎫ ⎝⎛--00000004053000706080 C. ⎪⎪⎪⎪⎪⎭⎫ ⎝⎛--00405000073000006080D. ⎪⎪⎪⎪⎪⎭⎫ ⎝⎛--00000304050000706080二、判断题1、广义表中原子个数即为广义表的长度。

第五章数组和广义表习题一、选择题1.已知广义表LS＝((a,b,c),(d,e,f))，运用head和tail函数取出LS中原子e运算是。

A.head(tail(LS))B.tail (head(LS))C.head(tail(head(tail(LS))))D. head(tail(tail(head(LS))))2.若广义表A满足head(A)＝ tail(A)，则A为。

A.（）B.（（））C.（（）,（））D.（（）,（）,（））3.广义表A=(a,b,(c,d),(e,(f,g)))，则下面式子Head(Tail(Head(Tail(Tail(A)))))的值为。

A.（）B.（d）C.cD.d4.稀疏矩阵一般的压缩存储方法有 两种。

A.二维数组和三维数组B.三元组和散列表C.三元组和十字链表D.散列表和十字链表5.已知矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行优先存放在一维数组B[1…n(n-1)/2]中，对下三角部分中任一元素aij(i>=j)在一维数组B的下标位置k值是。

A.i(i-1)/2+j-1B. i(i-1)/2+jC. i(i+1)/2+j-1D. i(i+1)/2+j6.已知广义表L＝((x,y,z),a,(u,t,w))，从L表中取出原子u的运算是。

A.head(tail(tail(L)))B.tail(head(head(tail(L))))C.head(tail(head(tail(L))))D.head(head(tail(tail(L))))7.广义表L＝((a,b,c))，则L的长度和深度分别为。

A.1和1B.1和3C.1和2D.2和38. tail (head(((a,b,c,d,e))))= 。

A.aB.c,dC.D.(b,c,d,e)9.二维数组A[10…20,5…10]采用列序方式存储，每个数据元素占4个存储单元，且A[10,5]的存储地址是1000，则A[20,9]的地址是。

第五章数组与广义表一、假设有二维数组A6*8，每个元素用相邻的6个字节存储，存储器按字节编址。

已知A的起始存储位置（基地址）为1000。

计算：1、数组A的体积（即存储量）；2、数组A的最后一个元素a57的第一个字节的地址；3、按行存储时，元素a14的第一个字节的地址；4、按列存储时，元素a47的第一个字节的地址；答案：1、（6*8）*6=2882、loc(a57)=1000+(5*8+7)*6=1282或=1000+（288-6）=12823、loc(a14)=1000+(1*8+4)*6=10724、loc(a47)=1000+(7*6+4)*6=1276二、假设按低下标(行优先)优先存储整数数组A9*3*5*8时第一个元素的字节地址是100，每个整数占四个字节。

问下列元素的存储地址是什么？（1）a0000(2)a1111(3)a3125 (4)a8247答案：（1）100（2）loc(a1111)=100+(1*3*5*8+1*5*8+1*8+1)*4=776(3) loc(a3125)=100+(3*3*5*8+1*5*8+2*8+5)*4=1784(4) loc(a8247)=100+(8*3*5*8+2*5*8+4*8+7)*4=4416五、设有一个上三角矩阵（aij）n*n,将其上三角元素逐行存于数组B[m]中，（m 充分大），使得B[k]=aij且k=f1(i)+f2(j)+c。

试推导出函数f1,f2和常数C（要求f1和f2中不含常数项）。

答：K=n+(n-1)+(n-2)+…..+(n-(i-1)+1)+j-i=(i-1)(n+(n-i+2))/2+j-i所以f1(i)=(n+1/2)i-1/2i2f2(j)=jc=-(n+1)九、已知A为稀疏矩阵，试从空间和时间角度比较采用两种不同的存储结构（二维数组和三元组表）完成∑aii运算的优缺点。

（对角线求和）解：1、二维数组For(i=1;i<=n;i++)S=s+a[i][i];时间复杂度：O（n）2、for(i=1;i<=m.tu;i++)If(a.data[k].i==a.data[k].j) s=s+a.data[k].value;时间复杂度：O（n2）二十一、当稀疏矩阵A和B均以三元组表作为存储结构时，试写出矩阵相加的算法，其结果存放在三元组表C中。

数据结构练习题习题5 数组和广义表一、基本内容数组定义及表示方式；特殊矩阵和稀疏矩阵的压缩存储方法及运算的实现；广义表的逻辑结构和存储结构。

二、学习要点1.了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。

2．掌握对特殊矩阵进行压缩存储时的下标变换公式。

3．了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。

4．掌握广义表的结构特点及其存储表示方法，读者可根据自己的习惯掌握任意一种结构的链表5.1 单项选择题1. 常对数组进行的两种基本操作是____。

A. 建立与删除B. 索引和修改查找与索引2. 二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从0到9，则存放M 至少需要①_ _个字节；M数组的第8列和第5行共占②____个字节。

①3. 二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是____。

4. 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为____。

5. 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为____。

5.21. 已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是__ LOC (A[0][0])+(n*i+j)*k __。

2. 二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且A[0][0]的存储地址是200，则A[6][12]的地址是__ 200+（12*10+6）= 326_。

一、选择题1. 将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（B ）。

供选择的答案：三条对角线有元素值，其他没有A. 198B. 195C. 1972. 二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。

从供选择的答案中选出应填入下列关于数组存储叙述中（）内的正确答案。

（1）存放A至少需要（ E ）个字节；（2）A的第8列和第5行共占（ A ）个字节；（3）若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素（B ）的起始地址一致。

供选择的答案：（1）A. 90 B. 180 C. 240 D. 270 E. 540（2）A. 108 B. 114 C. 54 D. 60 E. 150（3）A. A[8,5] B. A[3,10] C. A[5,8] D. A[0,9]3. 设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-14. 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+15. 设二维数组A[1.. m，1..n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为( A )。

A.（i-1）*n+jB.（i-1）*n+j-1C. i*（j-1）D. j*m+i-16. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（B ）。