数据结构第五章串和数组练习

基本概念题：

1 设S1 =“Data Structure Course”，S

2 =“Structure”，S

3 =“Base”，求：

（1）Length(S1)； 21

（2）（2）Compare(S2, S3)； 1

（3）Insert(S1, 5, S3)； DataBase Structure Course

（4）Delete(S1, 5, 9)； Datae Course

（5）SubString(S1, 5, 9, T)； Structur

（6）Search(S1, 0, S2)；

（7）Replace(S1, 0, S2, S3) Data Base Course

算法设计题：

2 设串采用静态数组存储结构，编写函数实现两个串的比较Compare(S, T)。要求比较结果有等于和不等于两种情况。

void compare(String s1,String s2){

int i=0;

else

while(i<=s1.length && s1.elem[i]!=s2.elem[i]){

i++;

}

if(i+1==s1.length)

cout<<"相等\n";

else

cout<<"不相等\n";

}

3 设串采用静态数组存储结构，编写函数实现两个串的比较Compare(S, T)。要求比较结果有大于、等于和小于三种情况。

void compare2(String s1,String s2){

int max,flag;

max=s1.length>=s2.length ? s1.length : s2.length;

for(int i=0;i

if(s1.elem[i]>s2.elem[i]){

flag=1;break;}

else

if(s1.elem[i]

flag=-1;break;}

else

continue;

}

if(flag==1)

cout<<"s1>s2\n";

if(flag==-1)

cout<<"s1

if(i==s1.length)

cout<<"s1=s2\n";

}

4 设串采用动态数组存储结构，编写函数实现两个串的比较Compare(S, T)。要求比较结果有大于、等于和小于三种情况。对比本题和习题4-13的算法，说明串的静态数组存储结构和串的动态数组存储结构是否对编写串的比较算法有影响。

静态数组存储结构，要定义字符串长度，且字符长度必须达到那么长。

动态数组存储结构，可按实际需要来确定字符长度。

5 设串采用静态数组存储结构，编写函数实现串的替换Replace(S, start, T, V)，即要求在主串S中，从位置start开始查找是否存在子串T，若主串S中存在子串T，则用子串V替换子串T，且函数返回1；若主串S中不存在子串T，则函数返回0。

