高中信息技术选修1：算法与程序设计 5.4 查找算法的程序实现 说课一等奖

二叉树在对分查找中的应用玉环中学林巍【多选】如下对分查找程序：i=1:j=10:nx=0Key=Int(Rnd*100)+0.5DoWhilei<=jm=(i+j)\2IfKey=a(m)ThenExitDoElseIfKey<a(m)Thenj=m-1:nx=nx-1Elsei=m+1:nx=nx+1EndIfLoopText1.Text=Str(nx)已经数组元素a(1)到a(10)分别为“11,26,37,49,55,62,78,79,85,98”，按照该程序执行后，Text1中的内容不可能的数字有（）A．-4

B．-3

C．-2

D．-1

E．0F．1

G．2

H．3

I．4典型题对分查找模型Key=Val(Text1.Text)i=1:j=10:s=""DoWhilei<=jm=(i+j)\2IfKey=a(m)ThenExitDo'ExitDo表示退出循环ElseIfKey<a(m)Thenj=m-1Elsei=m+1EndIfs=s+Str(a(m))Loop二叉树的概念在计算机科学中，二叉树是每个节点最多有两个子树的树结构。根结点：最上面的结点叶子结点：没有子结点的结点二叉树的子树有左右之分建树——对分查找模型Key=Val(Text1.Text)i=1:j=10:s=""DoWhilei<=jm=(i+j)\2IfKey=a(m)ThenExitDo'ExitDo表示退出循环ElseIfKey<a(m)Thenj=m-1Elsei=m+1EndIfs=s+Str(a(m))Loop建树key=Val(Text1.Text)i=1:j=10Text2.Text=""DoWhilei<=jm=Int((i+j)/2+0.5)Ifkey=a(m)ThenExitDoIfkey<a(m)Thenj=m-1Elsei=m+1Text2.Text=Text2.Text+Str(a(m))Loop第3题探究二叉树的性质性质1：从每节点出发，往左走数字______，往右走数字______。性质2：每个节点为每次计算的m值。m、i、j的关系是什么？若存在左子树，最左边的结点序号就是______，若不存在，就是______。若存在右子树，最右边的结点序号就是______，若不存在，就是______。性质3：如果数据找不到，m、i、j的关系是什么？若往左走出，则__________若往右走出，则__________变大变小i值m值j值m值j=m-1i=m+1探究二叉树的性质性质4：每个数所在的______，就是对分查找需要的______；如果找不到，最后走出的__________就是__________。层数次数结点层数查找次数【多选】如下对分查找程序：i=1:j=10:nx=0Key=Int(Rnd*100)+0.5DoWhilei<=jm=(i+j)\2IfKey=a(m)ThenExitDoElseIfKey<a(m)Thenj=m-1:nx=nx-1Elsei=m+1:nx=nx+1EndIfLoopText1.Text=Str(nx)已经数组元素a(1)到a(10)分别为“11,26,37,49,55,62,78,79,85,98”，按照该程序执行后，Text1中的内容不可能的数字有（）A．-4

B．-3

C．-2

D．-1

E．0F．1

G．2

H．3

I．4解决问题1第1题解决问题2对数组a中6个有序数据“11,22,33,44,55,66”，用下面的程序代码查找数据“23”，程序执行完毕后，下列各变量值正确的是a(1)=11:a(2)=22:a(3)=33:a(4)=44:a(5)=55:a(6)=66i=1:j=6:p=0:Key=23DoWhilei<=jp=p+1m=(i+j)\2IfjMod2=0Thenm=m+1Ifa(m)=KeyThenExitDoIfKey<a(m)Thenj=m-1Elsei=m+1LoopA．i=5 B．j=4 C．m=3 D．p=2第2题解决问题3（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表示退出循环Ifkey<a(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．4024 B．402436 C．3624 D．361724第3