习题四
一、选择项
l．空串与空格串（ B ）。
A．相同 B．不相同 C．可能相同 D．无法确定
2．设有两个申S1与S2，求串S2在S1中首次出现位置的运算称作（ C ）。
A．连接 B．求子串 C．模式匹配 D．判子串
3．串与普通的线性表相比较，它的特殊性体现在（ C ）。
A．顺序的存储结构 B．链接的存储结构
C．数据元素是一个字符 D．数据元素可以任意
4．设有串S=‘Computer’，则其子串的数目是（ A ）。
A．36 B．37 C．8 D．9
二、境空题
1．串是由零个或多个字符组成的有限序列。通常记作：s＝“c1，c2，…，cn”(n=>0)，其中，S称为串名；串中的Ci（1<=i<=n）可以是字母、数字 字格或其他字符。用双引号括起来的部分是串值．即串S的内容。
2．串中字符的个数称为串的长度。
3．不含有任何字符的串称为空串，它的长度为零。
4．由一个或多个空格构成的串称为空格串，它的长度为空格的个数。
5．串中任意多个连续字符组成的子序列称为该串的子串；包含子串的串称为主串。
6．字符在序列中的序号称为该字符在串中的位置。
7．两个字符串相等是指两个字符串的，也就是说这两个字符串不仅值相等，而且对应位置上长度相等的字符也相等。
8．两个串的比较实际上是ASCII码的比较。两个串从第一个位置上的字符开始进行比较，当第一次出现ASCII码大的串为大，若比较过程中出现一个字符串结束的情况，则另一个串为、较大者。
9．串的顺序存储结构就是把串所包含的字符序列，依次存人连续的存储单元中去。
10．有些计算机系统中为了充分利用存储空间，允许一个存储单元可以存放多个字
符，串的这种存储方式是一种紧缩式存储方式。
11．串的非紧缩存储方式是以存储单元为存储单位，一个存储单元中只存放一个字符。在这种情况下，即使一个存储单元能存放多个字符，这时候也只存放一个字符。
12．串在非紧缩方式下，串长度的存储是隐式的，串所占用的存储单元的个数即串的长度。
13．一些计算机是以字节为存取单位，恰好一个字符占用一个字节，自然形成了每个存储单元存放一个字符的分配方式，这种方式就是一种单字节存储方式。这种方式一般不需要存放串长的存储单元，而需要以程序中各变量值所不包含的字符为结束符。
14．串的链式存储结构是将存储区域分成一系列大小相同的结点，每个结点有两个城：数据域和指针域。其中数据域用于存放数据，指针域用于存放下一个结点的指针。
15．子串定位StrIndex (s，t)，也称为模式匹配，是返回串t在s主串中的位置。
三、判断回
1．子串是主串中字符构成的有限序列。（错误：子串是主串中连续字符构成的有限序列。 ）
2．KMP算法的最大特点是指示主串的指针不需要回溯。（正确 ）
3．串中的元素只能是字符。（正确：注意字符可以是字母、数字或计算机能表达的其他符号。 ）
4．串中的元素只可能是字母。（错误：可以是数字或其他字符 ）
5．串是一种特殊的线性表。（正确 ）
6．串中可以包含有空白字符。（ 正确 ）
7．串的长度不能为零。（错误：串可以是空串、长度可以为零 ）
8．两个串相等必有串长度相同。（ 正确 ）
9．两个串相等则各位置上字符必须对应相等。（ 正确 ）
四、综合题
l．编写算法实现将窜S1中的第 i个字符到第 j个字符之间的字符(不包括第 i个字符和第j个字符)之间的字符用串S2替换。假设串的存储结构为：
＃define MAXSIZE 81
struct string{
int len；
char ch［MAXSIZE］；
｝stringtype；
void replace (stringtype s1[], int i, int j, stringtype s2[])
{字符串长度17模式串长度8
stringtype s[100];
int h,k;
if ( i<=h && i<s1.len && j<s1.len )
{
for (h=1; h<=i; h++ )
s.ch[h]=s1.ch[h]; /*把s1的前i个字符赋值给s*/
s.len=i;
h=1;
while(h<s2.len) /*连接串s2*/
{
s.ch[s.len+h]=s2.ch[h];
h++;
}
s.len=s.len+s2.len;
for ( k=s.len+1; h=j; h<=s1.len; h++,k++ )
s.ch[k]=s1.ch[h]; /*将s1串中从第j个字符开始到结束的字符连接到s串*/
s.len=k;
s.ch[s.len]='\0';
}
return(s);
}
2．设计一个算法，测试一个串S是否回文（所谓回文是指从左面读起和从右面读起内容一样）。
int invert(stringtype *s)
{
/*判断是否回文*/
int i, j;
j=length(s)%2;
for ( i=0; i<j; i++ )
if (( SubStr(s,i,1) != SubStr(s, s.len-i+1,1))
return ( 0 ); /*返回False*/
return(1) /*返回True*/
}/*invert*/
3．写一个递归算法来实现字符的逆序存储，要求不另设存储空间。
void reverse ( stringtype *s )
{
char c;
int i;
i=1;
printf("Please char, '#' is the end.\n");
do
{
scanf("%c",&c);
Reverse(s);
s.ch[i]=c;
i++;
}while(c!='#'&&i<n)
}/*reverse*/
4．一个仅由字母组成的字符串s，长度为n，其结构为单链表，每个结点的数据城只存放一个字母。设计一个算法，去掉字符串中所有值为X的字母。
void sjt4( linklist *s, char x )
{
linklist *p,*q,*r;
int w;
p=s;
w=1;
while ( p!=NULL )
{
if ( w==1 ) /*处理第一个结点*/
if(p->data==x)/*删除第一个结点*/
{
s=p->next;
free(p);
p=s;
}
else
{
q=p;
p=p->next;
w=0;
}
else /*处理其他结点*/
{
if ( p->data==x) /*删除值为x的结点*/
{
q->next=p->next;
free (p);
p=q->next;
}
else
{
q=p;
p=p->next;
}
}
}
} /*sjt4*/
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论