2025届信息技术一轮复习练习：专题18　查找算法（含答案）.docxVIP

专题18查找算法

知识点一二分查找的算法思想

1.有如Python程序段：

importrandom

deffind(x，y)：

m＝(x＋y＋1)//2

ifa[m]＝＝key：

returnm

ifa[m]key：

y＝m－1

else：

x＝m＋1

returnfind(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

whilei＝jandf[m]＝＝0：

m＝(i＋j＋1)//2

n＝n＋1

ifa[m]＝＝key：

f[m]＝1

elifa[m]key：

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＝[iforiinrange(n)]

c＝0

foriinrange(1，n)：

L＝1；R＝i－1

whileL＝R：

m＝(L＋R)//2

ifa[i]*a[m]＝＝n：

c＋＝1

break

elifa[i]*a[m]n：

L＝m＋1

else：

R＝m－1

print(c)

输入36，执行程序后，输出结果是()

A.1 B.2C.3 D.4

4.某二分查找算法的程序段如下：

key＝int(input(待查数据为：))

i＝0；j＝10；n＝0

whilei＝j：

m＝(i＋j＋1)//2

ifa[m]＝＝key：

break

elifa[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＝″″

whilei＝j：

m＝(i＋j＋1)//2

ifkey＝＝a[m]：

break

elifkeya[m]：

j＝m－1

else：

i＝m＋1

ans＝ans＋str(a[m])＋″″

print(ans)

执行该程序，输入80，则输出的结果是()

A.3666 B.4480

C.3646 D.4466

6.某二分查找算法的Python程序段如下：

i，j＝0，24

n＝0

whilei＝j：

m＝(i＋j＋1)//2

n＝n＋1

ifkey＝＝a[m]：

break

ifkeya[m]：

i＝m＋1

else：

j＝m－1

print(n)

列表a中各元素值依次为1～25，若查找键key为下列选项的值，程序段执行后，输出结果与其他三项不同的是()

A.7 B.12

C.19 D.22

7.如下Python程序段：

importrandom

a＝[1，3，5，7，9，11，13，15]

key＝random.randint(1，8)*2

i，j＝0，len(a)－1

s＝0

whilei＝j：

m＝(i＋j＋1)//2

ifa[m]＝＝key：

break

ifa[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)foriinrange(26)]

dc＝{}

forkins：

i＝0

j＝len(s)－1

rt＝″0″

whilei＝j：

m＝(i＋j)//2

ifs[m]＝＝k：

dc[k]＝rt

break

elifs[m]k：

i＝m＋1

rt＋＝″1″

else