练习题及参考答案 答：所有可能的条件为： （1）s1和s2为空串

（2）s1或s2其中之一为空串 （3）s1和s2为相同的串

（4）若两串长度不等，则长串由整数个短串组成。 4. 算法设计题

（1）设计一个算法RepChar(s,x,y)，将顺序串s中所有字符x替换成字符y。要求空间复杂度为O(1)。

解：因要求算法空间复杂度为O(1)，所以只能对串s直接替换。从头开始遍历串s，一旦找到字符x便将其替换成y。对应算法如下：

void RepStr(SqString &s,char x,char y) { }

int i;

for (i=0;i

if (s.data[i]==x)

s.data[i]=y;

（2）设计一个算法，判断链串s中所有元素是否为递增排列的。

解：用p和q指向链串s的两个连续结点，p先指向开始结点，当q->data≥p->data时，p和q同步后移一个结点；否则返回0。当所有元素是递增排列时返回1。对应算法如下：

int increase(LinkString *s) { }

LinkString *p=s->next,*q; if (p!=NULL) { }

return 1;

while (p->next!=NULL) { }

q=p->next;

p=q;

//逆序时返回0

return 0;

//q指向*p的后续结点

if (q->data>=p->data) else

（3）假设以链式结构存储一个串s，设计一个算法求串s中最长等值子串。

解：假设串用带头结点的单链表存储串s。用max存放最大平台长度，扫描串s，计算一个平台的长度n，若n大于max，则置max为n。对应的算法如下：

int maxlength(LinkString *s) {

int n,max=0;

LinkString *p=s->next,*q; while (p!=NULL)

25

数据结构简明教程

}

{ }

return max;

n=1;

q=p;p=p->next;

while (p!=NULL && p->data==q->data) { }

if (n>max) max=n;

n++; p=p->next;

上机实验题4

两个非空串s和t采用顺序存储结构存储，设计一个算法求这两个串最大公共子串，并用相关数据进行测试。

解：采用Index算法思路设计由顺序串s、t产生最大公共子串str。对应的程序如下：

#include #include \ {

SqString str;

int midx=0,mlen=0,tlen,i=0,j,k; while (i

for (i=0;i

str.length=mlen;

//将最大公共子串复制到str中

str.data[i]=s.data[midx+i]; j=0; { } i++;

//继续扫描s中第i字符之后的字符

while (j

if (s.data[i]==t.data[j]) //找一子串,在s中下标为i,长度为tlen { }

else j++;

tlen=1;

for (k=1;i+k

j+=tlen;

//继续扫描t中第j+tlen字符之后的字符

&& s.data[i+k]==t.data[j+k];k++)

//将较大长度者赋给midx与mlen

tlen++; midx=i; mlen=tlen;

//用(midx,mlen)保存最大公共子串 //用i扫描串s //用j扫描串t

//包含顺序串的基本运算函数

SqString maxcomstr(SqString s,SqString t)

if (tlen>mlen)

}

void main() { }

SqString s,t,str;

Assign(s,\Assign(t,\printf(\printf(\

printf(\求s、t的最大公共子串str\\n\str=maxcomstr(s,t);

printf(\return str;

练习题及参考答案 //返回最大公共子串

练习题5

1. 单项选择题

（1）假设有60行70列的二维数组a[1..60,1..70]（数组下标从1开始）以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为（ ）。

A.16902 B.16904 C.14454 D.以上都不对 答：A

（2）对特殊矩阵采用压缩存储的目的主要是为了（ ）。 A.表达变得简单 B.对矩阵元素的存取变得简单 C.去掉矩阵中的多余元素 D.减少不必要的存储空间 答：D

（3）一个n×n的对称矩阵，如果采用压缩存储以行或列为主序放入内存，则压缩存储的容量是（ ）。 A. n2 B. n2/2 C. n(n+1)/2 D. (n+1)2/2

答：C

（4）设矩阵a是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组b[1..n(n-1)/2]中（数组下标均从1开始），对下三角部分中任一元素ai,j（i≤j）在一维数组b中下标k的值是（ ）。

A.i(i-1)/2+j-1 B.i(i-1)/2+j C.i(i+1)/2+j-1 D.i(i+1)/2+j 答：B

（5）有一个二维数组A，行下标的范围是0～8，列下标的范围是1～5，每个数组元素用相邻的4个字节存储。存储器按字节编址。假设存储数组元素A[0,1]的第一个字节的地址是0。存储数组A的最后一个元素的第一个字节的地址是（ ① ）。若按行存储，则A[3,5]和A[5,3]的第一个字节的地址分别是（ ② ）和（ ③ ）。若按列存储，则A[7,1]和A[2,4]的第一个字节的地址分别是（ ④ ）和（ ⑤ ）。

27

数据结构简明教程

A.28 B.44 C.76 D.92 E.108 F.116 G.132 H.176 I.184 J.188 答：①H ②C ③E ④A ⑤F

（6）有一个二维数组A，行下标的范围是1～6，列下标的范围是0～7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是（ ① ）个字节。假设存储数组元素A[1,0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是（ ② ）。若按行存储，则A[2,4]的第一个字节的地址是（ ③ ）。若按列存储，则A[5,7]的第一个字节的地址是（ ④ ）。

A.12 B.66 C.72 D.96 E.114 F.120

G.156 H.234 I.276 J.282 K.283 L.288 答：①L ②J ③C ④I

（7）稀疏矩阵一般的压缩存储方法有两种，即（ ）。 A.二维数组和三维数组 B.三元组和散列 C.三元组和十字链表 D.散列和十字链表 答：C 2. 填空题

（1）三维数组A[c1..d1,c2..d2,c3..d3]（c1≤d1，c2≤d2，c3≤d3）共含有（ ）个元素。 答：(d1-c1+1)×(d2-c2+1)×(d3-c3+1)。

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

答：LOC(A[0][0])+(n×i+j)×k。 （3）二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且A[0][0]的存储地址是200，则A[6][12]的地址是（ ）。

答：326

（4）二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是（ ）。

答：1208

（5）有一个10阶对称矩阵A，采用压缩存储方式（以行序为主存储下三角部分，且A[0][0]存放在B[1]中），则A[8][5]在B中的地址是（ ）。

答：42 （6）设n阶下三角矩阵A[1..n][1..n]已压缩到一维数组S[1..n(n+1)/2]中，若按行序为主存储，则A[i][j]对应的S中的存储位置是（ ）。

答：i(i-1)/2+j。

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

答：行下标、列下标和元素值