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

四应用题

．名词解释串 【大连海事 一 (分) 】【河海大学 二（分）】

．描述以下概念的区别空格串与空串【大连海事大学 三（） (分)】

．两个字符串S和S的长度分别为m和n求这两个字符串最大共同子串算法的时间复杂度为T(mn)估算最优的T(mn)并简要说明理由 【北京工业大学 一 (分)】

．设主串S=xxyxxxyxxxxyxyx模式串T=xxyxy请问如何用最少的比较次数找到T在S中出现的位置？相应的比较次数是多少？ 【大连海事大学 四 (分)】

．KMP算法(字符串匹配算法)较Brute(朴素的字符串匹配)算法有哪些改进?【大连海事大学三((分)】

．已知模式串t=abcaabbabcab写出用KMP法求得的每个字符对应的next和nextval函数值【北京邮电大学 三 （分）】

．给出字符串abacabaaad在KMP算法中的next和nextval数组【北京邮电大学 三（分）】

．令t=abcabaa求其next 函数值和nextval函数值 【北方交通大学 一 （分）】

．已知字符串cddcdececdea计算每个字符的next和nextval函数的值【南京邮电大学 一 】

．试利用KMP算法和改进算法分别求p=abaabaa和p=aabbaab的next函数和nextval函数【东南大学 一（分）】

．已知KMP串匹配算法中子串为babababaa写出next数组改进后的next数组信息值（要求写出数组下标起点）【西南交通大学 二】

．求模式串T=abcaabbac 的失败函数Next(j)值【西安交通大学 四 (分)】

．字符串的模式匹配KMP算法中失败函数(NEXT)是如何定义的?计算模式串p=aabaabaaabc中各字符的失败函数值【石油大学 一 (分)】

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