《数据结构》第四章 串 习题.doc

《《数据结构》第四章 串 习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》第四章串习题基本概念题：4-1设S1=“DataStructureCourse”，S2=“Structure”，S3=“Base”，求：（1）Length(S1)；（2）Compare(S2,S3)；（3）Insert(S1,5,S3)；（4）Delete(S1,5,9)；（5）SubString(S1,5,9,T)；（6）Search(S1,0,S2)；（7）Replace(S1,0,S2,S3)4-2什么叫串？串和字符在存储方法上有什么不同？空串和空格串是否相同，为什么？4-3串是由字符组成的，长度为1的串和字符是否相同。

2、为什么？4-4串是不定长的，表示串的长度有几种方法？C语言中的串采用哪种方法？4-5可以说串是数据类型固定为字符类型的线性表，但是串操作和线性表操作的主要不同之处在哪里？4-6可以用几种存储方法存储串？4-7分别写出串的静态数组存储结构和串的动态数组存储结构的结构体定义。4-8为什么动态数组结构下串的实现要增加撤消函数？复杂概念题：4-9令t1=“aaab”,t2=“abcabaa”,t3=“abcaabbabcabaacba”，试分别求出他们的next[j]值。4-10简述模式匹配的Brute-Force算法思想。简述模式匹配的KMP算

3、法思想。4-11简述求子串的next[j]值的算法思想。算法设计题：4-12设串采用静态数组存储结构，编写函数实现两个串的比较Compare(S,T)。要求比较结果有等于和不等于两种情况。4-13设串采用静态数组存储结构，编写函数实现两个串的比较Compare(S,T)。要求比较结果有大于、等于和小于三种情况。4-14设串采用动态数组存储结构，编写函数实现两个串的比较Compare(S,T)。要求比较结果有大于、等于和小于三种情况。对比本题和习题4-13的算法，说明串的静态数组存储结构和串的动态数组存储结构是否对编写串的比较算法有影响。4

4、-15设串采用静态数组存储结构，编写函数实现串的替换Replace(S,start,T,V)，即要求在主串S中，从位置start开始查找是否存在子串T，若主串S中存在子串T，则用子串V替换子串T，且函数返回1；若主串S中不存在子串T，则函数返回0。4-16设字符串采用静态数组的顺序存储结构，（1）编写算法删除字符串s中值等于ch的一个字符，并分析该算法的时间复杂度；（2）编写算法删除字符串s中值等于ch的所有字符。4-17设字符串采用单字符的链式存储结构，编写删除串s从位置i开始长度为k的子串的算法。*4-18设字符串采用块链存储结构，编

5、写删除串s从位置i开始长度为k的子串的算法。上机实习题：4-19在4.4.3节例4-6的基础上，编写比较Brute-Force算法和KMP算法比较次数的程序。4-20设串采用静态数组存储结构，编写函数实现串的替换Replace(S,start,T,V)，即要求在主串S中，从位置start开始查找是否存在子串T，若主串S中存在子串T，则用子串V替换子串T，且函数返回1；若主串S中不存在子串T，则函数返回0。并要求设计主函数进行测试。一个测试例子为：S=“Iamastudent”，T=“student”，V=“teacher”。*4-21对照

6、4.4.3节的例4-6，编写比较Brute-Force算法和KMP算法比较次数的程序。要求：（1）采用动态数组的顺序存储结构；（2）自己重新设计对比测试的例子；（3）对比静态数组存储结构和动态数组存储结构在程序设计方法的不同。