2. 从业资格
  3. 阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内 。 【

阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内 。 【

考试题库2022-08-02  48
问题 阅读以下说明和流程图，填补流程图中的空缺，将解答填入答题纸的对应栏内  。【说明】下面流程图的功能是：在给定的两个字符串中查找最长的公共子串，输出该公共子串的长度 L 及其在各字符串中的起始位置 （L=0时不存在公共字串）。例如，字符串"The light is not bright tonight ” 与“ Tonight the light is not bright ”的最长公共子串为 "The 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的指定字符串是否完全相同（该过程的流程略)。【流程图】
选项
答案
解析 （1）N 或 min(M，N)      
（2）M-L+1
（3）N-L+1   
（4）L-1
（5）L，I， J

本题考查对算法流程图的理解和绘制能力。这是程序员必须具有的技能 。
本题的算法可用来检查某论文是否有大段抄袭了另一论文 。"the light is not bright tonight" 是著名的英语绕口令，它与 "Tonight the light is not bright" 大同小异 。
由于字符串 A 和 B 的长度分别为 M 和 N ，而且M≥N≥1，所以它们的公共子串长度L 必然小于或等于 N。题中采用的算法是，从最大可能的公共子串长度值L 开始逐步递减，在 A、B 字符串中查找是否存在长度为 L 的公共子串。因此，初始时，应将 min (M，N) 送L，或直接将 N 送 L。 (1) 处应填写 N 或 min（M，N），或其他等价形式。
对每个可能的 L 值，为查看 A、B 串中是否存在长度为 L 的公共子串，显然需要执行双重循环。 A 串中，长度为 L 的子串起始下标可以从 1 开始直到 M-L+1 (可以用实例来检查其正确性); B 串中，长度为 L 的子串起始下标可以从 1 开始直到 N-L+1。因此双重循环的始值和终值就可以这样确定，即 (2)处应填 M-L+1 ，或等价形式;(3)处 应填 N-L+1 或等价形式（注意循环的终值应是最右端子串的下标起始值）。
A 串中从下标 1开始长度为 L 的子串可以描述为 A[I:I+L-1]; B 串中从下标J开始 长度为 L 的子串可以描述为 A[J:J+L-1]。因此，双重循环体内，需要比较这两个子串（题中采用调用专门的函数过程或子程序来实现）。
如果这两个子串比较的结果相同，那么就已经发现了 A、B 串中最大长度为 L 的公共子串，此时，应该输出公共子串的长度值 L、在A 串中的起始下标 I、在B 串中的起始下标 J。因此，(5) 处应填L，I， J (可不计顺序)。
如果这两个子串比较的结果不匹配，那么就需要继续执行循环。如果直到循环结束仍然没有发现匹配子串时，就需要将 L 减少 1 （（4）处填L-1或其等价形式）。只要 L 非 0，则还可以继续对新的L 值执行双重循环。如果直到 L=0，仍没有发现子串匹配， 则表示 A、B 两串没有公共子串。
转载请注明原文地址:https://tihaiku.com/congyezige/2427175.html
本试题收录于： 初级程序员题库软件水平考试初中高级分类

初级程序员

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)