当前位置：文档之家 › 第4章 串(习题)

第4章 串(习题)

  • 格式：doc
  • 大小：61.00 KB
  • 文档页数：2

第4章串
习题
一、选择题
1、如下陈述中正确的是（）
A．串是一种特殊的线性表 B．串的长度必须大于零
C．串中元素只能是字母 D．空串就是空白串
2、设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）
A．求子串 B．联接 C．匹配 D．求串长
3、串”ababaaababaa”的next数组为（）。

A．012345678999 B．012121111212 C．011234223456 D．0123012322345
4、串是_____________。

A.不少于一个字母的序列
B.任意个字母的序列
C.不少于一个字符的序列
D.有限个字符的序列
5、串的长度是指（）
A．串中所含不同字母的个数 B．串中所含字符的个数
C．串中所含不同字符的个数 D．串中所含非空格字符的个数
二、填空题
1、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为________。

2、一个字符串中________称为该串的子串。

3、串是一种特殊的线性表，其特殊性表现在__ __；串的两种最基本的存储方式是____、__ __；两个串相等的充分必要条件是____ 。

4、INDEX（‘MY STUDENT’，‘STU’）=________。

5、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为________。

6、设串S的长度为n,则S的子串个数为________
7、字符串”mnmnmmmn”的nextval函数值为________。

8、设T和P是两个给定的串，在T中寻找等于P的子串的过程称为__ __，又称P为_ __。

9、下列程序判断字符串s 是否对称，对称则返回1，否则返回0；如 f("abba")返回1，
f("abab")返回0；
int f(_______)
{int i=0,j=0;
while (s[j])________;
for(j--; i<j && s[i]==s[j]; i++,j--);
return(_______);
}
三、判断题
1、KMP算法的特点是在模式匹配时指示主串的指针不会变小。

2、设模式串的长度为m,目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。

3、next函数值序列的产生仅与模式串有关。

4、空格串就是由零个字符组成的字符序列。

5、从串中取若干个字符组成的字符序列称为串的子串。

四、应用题
1、空串与空格串有何区别？字符串中的空格符有何意义？
2、串的存储结构有几种？各有何特点？
3、两个字符串S1和S2的长度分别为m和n。

求这两个字符串最大共同子串算法的时间复杂度为T(m,n)。

估算最优的T(m,n)，并简要说明理由。

4、设主串S=‘xxyxxxyxxxxyxyx’，模式串T=‘xxyxy’。

请问：如何用最少的比较次数找到T在S中出现的位置？相应的比较次数是多少？
5、给出字符串‘abacabaaad’在KMP算法中的next和nextval数组
五、算法设计
1、利用C的库函数strlen，strcpy写一算法 void StrDelete(char *S,int i,int m)删除串S中从位置i开始的连续m个字符。

若i≥strlen(S),则没有字符被删除；若i+m≥strlen(S),则将S中位置I开始直至末尾的字符都删去。

2、设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，判断t是否为s 的子串。

如果是，输出子串所在位置（第一个字符），否则输出0。

3、输入一个字符串，内有数字和非数字字符，如：ak123x456 17960?302gef4563，将其中连续的数字作为一个整体，依次存放到一数组ａ中，例如123放入a［０］,456放入ａ［１］，……。

编程统计其共有多少个整数，并输出这些数。

4、已知串a和b，试以下两种方式编写算法，求得所有包含在a中而不在b中的字符构成
的新串r。

（1）利用串的基本操作来实现；
（2）以串的顺序存贮结构来实现。

5、编写一个算法frequency，统计在一个输入字符串中各个不同字符出现的频度。

用适当的测试数据来验证这个算法。

6、设x和y是表示成单链表的两个字符串，试写一个算法，找出x中第一个不在y中出现的字符（假定每个结点只存放一个字符）。

7、已知字符串S1中存放一段英文，写出算法format(s1,s2,s3,n),将其按给定的长度n格式化成两端对齐的字符串S2, 其多余的字符送S3。

