《数据结构》期末考试复习题第4章串.docx

第四章 串一、选择题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分）】AABC#G0123 BABCD#2345 CABC#G2345 DABC#2345EABC#G1234 FABCD#1234 GABC#012343设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）A求子串 B联接 C匹配 D求串长【北京邮电大学 2000 二、4（20/8分）】【西安电子科技大学 1996 一、1 （2分）】4已知串S=aaab,其Next数组值为（ ）。【西安电子科技大学 1996 一、7 （2分）】A0123 B1123 C1231 D12115串 ababaaababaa 的next数组为（ ）。【中山大学 1999 一、7】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,1) D(0,1,0,1,0,1,0,1,1 )【北京邮电大学 1999 一、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 2 E0 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【北京邮电大学 1998 二、3 （2分）】8若串S=software,其子串的数目是（ ）。【西安电子科技大学 2001应用 一、2（2分）】A8 B37 C36 D99设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非平凡子串（非空且不同于S本身）的个数为（ ）。【中科院计算所 1997 】A2n-1 Bn2 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串中所含非空格字符的个数二、判断题1KMP算法的特点是在模式匹配时指示主串的指针不会变小。（ ）【北京邮电大学 2002 一、4 （1分）】2设模式串的长度为m,目标串的长度为n，当nm且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（ ）【长沙铁道学院 1998 一、1 (1分)】3串是一种数据对象和操作都特殊的线性表。（ ）【大连海事大学 2001 1、L (1分)】二、填空题1空格串是指_(1)_，其长度等于_(2)_。 【西安电子科技大学 2001软件 一、4（2分）】2组成串的数据元素只能是_。 【中山大学 1998 一、5 （1分）】3一个字符串中_称为该串的子串 。 【华中理工大学 2000 一、3（1分）】4INDEX（DATASTRUCTURE， STR）=_。【福州大学 1998 二、4 (2分)】5设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为_。 【重庆大学 2000 一、4】6模式串P=abaabcac的next函数值序列为_。【西安电子科技大学 2001软件 一、6（2分）】7字符串ababaaab的nextval函数值为_。 【北京邮电大学 2001 二、4 （2分）】8设T和P是两个给定的串，在T中寻找等于P的子串的过程称为_(1)_，又称P为_(2)_。【西安电子科技大学 1998 二、5 （16/6分）】9串是一种特殊的线性表，其特殊性表现在_(1)_；串的两种最基本的存储方式是_(2)_、_(3)_；两个串相等的充分必要条件是_(4)_。 【中国矿业大学 2000 一、3 （4分）】10两个字符串相等的充分必要条件是_。 【西安电子科技大学 1999软件 一、1 （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）= _。 【东北大学 1997 一、1 (5分)】12实现字符串拷贝的函数 strcpy为： void strcpy(char *s , char *t) /*copy t to s*/ while (_) 【浙江大学 1999 一、5 (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)_) 【浙江大学 1999 一、6 (3分)】14下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。程序（a）PROCEDURE maxcomstr(VAR s,t : orderstring; VAR index,length : integer);VAR i,j,k,length1:integer; con:boolean;BEGIN index :=0; length :=0; i :=1;WHILE(i=s.len) DO j:=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) index=i; length=length1; (3)_; else (4) _; (5) _ 【上海大学 2000 一、2 （10分）】15完善算法：求KMP算法中next数组。PROC get _next(t:string,VAR next:ARRAY1.t.len OF integer);BEGIN j:=1; k:=(1)_; next1:=0; WHILE jt.len DO IF k=0 OR t.chj=t.chk THEN BEGIN j:=j+1; k:=k+1; nextj:=k;ENDELSE k:=(2)_;END;【中山大学 1998 四、1 （4分）】16下面函数index用于求t是否为s的子串，若是返回t第一次出现在s中的序号(从1开始计)，否则返回0。例如:s=abcdefcdek，t=cde,则indse(s,t)=3, index(s,aaa)=0 。已知t，s的串长分别是mt,ms FUNC index(s,t,ms,mt);i:=1;j:=1;WHILE (ims) AND (jmt THEN return (5)_; ELSE return (6)_ENDF;【南京理工大学 1999 三、2 （6分）】第四章 串 一、选择题 1.B2.E3.C4.A5.C6.A7.1D7.2F8.B注9.D10.B 注：子串的定义是：串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自身的子串。若字符串长度为n（n0），长为n的子串有1个，长为n-1的子串有2个，长为n-2的子串有3个，长为1的子串有n个。由于空串是任何串的子串，所以本题的答案为：8*（8+1）/2+1=37。故选B。但某些教科书上认为“空串是任意串的子串”无意义，所以认为选C。为避免考试中的二意性，编者认为第9题出得好。二、判断题1.2.3.三填空题1(1) 由空格字符（ASCII值32）所组成的字符串 (2)空格个数 2字符3任意个连续的字符组成的子序列 45 5.O(m+n)601122312 701010421 8(1)模式匹配 (2)模式串9(1)其数据元素都是字符(2)顺序存储(3)和链式存储(4)串的长度相等且两串中对应位置的字符也相等10两串的长度相等且两串中对应位置的字符也相等。11xyxyxywwy 12*s+=*t+ 或（*s+=*t+）!=013（1）char s (2) j+ (3) i = j14题目分析本题算法采用顺序存储结构求串s和串t的最大公共子串。串s用i指针（1=i=s.len）。t串用j指针（1=j=t.len）。算法思想是对每个i（1=i=s.len，即程序中第一个WHILE循环），来求从i开始的连续字符串与从j（1=j=t.len，即程序中第二个HILE循环）开始的连续字符串的最大匹配。程序中第三个（即最内层）的WHILE循环，是当s中某字符（si）与t中某字符（tj）相等时，求出局部公共子串。若该子串长度大于已求出的最长公共子串（初始为），则最长公共子串的长度要修改。程序（a）：（1）（i+k=s.len）AND(j+k=t.len) AND(si+k=tj+k) /如果在s和t的长度内，对应字符相等，则指针k 后移（加1）。 （2）con:=false /s和t对应字符不等时置标记退出 （3）j:=j+k /在t串中，从第j+k字符再与si比较 （4）j:=j+1 /t串取下一字符（5）i：=i+1 /s串指针i后移（加1）。程序（b）：(1) i+k=s.len & j+k=t.len & si+k=tj+k /所有注释同上（a） (2) con=0 (3) j+=k (4) j+ (5) i+15（1）0 （2）nextk16（1）i：=i+1 （2）j:=j+1 (3)i:=i-j+2 (4)j:=1; (5)i-mt（或i:=i-j+1） (6)017.程序中递归调用 （1）ch1midch /当读入不是分隔符&和输入结束符$时，继续读入字符 （2）ch1=ch2 /读入分隔符&后，判ch1是否等于ch2，得出真假结论。 （3）answer：=true （4）answer：=false （5）read（ch） （6）ch=endch18（1）initstack（s） /栈s初始化为空栈。 (2) setnull (exp) /串exp初始化为空串。 (3) ch in opset /判取出字符是否是操作符。 (4) push (s,ch) /如ch是运算符，则入运算符栈s。 (5) sempty (s) /判栈s是否为空。 (6) succ := false /若读出ch是操作数且栈为空，则按出错处理。 (7) exp (8)ch /若ch是操作数且栈非空，则形成部分中缀表达式。 (9) exp (10) gettop(s) /取栈顶操作符。 (11) pop(s) /操作符取出后，退栈。(12) sempty(s) /将pre的最后一个字符（操作数）加入到中缀式exp的最后。四应用题串是零个至多个字符组成的有限序列。从数据结构角度讲，串属于线性结构。与线性表的特殊性在于串的元素是字符。空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零。最优的T(m,n)是O（n）。串S2是串S1的子串，且在S1中的位置是1。开始求出最大公共子串的长度恰是串S2的长度，一般情况下，T(m,n) =O(m*n)。朴素的模式匹配（BruteForce）时间复杂度是（mn），KMP算法有一定改进，时间复杂度达到（mn）。本题也可采用从后面匹配的方法，即从右向左扫描，比较次成功。另一种匹配方式是从左往右扫描，但是先比较模式串的最后一个字符，若不等，则模式串后移；若相等，再比较模式串的第一个字符，若第一个字符也相等，则从模式串的第二个字符开始，向右比较，直至相等或失败。若失败，模式串后移，再重复以上过程。按这种方法，本题比较18次成功。KMP算法主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，KMP算法的优点更为突出模式串的next函数定义如下： nextj= 根据此定义，可求解模式串t的next和nextval值如下：j1 2 3 4 5 6 7 8 9 10 11 12 t串a b c a a b b a b c a bnextj0 1 1 1 2 2 3 1 2 3 4 5nextvalj0 1 1 0 2 1 3 0 1 1 0 57解法同上题6，其next和nextval值分别为0112123422和0102010422。8解法同题6，t串的next和nextval函数值分别为0111232和0110132。9解法同题6，其next和nextval 值分别为011123121231和011013020131。10p1的next和nextval值分别为：0112234和0102102；p2的next和nextval值分别为：0121123和0021002。11next数组值为011234567 改进后的next数组信息值为010101017。12011122312。13next定义见题上面6和下面题20。串p的next函数值为：01212345634。14（1）S的next与nextval值分别为012123456789和002002002009，p的next与nextval值分别为012123和002003。 （2）利用BF算法的