习题四 
一、单项选择题
1.下面关于串的的叙述中,哪一个是不正确的?(   
A.串是字符的有限序列          B.空串是由空格构成的串
C.模式匹配是串的一种重要运算  D.串既可以采用顺序存储,也可以采用链式存储
2.串是一种特殊的线性表,其特殊性体现在(    )。
A.可以顺序存储          B.数据元素是一个字符
C.可以链接存储          D.数据元素可以是多个字符
3.串的长度是指(   
A.串中所含不同字母的个数      B.串中所含字符的个数
C.串中所含不同字符的个数      D.串中所含非空格字符的个数
4.设有两个串pq,其中qp的子串,求qp中首次出现的位置的算法称为(   
A.求子串      B.联接      C.匹配        D.求串长
5.若串S=software,其子串的个数是(    )。
A8      B37      C36        D9
二、填空题
1.含零个字符的串称为______串。任何串中所含______的个数称为该串的长度。
2.空格串是指__                  __,其长度等于__                __
3.当且仅当两个串的______相等并且各个对应位置上的字符都______时,这两个串相等。一个串中任意个连续字符组成的序列称为该串的______串,该串称为它所有子串的______串。
4INDEX(‘DATASTRUCTURE’, ‘STR’)=________
5.模式串P=abaabcac’的next函数值序列为________
6下列程序判断字符串s 是否对称,对称则返回1,否则返回0;如 f("abba")返回1f("abab")返回0     
int f((1)__      ______)
    {int  i=0,j=0;
      while (s[j])(2)___        _____;
      for(j--; i<j  && s[i]==s[j]; i++,j--);
      return((3)___          ____)
    } 
7.下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。
void  maxcomstr(orderstring *s,*t; int index, length)
{int i,j,k,length1,con;
  index=0;length=0;i=1;
  while (i<=s.len)
{j=1;
while(j<=t.len)
{ if (s[i]= =t[j])
{ k=1;length1=1;con=1;
          while(con)
            if (1)          _ { length1=length1+1;k=k+1; } 
else (2)          __;
          if (length1>length) { index=i;  length=length1; }
          (3)__          __; 
  }
      else (4)              ___;
      }
    (5)            __
}  }
三、应用题
1.描述以下概念的区别:空格串与空串。
2.设有 A=”  ”,B="mule",C="old",D="my",试计算下列运算的结果(注:A+B是CONCAT(A,B)的简写,A="  "的 "  "含有两个空格)。
(a) A+B
(b) B+A
(c) D+C+B
(d) SUBSTR(B,3,2)
(e) SUBSTR(C,1,0)
(f) LENGTH(A)
(g) LENGTH(D)
(h) INDEX(B,D)
(i) INDEX(C,"d")
(j) INSERT(D,2,C)
字符串长度的正确表示(k) INSERT(B,1,A)
(l) DELETE(B,2,2)
(m) DELETE(B,2,0)
3.设主串S=xxyxxxyxxxxyxyx’,模式串T=xxyxy’。请问:如何用最少的比较次数到TS中出现的位置?相应的比较次数是多少?
4.给出字符串‘abacabaaad’在KMP算法中的nextnextval数组。
5.已知:s =“(xyz)+*”,t =“(xz)*y”。试利用联结、求子串和置换等基本运算,将 s 转化为 t
四、算法设计题
1.在顺序串上实现串的判等运算EQUAL(S,T)。
2.在链串上实现判等运算EQUAL(S,T)。
3.若S和T是用结点大小为1的单链表存储的两个串(S、T为头指针),设计一个算法将串S中首次与串T匹配的子串逆值。
4 以顺序存储结构表示串,设计算法。求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。(如果字符串的一个子串(其长度大于1)的各个字符均相同,则称之为等值子串。如果输入字符串S,以“!”作为结束标志。串S中不存在等值子串,则输出信息“无等值子串”,否则求出(输出)一个长度最大的等值子串。例如:若S=abc123abc123!”,则输出“无等值子串”;若S=abceebccadddddaaadd!”,则输出“ddddd”。)
5.写一个递归算法来实现字符串逆序存储,要求不另设串存储空间。

第四章 
一、单项选择题
1B
2. B
3B
4C
5. C
二、填空题
1.空、字符
2  由空格字符(ASCII32)所组成的字符串        空格个数
3.长度、相等、子、主
45
5
6.(1char s[ ]        (2) j++                    (3) i >= j
7[题目分析]本题算法采用顺序存储结构求串s和串t的最大公共子串。串si指针(1<=i<=s.len)。t串用j指针(1<=j<=t.len)。算法思想是对每个i1<=i<=s.len,即程序中
第一个WHILE循环),来求从i开始的连续字符串与从j1<=j<=t.len,即程序中第二个WHILE循环)开始的连续字符串的最大匹配。程序中第三个(即最内层)的WHILE循环,是当s中某字符(si])与t中某字符(tj])相等时,求出局部公共子串。若该子串长度大于已求出的最长公共子串(初始为0),则最长公共子串的长度要修改。
(1) i+k<=s.len && j+k<=t.len && s[i+k]==t[j+k]  //所有注释同上(a
  (2) con=0  (3) j+=k    (4) j++    (5) i++
三、应用题
1.空格是一个字符,其ASCII码值是32。空格串是由空格组成的串,其长度等于空格的个数。空串是不含任何字符的串,即空串的长度是零。
2(a)A+B                                  mule
  (b)B+A                                mule 
  (c)D+C+B                              myoldmule
  (d)SUBSTR(B,3,2)                      le
  (e)SUBSTR(C,1,0)                       
  (f)LENGTH(A)                        2
  (g)LENGTH(D)                        2
  (h)INDEX(B,D)                        0
  (i)INDEX(C,d)                        3
  (j)INSERT(D,2,C)                      myold
  (k)INSERT(B,1,A)                      m  ule
  (l)DELETE(B,2,2)                      me
  (m)DELETE(B,2,0)                      mule
3.朴素的模式匹配(BruteForce)时间复杂度是O(mn),KMP算法有一定改进,时间复杂度达到O(mn)。本题也可采用从后面匹配的方法,即从右向左扫描,比较6次成功。另一种匹配方式是从左往右扫描,但是先比较模式串的最后一个字符,若不等,则模式串后移;若相等,再比较模式串的第一个字符,若第一个字符也相等,则从模式串的第二个字符开始,向右比较,直至相等或失败。若失败,模式串后移,再重复以上过程。按这种方法,本题比较18次成功。

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。