資源簡介

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．在實際應用中，選擇合適的查找算法需要考慮數據結構的特點、查找效率、空間復雜度和實現難度等因素。對于無序數組，可以選擇順序查找；對于有序數組，可以選擇二分查找或插值查找；對于需要快速查找的場景，可以選擇哈希表查找。

展開更多......

收起↑