某晚会的猜数字游戏中，有100张写有1~100之间整数的卡片，主持人随机抽取一张卡片，让大家竞猜。有一种方案是：第一次猜50，若提示低了，则第二次猜75，若提示还是低了，则第三次猜87，依次类推；若第一次猜50，提示高了，则第二次猜25，若提示还是高了，则第三次猜12，依次类推；……。这种每次缩小一半查找范围而达到迅速确定目标的算法称为（）。

0 返回首页

1. 某晚会的猜数字游戏中，有100张写有1~100之间整数的卡片，主持人随机抽取一张卡片，让大家竞猜。有一种方案是：第一次猜50，若提示低了，则第二次猜75，若提示还是低了，则第三次猜87，依次类推；若第一次猜50，提示高了，则第二次猜25，若提示还是高了，则第三次猜12，依次类推；……。这种每次缩小一半查找范围而达到迅速确定目标的算法称为（）。

A. 顺序查找法 B. 排序法 C. 解析法 D. 二分查找法

【考点】

查找算法及程序实现;

【答案】

您现在未登录，无法查看试题答案与解析。登录

单选题容易

基础巩固

能力提升

变式训练

拓展培优

真题演练

换一批

1. 二分查找实际上就是( )的一种典型运用。

A. 动态规划法 B. 分治策略 C. 回溯法 D. 递推法

单选题容易

2. 关于对分查找，下列说法正确的是（）

A. 对分查找的数据必须是有序排列的 B. 对分查找的数据类型必须是数值型的 C. 顺序查找比对分查找的查找速度快 D. 使用对分查找对未排序数据查找时速度较慢

单选题容易

3. 图书管理系统对图书管理是按图书的序号从小到大进行管理的，若要查找一本已知序号的书，则能快速地查找的算法是（）。

A. 穷举算法 B. 解析算法 C. 对分查找 D. 冒泡排序

单选题容易

1. 有如下Python程序段：

import random

d=[28, 37, 39, 42, 45, 50, 70, 80]

i, j, n=0, len(d)-1, 0

key=random.randint(20, 35)*2

while i<=j：

m=(i+j)//2; n+=1

if key==d[m]:

break

elif key<d[m]:

j=m-1

else:

i=m+1

print(i, j, m, n)

执行该程序段后，下列说法正确的是（）

A. n的值可能为4 B. 若n值为2，则必定满足i<=j C. m的值可能为1 D. 若n值为3，则key的值可能是45

单选题普通

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

import random

key=random.randint(0,4)*2+5

n=10;ans=0

a=[4,5,5,8,9,11,11,13,15,17]

i=0;j=n-1

while i<=j:

m=(i+j)//2

if a[m]<=key:

i=m+1

else:

j=m-1

ans+=a[m]

print(ans)

程序运行后，输出ans的值不可能是（）

A. 19 B. 27 C. 37 D. 44

单选题普通

3. 用二分查找的方法求不等式 2x+3x-4<=n(n>=0)的最大正整数解，编写的程序如下：

n=int(input("请输入 n："))

L,R=1,n+1

while L<R:

x=(L+R+1)//2

if 2**x+3*x-4<=n:

①

else:

②

print(f"方程 2^x+3*x-4<={n}的最大正整数解为：",R)

要使程序实现上述功能，则缺失的代码是（）

A. ①L=x+1 ②R=x-1 B. ①L=x②R=x-1 C. ①R=x-1 ②L=x+1

单选题普通

1. 小李编写了一个成语接龙的VB程序，功能如下：在文本框Text1中输入一个成语，单击“接龙”按钮Command1，在列表框List1中显示接龙的成语。程序运行界面如下图所示。

实现上述功能的VB程序如下，但加框处代码有错，请改正。

Dim n As Integer, cy(30000) As String

Private Sub Form_Load()

'从数据库中读入n条成语，并存数组cy中

'代码略

End Sub

Private Sub Command1_Click()

Dim s As String, i As Integer, j As Integer

Dim m As Integer, flag As, Boolean

Dim s1 As Siring, s2 As String

s=Text1.Text

flag=True

Do While flag

