资源简介

专题八　查找算法的程序实现
【考纲标准】
考试内容
考试要求
查找算法的程序实现：
①顺序查找
②对分查找
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　j＝m－1：s＝s＋”L”
Else
　 i＝m＋1：s＝s＋”R”
End If
Loop
Text1.Text＝s
数组元素a(1)到a(7)的值依次为“24，35，38，41，45，69，78”。执行该程序段后，文本框Text1中显示内容可能的是(　　)
A．RL B．LMR C．RLR D．LRLM
解析　找到的情况下，显示M并停止查找，因此B选项是不可能的。7个数据，在找不到的情况下，至少查找的次数是Int(Log27)＋1＝3，因此A选项还需继续查找。D选项的查找次数超过了3次。第一次找到41，向右找，找到69，向左找，找到45，再向右找，没有找到，该数在(45，69)之间。
答案　C
一、顺序查找
1．查找是一种查询数据的技术，其目标是能以比较少的步骤或较短的时间找到所需的对象。
2．顺序查找是在一个已知无(或有序)序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从第一个开始逐个比较，直到找出与给定关键字相同的数为止。
3．由于该部分在前面的几个专题均有练习，本专题不做专题讲述。
二、对分查找
(一)基本算法思想
在一个升序或降序的数组中，确定该数组的开始位置i、结束位置j和中间位置m，用待查找的数key与m位置所在的值d(m)比较，如果相等，表示找到了，如果在前半段，把结束位置j修改为m－1，重新查找，如果在后半段，把开始位置i修改为m＋1，再次查找，直到找到或者开始位置大于结束位置为止。
中间位置m的计算公式：m＝Int((i＋j)/2)或者m＝(i＋j) 2或者m＝fix((i＋j)/2)。
(二)核心代码
1．在升序的数列d(1)至d(n)中查找key。用i表示开始位置下标，用j表示结束位置下标，m表示中间位置下标。若找到，输出该数据所在位置pos.如果pos＝0表示没有找到。
pos ＝ 0: c ＝ 0: i ＝ 1: j ＝ n
Do While i<＝j　 ′进入查找的条件，i与j的关系
　m ＝ Int((i＋j)/2)
　c ＝ c ＋ 1 　 ′表示查找次数
　If d(m) ＝ Key Then
pos ＝ m　　　′找到，用xb记录下标位置
Exit Do　　　　　′退出循环
　ElseIf Key < d(m) Then
　 j ＝ m － 1
　Else
　 i ＝ m ＋ 1
　End If
Loop
If pos＝0 Then
Text2.Text ＝“找不到”
Else
Text2.Text ＝“在数组中位置为” ＋ Str(pos) ＋“共查找了” ＋ Str(c) ＋“次”
End If
2．关于头尾指针移动有两种IF结构
If d(m) ＝ Key Then
　pos ＝ m　 ′记录下标位置
　Exit Do　　′退出循环
ElseIf Key < d(m) Then
　j ＝ m － 1
Else
　i ＝ m ＋ 1
End If
If d(m) ＝ Key Then
　pos ＝ m　　　 ′下标位置
　Exit Do　　　　′退出循环
Else
　If Key < d(m) Then
　　j ＝ m － 1
　Else
　　i ＝ m ＋ 1
　End If
End If
3.根据pos变量的值判断结果，如果pos＝0，表示没有找到，否则输出查找位置pos。
4．根据循环结束后变量i的值判断结果，如果没有找到，头指针i将移动到尾指针j的后面，即i>j；否则在中间位置找到，使用Exit DO语句中途退出，此时变量m表示查找位置。
(三)查找过程
1．明确i、j和m的含义，i表示开始位置，j表示结束位置，m表示[i，j]的中间位置。d(m)表示m这个位置所对应的数值。
2．修改i、j的值，如果是升序系列，当要查找的数比中间的数d(m)小，表示要查找的数在前半段，让j＝m－1；否则在后半段，让i＝m＋1。如果是降序系列，则相反。
3．结束查找有两个条件，中间m位置值d(m)与要查找的数key相等，或者是头指针i已经大于尾指针j。满足其中一个，就不再查找了。
4．查找结束后，查找的结论是要查找的数在数组中位置m或者没有找到。
(四)N个数最多的查找次数
N个数最多的查找次数最多的查找次数为Int(Log2N)＋1。
(五)常用解题技巧
1．列表法
用表格列出每次查找的区间和比较数的位置及值。
2．二叉树法
假设有10个数据1、2、3、4、5、6、7、8、9、10
②右 2 堆依次求出m值(2、8)，m 值保留在原位，然后把 2 边数分别放入它的左右2 个子树(小的放左子树，大的放右子树)；
③节点里还有 2 个及以上数的，按照上面规则求 m 值，m 值保留在原位，其他数放入它的左右 2 个子树(小的放左子树，大的放右子树)；
④有左子树的往左画条线，代表往左查找失败的范围；没有右子树的往右画条线，代表往右查找失败的范围。
【例1】 某对分查找算法的 VB 程序段如下：
i＝1: j＝6: n＝0: f＝False：key＝Val(Text1.Text)
Do While i<＝j and Not f
　n＝n＋1
m＝Fix((i＋j)/2)
If key＝a(m) Then f＝True
If keyLoop
数组元素 a(1)到 a(6)的值依次为“12，19，27，31，46，55”。文本框Text1中输入“30”后运行该程序，则以上程序段运行结束后，下列说法不正确的是(　　)
A．变量 i 的值为 4 B．变量 j 的值为 5　
C．变量 m 的值为 4 D．变量 n 的值为 3
解析　本题考核的知识点是对分查找。可以用列表法进行跟踪变量。
i
j
m
a(m)
n
flag
1
6
3
27
1
False
4
6
5
46
2
False
4
4
4
31
3
False
4
3
当i>j时，不再查找。
答案　B
【变式训练1】 某对分查找算法的 VB 程序段如下：
i＝1: j＝6: n＝0: f＝False：key＝Val(Text1.Text)
Do While i<＝j and Not f
n＝n＋1
m＝Fix((i＋j)/2)
If key＝a(m) then f＝True
If keyLoop
数组元素 a(1)到 a(6)的值依次为“12，19，27，31，46，55”。文本框 Text1 中输入“31”后运行该程序，则以上程序段运行结束后，下列说法不正确的是(　　)
A．变量 i 的值为 4 B．变量 j 的值为 5　
C．变量 m 的值为 4 D．变量 n 的值为 3
解析　采用列表法进行分析。
i
j
m
a(m)
f
n
1
6
3
27
False
1
4
6
5
46
False
2
4
4
4
31
True
3
答案　B
【例2】 一组“非降序”的数据分别存储在数组元素a(1)……a(n)中，用对分查找算法在数组a中查找key值所在位置，如果有重复的元素，则显示最小的位置。部分VB程序如下：
Key＝Val(Text1.Text)
i＝1: j＝n
Do While i <＝ j
　 m＝(i ＋ j) 2
　 If a(m) > Key Then
　 j＝m － 1
　 Elseif a(m) < Key Then
i＝m ＋ 1
　 Else
　 　 If__________Then
j＝m － 1
　 　 Else
Label2.Caption＝Str(Key) ＋“的起始位置是” ＋ Str(m): Exit Do
　 End If
End If
Loop
If i > j Then Label2.Caption＝“找不到” ＋ Str(Key)
要使程序实现上述算法思想，则划线处的语句为(　　)
A．a(m－1)＝key
B．a(m)＝key
C．m－1>0 and a(m－1)＝key
D．m－1>0 and a(m)＝key
解析　要求如果有重复的元素，则显示最小的位置。即m不是第1个元素且a(m－1)＝key时，将尾指针移到m的前一个位置，继续查找。同时如果要取最后一个相同的数值。
答案　C
【变式训练2】 某对分查找算法的VB程序段如下：
L＝1: R＝10: Key＝21
Do While L <＝ R
m＝(L ＋ R) 2
If a(m) <＝ Key Then　 L＝m ＋ 1　Else　R＝m － 1
Loop
数组元素a(1)到a(10)的值依次为3，9，21，21，21，21，27，28，39，40，执行该程序段，变量R、a(R)的值分别是(　　)
A．2，9 B．3，21 C．6，21 D．7，27
解析　采用列表法进行分析。
L
R
m
a(m)
a(m) <＝ Key？
1
10
5
21
True
6
10
8
28
False
6
7
6
21
True
7
7
7
27
False
7
6
可见此时R指向的位置就是要查找的元素。
答案　C
【例3】 某对分査找算法的VB程序段如下：
Key＝Int (Rnd*100)
i＝1: j＝7 ：s＝" "
Do While i <＝ j
m＝(i ＋ j) 2
If Key＝a(m) Then s＝s ＋ “M”： Exit Do
If Key < a(m) Then
j＝m － 1 : s＝s ＋ “L”
Else
i＝m ＋ 1 : s＝s ＋ “R”
End If
Loop
Text1.Text＝sText1.Text ＝s
数组元素a(1)到a(7)的值依次为“25，36，39，42，47，66，78”，执行该程序段，文本框Text1中显示的内容是“RLR”，则可以确定随机产生的Key值范围是(　　)
A．(25，36) B．(47，66)
C．(66，78) D．(78，100)
解析　画出对应的二叉树图如右图所示，其中圈中所示数字均为元素在数组中位置。
第一次查找，m的值为4，程序运行时，文本框Text1中显示的内容是“RLR”，即从第4个元素开始，进行向右、向左、向右查找，且没有出现M，说明要找的数没找到。向右查找，M的值为6，再向左查找，M的值为5，若要再向右找，应比第5个数大，比较第6个数小，因此答案为B。若显示RLL，即最后一次向左查找，应比第5个数小，但比第4个数大，Key的范围是(42，47)。
答案　B
【变式训练3】 若数组元素d(1)到d(8)的值依次为“92，88，71，64，43，28，5，2”，查找某Key值的VB程序段如下：
n＝0 : i＝1 : j＝8 ：Key＝Val(Text1.Text)
Do While i <＝ j
　m＝(i ＋ j) 2　　　　　　　
　If Key＝d(m) Then　Exit Do　 ′Exit Do表示退出循环
　If Key > d(m) Then
　 j＝m － 1 : n＝n － 1
　Else
i＝m ＋ 1 : n＝n ＋ 1
　End If
Loop
Label1.Caption＝Str(n)
当输入不同的Key值，运行该程序段后，在标签Label1中显示的不同结果共有(　　)
A．5种 B．6种 C．7种 D．8种
解析　画出8个数据的二叉树图，可见查找的次数最多是4次，即当M分别为4、6、7、8时，还没有找到，该数可能是第7、8之间的数，也可能是大于第8个数。
在程序代码中，如果在左边区域中继续查找，n＝n－1，在右边区域中继续查找，n＝n＋1。当n＝0，可能的结果是，找到第4、3、5个数。当n＝－1时，找到第2个数，当n＝－2时，找到第1个数，当n＝－3时，在数组中找不到该数，该数比第1个数小的数。当n＝1时，找到第6个数，也可能是在数组中找不到该数，该数比第3个数大。当n＝2时找到第7个数，当n＝3时，找到第8个数，当n＝4时，在数组中找不到该数，该数比第8个数大。
答案　D
一、选择题
1．某对分査找算法的VB程序段如下：
i ＝ 1: j ＝ 9: n ＝ 0
key ＝ Val(Text1.Text)
Do While i <＝ j
n ＝ n ＋ 1
m ＝ Fix((i ＋ j) / 2)
If key ＝ d(m) Then Exit Do　′Exit Do表示退出循环
Ifkey < d(m) Then j ＝ m － 1 Else i ＝ m ＋ 1
Loop
数组元素d(1)到d(9)的值依次为“7，12，18，25，39，58，61，72，86”。若该程序段运行结束后，n的值为2，则key的值是(　　)
A．39 B．18或61 C．18或72 D．12或61
解析　变量n表示循环次数，即查找次数，因此表示查找2次的key值。第1次d(m)＝39，第二次可能向前找，找到12。如果向后找，找到61。
答案　D
2．某公司的员工管理系统中有1200条员工记录(每条员工记录已按员工编号升序排序)，现用对分查找法搜索一员工信息，开始搜索的记录范围为1200条，若第5次对分查找后还需继续搜索，则第6次搜索的记录范围内的记录数为(　　)
A．18 B．19 C．36 D．75
解析　假设key的值较小，要一直往前找。
查找次数
i
j
m
1
1
1 200
600
2
1
599
300
3
1
299
150
4
1
149
75
5
1
74
37
6
1
36
答案　C
3．在10000条有序记录集中查找，没有找到相应的记录，则至少查找的次数为(　　)
A．13 B．14 C．15 D．10000
解析　对分查找要求数组有序，效率较高，至少需要Int(log2n)＋1次。210＝1024，211＝2048，212＝4096，213＝8192，因此log210000在[13，14]之间，取整＋1＝14。
答案　B
4．某对分查找算法的VB程序段如下：
flag＝False
i＝0: j＝7: c＝0
Do While i <＝ j And flag＝False
m＝Fix((i＋j)/2＋0.5)
If Key＝a(m) Then flag＝True
If Keyc＝c ＋ 1
Loop
数组元素a(0)到a(7)的值依次为“1，3，30，46，69，72，84，90”，key的值为85.若该程序段执行后，以下说法中正确的是(　　)
A．i＝6 B．j＝7 C．m＝7 D．c＝4
解析　本题中取中点m的计算方法不一样，属于四舍五入计算中点，且数组的下标从0开始。
i
j
m
a(m)
c
0
7
4
69
1
5
7
6
84
2
7
7
7
90
3
7
6
答案　C
5．某查找算法的部分VB程序代码如下：
i＝1∶j＝8∶k＝0
key＝95
Do While i＜＝j
　k＝k＋1
　m＝Int((i＋j)/2)
　If key＝a(m)　Then Exit Do
　If key＜a(m)　Then j＝m－1 Else i＝m＋1
Loop
数组元素a(1)到a(8)的数据依次为“12，28，49，56，67，88，95，100”，该程序运行过程中，当变量k的值为2时，对应查找的a(m)值是(　　)
A．28 B．56 C．88 D．95
解析　变量k用于记录查找次数，当k＝2时对应查找的a(m)即第2次访问的数据。第1次访问a(4)，第2次访问a(6) 。也可以用画二叉树的方法进行解题。查找2次，应在二叉树的第二层中，且要向右查找，因此是第6个数据。
答案　C
6．已知一无序数组A中的元素为“90，15，40，72，65，32，81，6”通过引入数组a元素按升序排列时的下标，b数组元素为“8，2，6，3，5，4，7，1”，使得a(b(1))<＝ a(b(2))<＝ a(b(3))……<＝ a(b(n))，从而对数组a中的数据进行对分查找。部分程序如下：
i＝1: j＝8: c＝0
Key＝Val(text1.Text)
Do While i <＝ j
m＝Int((i ＋ j) / 2)
t＝b(m)
c＝c ＋ 1
If a(t)＝Key Then p＝t: Exit Do
If a(t) < Key Then
　i＝m ＋ 1
　Else
　 j＝m － 1
　End If
Loop
当文本框Text1中输入的值为32时，程序运行结束后变量c的值是(　　)
A．1 B．2 C．3 D．4
解析　在数组a(b(1))、a(b(2))、a(b(3)) ……a(b(n))，即a(8)a(2)a(6)a(3) ……a(1)，对数组a中数据进行升序排列。要查找的数在第1个位置，从二叉树中可知要查找3次。
答案　C
7．已知数组元素a(1)到a(8)的值依次为89，78，67，56，45，34，23，12，若在Text1中输入12，然后执行以下程序段：
Key ＝ Val(Text1.Text)
Text2.Text ＝”　　”
i ＝ 1: j ＝ 8: f ＝ False
Do While i <＝ j And Not f
m ＝ (i ＋ j) 2
A．56　78　67 B．4　6　5
C．4　2　3 D．56　34　45
解析　考查二分查找算法。本题查找两位数的有序数列a(1)到a(8)，查找满足十位数和个位数上的数字之和为12的数(数列应按十位数和个位数上的数字之和有序排列，否则查找结果可能会出错)。Text2中显示的是查找过程中依次访问到的数据a(m)中的下标m ，第1次访问的是a(4), 第2次访问的是a(2), 第3次访问的是a(3) 。
答案　C
8．把学生成绩由高到低排序之后，按姓名在前、成绩在后的顺序依次存储在数组a中，例如(“张三”，“97”，“李四”，“92”，“王五”，“87”……)设计一个VB程序，利用对分查找实现在数组a中查找成绩为Key的学生姓名。程序段如下：
i＝1: j＝n：Key＝Val(Text1.Text)
Do While i <＝ j
m＝____①____
If Val(a(m))>Key Then i＝m
Loop
j＝j ＋ 1
Do While j <＝ n
If Val(a(2 * j))＝Key Then
　List1.AddItem a(2*j－1)＋”　”＋a(2*j)
Else
Exit Do
End If
j＝j ＋ 1
Loop
划线处应该填的语句是(　　)
A．(i＋j)2 B.(i＋j)/2
C．((i＋j)2)*2 D.((i＋j)2/2
解析　以5名学生成绩为例，有如下的位置(1，2)，(3，4)，(5，6)，(7，9)，(9，10)，当i＝1，j＝10时，m取值为6；当i＝1，j＝4，m取值为2。成绩所在下标是他在数组中第几位置再乘以2。
答案　C
9．某对分查找算法的VB程序段如下：
i＝1: j＝8: t＝0
Key＝Int(Rnd() * 18) ＋ 4
Do While i <＝ j
m＝Int((i ＋ j) / 2)
t＝t ＋ 1
If a(m)＝Key Then
　　 Exit Do
　Else
　　 If a(m) > Key Then j＝m － 1 Else i＝m ＋ 1
　End If
Loop
数组元素a(1)到a(8)的值依次为“2，3，12，15，18，19，20，22”，该程序段运行结束后，变量t达到最大值时的Key值可能是(　　)
A．5 B．18 C．21 D．23
解析　Key值的范围是[4，21]。上述对分查找用二叉树表示为
查找小于第7个结点前的数据，最多只需查找3次，即4－20之间数据最多只需查找3次。若查找的数据是21，则需查找4次。
答案　C
10．程序段如下所示：
i＝1 : j＝10 : flag＝True
n＝0 ：Key＝Val(Text1.Text)
Do While i <＝ j And flag＝True
　m＝(i ＋ j) '2
　If a(m)＝Key Then
　flag＝False
　Elseif a(m)> Key Then
i＝m ＋ 1 : n＝n － 1
　Else
j＝m － 1 : n＝n ＋ 1
　End If
Loop
数组元素a(1)到a(10)依次是99, 94, 90, 87, 70，69，60，56，45，36，变量n的值最终是0，则文本框Text1输入的数字可能是(　　)
A．100 B．87 C．69 D．41
解析　对分查找用二叉树表示为
从图中可以看出，找到第5个、第3个或第6个数据，n的值为0。
答案　C
11．数组a为一组循环有序不重复的数组，如(a(1)＝26，a(2)＝41，a(3)＝100，a(4)＝5，a(5)＝7，a(6)＝9)。依据对分查找思想：设计一个在数组a中查找数据Key并显示在列表框的程序，界面如图所示。实现该功能的VB程序段如下：
1＝1：r＝6
Key＝Val(Text1.Text)
Do While l <＝ r
　 m＝Int((l ＋ r) '2)
　 If a(m)＝Key Then

　 Exit Do
　 ElseIf a(m) >＝ a(l) Then

ElseIf a(m) < a(l) Then
　 End If
Loop
上述程序中方框处可选语句为：
① If a(m) < Key And a(r) >＝ Key Then l＝m ＋ 1 Else r＝m － 1
② List1.AddItem “第”＋ Str(m) ＋ ” 值是 ” ＋ Str(a(m))
③ If a(m) > Key And a(l) <＝ Key Then r＝m － 1 Else l＝m ＋ 1
则(1)、(2)、(3)处语句依次是(　　)
A．③①② B．②①③ C．①③② D．②③①
解析　当条件a(m)＝Key成立时，表示已经找到，因此要进行输出，即选②语句。当条件a(m) >＝ a(l)条件成立，表示当前m指向的是在前半段升序数据中，再进行检测要查找的数据是否在前半段中，即是否满足条件a(l)<＝Key，移动尾指针，继续在前半段区间中查找，否则在后半段区间中查找。当条件a(m)＝Key表示他处在后半个升序区间中，移动首指针，继续查找。
答案　D
12．某程序代码如下：
解析　把查找的区间用3个节点(mid1、mid2、mid3)分成4段，如果等于节点，退出查找，否则判断属于哪个区间，再继续查找。第1次查找，分成[1，25]，[26，50]，[51，76]，[77，100]四个区间，11在第1区间，在[1，10]之间。
i
j
mid1
mid2
mid3
n
1
100
25
50
76
1
1
24
6
12
19
2
7
11
8
9
10
3
11
11
11
11
11
4
答案　D
13．某对分査找算法的 VB 程序段如下：
Dim d(1 To 63) As Integer, i As Integer, s As Integer
For i＝1 To 63
d(i)＝i
Next i
Key＝Int(Rnd * 63) ＋ 1
s＝0: i＝1: j＝63
Do While i <＝ j
m＝(i ＋ j) 2
If Key＝d(m) Then Exit Do　′Exit Do 表示退出循环
If Key < d(m) Then
j＝m － 1: s＝2 * s
Else
i＝m ＋ 1: s＝2 * s ＋ 1
End If
Loop
若运行该程序段后，标签 Label1 中显示的结果是 28，则查找的 key 值是(　　)
A．28 B．29 C．57 D．58
解析　s的值若要得到28，则可以倒着推算，s的值应分别28、14、7、3、1，最后一次找到了，退出循环，没有计算s的值，共查找了6次，63个数，最多的查找次数为6次。在查找过程中，向右查找，s的值为奇数，向左查找为偶数。因此查找过程中，分别访问的数据为32、48、56、60、58、57。
答案　C
二、非选择题
14．编写VB程序，实现如下功能：在文本框Text1中输整数x，单击“查找删除”按钮Command1，在数组a(从小到大排列并显示在标签Label1中)中查找该数。若找到，则从数组a中删除该数(该数后的数组元素都往前移一位)，并在标签Label2中显示删除后的结果(运行效果如图所示)；否则在标签Label2中显示“该数没有找到”。
请在划线处填入合适代码。
Dim a(1 To 10) As Integer
Private Sub Form_Load()
　′产生10个升序的随机数并显示在Label1，代码略
End Sub
Private Sub Command1_Click()
Dim i As Integer, j As Integer, m As Integer, k As Integer
Dim x As Integer, f As Boolean, s As String
x ＝ Val(Text1.Text)
i ＝ 1: j ＝ 10: f ＝ False
Do While ____①____
m ＝ (i ＋ j) 2
If a(m) ＝ x Then
f ＝ True
ElseIf ____②____Then
　i ＝ m ＋ 1
Else
　j ＝ m － 1
End If
Loop
If f ＝ True Then
For k ＝ m To 9　
　____③______
Next k
For k ＝ 1 To 9　　　′逐个显示删除后的数组元素
s ＝ s ＋ Str(a(k)) ＋ ” ”
Next k
Else
s ＝ ”该数没有找到”
End If
Label2.Caption ＝ s
End Sub
解析　这是一个典型的对分查找算法，由于找到该数，程序中没有ExitDo语句，因此条件需要两个。找到以后，到m位置的数用后面的数替换，并只显示9个数。
答案　①i <＝ j And f ＝ False　②a(m)< x　③a(k) ＝ a(k ＋ 1)
15．编写VB程序，实现如下功能：在左边的文本框Text1中输入字符串，单击“加密”按钮Command1时，逐个字符进行加密，加密过程是：先在“加密表”m中找到相应字符，再得到其所对应位置的密钥Text3(下方)，并在右边的文本框Text2中显示密文，运行效果如图所示。本题不考虑解密问题。
实现上述功能的VB代码如下：
(1)如图所示，若将Text3中的密钥改为：“I.am.a.good.student.from.Zhejiang”(不含双引号)，文本框Text1中依然输入“zjks”，单击“加密”按钮Command1，则在文本框Text2中显示的是________。
(2)请在划线处填入合适代码。
Private Sub Command1_Click()
Dim s As String ，m As String
Dim t As String
s1 ＝ Len(Text3.Text)
If s1 < 26 Then
　 Text2.Text ＝”请重新输入密钥！”
　 Exit Sub
End If
s ＝ Text1.Text
n ＝ Len(s)
For i ＝ 1 To n
k ＝ Mid(s, i, 1)
m ＝ ”abcdefghijklmnopqrstuvwxyz”
a ＝ 1: b ＝ 26
Do While a <＝ b
　 c ＝ ____①____
　 If k ＝ Mid(m, c, 1) Then　
　　　Exit Do
　 End If
　 If ____②____Then
　　　b ＝ c － 1
　 Else
　　　a ＝ c ＋ 1
　 End If
Loop
s3 ＝ Text3.Text
t ＝ t ＋ ____③____
Next i
Text2.Text ＝ t
End Sub
解析　本题综合考查加密及对分查找算法。(1)按照加密算法，按位置逐个翻译出密码，其结果是Zodt。
(2)①本题使用对分查找算法确定c(也即是密码对应的位置)的值，c相当于m，a是i，b就是j，所以c＝(a＋b)
答案　(1)Zodt　(2)①int((a＋b)/2)或(a＋b)
16．对分查找算法可用于求解方程的近似解。现要求方程x3－4x2＋x＋5＝0的一个近似解，可设f(x)＝x3－4x2＋x＋5，若有区间[a，b]，使f(a)与f(b)异号，则该区间内必存在该方程的一个解。小吴为此编写了VB程序，功能如下：分别在文本框Text1和Text2中输入求解的区间值a和b(a实现上述功能的VB程序如下，请在划线处填上合适的代码。
Private Sub Command1_Click()
Dim a As Double, b As Double, m As Double, x As Double
Dim ym As Double, yb As Double
a ＝ Val(Text1.Text): b ＝ Val(Text2.Text)
If a > b Then t ＝ a: a ＝ b: b ＝ t
Do While____①____
m ＝ (a ＋ b) / 2
ym ＝ m ^ 3 － 4 * m ^ 2 ＋ m ＋ 5
yb ＝ b ^ 3 － 4 * b ^ 2 ＋ b ＋ 5
If Abs(ym) < 0.00001 Then Exit Do
If ____②____ Then
b ＝ m
　Else
a ＝ m
　End If
Loop
Text3.Text ＝ Str(Int(m * 10000) / 10000)
End Sub
解析　求解出该区间内的一个近似解(精确到10－5)，因此Abs(ym) < 0.00001时就表示找到了。查找的条件是头指针小于或等于尾指针。当b对应的值yb大于0时，表示在x轴的上方，将b＝m。
答案　①a<＝b　②yb*ym>0
17．如图 a 所示，已有若干学生从 1 开始编号，在文本框 Text1 中输入新增的学生姓名，填补到空缺的学号(2、3、6、11)位置。填补规则：从最小号开始依次填补。单击“新增”按钮后在列表框List1中完整显示所有学生信息，如图b所示。
实现上述功能的VB代码如下，但加框处有错，请改正。
Dim n As Integer ′学生人数
Dim a(1 To 100) As Integer ′存储学生的学号
Dim b(1 To 100) As String ′存储学生的姓名
Private Sub Form_Load()
′从数据库中读取学生学号、学生姓名和总人数，分别存储在数组 a、数组 b 和变量 n 中，代码略。
End Sub
Private Sub Command1_Click()
Dim L As Integer, R As Integer
Dim m As Integer, key as String
key ＝ Text1.Text
L ＝ 1: R ＝ n
Do While L <＝ R
m ＝ (L ＋ R) '2
If Then　　 ′(1)
　 L ＝ m ＋ 1
Else
　R ＝ m － 1
End If
Loop
For i ＝ 　　 ′(2)
a(i ＋ 1) ＝ a(i)
b(i ＋ 1) ＝ b(i)
Next i
n ＝ n ＋ 1
a(i＋1) ＝ L
b(i＋1) ＝ Key
′插入后的结果显示在列表框 List2，代码略。
End Sub
解析　从语句a(i＋1) ＝ L来看，L是存放插入值的位置，当m下标对应的数组元素比m小，说明前面还有空的序号。
答案　(1)a(m)＝m 或a(m)<＝m　(2)n To L Step －1
18．查找最接近的数。编写一个查找最接近数的 VB 程序：程序运行时，在文本框 Text1 中输入产生随机数的个数(1到100之间)，单击命令按钮“产生随机数并升序排列”后，在列表框List1中显示已经按升序排列后的随机整数。然后在文本框Text2中输入要查找的整数，单击命令按钮“查找”后，在标签Label3 中显示随机整数序列中与待查找数最接近的整数(当最接近的数有2个时，输出较大的一个)。程序运行效果如图所示。实现上述功能的VB代码如下，请在划线处填入合适代码。
Dim n As Integer　′存储随机数的个数
Dim f(1 To 100) As Boolean′　f(i)为true 时表示随机整数i已经产生过
Dim a(1 To 100) As Integer ′依次存放升序排序后的n个随机数
Private Sub Command1_Click()　　　′命令按钮”产生随机数并升序排列”的单击事件
Dim i As Integer
Randomize
For i ＝ 1 To 100
f(i) ＝ False
Next i
n ＝ Val(Text1.Text)
For i ＝ 1 To n
t ＝ Int(Rnd * 100 ＋ 1)
Do While f(t) ＝ True
t ＝ Int(Rnd * 100 ＋ 1)
Loop
____①____
Next i
j ＝ 0
For i ＝ 1 To 100　′实现排序并输出
If f(i) ＝ True Then
j＝j＋1
a(j) ＝ ____②____
List1.AddItem Str(i)
End If
Next i
End Sub
Private Sub Command2_Click()　　　　′命令按钮”查找”的单击事件
Dim key As Integer
key ＝ Val(Text2.Text)
If key <＝ a(1) Then Label3.Caption ＝ Str(a(1)): Exit Sub
If key >＝ a(n) Then Label3.Caption ＝ Str(a(n)): Exit Sub
L ＝ 1: R ＝ n
Do While L <＝ R　　 ′找到与key较为接近的两个数a(R)和a(L)
解析　数组f表示是否已经产生该下标数的标志，当f(t) ＝ True条件成立时，重新产生一个新的t，直到该数没有产生过。一旦该数t产生时，f数组中，t下标的数组元素值为True。
在a(R)和a(L)中选出更接近key的数，就是a(R)和a(L)与key差绝对值较小的数。
答案　①f(t) ＝ True　②i　③Abs(a(R) － Key) < abc(a(L) － Key)
19．数组a中存储的是一组正整数，特征是：①以三个数为一组的话，每组中任意一个数都比前面一组中的任意一个数要大；②每组中三个数依次递减；③数组中数的总个数为3的倍数。依据对分查找思想，设计一个在数组a中查找数据key的程序。实现该功能的VB程序如下，但加框处代码有错，请改正。
Private Sub Command1_Click()
Const n＝15
Dim a(1 To n) As Integer, search As Integer, key As Integer
Dim i As Integer, j As Integer, m As Integer
′读取一组正整数，按上述规则存入数组a中，代码略。
key＝Val(Text1.Text)
i＝1: j＝n: search＝0
Do While i <＝ j
m＝(i ＋ j) 2
If m Mod 3 <> 0 Then m＝m － 2 ′(1)
把m调整到三个一组的最后一个数的位置
If key＝a(m) Then
search＝m: Exit Do
ElseIf key < a(m) Then
j＝m － 3
ElseIf key <＝ a(m － 2) Then ′(2)
i＝m ＋ 1
ElseIf key＝a(m － 2) Then
search＝m － 2: Exit Do
ElseIf key＝a(m － 1) Then
search＝m － 1: Exit Do
Else
search＝0: Exit Do
End If
Loop
If search <> 0 Then
Text2.Text＝Str(search)
Else
Text2.Text＝”找不到”
End If
End Sub
解析　条件m Mod 3 <> 0成立 ，m Mod 3＝1或等于2，等于1时，需要往后推2个位置，等于2时，需要往后推1个位置，把m调整到三个一组的最后一个数的位置。满足key < a(m － 2)时，i＝m ＋ 1。
答案　(1)m－(3－m Mod 3)　 (2)key < a(m － 2)
20．“轮转后有序数组(RotatedSortedArray)”是将有序数组取其中某一个数为分割点，将其之前的所有数都轮转到数组的末尾所得。比如{7，11，13，17，2，3，5}就是一个轮转后的有序数组，原有序数组中的子串{2，3，5}被轮转到了数组的末尾处。
对于一个轮转后有序数组arr也可以进行二分查找，算法思路如下(以升序为例)：
每次根据查找的左侧位置L和右侧位置R求出中间位置M后，M左边[L，M]和右边[M＋1，R]，这两部分中至少一个是有序的(可根据中间位置数据和边界数据的大小关系判断)。
arr[M]和待查找数据Key比较
①arr[M]＝Key，返回M的值
②若M位置的右侧有序，当待查找数据在右侧，则下次在右侧查找，否则在M左侧查找
③若M位置的左侧有序，当待查找数据在左侧，则下次在左侧查找，否则在M右侧查找
(1)对于轮转后有序数组{7，11，13，17，2，3，5}使用以上函数search()查找key值3，所需要的查找次数为__________。
(2)以下VB函数Search( )实现了对轮转后有序数组arr进行二分查找的过程，如果查询成功，返回m值，查询失败则返回－1。 请补充程序中①②③划线处的代码：
Function Search(key As Integer, L As Integer, R As Integer) As Integer
______①____
Do While L <＝ R And Search ＝ －1
M ＝ (L ＋ R) '2
If arr(M) ＝ key Then
Search ＝ M
Else
If____②____Then
　　　　 If arr(L)<＝key And key　　　　　 　R ＝ M － 1
　　　　Else
　　　 　　　L ＝ M ＋ 1
　　　　 End If
Else
　　　　 If____③____ Then
　　　　　　L ＝ M ＋ 1
　　　　Else
　　　　　　R ＝ M － 1
　　　 　End If
End If
End If
Loop
End Function
解析　(1)第 1 次查找到的数据是 17，第 2 次就可以查找到 3。
(2)①对返回值的赋值，在循环条件中，满足条件。
②条件arr(L)<＝ key And key < arr(M)满足，继续在左侧查找，因此该处要判断M在左侧。根据对分查找的对称性填③空，同时结合 L＝M＋1 可知在右侧有序的情况下往右侧继续查找。
答案　(1)2　(2)①Search ＝ －1　②a(M)>a(R)
③a(M)21．小李编写了一个成语接龙的VB程序，功能如下：在文本框Text1中输入一个成语，单击“接龙”按钮Command1，在列表框List1中显示接龙的成语。程序运行界面如下图所示。
实现上述功能的VB程序如下，但加框处代码有错，请改正。
Dim n As Integer, cy(30000) As String
Private Sub Form_Load()
′从数据库中读入n条成语，并存入数组cy中
′代码略
End Sub
Private Sub Command1_Click()
Dim s As String, i As Integer, j As Integer
Dim m As Integer, flag As Boolean
Dim s1 As String, s2 As String
s ＝ Text1.Text
flag ＝ True
Do While flag
　　 ′(1)
i ＝ 1
j ＝ n
Do While i <＝ j
m ＝ Int((i ＋ j) / 2)
s2 ＝ Mid(cy(m), 1, 1)
If s2 ＝ s1 Then
　 　　　Exit Do
ElseIf s2 < s1 Then
　 　　　i ＝ m ＋ 1
Else
　　　 　j ＝ m － 1
End If
Loop
If Then　　 ′(2)
List1.AddItem s ＋ ”－－” ＋ cy(m)
s ＝ cy(m)
Else
List1.AddItem ”接不下去了”
flag ＝ False
End If
Loop
End Sub
解析　根据输入文字的第一个文字进行查找。如果找到的条件是i <＝ j，因此(2)中应填i＜＝j。
答案　(1)s1 ＝ Mid(s, Len(s), 1)　(2)i <＝ j
课件41张PPT。专题八　查找算法的程序实现【考纲标准】1．(2018·11月浙江选考)数组a中存储的是左右交替上升的n个正整数，如下表所示：依据对分查找思想，设计一个在数组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①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指向的数是奇数。
答案　C3．(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　 j＝m－1：s＝s＋" L"Else
　 i＝m＋1：s＝s＋"R"
End IfLoop
Text1.Text＝s
数组元素a(1)到a(7)的值依次为“24，35，38，41，45，69，78”。执行该程序段后，文本框Text1中显示内容可能的是(　　)
A．RL B．LMR C．RLR D．LRLM解析　找到的情况下，显示M并停止查找，因此B选项是不可能的。7个数据，在找不到的情况下，至少查找的次数是Int(Log27)＋1＝3，因此A选项还需继续查找。D选项的查找次数超过了3次。第一次找到41，向右找，找到69，向左找，找到45，再向右找，没有找到，该数在(45，69)之间。
答案　C一、顺序查找
1．查找是一种查询数据的技术，其目标是能以比较少的步骤或较短的时间找到所需的对象。
2．顺序查找是在一个已知无(或有序)序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从第一个开始逐个比较，直到找出与给定关键字相同的数为止。
3．由于该部分在前面的几个专题均有练习，本专题不做专题讲述。二、对分查找
(一)基本算法思想
在一个升序或降序的数组中，确定该数组的开始位置i、结束位置j和中间位置m，用待查找的数key与m位置所在的值d(m)比较，如果相等，表示找到了，如果在前半段，把结束位置j修改为m－1，重新查找，如果在后半段，把开始位置i修改为m＋1，再次查找，直到找到或者开始位置大于结束位置为止。
中间位置m的计算公式：m＝Int((i＋j)/2)或者m＝(i＋j)2或者m＝fix((i＋j)/2)。(二)核心代码
1．在升序的数列d(1)至d(n)中查找key。用i表示开始位置下标，用j表示结束位置下标，m表示中间位置下标。若找到，输出该数据所在位置pos.如果pos＝0表示没有找到。
pos ＝ 0: c ＝ 0: i ＝ 1: j ＝ n
Do While i<＝j　 ′进入查找的条件，i与j的关系
　m ＝ Int((i＋j)/2)
　c ＝ c ＋ 1 　 ′表示查找次数
　If d(m) ＝ Key Then pos ＝ m　　　′找到，用xb记录下标位置
Exit Do　　　　　′退出循环
　ElseIf Key < d(m) Then
　 j ＝ m － 1
　Else
　i ＝ m ＋ 1
　End If
LoopIf pos＝0 Then
Text2.Text ＝“找不到”
Else
Text2.Text ＝ “在数组中位置为” ＋ Str(pos) ＋ “共查找了” ＋ Str(c) ＋ “次”
End If2．关于头尾指针移动有两种IF结构3.根据pos变量的值判断结果，如果pos＝0，表示没有找到，否则输出查找位置pos。
4．根据循环结束后变量i的值判断结果，如果没有找到，头指针i将移动到尾指针j的后面，即i>j；否则在中间位置找到，使用Exit DO语句中途退出，此时变量m表示查找位置。(三)查找过程
1．明确i、j和m的含义，i表示开始位置，j表示结束位置，m表示[i，j]的中间位置。d(m)表示m这个位置所对应的数值。
2．修改i、j的值，如果是升序系列，当要查找的数比中间的数d(m)小，表示要查找的数在前半段，让j＝m－1；否则在后半段，让i＝m＋1。如果是降序系列，则相反。
3．结束查找有两个条件，中间m位置值d(m)与要查找的数key相等，或者是头指针i已经大于尾指针j。满足其中一个，就不再查找了。
4．查找结束后，查找的结论是要查找的数在数组中位置m或者没有找到。(四)N个数最多的查找次数
N个数最多的查找次数最多的查找次数为Int(Log2N)＋1。
(五)常用解题技巧
1．列表法
用表格列出每次查找的区间和比较数的位置及值。2．二叉树法
假设有10个数据1、2、3、4、5、6、7、8、9、10②右 2 堆依次求出m值(2、8)，m 值保留在原位，然后把 2 边数分别放入它的左右2 个子树(小的放左子树，大的放右子树)；
③节点里还有 2 个及以上数的，按照上面规则求 m 值，m 值保留在原位，其他数放入它的左右 2 个子树(小的放左子树，大的放右子树)；④有左子树的往左画条线，代表往左查找失败的范围；没有右子树的往右画条线，代表往右查找失败的范围。【例1】 某对分查找算法的 VB 程序段如下：i＝1: j＝6: n＝0: f＝False：key＝Val(Text1.Text)
Do While i<＝j and Not f
　n＝n＋1
m＝Fix((i＋j)/2)
If key＝a(m) Then f＝True
If keyLoop数组元素 a(1)到 a(6)的值依次为“12，19，27，31，46，55”。文本框Text1中输入“30”后运行该程序，则以上程序段运行结束后，下列说法不正确的是(　　)
A．变量 i 的值为 4 B．变量 j 的值为 5　
C．变量 m 的值为 4 D．变量 n 的值为 3解析　本题考核的知识点是对分查找。可以用列表法进行跟踪变量。当i>j时，不再查找。
答案　B【变式训练1】 某对分查找算法的 VB 程序段如下：i＝1: j＝6: n＝0: f＝False：key＝Val(Text1.Text)
Do While i<＝j and Not f
n＝n＋1
m＝Fix((i＋j)/2)
If key＝a(m) then f＝True
If keyLoop数组元素 a(1)到 a(6)的值依次为“12，19，27，31，46，55”。文本框 Text1 中输入“31”后运行该程序，则以上程序段运行结束后，下列说法不正确的是(　　)
A．变量 i 的值为 4 B．变量 j 的值为 5　
C．变量 m 的值为 4 D．变量 n 的值为 3解析　采用列表法进行分析。答案　B【例2】 一组“非降序”的数据分别存储在数组元素a(1)……a(n)中，用对分查找算法在数组a中查找key值所在位置，如果有重复的元素，则显示最小的位置。部分VB程序如下：Key＝Val(Text1.Text)
i＝1: j＝n
Do While i <＝ j
　 m＝(i ＋ j) '2
　 If a(m) > Key Then
　 j＝m － 1 　 Elseif a(m) < Key Then
i＝m ＋ 1
　 Else
　 　 If__________Then
j＝m － 1
　 　 Else
Label2.Caption＝Str(Key) ＋ “的起始位置是” ＋ Str(m): Exit Do
　 End If
End If
Loop
If i > j Then Label2.Caption＝ “找不到” ＋ Str(Key)要使程序实现上述算法思想，则划线处的语句为(　　)
A．a(m－1)＝key
B．a(m)＝key
C．m－1>0 and a(m－1)＝key
D．m－1>0 and a(m)＝key
解析　要求如果有重复的元素，则显示最小的位置。即m不是第1个元素且a(m－1)＝key时，将尾指针移到m的前一个位置，继续查找。同时如果要取最后一个相同的数值。
答案　C【变式训练2】 某对分查找算法的VB程序段如下：L＝1: R＝10: Key＝21
Do While L <＝ R
m＝(L ＋ R) 2
If a(m) <＝ Key Then　 L＝m ＋ 1　Else　R＝m － 1
Loop
数组元素a(1)到a(10)的值依次为3，9，21，21，21，21，27，28，39，40，执行该程序段，变量R、a(R)的值分别是(　　)
A．2，9 B．3，21 C．6，21 D．7，27解析　采用列表法进行分析。可见此时R指向的位置就是要查找的元素。
答案　C【例3】 某对分査找算法的VB程序段如下：Key＝Int (Rnd*100)
i＝1: j＝7 ：s＝ " "
Do While i <＝ j
m＝(i ＋ j) 2
If Key＝a(m) Then s＝s ＋ “M”： Exit Do
If Key < a(m) Then
j＝m － 1 : s＝s ＋ “ L”
Elsei＝m ＋ 1 : s＝s ＋ “R”
End If
Loop
Text1.Text＝sText1.Text ＝s
数组元素a(1)到a(7)的值依次为“25，36，39，42，47，66，78”，执行该程序段，文本框Text1中显示的内容是“RLR”，则可以确定随机产生的Key值范围是(　　)
A．(25，36) B．(47，66)
C．(66，78) D．(78，100)解析　画出对应的二叉树图如图所示，其中圈中所示数字均为元素在数组中位置。第一次查找，m的值为4，程序运行时，文本框Text1中显示的内容是 “RLR”，即从第4个元素开始，进行向右、向左、向右查找，且没有出现M，说明要找的数没找到。向右查找，M的值为6，再向左查找，M的值为5，若要再向右找，应比第5个数大，比较第6个数小，因此答案为B。若显示RLL，即最后一次向左查找，应比第5个数小，但比第4个数大，Key的范围是(42，47)。
答案　B【变式训练3】 若数组元素d(1)到d(8)的值依次为“92，88，71，64，43，28，5，2”，查找某Key值的VB程序段如下：n＝0 : i＝1 : j＝8 ：Key＝Val(Text1.Text)
Do While i <＝ j
　m＝(i ＋ j) 2　　　　　　　
　If Key＝d(m) Then　Exit Do　 ′Exit Do表示退出循环　If Key > d(m) Then
　 j＝m － 1 : n＝n － 1
　Else
i＝m ＋ 1 : n＝n ＋ 1
　End If
Loop
Label1.Caption＝Str(n)
当输入不同的Key值，运行该程序段后，在标签Label1中显示的不同结果共有(　　)
A．5种 B．6种 C．7种 D．8种解析　画出8个数据的二叉树图，可见查找的次数最多是4次，即当M分别为4、6、7、8时，还没有找到，该数可能是第7、8之间的数，也可能是大于第8个数。在程序代码中，如果在左边区域中继续查找，n＝n－1，在右边区域中继续查找，n＝n＋1。当n＝0，可能的结果是，找到第4、3、5个数。当n＝－1时，找到第2个数，当n＝－2时，找到第1个数，当n＝－3时，在数组中找不到该数，该数比第1个数小的数。当n＝1时，找到第6个数，也可能是在数组中找不到该数，该数比第3个数大。当n＝2时找到第7个数，当n＝3时，找到第8个数，当n＝4时，在数组中找不到该数，该数比第8个数大。
答案　D

展开更多......

收起↑