2. 从业资格
  3. 阅读以下说明和流程图，将应填入（n）处的字句写在答题纸的对应栏内。 【说明】

阅读以下说明和流程图，将应填入（n）处的字句写在答题纸的对应栏内。 【说明】

考试题库2022-08-02  83
问题 阅读以下说明和流程图，将应填入（n）处的字句写在答题纸的对应栏内。【说明】 下面的流程图旨在统计指定关键词在某一篇文章中出现的次数。设这篇文章由字符A(0)，…，A(n-1)依次组成，指定关键词由字符B(0)，…，B(m-1)依次组成，其中n>m≥1。注意，关键词的各次出现不允许有交叉重叠。例如，在“aaaa”中只出现两次“aa”。该流程图采用的算法是：在字符串A中，从左到右寻找与字符串B相匹配的并且没有交叉重叠的所有子串。流程图中，i 为字符串 A 中当前正在进行比较的动态子串首字符的下标，j为字符串B的下标，k为指定关键词出现的次数。【流程图】
选项
答案
解析 本题考查用流程图描述算法的能力。在文章中查找某关键词出现的次数是经常碰的问题。例如，为了给文章建立搜索关键词，确定近期的流行语，迅速定位文章的某个待修改的段落，判断文章的用词风格，甚至判断后半本书是否与前半本书是同一作者所写（用词风格是否一致）等，都采用了这种方法。流程图最终输出的计算结果 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，l ，…，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＜m 时就发现了字符不等的情况，这说明此处并不出现关键词。 因此流程图中用 j＜m来区分找到与没有找到关键词的两种情况。对于 j=m，己找到一处关键词的情况，显然应该执行 k=k+1，对关键词出现次数的变量 k进行增 1计算。同时，为了继续进行以后的判断，应将字符串  A 的下标 i右移 m（这是因为题中假设关键词的出现不允许重叠）。因此（3）处应填写 i+m，表示应该从已出现的关键词后面开始再继续进行判断。由于此时的   j=m，书写i+j的答案也是正确的，但这不是程序员的好习惯，因为这不符合逻辑思维的顺势，在程序不断修改的过程中容易出错。不少考生在（3）处填写i+1，这意味着下次判断关键词将从A（i+1）开始，这就 使关键词的出现有可能发生部分重叠的现象。流程图中，对于 j＜m 的情况，表示刚才判断关键词时并非各个字符都完全相同，也就是说，刚才的判断结论是此处并没有出现关键词。即 A（i）开始的子串并不是关键词。因此，下次判断关键词应该以 A（i+1）开始，即（4）处应填 i+1。在下次判断关键词之前还应该判断是否全文已经判断完。最后一次小循环判断应该是对 A（n-m），A（n-m+1），… ，A（n一1）的判断。下标 n-m来自从 n-1 倒数 m个数。可以先试验写出A（n-m），A（n-m+1），… ，A（n一1），再判断其个数是否为m。经检查，个数为 （n-1）-（n-m）+1=m个，所以这是正确的。也可以用例子来检查次数是否正确。检查次数是程序员的基本功，数目的计算很容易少一个或多一个。 既然最后一次判断关键词应该是对A（n-m），A（n-m+1），… ，A（n一1）的判断，即对 i=n-m进行的小循环判断，所以当 i>n-m 时就应该停止大循环，停止再查找关键词了。
转载请注明原文地址:https://tihaiku.com/congyezige/2428380.html
本试题收录于： 初级程序员题库软件水平考试初中高级分类

初级程序员

软件水平考试初中高级

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