Replace(char *S,int start,char *T,char *V){

int i,j,k,l,n,m,s,count=0,signal=0;

n=strlen(T);/*求字符串长度*/

m=strlen(V);

s=strlen(S);

for(i=start-1;S[i]!='\0';i++)/*开始查找*/

{

k=i;

j=0;

while(S[k]==T[j])/*与子串T对比*/

{

k++;

j++;

}//while

if(T[j]=='\0')/*判断是否T存在*/

{

if(m-n>0)/*第一种情况，字符串V比T长的情况下*/

{

for(l=s+(m-n)*(count+1)-1;l>=k;l--)

S[l]=S[l-m+n];

for(l=k-n,j=0;j

S[l]=V[j];

count++;

}

else

if(m-n<0)/*第二种情况，字符串V比T短的情况下*/

{

for(l=k-n,j=0;j

S[l]=V[j];

for(;l

S[l]=S[l+n-m];

count++;

}

else/*第三种情况，T和V一样长*/

{

for(l=k-1;l>=k-n;l--,j--)

S[l]=V[j-1];

}

signal=1;

} //if

}//for

S[s+(m-n)*count]='\0';

if(signal)

return 1;/*返回值*/

else

return 0;

}//Replace

6 设字符串采用静态数组的顺序存储结构，

（1）编写算法删除字符串s中值等于ch的一个字符，并分析该算法的时间复杂度；

void delchar(char *s, char ch)

{

while(*s)

{

if(*s == ch) //找到第一个ch

break;

s++;

}

while(*s) //开始删除

{

*s = *(s+1);

s++;

}

}

（2）编写算法删除字符串s中值等于ch的所有字符。

void delchar(char *a,char ch){

int i,j;

for(i=0,j=0;i

if(a[i]!=ch)

a[j++]=a[i];

a[j]='\0';

}

7 设字符串采用单字符的链式存储结构，编写删除串s从位置i开始长度为k的子串的算法。

8 设一个系统中二维数组采用以行序为主的存储方式存储，已知二维数组a[n][m]中每个数据元素占k个存储单元，且第一个数据元素的存储地址是Loc(a[0][0])，求数据元素a[i][j](0≤i≤n-1, 0≤j≤m-1)的存储地址。

Loc(a[i][j])=Loc(a[0][0])+(i*m+j)*k

9 设一个系统中二维数组采用以行序为主的存储方式存储，已知二维数组a[10][8]中每个数据元素占4个存储单元，且第一个数据元素的存储地址是1000，求数据元素a[4][5]的存储地址。

Loc(a[4][5])=1000+(4*8+5)*4=1148

10设矩阵A、矩阵B和矩阵C为采用压缩存储方式存储的n阶上三角矩阵，矩阵元素为整数类型，要求：

（1）编写实现矩阵加C = A + B的函数。

(完整word版)数据结构第五章数组和广义表习题及答案

习题五数组和广义表 一、单项选择题 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]*k B.Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k C.Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k D.Loc[i,j]=[(n+1)*i+j]*k 3．稀疏矩阵的压缩存储方法是只存储 ( ) A.非零元素 B. 三元祖（i,j, aij） C. aij D. i,j 4. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。 A. 1175 B. 1180 C. 1205 D. 1210 5. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。 A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+1 6. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为( )。 A. j=r[j].next B. j=j+1 C. j=j->next D. j=r[j]-> next 7. 对稀疏矩阵进行压缩存储目的是（）。 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））的表头是（），表尾是（）。 A. a B.（） C.（a,b,c,d） D.（b,c,d） 10. 设广义表L=（（a,b,c）），则L的长度和深度分别为（）。 A. 1和1 B. 1和3 C. 1和2 D. 2和3 11. 下面说法不正确的是( )。 A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构 二、填空题 1．通常采用___________存储结构来存放数组。对二维数组可有两种存储方法：一种是以___________为主序的存储方式，另一种是以___________为主序的存储方式。 2. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B 中的第8个元素是A 中的第_ _行，第_ _列的元素。

数据结构 第五章数组和广义表

第五章数组和广义表：习题 习题 一、选择题 1．假设以行序为主序存储二维数组A[1．．100,1．．100]，设每个数据元素占两个存储单元，基地址为10，则LOC(A[5，5])=( )。 A. 808 B. 818 C. 1010 D. 1020 2．同一数组中的元素( )。 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+j B. (i-l)×n+j-l C．i×(j-l) D. j×m+i-l 6．所谓稀疏矩阵指的是( )。 A.零元素个数较多的矩阵 B.零元素个数占矩阵元素中总个数一半的矩阵 C.零元素个数远远多于非零元素个数且分布没有规律的矩阵 D.包含有零元素的矩阵 7．对稀疏矩阵进行压缩存储的目的是( )。 A.便于进行矩阵运算 B.便于输入和输出 C.节省存储空间 D. 降低运算的时间复杂度 8．稀疏矩阵一般的压缩存储方法有两种，即( )。 A.二维数组和三维数组 B.三元组和散列 C.三元组和十字链表 D.散列和十字链表 9．有一个100×90的稀疏矩阵，非0元素有10个，设每个整型数占两字节，则用三元组表示该矩阵时，所需的字节数是( )。 A. 60 B. 66 C．18000 D．33 10. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N(N+I)/2] 中，则对任一上三角元素a[i][j]对应T[k]的下标k是( )。 A. i(i-l)/2+j B. j(j-l)/2+i C. i(j-i)/2+1 D. j(i-l)/2+1 11．已知广义表L=((x，y,z)，a，(u，t，w))，从L表中取出原子项t的运算是( ) A. head(tail(tail(L))) B. tail(head(head(taiI(L)))) C. head(tail(head(taiI(L)))) D. head(tail(head(tail(tail(L)))))

数据结构复习题 答案 新编新

第5章数组与广义表 一、选择题（每小题1分，共10分） 1.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ A ）。 A.110 B.108 C.100 D.120 2.在数组A中，每一个数组元素A[i][j]占用3个存储字节，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字节数是（ C ）。 A.80 B.100 C.240 D.270 3.假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为（ C ）。（无第0行第0列元素） A.16902 B.16904 C.14454 D.答案A, B, C均不对 4.将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（ A ）。 A. 198 B. 195 C. 197 D.196

5.数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是（ A ）。 A. 1175 B. 1180 C. 1205 D. 1210 6.假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]= （ B ）。 A. 808 B. 818 C. 1010 D. 1020 7. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为（ B ）。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 8.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ B ）。 A、 13 B、 33 C、 18 D、 40 9. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（ B ）的起始地址相同。设每个字符占一个字节。 A、 A[8,5] B、 A[3,10] C、 A[5,8] D、 A[0,9]

数据结构 第4—5章串和数组自测卷答案

第4～5章串和数组自测卷答案姓名班级 一、填空题（每空1分，共20分） 1. 不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。 2. 设S=“A;/document/Mary.doc”，则strlen(s)= 20 , “/”的字符定位的位置为3。 4. 子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。 5. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 6 次匹配成功。 6. 若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m。 7. 假设有二维数组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列开始！) 8.设数组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＝8950 9. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素 的行下标、列下标和元素值。 10.求下列广义表操作的结果： （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）; 二、单选题（每小题1分，共15分） （ D ）1.串是一种特殊的线性表，其特殊性体现在： Ａ．可以顺序存储Ｂ．数据元素是一个字符 Ｃ．可以链式存储Ｄ．数据元素可以是多个字符 （ B ）2.设有两个串p和q，求q在p中首次出现的位置的运算称作：

