教师备用题库
1.有如下VB程序段:
n=Val(Text1.Text)
k=0
left=1
right=n
Do While left <=right
k=k+1
m=(left+right) 2
If m-left < right-m Then
left=m+1
Else
right=m-1
End If
Loop
在文本框Text1中输入16,执行该程序段,下列说法错误的是( )
A.程序运行后k的值是4
B.程序运行后m的值是16
C.程序运行后right的值是15
D.程序运行后left的值是16
答案 A 本题考查对分查找。程序执行过程如下表。
查找次数
left
right
k
m
第1次
1
16
1
8
第2次
9
16
2
12
第3次
13
16
3
14
第4次
15
16
4
15
第5次
16
16
5
16
不能进循环
16
15
2.采用如下对分查找算法对数组a中7个有序数据“about、count、end、fly、high、jack、month”进行查找。
i=1:j=7:x=“high”
Do While i <=j
m=(i+j)2
If a(m)=x Then Exit Do
If a(m) > x Then
j=m-1
Else
i=m+1
End If
Loop
执行完上述代码后,根据最终变量值判断下列表达式,其中成立的是( )
A.i=j B.i=m-1 C.j>m+1 D.j
答案 A 本题考查对分查找算法及其程序的实现。第一次循环结束后,m=4,i=5,j=7;第二次循环结束后,m=6,i=5,j=5;第三次循环结束后,m=5,a(m)=x成立,循环结束。最终m=5,i=5,j=5,所以表达式i=j成立。
3.某高校学籍管理系统软件有2万个学生的电子档案(已按学籍号排序),假设从中取出一条记录并与待查项进行比较所花时间为8毫秒,则用对分法在该系统中查找任意一位学生档案最多花费的时间约为 ( )
A.16万毫秒 B.8万毫秒 C.10毫秒 D.120毫秒
答案 D 在规模为n的数中查找一个数据至多进行Int(log2n)+1次查找就能得到结果。Int(log220000)+1=14+1=15,因此本题中最多查找15次,故最多花费时间为15*8=120毫秒。
4.有如下VB程序段:
a(1)=2: a(2)=6: a(3)=8: a(4)=9: a(5)=12
a(6)=15: a(7)=17: a(8)=18: a(9)=22: a(10)=30
k=Val(Text1.Text)
i=1: j=10
Do While i <=j
m=(i+j) 2
If a(m) <=k Then
i=m+1
Else
j=m-1
End If
Loop
Text2.Text=Str(a(i))+"← →"+Str(a(j))
程序运行时,在文本框Text1中输入5,文本框Text2中显示的内容是( )
A.2← →1 B.6← →8 C.2← →6 D.6← →2
答案 D 本题考查对分查找算法及其实现。第1次循环时,变量i和j的值分别为1,10。第2次循环时,变量i和j的值分别为1,4。第3次循环时,变量i和j的值分别为1,1。第4次循环时,变量i和j的值分别为2,1。Do循环结束,最终输出Str(a(i))+"← →"+Str(a(j)),即Str(a(2))+"← →"+Str(a(1))。所以选D。
5.某对分查找算法的VB程序段如下:
k=Val(Text1.Text)
i=1: j=6: Label1.Caption="": f=False
Do While i <=j And Not f
m=(i+j) 2
If a(m)=k Then f=True
If a(m) > a(i) Then
If a(i) <=k And k < a(m) Then j=m-1 Else i=i+1
Else
If a(m) < k And k <=a(j) Then i=i+1 Else j=j-1
End If
Label1.Caption=Label1.Caption+Str(a(m))
Loop
数组元素a(1)到a(6)的值依次为“58,66,72,24,35,40”,在文本框Text1中输入的值为35,执行该程序段,标签Label1中显示的值是( )
A.72 35 B.24 35 C.72 24 35 D.72 24 24 35
答案 D 本题主要考查对分查找算法知识。根据程序代码模拟运行情况如下:
第一次查找:m=3,a(m)=72,i=2,j=6;
第二次查找:m=4,a(m)=24,i=3,j=6;
第三次查找:m=4,a(m)=24,i=4,j=6;
第四次查找:m=5,a(m)=35,f=True。
此时查找成功,循环结束,查找过的数组元素分别是72 24 24 35,因此D选项正确。注:对分查找只能查找有序序列,但本题的输入的数组序列是无序数列。
6.(2015浙江10月学考+选考,11,2分)已知单调函数f(x)在[0,1]区间存在一个x0,使f(x0)=0。现用对分查找法搜索x0的值,开始搜索区间为[0,1],若经过10次对分查找后还需继续搜索,则第11次搜索区间的长度为( )
A.
1
2
B.
1
10
C.
1
1
0
2
D.
1
2
10
答案 D 本题考查对分查找的查找区间长度。对分查找的主要思想是在一个有序的数据序列中不断地寻找当前区间的“中点”,通过与“中点”元素的比对,决定是在前半部分还是后半部分数据中继续查找,通过不断缩小查找区间以提高查找效率。本题中第一次查找区间为[0,1],其查找区间的长度为1,则第二次查找的区间长度为1/2,第三次查找的区间长度为1/4,依此类推,第11次查找的区间长度为1/210。
7.(2016义乌中学3月选考模拟,17,5分)对于函数f(x),若在某区间[a,b]内是单调函数,且其图像与x轴有交点,则存在一个x0使得f(x0)=0,我们可以设法找到x0的值。
满足上述条件的区间[a,b]和函数f(x)必定有f(a)·f(b)<=0,我们设计如下算法:
第一步:区间中点m=
a+b
2
。
第二步:若f(a)·f(m)<0,则含零点的区间为[a,m];否则,含零点的区间为[m,b],将新得到的含零点的区间仍记为[a,b]。
第三步:判断[a,b]的长度是否小于一个足够小的值d。若是,则m是方程的近似解;否则,返回第一步。
于是我们可以设计函数f(x)=x2-c,就可以用此算法求出任意非负常数c的非负平方根。程序运行效果如下图所示,程序中还输出了区间的左右端点和区间长度值。
/
Const min As Single=0.00005
Dim c As Single
Function fn(x As Single)As Single
① ?
End Function
Private Sub Command1_Click() ??按钮上的程序
Dim a As Single,b As Single,m As Single
c=Val(Text1.Text)a=0
b=c
Do While ② ?
m=(a+b)/2
List1.AddItem Str(a)&“”&Str(b)&“”&Str(b-a)
If ③ Then ?
b=m
Else
a=m
End If
Loop
Label2.Caption=Str(m)
End Sub
回答以下问题:
(1)事件处理过程“Command1_Click()”用到的算法是?
(填算法具体名称)。
(2)请将程序中的三处代码补充完整。
(3)通过测试可知,该程序得到的
2
的近似值为1.4142,实际上更精确的值是1.4142135623731,请问如何改善程序,得到一个更精确的近似值?请写出至少两种改善意见:
? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ?。
答案 (1)对分查找
(2)①fn=x*x-c
②(b-a)>=min(或abs(a-b)>=min,其中没有“=”亦可)
③fn(a)*fn(m)<0或fn(m)>0(有“=”亦可)
(3)把所有single换成double(双精度类型double的有效位数更多);把min的值设置得更小,如0.0000000001;结束条件的区间范围更小
解析 本题主要考查对分查找的算法思想:若函数f(x)在某区间[a,b]内是单调函数,若f(a)和f(b)的值互异,则该区间内必有某个值x0,使得f(x0)=0,则在曲线上体现为必和x轴相交。
程序实现时设计了一个结束条件:[a,b]的长度小于一个足够小的值,题中定义为一个常数:Const min As Single=0.00005,故②处代码含义为:当区间长度大于或者等于min时继续查找。变量m为当前区间[a,b]的中间点,若fn(a)*fn(m)<0,说明零点在区间[a,m]中,故将b的值设为m,否则,说明零点在区间[b,m]中,故将a的值设为m。
第4节 查找算法及程序实现
模拟演练
1.用对分查找从数列“1,5,9,13,16,20,33,40,61,77,89”中查找“5”,一共需要比较的次数为( )
A.2 B.3 C.4 D.5
答案 C 本题主要考查对分查找。对分查找的基本思想:首先将查找键与有序数组内处于中间位置的元素进行比较,如果中间位置上的元素数值与查找键相同,表示找到,否则根据数组元素的有序性,就可确定应该在数组的前半部分还是后半部分继续进行查找。在新确定的范围内,继续按上述方法进行查找,直到获得最终结果。对分查找是一种效率很高的查找方法,但被查找的数据必须是有序的。
若用一个数组d(1)到d(11)来存放升序的元素序列1,5,9,13,16,20,33,40,
61,77,89,查找键key为5。
比较次数
比较范围
mid
key与d(mid)的关系
第一次
d(1)~d(11)
6
key第二次
d(1)~d(5)
3
key第三次
d(1)~d(2)
1
key>d(mid)
第四次
d(2)
2
Key=d(mid)
2.某数组的6个元素依次为“27,32,57,78,80,90”。若对该数组进行顺序查找,其平均查找次数为(1+2+3+4+5+6)/6=7/2;若对该数组进行对分查找,其平均查找次数为( )
A.7/2 B.7/3 C.5/2 D.2
答案 B 本题考查对分查找算法。对该数组进行对分查找,其平均查找次数为(2+3+1+3+2+3)/6=7/3。
3.在数组d(1)到d(10)中存放了以下数据:10,12,17,20,22,27,40,45,50,80。指定关键字为50,对数组进行对分查找,依次所经过的元素为( )
A.22,27,50 B.27,45,50
C.22,45,50 D.22,40,50
答案 C 本题主要考查对分查找的思想方法。第一次找到d(5)=22(中间位置m=Fix((1+10)/2)=5),key=50,key>d(5),因此下一次查找的范围是后半部分,即d(6)到a(10)。第二次找到d(8)=45(中间位置m=Fix((6+10)/2)=8),key>d(8),因此下一次查找的范围是后半部分,即d(9)到d(10)。第三次找到d(9)=50(中间位置m=Fix((9+10)/2)=9),key=d(9),找到了目标。
4.有如下程序段:
Dim i As Integer,j As Integer,Key As Integer,m As Integer,s As String
i=1: j=7: s=“”:flag=False
Key=Int(Rnd()* 50)
Do While i <=j And Not Flag
m=(i+j)2
If Key=a(m) Then
Flag=True
ElseIf Key < a(m) Then
j=m-1
Else
i=m+1
End If
s=s+Str(a(m))
Loop
Text1.Text=s
数组中a(1)到a(7)的值依次为“23,33,45,56,68,77,89”,则Text1 中显示的内容不可能是( )
A.56 33 B.56 33 45 C.56 33 23 D.56 77 68 11
答案 D 此题考查对分查找,因为Key 的值为小于50 的整数,第一次访问的值为56,因此Key<56,所以第二次访问的值一定在前半段,可能是56 33 或56 33 45 或56 33 23,不可能在后半段,即不可能是56 77 68,因此本题答案为D。
5.某对分査找算法的VB程序段如下:
i=1: j=5: k=0: s=""
key=Int(Rnd*100)
Do While i <=j
k=k+1
m=(i+j) 2
s=s+Str(a(i))
If key=a(m) Then
Exit Do ’Exit Do表示退出循环
ElseIf key < a(m) Then
j=m-1
Else
i=m+1
End If
Loop
Text1.Text=s
数组元素a(1)到a(5)的值依次为“6,18,25,37,49”。若该程序段执行后,k的值为3,则key的值不可能为( )
A.4 B.18 C.47 D.55
答案 A 本题属于较难题,考查对分查找算法的思路。本题要点在于对分查找各种情况的判断,由程序可知,key为待查找数据,k表示访问数据的次数。若key=4,则依次访问的数据为“25,6”,k=2;若key=18,则依次访问的数据为“25,6,18”,k=3;若key=47,则依次访问的数据为“25,37,49”,k=3;若key=55,则依次访问的数据为“25,37,49”,k=3。故选项A结果与要求不符。
6.某对分查找算法的VB程序段如下:
n=0:i=l:j=6
key=Val(Text1.Text)
Do While i <=j
m=(i+j) 2
n=n+1
If key=d(m) Then Exit Do
If key > d(m) Then j=m-1 Else i=m+1
Loop
If 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的值是( )
A.89 B.77 C.47 D.39
答案 C 本题考查对分查找,由代码得如果 s=n 为 1,需满足 i>j,也即查找的 key不在数组中,但是又只找了1次(变量n是查找次数),这是不可能的情况,故推出应该是s=m-n=1。第一次m=3,n=1,不成立,继续第二次查找;第二次,m=1或m=5,n=2,不成立,继续第三次查找;第三次,m=2或m=4或m=6,n=3。因此在m=4,n=3的时候,找到了key,此时满足m-n=1,所以答案选择C。
7.对数组a中6个有序数据“11,22,33,44,55,66”,用下面的程序代码查找数据“23”,程序执行完毕后,下列各变量值正确的是( )
Dim a(1 To 6)As Integer
Dim i As Integer,j As Integer,Key As Integer,m As Integer
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 KeyElse i=m+1
Loop
A.i=5 B.j=4 C.m=3 D.p=2
答案 C 本题主要考查对分查找算法的变形算法。查找过程如下:一共有6个升序排列的数据,第一次查找,i=1,j=6,因此首先查找的是m=(i+j)2=3,而j mod 2=0,因此m=m+1=4,即查找到第4个数“44”。由于“23<44”,因此第二次查找,i=1,j=m-1=3,m=(i+j)2=2,即查找到第2个数“22”。由于“23>22”,因此第三次查找,i=m+1=3,j=3,则m=(i+j)2=3,即查找到第3个数“33”,而“23<33”,所以第四次查找,i=m+1=4,此时i=4,m=3,j=3,p=3,i>j,整个查找过程结束,只有选项C成立。
8.有如下VB程序段:
Dim a(1 To 10) As Integer
Private Sub Form_Load()
a(1)=2:a(2)=3:a(3)=3:a(4)=3:a(5)=3
a(6)=6:a(7)=7:a(8)=7:a(9)=8:a(10)=9
End Sub
Private Sub Command1_Click()
Dim key As Integer, i As Integer, j As Integer
Dim m As Integer, p As Integer
key=Val(Text1.Text)
i=1: j=10
Do While i <=j
m=(i+j) 2
If a(m)=key Then
p=m
j=m-1
Else If key < a(m) Then
j=m-1
Else
i=m+1
End If
Loop
Text2.Text=Str(p)
End Sub
程序运行时,在文本框Text1中输入3,单击按钮,文本框Text2显示的内容是( )
A.2 B.3 C.4 D.5
答案 A 本题考查程序阅读。本题的算法框架是对分查找,不同之处是,当If a(m)=key时,将j的值变为m-1,还要继续往左查找。最左边的3的位置是2,故本题选A。
9.某对分查找算法的VB程序段如下:
t=“”: i=0 : j=9 : key=62: f=False
Do While i <=j And Not f
m=Fix((i+j) / 2)
t=t+Str(rn)
If a(m)=key Then
f=True
Elself a(m) > key Then
i=m+1
t=t+“→”
Else
j=m-1
t=t+“←”
End If
Loop
数组元素a⑹到a⑼的值依次为“99, 94, 90, 87, 78,70, 63,56, 45,36”,执行该程序段,t的值是( )
A.“4→7←5→” B.“4→ 7← 5→ 6→”
C.“4→7←5→6” D.“4→ 7← 5”
答案 B 本题考查对分查找,查找过程如表:
i
0
5
5
6
7
j
9
9
6
6
6
m
4
7
5
6
退出循环
a(m)
78
56
70
63
t
4→
4→7←
4→7←5→
4→7←5→6→
10.循环升序数组指的是将一个升序数组循环右移动若干距离之后变成的数组。如5、7、9、26、41、100,循环右移3位得到26、41、100、5、7、9。对分查找算法适当优化后也适用于循环升序数组。程序段如下:
l=1: r=6
Key=Val(Text1.Text)
Do While l <=r
m=Int((l+r) 2)
If a(m)=Key Then
(1)
Exit Do
Elself a(m) >=a(l) Then
(2)
Elself a(m) < a(l) Then
(3)
End If
Loop
上述程序中方框处可选语句为:
①If a(m) < Key And a(r) >=Key Then l=m+1 Else r=m-1
②Listl .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.②③①
答案 D 分析循环升序数组的特点:一定有一个转折点,转折点两侧数组都是有序的,并且左侧数据全部比右侧数据大,也即a(n)“If a(m)=Key”的情况下,是找到了关键词,因此直接输出结果,所以(1)处填②。a(m) >=a(l),那么a(m)一定在左侧升序段,可以肯定[l,m]这一段是严格递增的,此时如果a(m) > Key And a(l) <=Key,则能得到结论key一定在[l,m]这一段里,否则就是在a(m)的右边;a(m) < a(l),那么a(m)一定在右侧升序段,可以肯定[m,r]这一段是严格递增的,此时如果a(m) < Key And a(r) >=Key,则能得到结论key一定在[m,r]这一段里,否则就是在a(m)的左边。
11.査找并删除重复数据的算法是对数组a中每个元素逐个作为关键字进行从后往前查找,如果有重复,删除该数据后继续查找。例如,第一次将a(1)作为关键字,从a(10)到a(1)进行逐个查找,如果和a(1)相等,则删除该数据,然后继续查找;如果是a(1)本身和它相等,则代表无重复数据。编写VB程序,程序功能如下:运行程序时,在列表框List1中显示数组a中的原始数据;单击“去除重复”按钮(Command1),在列表框List2中输出去除重复后的数组a中的数据,同时在标签Label1中显示删除的数据总个数,运行效果如图所示。
/
请回答下列问题:
(1)当数组a中的值依次为1,2,3,7,8,1,6,6,8,7时,共删除数据 (填写数值)个。?
(2)实现上述功能的VB程序如下,请在划线处填入合适的代码。
Const maxn=10
Dim a(1 To maxn) As Integer
Private Sub Form_Load()
’maxn 个数据存储在数组a中,并在列表框List1中显示
’代码略
End Sub
Private Sub Command1_Click()
Dim i As Integer, n As Integer ??n用于存储当前査找的数组长度
Dim j As Integer, key As Integer ??key用于存储本次查找关键字的数据位置
key=1: n=maxn
Do While key <=n
i=n
Do While a(i) <> a(key)
① ?
Loop
If i=key Then ??未找到,重新下一査找关键字
key=key+1
Else ??找到重复数据,删除
For j=i To n-1
② ?
Next j
n=n-1
End If
Loop
For i=1 To n
List2.AddItem Str(a(i))
Next i
Label1.Caption=“共删除数据”+ ③ +“个”?
End Sub
答案 (1)4
(2)①i=i-1 ②a(j)=a(j+1) ③Str(maxn-n)
解析 (1)略。
(2)①从底部开始逐个与a(key)比较,例如key=1时,a(10),a(9),…,a(i),…,a(2)逐个与a(1)比较,即数组下标递减i=i-1,若a(i)=a(key),则找到相同,循环结束。②上面a(i)=a(key)循环结束后,若i=key,则意味着没有重复元素。例如key=1时,只有a(1)=a(1),没有其他元素和a(1)相等,就没有重复元素。否则,意味着有重复元素,则需要去除重复元素。后面的元素依次往前移动,即a(j)=a(j+1)。③由于maxn是总共的数据个数,而n是剩下的数字个数,因此删除的数据个数就是Str(maxn-n)。
第4节 查找算法及程序实现
真题再现
选考题组
1.(2018浙江4月学考+选考,12,2分)数组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
(1)
ElseIf Key Mod 2=0 And a(m) Mod 2=1 Then
(2)
Else
(3)
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.③、②、①
答案 C 本题主要考查对分查找,并在此基础上加上奇数偶数的条件,稍稍增加了难度。数组 a不是一个升序序列,而是包含奇数和偶数两个升序序列。“If Key Mod 2=1 And a(m) Mod 2=0”的情况是:关键词key是奇数,而a(m)是偶数,则查找范围一定是在a(m)前面,因此(1)处填j=m-1。“ElseIf Key Mod 2=0 And a(m) Mod 2=1”的情况是:关键词key是偶数,而a(m)是奇数,则查找范围一定是在a(m)后面,因此(2)处填i=m+1。这两种情况是比较简单的,此时已经可得到答案是C。“Else”的情况是:key和 a(m)的奇偶性一样,此时可以把它当成在一个升序序列中查找,因此(3)处填If Key < a(m) Then j=m-1 Else i=m+1。
2.(2017浙江11月选考,12,2分)某算法的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表示退出循环
Else If 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
答案 C 本题考查对对分查找程序的理解。执行对分查找算法,7个数最多查找3次,而且找到后就会退出,排除B、D,如果只找了2次,必然是在找到的情况下才会发生,所以排除A。
3.(2017浙江4月学考+选考,11,2分)某对分查找算法的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中显示的是( )
A.40 24 B.40 24 36 C.36 24 D.36 17 24
答案 B 本题考查对分查找。需要注意的是代码里中间值的计算,m=Int((i+j) / 2+0.5),第1次:m=Int((1+10) / 2+0.5)=6,a(6)=40,大于关键词30,因此j=6-1=5;第2次:m=Int((1+5) / 2+0.5)=3,a(3)=24,小于关键词30,因此i=3+1=4;第3次:m=Int((4+5) / 2+0.5)=5,a(5)=36,大于关键词30,因此j=5-1=4;第4次:m=Int((4+4) / 2+0.5)=4,a(4)=30,等于关键词30,此时退出循环。因此输出前三次找到的数:40、24、36,最后一次的30不输出。
4.(2016浙江10月学考+选考,12,2分)某对分查找算法的VB程序段如下:
i=l: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表示退出循环
If keyLoop
数组元素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
答案 D 本题主要考查对分查找的思想方法。变量n记录了查找次数,即某个key值查找了两次。该数组共9个,第一次找到第5个元素(中间位置m=fix((1+9)/2)=5)。如果key比d(5)小,则第二次查找范围是前半部分,即第1个元素至第4个元素,则第二次找到第2个元素(中间位置m=fix((1+4)/2)=2),即12。如果第一次查找发现key比d(5)大,则第二次查找范围是后半部分,即第6个元素至第9个元素,则第二次找到第7个元素(中间位置m=fix((6+9)/2)=7),即61。如果查找两次找到目标的话,key的值应该是12或61。
5.(2016浙江4月学考+选考,12,2分)已知一无序数组a(下标1到n),通过引入数组b(下标1到n),使得a(b(1))≤a(b(2))≤a(b(3))≤…≤a(b(n))(示例如图所示),对这些有序数据可进行对分查找。则第一次查找时,中点位置m与中点值分别是( )
数组a
i
a(i)
1
95
2
12
3
44
4
78
5
67
?
引入数组b后
i
b(i)
a(b(i))
1
2
12
2
3
44
3
5
67
4
4
78
5
1
95
A.m的值是Fix((1+n)/2),中点值是 a(m)
B.m的值是Fix((1+n)/2),中点值是 a(b(m))
C.m的值是Fix((b(1)+b(n))/2),中点值是 a(m)
D.m的值是Fix((b(1)+b(n))/2),中点值是 a(b(m))
答案 B 本题考查的是对分查找。根据对分查找的算法思想,中点位置m仅取决于元素个数,已知数组共n个元素,所以第一次查找位置m=fix((1+n)/2),又因数组a的下标由数组b来表示,所以m位置的元素值为a(b(m)),故正确答案为B。
6.(2013浙江3月高考,4,3分)某查找算法的部分VB代码如下:
t=False
i=0
Do While i<7 And t=False
i=i+1
If a(i)=Key Then t=True
Loop
If t=False Then i=0
数组元素a(1)到a(7)的数据依次为“3,5,1,5,8,9,5”,当变量key值为5时,运用该算法处理后,变量i的值是( )
A.0 B.2 C.4 D.7
答案 B 本题主要考查顺序查找算法的代码。i是逐个查找的循环变量,而t记录当前是否已经找到,初值是False,表示未找到;如果在逐个查找的过程中找到了key,则t设置为True,表示找到了。由于Do语句设置了条件i<7 And t=False,因此一旦t=True,则会马上退出Do语句。当找到第二个数据时,key就找到了,这时就退出了循环,此时i的值为2。
7.(2018浙江11月选考,16,3分)数组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程序如下,但加框处代码有错,请改正。
Private Sub Command1_Click()
Const n=6
Dim a( 1 To n) As Integer,flag As Boolean
Dim i As Integer, j As Integer,m As Integer,key As Integer
’读取一组正整数,按上述规则存入数组a中,代码略。
key=Val(Text1.Text)
i=1
j=(n+1)2
flag=False
Do While i m=(i+j)2
If key=a(m)Then
flag=True
ElseIf key j=m-1
Else
i=m+1
End If
Loop
If Not flag And j>0 Then
m= n-i ’(2)
If key=a(m)Then flag=True
End If
If flag Then
Text2.Text=Str(m)
Else
Text2.Text=“找不到”
End If
End Sub
答案 (1)i<=j (2)n-i+2 或 n-j+1
解析 本题的数据源其实是由两个有序数列构成,前一半是递增序列,后一半是递减序列,最大值在中间。本题中采用的思想方法:在前一半序列按正常的对分查找思想找关键词,如果在前一半序列中找到,任务结束,如果没找到,有两种可能:①在整个序列中不存在关键词;②关键词在后一半序列中。利用前面对分查找退出时i的值,再加上条件“这是一个左右交替上升的序列”,找到后一半序列中对称位置的元素,如果与关键词相同,则找到,如果与关键词不相同,则表示整个序列中不存在关键词。
(1)查找的数据源是前一半序列,产用标准的对分查找思想。Flag是标记,标记是否已经找到。i和j分别表示起始位置和结束位置,因此此处填i<=j。
(2)If Not Flag and j>0的含义:关键词未找到并且j>0。当关键词比a(1)还小,则对分查找结束后,i=1,j=0,此时关键词也不可能在后一半序列中。如果j>0,则关键词可能在后一半序列中,根据对分查找的思想方法,在找不到的情况下,最后一次查找必定是i=j进入循环,此时m=i=j,最后一次查找分两种情况:keya(m),执行i=m+1。不管是哪种情况,最后j=i-1,并且key的值一定为a(j)由于这是一个左右交替上升的序列,因此目前唯一可能与key相同的元素只有后一半序列中第n-i+2这个元素,因为该元素值是介于a(i-1)与a(i)之间的。如i=3,则a(2)8.(2017浙江4月学考+选考,16,3分)小王编写了一个实现文字查找替换功能的VB程序,运行界面如图所示。文本框Text1显示原文内容,Text2中输入查找内容,Text3中输入替换内容,单击“全部替换”按钮Command1后,Text4显示查找替换的结果,Text5中显示替换的次数,Text6显示“查找内容”在原文中的起始位置。
/
实现上述功能的VB程序如下,但加框处代码有错,请改正。
Private Sub Command1_Click()
Dim s As String, resule As String, pos As String
Dim count As Integer, i As Integer
i=1: count=0
result=“”: pos=“”
Do While i <=Len(Text1.Text)
s=Mid(Text1.Text, i, Len(Text2.Text))
If s=Text2.Text Then
result=result+Text3.Text
count=count+1
pos= pos+Str(count) ’(1)
i=i+Len(Text2.Text)
Else
result=result+Text2.Text’(2)
i=i+1
End If
Loop
Text4.Text=result
Text5.Text=Str(count)
Text6.Text=pos
End Sub
答案 (1)pos+str(i)
(2)result=result+Mid(Text1.Text,i,1)
解析 (1)变量result存储替换后的新字符串,count存储替换次数,pos存储替换位置。程序通过变量i来读取原字符串中的字符,因此当前位置应该是i。
(2)Else语句对应的情况是:原字符串中取出来的子串不等于替换内容,因此不需要替换,保持原样,从该行代码紧接着的一句“i=i+1”可得出字符串往后移一位,因此result需要保存原字符串当前位置i上的一个字符。
课件35张PPT。
第4节 查找算法及程序实现一 查找算法的基本思想二 查找算法的程序实现教材研读突破 对分查找重难突破一、查找算法的基本思想
1.顺序查找
顺序查找的基本思想是从第一个数据开始,按数据的顺序逐个将数
据与给定的值进行比较。若某个数据和给定值相等,则查找成功;如果所
有的数据都比较过,没有一个数据和给定值相等,则查找不成功。教材研读 2.对分查找
对分查找的基本思想是在有序的数据列中,首先将要查找的数据与有
序数组内处于中间位置的数据进行比较,如果两者相等,则查找成功;否则 根据数组元素的有序性,就可确定该数据应该在数组的前半部分还是后 半部分继续进行查找。在新确定的范围内,继续按上述方法进行查找, 直到找到要查找的数据,则查找成功,或直到子表不存在,则查找不成功。
对分查找的条件是被查找的数据列必须是有序的。二、查找算法的程序实现1.顺序查找
在数据源中从头到尾逐个与查找关键词比较,顺序查找的代码如下:
For i=1 To n
If a(i)=key Then
Print i:Exit For
End If
Next i
If i=n+1 then s=“未找到”说明:①for 语句用于访问整个查找源的数据,一般是从开始位置到结束 位置。
②if 语句用于判断当前访问的元素是不是等于关键词。
③一旦某个位置的数据等于关键词,则输出该位置,并且查找任务结束, 通常用语句 Exit for 退出循环。
④未找到,也应该有输出。能找到的情况下,因为是通过exit for退出循 环的,因此退出循环时i<=n;找不到的情况下,退出循环时i=n+1。
⑤顺序查找不要求数据源是有序的。2.对分查找的代码如下:
key=text1.text ??????输入关键词
i=1:j=n ??????设置首次查找的范围
f=False ??????f标志是否已经找到关键词
Do While i<=j And Not f ??????未找到并且查找范围还存在
m=(i+j)2 ??????计算中间位置
If key=a(m) Then
f=True ??????相等表示找到了,将f设为True ElseIf key j=m-1 ??????下一次查找范围是前半部分
Else
i=m+1 ??????下一次查找范围是后半部分
End If
Loop 说明:①变量 i 和 j 记录每一次查找的起始位置和结束位置,变量 m
记录中间位置。如果 keya(m),则下一次查找的范围是后半部分,因此 j 不 变,i=m+1。
②退出 DO 循环有两种可能:第一种是 f 为 True,说明已经找到关键词, 此时结束查找;第二种是 i>j,查找的起始位置超过结束位置,说明已经找 遍数据源,但是找不到关键词,此时结束查找。
③对分查找的前提是被查找的数据必须是有序的。3.对分查找的其他写法
key=text1.text
i=1:j=n
Do While i<=j
m=(i+j)2
If key=a(m) Then Exit Do??????找到关键词,直接退出循环
If keyLoop1.小王拿着一大串钥匙去开仓库的某一扇门,由于钥匙上没有任何标记, 小王只能将这一串钥匙一把一把地去试。从算法角度看,小王的做法属
于?( D )
A.冒泡排序 B.选择排序 C.对分查找 D.顺序查找解析 本题主要考查两种查找算法的区别。顺序查找的基本思想 是从第一个数据开始,按数据的顺序逐个将数据与给定的值进行比较。 若某个数据和给定值相等,则查找成功;否则,查找不成功。本题中“一 把一把地去试”是顺序查找的基本思想。2.使用对分查找算法在包含某个有序元素的数组中查找某值,下列说法 错误的是(中括号[]表示向下取整)?( B )
A.第一次查找的位置一般是[(1+n)/2]
B.在某连续的三次查找中,不可能是三个相邻的元素
C.如果找不到,那么最少需要查找[log2n]次
D.如果找得到,那么最多需要查找[log2n]+1次解析 比如5个元素的查找,第一次查找3号位置,第二、三次分别查 找1号和2号位置,三者相邻。对分查找在找不到的情况下,最少也需要 [log2n]次查找,相当于每次都在元素个数较少的数组中查找;选项D刚好相反,每次都在元素个数较多的数组中查找,但总次数不会超过[log2n]+1次。3.用对分查找算法在含有100个元素的无重复有序数组中查找某元素, 已知第3次查找位置是62号元素,则第4次查找不可能是?( A )
A.第43号元素 B.第56号元素
C.第68号元素 D.无需第4次查找解析 考查对分查找算法的原理。100个有序元素中,第1次查找位 置是50,第2次查找位置是25或75,第3次查找位置是62,第4次查找位置是 62左右两段区间:[51,61]和[63,74]内的元素,而第4次无需查找也是有可 能的。4.7位学生的身高(单位:cm)从高到低依次为:178,177,175,172,170,165,16 2。用对分查找法找到178的过程中,依次被访问到的数据是?( C )
A.178 B.172,175,178
C.172,177,178 D.172,175,177,178解析 本题主要考查对对分查找算法基本思想的理解。将7个数据 从1到7进行编号。第一次访问到的数据是第4个,即172(中间位置m=Fix ((1+7)/2)=4),178>172,因此下一次查找的范围是前半部分,即第1个到第 3个。因此第二次访问的数据应该是第2个,即177(中间位置m=Fix((1+ 3)/2)=2),178>177,因此下一次查找的范围是前半部分,即第1个,因此第 三次访问的数据是第1个,即178。5.有一组数据为“2、3、5、5、7、7、8”,利用顺序查找和对分查找 查找5时,则分别查找几次可以找到目标值?( C )
A.3 无法使用对分查找 B.4 无法使用对分查找
C.3 1 D.4 1解析 本题主要考查顺序查找和对分查找的基本思想。顺序查找 的基本思想是在数据源中从头到尾逐个与查找关键词比较,因此顺序查 找第3次查找找到目标值5。对分查找的基本思想是将查找关键词与数 据源中间位置的数据进行比较,如果两者相等,则查找成功;如果不相等, 则将查找范围缩小一半,并进行下一次查找。数据源中间位置的数据是 5,因此第1次查找就找到了目标。6.数组A中存放了某校学生的身高数据(单位:厘米),数据存放情况如下 表:若要查找数组中是否存在数据182,以下表述正确的是?( A )
A.本组数据既能采用对分查找算法,也能采用顺序查找算法
B.本组数据采用对分查找需比较4次,而顺序查找只需2次,所以对分查 找效率高的说法不对
C.本组数据须先对数据进行升序排序后才能进行对分查找D.本组数据由于存在相同数据176,所以不能采用对分查找算法解析 本题主要考查查找算法的基本概念。顺序查找对于数据源 没有要求,可以是无序的,也可以是有序的,而对分查找要求数据源必须 是有序的,可以是升序的也可以是降序的,这是由顺序查找和对分查找 的思想方法决定的。从表中可以看出该组数据源是有序的,而且是降 序。因此选项A正确,C错误。如果数据源中存在相同的数据,则一般情 况下只要找到了一个,查找就算完成,因此存在相同数据时也可以使用 对分查找,D错误。顺序查找平均需要比较(n+1)/2次,因此时间复杂度是 O(n),而对分查找的每一次查找都将查找范围缩小一半,因此时间复杂度是O(log2n),比顺序查找的效率高。虽然对于查找某些关键词(往往在 数据源中是比较靠前的),顺序查找很快,但这只是特殊情况,不能代表平 均情况。对分查找
对分查找的基本思想:查找的数据源 a(1)到 a(n)是有序的(如从小 到大排序),查找的关键词是 key,则第一次查找的范围是[1,n],如果中间 位置为 m,则 m=(1+n)2。如果key=a(m),则查找成功;如果 keya(m),则下一次查找的范围变 为[m+1,n]。在新确定的范围内,继续按上述方法进行查找,直到找到要重难突破查找的数据,则查找成功;或直到子表不存在,则查找不成功。
说明:①对分查找的每一次查找,要么找到了目标,结束任务;要么通过
比较中间值与关键词,将下一次的查找范围缩小一半,因此对分查找的效 率往往高于顺序查找。对n个数据查找某个值,最多需要查找int(log2n)+ 1次。
②找不到关键词的情况下,最后一遍查找时,i=j=m,若key>a(m),则i=m+ 1;若key 实例:a(1)到a(10)的值依次为2,7,8, 10, 12, 13, 16, 18, 19, 20 序号表示第几次找到该数。如果“if (i+j) mod 2=1 then m=m+1”写
成“if j mod 2=0 then m=m+1”,查找过程可能也不同,要根据实际情况。例1 有一个由4000个整数构成的顺序表,假定表中的元素已经按升序 排列,采用对分查找查找一个元素,则最多需要 ????次比较就能确 定是否存在所查找的元素?( B )
A.11 B.12 C.13 D.14解析 本题主要考查对分查找的效率问题。根据对分查找的思想方法, 每一次查找的结果要么是找到,要么是找不到,如果找不到则将下一次 的查找范围缩小一半。最差的情况是数据源中没有查找对象,每次查找 都将查找范围缩小一半。规模为n个数的数据源,使用对分查找时,最多 经过Int(log2n)+1次查找。Int(log24000)+1=11+1=12。例2 某对分査找算法的VB程序段如下:
i=1: j=10: s=""
Key=Val(Text1.Text)
Do While i <=j
m=Int((i+j+1) / 2)
s=s+Str(m)
If Key=a(m) Then Exit Do
’Exit Do 表示退出循环 ElseIf Key < a(m) Then
j=m-1
Else
i=m+1
End If
Loop
Text2.Text=s
数组元素a(1)到a(10)的值依次为“3,10,25,34,40,52,61,72,83,90”。该程序段执行后,下列说法中正确的是?( D )
A.待查找的数据只能是整数
B.在文本框Text1中输入任意正整数进行查找,则查找的次数介于1和5 之间
C.在文本框Text1中输入10,则文本框Text2中显示的内容为5 2
D.若在某次查找中,i=j时,条件“Key=a(m)”仍不成立,表示查找的数据 不存在解析 本题属于较难题,考查对分查找算法的思路。本题要点在于对分 查找各种情况的判断,由程序可知,Key为待查找数据,其值可以是任意 数,查找的最多次数为Int(log210+1)=4次,当Key=10时,依次访问的位置 为6、3、2,故排除A、B、C选项。当i=j时,表示访问的数据为最后一个 数据,若条件“Key=a(m)”仍不成立,则原数据序列中无该数据。枚举算法与顺序查找易混易淆头到尾逐个访问数据源中的数据;if语句是检验可能解还是比较关键词。 不管是枚举算法还是顺序查找,都可以写成For循环语句,区分的方 法是要分析问题的本质:for语句是为了一一列举所有可能的解还是从