2019浙江选考信息技术查找算法专题.doc

知识点 (一)顺序查找1顺序查找算法顺序查找算法的处理过程假定在数组d中有n个数据，查找关键值已经存储在变量key中。其处理过程是：从数组d的第1个元素d(1)开始，依次判断各元素的值是否与key相等，若某个数组元素d(i)的值等于key，则结束处理(找到了指定的数据)；若找遍了所有的n个元素，无任何元素的值等于key，则结束处理(输出未找到信息)。顺序查找算法流程图与程序结构2.程序实现代码：(二)对分查找1.对分查找的过程若key为查找键，数组d存放n个已按升序排序的数据。在使用对分查找时，把查找范围i，j的中间位置上的数据d(m)与查找关键值key进行比较，结果必然是如下三种情况之一：(1)若keyd(m)，由与(1)相同的理由，必须在新的范围(m1，j)中继续查找。这样，除了出现情况(2)，在通过一次比较后，新的查找范围将不超过上次查找范围的一半。以规模为16的递增数组d为例，观察对分查找的过程。要查找的数据key为37。使用流程图描述对分查找的算法如下图所示：2对分查找算法程序的实现Private Sub Command1_Click()i 1: j nDo While i j m (i j) 2 If d(m) Key Then输出结果，退出查找(代码略) ElseIf Key d(m) Thenj m 1 Elsei m 1 End IfLoopEnd Sub注意：中间位置数据d(m)的下标m的常见计算方法：m (ij)2、m int(ij)/2)、mfix(ij)/2)、mfix(ij)/2+0.5)上面对分查找的算法用一个块if语句实现，也可以用其他等价的方式：3查找次数的估算对规模为n的数组进行对分查找时，无论是否找到，至多进行 log2n1次查找就能得到结果，平均查找次数计算：（第1个数据需要的查找次数+第2个数据需要的查找次数+第n个数据需要的查找次数）/n而使用顺序查找算法，在最坏的情况下(查找键在最后一个或没找到)，需要进行n次查找，最好的情况是一次查找(查找键在第一个)，平均查找次数是。真题再现1、（2018.4）数组a为一组正整数，奇数在前，偶数在后。奇数与偶数已分别按升序排序。依据对分查找思想：设计一个在数组a中查找数据Key的程序。实现该功能的VB程序段如下：i = 1: j = 10Key = Val(Text1.Text)Do While i j Then s = 没有找到！ Else s = 位置： + Str(m)Text2.Text = s上述程序中方框处可选语句为：i = m + 1j = m - 1If Key a(m) Then j = m - 1 Else i = m + 1则（1）、（2）、（3）处语句依次是A、B、C、D、2、（2017.11）某对分査找算法的VB程序段如下:i = 1: j = 7: s = key = Int(Rnd * 100)Do While i = j m = (i + j) 2 If key = a(m) Then s = s + M: Exit Do Exit Do 表示退出循环 ElseIf key a(m) Then j = m - 1: s = s + L Else i = m + 1: s = s + R End IfLoopText1.Text = s数组元素a(1)到a（9）的值依次为“24，35，38，41，45，69，78”。若该程序段执行后，文本框Text1中显示的内容可能是A. RL B. LMRC. RLRD. LRLM3、（2017.4）某对分查找算法的VB程序段如下：key = Val(Text1.Text)i = 1: j = 10Text2.Text = Do While i = j m = Int(i + j) / 2 + 0.5) If key = a(m) Then Exit Do Exit Do表示退出循环 If key a(m) Then j = m - 1 Else i = m + 1 Text2.Text = Text2.Text + Str(a(m)Loop数组元素a(1)到a(10)的值依次为“8,17,24,30,36,40,55 ,58,61,66”，文本框Text1中输入的值是30，执行该程序段，文本框Text2中显示的是A40 24 B40 24 36 C36 24 D36 17 244、（2016.10）某对分查找算法的VB程序段如下：i = 1: j = 9：n=0key = Val(Text1.Text)Do While i = j N=n+1 m = fix(i + j) / 2) If key = d(m) Then Exit Do If key dm) Then j = m - 1 Else i = m + 1Loop数组元素d(1)到d(9)的值依次为“7,12,18,25,39,58,61,72,86”，若该程序段运行结束后，n的值为2，则key的值是 A.39 B. 18或61 C.18或72 D. 12或615、（2016.4）已知一无序数组a（下标1到n），通过引入数组b（下标1到n），使得a(b(1)a(b(2) a(b(3)a(b(n)（示例如图所示），对这些有序数据可进行对分查找。则第一次查找时，中点位置m与中点值分别是A. m的值是Fix(1+n)/2),中点值是 a(m)B. m的值是Fix(1+n)/2),中点值是 a(b(m)C. m的值是Fix(b(1)+b(n)/2),中点值是 a(m)D. m的值是Fix(b(1)+b(n)/2),中点值是 a(b(m)6、（2015.10）已知单调函数在0，1区间存在一个，使。现用对分查找法搜索的值，开始搜索区间为0，1，若经过10次对分查找后还需继续搜索，则第11次搜索区间的长度为A.1/2B. 1/10C. D. 7、（2017.4）小王编写了一个实现文字查找替换功能的VB程序，运行界面如图所示。文本框Text1显示原文内容，Text2中输入查找内容，Text3中输入替换内容，单击“全部替换”按钮Command1后，Text4显示查找替换的结果，Text5中显示替换的次数，Text6显示“查找内容”在原文中的起始位置。实现上述功能的VB程序如下，但加框处代码有错，请改正。Private Sub Command1_Click() Dim s As String, resule As String, pos As String Dim count As Integer, i As Integer i = 1: count = 0 resule = : pos = Do While i = Len(Text1.Text) s = Mid(Text1.Text, i, Len(Text2.Text) If s = Text2.Text Then result = result + Text3.Text count = count + 1 pos = pos + Str(count) i = i + Len(Text2.Text) Else result = result + Text2.Text i = i + 1 End If Loop Text4.Text = result Text5.Text = Str(count) Text6.Text = posEnd Sub巩固训练1、 按钮command1的鼠标事件处理过程如下： Private Sub Command1_Click()Dim st(1 To 6) As Stringst(1) = she:st(2) = her:st(3) = yourst(4) = me:t(5) = you:st(6) = iKey = text1.Textt = Falsei = 0Do While i 6 And t = False i = i + 1 If st(i) = Key Then t = TrueLoopIf t = flase Then i = 0text2.Text = Str(i)End Sub程序运行时，在文本框中输入“you”后单击按钮command1后，在文本框text2中显示的内容是（ ）A.0 B.1 C.5 D.72、某8位男生的肺活量数据放在数组a（1）到a（8）中，其数据依次为“3104,3700,3058,3222,3621,3329,4233,4540”。使用顺序查找算法查找数据3339，则共需查找次数为（ ）A.0 B.1 C.8 D.93、有以下两组数据：54,31,43,12,8,73,56,34,89,60,23,6787,83,75,70,63,59,55,37,33,21,17,7下列有关查找方法描述不正确的是（ ）A. 可以直接使用对分查找 B. 可以直接使用对分查找C. 可以直接使用顺序查找 D. 可以直接使用顺序查找4、某8位男生的肺活量数据放在数组a（1）到a（8）中，其数据依次为“3205,3408,3471,3498,3621,3829,4233,4540”。使用对分查找，设定查找键key，若第一个被访问到的数据是3498，小于key值，则第二个被访问到的数据是（ ）A.3408 B.3829 C.4233 D.45405、某对分查找算法的vb程序段如下：i = 1: j = 9: n = 0Key = Val(Text1.Text)Do While i = j n = n + 1 m = Fix(i + j) / 2) If Key = d(m) Then Exit Do If Key d(m) Then j = m - 1 Else i = m + 1Loop数组元素d(1)到d(9)的值依次为“7,12,18,25,39,58,61,72,86”。若该程序段运行结束后，n的值为2，则key的值是（ ）A.39 B.18或61 C.18或72 D.12或616、数组元素d(1)到d(10)的值依次为“60,51,49,45,40,31,20,10,5”，用对分查找找到49的过程中，依次被访问到的数据是（ ）A.49 B.40 49 C.40 45 49 D.40 51 497、下列有关查找的说法，正确的是( ）A进行顺序查找时，被查找的数据必须是有序的B在任何情况下，顺序查找比对分查找的查找次数要多C进行对分查找时，被查找的数据可以是有序的，也可以无序的D对规模为n的有序数据进行对分查找，最多查找的次数是log2n+18、某查找算法的部分 VB 程序代码如下： Key=Val(Text1.Text) i = 1: j = 9: k = 0 Do While i = j k = k + 1 m = int(i + j)/2+0.5) If key = a(m) Then Exit Do If key a(m) Then j = m - 1 Else i = m + 1 Loop Text2.Text=str(k) 数组元素 a(1)到 a(9)的数据依次为“10，15，36，49，55，62，88，92，99”，该程序运行过程中，文本框 Text2 中显示的值为 2，文本框 Text1 中输入值可能是（ ） A.88B.62C.92D.15 9、某对分查找算法的VB程序段如下：i=1: j=6: n=0: f=Falsekey=val(Text1.Text)Do while i=j and f=False n=n+1 m=(i+j)2 If key=d(m) then f=True If keyd(m) then j=m-1 Else i=m+1Loop数组元素d(1)到d(6)的值依次为“13，18，25，30，35，59”。文本框Text1中输入33后运行该程序，运行结束后下列说法不正确的是（ ）A. 变量f的值为FalseB. 变量i的值为5C. 变量m的值为4D. 变量n的值为210、有如下程序段：i = 1: j = 6: s = : key = Text1.TextDo While i Key Then i = m + 1 Else j = m - 1 End IfLoopText1.Text = s数组元素a（1）到a（6）的值依次为Beijing、Guangdong、Jiangsu、Jiangxi、Shanghai、Zhejiang，已按字典序排序。当key的值为Zhejiang时，单击命令按钮Command1，文本框Text1中显示的内容为（ ）A. Jiangxi Zhejiang Zhejiang B. Jiangsu Shanghai Jiangxi C. Jiangxi Zhejiang Shanghai D. Jiangsu Shanghai Zhejiang11、某对分查找算法的VB程序段如下：key = Val(Text1.Text)i = 1: j = 10Text2.Text = Do While i = j m = Int(i + j) / 2 + 0.5) If key = a(m) Then Exit Do Exit Do表示退出循环 If key = a And ch = z Then If Not flag Thenm = m + 1 ： flag = TrueEnd IfElseflag = FalseEnd IfNext iText1.Text=Str(m)A4 B5 C6 D1913、编写一个技术成绩查询的 VB 程序。程序功能如下：在文本框 Text1 中输入分数 key(0-50 的整数)，单击“查询”按钮 Command1，查询出信息成绩大于等于 key 的所有记录，并以“信息”为主要关键字、“通用”为次要关键字均进行降序排序，结果输出在列表框 List2 中。运行界面如下图所示。实现上述功能的 VB 程序如下，请回答下列问题：（1）观察上图，排序后第 5 位的学生姓名是_。（2）请在划线处填入合适的代码。Dim xm(1 To 600) As String 存储学生姓名Dim xx(1 To 600) As Integer 存储信息成绩Dim ty(1 To 600) As Integer 存储通用成绩Dim n As Integer 存储记录总数Private Sub Form_Load()本过程从数据库中读取学生数据，存储在相应的变量中，并在 List1 中显示,代码略End subPrivate Sub Command1_Click()Dim key As Integer, mid As IntegerDim i As Integer, L As Integer, R As Integer, k As Integer Dim tmp1 As String, tmp2 As Integer 以“信息”为主要关键字、“通用”为次要关键字排序For i = 1 To n - 1 k = iFor j = i + 1 To nIf xx(k) xx(j) or _ Then k = jEnd If Next jIf k i Thentmp1 = xm(k) : xm(k) = xm(i) : xm(i) = tmp1tmp2 = xx(k) : xx(k) = xx(i) : xx(i) = tmp2tmp2 = ty(k) : ty(k) = ty(i) : ty(i) = tmp2 End IfNext i 查询记录key = Val(Text1Text) L = 1 : R = nDo While L = Rmid = (L + R) 2If _ Then L = mid + 1ElseR = mid - 1 End IfLoop List2Clear vbTab 相当于是键盘上制表符 TAB 按键的功能List2AddItem 姓名 & vbTab & 信息 & vbTab & 通用 For i = 1 to _List2AddItem xm(i) & vbTab & xx(i) & vbTab & ty(i) Next iEnd sub14、要求从某一个字符串中删除指定的字符（假设所含的英文字母均为小写字母），并将处理后的字符串重新输出。程序界面如图所示，在文本框text_1中输入原始字符串，在文本框text_2中输入需要删除的字符，单击“删除此字符”按钮（command1）后，在文本框text_3中输出处理后的结果，相应的vb程序如下： Private Sub Command3_Click()Dim p As String, k As StringDim i As Integer, result As Stringresult = p = text_1.Textk = text_2.TextFor i = 1 To Len(p) If Mid(p, i, 1) k Then result = result + _ End IfNext i_End Sub（1） 解决此问题的算法是_（选填：顺序查找 或 对分查找）（2） 在程序处，填入适当的语句或表达式，把程序补充完整。在程序出填入：_ 在程序出填入：_ 15、小王设计了学校食堂学生IC卡查询系统，输入学生的卡号，可以查出该卡号对应的余额。所有学生的IC卡号和相应的余额已分别保存在数组stu（按从小到大排序）和数组money中，第i个学生的卡号保存在stu（i）中，对应的卡号余额保存在money（i）中。程序界面如图所示，左边列表框List1中显示的是部分学生的卡号和余额，在文本框Text1中输入学生的IC卡号，单击“查询余额”按钮（Command1）后，如果找到此卡号，则在标签Lab3中显示“此卡号余额为”和卡号对应的余额值，如果未找到则显示“找不到此卡号”，请重新输入。 解决此问题的部分程序段如下：Const n = 1500Dim stu(1 To n) As LongDim money(1 To n) As SinglePrivate Sub Form_Load() 此过程用于对数组stu和数组money进行初始赋值，代码略End SubPrivate Sub Command1_Click()Dim x As Long, i As Long, j As Long, m As Long, find As Booleanx = Val(Text1.Text)_j = nfind = FalseDo While i = j And Not find _ If x = stu(m) Then _ ElseIf x stu(m) Then j = m - 1 Else i = m + 1 End IfLoopIf find Then Lab3.Caption = 此卡号余额为 + Str(money(m) + 元Else Lab3.Caption = 找不到此卡号，请重新输入End IfEnd Sub（1） 解决此问题的算法是_（选题：对分查找或顺序查找）（2） 在程序划线出填入适当的语句或表达式，将程序补充完整：_ _ _ 16、对于无序数组 a（下标 1 到 n），通过引入数组 b（下标 1 到 n），使得 a(b(1)a(b(2) a(b(3)a(b(n)。小王编写了一个 VB 程序,功能如下:在列表框 List1 中显 示 i、a(i)、b(i)、a(b(i)，在文本框 Text1 输入要查找的数据，单击“查找”按钮 Command1 后，在标签 Label3 中显示该数据在 a 数组中的位置。程序运行界面如图所示实现上述功能的 VB 程序如下，但加框处代码有错，请改正。Dim a(1 to 8) As Integer,b(1 to 8) As IntegerDim n As IntegerPrivate Sub Form_Load()n=8，对分查找前的 8 个数据存储在 a 数组中，每个数据的位次存储在 b 数组中在列表框 List1 中显示数组下标、a 数组、b 数组、a(b(i)数组代码略 End SubPrivate Sub Command1_Click()Dim i As Integer, j As Integer, k As Integer Dim m As Integer, key As Integerkey = Val(Text1.Text) i = 1:j = nDo While i k Then i = m + 1Elsej = m - 1 End IfLoopIf i j Then Label3.Caption=该数据不存在ElseStr(m)Label3.Caption =str(m) End IfEnd Sub【巩固训练-变式题】1、对数组 a 中 6 个有序数据“11，22，33，44，55，66”，用下面的程序代码查找数据“23”，程序执行完毕后，下列各变量值正确的是( )Dim a(1 To 6) As IntegerDim i As Integer,j As Integer , Key As Integer,m As Integer a(1) = 11: a(2) = 22: a(3) = 33: a(4) = 44: a(5) = 55: a(6) = 66i = 1: j = 6: p = 0: Key = 23Do While i = j p = p + 1m = (i + j) 2If j Mod 2 = 0 Then m = m + 1 If a(m) = Key Then Exit DoIf Key a(m) Then j = m - 1 Else i = m + 1 LoopAi=5Bj=4Cm=3Dp=22、有以下 VB 程序段( )a(1) = 6: a(2) = 8: a(3) = 7: a(4) = 3a(5) = 1: a(6) = 2: a(7) = 5: a(8) = 4i = 1: j = 8key = a(1)Do While ijDo While i = keyj = j - 1Loopa(i) = a(j)Do While i j And a(i) = keyi = i + 1Loopa(j)=a(i)Loopa(i) = keyFor i = 1 To 8Label1.Caption = Label1.Caption + + Str(a(i)Next i执行该程序段，标签 Label1 上显示的内容是A1 2 3 4 5 6 7 8B8765 4 3 2 1C4 5 2 3 1 6 7 8D4513 2 6 7 83、某对分查找算法的VB程序段如下：i = 1j = 7s = Do While i Key Thenj = m 1s = LElsei = m + 1s = R End IfLoop数组元素a(1)到a(7)的值依次为“25,42,53,66,77,83,98”，若key=60，运行上述程序段后，下列条件表达式成立的是( )A. s = E B. s = R C. s = L D. s = LRR4、某对分查找算法的vb程序段如下：i = 1: j = 7：s=key = int(Rnd*100)Do While i = j m = (i + j) 2 If key = a(m) Then s=s+M : Exit Do Exit Do表示退出循环 ElseIf key a(m) Then j = m - 1: s=s + L Else i = m + 1: s=s + R End If LoopText1.Text = s数组元素a(1)到a(7)的值依次为“24，35，38，41，45，69，78”。若该程序段执行后，文本框Text1中显示的内容可能是（ ）A.RL B.LMR C.RLR D.LRLM5、已知数组元素 a(1)到 a(9)的值为19,28,37,46,55,64,73,82,91,若在 Text1 中输入 29，然后执行下面程序段：Key = Val(Text1.Text) 10Text2.Text = i = 1: j = 9: f = FalseDo While i Key Theni = m + 1Elsej = m 1End IfText2.Text = Text2.Text + Str(m)Loop执行完该程序段后，Text2 中显示的内容是()A52B 553728C557382 D 5786、数组a为一组正整数，奇数在前，偶数在后。奇数与偶数已分别按升序排序。依据对分查找思想：设计一个在数组a中查找数据Key的程序。实现该功能的VB程序段如下：i = 1: j = 10Key = Val(Text1.Text)Do While i j Then s = 没有找到！ Else s = 位置： + Str(m)Text2.Text = s上述程序中方框处可选语句为：i = m + 1j = m - 1If Key a(m) Then j = m - 1 Else i = m + 1则（1）、（2）、（3）处语句依次是A、B、C、D、7、有一种查找算法，VB程序设计如下：cs = 0: i = 14: t = i: dx = 0Do While t find Thent = t 1If dx = t Then Exit Do Elsedx = t: i = i 1If t + i 100 Then t = t + 1 Else t = t + i End If End IfLoop 已知数组a有序递增，有100个元素a（1）到a（100），变量find的数值是从外部输入，则程序运行后，变量cs的值最大可以是A 7 B 13 C 14 D 508、小明设计了如下一个查找数据的程序：在一组升序的数列当中，查找不小于k 的最小数的位置，如果该值存在，则返回其第一次出现的位置，如果不存在则返回0。程序界面如下：（1） 若在Text1中输入“8”，Text2、Text3输出的分别为 。（2） 请在划线处填入适合代码。Dim a(1 To 10) As IntegerFunction find(L As Integer, R As Integer, key As Integer)As IntegerIf L R Thenfind = 0: Exit FunctionElseIf a(L) = key Thenfind = L: Exit FunctionElse If a(m) Low If Then 当只余下两个元素时 If Then Label1.Caption = 拐点元素为 + Str(a(1) + ,下标为 + Str(1) Else Label1.Caption = 拐点元素为 + Str(a(High) + ,下标为 + Str(High) End If Exit Do End Ifm = (Low + High) 2 If a(m) = a(Low) Then Low = m Else End If LoopEnd SubPrivate Sub Form_Load() 生成循环递增的数组a，代码略End Sub10、一个整数数组，里面有正有负，要求找到并输出其中连加和最大的子数组，输出其开始位置和结束位置。如果两个子数组的和相同，则取前一个子数组。如 2、-6、0、3、-1、2、5、-4、4、-3,连加和最大的子数组为 3、-1、2、5。算法：如果前几项之和为正，继续往后累加，否则从该项开始重新计算和。小李编写了一个实现该功能的 VB 程序，运行界面如图所示。单击“随机生成”按钮 Command1 后， 随机产生 10 个-10,10随机整数，并在列表框 List1 中显示。单击“找子数组”按钮 Command2 后，找出连加和最大的子数组，将最大和在标签 Label1 中输出，将子数组在标签 Label2 中输出，子数 组的起始位置和结束位置在标签 Label3 中输出。实现上述功能的 VB 程序如下，但加框处代码有误，请改正。 Dim a(1 To 10) As IntegerPrivate Sub Command1_Click()生成 10 个随机数，并显示在列表框 List1 中。代码略。 End SubPrivate Sub Command2_Click()Dim maxsum As Integer, lastsum As Integer, ks As Integer, js As Integer, k As Integer Dim s As String, i As Integerks = 1: js = 1: k = 1: maxsum = a(1): lastsum = a(1)For i = 2 To 10If lastsum 0 Thenlastsum = maxsum + a(i) （1） Elselastsum = a(i)ks = i （2） End IfIf lastsum maxsum Thenmaxsum = lastsumks = kjs = iEnd If Next iLabel1.Caption = 连加值最大的和为 + Str(maxsum)For i = ks To jss = s + Str(a(i)If i js Then s = s + 、 Next i11、“轮转后有序数组（Rotated Sorted Array）”是将有序数组取其中某一个数为 分割点，将其之前的所有数都轮转到数组的末尾所得。比如 7, 11, 13, 17, 2, 3, 5 就是一个轮转 后的有序数组，原有序数组中的子串 2，3，5 被轮转到了数组的末尾处。对于一个轮转后有序数组 arr 也可以进行二分查找，算法思路如下（以升序为例）： 每次根据查找的左侧位置 L 和右侧位置 R 求出中间位置 M 后，M 左边L, M和右边M+1, R这两部分中至少一个是有序的（可根据中间位置数据和边界数据的大小关系判断）。arrM和待查找数据 Key 比较(1). arrM=Key，返回 M 的值(2).若 M 位置的右侧有序，当待查找数据在右侧，则下次在右侧查找,否则在 M 左侧查找(3).若 M 位置的左侧有序，当待查找数据在左侧，则下次在左侧查找,否则在 M 右侧查找（1）对于轮转后有序数组 7, 11, 13, 17, 2, 3, 5 使用以上函数 search( )查找 key 值 3，所需 要的查找次数为。（2）以下 VB 函数 Search( )实现了对轮转后有序数组 arr 进行二分查找的过程，如果查询成 功，返回 m 值，查询失败则返回-1。请补充程序中划线处的代码：Function Search(key As Integer, L As Integer, R As Integer) As Integer 填写合适的代码Do While L = R And Search =-1 M = (L + R) 2If arr(M) = key Then Search = MElseIfThen填写合适的代码If arr(L)= key And key arr(M)Then R = M - 1ElseL = M + 1End If ElseIfThen填写合适的代码L = M + 1ElseR = M - 1End If End IfEnd IfLoopEnd Function12、小王编写一个 VB 程序模拟数据筛选，功能如下：程序运行时从数据库中读取 成绩数据，按升序排序后在列表框 List1 中显示，在文本框 Text1 中输入成绩 1,在文本框Text2 中输入成绩 2，单击“筛选”按钮 Command1，筛选出大于等于成绩 1 且小于等于成绩2 的记录，并显示在列表框 List2 中，程序运行