基本概念题: 4-1设S1=“ Data structure course”,S2=“ Structure”,S3=“Base”,求: (1) Length(s1) (2)Compare(S2, S3 nser (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的串和字符是否相同。为什么? 4-4串是不定长的,表示串的长度有几种方法?C语言中的串采用哪种方法? 4-5可以说串是数据类型固定为字符类型的线性表,但是串操作和线性表操作的主要不 同之处在哪里 4-6可以用几种存储方法存储串? 4-7分别写出串的静态数组存储结构和串的动态数组存储结构的结构体定义。 4-8为什么动态数组结构下串的实现要增加撤消函数? 复杂概念题 4-9令t1=“aab”,t2=“ ababa”,t3=“ abcaabbabcabaacba”,试分别求出他们的 extj值。 4-10简述模式匹配的 Brute- Force算法思想。简述模式匹配的KMP算法思想 4-11简述求子串的 nextLi]值的算法思想。 算法设计题 4-12设串采用静态数组存储结构,编写函数实现两个串的比较 Compare(s,T。要求比 较结果有等于和不等于两种情况。 4-13设串采用静态数组存储结构,编写函数实现两个串的比较 Compare(S,T。要求比 较结果有大于、等于和小于三种情况。 4-14设串釆用动态数组存储结构,编写函数实现两个串的比较 Compare(s,T)。要求比 较结果有大于、等于和小于三种情况。对比本题和习题4-13的算法,说明串的静态数组存 储结构和串的动态数组存储结构是否对编写串的比较算法有影响 4-15设串釆用静态数组存储结构,编写函数实现串的替换 Replace(s,stat;,T,V),即要 求在主串S中,从位置 start开始查找是否存在子串T,若主串S中存在子串T,则用子串Ⅴ 替换子串T,且函数返回1;若主串S中不存在子串T,则函数返回0。 4-16设字符串采用静态数组的顺序存储结构, (1)编写算法删除字符串s中值等于ch的一个字符,并分析该算法的时间复杂度 (2)编写算法删除字符串s中值等于ch的所有字符。 4-17设字符串采用单字符的链式存储结构,编写删除串s从位置i开始长度为k的子串 的算法。 *4-18设字符串采用块链存储结构,编写删除串s从位置i开始长度为k的子串的算法。 上机实习题: 4-19在4.4.3节例46的基础上,编写比较 Brute- Force算法和KMP算法比较次数的 程序 4-20设串采用静态数组存储结构,编写函数实现串的替换 Replace(S, start,T,V), 即要求在主串S中,从位置 start开始查找是否存在子串T,若主串S中存在子串T,则用基本概念题： 4-1 设 S1 =“Data Structure Course”，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 的串和字符是否相同。为什么？ 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 算法思想。 4-11 简述求子串的 next[j]值的算法思想。 算法设计题： 4-12 设串采用静态数组存储结构，编写函数实现两个串的比较 Compare(S, T)。要求比 较结果有等于和不等于两种情况。 4-13 设串采用静态数组存储结构，编写函数实现两个串的比较 Compare(S, T)。要求比 较结果有大于、等于和小于三种情况。 4-14 设串采用动态数组存储结构，编写函数实现两个串的比较 Compare(S, T)。要求比 较结果有大于、等于和小于三种情况。对比本题和习题 4-13 的算法，说明串的静态数组存 储结构和串的动态数组存储结构是否对编写串的比较算法有影响。 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 设字符串采用块链存储结构，编写删除串 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，则用