数据结构(C语言版)第5章 数组和广义表

第 5 章数组和广义表 一、选择题 为第一元素，其 1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a 11 的地址为（）。【燕山大学 2001 一、2 存储地址为1，每个元素占一个地址空间，则a 85 （2分）】 A. 13 B. 33 C. 18 D. 40 2. 有一个二维数组A[1:6，0:7] 每个数组元素用相邻的6个字节存储，存储器按字节编址， 那么这个数组的体积是（①）个字节。假设存储数组元素A[1，0]的第一个字节的地址是0， 则存储数组A的最后一个元素的第一个字节的地址是（②）。若按行存储，则A[2，4]的第 一个字节的地址是（③）。若按列存储，则A[5，7]的第一个字节的地址是（④）。就一般情 况而言，当（⑤）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。供选择的 答案：【上海海运学院 1998 二、2 （5分）】 ①-④： A．12 B. 66 C. 72 D. 96 E. 114 F. 120 G. 156 H. 234 I. 276 J. 282 K. 283 L. 288 ⑤： A．行与列的上界相同 B. 行与列的下界相同 C. 行与列的上、下界都相同 D. 行的元素个数与列的元素个数相同 3. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10， 数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 【南京理工大学 1997 一、8 （2分）】 4. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存 储单元，基地址为10，则LOC[5，5]=（）。【福州大学 1998 一、10 (2分)】 A. 808 B. 818 C. 1010 D. 1020 5. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000 的内存单元中，则元素A[5，5]的地址是( )。【南京理工大学 2001 一、13 （1.5分）】 A. 1175 B. 1180 C. 1205 D. 1210 6. 有一个二维数组A[0:8,1:5],每个数组元素用相邻的4个字节存储，存储器按字节编址， 假设存储数组元素A[0,1]的第一个字节的地址是0，存储数组A的最后一个元素的第一个字 节的地址是（①）。若按行存储，则A[3,5]和 A[5,3]的第一个字节的地址是（②） 和（③）。若按列存储，则A[7,1]和A[2,4]的第一个字节的地址是（④）和（⑤）。【上海海运学院 1996 二、1 （5分）】 ①-⑤:A.28 B.44 C.76 D.92 E.108 F.116 G.132 H.176 I.184 J.188 7. 将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元 （即该元素下标i=66，j=65），在B数组中的位置K为（）。供选择的答案： 素A 6665 A. 198 B. 195 C. 197 【北京邮电大学 1998 二、5 （2分）】 8. 二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈 从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中（）内的正确答案。（1）存放A至少需要（）个字节； （2）A的第8列和第5行共占（）个字节； （3）若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素（）的起始地

