第4章-串(习题).doc

第四章 串一、选择题1.下面关于串得得叙述中,哪一个就是不正确得？( )(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) 其结果为( )(7 分)A.ABC#G0123 B.ABCD#2345 C.ABC#G2345 D.ABC#2345E.ABC#G1234 F.ABCD#1234 G.ABC#012343.设有两个串p 与q,其中q 就是p 得子串,求q 在p 中首次出现得位置得算法称为( )A.求子串 B.联接 C.匹配 D.求串长(2 分)4.已知串S=aaab,其Next 数组值为( )。(2 分)A.0123 B.1123 C.1231 D.12115.串 ababaaababaa 得next 数组为( )。A.9 B.2 C.6 D.456.字符串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 )(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 2C.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 2E.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(2 分)8.若串S=software,其子串得数目就是( )。(2 分)A.8 B.37 C.36 D.99.设S 为一个长度为n 得字符串,其中得字符各不相同,则S 中得互异得非平凡子串(非空且不同于S本身)得个数为( )。A.2n1 B.n2 C.(n2/2)+(n/2) D.(n2/2)+(n/2)1 E、 (n2/2)(n/2)1 F、其她情况10.串得长度就是指( )(3 分)A.串中所含不同字母得个数 B.串中所含字符得个数C.串中所含不同字符得个数 D.串中所含非空格字符得个数二、判断题1.KMP 算法得特点就是在模式匹配时指示主串得指针不会变小。( ) (1 分)2.设模式串得长度为m,目标串得长度为n,当nm 且处理只匹配一次得模式时,朴素得匹配(即子串定位函数)算法所花得时间代价可能会更为节省。( ) (1 分)3.串就是一种数据对象与操作都特殊得线性表。( )(1 分)二、填空题1.空格串就是指_(1)_,其长度等于_(2)_。(2 分)2.组成串得数据元素只能就是_。 (1 分)3.一个字符串中_称为该串得子串 。(1 分)4.INDEX(DATASTRUCTURE, STR)=_。 (2 分)5.设正文串长度为n,模式串长度为m,则串匹配得KMP 算法得时间复杂度为_。6.模式串P=abaabcac得next 函数值序列为_。(2 分)7.字符串ababaaab得nextval 函数值为_。(2 分)8.设T 与P 就是两个给定得串,在T 中寻找等于P 得子串得过程称为_(1)_,又称P 为_(2)_。(16/6 分)9.串就是一种特殊得线性表,其特殊性表现在_(1)_;串得两种最基本得存储方式就是_(2)_、_(3)_;两个串相等得充分必要条件就是_(4)_。 (4 分)10.两个字符串相等得充分必要条件就是_。(2 分)11.知U=xyxyxyxxyxy;t=xxy;ASSIGN(S,U);ASSIGN(V,SUBSTR(S,INDEX(s,t),LEN(t)+1);ASSIGN(m,ww)求REPLACE(S,V,m)= _。 (5 分)12.实现字符串拷贝得函数 strcpy 为:void strcpy(char *s , char *t) /*copy t to s*/ while (_) (3 分)13.下列程序判断字符串s 就是否对称,对称则返回1,否则返回0;如 f(abba)返回1,f(abab)返回0;int f(1)_)int i=0,j=0;while (sj)(2)_;for(j; ij & si=sj; i+,j);return(3)_) (3 分)14.下列算法实现求采用顺序结构存储得串s 与串t 得一个最长公共子串。程序(a)PROCEDURE maxstr(VAR s,t : orderstring; VAR index,length : integer);VAR i,j,k,length1:integer; con:boolean;BEGINindex :=0; length :=0; i :=1;WHILE(i=s、len) DOj:=1;WHILE (jlength) THEN index:=i; length:=length1; (3)_;ELSE (4)_;(5) _;END;程序(b)void maxstr(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(jlength) index=i; length=length1; (3)_;else (4) _;(5) _ (10 分)15.完善算法:求KMP 算法中next 数组。PROC get _next(t:string,VAR next:ARRAY1、t、len OF integer);BEGINj:=1; k:=(1)_; next1:=0;WHILE jt、len DOIF k=0 OR t、chj=t、chk THEN BEGIN j:=j+1; k:=k+1; nextj:=k;ENDELSE k:=(2)_;END;(4 分)16.下面函数index 用于求t 就是否为s 得子串,若就是返回t 第一次出现在s 中得序号(从1 开始计),否则返回0。例如:s=abcdefcdek,t=cde,则indse(s,t)=3, index(s,aaa)=0 。已知t,s 得串长分别就是mt,msFUNC index(s,t,ms,mt);i:=1;j:=1;WHILE (ims) AND (jmt THEN return (5)_; ELSE return (6)_ENDF;(6 分)17.阅读下列程序说明与pascal 程序,把应填入其中得( )处得字句写在答题纸上。程序说明:本程序用于判别输入得字符串就是否为如下形式得字符串:W&M$ 其中,子字符串M 就是子字符串W 得字符反向排列,在此假定W 不含有字符&与字符$,字符&用作W 与M 得分隔符,字符$用作字符串得输入结束符。例如,对输入字符串ab&ba$、11&12$、ab&dd$、&$,程序将分别输出Ok、(就是),No、(不就是)。程序PROGRAM accept(input,output);CONST midch=&; endch=$;VAR an:boolean; ch:char;PROCEDURE match(VAR answer: boolean);VAR ch1,ch2:char; f:boolean;BEGINread(ch1);IF ch1endchTHEN IF (1)_THEN BEGIN match(f);IF f THEN BEGIN read(ch2); answer:=(2)_ END ELSE answer:=falseENDELSE (3)_ELSE (4)_END;BEGINwriteln(Enter String:);match(an);IF an THEN BEGIN(5)_ IF (6)_ THEN writeln(Ok、) ELSE writeln(No、)ENDELSE writeln(No、)END、 (15 分)18.试利用下列栈与串得基本操作完成下述填空题。initstack(s) 置s 为空栈;push(s,x) 元素x 入栈;pop(s) 出栈操作;gettop(s) 返回栈顶元素;sempty(s) 判栈空函数;setnull(st) 置串st 为空串;length(st) 返回串st 得长度;equal(s1,s2) 判串s1 与s2 就是否相等得函数;concat(s1,s2) 返回联接s1 与s2 之后得串;sub(s,i,1) 返回s 中第i 个字符;empty(st) 判串空函数FUNC invert(pre:string; VAR exp:string):boolean;若给定得表达式得前缀式pre 正确,本过程求得与它相应得表达式exp 并返回“true”,否则exp为空串,并返回“false”。已知原表达式中不包含括弧,opset 为运算符得集合。VAR s:stack; i,n:integer; succ:boolean; ch: char;BEGINi:=1; n:=length(pre); succ:=true;(1)_; (2)_;WHILE (in) AND succ DOBEGIN ch:=sub(pre,i,l);IF (3)_ THEN (4)_ELSE IF (5)_THEN (6)_ELSE BEGINexp:=concat(7)_,(8)_);exp:=concat(9)_,(10)_);(11)_;END;i:=i+1END;IF (12)_THENBEGIN exp:=concat(exp,sub(pre,n,1); invert:=true ENDELSE BEGIN setnull(exp); invert:=false ENDEND;注意:每个空格只填一个语句。四、应用题1.名词解释:串 (3 分)2.描述以下概念得区别:空格串与空串。(2 分)3.两个字符串S1 与S2 得长度分别为m 与n。求这两个字符串最大共同子串算法得时间复杂度为T(m,n)。估算最优得T(m,n),并简要说明理由。 (6 分)4.设主串S=xxyxxxyxxxxyxyx,模式串T=xxyxy。请问:如何用最少得比较次数找到T 在S 中出现得位置？相应得比较次数就是多少？ (8 分)5.KMP 算法(字符串匹配算法)较Brute(朴素得字符串匹配)算法有哪些改进? (2分)6.已知模式串t=abcaabbabcab写出用KMP 法求得得每个字符对应得next 与nextval 函数值。(10 分)7.给出字符串abacabaaad在KMP 算法中得next 与nextval 数组。(5 分)8.令t=abcabaa,求其next 函数值与nextval 函数值。 (6 分)9.已知字符串cddcdececdea,计算每个字符得next 与nextval 函数得值。10.试利用KMP 算法与改进算法分别求p1=abaabaa与p2=aabbaab得next 函数与nextval 函数。(8 分)11.已知KMP 串匹配算法中子串为babababaa,写出next 数组改进后得next 数组信息值(要求写出数组下标起点)。12.求模式串T=abcaabbac 得失败函数Next(j)值。(5 分)13.字符串得模式匹配KMP 算法中,失败函数(NEXT)就是如何定义得?计算模式串p=aabaabaaabc中各字符得失败函数值、 (10 分)14.设字符串S=aabaabaabaac,P=aabaac(1)给出S 与P 得next 值与nextval 值;(2)若S 作主串,P 作模式串,试给出利用BF 算法与KMP 算法得匹配过程。(15 分)15.设目标为t=abcaabbabcabaacbacba,模式为p=abcabaa(1)计算模式p 得naxtval 函数值;(5 分)(2)不写出算法,只画出利用KMP 算法进行模式匹配时每一趟得匹配过程。(10 分)16.模式匹配算法就是在主串中快速寻找模式得一种有效得方法,如果设主串得长度为m,模式得长度为n,则在主串中寻找模式得KMP 算法得时间复杂性就是多少？如果,某一模式 P=abcaacabaca,请给出它得NEXT 函数值及NEXT 函数得修正值NEXTVAL 之值。(5 分)17.设目标为S=abcaabbcaaabababaabca,模式为P=babab,(1)手工计算模式P 得nextval 数组得值;(5 分)(2)写出利用求得得nextval 数组,按KMP 算法对目标S 进行模式匹配得过程。(10 分)18.用无回溯得模式匹配法(KMP 法)及快速得无回溯得模式匹配法求模式串T 得nextj值,添入下面表中:kmp 法求得得nextj值快速无回溯法求得得nextj值(25/4 分)19.在改进了得(无回溯)字符串模式匹配中,要先求next 数组得值。下面就是求nextval 值得算法。TYPE SAR=ARRAY1、m OF INTEGER;PTY=ARRAY1、m OF CHAR;PROCEDURE next2(P:PTY;VAR NEXTVAL:SAR);在模式P 中求nextval 数组得值1 1 BEGIN2 2 J:=1;NEXTVAL1:=0;K:=03 3 REPEAT4 4 IF (K=0) OR (PJ=PK)5 5 THEN J:=J+1;K:=K+1;6 6 IF PJ=PK7 7 THEN NEXTVALJ:=NEXTVALK8 8 ELSE NEXTVALJ:=K 9 9 ELSE K:=NEXTVALK10 10 UNTIL J=m11 11 END;算法中第4 行有PJ=PK,第六行中也有PJ=PK。两处比较语句相同。请分析说明此两处比较语句得含义就是什么？分析此算法在最坏情况下得时间复杂度就是多少？(6 分)20.在字符串模式匹配得KMP 算法中,求模式得next 数组值得定义如下:请问:(1)当j=1 时,为什么要取next1=0？(2)为什么要取maxK,K 最大就是多少？(3)其它情况就是什么情况,为什么取nextj=1?(8 分)21.给出KMP 算法中失败函数f 得定义,并说明利用f 进行串模式匹配得规则,该算法得技术特点就是什么？ (8 分) 22. 在模试匹配KMP 算法中所用失败函数f 得定义中,为何要求p1p2pf(j)为p1p2pj 两头匹配得真子串？且为最大真子串？(7 分)23.如果两个串含有相等得字符,能否说它们相等？(5 分)24.设S1,S2 为串,请给出使S1/S2=S2/S1 成立得所有可能得条件(/为连接符)。(3 分)25.已知:s (xyz),t (xz)y。试利用联结、求子串与置换等基本运算,将 s 转化为 t 。(5 分)第五部分、算法设计1.设s、t 为两个字符串,分别放在两个一维数组中,m、n 分别为其长度,判断t 就是否为s 得子串。如果就是,输出子串所在位置(第一个字符),否则输出0。(注:用程序实现) (10分)2.输入一个字符串,内有数字与非数字字符,如:ak123x456 17960?302gef4563,将其中连续得数字作为一个整体,依次存放到一数组中,例如123 放入,456 放入, 。编程统计其共有多少个整数,并输出这些数。(13 分)3. 以顺序存储结构表示串,设计算法。求串S 中出现得第一个最长重复子串及其位置并分析算法得时间复杂度。(15 分)类似本题得另外叙述有:(1)如果字符串得一个子串(其长度大于1)得各个字符均相同,则称之为等值子串。试设计一算法,输入字符串S,以“！”作为结束标志。如果串S 中不存在等值子串,则输出信息“无等值子串”,否则求出(输出)一个长度最大得等值子串。例如:若S=“abc123abc123!”,则输出“无等值子串”;若S=“abceebccadddddaaadd!”,则输出“ddddd”。4.假设串得存储结构如下所示,编写算法实现串得置换操作。(15 分)TYPE strtp =RECORDch: ARRAY1、maxlen OF char;curlen:0、maxlenEND;5.函数void insert(char*s,char*t,int pos)将字符串t 插入到字符串s 中,插入位置为pos。请用c 语言实现该函数。假设分配给字符串s 得空间足够让字符串t 插入。(说明:不得使用任何库函数)(10 分)6.设计一个二分检索得算法,在一组字符串中找出给定得字符串,假设所有字符串得长度为4。(1)简述算法得主要思想;(3 分)(2)用PASCAL 语言分别对算法中用到得类型与变量作出说明;(3 分)(3)用类PASCAL 语言或自然语言写算法得非递归过程; (8 分)(4)分析该算法得最大检索长度;(3 分)(5)必要处加上中文注释。(3 分)7.设计一PASCAL 或C 语言得函数 atoi(x)、其中X 为字符串,由09 十个数字符与表示正负数得组成,返回值为整型数值 。(7 分)8.已知字符串S1 中存放一段英文,写出算法format(s1,s2,s3,n),将其按给定得长度n 格式化成两端对齐得字符串S2, 其多余得字符送S3。(15 分)9.串以静态存储结构存储,结构如下所述,试实现串操作equal 算法、CONST maxlen=串被确认得最大长度TYPE strtp=RECORDch:ARRAY1、maxlen OF char;curlen:0、maxlenEND;(以一维数组存放串值,并设指示器curlen 指示当前串长) (12 分)10.编写程序,统计在输入字符串中各个不同字符出现得频度并将结果存入文件(字符串中得合法字符为AZ 这26 个字母与09 这10 个数字)。(10 分)11.写一个递归算法来实现字符串逆序存储,要求不另设串存储空间。12.已知三个字符串分别为s=ababcaabcbcaa,s=caab, s=bcb。利用所学字符串基本运算得函数得到结果串为:s=caabcbcaacaa,要求写出得到上结果串S所用得函数及执行算法。(10 分)13.S=“S1S2Sn”就是一个长为N 得字符串,存放在一个数组中,编程序将S 改造之后输出:(1)将S 得所有第偶数个字符按照其原来得下标从大到小得次序放在S 得后半部分;(2)将S 得所有第奇数个字符按照其原来得下标从小到大得次序放在S 得前半部分;例如:S=ABCDEFGHIJKL,则改造后得S 为ACEGIKLJHFDB。14.编一程序,对输入得一表达式(字符串),输出其TOKEN 表示。表达式由变量A,B,C,常数(数字)0,1,9,运算符+,*与括号“(”,“)”组成。首先定义符号得类码: 其次定义符号得TOKEN 表示:其中NAMEL 就是变量名表(不允许有相同名),CONST 就是常量表(不允许有相同数)。例如,假设有表达式(A+A*2)+2*B*3#,则将生成如下TOKENL:(20 分)