5.4 对分查找程序实现 导学案 -2021-2022学年高中信息技术浙教版选修1

| 5页
| 273人阅读
| 71人下载
普通

高二信息技术导学案    VB模块   班级            姓名               

《对分查找程序实现》导学案

[考试要求]

1.对分查找算法思想      (c)

2.对分查找程序实现        (c)

[学习目标]

1. 对比顺序查找,掌握对分查找的算法思想。

2. 分解对分查找的算法思想,构建对分查找的代码

3. 充分解读和理解对分查找的程序代码     

[自主学习]

一、 知识梳理

1、  思想:首先将查找的数与          (有序/无序)数组内处于       位置的数据比较,如果中间位置上的数与查找的数不同,则根据有序性,确定应该在数组的前半部分还是后半部分继续查找。在新确定的范围内,继续按上述方法,直到获得最终结果。

2、  特点:①要求被查找数据必须           。

      ②查找效率         ,适用于大数据查找。

二、自我检测

1.在一个有序数据序列中,采用对分查找算法查找,则下面说法正确的是(    )

  A.对分查找算法的数据,必须是降序数列

  B.对分查找算法的数据,必须是升序数列

  C.对分查找算法的查找速度一定比顺序查找算法快

  D.对n个数采用对分查找算法的最多次数是log2n次

2.数组变量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

3.某电视台有一档与观众互动的猪物品价格的节目,让观众采用对分查找的算法在1- 1000元内进行竞猜,如某件物品价格为250元,则此价格被猜中至少需要的次数是(    )

  A.1             B.2                 C.3                     D.4

4.在有序数组内进行对分查找,如果中间位置上的元素内的数值大于查找键值,而接下来的查找范围确定在数组的后半部分测数组的排序方式为(    )

  A升序           B.降序              C.无序                  D.无法确定

5.7位学生的身高(单位:cm)从高到低依次为:178,177,175,172,170,165,162。用对分查找法找到178所需要的查找次数是(    )

  A.1             B.2                 C.3                     D.4

6.对22个记录的有序表作对分查找,当查找失败时,至少需要比较多少次关键字(    )

  A.3             B.4                C.5                     D.6

 [课堂练习]

1.某数组的6个元素依次为“27,32,57,78,80,90”。若对该数组进行顺序查找,其平均查找次数为(1+2+3+4+5+6) /6=7/2:若对该数组进行对分查找,其平均查找次数为(    )

  A.7/2           B.  7/3             C.5/2                   D. 2

2.在已排序的数组d(数组元素d(1)≥d(2)≥…≥d(n))中查找键值为key的数,其对分查找的VB程序段如下:

  i=1:j= n

  xb= O

  Do Whilei <=j

m=Fix((i+j)/2)

If d(m) = Key Then

   xb = m

   Exit Dopage number 0


高二信息技术导学案    VB模块   班级            姓名               

End lf

If         Tlren

  j =m -1

Else

  i=m+1

End if

Loop

划线处的语句为(    )

A. key>d(m)       B. key<d( m)      C. key<>d(m)           D. key=d(m)

3.有10个数据:83、80、66、46、44、36、21、16、15、12依次存放在数组元素a(1)到a(10)中,部分VB程序段如下所示:

key = Val(Text1.Text)

i = 1: j = 10: Text2.Text = ""

Do While i <= j

m = (i + j+ 1) \2

If key = a(m) Then Exit Do

If key >a(m) Then j = m-1 Else i = m+1

Text2.Text = Text2.Text + Str(a(m))

Loop

文本框Text1中输入80,执行该程序段,文本框Text2中显示的是(    )

A. 36 66          B. 44 80           C. 36 46               D.44 66

4.某对分查找算法的VB程序段如下:

i=1:j=8:c=0

Do While i<=j

    c=c+l

    m= Fix((i+j)/2)

    If key=b(m) Then Exit Do

If key<b(m) Then j=m-l Else i=m+l

Loop

数组元素b(l)到b(8)的值依次为“22,32,39,48,71,82,96,106”。若该程序段运行结束后,c的值为2,则key的值是(    )

A.48或32           B.48或96         C.32或82             D.82或96

 

[课后练习]

1.己知一元二次函数f(x)=在区间[0,1]之间必定存在着一个极大点x0,使f(x0)达到最大值。现用对分查找算法搜索x0的值,开始搜索区间为[O,1],在搜索到第n次时找到x0,已知第n次搜索区间的长度是1/32,则n的值是(  )  

A.3              B.4               C.5                    D.6

2.下列VB程序段功能为:在降序排序数组a中(a(1)≥a(2)≥…≥a(n))查找文本框Text1中输入的数据,若能找到,则输出该数在数组a中第一次出现的位置,否则输出“找不到”。

key= Val(Textl.Text)

i=1:j=n

Do While i <j

    m=(i+j)\2

    lf      ①   Then

       i=m+1

    Else

         ②    

    End lfpage number 1


由于学科网是一个信息分享及获取的平台,不确保部分用户上传资料的 来源及知识产权归属。如您发现相关资料侵犯您的合法权益,请联系学科网,我们核实后将及时进行处理。