数据结构 串和数组 练习试题

第4～5章串和数组自测卷姓名班级 一、填空题（每空1分，共20分） 1. 称为空串；称为空白串。 2. 设S=“A;/document/Mary.doc”，则strlen(s)= , “/”的字符定位的位置为。 4. 子串的定位运算称为串的模式匹配；称为目标串，称为模式。 5. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第次匹配成功。 6. 若n为主串长，m为子串长，则串的古典匹配算法最坏的情况下需要比较字符的总次数为。 7. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为；末尾元素A57的第一个字节地址为；若按行存储时，元素A14的第一个字节地址为；若按列存储时，元素A47的第一个字节地址为。 8. 设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为。 9. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的、和。 10.求下列广义表操作的结果： （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))】】】=== ; 二、单选题（每小题1分，共15分） （）1. 串是一种特殊的线性表，其特殊性体现在： Ａ．可以顺序存储Ｂ．数据元素是一个字符 Ｃ．可以链式存储Ｄ．数据元素可以是多个字符 （）2. 设有两个串p和q，求q在p中首次出现的位置的运算称作： Ａ．连接Ｂ．模式匹配Ｃ．求子串Ｄ．求串长 （）3. 设串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))的结果串是： Ａ．BCDEF Ｂ．BCDEFG Ｃ．BCPQRST Ｄ．BCDEFEF

数据结构课后习题及解

数据结构课后习题及解析第五章

第五章习题 5.1 假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A的基地址为 1000，计算： 数组A共占用多少字节； 数组A的最后一个元素的地址； 按行存储时元素A 36 的地址； 按列存储时元素A 36 的地址； 5.2 设有三对角矩阵A n×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]= a ij ， 求： （1）用i,j表示k的下标变换公式； （2）用k表示i,j的下标变换公式。 5.3假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放 结果矩阵。 5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个 辅助向量空间。 5.5写一个在十字链表中删除非零元素a ij 的算法。 5.6画出下面广义表的两种存储结构图示： ((((a), b)), ((( ), d), (e, f))) 5.7求下列广义表运算的结果： （1）HEAD[((a,b),(c,d))]; （2）TAIL[((a,b),(c,d))]; （3）TAIL[HEAD[((a,b),(c,d))]]; （4）HEAD[TAIL[HEAD[((a,b),(c,d))]]]; （5）TAIL[HEAD[TAIL[((a,b),(c,d))]]];

实习题 若矩阵A m×n 中的某个元素a ij 是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该 矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。 第五章答案 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

(习题)数据结构第五章 数组与广义表

第五章数组与广义表 5.1 假设有二维数组A6×8,每个元素用相邻的6个字节存储，存储器按字节编址。已知A 的起始存储位置（基地址）为1000，计算： (1)数组A的体积（即存储量）； (2)数组A的最后一个元素a57的第一个字节的地址； (3)按行存储时，元素a14的第一个字节的地址； (4)按列存储时，元素a47的第一个字节的地址。 5.2 若矩阵A m×n中的某个元素a i×j是第I行中的最小值，同时又是第j列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵A m×n，试编写求出矩阵中所有马鞍点的算法，并分析你的算法在最坏情况下的时间复杂度。 5.3 现有如下的稀疏矩阵A如图所示，要求画出以下各种表示法。 (1)三元组表示法； (2)伪地址表示法； (3)带行指针向量的单链表示法； (4)十字链表法。 5.4 求下列广义表操作的结果： ⑴GetHead【(p,h,w)】 ⑵GetTAil【(b,k,p,h)】 ⑶GetHead【((a,b),(c,d))】 ⑷GetTail【((a,b),(c,d))】 ⑸GetHead【GetTail【((a,b),(c,d))】】 ⑹GetTail【GetHead【((a,b),(c,d))】】 ⑺GetHead【GetTail【GetHead【((a,b),(c,d))】】】 ⑻GetTail【GetHead 【GetTail 【((a,b),(c,d))】】】 注意：【】是函数的符号。 5.5 利用广义表的GetHead和GetTail操作写出如上题的函数表达式，把原子banana分别从下列广义表中分离出来。 ⑴L1=(apple,pear,banana,orange); ⑵L2=((apple,pear),(banana,orange)); 5.6 下述广义表的长度和深度各是多少？ ⑴L1=((a),((b),c),(((d)))); ⑵L2=(a,(a,b),d,e,((i,j),k));

