阅读以下说明和流程图,将应填入__(n)__处的字句写在答题纸的对应栏内。
【说明】下面的流程图旨在统计指定关键词在某一篇文章中出现的次数。设这篇文章由字符A(0),…,A(n-1)依次组成,指定关键词由字符B(0),…,B(m-1)依次组成,其中n>m≥1。注意,关键词的各次出现不允许有交叉重叠。例如,在"aaaa"中只出现两次"aa"。该流程图采用的算法是:在字符串A中,从左到右寻找与字符串B相匹配的并且没有交叉重叠的所有子串。流程图中,i为字符串A中当前正在进行比较的动态子串首字符的下标,i为字符串B的下标,k为指定关键词出现的次数。【流程图】
参考答案:
(1)0→k (2)i+j (3)i+m (4)i+1 (5)i
解析:
本题考查用流程图描述算法的能力。 在文章中查找某关键词出现的次数是经常碰的问题。例如,为了给文章建立搜索关键词,确定近期的流行语,迅速定位文章的某个待修改的段落,判断文章的用 词风格,甚至判断后半本书是否与前半本书是同一作者所写(用词风格是否一致)等,都采用了这种方法。 流程图最终输出的计算结果k就是文章字符串A中出现关键词字符串B的次数。显然,流程图开始时应将k赋值0,以后每找到一处出现该关键词,就执行增1 操作k=k+1。因此(1)处应填0→k。 字符串A和B的下标都是从0开始的。所以在流程图执行的开始处,需要给它们赋值0。接下来执行的第一个小循环就是判断 A(i)A(i+1),…,A(i+j-1)是否完全等于B(0),B(1),…,B(m-1),其循环变量j=0,1,…,m-1。只要发现其中对应的 字符有一个不相等时,该小循环就结束,不必再继续执行该循环。因此,该循环中继续执行的判断条件应该是A(i+j)=B(j)且j<m。只要遇到 A(i+j)≠B(j)或者j=m(关键词各字符都已判断过)就不再继续执行该循环了。因此流程图的(2)处应填i+j。 许多考生在(2)处填i,当j增1变化后,仍然使用A(i)进行比较就不对了。因此,在检查循环程序段时应多走查一次循环。 如果(2)处整体的判断条件不成立,则该判断关键词的小循环结束。此时可能有两种情况。一是在j=0,1,…,m-1时全都成立A(i+j)=B(j) (找到了一处关键词),直到j=m时才结束小循环;二是在j