中国铁道出版社数据结构第二版单元5练习参考答案.docx
- 文档编号:11518466
- 上传时间:2023-06-01
- 格式:DOCX
- 页数:18
- 大小:24.15KB
中国铁道出版社数据结构第二版单元5练习参考答案.docx
《中国铁道出版社数据结构第二版单元5练习参考答案.docx》由会员分享,可在线阅读,更多相关《中国铁道出版社数据结构第二版单元5练习参考答案.docx(18页珍藏版)》请在冰点文库上搜索。
中国铁道出版社数据结构第二版单元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<
if(r1->len+r2->len>MAXLEN)
cout<<"两个串太长,溢出!
";
else
{for(i=0;i
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(i
{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;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;i
if(r->vec[i]==ch)
{
for(j=i;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(i
{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(i
{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;k 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;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); }出师表 两汉: 诸葛亮 先帝创业未半而中道崩殂,今天下三分,益州疲弊,此诚危急存亡之秋也。 然侍卫之臣不懈于内,忠志之士忘身于外者,盖追先帝之殊遇,欲报之于陛下也。 诚宜开张圣听,以光先帝遗德,恢弘志士之气,不宜妄自菲薄,引喻失义,以塞忠谏之路也。 宫中府中,俱为一体;陟罚臧否,不宜异同。 若有作奸犯科及为忠善者,宜付有司论其刑赏,以昭陛下平明之理;不宜偏私,使内外异法也。 侍中、侍郎郭攸之、费祎、董允等,此皆良实,志虑忠纯,是以先帝简拔以遗陛下: 愚以为宫中之事,事无大小,悉以咨之,然后施行,必能裨补阙漏,有所广益。 将军向宠,性行淑均,晓畅军事,试用于昔日,先帝称之曰“能”,是以众议举宠为督: 愚以为营中之事,悉以咨之,必能使行阵和睦,优劣得所。 亲贤臣,远小人,此先汉所以兴隆也;亲小人,远贤臣,此后汉所以倾颓也。 先帝在时,每与臣论此事,未尝不叹息痛恨于桓、灵也。 侍中、尚书、长史、参军,此悉贞良死节之臣,愿陛下亲之、信之,则汉室之隆,可计日而待也 。 臣本布衣,躬耕于南阳,苟全性命于乱世,不求闻达于诸侯。 先帝不以臣卑鄙,猥自枉屈,三顾臣于草庐之中,咨臣以当世之事,由是感激,遂许先帝以驱驰。 后值倾覆,受任于败军之际,奉命于危难之间,尔来二十有一年矣。 先帝知臣谨慎,故临崩寄臣以大事也。 受命以来,夙夜忧叹,恐托付不效,以伤先帝之明;故五月渡泸,深入不毛。 今南方已定,兵甲已足,当奖率三军,北定中原,庶竭驽钝,攘除奸凶,兴复汉室,还于旧都。 此臣所以报先帝而忠陛下之职分也。 至于斟酌损益,进尽忠言,则攸之、祎、允之任也。 愿陛下托臣以讨贼兴复之效,不效,则治臣之罪,以告先帝之灵。 若无兴德之言,则责攸之、祎、允等之慢,以彰其咎;陛下亦宜自谋,以咨诹善道,察纳雅言,深追先帝遗诏。 臣不胜受恩感激。 今当远离,临表涕零,不知所言。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 中国 铁道 出版社 数据结构 第二 单元 练习 参考答案