单元练习5.docx

单元练习5.docx

《单元练习5.docx》由会员分享，可在线阅读，更多相关《单元练习5.docx（17页珍藏版）》请在冰点文库上搜索。

单元练习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为子串长度，且n>>m，则模式匹配算法最坏情况下的时间复杂度为：

（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．"something"<"Somethig"D．"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．"IAM"B．"IAMASDUDENT"

C．"IAMASDUDENT"D."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．"mo"B．"or"C．"in"D．"ng"

（17）S1="good"，S2="morning"，执行串连接函数ConcatStr（S1,S2）后的结果为（A）。

A．"goodmorning"B．"goodmorning"

C．"GOODMORNING"D．"GOODMORNING"

（18）S1="good"，S2="morning"，执行函数SubStr（S2,4,LenStr（S1））后的结果为（B）。

A．"good"B．"ning"

C．"go"D．"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;

cout<vec<vec;

if（r1->len+r2->len>MAXLEN）

cout<<"两个串太长，溢出！

";

else

{for（i=0;ilen;i++）//把r2连接到r1

r1->vec[r1->len+i]=r2->vec[i];

r1->vec[r1->len+i]='\0';//添上字符串结束标记

r1->len=r1->len+r2->len;//修改新串长度

}

}

2.设x和y两个串均采用顺序存储方式，下面的程序是比较x和y两个串是否相等的函数，试完成程序填空。

#defineMAXLEN100

typedefstruct

{charvec[MAXLEN];len;

}str;

intsame（x,y）

str*x,*y;

{inti=0,tag=1;

if（x->len!

=y->len）return（0）;//（或<>）

else

{while（ilen&&tag）

{if（x->vec[i]!

=y->vec[i]）tag=0;

i++;（或i=i+1）

}

return（tag）;

}

}

3．下面算法是判断字符串是否为回文（即正读和倒读相同），试完成程序填空。

解：

#include"stdio.h"

typedefstruct

{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）

else

break;

}

if（j-i>=1）

cout<<"Itisnotapalindrome\n";

else

cout<<"Itisapalindrome\n";

}

五．编程题

1．设下面所用的串均采用顺序存储方式，其存储结构定义如下，请编写下列算法：

#defineMAXLEN100

typedefstruct

{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;ilen;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;ilen;i++）

if（r->vec[i]==ch）

{

for（j=i;jlen;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（ilen）

{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（ilen&&tag）

{if（x->vec[i]!

=y->vec[i]）

tag=0;

i++;

}

return（tag）;

}

}

2．解：

#include"stdio.h"

typedefstruct

{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;}

else

break;

}

if（j-i>=1）

printf（"Ttisnotapalindrome\n"）;

else

printf（"itisapalindrome\n"）;

}

3．解：

#include"stdio.h"

#include"string.h"

typedefstruct

{char*head;

intlength;

}Hstring;

char*DeleteSubString（HstringS,HstringT）

{

inti=0;

intj,k;

intSlength=S.length;

intTlength=T.length;

char*tail;

while（i<=Slenght-Tlength）

{

j=0;k=i;

while（j

{j++;k++;}

if（j==Tlength）//若匹配则执行下面的程序

{

if（i==0）//若位于头位置则改变头指针

{

S.head=S.head+Tlength;

S.length-=Tlength;

Slength-=Tlength;

i=0;

}

else

if（i+Tlength

{

tail=S.head+i+Tlength;

strcpy（S.head+i,tail）;

S.length-=Tlength;

Slength-=Tlength;

}

else//若位于尾部则割去

strncpy（S.head+i,”\0”,1）;

}

else//若不匹配则i加1

i++;

}

returnS.head;

}

4．解：

#include"stdio.h"

#include"string.h"

intFind_word（char*text,constchar*word）

{

inttextlength=strlen（text）;

intwordlength=strlen（word）;

inti,j,k;

intcount=0;

for（i=0;i

{j=0;k=i;}

while（j

{j++;k++;}

if（j==wordlength&&word[j]==’\0’）//匹配成功计数器加1

count++;

}

returncount;

}

模拟考题

1．下列程序是在字符串s的第i个字符起，连续删除长度为j的子串，试完成程序填空。

#include"stdio.h"

typedefstruct

{charvec[MAXLEN];

intlen;

}str;

voidDelStr（Str*s,inti,intj）

{intk;

if（i+j-1>s->len）

cout<<"\n\t\t所要删除的子串超界！

\n";

else

{for（k=i+j;klen;k++,i++）

s->vec[i]=s->vec[k];

s->len=s->len-j;

s->vec[s->len]='\0';

}

}

main（）

{cout<<"\n\t\t请输入从第几个字符开始：

";

cin>>i;

cout<<"\n\t\t请输入删除的连续字符数：

";

cin>>j;

DelStr（s,i-1,j）;

}

2．下列程序是在字符串s的第i个字符前，插入一个子串s1，试完成程序填空。

#include"stdio.h"

typedefstruct

{charvec[MAXLEN];

intlen;

}str;

Str*InsStr（Str*s,Str*s1,inti）

{intk;

if（i>=s->len||s->len+s1->len>MAXLEN）

printf（"\n\t\t不能插入!

\n"）;

else

{for（k=s->len-1;k>=i;k--）

s->vec[s1->len+k]=s->vec[k];

for（k=0;klen;k++）

s->vec[i+k]=s1->vec[k];

s->len=s->len+s1->len;

s->vec[s->len]='\0';

}

returns;

}

main（）

{cout<<"\n\t\t请输入在第几个字符前插入：

";

cin>>i;

cout<<"\n\t\t请输入所要插入的字符串：

";

s1=CseateStr（&b）;

InsStr（s,s1,i-1）;

}

3．下列程序是在字符串s的第i个字符起，取出长度为j的子串，试完成程序填空。

#include"stdio.h"

typedefstruct

{charvec[MAXLEN];

intlen;

}str;

voidSubStr（Str*s,inti,intj）

{intk;

Stra;

Str*s1=&a;

if（i+j-1>s->len）

{cout<<"\n\t\t子串超界!

\n";

return;

}

else

{for（k=0;k

s1->vec[k]=s->vec[i+k-1];

s1->len=j;

s1->vec[s1->len]='\0';

}

cout<<"\n\t\t取出字符为：

";

puts（s1->vec）;

}

main（）

{cout<<"\n\t\t请输入从第几个字符开始：

";

cin>>i;

cout<<"\n\t\t请输入取出的连续字符数：

";

cin>>j;

SubStr（s,i,j）;

}