当前位置:首页计算机类软件水平考试初级程序员->阅读以下说明和流程图,填补流程图中空缺,将解答填入答题纸对应

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

[说明]

下面流程图功能是:在给定两个字符串中查找最长公共子串,输出该公共子串长度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

【解析】

本题考查对算法流程图理解和绘制能力。这是程序员必须具有技能。

本题算法可用来检查某论文是否有大段抄袭了另一论文。"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子串起始下标可以从l开始直到M-L+1(可以用实例来检查其正确性);B串中,长度为L子串起始下标可以从1开始直到N-L+1。因此双重循环始值和终值就可以这样确定,即(2)处应填M-L+1,或等价形式;(3)处应填N-L+1或等价形式(注意循环终值应是最右端子串下标起始值)。

A串中从下标I开始长度为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两串没有公共子串。

更新时间:2022-08-06 07:47
纠错

你可能感兴趣的试题

单选题

高级系统分析师,专项练习,软件水平考试《高级系统分析师》押题

  • A.V(S2)和P(S4)
  • B.P(S2)和V(S4)
  • C.P(S2)和P(S4)
  • D.V(S2)和V(S4)
查看答案
单选题

高级系统分析师,专项练习,软件水平考试《高级系统分析师》押题

  • A.V(S1)P(S2)和V(S3)
  • B.P(S1)V(S2)和V(S3)
  • C.V(S1)V(S2)和V(S3)
  • D.P(S1)P(S2)和V(S3)
查看答案
单选题

高级系统分析师,专项练习,软件水平考试《高级系统分析师》押题

  • A.P(S4)和V(S4)V(S5)
  • B.V(S5)和P(S4)P(S5)
  • C.V(S3)和V(S4)V(S5)
  • D.P(S3)和P(S4)V(P5)
查看答案
单选题

高级系统分析师,专项练习,软件水平考试《高级系统分析师》押题

  • A.P(S3)和V(S4)V(S5)
  • B.V(S3)和P(S4)P(S5)
  • C.P(S3)和P(S4)P(S5)
  • D.V(S3)和V(S4)V(S5)
查看答案
单选题

高级系统分析师,专项练习,软件水平考试《高级系统分析师》押题

  • A.P(S2)和P(S4)
  • B.P(S2)和V(S4)
  • C.V(S2)和P(S4)
  • D.V(S2)和V(S4)
查看答案
单选题

高级系统分析师,专项练习,软件水平考试《高级系统分析师》押题

  • A.V(S1)、P(S1)和V(S2)V(S3)
  • B.P(S1)、V (S1)和V(S2)V(S3)
  • C.V(S1)、V(S2)和P(S1)V(S3)
  • D.P(S1)、V(S2)和V(S1)V(S3)
查看答案
单选题

高级系统分析师,专项练习,软件水平考试《高级系统分析师》押题

  • A.序列图
  • B.状态图
  • C.通信图
  • D.活动图
查看答案
单选题

高级系统分析师,专项练习,软件水平考试《高级系统分析师》押题

  • A.合并分叉
  • B.分支
  • C.合并汇合
  • D.流
查看答案
单选题

高级系统分析师,专项练习,软件水平考试《高级系统分析师》押题

  • A.产甲2套,乙3套
  • B.生产甲1套,乙4套
  • C.生产甲3套,乙4套
  • D.生产甲4套,乙2套
查看答案
单选题

高级系统分析师,专项练习,软件水平考试《高级系统分析师》押题

  • A.见图A
  • B.见图B
  • C.见图C
  • D.见图D
查看答案