数据结构数组和串自测题答案

串和数组自测卷答案姓名班级 一、填空题（每空1分，共20分） 1. 不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。 （对应严题集4.1①，简答题：简述空串和空格串的区别） 2. 设S=“A;/document/Mary.doc”，则strlen(s)= 20 , “/”的字符定位的位置为3。 4. 子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。 5. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 6 次匹配成功。 6. 若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m。 7. 假设有二维数组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列开始！) 8. 〖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＝8950 9. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素 的行下标、列下标和元素值。 二、单选题（每小题1分，共15分） （ B ）1.串是一种特殊的线性表，其特殊性体现在： Ａ．可以顺序存储Ｂ．数据元素是一个字符 Ｃ．可以链式存储Ｄ．数据元素可以是多个字符 （ B ）2.设有两个串p和q，求q在p中首次出现的位置的运算称作： Ａ．连接Ｂ．模式匹配Ｃ．求子串Ｄ．求串长 （ D ）3.设串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))的结果串是：

中南大学数据结构与算法第5章数组和广义表课后作业答案

第5章数组与广义表习题练习答案 5.1请按行及按列优先顺序列出四维数组A2*3*2*3的所有元素在内存中的存储次序，开始结点为a0000。 解： 按行优先的顺序排列时，先变化右边的下标，也就是右到左依次变化，这个四维数组的排列是这样的：(将这个排列分行写出以便与阅读，只要按从左到右的顺序存放就是在内存中的排列位置) a0000a0001a0002 a0010a0011a0012 a0100a0101a0102 a0110a0111a0112 a0200a0201a0202 a0210a0211a0212 a1000a1001a1002 a1010a1011a1012 a1100a1101a1102 a1110a1111a1112 a1200a1201a1202 a1210a1211a1212 按列优先的顺序排列恰恰相反，变化最快的是左边的下标，然后向右变化，所以这个四维数组的排列将是这样的，(这里为了便于阅读，也将其书写为分行形式)： a0000a1000 a0100a1100 a0200a1200 a0010a1010 a0110a1110 a0210a1210 a0001a1001 a0101a1101

a0201a1201 a0011a1011 a0111a1111 a0211a1211 a0002a1002 a0102a1102 a0202a1202 a0012a1012 a0112a1112 a0212a0212 5.2 给出C语言的三维数组地址计算公式。 解： 因为C语言的数组下标下界是0，所以 Loc(A mnp)=Loc(A000)+((i*n*p)+k)*d 其中Amnp表示三维数组。Loc(A000)表示数组起始位置。i、j、k表示当前元素的下标,d表示每个元素所占单元数。 5.3设有三对角矩阵A n*n，将其三条对角线上的元素逐行地存储到向量B[0...3n-3]中，使得B[k]=a ij,求： (1)用i , j 表示k的下标变换公式。 (2)用k 表示i,j 的下标变换公式。 (1) 解： 要求i,j 到k 的下标变换公式，就是要知道在k之前已有几个非零元素，这些非零元素的个数就是k 的值，一个元素所在行为i,所在列为j,则在其前面已有的非零元素个数为： (i*3-1)+j-(i+1) 其中(i*3-1)是这个元素前面所有行的非零元素个数，j-(i+1)是它所在列前面的非零元素个数 化简可得： k=2i+j; // c下标是从0开始的。

数据结构练习题-数组和广义表

