当前位置:文档之家› 2019浙江选考信息技术查找算法专题

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

(一)顺序查找1.顺序查找算法①顺序查找算法的处理过程假定在数组d中有n个数据,查找关键值已经存储在变量key中。

其处理过程是:从数组d的第1个元素d(1)开始,依次判断各元素的值是否与key相等,若某个数组元素d(i)的值等于key,则结束处理(找到了指定的数据);若找遍了所有的n个元素,无任何元素的值等于key,则结束处理(输出未找到信息)。

②顺序查找算法流程图与程序结构2.程序实现代码:k=0For i=1 T o nIf a i=key Then k=iNext iIf k<>0 Then' 输出查找成功Else' 输出查找不成功End If(二)对分查找1.对分查找的过程若key为查找键,数组d存放n个已按升序排序的数据。

在使用对分查找时,把查找范围[i,j]的中间位置上的数据d(m)与查找关键值key进行比较,结果必然是如下三种情况之一:(1)若key<d(m),查找key小于中点m处的数据。

由数组d中的数据的递增性,可以确定:在(m,j)内不可能存在值为key的数据,必须在新的范围(i,m-1)中继续查找;(2)key=d(m),找到了需要的数据;(3)key>d(m),由与(1)相同的理由,必须在新的范围(m+1,j)中继续查找。

这样,除了出现情况(2),在通过一次比较后,新的查找范围将不超过上次查找范围的一半。

以规模为16的递增数组d为例,观察对分查找的过程。

要查找的数据key为37。

使用流程图描述对分查找的算法如下图所示:2.对分查找算法程序的实现Private Sub Command1_Click()i =1: j =nDo While i <=jm =(i +j) \2If d(m) =Key Then'输出结果,退出查找(代码略)ElseIf Key < d(m) Thenj =m -1Elsei =m +1End IfLoopEnd Sub注意:中间位置数据d(m)的下标m的常见计算方法:m=(i+j)\2、m=int((i +j)/2)、m=fix((i+j)/2)、m=fix((i+j)/2+0.5)上面对分查找的算法用一个块if语句实现,也可以用其他等价的方式:3.查找次数的估算对规模为n的数组进行对分查找时,无论是否找到,至多进行log2n+1次查找就能得到结果,平均查找次数计算:(第1个数据需要的查找次数+第2个数据需要的查找次数+…+第n个数据需要的查找次数)/n而使用顺序查找算法,在最坏的情况下(查找键在最后一个或没找到),需要进行n次查找,最好的情况是一次查找(查找键在第一个),平均查找次数是n+1 2。

1、(2018.4)数组a为一组正整数,奇数在前,偶数在后。

奇数与偶数已分别按升序排序。

依据对分查找思想:设计一个在数组a中查找数据Key的程序。

实现该功能的VB程序段如下:i = 1: j = 10Key = Val(Text1.T ext)Do While i <= jm = (i + j) \ 2If a(m) = Key Then Exit Do 'Exit Do表示退出循环If Key Mod 2 = 1 And a(m) Mod 2 = 0 Then(1)ElseIf Key Mod 2 = 0 And a(m) Mod 2 = 1 Then(2)Else(3)End IfLoopIf i > j Then s = "没有找到!" Else s = "位置:" + Str(m)T ext2.T ext = s上述程序中方框处可选语句为:①i = m + 1②j = m - 1③If 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 <= jm = (i + j) \ 2If key = a(m) Thens = s + "M": Exit Do 'Exit Do 表示退出循环ElseIf key < a(m) Thenj = m - 1: s = s + "L"Elsei = m + 1: s = s + "R"End IfLoopT ext1.T ext = s数组元素a(1)到a(9)的值依次为“24,35,38,41,45,69,78”。

若该程序段执行后,文本框T ext1中显示的内容可能是A. RLB. LMRC. RLRD. LRLM3、(2017.4)某对分查找算法的VB程序段如下:key = Val(Text1.Text)i = 1: j = 10T ext2.T ext = ""Do While i <= jm = 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 + 1T ext2.T ext = T ext2.T ext + Str(a(m))Loop数组元素a(1)到a(10)的值依次为“8,17,24,30,36,40,55 ,58,61,66”,文本框T ext1中输入的值是30,执行该程序段,文本框T ext2中显示的是A .40 24B .40 24 36C .36 24D .36 17 244、(2016.10)某对分查找算法的VB 程序段如下:i = 1: j = 9:n=0key = Val(Text1.Text)Do While i <= jN=n+1m = fix((i + j) / 2)If key = d(m) Then Exit DoIf 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.39B. 18或61C.18或72D. 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)已知单调函数()f x 在[0,1]区间存在一个0x ,使0()0f x 。

现用对分查找法搜索0x 的值,开始搜索区间为[0,1],若经过10次对分查找后还需继续搜索,则第11次搜索区间的长度为A.1/2B. 1/10C. 21/10D. 101/27、(2017.4)小王编写了一个实现文字查找替换功能的VB 程序,运行界面如图所示。

文本框Text1显示原文内容,Text2中输入查找内容,Text3中输入替换内容,单击“全部替换”按钮Command1后,Text4显示查找替换的结果,Text5中显示替换的次数,Text6显示“查找内容”在原文中的起始位置。

实现上述功能的VB程序如下,但加框处代码有错,请改正。

Private Sub Command1_Click()Dim s As String, resule As String, pos As StringDim count As Integer, i As Integeri = 1: count = 0resule = "": pos = ""Do While i <= Len(T ext1.Text)s = Mid(Text1.T ext, i, Len(T ext2.T ext))If s = T ext2.Text Thenresult = result + T ext3.Textpos = pos + Str(count)result = result + T ext2.TextEnd IfLoopT ext4.T ext = resultT ext5.T ext = Str(count)T ext6.T ext = posEnd Sub1、按钮command1的鼠标事件处理过程如下:Private Sub Command1_Click()Dim st(1 T o 6) As Stringst(1) = "she":st(2) = "her":st(3) = "your"st(4) = "me":t(5) = "you":st(6) = "i"Key = text1.T extt = Falsei = 0Do While i < 6 And t = Falsei = i + 1If st(i) = Key Then t = TrueLoopIf t = flase Then i = 0text2.T ext = Str(i)End Sub程序运行时,在文本框中输入“you”后单击按钮command1后,在文本框text2中显示的内容是()A.0B.1C.5D.72、某8位男生的肺活量数据放在数组a(1)到a(8)中,其数据依次为“3104,3700,3058,3222,3621,3329,4233,4540”。

使用顺序查找算法查找数据3339,则共需查找次数为()A.0B.1C.8D.93、有以下两组数据:①54,31,43,12,8,73,56,34,89,60,23,67②87,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”。

相关主题