教科版（2019）选修一3.3数据的查找同步训练（含解析）

教科版（2019）选修一3.3数据的查找同步训练
学校:___________姓名：___________班级：___________考号：___________
一、选择题
1．有如下VB程序段：
Dim i As Integer,c As String,s As String,t As Integer
Dim s2 As String,pwd As String
s=Text1.Text:pwd="71zhYEAR":s2="":t=0
For i = 1 To Len(s)
c=Mid(s,i,1)
If c>="0" And c<="9"Then
t=t*10+Val(c)
Else
s2=s2+Mid(pwd,t Mod 8+1,1)
End If
Next i
Text2.Text=s2
运行该程序段，在文本框Text1中输入“20B13A8”，文本框Text2输出的是（ ）
A．hY B．YE C．YE7 D．hYA
2．有一组升序排列的数：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
3．数组A 中存放了某校学生的身高数据（单位：厘米），数据存放情况如下表：
若要查找数组中是否存在数据182，以下表述正确的是（ ）
A．本组数据既能采用对分查找算法，也能采用顺序查找算法
B．本组数据采用对分查找需比较4次，而顺序查找只需2 次，所以对分查找效率高的说法不对
C．本组数据须先对数据进行升序排序后才能进行对分查找
D．本组数据由于存在相同数据176，所以不能采用对分查找算法
4．已知一元二次函数 f（x）=在区间[0，1]之间必定存在着一个极大点x0，使 f（x0）达到最大值。现用对分查找算法搜索x0的值，开始搜索区间为[0，1]，在搜索到第 n 次时找到x0，已知第n次搜索区间的长度是1/32，则 n 的值是（ ）
A．3 B．4 C．5 D．6
5．某校校园一卡通系统中有4096条记录信息（已经索引排序），假设从中取出一条记录并与待查找项进行比较所花时间为8毫秒，则用对分法在该系统中查找一条指定记录最多花费的时间约为（ ）
A．80 毫秒 B．104 毫秒 C．160 毫秒 D．240 毫秒
6．数组a共有9个整数元素，依次为“8，7，3，1，9，5，6，3，1”，则执行下列程序后Label1中显示的是（ ）
i = 1: j = 9:s=" ":flag=True
Key = 3
Do While i <= j And flag
m = (i + j) \ 2
s = s + Str(m)
If a(m) = Key Then
flag = False
Exit Do 'Exit Do表示退出循环
ElseIf Key > a(m) Then
i = m + 1
Else
j = m - 1
End If
Loop
If flag then s="没有找到"
Label1.Caption = s
A．没有找到 B．3 C．9 D．5 2 1
7．对数组 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)= 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 Key < a(m) Then
j = m - 1
Else
i = m + 1
Loop
A．i=5 B．j=4 C．m=3 D．p=2
8．某对分查找算法的VB程序段如下：
i = 1 : j = 7 : s = ""
Do While i <= j
m = (i + j) \ 2
If a(m) = Key Then
s = "E":Exit Do
ElseIf a(m) > Key Then
j = m – 1 : s = "L"
Else
i = m + 1 : s = "R"
End If
Loop
数组元素a(1)到a(7)的值依次为“25，42，53，66，77，83，98”，若key=60，运行上述程序段后，下列条件表达式成立的是（ ）
A．s = “E” B．s = “L” C．s = “R” D．s = “LRR”
9．有如下程序段：
Dim i As Integer, j As Integer, m As Integer
i = 0: j = 8: k = Val(Text1.Text)
Do While i <= j
m = Fix((i + j) / 2)
If k = b(m) Then
Exit Do
Else
If k < b(m) Then
j = m-1
Else
i = m + 1
End If
End If
Loop
数组元素b(0)到b(8)存储着参加比赛同学的编号，依次为“5，8，11，21，32，39，56，65，72”，经过该程序段“加工”查找编号为8的同学的过程中，依次被访问到的编号是（ ）
A．32 11 8 B．21 8 C．32 8 D．39 21 8
10．某分查找算法的 VB 程序段如下：
Key = Val(Textl.Text)
i = 1: j = 10
flag = False
Do While i <= j And flag = False
m = Fix((i + j) / 2)
If a(m) = Key Then flag = True
If Key > a(m) Then
j = m – 1
Else
i = m + 1
Loop
数组元素 a(1)到 a(10)的值依次：“95， 82， 76， 70， 68， 50， 41，9， 3， 1”，文本框 Text1中输入的值是 32， 运行程序段后， 以下变量的值正确的是（ ）
A．flag = True B．m = 8 C．i = 8 D．j = 8
11．有如下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
12．已知单调函数f(x)在[0，1]区间存在一个x0，使f(x0)＝0。现用对分查找法搜索x0的值，开始搜索区间为[0，1]，若经过10次对分查找后还需继续搜索，则第11次搜索区间的长度为( )
A．1/2 B．1/10
C．1/102 D．1/210
13．7位幼儿园小朋友的体重(单位kg)从低到高依次为：13，15，16，18，20，21，23。用对分查找法找到23的过程中，依次被访问到的数据是( )
A．23 B．18，21，23
C．18，23 D．18，20，21，23
14．某超市商品信息管理系统中有1万条商品资料记录(已经索引排序)，假设从中取出一条记录并与待查项进行比较所花的时间为20毫秒，则用对分法在该系统中查找任意一个指定商品最多花费的时间约为( )
A．13毫秒 B．14毫秒
C．280毫秒 D．14万毫秒
15．整数序列“2，3，6，11，19，23，41，47，51”用对分查找法和顺序查找法在查找23时两种方法都能访问到的是
A．3 B．6 C．19 D．47
试卷第1页，共3页
试卷第1页，共3页
参考答案：
1．B
【详解】本题主要考查VB程序的执行。s=“20B13A8”，该程序通过for循环截取字符串s的每一位进行判断，当截取的是数字时，执行 t=t*10+Val(c)，否则执行s2=s2+Mid(pwd,t Mod 8+1,1)，i＝1时，c＝“2”，t＝2，i＝2时，c＝“0”，t＝2*10+0=20，i=3时，c="B"，20 mod 8+1=5，s2=“Y”，i=4时，c=“1”，t=20*10+1=201，i=5时，c=“3”，t=201*10+3=2013，i=6时，c=“A”，2013 mod 8+1=6，s2=“Y”+“E”=“YE”，后面是数字8，s2的值无变化，故文本框Text2输出的是YE，故本题选B选项。
2．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选项。
3．A
【详解】本题主要考查对分查找知识点。本数组已经是降序排序，故本组数据既能采用对分查找算法，也能采用顺序查找算法，故本题选A选项；本次数据采用对分查找比较次数高，并不能否定对分查找的效率低，选项B说法错误；本组数据可以直接进行对分查找，选项C说法错误；本组数据存在相同数据176，可以采用对分查找算法，选项D说法错误。
4．D
【详解】本题主要考查对分查找知识点。第一次搜索区间的长度是1，第二次搜索区间的长度是1/2，第三次搜索区间的长度是1/22，则第n次搜索区间的长度是1/2n-1。已知第n次搜索区间的长度是1/32，则1/2n-1=1/32，n=6，故本题选D选项。
5．B
【详解】本题主要考查对分查找知识点。对分查找前提是数据有序，对 n 个数据查找，最 多查找次数为 Log2n+1（向下取整）。2^12=4096<2^13=8192，故最多需要查找13次，每次取出记录进行比较需要8毫秒，故在该系统中查找一条指定记录最多花费的时间约为13*8=104毫秒，故本题选B选项。
6．A
【详解】本题主要考查VB程序的执行。i=1，j=9，flag=True，Key=3，第一遍循环，m=(1+9)\2=5，s=“5”，key7．C
【详解】本题主要考查查找算法。i=1，j=6，p=0，key=23，第一遍循环，满足i<=j，p=p+1=1，m= (1 + 6) \ 2=3，满足 j Mod 2 = 0 ，m=m+1=4，keya(2），i=m+1=3；第三遍循环，满足i<=j，p=p+1=3，m= (3+ 3) \ 2=3，key8．C
【详解】本题主要考查对分查找算法。i=1，j=7，key=60，第一遍循环，满足i<=j，m = (1+ 7) \ 2=4，keya(2)，i=m+1=3，s = "R"，第三遍循环，满足i<=j，m = (3+ 3) \ 2=3，key>a(3)，i=m+1=4，s = "R"，循环结束，故运行上述程序段后，s = “R”，故本题选C选项。
9．C
【详解】本题主要考查对分查找算法。i=0，j=8，k=8，第一遍循环，满足i<=j，m= Fix((0+8) / 2)=4，k=810．C
【详解】本题主要考查VB程序的执行。key=32，i=1，j=10，flag=False，第一遍循环，m = Fix((1+ 10) / 2)=5，keya(8)，j=m-1=7；第三遍循环，m = Fix((6+ 7) / 2)=6，key11．B
【详解】本题主要考查二分查找算法。二分查找的条件是数组有序，选项A说法错误；分析程序可知，无论key值是多少，循环结束后“i >j”一定成立，故本题选B选项；如果key值为55，那么该程序段运行后，变量n的值为3，选项C说法错误；如果key值为40，那么该程序段运行后，变量m的值为6，选项D说法错误。
12．D
【详解】本题主要考查对分查找算法。第1次搜索区间的长度为1，第2次搜索区间的长度为1/2，第3次搜索区间的长度为1/22，……，第11次搜索区间的长度为1/210，故本题选D选项。
13．B
【详解】本题主要考查对分查找算法。设i=1，j=7，m=(1+7)//2=4，则第一次访问的数据是18；23>18，i=m+1=5，m=(5+7)/2=6，则第二次访问的数据是21；23>21，i=m+1=7，m=(5+7)/2=7，则第三次访问的数据是23，查找结束，故依次被访问到的数据是18，21，23，故本题选B选项。
14．C
【详解】本题主要考查对分查找算法。对具有n个元素的有序数组进行二分法查找，最多需要比较log2(n)+1次。对1万条商品资料记录进行对分查找，最多需要log2(10000)+1=14次，从中取出一条记录并与待查项进行比较所花的时间为20毫秒，则最多花费的时间约为14*20=280毫秒，故本题选C选项。
15．C
【详解】本题主要考查对分查找算法。使用对分查找访问到的数分别为：19、41、23。使用顺序查找法访问的数分别是：2、3、6、11、19、23，故本题选C选项。
答案第1页，共2页
答案第1页，共2页