8、写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。

9、写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。

10、S=“S1S2…Sn”是一个长为N的字符串，存放在一个数组中，编程序将S改造之后输出：
（1）将S的所有第偶数个字符按照其原来的下标从大到小的次序放在S的后半部分；
（2）将S的所有第奇数个字符按照其原来的下标从小到大的次序放在S的前半部分；例如：
S=‘ABCDEFGHIJKL’
则改造后的S为‘ACEGIKLJHFDB’。

合集下载

严蔚敏《数据结构(c语言版)习题集》答案第四章 串

严蔚敏《数据结构(c语言版)习题集》答案第四章 串

《一定能摸到红球吗？》说课稿
林银花
一、教材说明：
１、 课题：《一定能摸到红球吗？》
２、 本节内容的地位和作用
在现代社会中，人们面临着更多的机会和选择，常常需要在不确定情境中作出合理的决策,概率正是通过对不确定现象和事件发生的可能性的刻画,来为人们更好的制定决策提供依据和建议.本节内容又是义务教育阶段,唯一培养学生从不确定的角度来观察世界的数学内容,让学生了解可能性是普遍的,有助于他们理解社会,适应生活.
(１) 每位同学从盒子中轮流摸球,记录下所摸球的颜色,并将球放回盒中.
(２) 做１０次这样的活动,将最终结果填在表中.
(３) 全班将各小组活动进行汇总，摸到红球的次数是多少?摸到黄球的次数是多少?他们各占总数的百分比是多少?
(４) 你认为哪种颜色的球多?打开看一看.
(５) 如果从盒中任意摸出一球,你认为摸到哪种颜色的球可能性大? 学生阅读学习目标.
学生两人一组进行活动.一人摸一人记录.并交流.
题(1)：学生先想象后画图，并通过搭建几何体验证学习成果。
题(2)：学生四人一组进行活动，一人搭几何体，另三人画图并交流，如有异义，举手询问。依次轮流。 使学生明确学习目标，进入学习角色，做到有的放矢。
目的是使学生体会到进行概率试验时,一定要保证随机性.
课堂组织策略：创设贴近学生生活，生动有趣的问题情境，开展活泼、主动、有效的数学活动，组织学生主动参与、勤于动手、积极思考，使他们在自主探索和合作交流的过程中真正理解和掌握概率有关内容。
学生学习策略：明确学习目标，了解所需掌握的知识，在教师的组织、引导、点拨下主动地从事观察、试验、猜测、验证与交流等数学活动，从而真正有效地理解和掌握知识。
（３）、情感目标：
第四、五章串、数组和广义表练习题答案

第四、五章串、数组和广义表练习题答案

第四、五章串、数组和广义表练习题答案一．填空题1. 不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。

2. 设S=“A;/document/Mary.doc”，则strlen(s)= 20 , “/”的字符定位的位置为3。

3. 子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。

4. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 6 次匹配成功。

5. 若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m。

6. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。

已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为288 B ；末尾元素A57的第一个字节地址为1282 ；若按行存储时，元素A14的第一个字节地址为(8+4)×6+1000=1072 ；若按列存储时，元素A47的第一个字节地址为(6×7＋4)×6＋1000）＝1276 。

(注：数组是从0行0列还是从1行1列计算起呢？由末单元为A57可知，是从0行0列开始！)7. 〖00年计算机系考研题〗设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为8950 。

