反馈
问题:
下面的流程图可在正文字符串T(1:L)中计算关键词字符串K(l:m)出现的次数(用n表示)。其中,L为字符串T的长度,m为字符串K的长度(m<L)„为便于模糊查找,关键词中的字符“?”可以匹配任意一个字符。<br/><br/> 在该流程图中,先从T中取出长度为m的子串存入A中,再将A与K进行逐个字符的比较(其中,K可以包含字符“? ”)。注意:从正文字符串中取出的关键词字符串不允许交叉。例如,“aaaaaa”中有3个关键词字符串“aa”。<br/><br/> 【流程图】<br/><br/> <img style='width:100%;' src="https://files.lightsoft.tech/rkfiles/ruankao_work_version_0103/userfile/image/cyx-2011-s-x-1.jpg">
选项 :
【问题:1.1】阅读以下说明和流程图,填补流程图中的空缺(1)〜(5),将解答填入答题纸的对应栏内。
答案:
解析:
(1) L-m+1或等价表示<br/>(2) i+m-1或等价表示<br/>(3) j+1或等价表示<br/>(4) n+1或等价表示<br/>(5) A(j)=K(j)或等价表示<br/>根据题意,正文字符串中的各个字符依次存放在T(1) ,T(2) ,…,T(L)中,关键词字符串中的各个字符依次存放在K(1) ,K(2) ,…,K(m)。显然i是字符数组T的动态下标指针。 为了与关键词字符串进行比较,题中需要每次从数组T中连续取出m个元素放在数组A 中。第1次将T(l:m)存入A(1:m),第2次将T(2:m+1)存入A(1:m),…,第i次就应将T(i:m+i-1)存入A(1:m),最后一次应将T(L-m+1:L)存入A(l:m)。因此,流程图的(2) 中 应填m+i-1,由于m+i-1必须小于或等于L。当m+i-1>L时,即当i>L-m+1时,就不应该再取子串了。因此流程图的(1) 处应填L-m+1。<br/>流程图右下方一片描述了字符数组A(i),A(i+1),…,A(i+m-1)与字符数组K(1) ,K(2) ,…, K(m)的比较过程。题中用j表示数组K的动态下标指针,j=1,2,……,m。显然,数组A的动态下标指针为i+j-1(j=1,2,…,m)。两个字符数组都从左到右逐个字符地进行比较,如果发现有不一致的字符,就结束比较,将i增1后准备继续从数组T中取新的子串放在A中。 如果一直到比较结束,发现两个数组中对应的各个字符都是一致的,那么,就找到了一处关键词。此时,找到关键词的计数器n应增l(n+1—n)。因此,流程图的(4) 处应填n+1。<br/>字符数组A与K的比较过程关键是逐个字符A(j)与K(j)的比较。由于允许模糊査找,即K(j)中的字符 "?" 可以与任何字符匹配。因此,可以写成判断“A(j)=K(j) or K(j)= "?""是否为真。只要K(j)= "?"",比较结果就一定为真。因此,流程图的(5) 处应填 A(j)=K(j)。如果比较结果为真,则还需要执行j+1→j,准备继续往下比较。因此流程图的(3) 处应填 j+1。 <br/>