第5章 数组和广义表答案

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章 串 第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 为 。

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

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

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

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

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

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

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

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

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

第四、五章串、数组和广义表练习题答案一．填空题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.建立与删除B. 索引与修改C. 查找与修改D. 查找与索引2．对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由( )式确定.A.Loc[i,j]=A[m,n]+[(n+1)*i+j]*kB.Loc[i,j]=loc[0,0]+[(m+n)*i+j]*kC.Loc[i,j]=loc[0,0]+[(n+1)*i+j]*kD.Loc[i,j]=[(n+1)*i+j]*k3．稀疏矩阵的压缩存储方法是只存储 ( )A.非零元素B. 三元祖（i,j, aij）C. aijD. i,j4. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。

A. 1175B. 1180C. 1205D. 12105. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。

A. i（i-1）/2+jB. j（j-1）/2+iC. i（j-i）/2+1D. j（i-1）/2+16. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为( )。

A. j=r[j].nextB. j=j+1C. j=j->nextD. j=r[j]-> next7. 对稀疏矩阵进行压缩存储目的是（）。

A．便于进行矩阵运算 B．便于输入和输出C．节省存储空间 D．降低运算的时间复杂度8. 已知广义表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))))9. 广义表（（a,b,c,d））的表头是（），表尾是（）。

第5章数组和⼴义表答案第五章答案5.2设有三对⾓矩阵A n×n,将其三条对⾓线上的元素逐⾏的存于数组B[1..3n-2]中，使得B[k]=a ij，求：（1）⽤i,j表⽰k的下标变换公式；（2）⽤k表⽰i、j的下标变换公式。

【解答】（1）k=2(i-1)+j(2) i=[k/3]+1, j=[k/3]+k%3 （[ ]取整，%取余）5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的⽅法稍加改动，使算法只占⽤⼀个辅助向量空间。

