高中信息技术选修1《查找算法的程序实现》ppt课件(浙教版)

二叉树在对分查找中的应用 玉环中学 林巍 【多选】如下对分查找程序： i = 1: j = 10: nx = 0 Key = Int(Rnd * 100) + 0.5 Do While i <= j m = (i + j) \ 2 If Key = a(m) Then Exit Do ElseIf Key < a(m) Then j = m - 1: nx = nx - 1 Else i = m + 1: nx = nx + 1 End If Loop Text1.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．0 F．1　　G．2　　H．3　　I．4 典型题 对分查找模型 Key = Val(Text1.Text) i = 1: j = 10 : s = "" Do While i <= j m = (i + j) \ 2 If Key = a(m) Then Exit Do 'Exit Do表示退出循环 ElseIf Key < a(m) Then j = m - 1 Else i = m + 1 End If s = s + Str(a(m)) Loop 二叉树的概念 在计算机科学中，二叉树是每个节点最多有两个子树的树结构。 根结点：最上面的结点 叶子结点：没有子结点的结点 二叉树的子树有左右之分 建树———对分查找模型 Key = Val(Text1.Text) i = 1: j = 10 : s = "" Do While i <= j m = (i + j) \ 2 If Key = a(m) Then Exit Do 'Exit Do表示退出循环 ElseIf Key < a(m) Then j = m - 1 Else i = m + 1 End If s = s + Str(a(m)) Loop 建树 key = Val(Text1.Text) i = 1: j = 10 Text2.Text = "" Do While i <= j m = Int((i + j) / 2 + 0.5) 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 第3题 探究二叉树的性质 性质1：从每节点出发，往左走数字_____，往右走数字_____。 性质2：每个节点为每次计算的m值。m、i、j的关系是什么？ 若存在左子树，最左边的结点序号就是_____，若不存在，就是_____。 若存在右子树，最右边的结点序号就是_____，若不存在，就是_____。 性质3：如果数据找不到，m、i、j的关系是什么？ 若往左走出，则_____ 若往右走出，则_____ 变大 变小 i值 m值 j值 m值 j=m-1 i=m+1 探究二叉树的性质 性质4：每个数所在的_____，就是对分查找需要的_____；如果找不到，最后走出的_____就是_____。 层数 次数 结点层数 查找次数 【多选】如下对分查找程序： i = 1: j = 10: nx = 0 Key = Int(Rnd * 100) + 0.5 Do While i <= j m = (i + j) \ 2 If Key = a(m) Then Exit Do ElseIf Key < a(m) Then j = m - 1: nx = nx - 1 Else i = m + 1: nx = nx + 1 End If Loop Text1.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．0 F．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) = 66 i = 1: j = 6: p = 0: Key = 23 Do While i <= j p = p + 1 m = (i + j) \ 2 If j Mod 2 = 0 Then m = m + 1 If a(m) = Key Then Exit Do If Key < a(m) Then j = m - 1 Else i = m + 1 Loop A．i = 5 B．j = 4 C．m = 3 D．p = 2 第2题 解决问题3 （2017年4月选考）某对分查找算法的VB程序段如下： key = Val(Text1.Text) i = 1: j = 10 Text2.Text = "" Do While i <= j m = Int((i + j) / 2 + 0.5) If key = a(m) Then Exit Do 'Exit Do表示退出循环 If key < a(m) Then j = m - 1 Else i = m + 1 Text2.Text = Text2.Text + Str(a(m)) Loop 数组元素a(1)到a(10)的值依次为“8,17,24,30,36,40,55,58,61,66”，文本框Text1中输 ... ...