资源简介

专题18　查找算法
知识点一　二分查找的算法思想
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)　#从序列的元素中随机挑选一个元素
i＝0；j＝len(a)－ 1
xb＝find(i，j)
print(xb，key)
上述程序执行完后，函数find被调用的最多次数是(　　)
A.3 B.4
C.5 D.6
2.某对分查找算法的Python程序如下：
f＝[0]*20
i＝0；j＝19；n＝0；m＝0
while i<＝j 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
数组a中的元素各不相同且按降序排列，执行该程序段后n的值为4，则key的值不可能为(　　)
A.a[1] B.a[4] C.a[12] D.a[16]
3.有如下Python代码：
n＝int(input(″请输入一个数：″))
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，执行程序后，输出结果是(　　)
A.1 B.2 C.3 D.4
4.某二分查找算法的程序段如下：
key＝int(input('待查数据为：'))
i＝0；j＝10；n＝0
while i<＝j：
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
执行该程序段后，下列说法正确的是(　　)
A.该程序若要实现对分查找，要求数组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(″输入要查找的数：″))
i＝0；j＝9
ans＝″″
while i<＝j：
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)
执行该程序，输入 80，则输出的结果是(　　)
A.36 66 B.44 80
C.36 46 D.44 66
6.某二分查找算法的Python程序段如下：
i，j＝0，24
n＝0
while i<＝j：
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为下列选项的值，程序段执行后，输出结果与其他三项不同的是(　　)
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：
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种
8.小明为英文字母A～Z定义了一套全新的二进制编码规则，代码如下
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：
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(″请输入英文字符串：″).upper()#将输入的英文字母转为大写
for c in inp：
print(dc[c]，end＝″ ″)
当程序运行后，输入“OK”后，其输出的二进制编码为(　　)
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))
执行该程序段后，输入待查找的数，输出的结果不可能是(　　)
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：
cnt＝cnt＋1
m＝(i＋j)//2
if a[m]＝＝a[k]：
break
if a[m]i＝m＋1
else：
j＝m－1
数组元素 a[0]到 a[6]各不相同且按升序排列，执行该程序段，下列说法不正确的是(　　)
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函数将mid进制的整数y转化为十进制数
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))
执行该程序段后，依次输入83和123，程序输出为(　　)
A.2 B.6
C.8 D.－1
12.某二分查找算法的Python程序段如下：
n＝0；flag＝True
key＝int(input(″输入要查找的数：″))
i，j＝0，9
while i<＝j 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]，程序运行后变量n的值是2，则输入的整数key值不可能是(　　)
A.25 B.34
C.45 D.60
知识点二　极值查找
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：
m＝(i＋j)//2
if keyj＝m－1
else：
i＝m＋1
print(j)
执行该程序段后，输出的结果不可能是(　　)
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：
m＝(i＋j)//2
if keyj＝m－1
else：
i＝m＋1
该程序段运行结束后，下列说法正确的是(　　)
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：
m＝(i＋j)//2
if keyj＝m－1
else：
　 　
若key值为22，程序运行结束后，加框处语句执行的次数为(　　)
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：
c＋＝1
m＝(i＋j)//2
if a[m]>key：
j＝m－1
else：
i＝m＋1
上述程序段执行结束，下列运行结果不正确的是(　　)
A.i的值为6 B.c的值为3
C.m的值为6 D.j的值为5
5.执行如下程序段：
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：
m＝(i＋j)//2
c＋＝1
if a[m]>key：
j＝m－1
else：
i＝m＋1
下列说法正确的是(　　)
A.变量c的值一定是4 B.变量i的值可能是7
C.a[i]的值可能等于key D.变量m和变量j的值可能相等
6.列表中有n个非降序的数字元素，即s[0]<＝s[1]<＝s[2]<＝…<＝s[n－1]的列表中，执行如下程序段：
i＝0；j＝n－1
key＝int(input(″输入一个要查找的数：″))
while i<＝j：
m＝(i＋j)//2
if s[m]>key：
j＝m－1
else：
i＝m＋1
print(s[m]，end＝″，″)
执行该程序，输出结果key，x，key(x和key不相等)，说法错误的是(　　)
A.x是比key小的数 B.x是比key大的数
C.其列表中最少有6个元素 D.其列表中最多有9个元素
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：
m＝(i＋j)//2
if a[m]<＝key：
i＝m＋1
else：
j＝m－1
c＋＝1
print(c)
若程序运行后，输出的结果是3，则输入的key可能是(　　)
A.20或73 B.24或49
C.23或24 D.23或49
8.列表a和列表b均有5个从小到大排列的整数元素，且列表a的最后一个元素大于列表b的最后一个元素。有如下Python程序段：
c＝0
i＝0；j＝len(a)－1
for key in b：
while i<＝j：
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
执行该程序段后，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)　#随机生成[1，30]之间的整数
i，j＝0，9
while i<＝j：
m＝(i＋j)//2
if a[m]>key：
j＝m－1
else：
i＝m＋1
print(j)
执行该程序段，下列说法正确的是(　　)
A.若key的值为10，则输出的值为3
B.若输出的值为8，则key的值一定为19
C.对于任意key值，语句“m＝(i＋j)//2”最少执行1次
D.对于任意key值，语句“m＝(i＋j)//2”最多执行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
上述程序段执行结束，下列说法正确的是(　　)
A.a列表中第3大的数r B.cnt的值为2
C.l的值为12 D.mid＝(l＋r)//2代码执行3次
专题18　查找算法
知识点一
1.B　[本题考查二分查找、自定义函数的综合应用。由“key＝random.choice(a)”可知查找键key是一定可以找得到的，由题中算法可知，找到最少找1次，最多找int(log2n)＋1次，本题中序列a中共有8个成员，则最多找4次。]
2.D　[本题考查二分算法以及二分判定树。根据本题代码m＝(i＋j＋1)//2，画出二分判定树，位于二分判定树第4层的节点下标分别是1、4、7、9、12、14、17、19所以key的值不可能是a[16]。]
3.C　[本题考查二分查找。程序的功能是是数组a的i索引前找一个数，满足a[i]*a[m]＝＝n的个数，因此分别是9*4、12*3、18*2。]
4.C　[本题考查二分查找算法。A选项由条件a[m]>key可以看出数组是升序。B选项查找a[3]需访问a[5]→a[2]→a[4]→a[3]，则n的值为－1。C选项由访问路径a[5]→a[8]→a[10]→a[9]→end，则n的值为n值为2。D选项如果要n的值最小为－4，最大为4，至少节点数满15个，本题节点数只有11个。]
5.A　[本题考查二分查找。m的值依次为5、2、1，当找到key时，直接退出，没有连接a[m]。]
6.A　[n的值为查找次数，7查找次数为2，其余查找次数是4。]
7.A　[本题考查对分查找。列表a中的元素为1－15中的奇数，查找的key为2－16中的偶数，所以查找的结果不存在a[m]＝＝key也就是找到的情况，break不会被执行。查找的过程如下：s的值可能为－2，－1，1，3，共4种。]
8.A　[构建一颗26个节点的升序二叉树，由于26小于31，因此最多查找4次，用一个4位二进制数存储访问的节点(标记为1)。]
9.B　[本题考查递归法求二分查找，找到后返回中间位置，没有找到，累加找过的位置m。用索引位置画出二叉树为，没有一条分支节点和为8。]
10.D　[本题考查二分查找的算法思想。查找的k值为0，2，4，即a[0]、a[2]、a[4]中的一个数，画出判定二叉树。由图可知，查找次数cnt均为3次，m只能是0，2，4。查找的值发生在叶子节点，因此区间中只剩下最后一个数，i，j，m的值是相等的。]
11.C　[本题考查进制转换与二分查找。函数find_base(x，y)的功能为通过二分查找算法查找十进制数x对应另一进制数y的基数，如果不存在则返回－1。由于123O＝83D，最后能够找到对应的基数为8。]
12.B　[本题考查二分查找算法。用二又搜索树画出各个元素的搜索顺序，图中各个左子树方向可以让n自减，右子树方向可以让n自增。A选项，若key＝25，则从节点23的右侧出循环，此时m，n的值是3、2，同理key＝45，m，n的值是8、2，key＝60，m，n的值是9、2。key＝34，m，n的值是6、1。]
知识点二
1.B　[本题考查二分查找的算法思想。产生一个[4，10]之间的偶数，当key＝＝a[m]时，没有终止查找，还是继续向右查找，直至i>j。A选项若key值为4，j的值为2；若key值为6和8，j的值为5；若key值为10，j的值为7。]
2.C　[本题考查二分查找。当找到key时，没有结束循环，而是向右继续查找。最后一个41的索引位置为5，因此找到后，i向后查找，i的值是6。]
3.C　[查找的数据依次为26，8，15，22，找到8后连续两次向右查找，但找到22后还是再一次查找，因此共找了3次。]
4.C　[本题考查右极值的查找，查找21，最后一次i，j，m的值均为5，找到后还要移动i，因此i的值为6。]
5.D　[本题考查二分查找的算法思想。可查找的数为[0，5]或[11，15]之间的整数。找到后中途不能结束查找，还要继续向右查找，当key为2时，查找3次。B选项当查找到13时不可结束循环，因此i的值不可能是7。C选项当找到后还要向右查找，因此a[i]不可能是要查找的数。D选项查找结束后，a[j]可能是要查找的数，因此变量m和变量j的值可能相等。]
6.A　[本题考查对二分查找的算法实现。当a>＝s[m]时向右查找，故x应比a大。由“a，x，a”可知，该二分查找进行了3次查找，即向右找1次，再向左找1次，则对应二叉查找树应为3层或4层，当有6个节点时，可实现3次查找。当节点数增加到10个时，对应第6个节点出现右子树，继续进行查找，则进行第4次查找。]
7.B　[本题考查二分查找。查找范围是[1，10]，当找到key时仍要往右边查找，当key＝20、24、49时，查找的次数是3，当key＝23、31、73时，查找的次数是4。]
8.B　[本题考查二分查找及插入排序的算法实现。]
9.B　[本题考查二分查找，其中主要考查利用二分查找边界。结束查找的条件是i>j，就算是找到，还是移到i继续查找，因此程序的功能是查找右边界。列表a的元素个数是10个，介于7～15之间，查找次数最少3次，最多4次。根据条件if a[m]>key，当key＝10时，i＝7，j＝6，选项A错误；j＝8，i＝9，对应的元素分别是19，20，19＝10.C　[本题考查对分查找的算法实现。找出了列表中比mid值大的元素个数并用cnt进行记录，若cnt

展开更多......

收起↑