5.4数据查找 学案 - 浙教版2019 高中 信息技术 选修1 学案

5.4数据查找 导学案 学科 高中信息技术 教材版本 浙教版2019选修1 课题 5.4数据查找 一、【学习目标】 1.理解顺序查找、二分查找的思想。（重点）（学科核心素养：信息意识、计算思维） 2.合理选用数据结构，理解顺序查找、二分查找的范围与条件。（难点）（学科核心素养：信息意识、计算思维） 3.能用自然语言、流程图、Python语言描述顺序查找算法、二分查找算法。 二、【自主探究】 任务一：学生自主学习课本，完成下列题目： 1.常见的查找算法有 和 。顺序查找又称 ，从顺序表的一端开始，依次将每个元素的关键字与给定值key（查找键）进行比较。若某个元素的关键字等于key，则表明查找成功；若所有元素都比较完毕仍找不到，则表明查找失败。 2.二分查找（Binary Search）又称 、对分查找。它是一种效率很高的查找方法， 但被查找的数据序列必须是 。 任务二：顺序查找、二分查找对比 查找对象 顺序查找 二分查找 效率 最少查找次数 最多查找次数 平均查找次数 任务三：(1)若一个班级一共有45人，查找成功最好情况是比较几次？最差呢？若查找不成功，需要比较几次？ （2）若有N个数据，那顺序查找的平均比较次为几次？ 3、 课后练习题 1. 给定任意的查找键，在序列3,5,8,12,15,23中进行数据查找，下列说法不正确的是 ( ) A.若用顺序查找实现，则最少查找1次 B.若用二分查找实现，则最少查找1次 C.若用顺序查找实现，则最多查找6次 D.若用二分查找实现，则最多查找4次 2. 在7个有序的数列“1，2，3，4，5，6，7” 中，采用二分查找数值key，依次需要进行比较的数据可能是( ) A.4 B.4，6，2 C.4，2，5 D.4，6，5，7 3. 某查找算法的Python 程序如下： key=int(input()) s=0 a=[3,5,8,10,5,6,9,5,36,35] for i in range(len(a)): if a[i]==key: s=s+1 print(s) 程序运行后，输入key的值为5,输出的结果是 ( ) A.1 B.2 C.3 D.4 4.某Python程序如下： a=[3,5,8,11,13,15,16,20,25,30] i.j,x=0,9,20 while i<=j: m=(i+j)//2 if x==a[m]: break if x<a[m]: j=m- 1 else: i=m+1 程序运行后，下列表达式的值为True的是 A.i==m+1 B.j=m-1 C.j>m+1 D.i==m- 1 5.某二分查找算法的Python程序如下： a=[125,117,115,108,102,95,88,63,51,36] key=108 i,j=0,len(a)- 1 ss="" while i<=j: m=int(i+j)/2+0.5) ss=ss+str(m) if key==a[m]: break if key<a[m]: i=m+1 ss=ss+">>"! else: j=m- 1 ss=ss+"<<" print(ss) 程序运行后，输出的结果是 A.4<<1>>2>>3 B.5<<2<<4>>3 C.5<<2>>4<<3 D.5<<2>>4>>3 课后练习答案 1 2 3 4 5 D A D C C 原创精品资源学科网独家享有版权，侵权必究！6 学科网（北京）股份有限公司 $$