刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

阅读以下说明和流程图,填补流程图中的空缺,将解答填入答题纸的对应栏内。
[说明]
下面流程图的功能是:在给定的两个字符串中查找最长的公共子串,输出该公共子串的长度L及其在各字符串中的起始位置(L=0时不存在公共字串)。例如,字符串"The light is not bright tonight"与"Tonight the light is not bright"的最长公共子串为"he light is not bright",长度为22,起始位置分别为2和10。
设A[1:M]表示由M个字符A[1],A[2],…,A[M]依次组成的字符串;B[1:N]表示由N个字符B[1],B[2],…,B[N]依次组成的字符串,M≥N≥1。
本流程图采用的算法是:从最大可能的公共子串长度值开始逐步递减,在A、B字符串中查找是否存在长度为L的公共子串,即在A、B字符串中分别顺序取出长度为L的子串后,调用过程判断两个长度为L的指定字符串是否完全相同(该过程的流程略)。
[流程图]

使用微信搜索喵呜刷题,轻松应对考试!

答案:

N或rnin(M,N)
M-L+1
N-L+1
L-1
L,I,J

解析:

本题考查对算法流程图的理解和绘制能力。本题的算法用于查找两个字符串中的最长公共子串,并输出其长度及在各自字符串中的起始位置。

根据说明和流程图的分析,我们可以得出以下解释:

  1. 由于字符串A和B的长度分别为M和N,且M≥N≥1,所以它们的公共子串长度L必然小于或等于N。因此,初始时,应将min(M,N)或N送L,表示开始查找的最大可能的公共子串长度。所以(1)处填写N或min(M,N)。
  2. 对于A串,长度为L的子串的起始下标可以从1开始直到M-L+1。因此,(2)处应填写M-L+1或其等价形式。
  3. 对于B串,同样的逻辑,长度为L的子串的起始下标可以从1开始直到N-L+1。所以,(3)处应填写N-L+1或其等价形式。
  4. 如果两个子串比较的结果不匹配,则需要继续执行循环。此时需要减小L的值,所以(4)处应填写L-1。
  5. 如果找到了匹配的子串,即找到了最长公共子串,此时应输出公共子串的长度L以及在A、B串中的起始位置I和J。所以,(5)处应填写L,I,J(顺序不分先后)。

综上所述,答案应为:N或min(M,N);M-L+1;N-L+1;L-1;L,I,J。

创作类型:
原创

本文链接:阅读以下说明和流程图,填补流程图中的空缺,将解答填入答题纸的对应栏内。[说明]下面流程图的功能是:在

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share