4.4二分查找法训练7(表格式)

资源下载
  1. 二一教育资源

4.4二分查找法训练7(表格式)

资源简介

4.4二分查找法训练7
学校:___________姓名:___________班级:___________考号:___________
一、选择题
1.某对分查找算法的VB程序段如下:
Key = Val(Text1. Text)
n = Val(Text2. Text)
i = 1:j = n
Do While i < = j
m = (i+j) \2
If a(m) = Key Then Exit Do' Exit Do表示退出循环
If a(m)> Key Then j= m - 1 Else i= m+ 1
LooP
整数数组元素a(1)到a(100)为升序序列。在文本框Text1和Text2中分别输入待查找数Key及n,表示在数组a(1)~a(n)间查找数字key。输入key的值,若找不到该数,且“m=(i+j)\2”该语句执行了4次,则n值可能是( )
A.7或8 B.5或31 C.8或30 D.6或15
2.已知一无序数组a中的元素为“90,15,40,72,65,32,81,6”,通过引入数组b存储数组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
3.有10个数据34,22,101,8,14,88,24,17,54,7依次存放在数组a(1 to 10)中,下列关于数据查找的说法中,正确的是( )
A.数据19不在数组a(1 to 10)中,不能进行查找
B.可以直接对数组a(1 to 10)采用对分查找
C.最多经过10次比较,肯定能得出查找结论
D.顺序查找肯定比对分查找效率低
4.某对分查找算法的VB程序段如下
Key =Val(Text1. Text)
i=1:j=10:n=0
Do While i <=j
m= (i+j)\2
n=n+1
If a(m)>Key Then
j=m-1
Else
i=m+1
End If
Loop
Text2. Text = str(n)
数组元素a(1)到a(10)的值依次为“2,3,5,8,9,10,13,17,19,25”,在文本框Text1中入待查找的整数,执行该程序段,则文本框Text2中显示3,待查找数不可能是( )
A.2 B.4 C.9 D.19
5.以下是依据对分查找思想,设计的一个三分查找程序。已知数组a(1 To 10)中的数据分别是12、21、34、45、59、63、72、86、94、100,当在文本框Text1中输入“34”时,输出“34”的位置值“3”,当输入“33”时,输出“33”邻近数的位置值“23”。实现该功能的VB程序段如下:
Key = Val (Text1. Text)
i=1 : j=10
flag = False
Do While i < = j And Not flag
mid1= Int (i + (j-i) /3)
mid2= Int (j - (j-i) /3)
If Key = a(mid1) Or Key = a (mid2) Then
flag = True
ElseIf Key < a (mid1) Then
______(1)______
ElseIf Key > a (mid2) Then
______(2)_______
El se
i=mid1 + 1
j=mid2 - 1
End If
Loop
If _______(3)_______ Then
List2. AddItem Str (mid1)
ElseIf flag Then
List2. AddItem Str (mid2)
Else
List2. AddItem Str(j) + Str (i)
End If
上述程序中方框处可选语句为 ①i=mid1+1;② i=mid2+1;③ j=mid1-1;④ j=mid2-1;⑤ Key=a(mid1);⑥ flag And Key=a(mid1),则(1)、(2)、(3)处语句依次是( )
A.④②⑤ B.③②⑥ C.②③⑥ D.④③⑤
6.某对分查找算法的VB程序段如下:
i =1:j=10:nc=0:f=False
Key = Val(Textl. Text)
Do Whilei < = j And Not f
m=(i+j)\ 2
nc=nc+1
If a(m) = Key Then
f = True
ElseIf Key > a(m) Then
j = m-1
Else
i = m+1
End If
Loop
数组元素a(1)到a(10)的值依次为“94,91,87,76,73,70,67,61,18,17”,该程序段运行结束后,若nc的值为2,则Key的值是 ( )
A.76或67 B.91或61 C.87或61 D.94或91
7.有如下 VB 程序段:
a(1) = 13: a(2) = 22: a(3) = 36: a(4) = 42: a(5) = 50: a(6) = 58: a(7) = 62: a(8) = 70 i = 1: j = 8: count = 0
Randomize
key = Int(Rnd * 100 )
Do While i <= j
m = (i + j + 1) \ 2
If a(m) >= key Then
count = count * 2 + 1
j = m - 1
Else
count = count * 2
i = m + 1
End If
Loop
执行该程序段后,count 的值不可能的是( )
A.15 B.14 C.7 D.6
8.有如下VB程序段:
key=Val(Text1.Text)
i=0:j=9:n=0
Do While i<=j
m=(i+ j)\2
n=n+1
If key<=a(m)Then
j=m-1
Else
i=m+1
End If
Loop
s=i
Do While i<9 And a(i)=a(i+1)
i=i+1
Loop
Labe12.Caption = Str(n)+":"+Str(i+1-s)
数组元素a(0~9)的值依次为“3,4,7,8,8,8,9,9,10,12”在文本框Text1中输入“8”,点击“查找”按钮后,Labe12中输出的结果是( )
A.3:3 B.3:4 C.4:3 D.4:4
9.某对分查找的程序代码如下
Key = Int(Rnd * 25) * 2
n = 0: i = 1: j = 10
Do While i <= j
m = (i + j) \ 2
If Key = a(m) Then
Exit Do
If Key < a(m) Then
j = m - 1: n = n + 1
Else
i = m + 1: n = n - 1
End If
Loop
Text2.Text = Str(n)
其中 a(1)到 a(10)数组的值分别“2,3,6,9,10,18,38,40,47,48”, 执行该程序段后,n 的值不可能的是( )
A.0 B.-1 C.-2 D.-3
10.有如下VB程序段:
i =1:j= 6:n =o :Key = Val(Text1.Text)
Do While i<= j
m = (i+j) \ 2
n = n+1
If Key > a(m) Then j = m- 1 Else i = m +1
Loop
a(1)到a(6)的值依次为“99,77,55,44,33,22”,下列说法正确的是( )
A.数组a中的元素若无序,也可用此程序段进行查找某个数字
B.无论key值是多少,循环结束后“i >j”一定成立
C.如果key值为55,那么该程序段运行后,变量n的值为1
D.如果key值为40,那么该程序段运行后,变量m的值为5
11.有n个连续的自然数,删除首尾两端之外的其中一个数后存储在数组元素a(1)到a(n-1)中,利用对分查找算法找出这个数的某VB程序段代码如下:
Constn=10
i=1:j=n–l
DoWhilej-i>=2
m=(i+j)\2
If (1) Then
i=m
Else
__(2)
EndIf
Loop
Text1.Text=Str(( 3 ))
上述程序中(1)(2)(3)划线处可选语句有:
①a(j)-a(m)=j-m②a(m)-a(i)=m–i
③j=m–1④j=m
⑤a(i)+1⑥a(i)
则上述程序中(1)、(2)、(3)划线处的代码依次为
A.①③⑤ B.②④⑤ C.①③⑥ D.②④⑥
12.有一组升序排列的数:3、6、7、10、12、17、26、31、79,如果用对分法查找数据10,则依次访问的数据为( )
A.12、6、7、10 B.12、7、10 C.12、6、10 D.12、7、6、10
13.有如下 VB 程序段:
Const n = 10
key = Val(Text1.Text) '文本框 1 中输入待查找的数据
i = 1: L = 1: R = n
If check(key) Then 'check(x)为自定义函数,判断 x 为否偶数,若是返回 True,否则为 False.
Do While Not check(a(L))
L = L + 1
Loop
Else
Do While check(a(R))
R = R - 1
Loop
End If
Do While L <= R
m = (L + R) \ 2
If key = a(m) Then Exit Do
If key > a(m) Then
L = m + 1
If key < a(m) Then
R = m - 1
Loop
若数组元素 a(1)到 a(10)依次为“1,3,5,7,9,2,4,6,8,10”,执行以上程序段,依次对该组数据进行查找,平均查找次数(平均查找次数=总查找次数/数据总个数)为( )
A.22/10 B.29/10 C.55/10 D.29/20
14.已知一元二次函数 f(x)=在区间[0,1]之间必定存在着一个极大点x0,使 f(x0)达到最大值。现用对分查找算法搜索x0的值,开始搜索区间为[0,1],在搜索到第 n 次时找到x0,已知第n次搜索区间的长度是1/32,则 n 的值是( )
A.3 B.4 C.5 D.6
参考答案:
1.C
【详解】本题主要考查对分查找算法。对分查找算法,最大比较次数为int(log2n)+1,由此可知C选项正确。
2.C
【详解】本题考查查找算法相关知识。由题目可知,key=32,初始值i=1,j=8,c=0,进入循环:
第一遍循环,m=4,t=3,c=c+1=1,a(t)>key,故执行j=m-1=3;
第二遍循环,m=2,t=2,c=c+1=2,a(t)第三遍循环,m=3,t=6,c=c+1=3, a(t)=key,故执行p=t:Exit Do,循环结束,可知程序运行结束后变量c的值为3,故本题选C。
3.C
【详解】本题考查查找算法相关知识。数据19虽然不在数组a(1 to 10)中,仍旧可对其进行查找,只是查找结果是找不到,选项A错误;数组a是无序数组,无法采用对分查找,对分查找是数组必须是有序排列的,选项B错误;最多经过10次比较,肯定能得出查找结论,选项C正确;若查找元素是第一个,则顺序查找比对分查找效率高,选项D错误。故本题正确的是选项C的说法。
4.D
【详解】本题考查查找算法相关知识。
假设Key=2;
第一次查找,i=1,j=10,则m=5,n=1,a(m)>key成立,故执行j=m-1=4;
第二次查找,i=1,j=4,则m=2,n=2,a(m)>key成立,故执行j=m-1=1;
第三次查找,i=1,j=1,则m=1,n=3,a(m)>key不成立,故执行i=m+1=2,此时i>j,退出循环,故最终n=3,符合题干。
假设Key=4;
第一次查找,i=1,j=10,则m=5,n=1,a(m)>key成立,故执行j=m-1=4;
第二次查找,i=1,j=4,则m=2,n=2,a(m)>key不成立,故执行i=m+1=3;
第三次查找,i=3,j=4,则m=3,n=3,a(m)>key成立,故执行j=m-1=2,此时i>j,退出循环,故最终n=3,符合题干。
假设Key=9;
第一次查找,i=1,j=10,则m=5,n=1,a(m)>key不成立,故执行i=m+1=6;
第二次查找,i=6,j=10,则m=8,n=2,a(m)>key成立,故执行j=m-1=7;
第三次查找,i=6,j=7,则m=6,n=3,a(m)>key成立,故执行j=m-1=5,此时i>j,退出循环,故最终n=3,符合题干。
假设Key=19;
第一次查找,i=1,j=10,则m=5,n=1,a(m)>key不成立,故执行i=m+1=6;
第二次查找,i=6,j=10,则m=8,n=2,a(m)>key不成立,故执行i=m+1=9;
第三次查找,i=9,j=10,则m=9,n=3,a(m)>key不成立,故执行i=m+1=10;
第四次查找,i=10,j=10,则m=10,n=4,a(m)>key成立,故执行j=m-1=9,此时i>j,退出循环,故最终n=4,不符合题干。
故本题待查找数不可能是19,本题选D。
5.B
【详解】本题主要考查对分查找算法知识点。如果Key = a(mid1) Or Key = a (mid2),则flag=True,循环结束,如果Key < a (mid1) ,说明查找关键字在左边1/3处,执行 j=mid1-1;如果Key > a (mid2) ,说明查找关键字在右边1/3处,执行 i=mid2+1;如果flag=True,且 Key=a(mid1),即找到关键字key在mid1处,执行List2. AddItem Str (mid1),故本题选B选项。
6.B
【详解】本题主要考查对分查找算法实现。对分查找的基本思路:在有序的数据序列中(一般放在数组中), 首先把查找的数据与数组中间位置的元素进行比较,若相等,则查找成功并退出查找;否则,根据数组元素的有序性,确定数据应在数组的前半部分还是在后半部分查找;在确定了新的查找范围后,重复进行以上比较,直到找到或未找到为止。本题中,i和j为数组元素的位置,即下标,key为查找关键字,nc为查找次数,m为对分查找时分别获得的数组元素的下标,要严格按照公式m=(i+j)\ 2来获得数据,第一次获得数据a (5) =73, 接下来有两种可能,可能key> 73或key<73,获得数据a(2) =91或a(8)=61,因此B选项正确。
【点睛】
7.C
【详解】本题考查查找算法相关知识。本题采用选项倒推法,选项A,若最终count=15,则倒推count的变化过程15→7→3→1→0,可知循环每一次都执行count=count*2+1和j=m-1,最终要得到count=15,i=1,j=0,选项A的值可能;选项B,若最终count=14,则倒推count的变化过程14→7→3→1→0,前三趟循环执行count=count*2+1,最后一趟执行count=count*2,最终要得到count=14,i=2,j=1,选项B的值可能;选项C,若最终count=7,则倒推count的变化过程7→3→1→0,当count=7时,此时i=1,j=1,循环并未结束,故count的值无法是7;选项D,若最终count=6,则倒推count的变化过程6→3→1→0,可知当i=3,j=2时,可以得到,选项D的值也可能。故执行该程序段后,count的值不可能的是选项C的值,本题选C。
8.C
【详解】本题主要考查VB程序查找算法。key=8,i=0,j=9,n=0,第一遍循环,满足i<=j,m=(0+9)\2=4,n=n+1=1,key=a(4)=8,j=m-1=3;第二遍循环,满足i<=j,m=(0+3)\2=1,n=n+1=2,key>a(1)=4,i=m+1=2;第三遍循环,满足i<=j,m=(2+3)\2=2,n=n+1=3,key>a(2),i=m+1=3;第四遍循环,满足i<=j,m=(3+3)\2=3,n=n+1=4,key=a(3),j=m-1=2,退出循环,s=i=3。第二个while循环,当i<9且a(i)=a(i+1)时,i递增,循环结束后i=5,i+1-s=5+1-3=3,故点击“查找”按钮后,Labe12中输出的结果是4:3,故本题选C选项。
9.C
【详解】本题主要考查对分查找。对分查找首先将查找键与有序数组内处于中间位置的元素进行比较,如果中间位置上的元素内的数值与查找键不同,根据数组元素的有序性,就可确定应该在数组的前半部分还是后半部分继续进行查找;在新确定的范围内,继续按上述方法进行查找,直到获得最终结果。题中a数组共10个元素,所查找数据Key = Int(Rnd * 25) * 2,由此可知,key取值范围为0-48之间的偶数,则程序执行结束后,n的值不可能为-2,因此C选项正确。
10.B
【详解】本题主要考查二分查找算法。二分查找的条件是数组有序,选项A说法错误;分析程序可知,无论key值是多少,循环结束后“i >j”一定成立,故本题选B选项;如果key值为55,那么该程序段运行后,变量n的值为3,选项C说法错误;如果key值为40,那么该程序段运行后,变量m的值为6,选项D说法错误。
11.B
【详解】本题主要考查VB程序的调试。如果a(m)-a(i)=m-i(因为是n个连续的自然数),则表明删除的数在m的右边,令i=m,继续循环,否则令j=m,最后循环结束,删除的数即为a(i)的下一个,即a(i)+1,故上述程序中(1)(2)(3)划线处可选语句有②④⑤,故本题选B选项。
12.A
【详解】本题主要考查对分查找算法。一共9个数,(1+9)/2=5,第一次查找的数是12,10<12,(1+4)/2=2,第二次查找的数是6,6<10,(3+4)/2=3,第三次查找的数是7,7<10,(4+4)/2=4,第四次查找的数是10,故依次访问的数据为12、6、7、10,故本题选A选项。
13.A
【详解】本题主要考查二分查找算法知识点。该数组前半段是奇数,后半段是偶数,所以当查找的关键字是奇数时,只需要在左半边查找,即L=1,R=5,故a(1)到a(5)的查找次数分别为3次、2次、1次、2次、3次,总共是3+2+1+2+3=11次,同理,当查找的关键字是偶数时,只需要在右半边查找,总的查找次数也是11次,故执行以上程序段,依次对该组数据进行查找,平均查找次数(平均查找次数=总查找次数/数据总个数)为(11+11)/10=22/10,故本题选A选项。
14.D
【详解】本题主要考查对分查找知识点。第一次搜索区间的长度是1,第二次搜索区间的长度是1/2,第三次搜索区间的长度是1/22,则第n次搜索区间的长度是1/2n-1。已知第n次搜索区间的长度是1/32,则1/2n-1=1/32,n=6,故本题选D选项。

展开更多......

收起↑

资源预览