第四章串习题_数据结构.doc

习题四 串一、单项选择题1下面关于串的的叙述中，哪一个是不正确的？（ ）A串是字符的有限序列 B空串是由空格构成的串C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储2串是一种特殊的线性表，其特殊性体现在（ ）。A可以顺序存储 B数据元素是一个字符C可以链接存储 D数据元素可以是多个字符3串的长度是指（ ）A串中所含不同字母的个数 B串中所含字符的个数C串中所含不同字符的个数 D串中所含非空格字符的个数4设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）A求子串 B联接 C匹配 D求串长5若串S=“software”,其子串的个数是（ ）。A8 B37 C36 D9二、填空题1含零个字符的串称为_串。任何串中所含_的个数称为该串的长度。2空格串是指_ _，其长度等于_ _。 3当且仅当两个串的_相等并且各个对应位置上的字符都_时，这两个串相等。一个串中任意个连续字符组成的序列称为该串的_串，该串称为它所有子串的_串。4INDEX（DATASTRUCTURE， STR）=_。5模式串P=abaabcac的next函数值序列为_。6下列程序判断字符串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)_ _) 7下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。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) _ 三、应用题1描述以下概念的区别：空格串与空串。2设有 A=” ”,B=mule，C=old，D=my,试计算下列运算的结果(注:A+B是CONCAT（A,B）的简写,A= 的 含有两个空格)。(a) A+B(b) B+A(c) D+C+B(d) SUBSTR(B,3,2)(e) SUBSTR(C,1,0)(f) LENGTH(A)(g) LENGTH(D)(h) INDEX(B,D)(i) INDEX(C,d)(j) INSERT(D,2,C)(k) INSERT(B,1,A)(l) DELETE(B,2,2)(m) DELETE(B,2,0)3设主串S=xxyxxxyxxxxyxyx，模式串T=xxyxy。请问：如何用最少的比较次数找到T在S中出现的位置？相应的比较次数是多少？4给出字符串abacabaaad在KMP算法中的next和nextval数组。5已知：s “（xyz）”，t “（xz）y”。试利用联结、求子串和置换等基本运算，将 s 转化为 t 。四、算法设计题1在顺序串上实现串的判等运算EQUAL(S,T)。2在链串上实现判等运算EQUAL(S,T)。3若S和T是用结点大小为1的单链表存储的两个串（S、T为头指针），设计一个算法将串S中首次与串T匹配的子串逆值。4 以顺序存储结构表示串，设计算法。求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。（如果字符串的一个子串（其长度大于1）的各个字符均相同，则称之为等值子串。如果输入字符串S，以“！”作为结束标志。串S中不存在等值子串，则输出信息“无等值子串”，否则求出（输出）一个长度最大的等值子串。例如：若S=“abc123abc123!”，则输出“无等值子串”；若S=“abceebccadddddaaadd!”，则输出“ddddd”。）5写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。第四章 串一、单项选择题1B2. B3B4C5. C二、填空题1空、字符2 由空格字符（ASCII值32）所组成的字符串 空格个数 3长度、相等、子、主455011223126（1）char s (2) j+ (3) i = j7题目分析本题算法采用顺序存储结构求串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）相等时，求出局部公共子串。若该子串长度大于已求出的最长公共子串（初始为），则最长公共子串的长度要修改。(1) i+k=s.len & j+k=t.len & si+k=tj+k /所有注释同上（a） (2) con=0 (3) j+=k (4) j+ (5) i+三、应用题1空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零。2(a)A+B “ mule” (b)B+A “mule ” (c)D+C+B “myoldmule” (d)SUBSTR(B,3,2) “le” (e)SUBSTR(C,1,0) “ ” (f)LENGTH(A) 2 (g)LENGTH(D) 2 (h)INDEX(B,D) 0 (i)INDEX(C,”d”) 3 (j)INSERT(D,2,C) “myold” (k)INSERT(B,1,A) “m ule” (l)DELETE(B,2,2) “me” (m)DELETE(B,2,0) “mule”3朴素的模式匹配（BruteForce）时间复杂度是（mn），KMP算法有一定改进，时间复杂度达到（mn）。本题也可采用从后面匹配的方法，即从右向左扫描，比较次成功。另一种匹配方式是从左往右扫描，但是先比较模式串的最后一个字符，若不等，则模式串后移；若相等，再比较模式串的第一个字符，若第一个字符也相等，则从模式串的第二个字符开始，向右比较，直至相等或失败。若失败，模式串后移，再重复以上过程。按这种方法，本题比较18次成功。4next和nextval值分别为0112123422和0102010422。5题中所给操作的含义如下：/：连接函数，将两个串连接成一个串substr（s,i,j）：取子串函数，从串s的第i个字符开始，取连续j个字符形成子串replace（s1,i,j,s2）：置换函数，用s2串替换s1串中从第i个字符开始的连续j个字符本题有多种解法，下面是其中的一种：（1） s1=substr（s,3,1） /取出字符：y（2） s2=substr（s,6,1） /取出字符：+（3） s3=substr（s,1,5） /取出子串：(xyz)（4） s4=substr（s,7,1） /取出字符：*（5） s5=replace（s3,3,1,s2）/形成部分串：（x+z）（6） s=s5/s4/s1 /形成串t即（x+z）*y四、算法设计题1const maxlen=串的最大长度;typedef struct char ch maxlen; int curlen; string;int EQUAL_string(string s,string t ) if (s.curlen!=t.curlen) return(0); for (t=0; tch=t-ch) s=s-next;t=t-next; return(t= = null)&(s= =null);3分析：首先判断串T是否为串S的子串，若串T是串S的子串对S中该子串逆置。 Int NZ_strlist (strlist s,strlist t) p=s-next;t=t-next;q=s; while(p!=null) pp =p ; tt =t; /*判断串T是否为串S的子串*/ while (tt!=null)&(pp!=null)&(pp-ch= =tt-ch) pp=pp-next;tt=tt-next;if (tt=null) /*串T是串S的子串对S中的该子串的位置*/ qq=q-next; /* q是子串的第一个结点前趋pp是子串最后一个结点后继*/ while(qq!=pp) g=qq; qq= qq-next; q-next =pp; pp=g; q-next=pp; /*将该子串的前趋与逆置后的子串的相连*/ return(1);/*找到并逆置返1 */else q=p;p=p-next;return(0);/*找不到匹配的串返0*/4题目分析设以字符数组s表示串，重复子串的含义是由一个或多个连续相等的字符组成的子串，其长度用max表示，初始长度为0，将每个局部重复子串的长度与max相比，若比max大，则需要更新max，并用index记住其开始位置。int LongestString(char s,int n)/串用一维数组s存储，长度为n，本算法求最长重复子串，返回其长度。int index=0,max=0; /index记最长的串在s串中的开始位置，max记其长度 int length=1,i=0,start=0; /length记局部重复子串长度，i为字符数组下标 while(in-1) if(si=si+1) i+; length+; else /上一个重复子串结束 if(maxlength) max=length; index=start; /当前重复子串长度大，则更新max i+;start=i;length=1; /初始化下一重复子串的起始位置和长度printf(“最长重复子串的长度为%d，在串中的位置%dn”，max,index);return(max);/算法结束算法讨论算法中用in-1来控制循环次数，因C数组下标从0 开始，故长度为n的串，其最后一个字符下标是n-1，当i最大为n-2时，条件语句中si+1正好是sn-1，即最后一个字符。子串长度的初值数为1，表示一个字符自然等于其身。算法的时间复杂度为O(n)，每个字符与其后继比较一次。5题目分析实现字符串的逆置并不难，但本题“要求不另设串存储空间”来