数据结构单元练习5

单元练习5一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（ㄨ）（1）串是n个字母的有限序列。（√）（2）串的数据元素是一个字符。（ㄨ）（3）串的长度是指串中不同字符的个数。（ㄨ）（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){inti=0;intj=s.length-1;while(j-i=1){if(s.head[i]==s.head[j]){i++;j--;continue;}elsebreak;}if(j-i=1)printf(T