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) { n=1; q=p;p=p->next; while (p!=NULL && p->data==q->data) { } if (n>max) max=n; n++; p=p->next; 数据结构简明教程 } } return max; 上机实验题4 两个非空串s和t采用顺序存储结构存储，设计一个算法求这两个串最大公共子串，并用相关数据进行测试。 解：采用Index算法思路设计由顺序串s、t产生最大公共子串str。对应的程序如下： #include SqString s,t,str; Assign(s,\Assign(t,\printf(\SqString str; int midx=0,mlen=0,tlen,i=0,j,k; while (i for (i=0;i str.length=mlen; return str; //返回最大公共子串 //将最大公共子串复制到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 //继续扫描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) } printf(\ printf(\求s、t的最大公共子串str\\n\str=maxcomstr(s,t); printf(\ 练习题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]的第一个字节的地址分别是（ ④ ）和（ ⑤ ）。 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）稀疏矩阵的三元组表示中，每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的（ ）。 答：行下标、列下标和元素值 3. 算法设计题 （1）假定数组A[0..n-1]的n个元素中有多个零元素，设计一个算法将A中所有的非零元素依次移到A的前端。 解：从前向后找为零的元素A[i]，从后向前找非零的元素A[j]，将A[i]和A[j]进行交换。对应的算法如下： void move(ElemType A[],int n) { int i=0,j=n-1;