3.3 数据的查找同步训练-2023-2024学年高二信息技术教科版（2019）选择性必修1

教科版（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”，key<a(5)，j=m-1=4；第二遍循环，m=(1+4)\2=2，s=“52”，key<a(2)，j=m-1=3；第三遍循环，m=(1+3)\2=2，s=“522”，key<a(2)，j=m-1=2；第四遍循环，m=(1+2)\2=1，s=“521”，key<a(1)，j=m-1=1；第五遍循环，m=(1+1)\2=1，s=“5211”，key<a(1)，j=m-1=0，退出循环，flag=True，执行s="没有找到"，故Label1中显示的是没有找到，故本题选A选项。 7．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，key<a(4)，j=m-1=3；第二遍循环，满足i<=j，p=p+1=2，m= (1 + 3) \ 2=2，key>a(2），i=m+1=3；第三遍循环，满足i<=j，p=p+1=3，m= (3+ 3) \ 2=3，key<a(3)，j=m-1=2，退出循环。程序执行完毕后，i=3，j=2，m=3，p=3，故本题选C选项。 8．C 【详解】本题主要考查对分查找算法。i=1，j=7，key=60，第一遍循环，满足i<=j，m = (1+ 7) \ 2=4，key<a(4)，j=m-1=3，s=“L”，第二遍循环，满足i<=j，m = (1+ 3) \ 2=2，key>a(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=8<b(4)=32，j=m-1=3；第二遍循环，满足i<=j，m= Fix((0+3) / 2)=1，k=8=b(1)，退出循环，程序结束，经过该程序段“加工”查找编号为8的同学的过程中，依次被访问到的编号是32 8，故本题选C选项。 10．C 【详解】本题主要考查VB程序的执行。key=32，i=1，j=10，flag=False，第一遍循环，m = Fix((1+ 10) / 2)=5，key<a(5)，i=m+1=6；第二遍循环，m = Fix((6+ 10) / 2)=8，key>a(8)，j=m-1=7；第三遍循环，m = Fix((6+ 7) / 2)=6，key<a(6)，i=m+1=7；第四遍循环，m = Fix((7+ 7) / 2)=7，key<a(6)，i=m+1=8，退出循环，故运行程序段后，flag=False，m=7，i=8，j=7，故本题选C选项。 11．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页 学科网（北京）股份有限公司 $$