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

《2019浙江选考信息技术查找算法专题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、知识点(一)顺序查找1．顺序查找算法①顺序查找算法的处理过程假定在数组d中有n个数据，查找关键值已经存储在变量key中。其处理过程是：从数组d的第1个元素d(1)开始，依次判断各元素的值是否与key相等，若某个数组元素d(i)的值等于key，则结束处理(找到了指定的数据)；若找遍了所有的n个元素，无任何元素的值等于key，则结束处理(输出未找到信息)。②顺序查找算法流程图与程序结构2.程序实现代码：(二)对分查找1.对分查找的过程若key为查找键，数组d存放n个已按升序排序的数据。在使用对分查找时，把查找范围[i，j]的中间位置上的数据d(m)与查找关键值key进行比较，结果必然是如下三种情

2、况之一：(1)若keyd(m)，由与(1)相同的理由，必须在新的范围(m＋1，j)中继续查找。这样，除了出现情况(2)，在通过一次比较后，新的查找范围将不超过上次查找范围的一半。以规模为16的递增数组d为例，观察对分查找的过程。要查找的数据key为37。知识点使用流程图描述对分查找的算法如下图所示：2．对分查找算法程序的实现PrivateSubCommand1_Click()i＝

3、1:j＝nDoWhilei<＝jm＝(i＋j)2Ifd(m)＝KeyThen'输出结果，退出查找(代码略)ElseIfKey

4、据需要的查找次数+…+第n个数据需要的查找次数）/n而使用顺序查找算法，在最坏的情况下(查找键在最后一个或没找到)，需要进行n次查找，最好的情况是一次查找(查找键在第一个)，平均查找次数是。真题再现1、（2018.4）数组a为一组正整数，奇数在前，偶数在后。奇数与偶数已分别按升序排序。依据对分查找思想：设计一个在数组a中查找数据Key的程序。实现该功能的VB程序段如下：i=1:j=10Key=Val(Text1.Text)DoWhilei<=jm=(i+j)2Ifa(m)=KeyThenExitDo'ExitDo表示退出循环IfKeyMod2=1Anda(m)Mod2=0Then（1）El

5、seIfKeyMod2=0Anda(m)Mod2=1Then（2）Else（3）EndIfLoopIfi>jThens="没有找到！"Elses="位置："+Str(m)Text2.Text=s上述程序中方框处可选语句为：①i=m+1②j=m-1③IfKey

6、Do'ExitDo表示退出循环ElseIfkey

7、退出循环Ifkey