专题八 查找算法的程序实现 【考纲标准】 考试内容 考试要求 查找算法的程序实现： ①顺序查找 ②对分查找 C 1．(2018·11月浙江选考)数组a中存储的是左右交替上升的n个正整数，如下表所示： a(1) a(2) a(3) …… a(n－2) a(n－1) a(n) 3 25 38 …… 55 31 12 依据对分查找思想，设计一个在数组a中查找数据key的程序。实现该功能的VB程序如下，但加框处代码有错，请改正。 End If End Sub 解析 本题考核对分查找的思想，算法比较简单，关键是对数组a中存储的是左右交替上升的n个正整数的理解，数组的前半部分是递增的，后半部分是递减的，且他们的大小变化规律是3→12→25→31→38→55。因此如果在前半部分找不到，还可能在右半部分对称的位置找到。因此(1)应修改为i<＝j，也就是说最后一次查找，变量i＝j＝m。如果在前半部分找不到，该数可能比a(m)小，此时j＝m－1，该数大于(j)但小于a(m)，在与j对称的位置(即n－j＋1)可能是要找的数；该数可能比a(m)大，此时i＝m＋1，该数大于a(m)但小于a(i)，在与(i－1)对称的位置(即n－(i－1)＋1)可能是要找的数。 答案 (1)i＜＝j (2)n－i＋2 或n－j＋1 或n＋1－(i＋j) 2．(2018·11月浙江选考)数组a为一组正整数，奇数在前，偶数在后。奇数与偶数已分别按升序排序。依据对分查找思想：设计一个在数组a中查找数据Key的程序。实现该功能的VB程序段如下： i ＝ 1: j ＝ 10 Key ＝ Val(Text1.Text) Do While i <＝ j m ＝ (i ＋ j) 2 If a(m) ＝ Key Then Exit Do ′Exit Do表示退出循环 If Key Mod 2 ＝ 1 And a(m) Mod 2 ＝ 0 Then ElseIf Key Mod 2 ＝ 0 And a(m) Mod 2 ＝ 1 Then Else End If Loop If i > j Then s ＝ “没有找到！” Else s ＝“位置：” ＋ Str(m) Text2.Text ＝ s 上述程序中方框处可选语句为： ①i ＝ m ＋ 1 ②j ＝ m － 1 ③If Key < a(m) Then j ＝ m － 1 Else i ＝ m ＋ 1 则(1)、(2)、(3)处语句依次是( ) A．①、②、③ B．①、③、② C．②、①、③ D．③、②、① 解析 本题考核对分查找算法。语句Key Mod 2 ＝ 1 And a(m) Mod 2 ＝ 0表示要查找的key是奇数，且m指向的数是偶数。奇数在前，向前找，移动尾指针。语句Key Mod 2 ＝ 0 And a(m) Mod 2 ＝ 1表示要查找的key是偶数，且m指向的数是奇数。 答案 C 3．(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
