2. 计算机
  3. 阅读以下说明和流程图，填补流程图中的空缺(1)～(5)，将解答填入对应栏内。 【说明】 下面流程图的功能是：在已知字符串A中查找特定字符串B，如果存在，则输出B串首字符在A串中的位置，否则输出-1。设串A由n个字符A(0)，A(1)，…，A(n-1)

阅读以下说明和流程图，填补流程图中的空缺(1)～(5)，将解答填入对应栏内。 【说明】 下面流程图的功能是：在已知字符串A中查找特定字符串B，如果存在，则输出B串首字符在A串中的位置，否则输出-1。设串A由n个字符A(0)，A(1)，…，A(n-1)

admin2009-09-20  29
问题 阅读以下说明和流程图，填补流程图中的空缺(1)～(5)，将解答填入对应栏内。
【说明】
   下面流程图的功能是：在已知字符串A中查找特定字符串B，如果存在，则输出B串首字符在A串中的位置，否则输出-1。设串A由n个字符A(0)，A(1)，…，A(n-1)组成，串B由m个字符B(0)，B(1)，…，B(m-1)组成，其中n≥m＞0。在串A中查找串 B的基本算法如下：从串A的首字符A(0)开始，取子串A(0)A(1)…A(m-1)与串B比较；若不同，则再取子串A(1)A(2)…A(m)与串B比较，依次类推。
   例如，字符串“CABBRFFD”中存在字符子串“BRF”(输出3)，不存在字符子串“RFD”(输出-1)。
   在流程图中，i用于访问串A中的字符(i=0，1，…，n-1)，j用于访问串B中的字符(j=0，1，…，m-1)。在比较A(i)A(i/1)…A(i+m-1)与B(0)B(1)…B(m-1)时，需要对 A(i)与B(0)、A(i+1)与B(1)、…、A(i+j)与B(j)等逐对字符进行比较。若发现不同，则需要取下一个子串进行比较，依此类推。
【流程图】
选项
答案(1) j+1 (2) i+1 (3) 0 (4) i (5) -1
解析 本题采用的是最简单的字符子串查找算法。
   在串A中查找是否含有串B，通常是在串A中从左到右取逐个子串与串B进行比较。在比较子串时，需要从左到右逐个字符进行比较。
   题中已设串A的长度为n，存储数组为A，动态指针标记为i；串B的长度为m，存储数组为B，动态指针标记为j。
   如果用伪代码来描述这种算法的核心思想，则可以用以下的两重循环来说明。
   外循环为：
   For  i=0  to  n-m  do
   A(i)A(i+1)...A(i+m-1)～B(0)B(1)...B(m-1)
   要实现上述比较，可以采用内循环：
   For  j=0  to  m-1  do
   A(i+j)～B(j)
   将这两重循环合并在一起就是：
   For  i = 0  to  n-1  do
   For  j = 0  to  m-1  do
   A(i+j)～B(j)
   这两重循环都有一个特点：若发现比较的结果不相同时，就立即退出循环。因此，本题中的流程图可以间接使用循环概念。
   初始时，i与j都赋值0，做比较A(i+j)～B(j)。
   若发现相等，则继续内循环(走图的左侧)，j应该增1，继续比较，直到j=m为止，表示找到了子串(应输出子串的起始位置i)；若发现不等，则退出内循环，继续开始外循环(走图的右侧)，j应恢复为0，i应增1，继续比较，直到i＞n-m为止，表示不存在这样的子串(输出-1)。
   在设计流程图时，主要的难点是确定循环的边界(何时开始，何时结束)。当难以确定边界值变量的正确性时，可以用具体的数值之例来验证。这是程序员应具备的基本素质。
转载请注明原文地址:https://kaotiyun.com/show/CIjZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

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