5.4查找算法的程序实现.docx

二叉树在对分查找中的应用班级：_姓名：_一、对分查找二叉树的性质性质1：从每节点出发，往左走数字_，往右走数字_。性质2：每个节点为每次计算的m值。m、i、j的关系是什么？若存在左子树，最左边的结点序号就是_，若不存在，就是_。若存在右子树，最右边的结点序号就是_，若不存在，就是_。性质3：如果数据找不到，m、i、j的关系是什么？若往左走出，则_；若往右走出，则_。性质4：每个数所在的_，就是对分查找需要的_；如果找不到，最后走出的_就是_。二、课堂练习（）【多选】如下对分查找程序：i = 1: j = 10: nx = 0Key = Int(Rnd * 100) + 0.5Do 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 IfLoopText1.Text = Str(nx)已经数组元素a(1)到a(10)分别为“11,26,37,49,55,62,78,79,85,98”，按照该程序执行后，Text1中的内容不可能的数字有A-4B-3C-2D-1E0F1G2H3I4（）对数组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 = 23Do 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 + 1LoopAi = 5Bj = 4Cm = 3Dp = 2（）（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中输入的值是30，执行该程序段，文本框Text2中显示的是A4024B402436C3624D361724三、课后练习（）（2017年11月选考）某算法VB程序段如下：i = 1: j = 7: s = Key = Int(Rnd * 100)Do While i = j m = (i + j) 2 If Key = a(m) Then s = s + M: Exit Do Exit Do表示退出循环 ElseIf Key a(m) Then j = m - 1: s = s + L Else i = m + 1: s = s + R End IfLoopText1.Text = s数组a(1)到a(7)的值依次为“24,35,38,41,45,69,78”，执行该程序段后，文本框Text1显示的内容可能是ARLBLMRCRLRDLRLM（）（2018年3月绍兴卷）某对分查找算法如下：Key = Val(Text1.Text) : Text2.Text = flag = Truei = 1: j = 8Do While i a(m) Then i = m + 1 Else j = m - 1 End If Text2.Text = Text2.Text + Str(m)Loop数组a(1)到a(8)的值依次为“1,3,5,8,10,13,16,21”，在Text1中输入7，执行该程序段，下列说法正确的是Aflag值为falseB文本框Text2中显示内容为“4 2 3”Ci值为3Dj值为4（）（2018年9月宁波卷）数组a中依次存放6个有序数据“23,33,44,55,66,77”。Dim a(1 To 10) As Integer, s As String, n As Integer, key As Integera(1) = 23: a(2) = 33: a(3) = 44: a(4) = 55: a(5) = 66: a(6) = 77i = 1: j = 6: c = 0: key = 35Do While i = j c = c + 1 m = (i + j) 2 If (j - i + 1) 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 + 1Loop该程序段运行后，下列各变量的值不正确的是Ai = 3Bj = 2Cc = 3Dm = 2（）（2018年1月杭州高三统考卷）对分查找自定义函数search()的VB程序段如下：Function search(key As Integer) As String Dim pos As Integer, i As Integer, j As Integer, nc As String i = 1: j = 6: nc = Do While i = j m = Int(i + j) / 2) nc = nc + Str(m) If d(m) = key Then Exit Do ElseIf key d(m) Then j = m - 1 Else i = m + 1 End If Loop search = ncEnd Function数组元素d(1)到d(6)的值依次为“23,34,45,65,78,98”，下列说法正确的是。A调用函数search(25)的返回值为字符串“3,2”B调用函数search(34)的返回值为字符串“45,32”C调用函数search(56)的返回值为字符串“3,5,4”D调用函数search(98)的返回值为字符串“45,78,98”（）（2016年10月选考）某对分査找算法的VB程序段如下：i = 1: j = 9: n = 0key = Val(Text1.Text)Do While i = j n = n + 1 m = Fix(i + j) / 2) If key = d(m) Then Exit Do If key d(m) Then j = m - 1 Else i = m + 1Loop数组元素d(1)到d(9)的值依次为“7,12,18,25,39,58,61,72,86”。若该程序段运行结束后，n的值为2，则key的值是。A39B18或61C18或72D12或61（）（2018年8月温州卷）有如下VB程序段：i = 1: j = 10: flag = True: n = 0key = Val(Text1.Text)Do While i key Then i = m + 1: n = n - 1 Else j = m - 1: n = n + 1 End IfLoop数组元素a(1)到a(10)依次是“99,94,90,87,70,69,60,56,45,36”，变量n的值最终是0，则文本框Text1输入的数字可能是A100B87C69D41（）某对分查找算法的VB程序段如下：t = : i = 0: j = 9: Key = 62: f = FalseDo While i Key Then i = m + 1 t = t + Else j = m - 1 t = t + End IfLoop数组元素a(0)到a(9)的值依次为“99,94,90,87,78,70,63,56,45,36”，执行该程序段，t的值是A475B4756C4756D475（）某对分查找算法的VB程序段如下：n = 0: i = 1: j = 6Key = Val(Text1.Text)Do While i d(m) Then j = m - 1 Else i = m + 1LoopIf i = j Then s = Str(m - n) Else s = Str(n)d(1)到d(6)的值依次为“88,77,53,47,39,28”，输入某个Key值后，运行该程序段后，变量s结果为1，则输入key的值是A89B77C47D39（）某对分找算法的VB程序段如下：i = 1: j = 7: n = 0: f = FalseKey = Val(Text1.Text)Do While i = j And f = False n = n + 1 m = Fix(i + j) / 2) If Key = d(m) Then f = True If Key d(m) Then j = m - 1 Else i = m + 1Loop元素d到d(7)的值依次“10,20,30,40,50,60,70”。文本框Text1中输入35后运行程序段，运行束后下列说法正确的是A变量f值TrueB变量i值4C变量m值3.5D变量n值4（）某对分查找算法的VB程序段如下：c = 0: i = 1: j = 8: f = FalseKey = Val(Text1.Text)Do While i d(m) Then j = m - 1 Else i = m + 1 End IfLoop数组元素d(1)到d(8)的值依次为“97,79,68,48,35,23,18,10”，若运行该程序段后，c的值为2，则Text1中输入的值是A68或18B68或23C79或23D79或18（）某对分查找算法的VB程序段如下：i = 1: