一、基础知识题

4.1简述下列每对术语的区别：

　　空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。

4.2 假设有如下的串说明：

　char s1[30]="Stocktom,CA", s2[30]="March 5 1999", s3[30], *p;

　(1)在执行如下的每个语句后p的值是什么?
　　　p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6');
　(2)在执行下列语句后，s3的值是什么?
　　　strcpy(s3,s1); strcat(s3,","); strcat(s3,s2);
　(3)调用函数strcmp(s1,s2)的返回值是什么?
　(4)调用函数strcmp(&s1[5],"ton")的返回值是什么?
　(5)调用函数stlen(strcat(s1,s2))的返回值是什么?

4.3 设T[0..n-1]="adaabaabcaabaa",P[0..m-1]="aab".当用模式串匹配目标串T时，请给出所有的有效位移。算法NaiveStrMatch(T,P)返回的位移是哪一个位移。

二、算法设计题：

4.4 利用C的库函数strlen,strcpy和strcat写一算法void StrInsert(char *S, char *T, int i),将串T插入到串S的第i个位置上。若i大于S的长度，则插入不执行。

4.5 利用C的库函数strlen 和strcpy(或strncpy)写一算法void StrDelete(char *S,int i, int m)删去串S中从位置i开始的连续m个字符。若i≥strlen(S),则没有字符被删除；若i+m≥strlen(S),则将S中从位置i开始直至末尾的字符均删去。

4.6 以HString为存储表示，写一个求子串的算法。

4.7 一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为：

　　a b c d e f g h i j k l m n o p q r s t u v w x y z 
　　n g z q t c o b m u h e l k p d a w x f y i v r s j 
　　则字符串"encrypt"被加密为"tkzwsdf".试写一算法将输入的文本串进行加密后输出；另写一算法，将输入的已加密的文本串进行解密后输出。

4.8 写一算法void StrReplace(char *T, char *P, char *S),将T中首次出现的子串P替换为串S。注意：S和P的长度不一定相等。可以使用已有的串操作。

4.9 将NaveStrMatch改写为输出目标串中所有与模式串匹配的有效位移。

*4.10 利用4.9的结果写一算法void StrReplaceAll(char *T, char *P, char *S),将T中出现的所有与P相等的不重叠子串替换为S，这里S和P的长度不一定相等。

4.11 若S和T是用结点大小为1的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现的字符。