已知二维数组A[3][5]，其每个元素占3个存储单元，并且A[0][0]的存储地址为1200。 求元素A[1][3]的存储地址（分别对以行序和列序为主序存储进行讨论），该数组共占用多少个存储单元？ 【解答】按照以行序为主序存储公式： LOC(i，j)=LOC(c1，c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*L 在C语言中有：LOC(i，j)=LOC(0，0)+(i*(d2+1)+j)*L 则： LOC(A[1][3])=1200+(1*5+3)*3=1224 (按行序存储) LOC(A[1][3])=1200+(3*3+1)*3=1230 (按列序存储) 有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，A[1][1]为第一元素，其存储地址为1，每个元素占一个地址空间，求A[7][5]和A[5][6]的地址。 【解答】按照公式： LOC(A[7][5])=7(7-1)/2＋5 = 26 LOC(A[5][6])=LOC(A[6][5])=6(6-1)/2+5=20 设有一个二维数组A[m][n]，设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]存放在什么位置？ 因为A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，说明一行有15个元素（算法：（676－2－644）/2）。A[3][3]存放位置是692。 二维数组A[9][10]的元素都是6个字符组成的串，请回答下列问题： （1）存放A至少需要( )个字节； （2）A的第7列和第4行共占( )个字节； （3）若A按行存放，元素A[7][4]的起始地址与A按列存放时哪一个元素的起始地址一致。 【解答】按照题5.1给出的公式： （1）存放A需要9*10*6=540个字节 （2）A的第7列和第行共占(9+10-1)*6=108个字节（3） LOC(A[7][4])= LOC(A[0][0])+[7*10+4]*L (按行序存储) LOC(A[i][j])= LOC(A[0][0])+[j*9+i]*L （按列序存储，0<=i<=8,0<=j<=9)所以,i=2,j=8。 即元素A[7][4]的起始地址与A按列存放时A[2][8]的起始地址一致。 什么是广义表？请简述广义表和线性表的主要区别。 【解答】广义表是零至多个元素的有限序列，广义表中的元素可以是原子，也可以是子表。 从“元素的有限序列”角度看，广义表满足线性结构的特性：在非空线性结构中，只有一个 称为“第一个”的元素，只有一个称为“最后一个”的元素，第一元素有后继而没有前驱， 最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说， 广义表属于线性结构。当广义表中的元素都是原子时，广义表就蜕变为线性表。 求广义表D=(a，(b，()，c)，((d)，e))的长度和深度。 【解答】3和3

数据结构数组和广义表自测题(附答案)

第4～5章串和数组 一、填空题 1. 不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。 2. 设S=“A;/document/Mary.doc”，则strlen(s)= 20, “/”的字符定位的位置为3。 4. 子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。 5. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第6次匹配成功。 6. 若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为 (n-m+1)*m。 7. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基 1282；若按行地址）为1000，则数组A的体积（存储量）为288 B ；末尾元素A 57的第一个字节地址为 (8+4)×6+1000=1072；若按列存储时，元素A47的第一个字节地址存储时，元素A 14的第一个字节地址为 为(6×7＋4)×6＋1000）＝1276。(注：数组是从0行0列还是从1行1列计算起呢？由末单元为A 57可知，是从0行0列开始！) 8.设数组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＝8950 9. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素 的行下标、列下标和元素值。 10.求下列广义表操作的结果： （1）GetHead【((a,b),(c,d))】=== (a, b) ; //头元素不必加括号 （2）GetHead【GetTail【((a,b),(c,d))】】=== (c,d) ;

《数据结构》第五章 数组 习题

