资源简介 第4节 查找算法考试内容 考试要求顺序查找算法思想及程序实现 c对分查找算法思想及其变形的程序实现 c一、顺序查找算法思想和程序实现顺序查找的基本思想是从第一个数据开始,按顺序逐个将数据与给定的数据(查找键)进行比较,若某个数据和查找键相等,则查找成功,输出所查数据的位置;反之,输出未找到。For i = 1 To n If a(i)=key Then Exit For End If Next i 代码分析:将数组中的每个元素逐个与key进行比较,如果相等则查找成功,循环结束。如果循环结束后,变量i的值等于n+1,则意味着没有找到。顺序查找数组可以无序二、对分查找算法思想对分查找又称二分查找,是一种高效的查找方法。对分查找的前提是被查找的数据是有序的(升序或降序)。对分查找的基本思想是在有序的数列中,首先将要查找的数据与有序数列内处于中间位置的数据进行比较,如果两者相等,则查找成功;否则就根据数据的有序性,再确定该数据的范围应该在数列的前半部分还是后半部分;在新确定的缩小范围内,继续按上述方法进行查找,直到找到要查找的数据,即查找成功,如果要查找的数据不存在,即查找不成功。若key为查找关键字,数组d存放n个已按升序排序的数据。使用对分查找时,把查找范围[i,j]的中间位置上的数据d(m)与key进行比较,结果必然是如下三种情况之一:(1)若key(2)key=d(m),找到了需要的数据;(3)key>d(m),查找键大于中点d(m)处的数据。由数组d中的数据的递减性,可以确定:在(i, m)内不可能存在值为key的数据,必须在新的范围(m+1,j)中继续查找。这样,除了出现情况(2),在通过一次比较后,新的查找范围将不超过上次查找范围的一半。数组d为例,观察对分查找的过程。要查找的数据key=52,查找过程如下:三、对分查找算法代码实现i = 1: j = n: s = 0 Do While i <= j m = (i + j) \ 2 If a(m) = key Then s = m: Exit Do ElseIf key < a(m) Then j = m - 1 Else i = m + 1 End If Loop 左边程序实现在升序数组a(1)…a(n)中查找值等于key的元素,将其下标存储在s中。如果没有找到则s值为0,如果找到,则s存储对应元素的下标。 对分查找前提是数据有序,对n个数据查找,最多查找次数为Log2n+1(向下取整)。 例如在有序数组a(1)…a(10000)中查找某个值,最多需要查找Log210000+1,即14次一、顺序查找算法思想和代码实现【典例1】 小王拿着一大串钥匙去开仓库的某一扇门,由于钥匙上没有任何标记,小王只能将这一串钥匙一把一把地去试,从算法角度看,小王的做法属于( )A.冒泡排序 B.选择排序C.对分查找 D.顺序查找解析 本题考查两个算法的区别。顺序查找的思想第从第一个数据开始,按数据的顺序逐个将数据与给定的值进行比较,若某个数据与给定的值相等,则查找成功,否则查找不成功。答案 D【变式训练】 用对分查找法和顺序查找法在数字序列“1,2,3,5,8,13,21,34,55”中查找数字13,两种方法都能访问到的数字是( )A.3 B.5 C.8 D.34解析 对分查找访问到的数字为8、21、13,顺序查找访问到的数字为1,2,3,5,8,13。两者共同为8。答案 C二、对分查找算法思想【典例2】 已知单调函数f(x)在[0,1]区间存在一个x0,使f(x0)=0。现用对分查找法搜索x0的值,开始搜索区间为[0,1],若经过10次对分查找后还需继续搜索,则第11次搜索区间的长度为( )A.1/2 B.1/10 C.1/102 D.1/210解析 对分查找的每次区间变为上次的二分之一。第2次为原搜索区间的长度1/2,第3次为原搜索区间的长度1/4……第11次为原搜索区间的长度1/210,所以答案D。答案 D【变式训练】 下列有关查找的说法,正确的是( )A.进行对分查找时,被查找的数据必须已按升序排列B.进行对分查找时,如果查找的数据不存在,则无需输出结果C.在新华字典中查找某个汉字,最适合使用顺序查找D.对规模为n的数据进行顺序查找,平均查找次数是解析 对分查找的前提是被查找的数据是有序的(升序或降序)。如果找不到,程序应该要输出未找到的相关提示信息。在新华字典中查找某个汉字,不适合使用顺序查找,适合使用对分查找。对规模为n的数据进行顺序查找,最少查找1次,最多查找n次,平均查找次数是。答案 D【典例3】 数组变量d(1)到d(8)的值依次为97、86、79、68、56、41、33、13,用“对分查找”找到“13”的过程中,依次被访问到的数据是( )A.68、13 B.68、41、13C.56、41、33、13 D.68、41、33、13解析 本题考查标准的对分查找,查找中间项为m=(i+j)\2,经过4次对分查找。i 1 5 7 8j 8 8 8 8m 4 6 7 8d(m) 68 41 33 13答案 D【变式训练】 在有序单词序列“bike,cake,data,easy,feel,great,hive,mark,sweet”中,用对分查找算法找到“easy”过程中,依次被访问到的数据为( )A.feel, data, easy B.great, data, easyC.bike, cake, dada,easy D.feel,cake,data,easy解析 本题考查标准的对分查找,查找中间项为m=(i+j)\2,经过4次对分查找。i 1 1 3 4j 9 4 4 4m 5 2 3 4d(m) feel cake data easy答案 D三、对分查找算法代码实现【典例4】 某对分査找算法的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 ′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或61C.18或72 D.12或61解析 n代表查找次数,代入选项计算查找次数为2,即为答案。key=12,第1次:m=5,i=1,j=4;第2次:m=2 ,d(m)=12查找成功。key=61,第1次:m=5,i=6,j=9;第2次:m=7 ,d(m)=61查找成功。所以答案选D。答案 D【变式训练】 采用如下对分查找算法对数组a中7个有序数据“15,38,51,66,77,81,99”进行查找,查找数据为“55”,i = 1: j = 7: x = 55Do While i <= jm = (i + j) \ 2If a(m) = x Then Exit DoIf a(m) > x Then j = m - 1 Else i = m + 1Loop执行完上述代码后,根据最终变量值判断下列表达式,其中正确的是( )A.i=m+1 B.i=m-1C.j>m+1 D.j解析 本题考查标准的对分查找,查找中间项为m=(i+j)\2,最终没有找到该数据。算法结束时i=4,j=3,m=3,所以答案选A。i 1 1 3 4j 7 3 3 3m 4 2 3 d(m) 66 38 51 答案 A【典例5】 有如下VB程序段:i = 1 : j = 10 : flag = True : n = 0 Key = Val(Text1.Text)Do While i <= j And flag = Truem = (i + j) \ 2If a(m) = Key Thenflag = FalseElseIf a(m) > Key Theni = m + 1 : n = n - 1Elsej = m - 1 : n = n + 1End IfLoop数组元素a(1)到a(10)依次是99, 94, 90, 87, 70,69,60,56,45,36,变量n的值最终是0,则文本框Text1输入的数字可能是( )A.100 B.87 C.69 D.41解析 本题考查的是对分查找的变形。当key=100时,程序执行过程中,各个变量的值变化情况如下表所示:i 1 1 1 1j 10 4 1 0m 5 2 1 d(m) 70 94 99 n 1 2 3 当key=87时,程序执行过程中,各个变量的值变化情况如下表所示:i 1 1 3 4j 10 4 4 4m 5 2 3 4d(m) 70 94 90 87n 1 0 -1 当key=69时,程序执行过程中,各个变量的值变化情况如下表所示:i 1 6 6j 10 10 7m 5 8 6d(m) 70 56 69n -1 0 当key=41时,程序执行过程中,各个变量的值变化情况如表所示。i 1 6 9 10 10j 10 10 10 10 9m 5 8 9 10 d(m) 70 56 45 36 n -1 -2 -3 -2 答案 C【变式训练】 有如下VB程序段:i = 1: j = 9: f = FalseDo While i <= j And Not fm = Fix((i + j) / 2)If a(m) = Key Thenp = m : f = TrueEnd IfIf a(m) > Key Thenj = m - 1Elsei = m + 1End IfLoopIf f = True Then Text1.Text=“数据位置:” + Str(p)Else Text1.Text=“没有找到该数据!”End If 数组元素a(1)到a(9)的值依次为10,15,30,32,38,42,45,48,68,若通过如下程序段查找数据key=43,则在执行该程序段的过程中,依次访问的数据是( )A.38,45,42 B. 38,45,48C.38,48,42 D. 38,48,45解析 本题考查的是对分查找的变形。在程序执行过程中,各个变量的值变化情况如下表所示,所以答案选A。i 1 6 6j 9 9 6m 5 7 6d(m) 38 45 42答案 A【典例6】 小明为了研究对分查找的过程中数据被访问的情况,编写了一个VB程序,功能如下:在列表框List1中显示已经排序的数据(存储在数组a中),在文本框Text1中输入要查找的数据,单击“查找”按钮Command1后,在标签Label1中显示查找中依次被访问到的数据。程序运行界面如图所示。实现上述功能的VB程序如下,但加框处代码有错,请改正。Const n = 10Dim a(1 To n) As IntegerDim s As StringPrivate Sub Form_Load()′产生随机数依次存储在数组a中,代码略′对数组a升序排序并在列表框输出,代码略End SubPrivate Sub Command1_Click() Dim x As Integer, p As Integer x = Val(Text1.Text) s = “ ” ′(1) If p > 0 Then s = s + “查找成功” Else s = s + “查找失败” Label1.Caption = “依次被访问的数据为:” + sEnd SubFunction search(key As Integer) As Integer Dim i As Integer, j As Integer, flag As Boolean flag = False i = 1: j = n: search = 0 Do While i <= j And Not flagm = (i + j) \ 2If a(m) = key Then search = m flag = True ′(2) j = m - 1Else i = m + 1End Ifs = s + Str(a(m)) + “→” LoopEnd Function程序中加框(1)处应改正为_________________________________________;加框(2)处应改正为________________________________________________。解析 (1)联系下文代码If p > 0 Then,需要对变量p赋值,结合函数search的功能:如果在数组a中找到要查找的数,函数search 返回该数在数组中的位置,如果没有找到,函数search 返回值为0,结合程序得知第1空为:p=search(x)。(2)在一个块If语句中结合对分查找算法得出第2空为: ElseIf Key < a(m) Then。答案 (1)p=search(x) (2)ElseIf Key < a(m) Then1.某数组有10个元素,依次为:5,12,16,23,27,30,35,41,49,50。下列说法正确的是( )A.使用对分查找数据12,需要的查找次是3次B.使用顺序查找数据50,需要的查找次数是9次C.使用对分查找数据41,需要的查找次数是2次D.使用顺序查找数据5,需要的查找次数是0次解析 本题考查标准的对分查找,查找中间项为m=(i+j)\2,查找12的过程如下表所示。故查找12需要2次。i 1 1j 10 4m 5 2d(m) 27 12顺序查找数据50,需要的查找次数是10次,查找41的过程如下表所示,故查找41需要4次。i 1 6j 10 10m 5 8d(m) 27 41顺序查找5需要1次。答案 C2.某对分查找算法的VB程序段如下:i=1:j=7:n=0:f=FalseKey=Val(Text1.Text)Do While i<=j And f=Falsen=n+1m = Fix((i + j) / 2)If Key=d(m) Then f=TrueIf KeyLoop元素d(1)到d(7)的值依次是“10,20,30,40,50,60,70”,文本框Text1中输入35后运行程序段,运行结束后下列说法正确的是( ) A.变量f的值是True B.变量i的值是4C.变量m的值是3.5 D.变量n的值是4解析 本题考查的是对分查找的变形。在程序执行过程中,各个变量的值变化情况如下表所示:i 1 1 3 4j 7 3 3 3n 1 2 3 m 4 2 3 f false false false d(m) 40 20 30 程序执行后,变量i=4,变量j=3,变量n=3,变量m=3,变量f=false。答案 B3.某对分查找算法的VB程序段如下:n = 0: i =1: j =6Key = Val(Text1.Text) f = FalseDo While i < = j And Not f m = (i + j +1) \ 2 n = n + 1 If Key = d (m) Thenf = True ElseIf Key > d(m) Thenj=m-1 Elsei=m+1 End IfLoop数组元素d(1)到d(6)的值依次为“87,72,53,41,29,18”,若该程序段运行后,n的值为2,则key的值是( )A.87或29 B.72或18C.72或29 D.53或18解析 本题考查对分查找的变形,n代表查找次数,n=2代表查找次数是2次。第一次查找:i=1,j=6,m=4,d(m)=41。第二次查找分为两种情况,第一种情况是key<41,i=1,j=3,m=2,d(m)=72;第二种情况是key>41,i=5,j=6,m=6,d(m)=18,所以答案是B。答案 B4.某对分査找算法的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(7)的值依次为“24,35,38,41,45,69,78”。若该程序段执行后,文本框Text1中显示的内容可能是( )A.RL B.LMRC.RLR D.LRLM解析 本题主要考查对分查找的变形和查找次数,最简单的方法是使用排除法。分析程序可知,查找成功则会输出“M”,循环结束,所以“M”不可能出现在中间,排除B选项。对于n个数据查找,最多的查找次数是Log2n+1(向下取整),7个元素最多只需要查找3次,所以排除D选项,如果无法找到数据,则不会输出“M”,则需要查找的次数是3次,所以排除A选项。答案 C5.数组a中有100个正整数,已按升序排列。在文本框Text1中输入一个正整数key,寻找数组a中是否有一对数的和等于给定的数key。若存在和为key的数对,输出该数对包含的两个整数,小的在前,大的在后。若有多个数对满足条件,则输出最先找到的数若找不到符合要求的数对,则输出“没有符合条件的数对”。小吴为此编写了VB程序,代码如下,但加框处代码有错,请改正。Dim a(1 To 100) As IntegerConst n = 100Private Sub Command1_C1ick()Dim key As Integer, left As Integer, right As Integer, mid As IntegerDim flag As Booleanflag = False: key = Val(Text1.Text)For i = 1 To n - 1 ′①right = nDo While ′②mid = (left + right)\2If a(i)+a(mid) < key Then left = mid + 1ElseIf a(i)+a(mid) > key Then right = mid-1Else List1.AddItem Str(a(i)) & “ ” & Str(a(mid)) flag = TrueEnd IfLoopNext iIf Not flag Then Listl.AddItem “没有符合条件的数对”End Sub程序中加框①处应改正为____________________________________________;加框②处应改正为___________________________________________________。解析 i=1时,从a(2)到a(100)里面查找a(mid),使a(1)+a(mid)等于key。在a(2)到a(50)之间采用对分查找如果找到,输出,Flag变为True,循环结束。否则继续……i=2时,从a(3)到a(50)里面查找a(mid),使a(2)+a(mid)等于key。答案 ①left=i+1 ②left<=right And Not Flag基础巩固1.下列关于数列查找说法,正确的是( )A.使用对分查找,数列中每个元素对象不能是字符串类型的数据B.使用对分查找数列,数列中每个元素要求必须是经过排序的C.对于规模为1000万项数的数列,不能使用顺序查找D.使用顺序查找,只能从第1个元素依次向后进行查找解析 对分查找的前提是被查找的数据是有序的(升序或降序),数据类型可以使数字类型也可以是字符串类型。顺序查找可以从第一个数据依次往后查找,也可以从最后一个数据依次向前查找。答案 B2.某对分査找算法的VB程序段如下:i = 1: j = 9: f = FalseDo While i <= j And Not fm = Fix((i + j) / 2)If a(m) = Key Thenp = m : f = TrueEnd IfIf a(m) > Key Thenj = m - 1Elsei = m + 1End IfLoopIf f = True Then Text1.Text=“数据位置:” + Str(p)Else Text1.Text=“没有找到该数据!”End If 数组元素a(1)到a(9)的值依次为10,15,30,32,38,42,45,48,68,若通过如下程序段查找数据key=43,则在执行该程序段的过程中,依次访问的数据是( )A.38,45,42 B.38,45,48C.38,48,42 D.38,48,45解析 本题考查的是对分查找的变形。在程序执行过程中,各个变量的值变化情况如下表所示,所以答案选A。i 1 6 6 7j 9 9 6 6m 5 7 6 a(m) 38 45 42 答案 A3.某对分査找算法的VB程序段如下:Key = Val(Text1.Text)i = 1: j = 10:Text2.Text=“ ”Do While i <= jm=(i+j+1)\2If key = a(m) Then Exit DoIf key > a(m) Then j=m-1 Else i=m+1Text2.Text=Text2.Text+Str(a(m))Loop已知数组 a(1 To 10)中的数据分别是83、80、66、46、44、36、21、16、15、12,在文本框Text1中输入80,执行该程序段,文本框Text2中显示的是( )A.36 66 B.44 88C.36 46 D.44 66解析 本题考查的是对分查找的变形。在程序执行过程中,各个变量的值变化情况如下表所示,所以答案是A。i 1 1 1j 10 5 2m 6 3 2a(m) 36 66 80答案 A4.某对分查找算法的VB程序段如下:Key = Val(Text1.Text) Mod 10Text2.Text = “ ”i = 1: j = 10: f = FalseDo While i <= j And Not fm = (i + j) \ 2If a(m) \ 10 = Key Then search = m:f = TrueElseIf a(m) \ 10 < Key Then i = m + 1Else j = m - 1End IfText2.Text = Str(m) + Text2.TextLoop数组元素a(1)到a(10)的值依次为:8,15,19,23,35,37,42,48,55,68,文本框Text1中输入21,执行该程序段,文本框Text2中显示的是( )A.5 2 B.2 5C.15 35 D.35 15解析 本题考查的是对分查找的变形。Key=1,在程序执行过程中,各个变量的值变化情况如下表所示,所以答案是B。i 1 1j 10 4m 5 2a(m) 35 15a(m)\10 3 1答案 B能力提升5.已知一无序数组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))解析 对分查找的数组必须有序,数组a(i)是无序的无法对分查找,但a(b(i))是有序的可以对分查找。第一次查找时,有序数组a(b(i))的中点数据为a(b(3)),也就是m=3。所以答案是B。答案 B6.有如下VB程序段:Key = Val(Text1. Text)i = 1: j = 10flag = Falses =“ ”Do While i <= j And Not flag mid1 = Int(i + (j - i) / 3) mid2 = Int(j - (j - i) / 3) If Key = a (mid1) Then flag = True ElseIf Key j = mid1 - 1 ElseIf Key = a(mid2) Then flag = True ElseIf Key >a(mid2) Then i = mid2 + 1 Else i = mid1 + 1 :j = mid2 - 1 End If s = s & “ ” & mid1 & “:” & mid2LoopText2.Text = s已知数组 a(1 To 10)中的数据分别是 12、21、34、45、59、63、72、86、94、100,在文本框Text1中输入34,程序运行后文本框Text2 中显示的内容是( )A.4:7 1:2 B.4:7 1:2 3:3C.4:7 1:3 3:3 D.4:7 3:3解析 本题考查的是对分查找的变形。在程序执行过程中,各个变量的值变化情况如下表所示,所以答案选B。i 1 1 3j 10 3 3mid1 4 1 3mid2 7 2 3a(mid1) 45 12 34a(mid2) 72 21 34答案 B7.利用对分査找算法计算整数勾股数对的VB程序段如下:flag = True : p = 0Key = 5For i = 1 To Key - 1 L = i + 1: R = Key - 1 Do While L <= R And flagM = (L + R) \'2p = p + 1If i * i + M * M < Key * Key Then L = M + 1ElseIf i * i + M * M > Key * Key Then R = M - 1Else Text2.Text = Str(i) + “ ”+Str(M) + “ ” + Str(key) flag = False i = KeyEnd If LoopNext iIf flag Then Text2.Text = “没有符合条件的整数勾股数对!”程序运行后,变量p的值为( )A.3 B.4 C.5 D.6解析 采用分类讨论的方法。当i=1时,m=3、4循环2次,i=2时,m=3、4循环2次,i=3时,m=4循环1次,找到Key为5,符合条件,共循环5次。答案 C8.数组元素a(0)到a(9)的值依次为“13,20,22,25,30,33,40,52,65,100”,文本框Text1中输入的值是33,执行该程序段,下列描述正确的是( )key = Val(Text1.Text)i = 0: j = 9: s = 0Do While i <= j m = Fix((i + j) \ 2 + 0.5) s = s + 1 If key = a(m) ThenLabel1.Caption = Label1.Caption + “→” + Str(m)Exit Do ′Exit Do表示退出循环 End If If key < a(m) Then j = m - 1 Else i = m + 1 Label1.Caption = Label1.Caption + “→” + Str(m)LoopLabel2.Caption = “历经” + CStr(s) + “步”A.标签Label1显示内容为“→4→7→5”B.标签Label2显示内容为“历经1步”C.该程序为顺序查找,查找次数为3D.该程序为对分查找,查找次数为4解析 本题考查的是对分查找的变形。在程序执行过程中,各个变量的值变化情况如下表所示,标签Label1显示内容为“→4→7→5”,标签Label2显示内容为“历经3步”,该程序为对分查找,查找次数为3,故答案是A。i 0 5 5j 9 9 6m 4 7 5a(m) 30 52 33答案 A9.小王编写了一个实现文字查找替换功能的VB程序,运行界面如图所示。文本框Text1显示原文内容,Text2中输入查找内容,Text3中输入替换内容,单击“全部替换”按钮Command1后,Text4显示查找替换的结果,Text5中显示替换的次数,Text6显示“查找内容”在原文中的起始位置。实现上述功能的VB程序如下,但加框处代码有错,请改正。Private Sub Command1_Click() Dim s As String, result As String, pos As String Dim count As Integer, i As Integer i = 1: count = 0 result = “ ”: 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 = ′① i = i + Len(Text2.Text)Else ′② i = i + 1End If Loop Text4.Text = result Text5.Text = Str(count) Text6.Text = posEnd Sub程序中加框①处应改正为____________________________________________;加框②处应改正为________________________________________________。解析 ①变量result存储替换后的新字符串,count存储替换次数,pos存储替换位置。程序通过变量i来读取原字符串中的字符,因此当前的位置是i。②Else语句对应的情况是:原字符串中取出来的子串不等于替换内容,因此不需要替换,保持原样,从该行代码紧接着“i=i+1”可得出字符串往后移动一位,因此result需要保存原字符串当前位置i上的一个字符。答案 ①pos+Str(i) ②result=result+Mid(Text1.Text,i,1)10.某校季运动会共n名运动员参赛,小明编写了根据号码牌查询学生信息的软件,输入号码牌就能查询该号码牌所属的班级和选手姓名。数组a、b、c分别保存了本次运动会所有选手的号码牌、班级、姓名的信息。第i个选手的号码牌保存在a(i)中,对应的班级和姓名保存在b(i)和c(i)中。程序界面如图所示,在文本框Text1中输入号码牌,单击“查询”按钮(Command1),如果找到对应的信息,就显示所属班级和选手姓名,如果没有找到,则显示“未找到”。(1)分析程序,可知数据库的文件名为__________,当前数据表的名称为:________。(2)填入适当的语句和代码,把程序补充完整。Dim n As Integer ′用于存储运动员总人数Dim a(1000) As Integer, b(1000) As String,c(1000) As StringPrivate Sub Form_Load()Dim conn As New ADODB.ConnectionDim rs As New ADODB.Recordsetconn.ConnectionString = “Provider = Microsoft.Jet.OLEDB.4.0;DATA Source=” & App.Path & “\sport.accdb”conn.OpenSet rs.ActiveConnection = connrs.Open “号码牌”n = 0Do While Not rs.EOF ′到记录集rs的最后一条记录后退出循环n = n + 1 a(n) = rs.Fields(“号码”) ′读取当前记录“号码”字段值b(n) = ____①____ ′读取当前记录“班级”字段值c(n) = rs.Fields(“姓名”) ′读取当前记录“姓名”字段值 ____②____ ′移动到下一条记录Loop′按号码牌升序排序后,显示在列表框List1中′其他代码略。End SubPrivate Sub Command1_Click() Dim x As Integer x = Val(Text1.Text) pos = ______③______ If pos > 0 ThenText2.Text = b(pos):Text3.Text = c(pos) ElseText2.Text = “未找到” End IfEnd SubFunction Search(Key As Integer) As Integer Dim i As Integer, j As Integer, i = 1:j = n:Search = 0 Do While i <= jm = Fix((i + j) / 2)If Key = a(m) Then Search = m : Exit FunctionElseIf______④______ Thenj = m - 1Elsei = m + 1End If LoopEnd Function解析 (1)①根据数据文件名的扩展名accdb,在数据库连接代码中查找,即可找到sport.accdb。②代码rs.Open “号码牌”得知打开的是“号码牌”数据表。(2)①读取当前记录“班级”字段值到数组b中,即b(n)=rs.Fields(“班级”)。②移动到下一条记录rs.MoveNext。③调用自定义函数,注意函数参数,将过程中x值传递给自定义函数中的key,即:Search(x)。函数的计算结果为数组中对应元素的下标,如果函数结果为0,意味着没有找到。 ④理解对分查找算法。答案 (1)①sport.accdb ②号码牌 (2)①rs.Fields(“班级”) ②rs.MoveNext ③Search(x) ④key < a(m)(共31张PPT)第4节 查找算法考试内容 考试要求 顺序查找算法思想及程序实现 c 对分查找算法思想及其变形的程序实现 c 一、顺序查找算法思想和程序实现顺序查找的基本思想是从第一个数据开始,按顺序逐个将数据与给定的数据(查找键)进行比较,若某个数据和查找键相等,则查找成功,输出所查数据的位置;反之,输出未找到。For i = 1 To nIf a(i)=key Then Exit ForEnd IfNext i 代码分析:将数组中的每个元素逐个与key进行比较,如果相等则查找成功,循环结束。如果循环结束后,变量i的值等于n+1,则意味着没有找到。顺序查找数组可以无序 二、对分查找算法思想对分查找又称二分查找,是一种高效的查找方法。对分查找的前提是被查找的数据是有序的(升序或降序)。对分查找的基本思想是在有序的数列中,首先将要查找的数据与有序数列内处于中间位置的数据进行比较,如果两者相等,则查找成功;否则就根据数据的有序性,再确定该数据的范围应该在数列的前半部分还是后半部分;在新确定的缩小范围内,继续按上述方法进行查找,直到找到要查找的数据,即查找成功,如果要查找的数据不存在,即查找不成功。若key为查找关键字,数组d存放n个已按升序排序的数据。使用对分查找时,把查找范围[i,j]的中间位置上的数据d(m)与key进行比较,结果必然是如下三种情况之一:(1)若key(2)key=d(m),找到了需要的数据;(3)key>d(m),查找键大于中点d(m)处的数据。由数组d中的数据的递减性,可以确定:在(i, m)内不可能存在值为key的数据,必须在新的范围(m+1,j)中继续查找。这样,除了出现情况(2),在通过一次比较后,新的查找范围将不超过上次查找范围的一半。数组d为例,观察对分查找的过程。要查找的数据key=52,查找过程如下:三、对分查找算法代码实现i = 1: j = n: s = 0Do While i <= j m = (i + j) \ 2 If a(m) = key Then s = m: Exit Do ElseIf key < a(m) Then j = m - 1 Else i = m + 1 End IfLoop 左边程序实现在升序数组a(1)…a(n)中查找值等于key的元素,将其下标存储在s中。如果没有找到则s值为0,如果找到,则s存储对应元素的下标。对分查找前提是数据有序,对n个数据查找,最多查找次数为Log2n+1(向下取整)。例如在有序数组a(1)…a(10000)中查找某个值,最多需要查找Log210000+1,即14次 一、顺序查找算法思想和代码实现【典例1】 小王拿着一大串钥匙去开仓库的某一扇门,由于钥匙上没有任何标记,小王只能将这一串钥匙一把一把地去试,从算法角度看,小王的做法属于( ) A.冒泡排序 B.选择排序 C.对分查找 D.顺序查找 解析 本题考查两个算法的区别。顺序查找的思想第从第一个数据开始,按数据的顺序逐个将数据与给定的值进行比较,若某个数据与给定的值相等,则查找成功,否则查找不成功。 答案 D【变式训练】 用对分查找法和顺序查找法在数字序列“1,2,3,5,8,13,21,34,55”中查找数字13,两种方法都能访问到的数字是( ) A.3 B.5 C.8 D.34 解析 对分查找访问到的数字为8、21、13,顺序查找访问到的数字为1,2,3,5,8,13。两者共同为8。 答案 C二、对分查找算法思想【典例2】 已知单调函数f(x)在[0,1]区间存在一个x0,使f(x0)=0。现用对分查找法搜索x0的值,开始搜索区间为[0,1],若经过10次对分查找后还需继续搜索,则第11次搜索区间的长度为( ) A.1/2 B.1/10 C.1/102 D.1/210 解析 对分查找的每次区间变为上次的二分之一。第2次为原搜索区间的长度1/2,第3次为原搜索区间的长度1/4……第11次为原搜索区间的长度1/210,所以答案D。 答案 D【变式训练】 下列有关查找的说法,正确的是( )A.进行对分查找时,被查找的数据必须已按升序排列B.进行对分查找时,如果查找的数据不存在,则无需输出结果C.在新华字典中查找某个汉字,最适合使用顺序查找答案 D【典例3】 数组变量d(1)到d(8)的值依次为97、86、79、68、56、41、33、13,用“对分查找”找到“13”的过程中,依次被访问到的数据是( ) A.68、13 B.68、41、13 C.56、41、33、13 D.68、41、33、13 解析 本题考查标准的对分查找,查找中间项为m=(i+j)\2,经过4次对分查找。答案 Di 1 5 7 8 j 8 8 8 8 m 4 6 7 8 d(m) 68 41 33 13 【变式训练】 在有序单词序列“bike,cake,data,easy,feel,great,hive,mark,sweet”中,用对分查找算法找到“easy”过程中,依次被访问到的数据为( )A.feel, data, easy B.great, data, easyC.bike, cake, dada,easy D.feel,cake,data,easy解析 本题考查标准的对分查找,查找中间项为m=(i+j)\2,经过4次对分查找。i 1 1 3 4 j 9 4 4 4 m 5 2 3 4 d(m) feel cake data Easy 答案 D三、对分查找算法代码实现【典例4】 某对分査找算法的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 ′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或61C.18或72 D.12或61解析 n代表查找次数,代入选项计算查找次数为2,即为答案。key=12,第1次:m=5,i=1,j=4;第2次:m=2 ,d(m)=12查找成功。key=61,第1次:m=5,i=6,j=9;第2次:m=7 ,d(m)=61查找成功。所以答案选D。答案 D【变式训练】 采用如下对分查找算法对数组a中7个有序数据“15,38,51,66,77,81,99”进行查找,查找数据为“55”,i = 1: j = 7: x = 55Do While i <= j m = (i + j) \ 2 If a(m) = x Then Exit Do If a(m) > x Then j = m - 1 Else i = m + 1Loop执行完上述代码后,根据最终变量值判断下列表达式,其中正确的是( )A.i=m+1 B.i=m-1C.j>m+1 D.j解析 本题考查标准的对分查找,查找中间项为m=(i+j)\2,最终没有找到该数据。算法结束时i=4,j=3,m=3,所以答案选A。答案 Ai 1 1 3 4 j 7 3 3 3 m 4 2 3 ? d(m) 66 38 51 ? 【典例5】 有如下VB程序段:i = 1 : j = 10 : flag = True : n = 0 Key = Val(Text1.Text)Do While i <= j And flag = True m = (i + j) \ 2 If a(m) = Key Then flag = False ElseIf a(m) > Key Then i = m + 1 : n = n - 1 Else j = m - 1 : n = n + 1 End IfLoop数组元素a(1)到a(10)依次是99, 94, 90, 87, 70,69,60,56,45,36,变量n的值最终是0,则文本框Text1输入的数字可能是( )A.100 B.87 C.69 D.41解析 本题考查的是对分查找的变形。当key=100时,程序执行过程中,各个变量的值变化情况如下表所示:i 1 1 1 1 j 10 4 1 0 m 5 2 1 ? d(m) 70 94 99 ? n 1 2 3 ? 当key=87时,程序执行过程中,各个变量的值变化情况如下表所示:i 1 1 3 4 j 10 4 4 4 m 5 2 3 4 d(m) 70 94 90 87 n 1 0 -1 ? 当key=69时,程序执行过程中,各个变量的值变化情况如下表所示:i 1 6 6 j 10 10 7 m 5 8 6 d(m) 70 56 69 n -1 0 ? 当key=41时,程序执行过程中,各个变量的值变化情况如表所示。i 1 6 9 10 10 j 10 10 10 10 9 m 5 8 9 10 ? d(m) 70 56 45 36 ? n -1 -2 -3 -2 ? 答案 C【变式训练】 有如下VB程序段:i = 1: j = 9: f = FalseDo While i <= j And Not f m = Fix((i + j) / 2) If a(m) = Key Then p = m : f = True End If If a(m) > Key Then j = m - 1 Else i = m + 1 End IfLoopIf f = True Then Text1.Text=“数据位置:” + Str(p)Else Text1.Text=“没有找到该数据!”End If 数组元素a(1)到a(9)的值依次为10,15,30,32,38,42,45,48,68,若通过如下程序段查找数据key=43,则在执行该程序段的过程中,依次访问的数据是( )A.38,45,42 B. 38,45,48 C.38,48,42 D. 38,48,45解析 本题考查的是对分查找的变形。在程序执行过程中,各个变量的值变化情况如下表所示,所以答案选A。答案 Ai 1 6 6 j 9 9 6 m 5 7 6 d(m) 38 45 42 【典例6】 小明为了研究对分查找的过程中数据被访问的情况,编写了一个VB程序,功能如下:在列表框List1中显示已经排序的数据(存储在数组a中),在文本框Text1中输入要查找的数据,单击“查找”按钮Command1后,在标签Label1中显示查找中依次被访问到的数据。程序运行界面如图所示。实现上述功能的VB程序如下,但加框处代码有错,请改正。Const n = 10Dim a(1 To n) As IntegerDim s As StringPrivate Sub Form_Load()′产生随机数依次存储在数组a中,代码略′对数组a升序排序并在列表框输出,代码略End SubPrivate Sub Command1_Click() Dim x As Integer, p As Integer x = Val(Text1.Text) s = “ ” If p > 0 Then s = s + “查找成功” Else s = s + “查找失败” Label1.Caption = “依次被访问的数据为:” + sEnd SubFunction search(key As Integer) As Integer Dim i As Integer, j As Integer, flag As Boolean flag = False i = 1: j = n: search = 0 Do While i <= j And Not flag m = (i + j) \ 2 If a(m) = key Then search = m flag = True j = m - 1Else i = m + 1End Ifs = s + Str(a(m)) + “→” LoopEnd Function程序中加框(1)处应改正为_________________________________________;加框(2)处应改正为________________________________________________。解析 (1)联系下文代码If p > 0 Then,需要对变量p赋值,结合函数search的功能:如果在数组a中找到要查找的数,函数search 返回该数在数组中的位置,如果没有找到,函数search 返回值为0,结合程序得知第1空为:p=search(x)。(2)在一个块If语句中结合对分查找算法得出第2空为: ElseIf Key < a(m) Then。答案 (1)p=search(x) (2)ElseIf Key < a(m) Then 展开更多...... 收起↑ 资源列表 第4节查找算法.doc 第五单元第4节?查找算法.pptx