题库 高中信息
题干
查找最短26个字母字符串: 在文本框Text1中输入任意一串仅包含小写字母的字符串（长度n>=26），要求找到长度最小的一段区间，能够包含全部26个小写英文字母。小王设计了VB程序用于搜索最短字符串，单击“查找”按钮 Command1，若无解，则在标签 Label1中输出“无解！”，反之程序在标签 Labell中输出该最小区间的长度以及字符的开始位置，并在文本框Text2中输出相应的最短字符串，程序界面如图所示。
查找最短26个字母字符串的算法可描述为:
1）确定初始右边界: 从第1个字符开始，向右搜索到包含全部26个字母的子串，并因此而确定右边界，同时记录每个字母在子串中出现过的次数。
2）调整子串左边界: 若左边界有重复的字母则表明该子串可缩短，故左边界可右移1位，……直到找到一个符合条件的子串并记录，然后子串左边界再右移1位。
3）调整子串右边界: 子串右边界继续右移，在新子串符合条件后，记录并进行比较。重复2）各调整步骤，直至遍历完整个字符串，获得并输出满足条件的最小长度字符串。
实现上述功能的VB程序如下，请回答下列问题:
（1）对于字符串“ qbwcadsgeqbdatcy”，包括字母 abcde的最短字符串长度为___________（填数字）
（2）请在划线处填入合适的代码。
Const n=200
Dim i As Integer, k As Integer, length As Integer, L As Integer
Dim pos As Integer, sl As String, res As String
Dim f(1 To 26) As Integer ＇数组f记录每个小写英文字母的出现次数
Dim s(1 To n)As Integer ＇数组s记录每个输入字符在字母表中的位置
Private Sub Command1_ Click
Next i
k=0: pos=1: length=n
For i=1 To 26
f(i)=0
Next i
For i=1 To Len(sl)
If f(s(i))=0 Then k=k+1
f(s(i))=f(s(i))+1
Do While___________
f(s(pos))=f(s(pos))-1
If______________Then
k=k-1
If i-pos+1<length Then
length=i-pos+1
res=Mid (sl, pos, length)
L=pos
End If
End If
pos=pos+1
Loop
Next i
If res<>""Then
查找最短26个字母字符串的算法可描述为:
1）确定初始右边界: 从第1个字符开始，向右搜索到包含全部26个字母的子串，并因此而确定右边界，同时记录每个字母在子串中出现过的次数。
2）调整子串左边界: 若左边界有重复的字母则表明该子串可缩短，故左边界可右移1位，……直到找到一个符合条件的子串并记录，然后子串左边界再右移1位。
3）调整子串右边界: 子串右边界继续右移，在新子串符合条件后，记录并进行比较。重复2）各调整步骤，直至遍历完整个字符串，获得并输出满足条件的最小长度字符串。
实现上述功能的VB程序如下，请回答下列问题:
（1）对于字符串“ qbwcadsgeqbdatcy”，包括字母 abcde的最短字符串长度为___________（填数字）
（2）请在划线处填入合适的代码。
Const n=200
Dim i As Integer, k As Integer, length As Integer, L As Integer
Dim pos As Integer, sl As String, res As String
Dim f(1 To 26) As Integer ＇数组f记录每个小写英文字母的出现次数
Dim s(1 To n)As Integer ＇数组s记录每个输入字符在字母表中的位置
Private Sub Command1_ Click
res=" "
s1=Textl. Text
For i=1 To Len(s1)
s(i)= _____________Next i
k=0: pos=1: length=n
For i=1 To 26
f(i)=0
Next i
For i=1 To Len(sl)
If f(s(i))=0 Then k=k+1
f(s(i))=f(s(i))+1
Do While___________
f(s(pos))=f(s(pos))-1
If______________Then
k=k-1
If i-pos+1<length Then
length=i-pos+1
res=Mid (sl, pos, length)
L=pos
End If
End If
pos=pos+1
Loop
Next i
If res<>""Then
Text2 Text=res
Labell. Caption="最短长度: "+Str( length)+"开始位置: "+Str(L)Else
Labell. Caption="无解！"
End if
End Sub答案(点此获取答案解析）
