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

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

　　 ．在字符串模式匹配的KMP算法中 求模式的next数组值的定义如下 【北京邮电大学   二（ 分）】

　　next［j］=

　　请问

　　（ ）当j= 时 为什么要取next[ ]= ？

　　（ ）为什么要取max{K} K最大是多少？

　　（ ）其它情况是什么情况 为什么取next[j]= ?

　　 ．给出KMP算法中失败函数f的定义 并说明利用f进行串模式匹配的规则 该算法的技术特点是什么？【东南大学 一 （ 分） 一 （ 分） 一 （ 分）】

　　 ． 在模试匹配KMP算法中所用失败函数f的定义中 为何要求p p ……pf(j)为p p ……pj两头匹配的真子串？且为最大真子串？ 【东南大学 一 （ 分）】

　　 ．如果两个串含有相等的字符 能否说它们相等？【西安电子科技大学 软件 一 （ 分）】

　　 ．设S S 为串 请给出使S //S =S //S 成立的所有可能的条件（//为连接符） 【长沙铁道学院   三 ( 分)】【国防科技大学  一 】

　　 ．已知 s ＝ （xyz）＋＊ t ＝ （x＋z）＊y 试利用联结 求子串和置换等基本运算 将 s 转化为 t 【北方交通大学 一 （ 分）】【山东科技大学 一 （ 分）】