资源简介 (共20张PPT)对分查找变式基础知识key不确定情况key确定情况代码选填情况基础知识(1)基本理念(2)基本代码(3)查找次数(4)中值情况m=(i+j)\2m=Int((i+j))/2m=Int(i+j+1)\2m=Fix((i+j)/2)m=Fix((i+j)/2+0.5)m=Fix((i+j+0.5)/2)左左右左右左1.某对分查找算法的部分代码如下:i=1:j=1000:flag=True:p=0key=val(Text1.Text)DoWhilei<=jAndflagm=(i+j)\2p=p+1ifa(m)=keyThenflag=Falseifa(m)>keyThenj=m-1Theni=m+1Loop数组元素a(1)到a(1000)中存放着升序排列的数据。下列说法正确的是()A.若key的值小于a(1),则执行该段程序后,变量j的值等于1B.若key的值等于a(1),则执行该段程序后,变量p的值等于10C.若key的值等于a(1000),则执行该段程序后,变量i的值等于1001D.无论key的值是否在数值中a中,执行该段程序后,变量i的值均不可能等于m基础知识key确定情况(1)观察key的值(2)注意分支语句代码块的变化(3)通过输出进行推导key确定情况1.数组元素a(0)到a(9)的值依次为“15,20,25,30,35,40,45,50,55,60”,文本框Text1中输入的是40,执行该程序段,下列描述正确的是()Key=Val(Text1.Text)i=0:j=9:s=0DoWhilei<=jm=Fix((i+j)/2+0.5)s=s+1ifKey=a(m)ThenLabel1.Caption=Label1.Caption+”→”+Str(m)ExitDoEndififKeyThenj=m-1Elsei=m+1Label1.Caption=Label1.Caption+”→”+Str(m)LoopLabel2.Caption=“经历”+Str(s)+“步”A.标签Label1显示内容为“→4→7→5”B.标签Label2显示内容为“历经1步”A.该程序为顺序结构,查找次数为3A.该程序为对分查找,查找次数为3key确定情况2.已知数组元素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=FalseDoWhilei<=jAndNotfm=(i+j)\2ifa(m)Mod10=KeyThensearch=mf=TrueElseifa(m)Mod10>KeyTheni=m+1Elsej=m-1EndifText2.Text=Text2.Text+Str(m)Loop则在执行该程序后,Text2中显示的内容是()A.52B.578C.552837D.553728key不确定情况(1)观察key的取值(2)注意分支语句代码块的变化(3)通过二叉树求解key不确定情况1.a(1)=2:a(2)=4:a(3)=5:a(4)=6:a(5)=8:a(6)=10:a(7)=11:a(8)=12n=0Key=int(Rnd7)+2L=1:R=8DoWhileL<=Rm=(L+R)\2ifKey=a(m)ThenExitDoElseifa(m)ThenL=m+1n=n+1ElseR=m-1n=n-1LoopprintStr(n)则程序运行后,输出的结果不可能是()A.0B.1C.-1D.-2key不确定情况2.某对分查找算法的VB程序段如下:Key=int(Rnd49)2+1s=0:i=1:j=10DoWhilei<=jm=(i+j)\2ifKey=a(m)ThenExitDoifKeyThenj=m-1:s=2sElsei=m+1:s=2s+1EndifLoop数组元素a(1)到a(10)的值依次为“2,6,7,15,20,24,27,43,52,63”,执行该程度段后,s的值不可能为()A.2B.3C.5D.15代码选填情况(1)关注填空区域(2)考虑最不利情况代码选填情况1.用对分查找的方法求不等式2x+3x-5≤n(n≥0)的最大正整数解,编写的VB程序段如下:PrivateSubCommand1_Click()DimLAsInteger,RAsInteger,nAsIntegerxAsIntegern=Val(Text1.Text)L=1R=n+1DoWhile①x=(L+R)\2if2^X+3x-5<=nThenL=x+1ElseR=x-1LoopLabel1.Cption=”方程2^X+3x-5<=n的最大正整数解为:”+②EndSu要使程序实现上述算法思想,则横线上的语句是()A.①L②Str(L)B.①L②Str(R)C.①L<=R②Str(L)D.①L<=R②Str(R)代码选填情况2.某vb程序段如下:L=1:R=10:n=10:key=78DoWhileL<=Rm=Fix((L+R)/2)if①ThenR=m-1ElseL=m+1EndIfLoopFori=1ToRList1.AdditemStr(a(i))Nexti数组元素a(1)到a(10)的值依次为86,78,78,77,73,69,60,54,54,51,若执行该程序段后,列表框List1中输出的数据个数为3,则①处的代码为()A.Key>a(m)B.Key>=a(m)C.KeyD.Key<=a(m)实战训练1.有如下VB程序段:i=1:j=63:n=0DoWhilei<=jM=(i+j)\2IfKey=a(m)ThenExitDoElselfKey<a(m)ThenJ=m-1:n=n-1ElseI=m+1:n=n+1EndifLoop数组元素a(1)到a(63)存放着递增的数据。若执行该程序段后n的值为6,则下列表达式成立的是()A.keyB.key=a(1)C.key=a(63)D.key>a(63)2.有VB程序段如下:a(1)=2:a(2)=2:a(3)=5:a(4)=6:a(5)=7Key=2i=1:j=5:flag=FalseDoWhilei<=jAndNotFlagm=(i+j)\2ifKey=a(m)Thens=”找到第”+Str(m)+“个”flag=True:ExitDoElseifKeyThenj=m-1Elsei=m+1Endifs=str(m)+sLoopLabel1.Caption=s实战训练执行该程序后,在标签Label1中显示的内容是()A.13B.31C.找到第1个D.找到第2个实战训练3.某对分查找算法的VB程序段如下:i=1:j=8:t=0key=int(Rnd()7)+14DoWhilei<=jm=int((i+j)/2)t=t+1ifa(m)=keyThenExitDoElseifa(m)>KeyThenj=m-1Elsei=m+1EndifEndifLoop数组元素a(1)到a(8)的值依次为“2,11,14,15,18,19,20,22”,执行该程度段后,变量t的最大值可能是()A.1B.2C.3D.4实战训练4.数组元素a(1)-a(2n)中存储的一批正整数,以两个数为一组,每组中两个数均比前面一组的两个数要大。现用对分查找的思想,设计一个在数组a中查找数据key的程序,如果找到key,在标签Label1上显示“yes”,否则显示“no”。Key=Val(Text1.Text)i=1:j=n2:flag=FalseDoWhilei+1<=jAndNotflagm=(i+j)\2If①Thenm=m-1Ifa(m)=Keyora(m+1)=KeyThenFlag=TrueElseifa(m)>keyThen②Else③EndifLoopIfa(i)=KeyOra(j)=KeyThenflag=TrueIfflagThenLabel1.Caption=”yes”ElseLabel1.Caption=”no”划线处的代码正确的是()A.①mMod2=1②j=m-1③i=m+2B.①mMod2=0②j=m-1③i=m+2C.①mMod2=1②j=m-2③i=m+2D.①mMod2=0②j=m-2③i=m+2小结1.key确定情况2.key不确定情况3.代码选填情况中小学教育资源及组卷应用平台对分查找变式【基础知识】1.某对分查找算法的部分代码如下:i=1:j=1000:flag=True:p=0key=val(Text1.Text)DoWhilei<=jAndflagm=(i+j)\2p=p+1ifa(m)=keyThenflag=Falseifa(m)>keyThenj=m-1Theni=m+1Loop数组元素a(1)到a(1000)中存放着升序排列的数据。下列说法正确的是()A.若key的值小于a(1),则执行该段程序后,变量j的值等于1B.若key的值等于a(1),则执行该段程序后,变量p的值等于10C.若key的值等于a(1000),则执行该段程序后,变量i的值等于1001D.无论key的值是否在数值中a中,执行该段程序后,变量i的值均不可能等于m【key确定情况】技巧:(1)观察key的值(2)注意分支语句代码块的变化(3)通过输出进行推导1.数组元素a(0)到a(9)的值依次为“15,20,25,30,35,40,45,50,55,60”,文本框Text1中输入的是40,执行该程序段,下列描述正确的是()Key=Val(Text1.Text)i=0:j=9:s=0DoWhilei<=jm=Fix((i+j)/2+0.5)s=s+1ifKey=a(m)ThenLabel1.Caption=Label1.Caption+”→”+Str(m)ExitDoEndififKeyThenj=m-1Elsei=m+1Label1.Caption=Label1.Caption+”→”+Str(m)LoopLabel2.Caption=“经历”+Str(s)+“步”A.标签Label1显示内容为“→4→7→5”B.标签Label2显示内容为“历经1步”A.该程序为顺序结构,查找次数为3A.该程序为对分查找,查找次数为32.已知数组元素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=FalseDoWhilei<=jAndNotfm=(i+j)\2ifa(m)Mod10=KeyThensearch=mf=TrueElseifa(m)Mod10>KeyTheni=m+1Elsej=m-1EndifText2.Text=Text2.Text+Str(m)Loop则在执行该程序后,Text2中显示的内容是()A.52B.578C.552837D.553728【key不确定情况】技巧:(1)观察key的取值(2)注意分支语句代码块的变化(3)通过二叉树求解1.a(1)=2:a(2)=4:a(3)=5:a(4)=6:a(5)=8:a(6)=10:a(7)=11:a(8)=12n=0Key=int(Rnd7)+2L=1:R=8DoWhileL<=Rm=(L+R)\2ifKey=a(m)ThenExitDoElseifa(m)ThenL=m+1n=n+1ElseR=m-1n=n-1LoopprintStr(n)则程序运行后,输出的结果不可能是()A.0B.1C.-1D.-22.某对分查找算法的VB程序段如下:Key=int(Rnd49)2+1s=0:i=1:j=10DoWhilei<=jm=(i+j)\2ifKey=a(m)ThenExitDoifKeyThenj=m-1:s=2sElsei=m+1:s=2s+1EndifLoop数组元素a(1)到a(10)的值依次为“2,6,7,15,20,24,27,43,52,63”,执行该程度段后,s的值不可能为()A.2B.3C.5D.15【代码选填情况】技巧:(1)关注填空区域(2)考虑最不利情况1.用对分查找的方法求不等式2x+3x-5≤n(n≥0)的最大正整数解,编写的VB程序段如下:PrivateSubCommand1_Click()DimLAsInteger,RAsInteger,nAsIntegerxAsIntegern=Val(Text1.Text)L=1R=n+1DoWhile①x=(L+R)\2if2^X+3x-5<=nThenL=x+1ElseR=x-1LoopLabel1.Cption=”方程2^X+3x-5<=n的最大正整数解为:”+②EndSub要使程序实现上述算法思想,则横线上的语句是()A.①L②Str(L)B.①L②Str(R)C.①L<=R②Str(L)D.①L<=R②Str(R)2.某vb程序段如下:L=1:R=10:n=10:key=78DoWhileL<=Rm=Fix((L+R)/2)if①ThenR=m-1ElseL=m+1EndIfLoopFori=1ToRList1.AdditemStr(a(i))Nexti数组元素a(1)到a(10)的值依次为86,78,78,77,73,69,60,54,54,51,若执行该程序段后,列表框List1中输出的数据个数为3,则①处的代码为()A.Key>a(m)B.Key>=a(m)C.KeyD.Key<=a(m)【实战演练】有如下VB程序段:i=1:j=63:n=0DoWhilei<=jM=(i+j)\2IfKey=a(m)ThenExitDoElselfKey<a(m)ThenJ=m-1:n=n-1ElseI=m+1:n=n+1EndifLoop数组元素a(1)到a(63)存放着递增的数据。若执行该程序段后n的值为6,则下列表达式成立的是()A.keyB.key=a(1)C.key=a(63)D.key>a(63)2.有VB程序段如下:a(1)=2:a(2)=2:a(3)=5:a(4)=6:a(5)=7Key=2i=1:j=5:flag=FalseDoWhilei<=jAndNotFlagm=(i+j)\2ifKey=a(m)Thens=”找到第”+Str(m)+“个”flag=True:ExitDoElseifKeyThenj=m-1Elsei=m+1Endifs=str(m)+sLoopLabel1.Caption=s执行该程序后,在标签Label1中显示的内容是()A.13B.31C.找到第1个D.找到第2个3.某对分查找算法的VB程序段如下:i=1:j=8:t=0key=int(Rnd()7)+14DoWhilei<=jm=int((i+j)/2)t=t+1ifa(m)=keyThenExitDoElseifa(m)>KeyThenj=m-1Elsei=m+1EndifEndifLoop数组元素a(1)到a(8)的值依次为“2,11,14,15,18,19,20,22”,执行该程度段后,变量t的最大值可能是()A.1B.2C.3D.4数组元素a(1)-a(2n)中存储的一批正整数,以两个数为一组,每组中两个数均比前面一组的两个数要大。现用对分查找的思想,设计一个在数组a中查找数据key的程序,如果找到key,在标签Label1上显示“yes”,否则显示“no”。Key=Val(Text1.Text)i=1:j=n2:flag=FalseDoWhilei+1<=jAndNotflagm=(i+j)\2If①Thenm=m-1Ifa(m)=Keyora(m+1)=KeyThenFlag=TrueElseifa(m)>keyThen②Else③EndifLoopIfa(i)=KeyOra(j)=KeyThenflag=TrueIfflagThenLabel1.Caption=”yes”ElseLabel1.Caption=”no”划线处的代码正确的是()A.①mMod2=1②j=m-1③i=m+2B.①mMod2=0②j=m-1③i=m+2C.①mMod2=1②j=m-2③i=m+2D.①mMod2=0②j=m-2③i=m+2答案:1.C1.B2.B1.B2.A1.D2.A1.D2.C3.C4.B21世纪教育网www.21cnjy.com精品试卷·第2页(共2页)HYPERLINK"http://21世纪教育网(www.21cnjy.com)"21世纪教育网(www.21cnjy.com) 展开更多...... 收起↑ 资源列表 对分查找.pptx 对分查找变式.doc