教科版（2019）选修一3.3数据的查找同步练习

教科版（2019）选修一3.3数据的查找同步练习 学校:___________姓名：___________班级：___________考号：___________ 一、选择题 1．二分查找又叫折半查找，该方法主要将数列有序排列，采用跳跃式的方式查找数据。二分搜索算法是利用（  ）实现的算法 A．分治法 B．动态规划 C．贪心法 D．回溯法 2．报名参加冬季越野赛跑的某班5位同学的学号为：5，8，11，33，45。利用二分查找，查找33号学生的过程中，依次被访问到的学号是（   ）。 A．5，11，33 B．8，33 C．11，45，33 D．11，33 3．二分查找又称折半直找，是种应用于有序数列的高效查找算法。下列数列中适合二分查找算法的是（  ） A．1，4，7，15，13 B．15，14，12，7，2，3 C．34，25，17，9，10，3 D．6，9，12，14，23，25 4．二分查找又称折半查找，是一种应用于有序数列的高效查找算法。下列数列中适合二分查找算法的是（   ） A．11  99  5  17  2  39 B．30  52  43  71  78  81 C．67  62  68  6   15   15 D．85  78  59  53  19  18 5．某对分查找算法如下： i=1:j=6:c=1 key=int（rnd*100+1） do while i <= j m=（i+j）\2 c=c+1 if key<d（m）then j=m-1 else i=m+1 1oop 数组d（1）~d（6）的值分别为“17，21，29，32，39，75”，则程序运行结束后，下列说法错误的是（    ） A．i=j+1是成立的 B．若key=21，则i=1 C．当key=32时，m=j是成立的 D．若key如果是38，那么m=4 6．有数组a，其奇数下标的元素是降序排序的奇数，偶数下标的元素是降序排序的偶数，依据对分查找思想，设计一个在数组a中查找数据key的程序。部分程序段如下： Key = Val(Text1.Text) i = 1: j = 10: flag = False Do While    m = Int((i + j) / 2 + 0.5)     If Then m = m - 1    If a(m) = Key Then         flag = True     ElseIf   Then        i = m + 2     Else         j = m - 2     End If Loop If Not flag Then     Text2.Text = "查无数据" Else     Text2.Text = "该数位置为" + Str(m) End If 方框①②③中的代码依次为（   ） A．①i <= j And Not flag ②Key Mod 2 + a(m) Mod 2 = 1  ③a(m) > Key B．①i <= j And Not flag ②Key Mod 2 <> a(m) Mod 2     ③a(m) < Key C．①i <= j Or Not flag  ②Key Mod 2 + a(m) Mod 2 = 1  ③a(m) > Key D．①i <= j Or Not flag  ②Key Mod 2 <> a(m) Mod 2     ③a(m) < Key 7．某VB程序段如下： n = 6 :i = 1 j = i+1 : key = a(i) Do While j <= n 　　If key = a(j) Then 　　　　k =i 　　　　Do While k < n 　　　　　　a(k)= a(k + 1):k = k + 1 　　　　Loop 　　　　key =a(j - 1): n = n - 1 　　Else 　　　　j = j + 1 　　End If Loop For i = 1 To n 　　List1.AddItem a(i) Next 数组元素a（1）到a（6）的值依次为 “a1，a3，a5，b3，a1，c1”，则经过该程序段“加工”后，列表框List1显示的项依次为（　　） A．“a3，a5，b3，a1，c1，c1” B．“a1，a3，a5，b3，c1，c1” C．“a3，a5，b3，a1，c1” D．“a1，a3，a5，b3，c1” 8．有如下VB程序段 a＝"access"：b＝"col"：s＝"" For i=1 To Len（b） L＝1：R＝Len（a） Do While L＜＝R m＝（L＋R）\2 If Mid（a，m，1）＞Mid（b，i，1）Then R＝m－1 Else L＝m＋1 Loop a＝Mid（a，1，R）＋Mid（b，i，1）＋Mid（a，L，Len（a）－L＋1） s＝s＋Str（L） Next i 上述程序执行后，变量s的值为（    ） A．4 5 5 B．4 6 6 C．2 5 5 D．2 6 6 9．已知数组a(1)到a(n)为非递减序列，使用对分查找算法在数组中查找最后一个不大于key的元素下标，若a(1)>key，则在Text2框中输出0。实现该算法的VB程序段如下： key=Val(Text1. Text) ① Do WhileL < R m=(L+R+1)\2 If a(m) < = key Then ② Else ③ End If Loop Text 2. text= ④ 以下说法正确的是（    ） A．①处可填写代码L=1:R=n B．②处可填写代码L=m+1或L=m C．③处可填写代码R=m-1或R=m D．④处可填写代码L或R 10．现有一个整数型数组a（下标1到n），其值的规律是先升序中间相等，之后降序。现要找到降序的拐点，如数列2、4、8、12、18、18、18、18、5、3，其降序的拐点为最后一个18所在的位置，即8号位置。部分程序如下： L=1:R=n Do While L<=R m=(L+R)\2 If ① Then R=m-1 Else L=m+1 End If Loop Text.text= ② 为实现上述功能，则程序中①、②处填写的代码是（    ） A．①a（m）>a（m+1）②Str（R） B．①a（m）>a（m+1）②Str（L） C．（m）>=a（m+1）②Str（R） D．①a（m）>=a（m+1）②Str（L） 11．某对分查找算法的VB程序段如下: key=Int(Rnd*20)+3 i=1:j=6:id=1 Do While i<=j     m=(i+j)\2     If key=a(m)Then Exit Do     If key〈a(m)Then         j=m-1:id=id*2     Else         i=m+1:id=id*2+1     End If Loop Labe11. Caption=Str(id) 数组元素a（1）到a（6）的值依次为“4，7，9，14，15，21”，执行该程序段后，标签Labell中显示的内容不可能的是（   ） A．4 B．7 C．13 D．15 12．有如下VB程序段： a(1) = 11 : a(2) = 14 : a(3) = 23 : a(4) = 23 : a(5) = 30 : a(6) = 42 key = Val(Text1.Text) L = 1 : R = 6 : x = 0 Randomize Do while L <= R     mid = Int(Rnd() * (R-L+1))+ L     If a(mid) = key Then         Exit Do     ElseIf a(mid) > key Then         R = mid - 1         x = x - 1     Else         L = mid + 1         x = x + 1     End If Loop If L <= R Then     Label1.Caption = "查找成功，" + "位置为" + str(mid) Else     Label1.Caption = "查找失败" End If 该程序执行后，在文本框Text1中输入23，则x的值不可能是（  ） A．-3 B．-2 C．1 D．2 13．有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．顺序查找肯定比对分查找效率低 14．某对分查找算法的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 15．某对分查找的程序代码如下 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 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．B 【详解】本题主要考查二分查找算法。动态规划算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解的处理算法。二分搜索算法根据搜索值会动态规划缩小搜索范围，故本题选B选项。 2．D 【详解】本题主要考查二分查找算法。设i=1，j=5，第一次查找m=(1+5)//2=3，a(3)=11<33，i=m+1=4；第二次循环，m=(4+5)//2=4，a(4)=33，查找结束，故依次被访问到的学号是11，33，故本题选D选项。 3．D 【详解】本题主要考查二分查找算法。二分查找又称折半直找，是种应用于有序数列的高效查找算法，6，9，12，14，23，25是升序序列，适合二分查找算法，故本题选D选项。 4．D 【详解】本题主要考查二分查找算法。二分查找适合用于有序的数列，故85 78 59 53 19 18（降序序列）适合二分查找算分，故本题选D选项。 5．B 【详解】本题主要考查对分查找。此题需要画出二叉树。数组为递增的有序数列，根据算法要求有可能出现i=j+1，因此A选项正确；key=21时，发生指针跳转，因此B选项符合题意；key=32时，m=3，i=m+1，然后m=5，j=m-1，然后m=4，m=j成立，因此C选项正确；key=38时，根据算法要求，查找失败，且m=4，因此D选项正确。 【点睛】 6．B 【详解】本题主要考查数据查找。①数据查找的循环条件是i小于等于j，并且flag为False，故此处填i <= j And Not flag。②如果Key Mod 2 <> a(m) Mod 2，则key与a(m)的奇偶性不同，则m递减1，故此处填Key Mod 2 <> a(m) Mod 2。③当a(m) < Key时，表明key在a(m)的右边，执行i=m+2，否则执行j=m-2，故此处填a(m) < Key，故本题选B选项。 7．C 【详解】本题主要考查VB程序的执行。n=6，i=1，j=i+1=2，key=a(1)=a1，j=5时，key=a(5)=a1，k=i=1，执行完内层循环后，a(1)=a(2)=a3，a(2)=a(3)=a5，a(3)=a(4)=b3，a(4)=a(5)=a1，a(5)=a(6)=c1，key=a(4)=a1，n=n-1=5，j=j+1=6，退出while循环，最后一个for循环中，输出a(1)~a(5)，故经过该程序段“加工”后，列表框List1显示的项依次为“a3，a5，b3，a1，c1”，故本题选C选项。 8．B 【详解】本题主要考查VB程序的执行。a="access"，b＝"col"，s＝""，Len(b)=3，i=1，L=1，R=Len(a)=6，执行完while循环后，L=4，R=3，a="acccess"，s＝s＋Str(L)="4"；i=2时，L=1，R=7，执行完while循环后，L=6，R=5，a="accceoss"，s＝s＋Str(L)="4 6"；i=3时，L=1，R=8，执行完while循环后，L=6，R=5，s＝s＋Str(L)="4 6 6"，故上述程序执行后，变量s的值为4 6 6，故本题选B选项。 9．D 【详解】本题主要考查对分查找算分。①处是初始化L和R，由m=(L+R+1)\2，可知，此处填写代码是L=0，R=n。②如果a(m) < = key，则key在右边，故此处填L=m。③如果a(m) > key，则key在左边，故此处填R=m-1。④循环结束完，即找到最后一个不大于key的元素下标，即L或R，故此处填L或R，故本题选D选项。 10．B 【详解】本题主要考查对分查找算法。要判断降序的拐点，即判断是否a（m）>a（m+1），若是，则表明拐点在左边，执行R=m-1，否则，拐点在右边，执行L=m+1，循环结束，L的位置即为拐点的位置，故程序中①、②处填写的代码是a（m）>a（m+1），Str（L），故本题选B选项。 11．C 【详解】本题主要考查对分查找算法。key=Int(Rnd*20)+3，key是随机生成[3,22]之间的整数，第一种情况，当key=3，经过程序执行，id=4；第二种情况，当key=21，经过程序执行，id=7；第三种情况，当key=22，经过程序执行，id=15。故执行该程序段后，标签Labell中显示的内容不可能的是13，故本题选C选项。 12．A 【详解】本题主要考查VB程序查找算法。key=23，L=1，R=6，x=0，第一种情况：mid = Int(Rnd() * (6-1+1))+ 1，mid是随机生成[1,6]之间的整数，当mid=1时，a(1)<key，L=mid+1=2，x=x+1=1，继续循环，mid = Int(Rnd() * (6-2+1))+ 2，mid是随机生成[2,6]之间的整数，当mid=2时，a(2)<key，L=mid+1=3，x=x+1=2，继续循环，当mid=3时，程序结束，故x可能是2；第二种情况：当mid = Int(Rnd() * (6-1+1))+ 1，mid是随机生成[1,6]之间的整数，当mid=2时，a(mid)<key，L=mid+1=3，x=x+1=1，继续循环，mid = Int(Rnd() * (6-3+1))+3，mid是随机生成[3,6]之间的整数，当mid=3时，程序结束，故x可能是1；第三种情况：当mid = Int(Rnd() * (6-1+1))+ 1，mid是随机生成[1,6]之间的整数，当mid=5时，a(5)>key，R=mid-1=4，x=x-1=-1，继续循环，mid= Int(Rnd() * (4-3+1))+3，mid是随机生成[3,4]之间的整数，当mid=4时，程序结束，故x可能是-1；第四种情况：当mid = Int(Rnd() * (6-1+1))+ 1，mid是随机生成[1,6]之间的整数，当mid=6时，a(6)>key，R=mid-1=5，x=x-1=-1，继续循环，mid = Int(Rnd() * (5-3+1))+3，mid是随机生成[3,5]之间的整数，当mid=5时，a(5)>key，R=mid-1=4，x=x-1=-2，继续循环，mid = Int(Rnd() * (4-3+1))+3，mid是随机生成[3,4]之间的整数，当mid=4时，程序结束，故x可能是-2。故该程序执行后，在文本框Text1中输入23，则x的值不可能是-3，故本题选A选项。 13．C 【详解】本题考查查找算法相关知识。数据19虽然不在数组a（1 to 10）中，仍旧可对其进行查找，只是查找结果是找不到，选项A错误；数组a是无序数组，无法采用对分查找，对分查找是数组必须是有序排列的，选项B错误；最多经过10次比较，肯定能得出查找结论，选项C正确；若查找元素是第一个，则顺序查找比对分查找效率高，选项D错误。故本题正确的是选项C的说法。 14．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。 15．C 【详解】本题主要考查对分查找。对分查找首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。题中a数组共10个元素，所查找数据Key = Int(Rnd * 25) * 2，由此可知，key取值范围为0-48之间的偶数，则程序执行结束后，n的值不可能为-2，因此C选项正确。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$