第4章串
习题
一、 选择题
1、如下陈述中正确的是（    ）
A．串是一种特殊的线性表        B．串的长度必须大于零
C．串中元素只能是字母          D．空串就是空白串
2、设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（    ）
A．求子串      B．联接      C．匹配        D．求串长
3、串”ababaaababaa”的next数组为（    ）。
A．012345678999  B．012121111212  C．011234223456    D．0123012322345
4、串是_____________。
A.不少于一个字母的序列  B.任意个字母的序列
C.不少于一个字符的序列  D.有限个字符的序列
5、串的长度是指（    ）
A．串中所含不同字母的个数      B．串中所含字符的个数
C．串中所含不同字符的个数      D．串中所含非空格字符的个数
二、填空题
1、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为________。。
2、一个字符串中________称为该串的子串 。
3、串是一种特殊的线性表，其特殊性表现在__ __；串的两种最基本的存储方式是____、__ __；两个串相等的充分必要条件是____ 。
4、INDEX（‘MY STUDENT’， ‘STU’）=________。
5、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为________。
6、设串S的长度为n,则S的子串个数为________
7、字符串”mnmnmmmn”的nextval函数值为________。
8、设T和P是两个给定的串，在T中寻等于P的子串的过程称为__ __，又称P为_ __。
9、下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f("abba")返回1，f("abab")返回0；     
int f(_______)
    {int  i=0,j=0;
      while (s[j])________;字符串长度的正确表示
      for(j--; i<j  && s[i]==s[j]; i++,j--);
      return(_______);
    } 
三、 判断题
1、KMP算法的特点是在模式匹配时指示主串的指针不会变小。
2、设模式串的长度为m,目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。
3、next函数值序列的产生仅与模式串有关。
4、空格串就是由零个字符组成的字符序列。 
5、从串中取若干个字符组成的字符序列称为串的子串。
四、 应用题
1、空串与空格串有何区别？字符串中的空格符有何意义？
2、 串的存储结构有几种？各有何特点？
3、两个字符串S1和S2的长度分别为m和n。求这两个字符串最大共同子串算法的时间复杂度为T(m,n)。估算最优的T(m,n)，并简要说明理由。
4、设主串S=‘xxyxxxyxxxxyxyx’，模式串T=‘xxyxy’。请问：如何用最少的比较次数到T在S中出现的位置？相应的比较次数是多少？
5、给出字符串‘abacabaaad’在KMP算法中的next和nextval数组   
五、 算法设计
1、利用C的库函数strlen，strcpy写一算法 void StrDelete(char *S,int i,int m)删除串S中从位置i开始的连续m个字符。若i≥strlen(S),则没有字符被删除；若i+m≥strlen(S),则将S中位置I开始直至末尾的字符都删去。
2、设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，判断t是否为s的子串。如果是，输出子串所在位置（第一个字符），否则输出0。
3、输入一个字符串，内有数字和非数字字符，如：ak123x456 17960?302gef4563，将其中连续的数字作为一个整体，依次存放到一数组ａ中，例如123放入a［０］,456放入ａ［１］，…　…　。编程统计其共有多少个整数，并输出这些数。
4、已知串a和b，试以下两种方式编写算法，求得所有包含在a中而不在b中的字符构成的新串r。
（1） 利用串的基本操作来实现；
（2） 以串的顺序存贮结构来实现。
5、编写一个算法frequency，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。
6、设x和y是表示成单链表的两个字符串，试写一个算法，出x中第一个不在y中出现的字符（假定每个结点只存放一个字符）。
7、已知字符串S1中存放一段英文，写出算法format(s1,s2,s3,n),将其按给定的长度n格式化成两端对齐的字符串S2, 其多余的字符送S3。
8、写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。
9、写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。
10、S=“S1S2…Sn”是一个长为N的字符串，存放在一个数组中，编程序将S改造之后输出：
（1）将S的所有第偶数个字符按照其原来的下标从大到小的次序放在S的后半部分；
（2）将S的所有第奇数个字符按照其原来的下标从小到大的次序放在S的前半部分；
例如：
S=‘ABCDEFGHIJKL’
则改造后的S为‘ACEGIKLJHFDB’。

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