一. 选择

1. 以下叙述正确的是（A）。

A. 串是一种特殊的线性表                            B. 串的长度必须大于0

C. 串中元素只能是字母                               D. 空串就是空白串 

2. 已知模式串T="abcdabcd"，则其next数组值是（B）。

A. 00123412        B. 01111234        C. 01232412         D. 11213412 

3. 设有两个串S1和S2，求串S2在S1中首次出现位置的运算称作（C）。

A. 连接                B. 求子串              C. 模式匹配             D. 判断子串 

4. 已知串S='aaab'，则next值为（A）。

A. 0123                B. 1123                 C. 1231               D.1211      

5. 设串 s1='ABCDEFG'，s2='PQRST'，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是（D）。

A. BCDEF            B. BCDEFG            C. BCPQRST           D. BCDEFEF 

6. 设串长为n，模式串长为m，则KMP算法的平均时间复杂度为（D）。

A. O(m)                 B. O(n)                  C. O(m*n)                D. O(m+n) 

7. 串是一种特殊的线性表，其特殊性体现在（B）。

A. 可以顺序存储          B. 数据元素是一个字符       

C. 可以随机存储          D. 数据元素是多个字符 

8. 若串s1="bc_cad_cabcadf"，串s2="abc"，则s2在s1中的位置是（D）。

A. 7                B. 8                C. 6               D.9 

9. 若一个串的长度为8，则其子串的总个数为（B）。

A. 8               B. 37             C. 36             D. 9 

二. 填空 

1. 串的两种最基本的存储方式是顺序存储和链式存储。 

2. 一个字符串中任意连续字符组成的子序列称为该串的子串。 

3. 模式串T="abcaabbcabca"的next值为 011122311234。

三. 判断题 

1. 空串是由一个或多个空格字符组成的串。                                                                （×） 

2. 当两个字符串的长度相等时，则可判定这两个串相等。                                           （×） 

3. 串是由有限个字符构成的连续序列，子串是主串中字符构成的有限序列。               （×）

4. 子串定位函数的时间复杂度在最坏的情况下为O(M*N)，因此子串定位函数没有实际应用价值。                                                                                                                               （×）

5. KMP算法的最大特点是指示主串的指针无序回溯。                                                   （√）