【解答】算法（⼀）FastTransposeTSMatrix(TSMartrix A, TSMatrix *B){/*把矩阵A转置到B所指向的矩阵中去，矩阵⽤三元组表表⽰*/int col,t,p,q;int position[MAXSIZE];B->len=A.len; B->n=A.m; B->m=A.n;if(B->len>0){position[1]=1;for(t=1;t<=A.len;t++)position[A.data[t].col+1]++; /*position[col]存放第col-1列⾮零元素的个数, 即利⽤pos[col]来记录第col-1列中⾮零元素的个数*/ /*求col列中第⼀个⾮零元素在B.data[ ]的位置，存放在position[col]中*/ for(col=2;col<=A.n;col++)position[col]=position[col]+position[col-1];for(p=1;p{col=A.data[p].col;q=position[col];B->data[q].row=A.data[p].col;B->data[q].col=A.data[p].row;B->data[q].e=A.data[p].e;Position[col]++;}}}算法(⼆)FastTransposeTSMatrix(TSMartrix A, TSMatrix *B){int col,t,p,q;int position[MAXSIZE];B->len=A.len; B->n=A.m; B->m=A.n;if(B->len>0){for(col=1;col<=A.n;col++)position[col]=0;for(t=1;t<=A.len;t++)position[A.data[t].col]++; /*计算每⼀列的⾮零元素的个数*//*从最后⼀列起求每⼀列中第⼀个⾮零元素在B.data[]中的位置，存放在position[col]中*/ for(col=A.n,t=A.len;col>0;col--) { t=t-position[col];position[col]=t+1;}for(p=1;p{col=A.data[p].col;q=position[col];B->data[q].row=A.data[p].col;B->data[q].col=A.data[p].row;B->data[q].e=A.data[p].e;Position[col]++;}}}5.6画出下⾯⼴义表的两种存储结构图⽰：((((a), b)), ((( ), d), (e, f)))【解答】第⼀种存储结构第⼆种存储结构5.7求下列⼴义表运算的结果：（1）HEAD[((a,b),(c,d))]; (a,b) （2）TAIL[((a,b),(c,d))]; ((c,d)) （3）TAIL[HEAD[((a,b),(c,d))]]; (b)（4）HEAD[TAIL[HEAD[((a,b),(c,d))]]]; b（5）TAIL[HEAD[TAIL[((a,b),(c,d))]]]; (d)。

第5章数组和广义表答案第 5 章数组和广义表一、选择1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ B ）。

A. 13B. 33C. 18D. 402. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为(B )。

A. BA+141B. BA+180C. BA+222D. BA+2253. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（ B ）。

A. 808B. 818C. 1010D. 10204. 二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从0到9。

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

（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[4,9]C. A[5,8]D. A[0,9]5. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i<="" b="" p="">A. i*(i-1)/2+jB. j*(j-1)/2+iC. i*(i+1)/2+jD. j*(j+1)/2+i6. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（ B ）。

第五章数组和广义表5.18⑤试设计一个算法，将数组A中的元素A[0..n-1]循环右移k位，并要求只用一个元素大小的附加存储，元素移动或交换次数为O(n)。

要求实现以下函数：void Rotate(Array1D &a, int n, int k);一维数组类型Array1D的定义：typedef ElemType Array1D[MAXLEN];void Rotate(Array1D &a, int n, int k)/* a[n] contains the elements, *//* rotate them right circlely by k sits */{int i,b=n-1,m=n;int t,c=k/n,r,g,d,e;r=k-c*n;e=r;while(r!=0){g=r;d=m/r;r=m-d*r;m=g;}for(;b>n-1-m;--b){ElemType q=a[b];i=b;t=b+e-n;if(t<0){t=b+e;}while(i!=t){if(i<e){a[i]=a[i+n-e];i=i+n-e;}else{a[i]=a[i-e];i-=e;}}//whilea[t]=q;}//for}5.21④假设稀疏矩阵A和B均以三元组表作为存储结构。

试写出矩阵相加的算法，另设三元组表C存放结果矩阵。

要求实现以下函数：Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C);/* 三元组表示的稀疏矩阵加法: C=A+B */稀疏矩阵的三元组顺序表类型TSMatrix的定义：#define MAXSIZE 20 // 非零元个数的最大值typedef struct {int i,j; // 行下标,列下标ElemType e; // 非零元素值}Triple;typedef struct {Triple data[MAXSIZE+1]; // 非零元三元组表,data[0]未用int mu,nu,tu; // 矩阵的行数、列数和非零元个数}TSMatrix;Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C)/* 三元组表示的稀疏矩阵加法: C=A+B */{if( A.mu != B.mu || A.nu != B.nu )return ERROR;C.mu=A.mu;C.nu=A.nu;C.tu=0;int pa=1;int pb=1;int pc=1;ElemType ce;int x;for(x=1;x<=A.mu;x++) //对矩阵的每一行进行加法{while(A.data[pa].i<x) pa++;while(B.data[pb].i<x) pb++;while(A.data[pa].i==x&&B.data[pb].i==x) //行列值都相等的元素{if(A.data[pa].j==B.data[pb].j){ce=A.data[pa].e+B.data[pb].e;if(ce) //和不为0{C.data[pc].i=x;C.data[pc].j=A.data[pa].j;C.data[pc].e=ce;pa++;pb++;pc++;}}//ifelse if(A.data[pa].j>B.data[pb].j){C.data[pc].i=x;C.data[pc].j=B.data[pb].j;C.data[pc].e=B.data[pb].e;pb++;pc++;}else{C.data[pc].i=x;C.data[pc].j=A.data[pa].j;C.data[pc].e=A.data[pa].e;pa++;pc++;}}//whilewhile(A.data[pa].i==x) //插入A中剩余的元素(第x行) {C.data[pc].i=x;C.data[pc].j=A.data[pa].j;C.data[pc].e=A.data[pa].e;pa++;pc++;}while(B.data[pb].i==x) //插入B中剩余的元素(第x行) {C.data[pc].i=x;C.data[pc].j=B.data[pb].j;C.data[pc].e=B.data[pb].e;pb++;pc++;}}//forC.tu=pc;return OK;}//TSMatrix_Add5.26③试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。

第5章数组和广义表本章所讨论的多维数组和广义表是对线性表的推广，其特点是数据元素仍可被视为一个表。

要求熟悉多维数组的逻辑结构、存储结构，广义表的逻辑结构、表示形式，以及矩阵的压缩存储的有关内容。

重点提示：●多维数组的存储方式和存取特点●特殊矩阵的存储●稀疏矩阵的存储●广义表的表示形式5-1 重点难点指导5-1-1 相关术语1．特殊矩阵要点：矩阵中非零元素或零元素的分布有一定规律的矩阵。

2．对称矩阵要点：一种特殊矩阵；n阶方阵的元素满足性质：a ij=a ji（0≤i，j≤n-1）。

3．三角矩阵要点：以主对角线划分，有上三角矩阵和下三角矩阵两种；主对角线以下，不包括主对角线中的元素，均为常数c，称为上三角矩阵；主对角线以上，不包括主对角线中的元素，均为常数c，称为下三角矩阵。

4．对角矩阵要点：非零元素集中在以主对角线为中心的带状区域中，也称带状矩阵。

5．稀疏矩阵要点：矩阵中非零元素的个数远小于矩阵元素总数的矩阵。

6．三元组表要点：是稀疏矩阵的一种存储结构；将稀疏矩阵的非零元素的三元组（行、列和值）按行优先的顺序排列；得到结点均是三元组的线性表。

7．广义表要点：是线性表的推广；是n个元素a1,a2,…,a n的有限序列；其中a i或者是原子或者是广义表；通常记为LS=(a1,a2,…,a n)，LS为广义表的名字。

5-1-2 多维数组1．对n维数组逻辑结构的理解n维数组可视为由n-1维数组为元素的线性结构。

举例：一个m行n列的二维数组可视为由m个一维数组为元素组成的线性结构，其中每个一维数组又由n 个单元素组成。

]a ,,a ,[a A A A A a a a a a a a a a Amn in i2i1i m 21mnv m2m12n 22211n 1211 =⎪⎪⎪⎪⎪⎭⎫⎝⎛=⎪⎪⎪⎪⎪⎭⎫⎝⎛=其中2．数组的顺序存储方式（1）行优先顺序——将数组元素按行向量排列，即第i ＋1行紧接在第i 行后面。

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

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。