数据结构考研分类复习真题 第四章 串[10]

第五部分算法设计

．设st为两个字符串分别放在两个一维数组中mn分别为其长度判断t是否为s的子串如果是输出子串所在位置（第一个字符）否则输出（注用程序实现）【南京航空航天大学 九(分)】

．输入一个字符串内有数字和非数字字符如akx ?gef将其中连续的数字作为一个整体依次存放到一数组ａ中例如放入ａ［０］放入ａ［１］……编程统计其共有多少个整数并输出这些数【上海大学 一 （分）】

． 以顺序存储结构表示串设计算法求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度【东南大学 五 （分）】

类似本题的另外叙述有

（）如果字符串的一个子串（其长度大于）的各个字符均相同则称之为等值子串试设计一算法输入字符串S以！作为结束标志如果串S中不存在等值子串则输出信息无等值子串否则求出（输出）一个长度最大的等值子串【华中科技大学 】

例如若S=abcabc!则输出无等值子串若S=abceebccadddddaaadd!则输出ddddd

．假设串的存储结构如下所示编写算法实现串的置换操作【清华大学 五（分）】

TYPE strtp =RECORD

ch: ARRAY[maxlen] OF char;

curlen:maxlen

END;

．函数void insert(char*schar*tint pos)将字符串t插入到字符串s中插入位置为pos请用c语言实现该函数假设分配给字符串s的空间足够让字符串t插入（说明不得使用任何库函数）【北京航空航天大学 六 （分）】

[] [] [] [] [] [] [] [] [] [] [] []