首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和流程图,填补流程图中的空缺。 【说明】 下面流程图的功能是:在给定的两个字符串中查找最长的公共子串,输出该公共子串的长度L及其在各字符串中的起始位置(L一O时不存在公共字串)。例如,字符串“Thelight is not bright
阅读以下说明和流程图,填补流程图中的空缺。 【说明】 下面流程图的功能是:在给定的两个字符串中查找最长的公共子串,输出该公共子串的长度L及其在各字符串中的起始位置(L一O时不存在公共字串)。例如,字符串“Thelight is not bright
admin
2016-09-08
29
问题
阅读以下说明和流程图,填补流程图中的空缺。
【说明】
下面流程图的功能是:在给定的两个字符串中查找最长的公共子串,输出该公共子串的长度L及其在各字符串中的起始位置(L一O时不存在公共字串)。例如,字符串“Thelight is not bright tonight”与“Tonight the light is not bri.ght”的最长公共子串为“he light isnot bright”,长度为22,起始位置分别为2和10。
设A[1:M]表示由M个字符A[l],A[2],…,A[M]依次组成的字符串;B[1:N]表示由N个字符B[l],B[2],…,B[N]依次组成的字符串,M≥N≥l。
本流程图采用的算法是:从最大可能的公共子串长度值开始逐步递减,在A、B字符串中查找是否存在长度为L的公共子串,即在A、B字符串中分别顺序取出长度为L的子串后,调用过程判断两个长度为L的指定字符串是否完全相同(该过程的流程略)。
【流程图】
选项
答案
(1)N或min(M,N) (2)M一L+1 (3)N一L+1 (4)1一1 (5)L,I,J
解析
本题考查对算法流程图的理解和绘制能力。这是程序员必须具有的技能。
本题的算法可用来检查某论文是否有大段抄袭了另一论文。“The light is not brighttonight”是著名的英语绕口令,它与“Tonight the light is not bright”大同小异。
由于字符串A和B的长度分别为M和N,而且M≥N≥l,所以它们的公共子串长度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+l,或等价形式;(3)处应填N一L+l或等价形式(注意循环的终值应是最右端子串的下标起始值)。
A串中从下标I开始长度为L的子串可以描述为A[I:I+L一1];B串中从下标J开始长度为L的子串可以描述为A[J:J+L一l]。因此,双重循环体内,需要比较这两个子串(题中采用调用专门的函数过程或子程序来实现)。
如果这两个子串比较的结果相同,那么就已经发现了A、B串中最大长度为L的公共子串,此时,应该输出公共子串的长度值L、在A串中的起始下标I、在B串中的起始下标J。因此,(5)处应填L,I,J(可不计顺序)。
如果这两个子串比较的结果不匹配,那么就需要继续执行循环。如果直到循环结束仍然没有发现匹配子串时,就需要将L减少l((4)处填L一l或其等价形式)。只要L非0,则还可以继续对新的L值执行双重循环。如果直到L=0,仍没有发现子串匹配,则表示A、B两串没有公共子串。
转载请注明原文地址:https://jikaoti.com/ti/cHW7FFFM
本试题收录于:
程序员下午应用技术考试题库软考初级分类
0
程序员下午应用技术考试
软考初级
相关试题推荐
在编辑Word2007文档时,若多次使用剪贴板移动文本内容,当操作结束时,剪贴板中的内容为__________。
Access数据库属于______数据库。
小张刚接到领导分配的数据分析任务,他第一步应当首先________。
Windows系统的快捷方式确切的含义是______。
在Access2007中,若要想查询所有姓名为2个汉字的学生记录,应在准则中输入______。
在Access中,查询“学生”数据表的所有记录及字段的SQL语句是______。
下列关于Word绘图功能的叙述中,不正确的是__________。
框架在网页布局中主要起什么作用?主页中定义了几个框架,分别显示哪个文档?网页中使用的数据库连接引擎是什么?连接的后台数据库文件名是什么?
[说明]请根据网页显示的效果图,将HtML文本(n)处的解答填写在相应的解答栏内。[上图网页中的元素说明][HTML文档代码]<!DOCTYPEHTMLPUBLIC“-//W3C//DTDHTML
随机试题
胎盘的实质部分是指:
A注册会计师负责审计甲公司2012年度财务报表。在了解内部控制时,A注册会计师遇到下列事项,请代为做出正确的专业判断。(根据2009年新制度考题修订)持续监督活动应当贯穿于日常经营活动与常规管理工作。下列活动中属于持续监督活动的是()。
斜Y坡口焊接裂纹试验,应对试件的5个横断面进行裂纹检查。
Youlookpale,What’swrong______you?
发生腹部损伤时下列哪项陈述不正确
【背景资料】建设单位投资兴建写字楼工程,地下1层,地上5层.建筑面积为60000平方米,总投资额4200.00万元。建设单位编制的招标文件部分内容有:“质量标准为合格;工期自2018年5月1日起至2019年9月30日止;采用工程量清单计价模式;项
《学记》中“道而弗牵,强而弗抑,开而弗达”的教学思想,体现的教学原则是()
有关研究表明,手机比电脑更伤人,因为手机屏幕小,玩手机时注意力更投入,目不转睛,因此更伤眼。使用电脑时,人们的肢体还能活动活动,可是手机控往往很少活动,这对身心健康更为不利。如果以下各项为真,最能削弱上述论断的是()。
根据法律的规定,下列民事主体中享有优先受偿权的有
Studiesalonecanconductustothatenjoymentwhichisbestinqualityandinfiniteinquantity.
最新回复
(
0
)