答：不考虑0行0列，利用列优先公式：LOC(a ij)=LOC(a c1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L 得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝89508. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的行下标、列下标和元素值。

9.求下列广义表操作的结果：（1）GetHead【((a,b),(c,d))】=== (a, b) ; //头元素不必加括号（2）GetHead【GetTail【((a,b),(c,d))】】=== (c,d) ;（3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== b ;（4）GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== （d）;10．C语言规定，字符串常量按_字符数组_____处理，它的值在程序的执行过程中是不能改变的。

第4章 串(习题)

第4章 串(习题)

第四章串一、选择题1．下面关于串的的叙述中，哪一个是不正确的？（）（2 分）A．串是字符的有限序列 B．空串是由空格构成的串C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储2 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘’,执行concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2))) 其结果为（）（7 分）A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345E．ABC###G1234 F．ABCD###1234 G．ABC###012343．设有两个串p 和q，其中q 是p 的子串，求q 在p 中首次出现的位置的算法称为（）A．求子串 B．联接 C．匹配 D．求串长（2 分）4．已知串S=‘aaab’,其Next 数组值为（）。

（2 分）A．0123 B．1123 C．1231 D．12115．串‘ababaaababaa’的next 数组为（）。

A．9 B．2 C．6 D．456．字符串‘ababaabab’的nextval 为（）A．(0,1,0,1,04,1,0,1) B．(0,1,0,1,0,2,1,0,1)C．(0,1,0,1,0,0,0,1,1) D．(0,1,0,1,0,1,0,1,1 )（2 分）7．模式串t=‘abcaabbcabcaabdab’，该模式串的next 数组的值为（），nextval 数组的值为（）。

A．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B．0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2C．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2E．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F．0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1（2 分）8．若串S=’software’,其子串的数目是（）。

李春葆《数据结构教程》(第4版)课后习题-串(圣才出品)

李春葆《数据结构教程》(第4版)课后习题-串(圣才出品)

第4章串1．采用顺序结构存储串，编写一个实现串通配符匹配的算法pattern______index（），其中的通配符只有“？”，它可以和任一字符匹配成功，例如，pattern______index（″? re″，″there are″）返回的结果是2。

答：本题的基础是Brute—Force模式匹配算法，只是增加了“？”的处理功能。

对应的算法如下：2．有两个串s1和s2，设计一个算法求这样一个串，该串中的字符是s1和s2中的公共字符。

答：扫描s1，对于当前字符s1.data[i]，若在s2中，则将其加入到串s3中。

最后返回s3串。

对应的算法如下：3．设目标为t=’abcaabbabcabaacbacba’，模式p=’abcabaa’。

（1）计算模式P的nextval函数值。

（2）不写算法，只画出利用KMP算法进行模式匹配时的每一趟匹配过程。

答：（1）先计算next数组，在此基础上求nextval数组，如表4-1所示。

表4-1 计算next数组和nextval数组（2）采用KMP算法求子串位置的过程如下（开始时i=0，j=0）：第1趟匹配：此时i=4，j=4，匹配失败，而nextval[4]=0，则i=4，j=nextval[4]=0，即：第2趟匹配：此时i=6，j=2，匹配失败，而nextval[2]=0，则i=6，j=nextval[2]=0，即：第3趟匹配：此时i=6，j=0，匹配失败，而nextval[0]=-1，则i=6，j=nextval[0]=-1。

因j=-1，执行i=i+1=7，j=j+1=0，即：第4趟匹配：此时i=14，j=7，匹配成功，返回v=i-t．1ength=14-7=7。

上机实验题4实验题1编写一个程序algo4-1.cpp，实现顺序串的各种基本运算，并在此基础上设计一个程序exp4-1.cpp完成如下功能：（1）建立串s=″abcdefghefghijklmn″和串sl=″xyz″；（2）输出串s；（3）输出串s的长度；（4）在串s的第9个字符位置插入串s1而产生串s2；（5）输出串s2；（6）删除串s第2个字符开始的5个字符而产生串s2；（7）输出串s2；（8）将串s第2个字符开始的5个字符替换成串s1而产生串s2；（9）输出串s2；（10）提取串s的第2个字符开始的10个字符而产生串s3；（11）输出串s3；（12）将串s1和串s2连接起来而产生串s4；（13）输出串s4。