'①

i=1

j=n

Do While<= j

m= Int((i+j)/2)

s2=Mid(cy(m), 1, 1)

If s2=s1 Then

Exit Do

ElseIf s2<s1 Then

i=m+1

Else

j=m-1

End If

Loop

If Then '②

List1.AddItem s+ "— —"+cy(m)

s=cy(m)

Else

List1.AddItem "接不下去了"

flag=False

End If

Loop

End Sub

① ②

综合题普通

2. 给定n(n小于1000)个整数，整数的范围在0到m之间，请使用“对分法”思想求出这n个整数的中位数(所谓中位数，是指将这n个数排序之后，排在正中间的数)。

小丫编写了一个求中位数的VB程序，功能如下：单击“求中位数”按钮Command1，程序根据输入的n和m，随机产生n个在[0,m]范围内的数。程序运行界面如下所示：

实现上述功能的VB 程序如下：

Dim x(1 To 1000) As Long

Private Sub Command1_Click()

Dim n As Integer, i As Integer, rbound As Integer, mid As Integer

Dim m As Integer, count As Integer

n = Val(Text1.Text)

m = Val(Text2.Text)

List1.Clear

Randomize

For i = 1 To n

x(i) =Int(Rnd * (m + 1)) ' 产生[0,m] 的随机数

List1.AddItem x(i)

Next i

lb = 0

rb = m

Do While lb <rb

mid = (lb + rb) \ 2

①

For i = 1 To n

If ② Then

count = count + 1

End If

Next i

If count > n \ 2 Then

lb = mid + 1

Else

③

End If

Loop

Text3. text = str(rb)

End Sub

程序要实现该功能，画线处应填入的代码为：

①②③

填空题普通

3. 编写VB程序，实现如下功能：在文本框Text1中输入一个整数，单击“查找删除”按钮Command1，采用对分查找法在数组a(从小到大排列，并显示在文本框Text2中)中查找该数。若找到，则从数组a中删除该数(该数后面的数组元素都前移一位)，并在文本框Text3中显示删除后的结果；否则，在文本框Text3中显示“该数没有找到!”。运行效果如图所示。

实现上述功能的VB代码如下，但加框处代码有错，请改正。

Dim a(1 To 20) As Integer ’用于保存n(n<=20)个按从小到大顺序排列的整数

‘Form_Load事件过程产生n个整数，按升序保存在数组a中，并在Text1中显示

Private Sub Form_Load()

‘代码略

End Sub

Private Sub Command1_Click()

Dim i , j , m , k As Integer

Dim x As Integer，f As Boolean ’变量f用于标记是否在数组中找到x

x = Val(Text2.Text)

i=1 ：j=n : f=False

Do While i<=j And f=False

m = Fix((i＋j)/2)

If a(m)=x Then f=True

If Then i=m＋1 Else j=m－1 ‘(1)

Loop

If f = True Then

For k = m To n-1

‘(2)

Next k

n = n - 1

Text3.Text = ""

For k = 1 To n

Text3.Text = Text3.Text＋Str(a(k))＋","

Next k

Else

Text3.Text = "该数没有找到!"

End If

End Sub

以上程序段运行时，为了实现上述功能，加框处代码应改正为：

⑴；⑵。

综合题普通

1. 张三是一名计算机专业的大学生，为了帮助同学们学习专业相关的英语词汇，编写一个简易字典程序。该程序中存放词汇数据库，在学习中输入英文单词，可以获得中文翻译结果。程序中的词汇数据库采用链表方式存储，首字母相同时按升序排序。查找单词时，首先根据首字母找到同首字母最小单词所在链表，再按照链表顺序查找该单词。

(1) 根据题意，部分的单词库数据逻辑结构如图所示，查找单词“byte” 的过程是 “binary ”→ “bit ”→“byte”，补充图中空白单元格的值为。

(2) wordlist(data,info)函数实现将词汇数据库 data 以链表的方式按字母序升序排列。info 表示词汇数据库中各字母开头的最小单词位置，如 info[0]表示字母 a 开头的最小单词在词汇数据库 data 中的位置。实现该功能的程序如下，请在划线处填入合适的代码。

