资源简介

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．在无序数组中查找数据时，如果不使用排序算法，则只能使用 搜索。
19．在数组中查找数据的基本方法是 和 。
三、操作题
20．二分查找，完善下列程序代码。
x=int(input(“请输入要查找的1000以内的整数：”))
step=0
flag1=1
flag2=1000
while(flag1<=flag2):
mid=(flag1+flag2)//2
step=step+1
if mid>x:
elif midelse:
break
print(“查找的次数为：”,step)
四、简答题
21．举例说明如何在编程中实现线性搜索。
22．说明为什么在有序数组中查找数据比在无序数组中查找数据更高效。
23．论述在实际应用中如何选择合适的查找算法。
参考答案：
1．A
2．D
3．B
4．A
5．A
6．C
7．AD
8．A
9．A
10．B
11．B
12．D
13．B
14．D
15．A
16．O(1)
17． 中点 缩小
18．线性
19． 线性搜索 二分搜索
20． flag2=mid-1 flag1=mid+1
21．在编程中实现线性搜索，可以通过遍历数组并逐个比较元素来实现。例如，在Python中可以使用for循环来遍历数组并检查每个元素是否等于目标元素。
22．在有序数组中查找数据更高效，因为可以利用数组的顺序来加速搜索过程，如使用二分搜索法。而在无序数组中只能使用线性搜索，效率较低。
23．在实际应用中，选择合适的查找算法需要考虑数据结构的特点、查找效率、空间复杂度和实现难度等因素。对于无序数组，可以选择顺序查找；对于有序数组，可以选择二分查找或插值查找；对于需要快速查找的场景，可以选择哈希表查找。

展开更多......

收起↑