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

教科版（2019）选修一3.3数据的查找同步作业 学校:___________姓名：___________班级：___________考号：___________ 一、选择题 1．某对分查找算法的python程序如下： 数组a中的元素各不相同且按降序排列，执行该程序段后n的值为4，则key的值不可能为（   ） A．a[1] B．a[4] C．a[12] D．a[16] 2．有如下Python程序段 k=int(input());s="" left,right=0,len(a)-1 while left<=right:     m=(left+right)//2     if a[m] < k:         left=m+1         s=s+"R"     else:         right=m-1         s=s+"L" 已知数组a中的值为[10,15,32,32,45,53,53,65,77,98]，程序运行后，变量s的值可能是（  ） A．"LR" B．"LRL" C．"LRR" D．"RLR" 3．某算法的VB程序段如下： key=randint（0，3）*2+13 i，j，c=0，len（a）–1，0 while i<=j： m=（i+j+1）//2 if a［m］>=key： i=m+1 else： j=m-1 c+=1 列表a=［23，21，19，18，16，15，14，11］，该程序段执行后，下列说法不正确的是（   ） A．i的值为j+1 B．i的值可能是8 C．j的值可能是5 D．c的值一定是3 4．用二分查找法查找列表[3，9，16，25，33，47，56]中的数字33，需要查找（    ）次 A．1 B．2 C．3 D．4 5．某二分查找算法的Python程序段如下： a=[14, 17, 18, 19, 19, 22, 22, 22, 28, 28] s=0 key=int(input ("key:")) L, R=0, len(a)-1 while L<=R:     m=(L+R)//2     s+=1     if a[m]>key:       R=m-l     else:       L=m+1 当输入key的值为22，程序运行结束后，下列描述不正确的是（    ） A．m的值是7 B．s的值是3 C．L的值是8 D．R的值是7 6．某二分查找算法的Python程序段如下： list1=["Carrot","Celery","Garlic","Lettuce","Mooli","Onion","Potato","Tomato"] key＝list1[2] left，right＝0，len(list1)－1 c＝0 while left<＝right： m＝(left＋right)//2 c＝c＋1 if list1[m]>key： right＝m－1 else： left＝m＋1 print(list1[left]) 程序执行后，下列说法正确的是(　　) A．变量c的值为4 B．程序输出的结果为Lettuce C．变量left的值为2 D．变量right的值为3 7．小明和小华玩猜数字的游戏，所猜数字不超过800，小明首先猜400，小华说大了，小明又猜200，当小华再次说大了，小明猜100，当小华说小了，小明猜150，以此类推，直到猜到正确的数字。上述方法中蕴含的算法思想是（   ） A．穷举算法 B．递归算法 C．二分查找法 D．顺序查找法 8．某同学在做物理实验时，需要用天平测量物品的质量，过程如下：先放置200克砝码，若砝码偏重；再将砝码改为100克,若砝码偏轻；再将砝码改为150克，砝码偏重；再将砝码改为125克……以此类推。通过这种策略，该同学完成了物品的称重。此过程借鉴的算法思想是(  ) A．排序 B．二分查找 C．顺序查找 D．枚举 9．某对分查找算法的 Python 程序段如下： a = [8, 17, 24, 30, 36, 40, 55, 58, 61, 66] L, R = 0, 9 s = [] key = int(input("请输入要查找的数据：")) while L <= R:     m = (L + R + 1) // 2     if a[m] == key:         break     elif a[m] > key:         R = m - 1     else:         L = m + 1     s.append(a[m]) print(s) 执行该程序段，当输入的值为30时，程序输出的结果是 A．[40, 24] B．[40, 24, 36] C．[24, 36] D．[36, 17, 24] 10．下列程序实现了输入k，找出大于k的数据的起始索引位置并显示 a=[1,3,3,5,5,7,10,11,12,15] n=10 k=int(input()) i=-1 j= while i < j:     m=(i+j+1)//2     if k < a[m]:         j=     else:         i=m L= print(">",k,"的数据索引起始位置为",L) 上述程序段横线处语句依次为（     ） A．n  m-1  i B．n-1  m-1  i+1 C．n  m+1  i D．n-1  m+1  i+1 11．小华玩猜价格游戏，已知价格的范围在 1 元到 200 元之间。他第一次猜 100 元，太低；第二次猜 150元，太高；第三次猜 125 元，又太低；……，小明在猜价格时采用的方法是（ ）。 A．顺序查找 B．随机查找 C．对分查找 D．排序查找 12．有如下程序： a=[3,5,8,11,13,15,16,20,25,30] i,j,x=0,9,20 while i<=j:     m=(i+j)//2     if x==a[m]:         break     if x < a[m]:         j=m-1     else:         i=m+1 该程序段运行后，下列表达式为True的是（    ） A．i==m+1 B．j==m-1 C．j>m+1 D．i=m-1 13．有某算法的程序段如下： i = 0; j = 6; s = “” key = int( random( ) * 100 ) while i <= j: m = ( i + j ) // 2 if key == p[ m ]:     s +=” M ”     break elif key < p[ m ]:     j = m - 1     s += “ L ” else:     i = m+1     s += ” R ” print( s ) 列表p中的元素依次为“24， 35， 38， 41， 45， 69， 78”。执行该程序段后，计算机显示的内容可能为（） A．RL B．LMR C．RLR D．LRLM 14．阅读下列用二分法查找输入的1000以内的整数次数的程序 x=int(input("请输入要查找的1000以内的整数:")) step=0 flag1=1 flag2=1000 while(flag1<=flag2):     mid=①       step=step+1     if mid>x:         flag2=②           elif mid<x:         flag1=③         else:                break print("查找次数为："，step) input("运行完毕，请按回车键退出...") 下列说法正确的是（  ） A．①处填(flag1+flag2)/2，②处填mid-1，③处填mid+1 B．①处填(flag1+flag2)//2，②处填mid-1，③处填mid+1 C．①处填(flag1+flag2)//2，②处填mid+1，③处填 mid-1 D．以上都不对 15．对线性表进行二分查找时，要求线性表必须（  ） A．以顺序方式存储 B．以顺序方式存储，且数据元素有序 C．以链接方式存储 D．以链接方式存储，且数据元素有序 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．D 【详解】本题主要考查对分查找算法及Python程序实现。该对分查找过程用二叉树表示如下： 分析程序可知，每遍历一次，变量n递增1，同时当查找到时，循环结束。执行该程序段后n的值为4，由图可知，遍历到第四层，则key的值不可能为a[16]，故本题选D选项。 2．B 【详解】本题主要考查对分查找算法及Python程序实现。该查找过程用二叉树表示如下，分析程序可知，当遍历左子树时，执行 s=s+"R"；当遍历右子树时，执行 s=s+"L"。结合二叉树以及选项可知，程序运行后，变量s的值可能是"LRL"，故本题选B选项。 3．B 【详解】本题主要考查二分查找及Python程序实现。key=randint（0，3）*2+13，可知key依次取的值是0、15、17、19，第一次查找，m=4，a(4)=16，如果向右查找，则i=m+1=5，进行第二次查找m=6，a(6)=14，若key=0，则i=7，此时进行第三次查找，m=8，a(8)=11,11仍然大于0，更新i=m+1=9，故i的值不可能是8，故本题选B选项。 4．C 【详解】本题主要考查二分查找算法。用变量i和j分别表示列表数据的开始和结束位置，i=1，j=7。第一次查找：(i+j)//2=4，25<33，i=4+1=5；第二次查找：(i+j)//2=6，47>33，j=6-1=5；第三次查找：(i+j)//2=33，故需要查找3次，故本题选C选项。 5．A 【详解】本题主要考查二分查找及Python程序实现。该二分查找用二叉树表示如下，因为列表a中有3个22，可知程序运行结束后，m的值一定不为7，故本题选A选项。 6．B 【详解】本题主要考查二分查找算法及Python程序实现。已知left=0，right=7，key="Garlleftc"，第一次查找m=(left+right) //2=3，c=c+1=1，a (3) ="Lettuce"，判断list1[m] > key成立，执行right=m-1=2；第二次查找m= (left+right) //2=1， c=c+1=2， a (2)= "Garlleftc"，判断list1[m] > key不成立，执行left=m+1=2；第三次查找m= (left+right) //2=2，c=c+1=3，a (2) ="Garlleftc"，判断list1[m] > key不成立，执行left=m+1=3；此时left=3，right=2不在满足循环条件，输出list1[3]= "Lettuce"，c的值为3，left=3，right=2，故本题选B选项。 7．C 【详解】本题主要考查二分查找算法。二分查找(Binary Search)算法，也叫折半查找算法。二分查找的思想非常简单，有点类似分治的思想。二分查找针对的是一个有序的数据集合，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。分析题干可知，上述方法中蕴含的算法思想是二分查找法，故本题选C选项。 8．B 【详解】本题主要考查二分查找算法。二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2]，则只要在数组a的左半部搜索x；如果x>a[n/2],则只要在数组a的右半部搜索x，由题干可知，此过程借鉴的算法思想是二分查找，故本题选B选项。 9．B 【详解】本题主要考查对分查找算法及Python程序实现。当输入的值为30时，第一次循环，m = (L + R + 1) // 2=5，a[5]=40>key，R=m-1=4， s.append(a[m])=[40]；第二次循环，m = (L + R + 1) // 2=2，a[2]=24<key，L=m+1=3， s.append(a[m])=[40，24]；第三次循环，m = (L + R + 1) // 2=4，a[4]=36>key，R=m-1=3，s.append(a[m])=[40，24，36]；第四次循环，m = (L + R + 1) // 2=3，a[3]=30=key，循环结束，故程序输出的结果是[40, 24, 36]，故本题选B选项。 10．B 【详解】本题主要考查对分查找算法及Python程序实现。列表的索引从0开始，i是左端点，j是右端点，m=(i+j+1)//2，故j的初值为n-1；如果k < a[m]，说明k在a[m]的左边，应更新j=m-1，否则说明k在a[m]的右边，应更新i=m。找出大于k的数据的起始索引位置，循环结束后，查找到的起始索引值应在i的右边，即i+1，故本题选B选项。 11．C 【详解】本题考查的是查找算法。对分查找首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找;在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。故本题应选C。 12．C 【详解】本题主要考查对分查找算法。该查找过程用二叉树表示如下，当查找到20时，此时m=7，i=5，j=9，满足j>m+1，故本题选C选项。 13．C 【详解】本题主要考查二分查找及Python程序实现。分析程序可知，当不满足key==p[m]时，循环执行次数大于2，故选项A不可能，同理当满足if判断条件，执行 s +="M"后退出循环，故选项B也不可能。验证选项C，当45<key<69时，i=m+1=4，s=s+"R"="R"，m= (4+6) // 2=5，p[5]=69，j=m-1=4，s=s+"L"="RL"，m= (4+4) // 2=4，a(4)=45，i=m+1=5，s=s+"R"="RLR"，退出循环条件，故选项C可能。同理选项D不可能，故本题选C选项。 14．B 【详解】本题主要考查二分查找及Python程序实现。flag1=1，flag2=1000，二分查找的中间位置mid=(flag1+flag2)//2，故①处填(flag1+flag2)//2， mid>x，说明要查找的x在mid的左边，需要更新flag2=mid-1，否则更新flag1=mid+1，故②处填mid-1，③处填mid+1，故本题选B选项。 15．B 【详解】本题主要考查二分查找及线性表。对线性表进行二分查找时，要求线性表必须以顺序方式存储，且数据元素有序，故本题选B选项。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$