《第4章-串(习题)》由会员分享，可在线阅读，更多相关《第4章-串(习题)（10页珍藏版）》请在金锄头文库上搜索。
1、第四章 串一、选择题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 分）AABC#G0123 BABCD#2345 CABC#G2345 DABC#2345EABC#G1234 FABCD#123
2、4 GABC#012343设有两个串p 和q，其中q 是p 的子串，求q 在p 中首次出现的位置的算法称为（ ）A求子串 B联接 C匹配 D求串长（2 分）4已知串S=aaab,其Next 数组值为（ ）。（2 分）A0123 B1123 C1231 D12115串 ababaaababaa 的next 数组为（ ）。A012345678999 B012121111212 C011234223456 D01230123223456字符串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
3、,1) D(0,1,0,1,0,1,0,1,1 )（2 分）7模式串t=abcaabbcabcaabdab，该模式串的next 数组的值为（ ），nextval 数组的值为 （ ）。A0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2C0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2E0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1（2
4、 分）8若串S=software,其子串的数目是（ ）。（2 分）A8 B37 C36 D99设S 为一个长度为n 的字符串，其中的字符各不相同，则S 中的互异的非平凡子串（非空且不同于S本身）的个数为（ ）。A2n-1 Bn2 C(n2/2)+(n/2) D(n2/2)+(n/2)-1 E. (n2/2)-(n/2)-1 F.其他情况10串的长度是指（ ）（3 分）A串中所含不同字母的个数 B串中所含字符的个数C串中所含不同字符的个数 D串中所含非空格字符的个数二、判断题1KMP 算法的特点是在模式匹配时指示主串的指针不会变小。（ ） （1 分）2设模式串的长度为m,目标串的长度为n，当nm
5、 且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（ ） (1 分)3串是一种数据对象和操作都特殊的线性表。（ ）(1 分)二、填空题1空格串是指_(1)_，其长度等于_(2)_。（2 分）2组成串的数据元素只能是_。 （1 分）3一个字符串中_称为该串的子串 。（1 分）4INDEX（DATASTRUCTURE， STR）=_。 (2 分)5设正文串长度为n，模式串长度为m，则串匹配的KMP 算法的时间复杂度为_。6模式串P=abaabcac的next 函数值序列为_。（2 分）7字符串ababaaab的nextval 函数值为_。（2 分）8设T 和
6、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(cha
7、r *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 maxcomstr(VAR s,t : orderstring; VAR index,length : integer);VAR i,
8、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 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(jlength) inde
9、x=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 中的序
10、号(从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 不含有字符&和字符$
11、,字符&用作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 BEG
12、IN 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) 返回栈顶元素；semp
13、ty(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