《数据结构》第五章 数组 习题 基本概念题： 5-1 分别写出一维数组和二维数组的存储映象公式。 5-2 什么叫二维数组的行序优先存储？什么叫二维数组的列序优先存储？C 语言采用的是行序优先存储还是列序优先存储？ 5-3 什么叫随机存储结构？为什么说数组是一种随机存储结构？ 5-4 动态数组和静态数组在使用方法上有什么不同？ 5-5 什么样的矩阵叫特殊矩阵？特殊矩阵压缩存储的基本思想是什么？ 5-6 什么样的矩阵叫稀疏矩阵？稀疏矩阵压缩存储的基本思想是什么？ 5-7 什么叫稀疏矩阵的三元组？什么叫稀疏矩阵的三元组线性表？ 5-8 稀疏矩阵主要有哪些压缩存储结构？ 复杂概念题： 5-9 设一个系统中二维数组采用以行序为主的存储方式存储，已知二维数组a[n][m]中每个数据元素占k 个存储单元，且第一个数据元素的存储地址是Loc(a[0][0])，求数据元素a[i][j](0≤i≤n -1, 0≤j≤m -1)的存储地址。 5-10 设一个系统中二维数组采用以行序为主的存储方式存储，已知二维数组a[10][8]中每个数据元素占4个存储单元，且第一个数据元素的存储地址是1000，求数据元素a[4][5]的存储地址。 5-11 画出一个3行3列二维动态数组存储结构示意图。 5-12 对于如下所示的稀疏矩阵A （1）写出该稀疏矩阵的三元组线性表； （2）画出稀疏矩阵A 的三元组顺序表结构； （3）画出稀疏矩阵A 的带头结点单链表结构； （4）画出稀疏矩阵A 的行指针数组链表结构； （5）画出稀疏矩阵A 的三元组十字链表结构。 算法设计题： 5-13 为节省内存，n 阶对称矩阵采用压缩存储，要求： （1）编写实现C = A + B 操作的函数。设矩阵A 、矩阵B 和矩阵C 均采用压缩存储方式存储，矩阵元素均为整数类型。 （2）编写一个采用压缩存储的n 阶对称矩阵的输出函数，要求输出显示成矩阵形式，设矩阵元素均为整数类型。 （3）设矩阵A 和矩阵B 为如下所示的矩阵，编写一个用矩阵A 和矩阵B 作为测试例子的测试上述函数的主程序。 ?????????? ????????????=0000000033000220000000000001900000000000090000500000A

《数据结构》习题集：第5章_数组与广义表

第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+141 B、SA+180 C、SA+222 D、SA+225 4.数组SA 中，每个元素的长度为3 个字节，行下标I 从0 到7，列下标J 从0 到9，从首地址SA 开始连续 存放在存储器内，存放该数组至少需要的字节数是（ C ）。 A、80 B、100 C、240 D、270 5.常对数组进行的两种基本操作是（B ）。 A、建立与删除 B、索引和修改 C、查找和修改 D、查找和索引 6.将一个A[15][15]的下三角矩阵（第一个元素为A[0][0]），按行优先存入一维数组B[120]中，A 中元素A[6][5] 在B 数组中的位置K 为（ B ）。 A、19 B、26 C、21 D、15 7.若广义表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、D

数据结构课后习题及解析第五章

第五章习题 5.1 假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A的基地址为 1000，计算： 数组A共占用多少字节； 数组A的最后一个元素的地址； 按行存储时元素A 36 的地址； 按列存储时元素A 36 的地址； 5.2 设有三对角矩阵A n×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]= a ij ， 求： （1）用i,j表示k的下标变换公式； （2）用k表示i,j的下标变换公式。 5.3假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表C存放 结果矩阵。 5.4在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个 辅助向量空间。 5.5写一个在十字链表中删除非零元素a ij 的算法。 5.6画出下面广义表的两种存储结构图示： ((((a), b)), ((( ), d), (e, f))) 5.7求下列广义表运算的结果： （1）HEAD[((a,b),(c,d))]; （2）TAIL[((a,b),(c,d))]; （3）TAIL[HEAD[((a,b),(c,d))]]; （4）HEAD[TAIL[HEAD[((a,b),(c,d))]]]; （5）TAIL[HEAD[TAIL[((a,b),(c,d))]]];

实习题 若矩阵A m×n 中的某个元素a ij 是第i行中的最小值，同时又是第j列中的最大值，则称此元素为该 矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。 第五章答案 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

数据结构 第五章 数组与广义表作业及答案

第五章数组与广义表作业（50分） 一、选择题（每题 2 分，共20 分）。 1．两个串相等必有（ A ，D（或写D也可以得全分））。 A．串长度相等 B．串长度任意 C．串中各位置字符任意 D．串中各位置字符均对应相等 2．对称矩阵的压缩存储：以行序为主序存储下三角中的元素，包括对角线上的元素。二维下标为( i, j ),存储空间的一维下标为k，给出k与i, j (i