def wordlist(data,info) :

n = len (data)

for i in range(n):

data[i].append(-1) #data[i]追加一个元素-1

for i in range(n):

d = data[i][0]

if info[k] == -1:

info[k] = i

else:

head = info[k]

q = head

while :

p = q

q = data[q][2]

if q != head:

data[p][2] = i

data[i][2] = q

else:

data[i][2] = head

return data,info

(3) searchword(data,info,key)函数实现单词的查找。程序如下，请在划线处填入合适的代码。

def searchword(data,info,key) :

k = ord(key [0]) - ord("a")

head = info[k]

p = head

while p != -1:

if data[p][0] == key:

return

p = data[p][2]

return "没有找到该单词"

读取词汇数据库，存入列表 data 中，列表的每个元素包含 2 个数据项，分别为英文单词和中文翻译，如 data = [[‘audio ’,‘音频 ’], [‘binary ’,‘二进制数 ’] …]，数据读取存入的代码略。

'''

info = [-1] * 26

data,info = wordlist(data,info)

key = input("请输入查找单词：").lower () #转化为小写字母

res = searchword(data,info,key)

print(key, "查找结果是：", res)

综合题困难

2. 贪吃蛇在𝑛×𝑛(1≤𝑛≤10)的方阵中游走，它可以往上下左右四个方向游走，当穿越方阵的边界时还可以从该边界的对立面继续进入方阵。初始时你可以任意安排贪吃蛇的起点位置，并且选择一个方向一直走𝑛步。方阵中“.”表示空位置，数字表示可以吃的食物，每吃到一个数字时，这个数字便会附着到贪吃蛇的尾部，同时方阵中该数字会消失。问：在某个时刻，贪吃蛇身上会不会出现我们想要的某个整数；若有，会有多少个数会小于该整数。

例如，在右侧5×5的方阵中可以产生[1,3,4,12,21,234,243,324,342,423,432]共11个数。其中数“234”的产生过程可以是：选择第4行第2列为起点，第一步吃掉2，接着往右走三步吃掉3，再往右走一步穿越到对面的4，吃掉它成为“234”，共五步。其中“1234”或“123”等整数是不可能出现的。

请回答以下问题。

(1) 输入方阵保存至数组𝑎，然后将贪吃蛇所有可能吃到的所有数字组合保存到数组𝑏中，请补充完该算法程序。

dx = [0, 1, 0, -1] # 模拟贪吃蛇往四个方向游走时行号变化的数组

dy = [1, 0, -1, 0] # 列号变化数组

n = int(input()) # 方阵的大小

a, b = [], []

for i in range(n):

s = input().strip().split() #方阵中的一行数据，“.”号和数字字符都以空格分隔

a.append(s)

def calc(i, j, p):

x, y, res = i, j, 0

if '0' <= a[x][y] <= '9':

res = int(a[x][y])

for i in range(n-1):

x = # 产生新的行号

y = # 产生新的列号（与行号类似），代码略

if '0' <= a[x][y] <= '9':

res = res * 10 + int(a[x][y])

return res

for i in range(n):

for j in range(n):

for k in range(4):

num =

if num > 0:

b.append(num)

print(b) # 输出所有可能能产生的整数（可能会产生重复的整数）

(2) 若数组 a= [['.', '1', '.'], ['.', '2', '3'], ['.', '.', '.']]，上述程序处理完后𝑏数组中（选填：存在 / 不存在）整数2。

(3) 对𝑏数组中的所有整数进行升序排序，输入待查找的数据，输出小于等于该数字的数有多少个。请补充完该算法程序。

b = [1, 12, 23, 23, 23, 35, 35,146]

输入输出示例：

请输入待查找的整数：23

小于等于23的数共有5个

请输入待查找的整数：31

小于等于31的数共有5个

bn = len(b)

for i in range(bn-1):

for j in range( ):

if b[j] > b[j+1]:

b[j], b[j+1] = b[j+1], b[j]

key = int(input("请输入待查找的整数："))

i, j = 0, bn-1

while i <= j:

m = (i + j) // 2

if :

i = m + 1

else:

j = m - 1

print("小于等于", key, "的数共有", i, "个")

综合题困难

3. 并列一排的n个房间(房间间距均为1个单位)，依次编号为1~m，其中k个房间需要配送服务，现有处于不同房间的m台机器人可提供配送服务。配送系统为管理方便，对所有机器人设置相同的配送半径r (机器人以所在房间为起点，可配送左右各r个连续房间)。可以设置最小配送半径来满足k个房间的配送要求。

例如，根据系统依次采集到的数据，当前需要配送的5个房间编号分别为1，8，3，4，7，可提供配送服务的机器人1、机器人2分别处在房间2、房间7，如下图所示。各房间可选择最近的机器人提供配送服务，例如房间4离机器人1的距离为2，离机器人2的距离为3，因此可以选择机器人1的配送服务。确定各房间所选择的机器人后，计算各房间与所选择的机器人的距离，取其最大值即为最小配送半径。因此，要满足这5个房间的配送要求，对2台机器人可以设置的最小配送半径为2。

房间编号	1	2	3	4	5	6	7	8
需配送的房间	√		√	√			√	√
机器人		机器人1					机器人2

(1) 若需配送服务的房间编号分别为1，3，2，4，5，6，可提供配送服务的2台机器人所处房间编号为4，1，则最小配送半径应设置为；

(2) 实现上述功能的Python程序如下，请在划线处填入合适的代码。

def sort_ arr(a)： #对数组进行升序排序

m = len(a)

i=1

whilei<= m- 1 and flag == True：

flag = False

for j in

if a[j] <a[j-1]：

a[j], a[j-1|=a[j-1], a[j]

flag = Truc

i+=1

return a

def bisearch(v, b)：．

i，k = 0, len(b)

j=k- 1

while i<=j：

mid=(i+j)//2

i=mid+1

else：

j= mid- 1

retur i

def max_ min(houses, b)：

minr= 0

for h in houses：

R = bisearch(h, b)

if R == len(b)：

r=h-b[R- 1]

elif R== 0：

r= b[R]- h

else：

minr = max(r, minr)

return minr

if_ name_ == '_ main_ '： #主程序

#将需配送的房间编号存入整型数组houses

#将机器人所在房间编号存入整型数组b，代码略

#例如： houses= |8, 3, 4, 7, 1], b= |7, 3|

b= sort_ arr(b)

print(max_ min (houses, b))#输出最小配送半径

综合题困难

1. 用二分查找的方法求不等式 2x+3x-4<=n(n>=0)的最大正整数解，编写的程序如下：

n=int(input("请输入 n："))

L,R=1,n+1

while L<R:

x=(L+R+1)//2

if 2**x+3*x-4<=n:

①

else:

②

print(f"方程 2^x+3*x-4<={n}的最大正整数解为：",R)

要使程序实现上述功能，则缺失的代码是（）

A. ①L=x+1 ②R=x-1 B. ①L=x②R=x-1 C. ①R=x-1 ②L=x+1

单选题普通

2. 某对分查找算法的VB程序段如下：

key = Val(Text1．Text)

s="" ：i=1；j= 10

Do While i<=j

m=(i+j)\2

If a(m)= key Then Exit Do 'Exit Do表示退出循环

If key < a(m) Then

j=m-1：s=s+"L"

Else

i=m+1 ：s=s+ "R"

End If

Loop

按非降序排序的整型数组a(1)到a( 10)的值依次为“11，23，31，39，44，52，60，x，69，89”。在文本框Text1中输入66，执行该程序段后s值为“RRL”，则x的可能值的个数为( )

A. 3 B. 4 C. 5 D. 6

单选题普通

3. 某对分查找算法的VB程序段如下：

i=1：j=30

m=（i+j）\2

Do While i < = j And key < > a（m）

If key >a（m） Then i = m+1 Else j = m-1

m=（i+j）\2 ①

Loop

数组元素a（1）到a（30）各不相同且按升序排列，若查找键key与a（9）相等，执行该程序段，①处语句的执行次数是（）

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

单选题普通