niusouti.com

KMP模式匹配算法是由（）同时发现的，因此而得名。A、莫里斯B、克努特C、普拉特D、克鲁伊特

题目

KMP模式匹配算法是由（）同时发现的，因此而得名。

  • A、莫里斯
  • B、克努特
  • C、普拉特
  • D、克鲁伊特
相似考题

1.在KMP算法中，已知模式串为ADABCADADA，请写出模式串的next数组值()A.0,1,1,2,1,1,2,3,4,3B.1,2,3,2,1,1,2,4,4,3C.0,1,1,1,2,1,2,3,4,3D.2,1,1,2,1,1,2,3,3,4

2.设目标为t=“abcaabbabcabaacbacba”,模式为p=“abcabaa” ① 计算模式p的naxtval函数值; ② 不写出算法,只画出利用KMP算法进行模式匹配时每一趟的匹配过程。

3.当运用改进的模式匹配算法时，模式串P='ABAABCAC'的next函数值序列为(41)。A．1222312B．1122312C．1122212D．122312

4.已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”。采用KMP算法进行匹配，第一次出现“失配”(s[i]≠t[j])时，i=j=5，则下次开始匹配时，i和j的值分别是()。A.i=1,j=0B.i=5,j=0C.i=5,j=2D.i=6,j=2

更多“KMP模式匹配算法是由（）同时发现的，因此而得名。”相关问题

  • 第1题：

    ●在KMP模式匹配算法中，需要求解模式串p的next函数值，其定义如下（其中，j为模式串中字符的序号）。对于模式串“abaabaca”，其next函数值序列为(57)。

    (57)

    A. 01111111

    B.01122341

    C.01234567

    D.01122334


    正确答案：B

  • 第2题：

    在字符串的KMP模式匹配算法中，需先求解模式串的next函数值，其定义如下式所示，j表示模式串中字符的序号（从1开始）。若模式串p为"abaac"，则其next函数值为 （ ） 。

    A.01234
    B.01122
    C.01211
    D.01111

    答案：B
    解析：
    根据公式依次推导即可。

  • 第3题：

    “象脚鼓舞”是因为舞蹈所用之鼓形似大象脚，因此而得名。( )


    答案：对
    解析：

  • 第4题：

    KMP模式匹配算法的改进之处是（）。

    • A、主串指针不需要回溯
    • B、模式串的指针来回移动
    • C、主串的指针也会回到之前比较过的字符
    • D、时间复杂度可以达到O（nm）

    正确答案:A

  • 第5题：

    KMP算法的最大特点是指示主串的指针不需要回溯。


    正确答案:正确

  • 第6题：

    朴素模式匹配算法，算法运行时间为O（m*n）。


    正确答案:正确

  • 第7题：

    烹茗井在灵隐山，苏东坡曾经用它煮饮茶汤，因此而得名。


    正确答案:错误

  • 第8题：

    Apriori算法是一种常见的（）。

    • A、关联规则发现算法
    • B、聚类分析算法
    • C、分类算法
    • D、序列模式发现算法

    正确答案:A

  • 第9题：

    多选题
    KMP模式匹配算法是由（）同时发现的，因此而得名。
    A

    莫里斯

    B

    克努特

    C

    普拉特

    D

    克鲁伊特


    正确答案： A,C
    解析： 暂无解析

  • 第10题：

    单选题
    设串长为n，模式串长为m，则KMP算法所需的附加空间为（）。
    A

    O（m）

    B

    O（n）

    C

    O（m*n）

    D

    O（nlog2m）


    正确答案： C
    解析： KMP算法时间复杂度为O(m+n)，空间复杂度是O(m).因为KMP算法设计到next数组的存储，且next数组是基于模式串长度计算的。
    BF算法（普通匹配算法）时间复杂度为O(m*n)；空间复杂度为O(1).

  • 第11题：

    判断题
    KMP算法时间代价为O（n）。
    A

    对

    B

    错


    正确答案： 对
    解析： 暂无解析

  • 第12题：

    单选题
    模式匹配的改进算法是D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的，因此人们称它为克努特-莫里斯-普拉特操作简称（）。
    A

    KMP算法

    B

    Prime算法

    C

    克鲁斯卡尔算法

    D

    迪杰斯特拉算法


    正确答案： D
    解析： 暂无解析

  • 第13题：

    在字符串的KMP模式匹配算法中，需先求解模式串的next函数值，其定义如下式所示，j表示模式串中字符的序号（从1开始）。若模式串p为“abaac”，则其next函数值为 (60) 。

    A.01234

    B.01122

    C.01211

    D.01111


    正确答案：B
    本题考查字符串的模式匹配运算知识。KMP是进行字符串模式匹配运算效率较高的算法。根据对next函数的定义，模式串前两个字符的next值为0、1。对于第3个字符“a”，其在模式串中的前缀为“ab”从该子串找不出前缀和后缀相同的部分，因此，根据定义，该位置字符的next值为1。对于第4个字符“a”，其在模式串中的前缀为“aba”，该子串只有长度为l的前缀“a”和后缀“a”相同，根据定义，该位置字符的next值为2。对于第5个字符“a”，其在模式串中的前缀为“abaa”，该子串只有长度为1的前缀“a”和后缀“a”相同，根据定义，该位置字符的next值为2。综上可得，模式串“abaac”的next函数值为01122。

  • 第14题：

    KMP算法的特点是在模式匹配时指示主串的指针()。

    A.不会变大
    B.不会变小
    C.都有可能
    D.无法判断

    答案：B
    解析：
    在KMP算法中，模式匹配时主串不会回溯，所以主串的指针不会变小。

  • 第15题：

    KMP算法的特点是在模式匹配时指示主串的指针不会回溯。


    正确答案:正确

  • 第16题：

    红豆杉果实似红豆，叶似杉木，因此而得名（）


    正确答案:正确

  • 第17题：

    KMP模式匹配算法是由（）同时发现的，因此而得名。

    • A、莫里斯
    • B、克努特
    • C、普拉特
    • D、克鲁伊特

    正确答案:A,B,C

  • 第18题：

    KMP算法时间代价为O（n）。


    正确答案:正确

  • 第19题：

    模式匹配的改进算法是D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的，因此人们称它为克努特-莫里斯-普拉特操作简称（）。

    • A、KMP算法
    • B、Prime算法
    • C、克鲁斯卡尔算法
    • D、迪杰斯特拉算法

    正确答案:A

  • 第20题：

    判断题
    朴素模式匹配算法，算法运行时间为O（m*n）。
    A

    对

    B

    错


    正确答案： 对
    解析： 暂无解析

  • 第21题：

    单选题
    Apriori算法是一种常见的（）。
    A

    关联规则发现算法

    B

    聚类分析算法

    C

    分类算法

    D

    序列模式发现算法


    正确答案： B
    解析： 暂无解析

  • 第22题：

    判断题
    KMP算法的特点是在模式匹配时指示主串的指针不会回溯。
    A

    对

    B

    错


    正确答案： 错
    解析： 暂无解析

  • 第23题：

    判断题
    KMP算法的最大特点是指示主串的指针不需要回溯。
    A

    对

    B

    错


    正确答案： 错
    解析： 暂无解析

  • 第24题：

    单选题
    KMP模式匹配算法的改进之处是（）。
    A

    主串指针不需要回溯

    B

    模式串的指针来回移动

    C

    主串的指针也会回到之前比较过的字符

    D

    时间复杂度可以达到O（nm）


    正确答案： D
    解析： 暂无解析

相关内容