2022届高三信息技术选考总复习 专题18 简单遍历算法 课件-（53张PPT）

(共53张PPT)
专题18 简单遍历算法
1.在查找连续的数字串、多个英文单词、多个区间、压缩字符串等问题时，可以把系列看成是____个小段组成的，每个小段有______位置和______位置。在此类题目解题时，关键把握每一段(每个区间)的开始位置和结束位置。在专题15字符串处理章节中，已经学习了如何找出简单遍历过程中3条线索，第2线索也可以用循环结构来实现区间的开始位置和结束位置元素的遍历。
2.采用双重遍历是对一维数组同时扫描____个元素(开始位置和结束位置)，并且关注这两个元素之间的关系。以计算数组a中28，19，54，36，21共5个数排名为例，找出大于第i个数的个数k(用数组pm(1 To 5)来记录)，那么第i个数的排名为k＋1。方法一：从第1个数开始，与全部数据逐一进行比较，计算第1个数的排名，接着第2个数与全体数据进行比较，计算排名，因此每趟的比较区间是[1，5]。方法二：从第1个数开始，与他后面的数a(j)进行比较，如果该数小于后面的数，将pm(1)将增加1，否则pm(j)将增加1。在计算第j个元素排名时，他已经与前面数进行了比较且记录比较结果，因此不需要再次与前面的数据进行比较，第i个数的比较范围是[i＋1，5]。
开始
结束
多
两
3.简单排序即为这种双重遍历的典型例子，是后面将复习的内容，主要是明确查找区间两个位置的重要性。冒泡排序：前后两个元素之间进行比较与交换；选择排序：当前元素与当前为止的最小(或最大)元素进行比较与交换；插入排序：当前元素与前面(已经有序的元素)依次比较与交换。该种范式是循环结构内嵌套一个循环结构，要注意内循环的开始位置和结束位置，即左边界和右边界。
第i趟排序算法 左边界 右边界
从后往前冒泡 i n
从前往后冒泡 1 n－i＋1
选择排序 i＋1 n
插入排序 1 i－1
4.对分查找算法也涉及到左右边界问题。对分查找是在区间[i，j]范围内查找一个中间位置m的值a(m)，与要查找的数key比较。当key不等于a(m)时，如果在左边的半个区间，调整右边界为m－1，如果在右边的半个区间，调整左边界为m＋1，继续查找，直到这个数找到或者区间不存在。
5.尺取法(顾名思义，像尺子一样取一段)，即选取区间的______端点，然后根据实际情况不断地推进区间左右端点以得出答案。尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的时候，所以说尺取法是一种高效的枚举区间的方法，是一种技巧，一般用于求取有一定限制的区间个数或最短的区间等等。
左右
考点一　从内循环来看遍历的方向和位置
外循环往往控制查找的次数或位置，内循环往往控制每趟查找的开始和结束位置。在审题时，一定要关注内循环的初值和终值，列出第1次比较的对象和最后一次比较的对象。这类问题可能沿用专题15字符串处理线索的思想。把顺序查找数组中每个元素为第1线索，与他前面的或他后面的所有元素进行比较为第2线索，满足某种条件称为第3线索。
(一)从当前位置向后遍历
数组a(i＋1)位于a(i)的后面第1个位置，在遍历算法中往往是当前位置与他后面第1个位置比较，再依次比较到最后位置。由于过程中往往要涉及到2个或2个以上数组，往往用横向列表法来找出各个数组元素的值。
【例1】 有如下VB程序段：
For i＝1 To 4
a(i)＝Int(Rnd * 9 ＋ 1)
b(i)＝1
Next i
For i＝1 To 3
For j＝i ＋ 1 To 4
If a(i) < a(j) Then
　　　　b(i)＝b(i) ＋ 1
Else
　　　　b(j)＝b(j) ＋ 1
End If
Next j
Next i
执行该程序段后，数组b各元素的值依次是1，4，2，3，则数组a各元素的值不可能是(　　)
A.4 1 3 2 B.6 4 5 1 C.6 4 5 5 D.9 1 8 3
解析　产生1～9范围的4个整数存放到数组元素a(1)～a(4)中，数组b初值均为1。第1线索是顺序遍历每个元素，第2线索是a(i)与数组元素a(j)进行比较，第3线索是若a(i) < a(j)，则b数组中第i个元素，即b(i)加1；a(i)>＝a(j)，则b数组中第j个元素，即b(j)加1；A选项a(1)与他后面的元素比较，b(2)、b(3)、b(4)均加1。a(2)与后面元素比较，b(2)加2，a(3)与a(4)比较，b(4)加1，因此b数组值依次为1，4，2，3。可见程序实现的功能是b数组中保存的是a数组各元素从大到小的降序名次。C选项中，当a(3)等于a(4)时，对b(4)加1。B选项中，各数字的位次为1，3，2，4。
B
【变式1】 有如下VB程序段：
m＝Int(Rnd * 4) * 2 ＋ 1
For i＝1 To m － 1
k＝i
For j＝i ＋ 1 To m
If a(j) < a(k) Then k＝j
Next j
If i <>k Then
t＝a(i): a(i)＝a(k): a(k)＝t
End If
Next i
D
数组a(1)至a(8)的值分别为8，7，1，6，9，5，4，7，执行该程序段后，数组a各元素的值不可能是(　　)
A.8 7 1 6 9 5 4 7 B.1 7 8 6 9 5 4 7
C.1 4 5 6 7 8 9 7 D.1 4 5 6 7 7 8 9
解析　本题考查双重循环的算法。产生[1，7]范围的奇数m，再关注内循环的开始位置和结束位置，第1线索是顺序遍历i个数组元素，并定位为k，第2线索是与他后面到m位置数据a(j)进行比较，注意比较的范围不是到最后一个元素，第3线索是a(k)与a(j)比较，更新k的值，可知程序实现对数组a前m个数据升序选择排序。当m的值为1时，外循环0次，不排序，结果如A选项所示。当m的值为3时，外循环2次，内循环最后一次比较的位置是a(3)，因此实现前3个数据有序，排序结果如B选项所示。同理当m等于5和7时，实现前5个和前7个数有序，选项C为前7项有序。D选项实现了8个数据有序，因此m的值必须为8。
(二)从当前位置向前遍历
区间[1，i－1]指位于位置i前面的所有元素，在插入排序和冒泡排序中经常用到这种遍历方法。要找出遍历的方向和比较对象，用自然语言来描述算法，从而达到理解算法思想的目的。
【例2】 下列VB程序段功能为：在文本框Text1输入一个字符串，去除重复字符后在标签Label1上显示，如Text1中输入“abcdaed”，则Label1上显示“bcaed”。实现的程序代码如下：
s＝Text1.Text
i＝2
Do While i <＝ Len(s)
j＝1
Do While j <＝ i － 1
上述程序段中方框处可选语句为：①i＝i＋1　②i＝i－1　③j＝j＋1，则(1)(2)(3)处语句依次可为(　　)
A.①②③ B.②③① C.③②① D.②①③
解析　语句s＝Mid(s，1，j－1)＋Mid(s，j＋1，Len(s)－j)的功能是把j－1前面的字符和j＋1后面的字符连接起来，赋值给s，即删除s字符串第j位置上的字符。内循环的功能是在字符串第1到第i－1位置字符中顺序查找第i位置字符，若找到，则表示有重复，找到的位置为j，需删除第j位置的字符。若不重复，则继续往后比较，故(2)处代码为“j＝j＋1”。若第i位置字符处理完毕，需处理下一个字符，故(3)处代码为“i＝i＋1”。若删除了位置j的字符，字符串s的长度减少了1个，变量i指向重复后面的字符，再执行i＝i＋1语句后，变量i指向重复后面第2个字符，因此i需回退一个位置，再加1后继续处理，故(1)处代码为“i＝i－1”。如示例中，当i＝5时，删除第1个字符，字符s的值为“bcdaed”，i指向e，再加1后，直接处理d，没有对e是否重复进行判断。
B
C
【变式2】 有如下VB程序段：
n＝6: Max＝0: pos＝1
For i＝2 To n
For j＝1 To i － 1
If a(j)>a(i) Then b(j)＝b(j) ＋ 1
Next j
Next i
For i＝1 To n
If b(i)>＝ Max Then Max＝b(i): pos＝i
Next i
Text1.Text＝Str(Max) & ” ” & Str(pos)
数组a(1)至a(6)的值分别为21，21，12，29，12，21，数组b各元素初值均为0，执行完以上程序后，文本框Text1中显示的内容为(　　)
A.3 1 B.4 2 C.2 4 D.1 3
解析　第1线索为从第2个元素开始遍历a数组，第2线索为与a(i)前的数组元素a(j)比较，第3线索为若a(j)大于a(i)，对应的b数组元素加1。当i＝2和4时，他前面的字符均比a(i)大，因此b(i)没有增加。当i＝3时，b(1)和b(2)分别加1，当i＝5时，b(1)、b(2)和b(4)分别加1，当i＝5时，b(4)加1，因此有3个相同最大的b数组值为2，下标分别为1、2、4，条件b(i)>＝ Max表示当有多个最大值，找到最后一个位置的最大值，pos表示最大值的下标。
考点二　通过循环结构，不断地更新起始位置和结束位置
确定一个起点后，通过循环结构，不断地往后查找，记录结束位置，同时更新另一段(区间)的起始位置和结束位置。
【例3】 查找“长度递增单词”的程序，其实现的功能为：在文本框Text1中输入一段英文(以空格为分隔符，“.”为结束符)，单击“分析”按钮Command1，在标签Lab1中输出该段英文中单词长度呈递增变化的所有单词(如：输入A dream comes from your persistence.)程序运行界面，如图所示。
该程序段的主线索是英文字符串s中的每个字符，第2线索是单词，第3线索是长度呈递增变化。判断单词是否结束的条件是找到的字符不是字母。
程序段如下：
Private Sub Command1_Click()
Dim i As Integer，wd As Integer，wm As Integer
Dim n As Integer，s As String，rs As String
s＝Text1.Text
s＝s＋＂＂
n＝Len(s)：wd＝0: wm＝0
For i＝1 To n
c＝Mid(s，i，1)
If wd>wm Then
　　　　wm＝wd
　　　　rs＝rs＋＂＂＋____①____
End If
wd＝0
Else
____②____
End If
Next i
Lab1.Caption＝rs
End Sub
(1)若在文本框中输入“God helps those who helps themselves.”，单击“分析”按钮后，Lab中显示的是________________。
(2)加框处的条件语句还可以怎么表示________________。
(3)将程序代码中空白处填写完整。
答案　(1)God helps　themselves　(2)Not(c>＝＂a＂ And c <＝＂z＂ Or c>＝
＂A＂ And c <＝”Z”)　(3)①Mid(s，i－wd，wd)　②wd＝wd＋1
解析　第(1)题的单词的长度分别是3，5，5，3，5，10。根据题意，可以取出相应的单词。选择If wd>wm Then中，在找比前面长度长的单词，所以应该是单词结束后的操作，加框处应修改为单词结束的条件。可以得知wd是当前单词的长度，wm是前面最长单词的长度，因此当读取的是字母时，需增加单词的长度。当读取的字符不是字母时，需取出当前字母(结束是i－1，长度是wd)，设该字母的开始位置是x，计算长度的等式为i－1－x＋1＝wd，因此x＝i－wd。
【变式3】 上述例3程序的功能也可以用下列程序段实现：
j＝1
wd＝0: wm＝0: n＝Len(s)
For i＝1 To n
c＝Mid(s，i，1)
If Not (c>＝＂a＂ And c <＝＂z＂ Or c>＝＂A＂ And c <＝＂Z＂) Then
wd＝i－ j
If wd>wm Then
　　　　wm＝wd
　　　　rs＝rs＋＂＂＋____①____
End If
　　　　____②____
End If
Next i
将程序代码中空白处填写完整。
答案　①Mid(s，j，wd)或Mid(s，j，wm)或Mid(s，j，i－j)　②j＝i＋1
解析　变量j记录了每个单词的开始位置，当找到的不是字母时，单词结束，取出字母，此时i＋1将作为下一个单词的开始位置。
【变式4】 上述例3程序的功能也可以用双重遍历程序段实现，但要注意程序中边界控制问题。
wd＝0: wm＝0 ：n＝Len(s)
For i＝1 To n
c＝Mid(s，i，1)
If c>＝＂a＂ And c <＝＂z＂ Or c>＝＂A＂ And c <＝＂Z＂ Then
j＝i＋1
c1＝Mid(s，j，1)
Do While j <＝n And (c1>＝＂a＂ And c1 <＝＂z＂ Or c1>＝＂A＂ And c1 <＝＂Z＂)
　　　　j＝j＋1
　　　　c1＝Mid(s，j，1)
Loop
wd＝____①____
If wd>wm Then wm＝wd: rs＝rs＋＂＂＋____②____
　　____③____
End If
Next i
将程序代码中空白处填写完整。
答案　①i－j　②Mid(s，i，wd)或其他等价答案　③i＝j
解析　变量i为单词的开始位置，用j循环从i的下一位置开始，不断遍历，找到单词的结束位置，并要注意程序的边界，即不能超过字符的长度。下一个单词将从i＋1的位置开始，但Next i语句将i的值增加1，因此④i＝j，若用Do While，i可以等于j＋1。
【例4】 (2020·1月浙江选考)甲乙双方进行一场球类比赛，一局计分的规则是：赢1球得1分，用“1”表示：输一球失1分，用“0”表示。当任一方得分大于等于6分，且领先对方2分及以上，领先方赢一局。如甲选手一局比赛数据为“101110101”，表示甲选手得6分失3分，局比分6：3。小王用一个字符串记录了甲选手多局比赛数据，其中有一处错误，位于连续多个“0”的最后一个。为了找出错误，小王的处理方法如图a所示，对示例中的疑似错误位置6和20分别修改数据，并统计每局比分，单击“分析”按钮Command1，在列表框List1中输出修改位置以及修改后每局的比分。程序运行界面如图b所示。
(1)下列对象中Text属性的是________。(单选，填字母：A.Command1/B.Form1/
C.Text1)
(2)实现上述功能的VB程序如下，请在划线处填入合适的代码。
(3)程序中加框处代码有错，请改正。
Private Sub Command1_Click()
Dim sp As String，s As String　′s存储甲选手多局比赛的记录数据，长度小于50
Dim a(1 To 50) As Integer，e(1 To 20) As Integer
Dim i As Integer，j As Integer，k As Integer，n As Integer，m As Integer
Dim f1 As Integer，f2 As Integer
s＝Text1.Text
n＝Len(s)
For i＝1 To n
a(i)＝Val(____①____ )
Next i
m＝0: i＝1
Do While i <＝n　　　　′找出疑似错误位置
k＝i
Do While a(i)＝0 And i <＝n
i＝i＋1
Loop
If____②____ Then
m＝m＋1: e(m)＝i－1
End If
i＝i＋1
Loop
For i＝1 To m　′m对每个疑似错误位置分别修改数据，并统计每局比分
f1＝0: f2＝0
k＝e(i)
a(k)＝1
sp＝＂＂ & k & ＂＂
For j＝1 To n
If a(j)＝1 Then f1＝f1＋1 Else f2＝f2＋1
　　　　sp＝sp & ＂/＂ & f1 & ＂：＂ & f2
　　　　f1＝0: f2＝0
End If
Next j
If f1＋f2>0 Then sp＝sp & ＂/＂ & f1 & ＂：＂ & f2
List1.AddItem sp
____③____
Next i
End Sub
答案　(1)C　(2)①Mid(s，i，1)　②i－k>1　③a(k)＝0　(3)(f1>＝6 Or f2>＝6) And Abs(f1－f2)>＝2
解析　根据语句n＝Len(s)，联系下文得知数组a存储比赛数据，将字符串s中的每个字符存储到数组a中，所以答案为Mid(s，i，1)。整个程序可以分为三部分，其中第二部分和第三部分均为简单遍历，主线索均为字符串s中数字，第2线索分别是找到连续多个0和符合对局结束的条件。变量k记录起始位置，如果是连续的0，变量i一直递增，直到i指向非0位置。易知i－1即连续0末位位置，从语句e(m)＝i－1得知数组e记录连续0的末位位置。只有0的个数大于1个时，才需要记录。而k－i就连续0的个数。所以②答案为i－k>1。根据输出语句分析得知变量f1和f2分别存储甲乙双方的比分。当任一方得分大于等于6分，且领先对方2分及以上，领先方赢一局，此时一局结束，需要记录。And的优先级别比Or要高。所以此处改错答案为(f1>＝6 Or f2>＝6)And Abs(f1－f2)>＝2。根据题意每次只修正1处后输出结果，修正下一次时上一处要还原。语句a(k)＝1修正疑似错误位置后要还原，所以③空答案为a(k)＝0。
【变式5】 编写“字符串缩写”程序，实现如下功能：在文本框Text1中输入ASCII字符串，字符串中如果有由ASCII表中相邻字符(升序)组成的子串，则把该子串缩写成由第一个字符、“－”和最后一个字符组成，比如“abcdfpxcba”则缩写成“a－dfpxcba”。程序运行界面如下图所示，请将下列程序空白处填写完整。
Private Sub Command1_Click()
Dim s As String，result As String，i As Integer，j As Integer，t As Integer
s＝Text1.Text: t＝Len(s): result＝＂＂
i＝1
Do While i <＝t
j＝i
Do While____①____
If Asc(Mid(s，i＋1，1))＝Asc(Mid(s，i，1))＋1 Then
　　　　 i＝i＋1
Else
　　　　 Exit Do
End If
Loop
If____②____ Then
result＝result＋Mid(s，j，1)＋ ＂－＂＋Mid(s，i，1)
　Else
　　 result＝result＋Mid(s，i，1)
End If
i＝i＋1
Loop
Text2.Text＝result
End Sub
答案　①ij或其他等价答案
解析　 变量j记录了连续字母的开始位置，指针i继续往后找ASCII值大1的字符，但要注意边界问题，如果i比j大，说明有连续增长字符串。
【变式6】 上述变式5程序实现的功能也可以由下列程序段完成，请将划线处补充完整。
Private Sub Command2_Click()
Dim s As String，result As String，i As Integer，j As Integer，t As Integer
s＝Text1.Text
t＝Len(s): result＝＂＂
i＝1
Do While i <＝t
For j＝____①____
If Asc(Mid(s，j－1，1))＋1 <>Asc(Mid(s，j，1)) Then Exit For
Next j
If j>i＋1 Then
result＝result＋Mid(s，i，1)＋ ＂－＂＋Mid(s，____②____ ，1)
i＝____③____
Else
result＝result＋Mid(s，i，1)
i＝i＋1
End If
Loop
Text2.Text＝result
End Sub
答案　①i＋1 To t　②j－1　③j
解析　 用变量j从i的下一位置开始查找连续增长的字符，不满足条件时，退出循环，此时j的位置已经不符合要求，下一个连续增长的段将从j的位置开始。
考点三　尺取法
像尺子一样取一段，即选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。
【例5】 连续自然数之和。对一个给定的自然数M，求出所有的连续的自然数段，这些连续的自然数段中的全部数之和为M。程序运行效果如下图所示，在划线处将代码填写完整。
Private Sub Command1_Click()
Dim L As Integer，R As Integer
Dim n As Integer，sum As Integer
n＝Val(Text1.Text)
L＝1: sum＝0
For R＝1 To n\2
sum＝sum＋R
Do While sum>n
　　____①____
L＝L＋1
Loop
If____②____ Then List1.AddItem Str(L)＋””＋Str(R)
Next R
End Sub
答案　①sum＝sum－L　②sum＝n
解析　程序产生记录起始点L，向右查找右端点R。当内循环条件sum>n成立时，表示当前和已经超出连续自然数的和，而超出部分不可能在右边(如果在右边，上次循环加上R时，已经超出)，那么就要不断地减去左端点的值，缩进左端点。
【变式7】 在文本框Text1中输入一串英文字母，查找一段不重复的最长子串，同一字母的大小写按相同字符处理，如输入“abcabcdc”，则输出“abcd”。部分程序代码如下：
Dim wz(26) As Integer，i As Integer
Dim L As Integer，begin As Integer
s＝Text1.Text
L＝1: ans＝0
For i＝1 To Len(s)
ch＝Mid(s，i，1)
If ch>＝”a” And ch <＝”z” Then t＝Asc(ch)－96 Else t＝Asc(ch)－65
If______①____ Then
If i－L＋1>ans Then ans＝i－L＋1: begin＝L
Else
L＝____②____
End If
wz(t)＝i
Next i
Text2.Text＝Mid(s，____③____ ，ans)
则横线处代码应为(　　)
A.①wz(t)＝0　②wz(t)＋1　③begin B.①wz(t)C.①wz(t)＝0　②L＋1　③L D.①wz(t)B
解析　本题考查字符处理及双重循环结构。变量t代表字母ch在字母表中位置，当条件wz(t)＝0成立时，表示该字母未出现过，语句wz(t)＝i表示把该字母出现的位置存储在wz(i)中。当条件wz(t)1.有如下VB程序段：
Const n＝10
For i＝1　to n
flag(i)＝False
Next i
For i＝1 To n－1
For j＝i＋1 To n
　　　　If a(i)＋a(j)＝10 And Not flag(i) And Not flag(j) Then
　　　　　　cnt＝cnt＋1
flag(i)＝True : flag(j)＝True
　　　　　　Exit For
End If
Next j
Next i
数组元素a(1)至a(n)的值依次为：4，4，7，3，6，2，2，6，1，5，上述程序运行完后，cnt的值为(　　)
A.2 B.3 C.4 D.5
解析　该程序用来统计所给的数据中有多少对数据的和是10，且由Not flag(i) And Not flag(j)可以分析出，使用过的数不可再使用。
B
2.有如下VB程序段：
s＝Text1.Text
n＝Len(s): ans＝0：j＝3
Do While j>＝1
　t＝1
　For i＝2 To Len(s)－j＋1
If Mid(s，t，1)　Next i
ans＝ans*10＋Val(Mid(s，t，1))
s＝Mid(s，t＋1，n－t)
n＝Len(s)
j＝j－1
Loop
Text2.Text＝Str(ans)
程序运行时，在文本框Text1中输入7816629，文本框Text2中输出的内容是(　　)
A.23 B.247 C.789 D.869
解析　当j＝3时，在字符串s的[1，5]之间查找一个最大值8位置t，接着把t位及t位之前的字符去除。在j＝2时，在“16629”的[1，4]之间查找一个最大值6位置t，接着把t位及t位之前的字符去除。在j＝1时，在“629”的[1，3]找到最大值9。把找到的最大值依次*10并相加。
C
3.有如下VB程序段：
s＝”251894”
i＝1 ：n＝Len(s)
Do While i <＝n\2
j＝2
Do While Mid(s，1，1)>Mid(s，j，1) And j<＝n
j＝j＋1
Loop
j＝j－1
s＝Mid(s，1，j－1)＋Mid(s，j＋1，n－j)
n＝Len(s)
i＝i＋1
Loop
Text1.Text＝s
程序运行后，文本框Text1中显示的内容是(　　)
A.5894 B.894 C.1894 D.2194
解析　本题考查字符串处理。内循环j的初值为2，表示从第2个位置开始的字符，与第1个位置的字符进行比较，如果比第1个字符小，则继续往下比较，直到出现大于第1个字符为止。表达式Mid(s，1，j－1)是取出j前面的字符，Mid(s，j＋1，n－j)是取出j后面的字符，因此是将j位置的字符去除后重新连接。当i＝1时，去除2，s的值为”51894”，当i＝2时，去除1，s的值为”5894”，当i＝3时，Len(s)\2的值为2，不满足条件，退出循环。
A
4.有如下VB程序段：
sum(0)＝0：sum(1)＝a(1)
For i＝2 To n
sum(i)＝sum(i－1)＋a(i)
Next i
ans＝0
For i＝1 To n
For j＝i To n
tmp＝sum(j)－sum(i－1)
If tmp>ans Then ans＝tmp
Next j
Next i
Label1.Caption＝Str(ans)
若a(1)～a(6)的值依次为－2，11，－4，13，－5，2，则标签Label1显示的结果是(　　)
A.2 B.11 C.13 D.20
解析　类似2个或2个以上数组，通常用横向列表法进行变量值的跟踪。下标i－1是在i前面一个位置，语句sum(i)＝sum(i－1)＋a(i)表示当前sum数组元素值是他前面的数加上当前a数组的值。
D
下标i 1 2 3 4 5 6
数组a －2 11 －4 13 －5 2
数组sum －2 9 5 18 13 15
语句If tmp>ans Then ans＝tmp的功能是求最大的tmp值，当sum(i － 1)达到最小值，sum(j)达到最大值时，tmp达到最大值。因此当i＝2时，sum(1)＝－2，值最小，当j＝4时，可以找到sum数组的最大值，因此tmp的最大值为20。
5.下列VB程序段功能为：在文本框Text中显示整型数组元素a(1)到a(9)中的最小值和最大值。
amin＝a(1)：amax＝a(1)
i＝2: j＝9
Do While i <＝j
If a(i)>a(j) Then
End If
i＝i＋1: j＝j－1
Loop
Text1.Text＝Str(amin)＋”，”＋Str(amax)
上述程序段中方框处可选语句为：①If a(j)>amax Then amax＝a(j)　②If a(j)amax Then amax＝a(i)
则(1)(2)(3)(4)处语句依次可为(　　)
A.④③②① B.④②③① C.③②④① D.③①④②
解析　本题考查数组中求最值的算法。amin记录最小值，amax记录最大值。从数组两头依次往中间遍历，每次取出头尾的a(i)和a(j)，将较大值和amax比较，将较小值和amin比较。
B
6.在字符串s中找连续数字(仅限1位数)之和为n的子串，如字符串“142176”中，和为10的子串为“217”。假设所给字符串中必存在满足条件的子串实现该功能的VB程序段如下：
i＝1: sum＝0
For j＝1 To Len(s)
____ (1)____
sum＝sum＋Val(ch1)
Do While sum>n
ch2＝Mid(s，i，1)
　　____(2)____
i＝i＋1
Loop
If sum＝n Then List1.Additem____(3)____
Next j
上述程序段3个横线处的表达式分别为(　　)
A.(1)ch1＝Mid(s，i，1)　(2)sum＝sum－Val (ch2)　(3)Mid(s，i，j)
B.(1)ch2＝Mid(s，i，1)　(2)sum＝sum＋Val(ch2)　(3)Mid(s，i，j－ i)
C.(1)ch1＝Mid(s，j，1)　(2)sum＝sum－Val(ch2)　(3)Mid(s，i，j－i＋ 1)
D.(1)ch2＝Mid(s，j，1)　(2)sum＝sum＋Val(ch2)　(3)Mid(s，i，j －i＋ 1)
解析　当条件sum>n成立时，要进行操作，显然是减去i(i的初值为1)位置的数字，那么先进行累加，直到累加的和大于sum。(1)处应填写把j位置的数字进行累加，(2)处不断地减去前面的数字，若sum＝n条件成立，位置i表示和为sum的起始位置，j是终止位置，长度应为j－i＋1。
C
7.数组a中存储着n个范围为[1，50]的随机整数，现要在数组a中找到一个最长的区间，使得该区间里没有重复的元素，输出该区间的长度。实现该功能的VB程序段如下：
Dim flag(1 To 50) As Boolean　　′flag 数组每个元素的默认初始值为 False
L＝0: ans＝0: i＝1: j＝1
Do While j <＝n
If Not flag(a(j)) Then
flag(a(j))＝True
L＝L＋1
上述程序三个方框处的语句分别为(　　)
A.①j＝j＋1　②flag(a(i))　③L＝L－1
B.①j＝j＋1　②flag(a(j))　③L＝L－1
C.①i＝i－1　②flag(a(i))　③L＝L＋1
D.①i＝i－1　②flag(a(j))　③L＝L＋1
解析　变量L表示每段的长度。j表示每段的结束位置，当没有重复时，继续往后查找。i表示每段的开始位置，当j位置上数与前面重复时，表示该段已经结束，从i的位置开始查找与j位置上数相同的数，同时第二段的长度也在不断地缩小。当a(i)和a(j)相等时，将flag(a(i))的值置为False，再次进入循环时，flag(a(j))条件不成立。
B