2023-2024学年高二上学期浙教版(2019)选修一5.4 数据查找 同步练习（含答案）

2023-2024学年高二上学期浙教版(2019)选修一5.4 数据查找 一、选择题 1．某论坛报名参加免费泰国游的网友序列号为101、135、238、342、450、558、633、708、846、910，采用对分查找，查找序列号为846号网友信息的过程中，依次被访问的序列号是（ ） A．450、708、846 B．450、708、910、846 C．558、708、846 D．558、708、910、846 2．某对分查找算法的python程序如下： 数组a中的元素各不相同且按降序排列，执行该程序段后n的值为4，则key的值不可能为（ ） A．a[1] B．a[4] C．a[12] D．a[16] 3．二分搜索法在有序数组中查找数据的复杂度是多少？（ ） A．O(1) B．O(log n) C．O(n) D．O(n^2) 4．采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为（ ） A．O(log2n) B．O(n2) C．O(nlog2n) D．O(n) 5．如下Python程序段： import random a=[1,3,5,7,9,11,13,15] key=random.randint(1,8)*2 i,j=0,len(a)-1 s=0 while i<=j: m=(i+j+1)//2 if a[m]==key: break if a[m]>key: j=m-1;s-=1 else: i=m+1;s+=1 print(s) 上述程序执行完以后，s的值有几种可能（ ） A．4种 B．5种 C．7种 D．8种 6．有某算法的程序段如下： 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 7．在实现查找算法时，以下哪种算法适用于无序列表（ ） A．顺序查找 B．二分查找 C．哈希查找 D．线性查找 8．插值查找是一种改进的二分查找算法，它适用于（ ） A．有序数组 B．无序数组 C．有序链表 D．无序链表 9．采用二分查找方法，在1-100中查找53需要比较（ ）次。 left=l right = 100 cnt=0 while left<=right: mid=(left+right)//2 cnt +=i if mid==53: Break elif mid<53: left = mid+1 else: right = mid-1 print("采用二分查找方法,在1-100中查找53需要比较()次".format(cnt)) A．5 B．6 C．7 D．8 10．在序列[2,4,6,7,8]中查找4，使用顺序查找的算法，需要对比（ ）次才能找到。 A．1 B．2 C．3 D．4 11．某二分查找算法的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 12．哈希表查找的平均时间复杂度是（ ） A．O(n) B．O(n^2) C．O(logn) D．O(1) 13．数据1~100升序排列，若用二分查找该范围内的数据78，最少需要查找的次数为（ ） A．3 B．5 C．20 D．78 14．哈希表查找的时间复杂度接近于（ ） A．O(n) B．O(n^2) C．O(logn) D．O(1) 15．在序列 [2,4,6,7,8] 中查找4，使用顺序查找的算法，第一轮和（ ）进行比较。（ ） A．2 B．4 C．6 D．8 二、填空题 16．哈希表查找是一种基于哈希表的查找算法，它的基本思想是将目标值通过哈希函数映射到哈希表的某个位置，然后在该位置查找目标值。哈希表查找的平均时间复杂度为 。 17．递增数列用二分法查找时，先以 位置的元素作为比较对象，如果要找的元素值小于该中点元素，则将待查序列 为左半部分，否则为右半部分。每一次比较后都可以将查找区间缩小一半。 18．在无序数组中查找数据时，如果不使用排序算法， ... ...