查找算法

必考+加试·信息技术第三单元查找算法必考+加试·信息技术考点与典例考点1顺序查找1.查找算法所谓查找就是在指定的数据中寻找某一特定的数据。查找结果有两种:找到(查找成功)和未找到(查找失败)。2.顺序查找的基本思想从第一个数据开始,从左往右(或从上到下)将数据按顺序逐个与给定的关键字进行比较,若某个数据和给定的关键字相等,则查找成功,找到并输出第一个与关键字相等的数据的位置;反之,查找失败。若有n个数,则可能的最多查找次数为n。必考+加试·信息技术3.顺序查找算法基本框架假设:要查找的数为key,待查找的数存放在数组d中。For语句框架:Fori=1Ton若d(i)=key,则表示找到,做相应处理Nexti若in表示未找到DoWhile语句框架:i=1DoWhilei=n若d(i)=key,则表示找到,做相应处理i=i+1Loop若in表示未找到必考+加试·信息技术4.顺序查找的程序实现在n个数组元素中依次查找,找到第1个满足条件的值,查找即结束,输出找到元素所在的位置;若找不到,输出“未找到”。程序实现:设:(1)要查找的数据是key(在文本框Text1中输入),查找的数据存放在数组d中。(2)pos为找到数的位置,pos=0表示未找到。(3)p记录查找的次数。key=Val(Text1.Text)′Val要根据实际情况决定是否要添加p=0pos=0必考+加试·信息技术find=False′find=False表示未找到,find=True表示找到i=1DoWhilei=nAndfind=False′表示还没找完并且还未找到,则继续查找,notfind也可表示为find=Falsep=p+1Ifkey=d(i)Thenpos=ifind=TrueEndIfi=i+1LoopIffindThen′也可表示为Iffind=TrueThenText2.Text=在d(+Str(pos)+)中ElseText2.Text=未找到EndIf必考+加试·信息技术【典例1】某查找算法的部分VB代码如下:t=Falsei=0DoWhilei7Andt=Falsei=i+1Ifa(i)=keyThent=TrueLoopIft=FalseTheni=0数组元素a(1)到a(7)的数据依次为“3,5,1,5,8,9,5”,当变量key值为5时,运用该算法处理后,变量i的值是()A.0B.2C.4D.7必考+加试·信息技术解析:本题主要考查的是顺序查找的实现过程。本程序的功能是查找数组中第一个与目标数据相等的数,若找到将其在数组中的位置赋给变量i,结束查找;若找不到,变量i=0。因为目标值key=5,它和数组中第二个数正好相等,因此i=2。答案:B必考+加试·信息技术【典例2】(2017·浙江省4月选考)小王编写了一个实现文字查找替换功能的VB程序,运行界面如图4-3-1所示。文本框Text1显示原文内容,Text2中输入查找内容,Text3中输入替换内容,单击“全部替换”按钮Command1后,Text4显示查找替换的结果,Text5中显示替换的次数,Text6显示“查找内容”在原文中的起始位置。必考+加试·信息技术实现上述功能的VB程序如下,但加框处代码有错,请改正。PrivateSubCommand1_Click()DimsAsString,resuleAsString,posAsStringDimcountAsInteger,iAsIntegeri=1:count=0resule=:pos=DoWhilei=Len(Text1.Text)s=Mid(Text1.Text,i,Len(Text2.Text))Ifs=Text2.TextThenresult=result+Text3.Textcount=count+1pos=pos+Str(count)′(1)必考+加试·信息技术i=i+Len(Text2.Text)Elseresult=result+Text2.Text′(2)i=i+1EndIfLoopText4.Text=resultText5.Text=Str(count)Text6.Text=posEndSub必考+加试·信息技术解析:本题利用顺序查找算法实现查找替换的功能。语句“Ifs=Text2.TextThen”表示在原文中找到了所要的查找内容时的情况,此时需要做的是:①将查找内容用替换内容代替(result=result+Text3.Text);②替换次数计数(count=count+1);③记录起始位置i(pos=pos+Str(i),添加在字符串pos中);④查找位置从当前位置前进Len(Text1.Text)个位置(i=i+Len(Text1.Text))。否则,将当前位置上的字符添加到字符串result中,因此(2)处语句修改为result=result+mid(Text1.Text,i,1)。答案:(1)pos+Str(i)(2)result=result+mid(Text1.Text,i,1)必考+加试·信息技术【典例3】某8位男生的肺活量数据放在数组元素a(1)到a(8)中,其数据依次为“3104,3700,3058,3222,3621,3329,4233,4540”。使用顺序查找算法查找数据3339,则共需查找次数为()A.0B.1C.8D.9解析:本题考查的是顺序查找算法的实现过程。由于给定的数列中没有数据3339,因此需要与数列中每个数进行比较,全部比较完后才知道查找失败,因此共需查找次数为8次。答案:C必考+加试·信息技术考点2对分查找1.对分查找的基本思想在有序的数据序列中(一般存放在数组中),首先把要查找的数据与数组中间位置的元素进行比较,如果相等,则查找成功并退出查找;否则,根据数组元素的有序性,确定数据应在数组的前半部分还是在后半部分查找;在确定了新的查找范围后,重复进行以上比较,直到找到或未找到为止。重难点剖析①对分查找的前提是被查找的数据序列必须是有序。②“未找到”是指当指定范围内的起点大于终点仍未找到该数据。必考+加试·信息技术2.对分查找算法基本框架说明:要查找的数为key,待查找的数存放在数组d中。i为查找范围的起点,j为查找范围的终点,m为范围[i,j]的中间位置。i=1j=nDoWhilei=j计算中点位置m比较key与d(m),并做相应处理Loop若ij,则表示未找到必考+加试·信息技术3.对分查找程序实现在n个数组元素中依次查找,找到第1个满足条件的值,查找就结束,输出找到元素所在的位置;若找不到,输出“未找到”。程序实现:设要查找的数据是key(在文本框Text1中输入),查找的数据存放在数组d中。在文本框Text2中输出查找结果,若找到输出“找到!位置为:X”,否则输出“未找到!”在文本框Text3中输出共查找的次数。p表示查找的次数。核心代码为(以升序为例):key=Val(Text1.Text)′表示要查找的数p=0′表示查找的次数必考+加试·信息技术find=False′查找的结果,若find=True表示找到,find=False表示未找到i=1′查找范围的起点j=n′查找范围的终点DoWhilei=jAndNotfind′如果还未找完并且未找到p=p+1′查找次数计数m=(i+j)\2′计算中点位置mIfkey=d(m)Then′表示找到的情况find=TrueText2.Text=找到!位置为:+Str(m)必考+加试·信息技术EndIfIfkeyd(m)Then′表示查找的数比中间位置上的数大时i=m+1Else′表示查找的数比中间位置上的数小时j=m-1EndIfLoopIfNotfindThenText2.Text=未找到!Text3.Text=共查找的次数为:+Str(p)重难点剖析计算中点位置的语句还可以写成:m=Int((i+j)/2)或m=Fix((i+j)/2)。必考+加试·信息技术解析:本题主要考查的是对分查找算法。在[0,1]区间内查找一个数,第一次取[0,1]区间中间值0.5,每次都减少为原来的1/2,所以答案为D。答案:D【典例4】已知单调函数在[0,1]区间存在一个x0,使f(x0)=0。现用对分查找算法搜索x0的值,开始搜索区间为[0,1],若经过10次对分查找后还需继续搜索,则第11次搜索区间的长度为()A.1/2B.1/10C.1/102D.1/210必考+加试·信息技术【典例5】(2017·浙江11月选考)某算法的VB程序段如下:i=1:j=7:s=key=Int(Rnd*100)DoWhilei=jm=(i+j)\2Ifkey=a(m)Thens=s+M:ExitDo′ExitDo表示退出循环ElseIfkeya(m)Thenj=m-1:s=s+LElsei=m+1:s=s+R必考+加试·信息技术EndIfLoopText1.Text=s数组元素a(1)到a(7)的值依次为“24,35,38,41,45,69,78”。若该程序段执行后,文本框Text1中显示的内容可能是()A.RLB.LMRC.RLRD.LRLMC解析:本题主要考查的是对分查找算法。查找的结果有成功和不成功两种,若查找成功,则最后输出M,如果查找不成功,则不会出现M,因此M不可能出现在中间,故B选项错误。对n个数据查找,最多查找次数为log2n+1(向下取整),7个元素最多查找3次,因此可排除D选项。如果查找失败,则需要查找3次,即不可能查找2次就结束,因此A选项也错误。故答案为C。必考+加试·信息技术【典例6】(2017·浙江省4月选考)某对分查找算法的VB程序段如下:Key=Val(Text1.Text)i=1:j=10Text2.Text=DoWhilei=jm=Int((i+j)/2+0.5)IfKey=a(m)ThenExitDo′ExitDo表示退出循环IfKeya(m)Thenj=m-1Elsei=m+1Text2.Text=Text2.Text+Str(a(m))Loop数组元素a(1)到a(10)的值依次为“8,17,24,30,36,40,55,58,61,66”,文本框Text1中输入的值是30,执行该程序段,文本框Text2中显示的是()A.4024B.402436C.3624D.361724必考+加试·信息技术解析:本题主要考查对分查找代码执行过程。具体查找过程如表所示:Key=30由此可知,共查找了4次,最后一次满足Key=a(m),执行ExitDo退出循环,其他几次的a(m)按次序依次显示在Text2中。答案:B查找次数ijm=Int((i+j)/2+0.5)a(m)比较结果1110640Keya(m)215324Keya(m)345536Keya(m)444430Key=a(m)必考+加试·信息技术【典例7】小明编写了一个查询学生的选考组合的VB程序。程序运行时,在列表框List1中显示所有学生的选考组合信息,在文本框Text1中输入学号,单击“开始查询”按钮(Command1),就开始查找该学号,如果找到,则在标签Label4中显示此学号对应的学生姓名和选考组合;如果没有找到,则显示信息“找不到此学号!”。程序的运行效果如图4-3-2所示。必考+加试·信息技术说明:(1)共有n名学生,其学号、姓名和选考组合信息分别存储在数组a,b,c中。(2)数据已按学生学号从小到大排列,第i个学生的学号保存在a(i),对应的姓名保存在b(i),选考组合保存在c(i)。实现上述功能的VB程序如下,在程序划线处填入适当的代码,把程序补充完整。DimnAsInteger′考生数Dima(1000)AsString,b(1000)AsString,c(1000)AsStringPrivateSubForm_Load()′此过程用于输入n个学生的学号、姓名和选考组合,并分别存储在数组a、b、c中′对学生信息按学号升序排序′将学生信息显示在列表框List1中必考+加试·信息技术′代码略EndSubP