数据结构考研精编1800题（四）

松花江里的鱼

第四章 串
　　一、选择题
　　1.下面关于串的的叙述中，哪一个是不正确的?( )【北方交通大学 2001 一、5(2分)】
　　A.串是字符的有限序列 B.空串是由空格构成的串
　　C.模式匹配是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储
　　2 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行
　　concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2)))
　　其结果为( )【北方交通大学 1999 一、5 (25/7分)】
　　A.ABC###G0123 B.ABCD###2345 C.ABC###G2345 D.ABC###2345
　　E.ABC###G1234 F.ABCD###1234 G.ABC###01234
　　3.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为( )
　　A.求子串 B.联接 C.匹配 D.求串长
　　【北京邮电大学 2000 二、4(20/8分)】【西安电子科技大学 1996 一、1 (2分)】
　　4.已知串S=‘aaab’,其Next数组值为( )。【西安电子科技大学 1996 一、7 (2分)】
　　A.0123 B.1123 C.1231 D.1211
　　5.串 ‘ababaaababaa’ 的next数组为( )。【中山大学 1999 一、7】
　　A.012345678999 B.012121111212 C.011234223456 D.0123012322345
　　6.字符串‘ababaabab’ 的nextval 为( )
　　A.(0,1,0,1,04,1,0,1) B.(0,1,0,1,0,2,1,0,1)
　　C.(0,1,0,1,0,0,0,1,1) D.(0,1,0,1,0,1,0,1,1 )
　　【北京邮电大学 1999 一、1(2分)】
　　7.模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为( )，nextval数组的值为 ( )。
　　A.0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B.0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2
　　C.0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D.0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2
　　E.0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F.0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1
　　【北京邮电大学 1998 二、3 (2分)】
　　8.若串S=’software’,其子串的数目是( )。【西安电子科技大学 2001应用一、2(2分)】
　　A.8 B.37 C.36 D.9
　　9.设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串(非空且不同于S本身)的个数为( )。【中科院计算所 1997 】
　　A.2n-1 B.n2 C.(n2/2)+(n/2) D.(n2/2)+(n/2)-1 E. (n2/2)-(n/2)-1 F.其他情况
　　10.串的长度是指( )【北京工商大学 2001 一、6 (3分)】
　　A.串中所含不同字母的个数 B.串中所含字符的个数
　　C.串中所含不同字符的个数 D.串中所含非空格字符的个数
海文专业课 http://www.VIPkaoyan.com/