資源簡(jiǎn)介

專題18　查找算法
知識(shí)點(diǎn)一　二分查找的算法思想
1.有如Python程序段：
import random
def find(x，y)：
m＝(x＋y＋1)//2
if a[m]＝＝key：
return m
if a[m]>key：
y＝m－1
else：
x＝m＋1
return find (x，y)
a＝[2，4，6，8，10，12，14，16]
key＝random.choice(a)　#從序列的元素中隨機(jī)挑選一個(gè)元素
i＝0；j＝len(a)－ 1
xb＝find(i，j)
print(xb，key)
上述程序執(zhí)行完后，函數(shù)find被調(diào)用的最多次數(shù)是(　　)
A.3 B.4
C.5 D.6
2.某對(duì)分查找算法的Python程序如下：
f＝[0]*20
i＝0；j＝19；n＝0；m＝0
while i<＝j(luò) and f[m]＝＝0：
m＝(i＋j＋1)//2
n＝n＋1
if a[m]＝＝key：
f[m]＝1
elif a[m]j＝m－ 1
else：
i＝m＋1
數(shù)組a中的元素各不相同且按降序排列，執(zhí)行該程序段后n的值為4，則key的值不可能為(　　)
A.a[1] B.a[4] C.a[12] D.a[16]
3.有如下Python代碼：
n＝int(input(″請(qǐng)輸入一個(gè)數(shù)：″))
a＝[i for i in range(n)]
c＝0
for i in range(1，n)：
L＝1；R＝i－1
while L<＝R：
m＝(L＋R)//2
if a[i]*a[m]＝＝n：
　　　　 c＋＝1
　　　 　break
elif a[i]*a[m]　　 　　L＝m＋1
else：
　　 　　R＝m－1
print(c)
輸入36，執(zhí)行程序后，輸出結(jié)果是(　　)
A.1 B.2 C.3 D.4
4.某二分查找算法的程序段如下：
key＝int(input('待查數(shù)據(jù)為：'))
i＝0；j＝10；n＝0
while i<＝j(luò)：
m＝(i＋j＋1)//2
if a[m]＝＝key：
break
elif a[m]>key：
j＝m－1；n＝n－1
else：
i＝m＋1；n＝n＋1
執(zhí)行該程序段后，下列說(shuō)法正確的是(　　)
A.該程序若要實(shí)現(xiàn)對(duì)分查找，要求數(shù)組a按降序排列
B.若n為－2，則查找key值可能等于a[3]的值
C.若n為2，則查找 key 的值可能小于a[10]
D.n的值最小為－4，最大為4
5.有如下Python程序：
a＝[83，80，66，46，44，36，21，16，15，12]
key＝int(input(″輸入要查找的數(shù)：″))
i＝0；j＝9
ans＝″″
while i<＝j(luò)：
m＝(i＋j＋1)//2
if key＝＝a[m]：
break
elif key>a[m]：
j＝m－1
else：
i＝m＋1
ans＝ans＋str(a[m])＋″ ″
print(ans)
執(zhí)行該程序，輸入 80，則輸出的結(jié)果是(　　)
A.36 66 B.44 80
C.36 46 D.44 66
6.某二分查找算法的Python程序段如下：
i，j＝0，24
n＝0
while i<＝j(luò)：
m＝(i＋j＋1)//2
n＝n＋1
if key＝＝a[m]：
break
if key>a[m]：
i＝m＋1
else：
j＝m－1
print(n)
列表a中各元素值依次為1～25，若查找鍵key為下列選項(xiàng)的值，程序段執(zhí)行后，輸出結(jié)果與其他三項(xiàng)不同的是(　　)
A.7 B.12
C.19 D.22
7.如下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(luò)：
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)
上述程序執(zhí)行完以后，s 的值可能有(　　)
A.4種 B.5種
C.7種 D.8種
8.小明為英文字母A～Z定義了一套全新的二進(jìn)制編碼規(guī)則，代碼如下
s＝[chr(i＋65)for i in range(26)]
dc＝{}
for k in s：
i＝0
j＝len(s)－1
rt＝″0″
while i<＝j(luò)：
m＝(i＋j)//2
if s[m]＝＝k：
　　　 　dc[k]＝rt
　　　 　break
elif s[m]　　 　　i＝m＋1
　　　 　rt＋＝″1″
else：
　　　　 j＝m－1
　　　　 rt＋＝″0″
inp＝input(″請(qǐng)輸入英文字符串：″).upper()#將輸入的英文字母轉(zhuǎn)為大寫
for c in inp：
print(dc[c]，end＝″ ″)
當(dāng)程序運(yùn)行后，輸入“OK”后，其輸出的二進(jìn)制編碼為(　　)
A.01001 0011 B.01001 000
C.00001 0011 D.01001 00110
9.有如下Python程序段：
def binSearch(i，j，key)：
if i>j：
return 0
m＝(i＋j)//2
if key＝＝a[m]：
return m
if keyreturn binSearch(i，m－1，key)＋m
return binSearch(m＋1，j，key)＋m
n＝7
a＝[5，6，7，8，9，9，11]
key＝int(input(″輸入查找鍵：″))
print(binSearch(0，n－1，key))
執(zhí)行該程序段后，輸入待查找的數(shù)，輸出的結(jié)果不可能是(　　)
A.6 B.8 C.12 D.14
10.有如下Python程序段：
from random import randint
k＝randint(0，2)*2
i＝0；j＝6；cnt＝0
while i<＝j(luò)：
cnt＝cnt＋1
m＝(i＋j)//2
if a[m]＝＝a[k]：
break
if a[m]i＝m＋1
else：
j＝m－1
數(shù)組元素 a[0]到 a[6]各不相同且按升序排列，執(zhí)行該程序段，下列說(shuō)法不正確的是(　　)
A.m的值不可能為6 B.cnt的值一定為3
C.變量i、j的值一定相同 D.i的值可能小于m
11.有如下Python程序段：
def find_base(x，y)：
left，right＝2，10
while left<＝right：
mid＝(left＋right)//2
value＝calc(mid，y)　#calc函數(shù)將mid進(jìn)制的整數(shù)y轉(zhuǎn)化為十進(jìn)制數(shù)
if value＝＝x：
　　　 　return mid
elif value　　　 　left＝mid＋1
else：
　　 　　right＝mid－1
return －1
x＝int(input())；y＝int(input())
print(find_base(x，y))
執(zhí)行該程序段后，依次輸入83和123，程序輸出為(　　)
A.2 B.6
C.8 D.－1
12.某二分查找算法的Python程序段如下：
n＝0；flag＝True
key＝int(input(″輸入要查找的數(shù)：″))
i，j＝0，9
while i<＝j(luò) and flag：
m＝(i＋j) //2
if a[m]＝＝key：
flag＝False
elif a[m]i＝m＋1
n＝n＋1
else：
j＝m－1
n－＝1
若列表a中的元素依次是[5，11，18，23，27，33，34，41，45，69]，程序運(yùn)行后變量n的值是2，則輸入的整數(shù)key值不可能是(　　)
A.25 B.34
C.45 D.60
知識(shí)點(diǎn)二　極值查找
1.有如下Python程序段：
import random
a＝[1，3，4，6，6，6，9，9，11，12]
key＝random.randint(2，5)*2
i，j＝0，9
while i<＝j(luò)：
m＝(i＋j)//2
if keyj＝m－1
else：
i＝m＋1
print(j)
執(zhí)行該程序段后，輸出的結(jié)果不可能是(　　)
A.2 B.3
C.5 D.7
2.有如下Python程序段：
a＝[34，35，38，41，41，41，45，45，69，78]
key＝41；n＝0
i＝0；j＝9
while i<＝j(luò)：
m＝(i＋j)//2
if keyj＝m－1
else：
i＝m＋1
該程序段運(yùn)行結(jié)束后，下列說(shuō)法正確的是(　　)
A.i的值是3 B.j的值是3
C.i的值是6 D.j的值是6
3.有如下Python程序段：
d＝[1，3，8，15，22，26，28，40，46，61，80]
i＝0；j＝len(d)－1
while i<＝j(luò)：
m＝(i＋j)//2
if keyj＝m－1
else：
　 　
若key值為22，程序運(yùn)行結(jié)束后，加框處語(yǔ)句執(zhí)行的次數(shù)為(　　)
A.1 B.2
C.3 D.4
4.有如下Python程序段：
a＝[3，8，12，17，19，21，23，25，27]
i，j＝0，8
c，key＝0，21
while i<＝j(luò)：
c＋＝1
m＝(i＋j)//2
if a[m]>key：
j＝m－1
else：
i＝m＋1
上述程序段執(zhí)行結(jié)束，下列運(yùn)行結(jié)果不正確的是(　　)
A.i的值為6 B.c的值為3
C.m的值為6 D.j的值為5
5.執(zhí)行如下程序段：
from random import randint
a＝[2，3，3，5，9，10，13，13，15，19]
i，j，c＝0，9，0
key＝randint(0，10)
if key>5：key＝key＋5
while i<＝j(luò)：
m＝(i＋j)//2
c＋＝1
if a[m]>key：
j＝m－1
else：
i＝m＋1
下列說(shuō)法正確的是(　　)
A.變量c的值一定是4 B.變量i的值可能是7
C.a[i]的值可能等于key D.變量m和變量j的值可能相等
6.列表中有n個(gè)非降序的數(shù)字元素，即s[0]<＝s[1]<＝s[2]<＝…<＝s[n－1]的列表中，執(zhí)行如下程序段：
i＝0；j＝n－1
key＝int(input(″輸入一個(gè)要查找的數(shù)：″))
while i<＝j(luò)：
m＝(i＋j)//2
if s[m]>key：
j＝m－1
else：
i＝m＋1
print(s[m]，end＝″，″)
執(zhí)行該程序，輸出結(jié)果key，x，key(x和key不相等)，說(shuō)法錯(cuò)誤的是(　　)
A.x是比key小的數(shù) B.x是比key大的數(shù)
C.其列表中最少有6個(gè)元素 D.其列表中最多有9個(gè)元素
7.有如下Python程序：
a＝[0，20，23，23，24，24，31，48，49，73，75]
key＝int(input())
c＝0
i，j＝1，10
while i<＝j(luò)：
m＝(i＋j)//2
if a[m]<＝key：
i＝m＋1
else：
j＝m－1
c＋＝1
print(c)
若程序運(yùn)行后，輸出的結(jié)果是3，則輸入的key可能是(　　)
A.20或73 B.24或49
C.23或24 D.23或49
8.列表a和列表b均有5個(gè)從小到大排列的整數(shù)元素，且列表a的最后一個(gè)元素大于列表b的最后一個(gè)元素。有如下Python程序段：
c＝0
i＝0；j＝len(a)－1
for key in b：
while i<＝j(luò)：
m＝(i＋j)//2；c＋＝1
if key　　　　 j＝m－1
else：
　　　　 i＝m＋1
a＝a[：i]＋[key]＋a[i：]
i＋＝1；j＝len(a)－1
執(zhí)行該程序段后，c的值至少是(　　)
A.5 B.6
C.10 D.20
9.有如下Python程序段：
import random
a＝[2，3，5，8，10，10，10，17，19，20]
key＝random.randint(1，30)　#隨機(jī)生成[1，30]之間的整數(shù)
i，j＝0，9
while i<＝j(luò)：
m＝(i＋j)//2
if a[m]>key：
j＝m－1
else：
i＝m＋1
print(j)
執(zhí)行該程序段，下列說(shuō)法正確的是(　　)
A.若key的值為10，則輸出的值為3
B.若輸出的值為8，則key的值一定為19
C.對(duì)于任意key值，語(yǔ)句“m＝(i＋j)//2”最少執(zhí)行1次
D.對(duì)于任意key值，語(yǔ)句“m＝(i＋j)//2”最多執(zhí)行3次
10.有如下Python程序段：
a＝[5，14，3，12，6，7，3，9，20，1]
l＝min(a)；r＝max(a)　#min取列表最小值，max取列表最大值
maxi＝3
while l<＝r：
mid＝(l＋r)//2
cnt＝0
for i in a：
if mid　 　　　cnt＋＝1
if cntr＝mid－1
else：
l＝mid＋1
上述程序段執(zhí)行結(jié)束，下列說(shuō)法正確的是(　　)
A.a列表中第3大的數(shù)r B.cnt的值為2
C.l的值為12 D.mid＝(l＋r)//2代碼執(zhí)行3次
專題18　查找算法
知識(shí)點(diǎn)一
1.B　[本題考查二分查找、自定義函數(shù)的綜合應(yīng)用。由“key＝random.choice(a)”可知查找鍵key是一定可以找得到的，由題中算法可知，找到最少找1次，最多找int(log2n)＋1次，本題中序列a中共有8個(gè)成員，則最多找4次。]
2.D　[本題考查二分算法以及二分判定樹(shù)。根據(jù)本題代碼m＝(i＋j＋1)//2，畫出二分判定樹(shù)，位于二分判定樹(shù)第4層的節(jié)點(diǎn)下標(biāo)分別是1、4、7、9、12、14、17、19所以key的值不可能是a[16]。]
3.C　[本題考查二分查找。程序的功能是是數(shù)組a的i索引前找一個(gè)數(shù)，滿足a[i]*a[m]＝＝n的個(gè)數(shù)，因此分別是9*4、12*3、18*2。]
4.C　[本題考查二分查找算法。A選項(xiàng)由條件a[m]>key可以看出數(shù)組是升序。B選項(xiàng)查找a[3]需訪問(wèn)a[5]→a[2]→a[4]→a[3]，則n的值為－1。C選項(xiàng)由訪問(wèn)路徑a[5]→a[8]→a[10]→a[9]→end，則n的值為n值為2。D選項(xiàng)如果要n的值最小為－4，最大為4，至少節(jié)點(diǎn)數(shù)滿15個(gè)，本題節(jié)點(diǎn)數(shù)只有11個(gè)。]
5.A　[本題考查二分查找。m的值依次為5、2、1，當(dāng)找到key時(shí)，直接退出，沒(méi)有連接a[m]。]
6.A　[n的值為查找次數(shù)，7查找次數(shù)為2，其余查找次數(shù)是4。]
7.A　[本題考查對(duì)分查找。列表a中的元素為1－15中的奇數(shù)，查找的key為2－16中的偶數(shù)，所以查找的結(jié)果不存在a[m]＝＝key也就是找到的情況，break不會(huì)被執(zhí)行。查找的過(guò)程如下：s的值可能為－2，－1，1，3，共4種。]
8.A　[構(gòu)建一顆26個(gè)節(jié)點(diǎn)的升序二叉樹(shù)，由于26小于31，因此最多查找4次，用一個(gè)4位二進(jìn)制數(shù)存儲(chǔ)訪問(wèn)的節(jié)點(diǎn)(標(biāo)記為1)。]
9.B　[本題考查遞歸法求二分查找，找到后返回中間位置，沒(méi)有找到，累加找過(guò)的位置m。用索引位置畫出二叉樹(shù)為，沒(méi)有一條分支節(jié)點(diǎn)和為8。]
10.D　[本題考查二分查找的算法思想。查找的k值為0，2，4，即a[0]、a[2]、a[4]中的一個(gè)數(shù)，畫出判定二叉樹(shù)。由圖可知，查找次數(shù)cnt均為3次，m只能是0，2，4。查找的值發(fā)生在葉子節(jié)點(diǎn)，因此區(qū)間中只剩下最后一個(gè)數(shù)，i，j，m的值是相等的。]
11.C　[本題考查進(jìn)制轉(zhuǎn)換與二分查找。函數(shù)find_base(x，y)的功能為通過(guò)二分查找算法查找十進(jìn)制數(shù)x對(duì)應(yīng)另一進(jìn)制數(shù)y的基數(shù)，如果不存在則返回－1。由于123O＝83D，最后能夠找到對(duì)應(yīng)的基數(shù)為8。]
12.B　[本題考查二分查找算法。用二又搜索樹(shù)畫出各個(gè)元素的搜索順序，圖中各個(gè)左子樹(shù)方向可以讓n自減，右子樹(shù)方向可以讓n自增。A選項(xiàng)，若key＝25，則從節(jié)點(diǎn)23的右側(cè)出循環(huán)，此時(shí)m，n的值是3、2，同理key＝45，m，n的值是8、2，key＝60，m，n的值是9、2。key＝34，m，n的值是6、1。]
知識(shí)點(diǎn)二
1.B　[本題考查二分查找的算法思想。產(chǎn)生一個(gè)[4，10]之間的偶數(shù)，當(dāng)key＝＝a[m]時(shí)，沒(méi)有終止查找，還是繼續(xù)向右查找，直至i>j。A選項(xiàng)若key值為4，j的值為2；若key值為6和8，j的值為5；若key值為10，j的值為7。]
2.C　[本題考查二分查找。當(dāng)找到key時(shí)，沒(méi)有結(jié)束循環(huán)，而是向右繼續(xù)查找。最后一個(gè)41的索引位置為5，因此找到后，i向后查找，i的值是6。]
3.C　[查找的數(shù)據(jù)依次為26，8，15，22，找到8后連續(xù)兩次向右查找，但找到22后還是再一次查找，因此共找了3次。]
4.C　[本題考查右極值的查找，查找21，最后一次i，j，m的值均為5，找到后還要移動(dòng)i，因此i的值為6。]
5.D　[本題考查二分查找的算法思想。可查找的數(shù)為[0，5]或[11，15]之間的整數(shù)。找到后中途不能結(jié)束查找，還要繼續(xù)向右查找，當(dāng)key為2時(shí)，查找3次。B選項(xiàng)當(dāng)查找到13時(shí)不可結(jié)束循環(huán)，因此i的值不可能是7。C選項(xiàng)當(dāng)找到后還要向右查找，因此a[i]不可能是要查找的數(shù)。D選項(xiàng)查找結(jié)束后，a[j]可能是要查找的數(shù)，因此變量m和變量j的值可能相等。]
6.A　[本題考查對(duì)二分查找的算法實(shí)現(xiàn)。當(dāng)a>＝s[m]時(shí)向右查找，故x應(yīng)比a大。由“a，x，a”可知，該二分查找進(jìn)行了3次查找，即向右找1次，再向左找1次，則對(duì)應(yīng)二叉查找樹(shù)應(yīng)為3層或4層，當(dāng)有6個(gè)節(jié)點(diǎn)時(shí)，可實(shí)現(xiàn)3次查找。當(dāng)節(jié)點(diǎn)數(shù)增加到10個(gè)時(shí)，對(duì)應(yīng)第6個(gè)節(jié)點(diǎn)出現(xiàn)右子樹(shù)，繼續(xù)進(jìn)行查找，則進(jìn)行第4次查找。]
7.B　[本題考查二分查找。查找范圍是[1，10]，當(dāng)找到key時(shí)仍要往右邊查找，當(dāng)key＝20、24、49時(shí)，查找的次數(shù)是3，當(dāng)key＝23、31、73時(shí)，查找的次數(shù)是4。]
8.B　[本題考查二分查找及插入排序的算法實(shí)現(xiàn)。]
9.B　[本題考查二分查找，其中主要考查利用二分查找邊界。結(jié)束查找的條件是i>j，就算是找到，還是移到i繼續(xù)查找，因此程序的功能是查找右邊界。列表a的元素個(gè)數(shù)是10個(gè)，介于7～15之間，查找次數(shù)最少3次，最多4次。根據(jù)條件if a[m]>key，當(dāng)key＝10時(shí)，i＝7，j＝6，選項(xiàng)A錯(cuò)誤；j＝8，i＝9，對(duì)應(yīng)的元素分別是19，20，19＝10.C　[本題考查對(duì)分查找的算法實(shí)現(xiàn)。找出了列表中比mid值大的元素個(gè)數(shù)并用cnt進(jìn)行記錄，若cnt

展開(kāi)更多......

收起↑