数据结构课程课后习题答案. 下载本文

练习题及参考答案 答:所有可能的条件为: (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)稀疏矩阵的三元组表示中,每个结点对应于稀疏矩阵的一个非零元素,它包含有三个数据项,分别表示该元素的( )。

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