单元练习5一.判断题(下列各题,正确的请在前面的括号内打√;错误的打╳)(ㄨ)(1)串是n个字母的有限序列。“串”是由0个或多个字符构成的一个有限序列,用双引号作为其定界符。(√)(2)串的数据元素是一个字符。(ㄨ)(3)串的长度是指串中不同字符的个数。括在双引号内的字符个数n,称为字符串的“长度”。当n=0时,称其是一个“空串”(ㄨ)(4)如果两个串含有相同的字符,则说明它们相等。(ㄨ)(5)如果一个串中所有的字母均在另一个串中出现,则说明前者是后者的子串。字符串中任意多个连续字符所组成的子序列,称作是该串的“子串”(√)(6)串的堆分配存储是一种动态存储结构。(ㄨ)(7)“DT”是“DATA”的子串。要连续。(ㄨ)(8)串中任意个字符组成的子序列称为该串的子串。(√)(9)子串的定位运算称为模式匹配。(√)(10)在链串中为了提高存储密度,应该增大结点的大小。二.填空题(1)由零个或多个字符组成的有限序列称为字符串(或串)。(2)字符串按存储方式可以分为:顺序存储、链接存储和堆分配存储。(3)串的顺序存储结构简称为顺序串。(4)串顺序存储非紧凑格式的缺点是:空间利用率低。(5)串顺序存储紧凑格式的缺点是对串的字符处理效率低。(6)串链接存储的优点是插入、删除方便,缺点的空间利用率低。(7)在C或C++语言中,以字符\0表示串值的终结。(8)空格串的长度等于空格的个数。(9)在空串和空格串中,长度不为0的是空格串。(10)两个串相等是指两个串相长度等,且对应位置的字符都相同。(11)设S=MyMusic,则LenStr(s)=_8。(12)两个字符串分别为:S1=Todayis,S2=30July,2005,ConcatStr(S1,S2)的结果是:Todayis30July,2005。(13)求子串函数SubStr(Todayis30July,2005,13,4)的结果是:July。(14)在串的运算中,EqualStr(aaa,aab)的返回值为0。(15)在串的运算中,EqualStr(aaa,aaa)的返回值为0。(16)在子串的定位运算中,被匹配的主串称为目标串,子串称为模式。(17)模式匹配成功的起始位置称为:有效位移。(18)设S=abccdcdccbaa,T=cdcc,则第6次匹配成功。(19)设S=c:/mydocument/text1.doc,T=mydont,则字符定位的位置为0。(20)若n为主串长度,m为子串长度,且nm,则模式匹配算法最坏情况下的时间复杂度为:(n-m+1)*m。三.选择题(1)串是一种特殊的线性表,其特殊性体现在(B)。A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符(2)某串的长度小于一个常数,则采用(B)存储方式最节省空间。A.链式B.顺序C.堆结构D.无法确定(3)以下论述正确的是(C)。A.空串与空格串是相同的B.tel是Teleptone的子串C.空串是零个字符的串D.空串的长度等于1(4)以下论述正确的是(B)。A.空串与空格串是相同的B.ton是Teleptone的子串C.空格串是有空格的串D.空串的长度等于1(5)以下论断正确的是(A)。A.是空串,空格串B.BEIJING是BEIJING的子串C.somethingSomethigD.BIT=BITE(6)设有两个串S1和S2,则EqualStr(S1,S2)运算称作(D)。A.串连接B.模式匹配C.求子串D.串比较(7)串的模式匹配是指(D)。A.判断两个串是否相等C.找某字符在主串中第一次出现的位置B.对两个串比较大小D.找某子串在主串中第一次出现的第一个字符位置(8)若字符串ABCDEFG采用链式存储,假设每个字符占用1个字节,每个指针占用2个字节。则该字符串的存储密度为(D)。A.20%B.40%C.50%D.33.3%(9)若字符串ABCDEFG采用链式存储,假设每个指针占用2个字节,若希望存储密度50%,则每个结点应存储(A)个字符。A.2B.3C.4D.5(10)设串S1=IAM,S2=ASDUDENT,则ConcatStr(S1,S2)=(B)。A.IAMB.IAMASDUDENTC.IAMASDUDENTD.ASDUDENT(11)设S=,则LenStr(S)=(A)。A.0B.1C.2D.3(12)设目标串T=AABBCCDDE,模式P=ABCDE,则该模式匹配的有效位移为(A)。A.0B.1C.2D.3(13)设目标串T=AABBCCDDEEFF,模式P=CCD,则该模式匹配的有效位移为(D)。A.2B.3C.4D.5(14)设目标串T=aabaababaabaa,模式P=abab,朴素匹配算法的外层循环进行了(D)次。A.1B.9C.4D.5(15)朴素模式匹配算法在最坏情况下的时间复杂度是(D)。A.O(m)B.O(n)C.0(m+n)D.0(m*n)(16)S=morning,执行求子串函数SubStr(S,2,2)后的结果为(B)。A.moB.orC.inD.ng(17)S1=good,S2=morning,执行串连接函数ConcatStr(S1,S2)后的结果为(A)。A.goodmorningB.goodmorningC.GOODMORNINGD.GOODMORNING(18)S1=good,S2=morning,执行函数SubStr(S2,4,LenStr(S1))后的结果为(B)。A.goodB.ningC.goD.morn(19)设串S1=ABCDEFG,S2=PQRST,则ConcatStr(SubStr(S1,2,LenStr(S2)),SubStr(S1,LenStr(S2),2))的结果串为(D)。A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF(20)若串S=SOFTWARE,其子串的数目最多是:(C)。A.35B.36C.37D.38(8+7+6+5+4+3+2+1+1=37)四.程序题填空(每空2分,共50分)1.下面程序是把两个串r1和r2首尾相连的程序,即:r1=r1+r2,试完成程序填空。typedefStruct{charvec[MAXLEN];//定义合并后串的最大长度intlen;//len为串的长度}St;voidConcatStr(Str*r1,Str*r2)//字符串连接函数{inti;coutr1-vecr2-vec;if(r1-len+r2-lenMAXLEN)cout两个串太长,溢出!;else{for(i=0;ir2-len;i++)//把r2连接到r1r1-vec[r1-len+i]=r2-vec[i];r1-vec[r1-len+i]='\0';//添上字符串结束标记r1-len=r1-len+r2-len;//修改新串长度}}2.设x和y两个串均采用顺序存储方式,下面的程序是比较x和y两个串是否相等的函数,试完成程序填空。#defineMAXLEN100typedefstruct{charvec[MAXLEN];len;}str;intsame(x,y)str*x,*y;{inti=0,tag=1;if(x-len!=y-len)return(0);//(或)else{while(ix-len&&tag){if(x-vec[i]!=y-vec[i])tag=0;i++;(或i=i+1)}return(tag);}}3.下面算法是判断字符串是否为回文(即正读和倒读相同),试完成程序填空。解:#includestdio.htypedefstruct{charvec[MAXLEN];intlen;}str;voidPalindrome(strs){inti=0;ingj=s.len-1;while(j-i=1){if(s.vec[i]==s.vec[j]){i++;j--;continue}//(或j=j+1)elsebreak;}if(j-i=1)coutItisnotapalindrome\n;elsecoutItisapalindrome\n;}五.编程题1.设下面所用的串均采用顺序存储方式,其存储结构定义如下,请编写下列算法:#defineMAXLEN100typedefstruct{charvec[MAXLEN];intlen;}str;(1)将串中r中所有其值为ch1的字符换成ch2的字符。(2)将串中r中所有字符按照相反的次序仍存放在r中。(3)从串r中删除其值等于ch的所有字符。(4)从串r1中第index个字符起求出首次与字符r2相同的子串的起始位置。(5)从串r中删除所有与串r3相同的子串(允许调用第(4)小题的函数)。(6)编写一个比较x和y两个串是否相等的函数。2.设计一算法判断字符串是否为回文(即正读和倒读相同)3.设计一算法从字符串中删除所有与字串del相同的子串4.设计一算法统计字符串中否定词not的个数1.解:(1)算法思想:从头至尾扫描r串,对于值为ch1的元素直接替换成ch2即可。str*trans(r,ch1,ch2)str*r;charch1,ch2;{inti;for(i=0;ir-len;i++)if(r-vec[i]==ch1)r-vec[i]=ch2;return(r);}(2)算法思想是:将第一个元素与最后一个元素交换,第二个元素与倒数第二个元素交换,依次类推,便将该串的所有字符反序了。str*invert(r)str*r;{inti;charx;for(i=0;i(r-len%2);i++){x=r-vec[i];r-vec[i]=r-[r-len-i+1];r-vec[r-len-i+1]=x;}return(r);}(3)算法思想:从头到尾扫描r串,对于值为ch的元素用移动的方式进行删除。str*delall(r,ch)str*r;charch;{inti,j;for(i=0;ir-len;i++)if(r-vec[i]==ch){for(j=i;jr-len;j++)r-vec[i]=r-vec[i+1];r-len=r-len-1;}return(r);}(4)算法思想:从第index个元素开始扫描r1,当其元素值与r2的第一个元素的值相同时,判定它们之后的元素值是否依次相同,直到r2结束为止,若都相同则返回,否则继续上述过程直到r1扫描完为止。intpartposition(r2,r1,index)str*r2,*r1;intindex;{inti,j,k;for(i=index;r1-vec[i];i++)for(j=i,k=0;r1-vec[j]==r2-vec[k];j++,k++)if(!r2-vec[k+1])return(i);return(-1);}(5)算法思想:从位置1开始调用第(4)小题的函数partposition(),若找到了一个相同子串,则调用delsubstring(),再相同的方法查找后面位置的相同子串。str*delstringall(r,r3)str*r,*r3;{inti=0;while(ir-len){if(partposition(r,r3,i)!=-1)delsubstring(r,i,r3-len)i++;}}(6)两个串相等的条件是两个串的长度相等,且两个串的对应的字符必须都相同。intsame(x,y)str*x,*y;{inti=0,tag=1;if(x-len!=y-len)return(0);else{while(ix-len&&tag){if(x-vec[i]!=y-vec[i])tag=0;i++;}return(tag);}}2.解:#includestdio.htypedefstruct{char*head;intlength;}Hstring;voidisPalindrome(Hstrings){int