习题四
一、选择项
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小时内删除。