首页
登录
从业资格
阅读以下说明和流程图,填补流程图中的空缺,将解答填入答题纸的对应栏内 。 【
阅读以下说明和流程图,填补流程图中的空缺,将解答填入答题纸的对应栏内 。 【
考试题库
2022-08-02
73
问题
阅读以下说明和流程图,填补流程图中的空缺,将解答填入答题纸的对应栏内 。【说明】下面流程图的功能是:在给定的两个字符串中查找最长的公共子串,输出该公共子串的长度 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
本试题收录于:
初级程序员题库软件水平考试初中高级分类
初级程序员
软件水平考试初中高级
相关试题推荐
阅读以下说明,回答问题1至问题2,将解答填入答题纸对应的解答栏内。 【说明】
阅读以下说明,回答问题1至问题4,将答案填入答题纸对应的解答栏内。(注:此题为思
阅读下列说明信息,回答问题1至问题5。将答案填入答题纸对应的解答栏内。 【说明
阅读以下说明,回答问题1至问题5,将解答填入答题纸对应的解答栏内。 【说明】
阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。 【说明】 某
阅读以下说明,回答问题l至问题4,将解答填入答题纸对应的解答栏内。 【说明】
阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。 【说明】 某
阅读以下说明,回答问题1至问题4,将解答填入答题纸对应的解答栏内。(注:此题为
阅读以下说明,回答问题l至问题4,将解答填入答题纸对应的解答栏内。 【说明】
阅读下列说明,回答问题1至问题3,将解答填入答题纸的对应栏内。 【说明】 某
随机试题
如你所知道的,人生常比作航海。Asyouknow,lifeisoftencomparedtoavoyage.同种类的东西相比用compared
Thesemagnificent______buildingsdemonstratethegreatintelligenceofthelab
Allmammalsfeedtheiryoung.Belugawhalemothers,forexample,nursetheir
[originaltext]Q:Hello.Isthisyourmanager’soffice?[/originaltext][original
A.医生诊断时应考虑患者的各方面因素 B.医生治疗时应努力使患者受益 C.医
在教育活动中,教育者是教育活动的主导因素。( )
客户下达的交易指令(),期货公司未予拒绝而进行交易造成客户的损失,由期货公司承
左边给定的是多面体的外表面,右边哪一项能由它折叠而成?请把它找出来。 A.如上
企业人工成本一般包括( )。A.劳动报酬总额 B.福利费用 C.房屋折旧费
牛黄中含有的主要成分是A.蜕皮激素 B.可水解鞣质 C.复合鞣质 D.胆汁
最新回复
(
0
)