某对分查找算法的VB程序段如下： i=1 : j=6 : k=0 key = Val( Textl．Text) Do Whilei<= j k=k+ 1 m= Int((i +j)/2+0.5) If key = a(m) Then Exit Do If key< a(m) Then j=m-1 Else i=m+ 1 Loop 文本框Text1中输入27，执行该程序段后，k的值为2，则a(1)到a(6)各元素可能的值是（）

1. 运用二分查找算法可以提高查找的效率，前提是待查找序列必须是（）排序的。

A. 递增 B. 递减 C. 有序 D. 无序

单选题容易

2. 二分查找算法是利用（）实现的算法。

A. 分治策略 B. 迭代法 C. 贪心法 D. 回溯法

单选题容易

3. 关于查找，下列叙述正确的是（）

A. 顺序查找就是按照从大到小的顺序逐一查找 B. 二分查找就是按照从大到小顺序逐一查找 C. 顺序查找一定比二分查找搜索速度慢 D. 二分查找要求数据是有序的

单选题容易

1. 小明和小华玩猜数字游戏，所猜数字不超过800，小明首先猜400，小华说大了，小明又猜200，小华再次说大了，小明猜100，小华说小了，小明猜150，以此类推，直到猜到正确的数字。上述方法中蕴含的算法是（）。

A. 穷举算法 B. 递归算法 C. 二分查找法 D. 顺序查找法

单选题普通

2. 某电子字典产品，假设内部采用二分算法来查找单词，每查找一个中间值并进行大小比较约需0.1秒，现有一个单词库，内有已索引好的2023个单词，在该词库中找到某个单词所需时间最多不超过（）秒。

A. 0.1 B. 1.4 C. 1.1 D. 1.2

单选题普通

3. 在序列“7,14,18,21,23,29,31,35,38,42,46,49,52”中用二分查找法查找数字“42”，一共找了（）就找到了。

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

单选题普通

1. 编写一个单词查找程序，其功能是：在文本框Text1中输入要查找的单词，单击“查找”按钮Command1后，在标签Label4中输出查找结果。程序运行效果如下图所示。

算法说明：

1)英语单词存放在数组words中。

2)如果在数组words中找到要查找的单词，则在标签Label4中显示“查找成功！”，并显示单词在数组words中出现的次数，如果未找到则显示“无此单词，请重输！”。

实现上述功能的VB程序如下，请在程序划线处填入合适的语句。

Dim n As Integer

Dim words(1 To 100) As String

Private Sub Command1_Click()

Dim key As String, i As Integer, times As Integer

key = Text1.Text

times = 0

For i = 1 To n

If key=words(i) Then

Next i

If times > 0 Then

Label4.Caption=“查找成功！共找到”+ +“个”

Else

Label4.Caption = “无此单词，请重输！”

End If

End Sub

Private Sub Text1_KeyPress(KeyAscii As Integer)

Dim word As String

word = Text1.Text

If KeyAscii = 13 Then

n = n + 1

List1.AddItem Str(n) + “：” + word

Text1.Text = “ ”

End If

End Sub

综合题普通

2. 大家期盼的校运会要来了，同学们踊跃报名，共有20人报了100米，30人报了200米。小明编写了一个VB程序，用于查询同时报名参加100米和200米比赛的学生，并统计学生数。具体功能如下：程序运行时，在列表框List1中显示报100米的学生学号和姓名，在列表框List2中显示报200米的学生学号和姓名，单击“排序”按钮Command1后，将List2中数据按“姓名”升序排序，并将排序后的数据重新显示在列表框List2中；单击“查询并统计”按钮Command2后，在列表框List3中显示同时报名参加100米和200米比赛的学生信息，并在该列表框的最后显示同时报名这两项比赛的学生数。程序运行界面如下图所示：

为实现上述功能的程序如下，请在划线处填入合适的语句或代码。

Dim xm1(1 To 20) As String, xh1(1 To 20) As String′数组xm1、xh1分别存储选报课程1的学生的姓名和学号

Dim xm2(1 To 30) As String, xh2(1 To 30) As String′数组xm2、xh2分别存储选报课程2的学生的姓名和学号

Const n = 20, m = 30

Private Sub Form_Load()

'获取选报数据，并显示在列表框List1和List2中

'代码略

End Sub

Private Sub Command1_Click()

Dim i As Integer, j As Integer, tt As String

List2.Clear

For i = 1 To m - 1

For j =Step -1

If xm2(j) < xm2(j - 1) Then

tt = xm2(j): xm2(j) = xm2(j - 1): xm2(j - 1) = tt

tt = xh2(j): xh2(j) = xh2(j - 1): xh2(j - 1) = tt

End If

Next j

Next i

For i = 1 To m

List2.AddItem xh2(i) + “ ” + xm2(i)

Next i

End Sub

Private Sub Command2_Click()

Dim i As Integer, j As Integer, w As Integer, tt As String, k As Integer

For i = 1 To n

p = 1

Do While p <= q

w = (p + q) \ 2

If xm1(i) = xm2(w) Then

List3.AddItem xh1(i) + “ ” + xm1(i)

k = k + 1

End If

If Then

q = w - 1

Else

p = w + 1

End If

Loop

Next i

List3.AddItem “共有” + Str(k) + “ 位同学”

End Sub

综合题困难

3. 对分查找算法可用于求解方程的近似值。现要求方程x³-4x²+x+5=0的一个近似值，可设f(x)= x³-4x²+x+5，若有区间[a，b]，使f(a)与f(b)异号，则该区间内必存在该方程的一个解。小明为此编写了VB程序，功能如下：程序运行时，在文本框Text1、Text2中输入区间值a、b，要求a<b，单击“计算”按钮Command1，若该区间有解，则计算出该区间内的一个近似值(精确到0.00001)，否则提示“请重新输入区间”，计算后的相关结果显示在列表框List1中。程序运行效果如下图所示。

实现上述功能的VB程序如下，请在划线处填入合适的语句。

Function f(x As Double) As Double

Dim y As Double

f = y

End Function

Private Sub Command1_Click()

Dim a As Double, b As Double, m As Double, x As Double

a = Val(Text1.Text)

b = Val(Text2.Text)

If f(a) * f(b) < 0 And a < b Then

Do While a <= b

If Abs(f(m)) < 0.00001 Then Exit Do

If Then

b = m

Else

a = m

End If

Loop

x = Format(m, “0.00000”) ′Format函数用于定义输出的小数位数

List1.AddItem “[” & Text1.Text & “，” & Text2.Text & “]” & “解为：” & x

Else

List1.AddItem “[“ & a & ”，“ & b & ”]” & “请重新输入区间”

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

if

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

单选题普通