资源简介

/ 让教学更有效 精品试卷 | 信息
第12课　课后练习
（学生用）
班级：____________　姓名：____________　得分：__________
一、填空（每空 3 分，共 24 分）
1．顺序查找最坏情况下要比较 ______ 次（列表有 n 个元素）。
2．二分查找的前提条件是：数据必须已经 ______________。
3．二分查找中，中间位置的计算式是 mid = ______________。
4．当 a[mid] < target 时，应该更新 ______ = mid + 1。
5．当 a[mid] > target 时，应该更新 ______ = mid - 1。
6．二分查找的循环条件是 while ______ <= ______。
7．100 个数用二分查找，最多比较 ______ 次。
二、判断对错（每题 3 分，共 12 分）
1．二分查找可以在没有排序的列表上直接使用。（　　）
2．二分查找的 while 条件写成 low < high 会影响结果。（　　）
3．顺序查找不需要数据有序，这是它的优点。（　　）
4．冒泡排序中如果某一轮一次交换都没有发生，说明列表已经有序。（　　）
三、手算模拟题（14 分）
对有序列表 a = [10, 20, 30, 40, 50, 60, 70, 80, 90]，用二分查找找 70，请补齐每一步。
轮次 low high mid a[mid] 与 70 比较后的动作
1
2
3
结论：需要比较 ______ 次找到 70，它在第 ______ 个位置（从 1 数）。
四、★ 补全代码（每空 5 分，共 20 分）
第 1 题　二分查找。
a = [11, 22, 33, 44, 55, 66, 77, 88, 99]
target = 77
low, high = 0, len(a) - 1
ans = -1
while low ①______ high:
mid = (low + high) // 2
if a[mid] == target:
ans = mid
break
elif a[mid] < target:
low = ②______________
else:
high = ③______________
第 2 题　冒泡排序的提前结束优化。
n = len(a)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
if not ④__________:
break
① ______　② ______　③ ______　④ ______
五、★★ 提高题（每题 10 分，共 30 分）
第 1 题　效率对比实验
生成一个包含 1~1000 的有序列表，分别用顺序查找和二分查找找最后一个数，记录各自的比较次数。请写出程序并填入下表。
方　法 比较次数
顺序查找
二分查找
两种方法相差约 ______ 倍。
______________________________________________________________
______________________________________________________________
第 2 题　手写冒泡并观察
请完整写出冒泡排序程序，并在程序中加一个计数器，统计对 a = [5, 3, 8, 1, 9] 排序时一共交换了多少次。
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
第 3 题　改错辨析
下面这段二分查找为什么可能陷入死循环？请指出原因并改正。
while low <= high:
mid = (low + high) // 2
if a[mid] == target:
break
elif a[mid] < target:
low = mid # ← 这里有问题
else:
high = mid - 1
原因：____________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
六、★★★ 挑战题（每题 12 分，共 24 分）
第 1 题　查找与排序综合
随机生成 20 个 1~100 的整数（可用列表直接写死），要求：① 用冒泡排序把它们从小到大排好；② 分别用顺序查找和二分查找查找同一个数；③ 打印两种方法各自的比较次数。
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
第 2 题　猜数字游戏升级（结合二分思想）
写一个程序：电脑随机想一个 1~100 的数，你用「每次猜中间数」的策略去猜，让程序统计出需要几次才能猜中。把 100 改成 1000、10000 各试一次，记录次数，你发现了什么规律？
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
教师评语：
__________________________________________________________________
__________________________________________________________________
21世纪教育网 www.21cnjy.com 精品试卷·第 2 页 （共 2 页）
21世纪教育网(www.21cnjy.com)/ 让教学更有效 精品试卷 | 信息
第12课　课后练习
（答案版 · 教师用）
班级：____________　姓名：____________　得分：__________
一、填空（每空 3 分，共 24 分）
1．顺序查找最坏情况下要比较 ______ 次（列表有 n 个元素）。
2．二分查找的前提条件是：数据必须已经 ______________。
3．二分查找中，中间位置的计算式是 mid = ______________。
4．当 a[mid] < target 时，应该更新 ______ = mid + 1。
5．当 a[mid] > target 时，应该更新 ______ = mid - 1。
6．二分查找的循环条件是 while ______ <= ______。
7．100 个数用二分查找，最多比较 ______ 次。
二、判断对错（每题 3 分，共 12 分）
1．二分查找可以在没有排序的列表上直接使用。（　　）
2．二分查找的 while 条件写成 low < high 会影响结果。（　　）
3．顺序查找不需要数据有序，这是它的优点。（　　）
4．冒泡排序中如果某一轮一次交换都没有发生，说明列表已经有序。（　　）
三、手算模拟题（14 分）
对有序列表 a = [10, 20, 30, 40, 50, 60, 70, 80, 90]，用二分查找找 70，请补齐每一步。
轮次 low high mid a[mid] 与 70 比较后的动作
1
2
3
结论：需要比较 ______ 次找到 70，它在第 ______ 个位置（从 1 数）。
四、★ 补全代码（每空 5 分，共 20 分）
第 1 题　二分查找。
a = [11, 22, 33, 44, 55, 66, 77, 88, 99]
target = 77
low, high = 0, len(a) - 1
ans = -1
while low ①______ high:
mid = (low + high) // 2
if a[mid] == target:
ans = mid
break
elif a[mid] < target:
low = ②______________
else:
high = ③______________
第 2 题　冒泡排序的提前结束优化。
n = len(a)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
if not ④__________:
break
① ______　② ______　③ ______　④ ______
五、★★ 提高题（每题 10 分，共 30 分）
第 1 题　效率对比实验
生成一个包含 1~1000 的有序列表，分别用顺序查找和二分查找找最后一个数，记录各自的比较次数。请写出程序并填入下表。
方　法 比较次数
顺序查找
二分查找
两种方法相差约 ______ 倍。
______________________________________________________________
______________________________________________________________
第 2 题　手写冒泡并观察
请完整写出冒泡排序程序，并在程序中加一个计数器，统计对 a = [5, 3, 8, 1, 9] 排序时一共交换了多少次。
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
第 3 题　改错辨析
下面这段二分查找为什么可能陷入死循环？请指出原因并改正。
while low <= high:
mid = (low + high) // 2
if a[mid] == target:
break
elif a[mid] < target:
low = mid # ← 这里有问题
else:
high = mid - 1
原因：____________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
六、★★★ 挑战题（每题 12 分，共 24 分）
第 1 题　查找与排序综合
随机生成 20 个 1~100 的整数（可用列表直接写死），要求：① 用冒泡排序把它们从小到大排好；② 分别用顺序查找和二分查找查找同一个数；③ 打印两种方法各自的比较次数。
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
第 2 题　猜数字游戏升级（结合二分思想）
写一个程序：电脑随机想一个 1~100 的数，你用「每次猜中间数」的策略去猜，让程序统计出需要几次才能猜中。把 100 改成 1000、10000 各试一次，记录次数，你发现了什么规律？
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
______________________________________________________________
教师评语：
__________________________________________________________________
__________________________________________________________________
第 12 课　参考答案（教师用）
与《教师参考答案》册同源，全部数值均已实际运行核验
一、填空
1．n　2．排好序（有序）　3．(low + high) // 2　4．low　5．high
6．low、high　7．7
二、判断对错
1．×（二分查找的前提就是数据有序，乱序会找不到明明存在的数）　2．√　3．√　4．√
三、手算模拟题
在 [10, 20, 30, 40, 50, 60, 70, 80, 90] 中查找 70：
轮次 low high mid a[mid] 动作
1 0 8 4 50 50 < 70 → low = 5
2 5 8 6 70 找到了！
结论：需要比较 2 次，70 在第 7 个位置。
四、★ 补全代码
① <=　② mid + 1　③ mid - 1　④ swapped
五、★★ 提高题
第 1 题：
def seq_steps(a, t):
c = 0
for x in a:
c += 1
if x == t:
break
return c
def bin_steps(a, t):
low, high, c = 0, len(a) - 1, 0
while low <= high:
c += 1
mid = (low + high) // 2
if a[mid] == t:
break
elif a[mid] < t:
low = mid + 1
else:
high = mid - 1
return c
a = list(range(1, 1001))
t = 1000
print("顺序查找：", seq_steps(a, t), "次") # 1000 次
print("二分查找：", bin_steps(a, t), "次") # 10 次
顺序查找 1000 次，二分查找 10 次，相差约 100 倍。
第 2 题：在冒泡排序内层交换处加计数器：
a = [5, 3, 8, 1, 9]
n = len(a)
cnt = 0
for i in range(n - 1):
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
cnt += 1
print(a)
print("共交换", cnt, "次") # 4 次
第 3 题：low = mid 是错误的。因为 a[mid] 已经确定不等于目标，如果不 +1，low 可能一直停在原处不动，导致 mid 反复取同一个值，程序陷入死循环。应改为 low = mid + 1。
六、★★★ 挑战题
第 1 题：
a = [45, 12, 78, 34, 56, 89, 23, 67, 90, 11,
5, 42, 88, 29, 73, 61, 17, 95, 38, 51]
n = len(a)
for i in range(n - 1):
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
print("排序后：", a)
t = 45
# 顺序查找
c1 = 0
for x in a:
c1 += 1
if x == t:
break
# 二分查找
low, high, c2 = 0, n - 1, 0
while low <= high:
c2 += 1
mid = (low + high) // 2
if a[mid] == t:
break
elif a[mid] < t:
low = mid + 1
else:
high = mid - 1
print("顺序查找比较", c1, "次；二分查找比较", c2, "次")
第 2 题参考思路：每次猜范围中间的数，100 个数最多 7 次；1000 个数最多 10 次；10000 个数最多 14 次。规律：每扩大 10 倍，只需多猜约 3~4 次（因为 2 = 1024）。这就是二分查找「对数级」的效率。
21世纪教育网 www.21cnjy.com 精品试卷·第 2 页 （共 2 页）
21世纪教育网(www.21cnjy.com)

展开更多......

收起↑