资源简介
第五章 数据结构与算法
课时1 数据结构与算法关系
一、基础巩固
1.下列有关数据结构的说法，不正确的是( )
A.数据结构是指带有结构特性的数据元素的集合
B.数据结构包括数据的逻辑结构和物理结构
C.数据结构按照数据的逻辑结构分类，分为线性结构和非线性结构两类
D.数据结构中的非线性结构就是指表中各个结点之间具有多个对应关系，如队列
2.下列有关算法效率的说法中，不正确的是( )
A.同一个问题采用不同的算法，其算法效率可能不同
B.算法效率的高低可由算法复杂度来度量
C.评价算法效率优劣时，只需评价时间复杂度即可
D.算法的平均效率是指当输入规模为n时算法的平均效率
3.下列有关数据结构与算法效率的描述中，不正确的是( )
A.常用的数据结构主要有：数组、链表、栈、队列、二叉树等
B.数组是一种线性表数据结构
C.若代码的执行时间不随问题规模n的增大而增长，则该代码的时间复杂度记作 O(n)
D.常见的时间复杂度比较为：O(1)4.下列有关数据结构与算法的描述中，错误的是( )
A.同一问题可用不同算法解决，不同算法的执行效率可能不同
B.对于同一个问题，如果选用不同的数据结构，则解决问题的算法可能也不同
C.高效的程序只与所使用的算法有关，与选择的数据结构无关
D.设计算法时，需要考虑选用何种数据结构
5.有如下Python程序代码：
s＝0
n＝int(input(″n＝″))
s＝n*(n＋1)∥2
print(″s＝″，s)
则该算法的时间复杂度为( )
A.O(1) B.O(n) C.O(n2) D.O(2n)
6.有如下Python程序代码：
n＝int(input(″please input n：″))
s1＝s2＝0
for i in range(n－1)：
for j in range(n)：
s1＝s1＋j
s2＝s2＋s1
print(″s＝″，s)
则该程序的时间复杂度为( )
A.O(1) B.O(n) C.O(log2n) D.O(n2)
二、能力提升
7.有如下Python程序代码：
count＝0
n＝int(input(″n＝″))
for i in range(2，n＋1)：
j＝2
flag＝True
while j<＝i－1：
if i % j＝＝0：
flag＝False
break
j＝j＋1
if flag：
print(i，end＝″″)
count＝count＋1
print(″count＝″，count)
下列说法不正确的是( )
A.该程序算法的时间复杂度为O(n2)
B.算法的功能是求区间[2，n]间的素数并统计素数的个数
C.将代码while j<＝i－1：修改为while j<＝int(i**0.5)，算法效率将更高
D.代码if flag：等价于if flag＝＝False：
8.有如下Python程序代码：
n＝int(input(″请输入n：″))
s，i＝0，1
while i<＝n：
s＝s＋i
i*＝2
print(″s＝″，s)
下列说法正确的是( )
A.该程序算法的时间复杂度为O(log2n)
B.若输入n的值为8，则输出的结果为21
C.交换语句s＝s＋i与i*＝2的位置，输出s的值将不变
D.该算法的功能是求1＋2＋4＋6＋8＋…＋2*n的和
9.下列关于数据结构的说法正确的是( )
A.用不同的数据结构解决同一个问题时，其算法效率是一样的
B.使用数组存储数据时，数据访问效率低，数据插入删除速度快
C.在 word 中执行“撤销键入”操作的原理与队列的特点相同
D.线性表是一种广泛使用的数据结构，常见的线性表有：字符串、队列、栈等
小明在学习了随机数模块后，编写了如下Python程序。请阅读该程序并回答第10～11题。
import random
n＝int(input(″n : ″))
st＝[0]* n
head，tail＝0，len(st)－1
p＝random.randint(5，8)*10＋random.randint(0，9)
while head<＝tail ：
p＝p＋random.randint(1，3)
if p%2＝＝0：
st[head]＝p
head＋＝1
else：
st[tail]＝p
tail－＝1
print(st)
10.该程序的时间复杂度为( )
A.O(1) B.O(n/2) C.O(n) D.O(2n)
11.若输入的n值为5，则该程序运行后的结果可能为( )
A.[48，84，81，79，77] B.[88，92，95，91，87]
C.[76，77，82，84，79] D.[80，81，87，85，83]
课时1 数据结构与算法关系
1.D [数据结构中的非线性结构就是指表中各个结点之间具有多个对应关系，如树、图等，而队列属于线性的数据结构。因此，答案为D。]
2.C [评价算法效率优劣时，不仅要评价算法的时间复杂度，还要评价算法的空间复杂度，因此，答案为C。]
3.C [若代码的执行时间不随问题规模n的增大而增长，则该代码的时间复杂度记作 O(1)，因此，答案为C。]
4.C [算法的设计和选择总是依赖于数据结构，因此，高效的程序不仅与所使用的算法有关，还与选择的数据结构有关，故答案为C。]
5.A [本程序只包含顺序结构，时间复杂度为O(1)，因此，答案为A。]
6.D [本程序使用的是二重循环，时间复杂度为O(n2)，因此，答案为D。]
7.D [代码if flag：等价于if flag＝＝True：或if flag！＝False：，因此，答案为D。]
8.A [若输入n的值为8，则输出的结果为15，因此B选项错误；交换语句s＝s＋i与i*＝2的位置，将会影响s的值，因此C选项错误；该算法的功能是求1＋2＋4＋…＋2i的和，因此D选项错误；本题程序使用的是一重循环，但每次循环后，循环变量i的值变为i＝i*2，因此，时间复杂度为O(log2n)，也可以记为O(logn)，答案为A。]
9.D [A选项解决某问题，选择合适的数据结构可以提高算法效率。B选项数组采用下标访问数据，访问效率高。C选项撤销操作的原理是模拟栈的过程。D选项线性表是除了第一个和最后一个元素，每个元素只有一个前驱和一个后继。]
10.C [本题考查算法时间复杂度。p的初值为[50，89]之间的整数，接着产生的p是连续增加的值。建立长度为n的值均为0的队列，若产生的p是偶数则入队，否则将该值存入队尾，并进行出队操作，该算法循环n次。]
11.B [st数组中偶数在前，奇数在后。A选项不可能有48。C选项77不可能介于两个偶数之间。D产生的数要连续递增，先产生83、85、87，不可能再产生81。]课时2 迭代与递归
一、基础巩固
1.下列Python程序的功能是：求s＝1＋2＋3＋…＋1000的和。
n＝1000
s＝0
for i in range(1，1001)：
s＝s＋i
print(″1＋2＋3＋…＋1000＝″，s)
在求s的过程中使用到的算法是( )
A.递归算法 B.迭代算法 C.枚举算法 D.解析算法
2.把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，最终求出原问题的解，这种算法称为( )
A.递归算法 B.迭代算法 C.枚举算法 D.解析算法
3.某Python 程序如下：
def output(s，n)：
if n＝＝0：
return
print(s[n－1]，end＝″″)
output(s，n－1)
s＝input(″input a string：″)
x＝len(s)
output(s，x)
运行该代码，输入″12345″，则下列说法正确的是( )
A.输出结果为12345
B.有 0 个输出
C.n为0是递归结束条件
D.程序无法结束
4.小明学习了算法后，写了以下两段代码来求斐波那契数列的第6项：
a＝1；b＝1 for i in range(2，6)： c＝a＋b a＝b b＝c print(c) 算法一 def f(n)： if n＝＝1 or n＝＝2： return 1 else： returnf(n－1)＋f(n－2) print(f(6)) 算法二
下列说法正确的是( )
A.两种算法的时间复杂度均为O(1)
B.算法一是迭代算法，算法二是递归算法，相比之下，算法二的时间效率更高
C.执行算法二代码，f(4)共被调用了2次
D.执行算法一代码，当i＝4这一遍循环刚结束时，a的值等于5
5.编写一个简短的递归Python函数，它接受一个字符串s并输出其逆置字符串。例如字符串“dog”的逆置字符串为“god”。程序如下：
s＝input(″请输入字符串：″)
def reverse(s)：
if len(s)<＝1：
return s
return ①________
print(″逆置字符串为：″，reverse(s))
①处的代码应为( )
A.s[－1]＋reverse(s[1：])
B.reverse(s[1：])＋s[－1]
C.s[－1]＋reverse(s[：－1])
D.reverse(s[：－1])＋s[－1]
6.有如下Python程序：
def fun(x)：
if x＝＝1：
return ″1″
elif x%2＝＝0：
return str(x)＋'－'＋fun(x∥2)
else:
return str(x)＋'－'＋fun(x*3＋1)
print(fun(5))
执行该程序后，输出的结果是( )
A.5－2－7－3－6－3－1 B.1－2－4－8－16－5
C.5－16－8－4－2－1 D.1－4－8－16－5
7.有如下Python程序：
def hill(n)：
if n＝＝1 or n＝＝2:
return 1
elif n＝＝3：
return 2
else：
return hill(n－1)＋hill(n－3)
x＝int(input())
print(hill(x))
执行该程序，若输入的值为7，输出的结果是( )
A.7 B.8 C.9 D.10
8.有如下函数：
def f(m，n)：
s＝″″
if m>1：
if m%n＝＝0：
s＝f(m∥n，n)＋str(n)
else：
s＝f(m，n＋1)
return s
执行语句 k＝f(45，2)后，k 的值为( )
A.″533″ B.″53″ C.″35″ D.″335″
二、能力提升
9.对于任意一个自然数，若该自然数为偶数，则将其除以2；若是奇数，则将其乘以3，然后再加 1。如此经过有限次运算后，总能够得到自然数1 。
编写一个程序，由键盘输入一个自然数x，把n经过有限次运算后，输出最终变成1的全过程，并计算运算的次数。
程序运行结果如图所示：
请输入一个整数：24 21→12→6→3→10→5→16→8→4→2→1 运算次数为：10
实现上述功能的Python程序如下，请回答下列问题。
x＝int(input(″请输入一个整数：″))
print(x，″→″，end＝″″)
n＝0
while x！＝1：
if ①________________：
x＝x*3＋1
else：
if x＝＝1：
print(x)
else：
print(x，″→″，end＝″″)
③________________
print(″运算次数为：″，n)
(1)请在程序划线处填入合适的代码。
(2)程序执行时，输入x的值为120，则运算次数为__________。
10.有如下 Python 程序段：
def f(n)：
if n<2：
return 0
elif n % 2＝＝0：
return n＋f(n－2)
else：
return f(n－1)
n＝int(input())
print(f(n))
若输入 n 的值为 101，则程序运行后，输出的内容为( )
A.100 B.2500 C.2550 D.5050
11.李华同学尝试使用递归算法来实现斐波那契数列求值，用 Python 程序实现如下。
def fibo(n)：
if n＝＝0 or n＝＝1：
s＝n
else：
s＝fibo(n－1)＋fibo(n－2)
return s
n＝int(input(″输入所求项：″))
print(fibo(n))
有关递归算法及其应用，下列说法正确的是( )
A.递归算法的执行过程分递推和回归两个阶段
B.计算机在执行递归程序时，通过队列的调用来实现
C.使用上述递归算法求斐波那契数列，时间复杂度为O(n)
D.求斐波那契数列的第6项fibo(5)时，fibo(3)被调用了3次
12.斐波那契数列指的是这样一个数列：1，1，2，3，5，8，13，21，34，55，……。这个数列的规律是：从第3项开始，每一项都等于前两项之和。
求数列中第n项(n≥3)的数据的程序如下，请回答下列问题：
def fibo(x)：
if x＝＝1：
return 1
elif x＝＝2：
return 1
else：
return ①________
n＝int(input(″n＝″))
print(″第″，n，″项为″，②________)
(1)该程序中函数fibo()采用了________思想。
(2)阅读程序，补充划线处的代码。
13.求从自然数1、2、……、n中任取r个数的所有组合。例如n＝5，r＝3的所有组合为：
(1)5、4、3
(2)5、4、2
(3)5、4、1
(4)5、3、2
…
(10)3、2、1
实现上述功能的Python代码如下，请在程序划线处填入合适的代码：
def comb(m，k)：
global c #定义c为全局变量
for i in range(m，k－1，－1)：
①________________
if k>1：
②________________
else：
c＋＝1
print(″(″＋str(c)＋″)″，end＝″″)
for j in range(lista[0]，0，－1)：
print(lista[j]，end＝″″)
print()
lista＝[0]*100
n＝int(input(″请输入n：″))
r＝int(input(″请输入r：″))
lista[0]＝r
c＝0
③________________
程序划线①处应填入的语句为：___________________________________________；
程序划线②处应填入的语句为：___________________________________________；
程序划线③处应填入的语句为：___________________________________________。
课时2 迭代与递归
1.B [本题主要考查的是迭代算法的思想。本题使用变量s记录总和，通过更改变量i的值来更新s的值，从而求出1＋2＋…＋1000的和，因此使用的算法是迭代算法，答案为B。]
2.A [本题主要考查的是递归算法思想。题目中描述的方法是递归算法，因此，答案为A。]
3.C [本题考查递归函数。 A选项递归函数借助栈这种数据结构，12345依次入栈，因此输出54321。当n为0时，return表示返回，意味着结束程序。]
4.C [算法一为迭代算法，时间复杂度为O(n)，算法二为递归算法，f(n－1)＋f(n－2)语句每次调用2次，递归算法时间复杂度为(二叉树的节点个数)即O(2n)。D选项a的值为3。]
5.C [本题主要考查的是递归算法。将一个字符串分解成两部分，即最后一个字符和前面的所有字符，逆置时只要把最后一个字符放到最前面，前一部分的子串使用同样的逆置方法即可。当规模n＝1时，直接得解，即逆置字符串为其自身。s的最后一个字符表示为s[－1]，前面的子串表示为s[：－1]，因此答案为C。]
6.C [程序的功能是将一个数n转换成1的过程，若n为偶数，n更新为x∥2，否则更新为x*3＋1，直到n的值为1。]
7.C [函数hill(7)返回值为hill(6)＋hill(4)；函数hill(6)返回值为hill(5)＋hill(3)；函数hill(5)返回值为hill(4)＋hill(2)；函数hill(4)返回值为hill(3)＋hill(1)；因此hill(4)＝3，hill(5)＝4，hill(6)＝6，hill(6)＝9。]
8.A [本题考查递归算法思想。函数f(45，2)返回值为f(45，3)；函数f(45，3)返回值为f(15，3)＋″3″；函数f(15，3)返回值为f(5，3)＋″3″；函数f(5，3)返回值为f(5，4)；函数f(5，4)返回值为f(5，5)；函数f(5，5)返回值为f(1，5)＋″5″。]
9.(1)①x % 2＝＝1 或x % 2！＝0 ②x＝x∥2 ③n＋＝1 或 n＝n＋1 (2)20
解析 本题主要考查的是迭代算法的程序实现。(1)本题使用的是迭代算法，当自然数变为1时，循环结束，否则，若x为奇数时，x＝n*3＋1，因此，①处代码为x % 2＝＝1或x % 2！＝0；若x为偶数时，x＝x∥2，因此②处语为x＝x∥2；每循环一次表示一次运算，根据语句print(″运算次数为：″，n)可知，变量n的功能是统计运算次数，因此③处代码为n＋＝1或n＝n＋1。
(2)程序执行时，输入n的值为120时，变量x的值的变化过程为：120 →60→30→15→46→23→70→35→106→53→160→80→40→20→10→5→16→8→4→2→1，因此共运算20次。
10.C [本题考查递归算法的应用。f(100)＝100＋f(98)，f(98)＝98＋f(96)，而后面的参数均为偶数，依此类推，可得：f(100)＝100＋98＋96＋94＋…＋2＝2550。]
11.A [本题考查递归算法。A选项递归函数中包含一个递推公式，先依次调用自己，再进行回归。B选项通过栈调用来实现。C选项以第6项fibo(5)为例，可以画出二叉树来表示，
若根节点为n，则树的高度为n，深度为n的满二叉树的节点数量(函数的调用次数)为n2－1，因此时间复杂度为O(n2)。D选项fibo(3)被调用了 2次。
fibo(5)＝fibo(4)＋fibo(3)；
fibo(4)＝fibo(3)＋fibo(2)。]
12.(1)递归算法 (2)①fibo(x－1)＋fibo(x－2) ②fibo(n)
解析 本题主要考查的是递归算法的实现过程。根据题意分析递归公式为：当x<＝2时，fibo(x)＝1；当x>2时，fibo(x)＝fibo(x－1)＋fibo(x－2)，所以空①处答案为fibo(x－1)＋fibo(x－2)；空②处调用递归函数fibo()计算数列的第n项，故答案是fibo(n)。
13.①lista[k]＝i ②comb(i－1，k－1) ③comb(n，r)
解析 列表lista存放求出的组合的数字，本题中将确定的k个数字组合的第一个数字放在lista[k]中，变量c用来统计组合数，当一个组合求出后，进行计数，并将lista列表中的一个组合输出，因此①处语句为lista[k]＝i；当组合的第一个数字选定时，其余的数字是从余下的m－1个数中取k－1数的组合，即将求m 个数中取k个数的组合问题转化成求m－1个数中取k－1个数的组合问题，因此②处代码为comb(i－1，k－1)；③处代码的功能是调用递归函数comb，参数分别为n和r，因此，③处代码为comb(n，r)。课时3 数据排序
一、基础巩固
1.下列有关冒泡排序算法的说法，不正确的是( )
A.使用冒泡排序算法完成n个数据的排序，共需要进行n－1趟
B.冒泡排序是通过比较相邻两个元素的大小和位置交换来完成的
C.冒泡排序进行时，相邻元素的比较和交换只能从前往后进行
D.使用冒泡排序算法完成6个数据的排序，最坏情况下，数据交换次数为15次
2.采用冒泡排序算法完成数据序列“9，8，7，6，5，2，3，4”的升序排序，则数据交换的次数为( )
A.18次 B.22次 C.25次 D.27次
3.有8个学生的体重(单位：公斤)依次为“50.5，60.8，65.6，80.8，48.5，52.1，61.3，70.2”，若采用冒泡排序算法对其进行升序排序，则第3遍的排序结果是( )
原始数据 50.5，60.8，65.6，80.8，48.5，52.1，61.3，70.2
第1遍完成后的数据为 48.5，50.5，60.8，65.6，80.8，52.1，61.3，70.2
第2遍完成后的数据为 48.5，50.5，52.1，60.8，65.6，80.8，61.3，70.2
第3遍完成后的数据为
A.48.5，50.5，52.1，60.8，65.6，61.3，80.8，70.2
B.48.5，50.5，52.1，60.8，61.3，65.6，70.2，80.8
C.48.5，50.5，52.1，60.8，65.6，70.2，80.8，61.3
D.48.5，50.5，52.1，60.8，61.3，65.6，80.8，70.2
4.对列表b中的n个元素进行降序排序，其排序算法的Python部分程序段如下：
b＝[34，435，23，98，788，30，77]
n＝len(b)
count＝0
for i in range(0，n－1)：
for j in range(①__________)：
if ②________________：
count＝count＋1
b[j]，b[j＋1]＝b[j＋1]，b[j]
print(″排序后的序列为：″，b)
print(″数据交换次数为：″，count)
程序划线①②处应填入的语句为( )
A.①0，n－i－1 ②b[j]B.①n－1，i，－1 ②b[j]>b[j－1]
C.①0，n－i ②b[j]D.①0，n－i－1 ②b[j]>b[j＋1]
5.有如下 Python 程序段：
a＝[19，17，6，9，8]
n＝len(a)
f＝True；i＝4；k＝0
while i>0 and f：
f＝False
for j in range(i):
if a[j] a[j]，a[j＋1]＝a[j＋1]，a[j]
k＝k＋1；f＝True
i＝i－1
该程序段执行后，下列说法正确的是( )
A.数组a各元素的值是：6 8 9 17 19
B.变量 k 的值为 3
C.数组元素 6 在此过程中共交换了 3 次
D.变量 i 的值为 2
6.有如下Python程序段：
b＝[5，32，17，22，15，36，41，55]
count＝len(b)
for i in range(1，3)：
for j in range(1，count－i)：
if b[j] b[j]，b[j＋1]＝b[j＋1]，b[j]
经过该程序段“加工”后，列表b中的元素为( )
A.[32，22，17，36，41，55，15，5]
B.[32，22，36，41，55，17，15，5]
C.[5，32，22，36，41，55，17，15]
D.[5，32，36，41，55，22，17，15]
7.如下 Python 程序段：
s＝list(″bcaabca″)
n＝len(s)
for i in range(1，n)：
for j in range(n－1，i－1，－1)：
if s[j]＝＝'a' and s[j－1]！＝'a'：
s[j]，s[j－1]＝s[j－1]，s[j]
print(s)
执行该程序段后，输出的内容为( )
A.['b'，'c'，'b'，'c'，'a'，'a'，'a']
B.['b'，'b'，'c'，'c'，'a'，'a'，'a']
C.['a'，'a'，'a'，'b'，'c'，'b'，'c']
D.['a'，'a'，'a'，'b'，'b'，'c'，'c']
8.采用冒泡排序算法，对某数组数据进行排序，经过一轮后的结果是“2，3，9，5，6，7”，那么下列说法不正确的是( )
A.这轮排序，有可能没发生数据交换
B.这轮排序，有可能只发生了1次数据交换
C.排序结束后，数据是升序的
D.完成全部排序后，数据交换的次数和冒泡的方向无关
9.有如下 Python 程序段：
a＝[3，6，7，2，8，2]; b＝[5，3，7，7，7，4]
for i in range(len(a)－1)：
for j in range(0，len(a)－i－1)：
if a[j]>a[j＋1] or a[j]＝＝a[j＋1] and b[j] a[j]，a[j＋1]＝a[j＋1]，a[j]
b[j]，b[j＋1]＝b[j＋1]，b[j]
执行上述程序段后，a[1]与 b[1]的值分别是( )
A.8，7 B.7，7 C.2，4 D.2，7
10.使用列表a 和列表b 分别存储学生的总分和考号，已知考号为b[i]的学生的总分为a[i]，使用 Python 编程实现如下功能：将成绩数据“按总分降序排序、总分相同按学号升序排序”，代码如下。
n＝len(a)
for i in range(1，n)：
for j in range(0，n－i)：
ifor and ：
a[j]，a[j＋1]＝a[j＋1]，a[j]
b[j]，b[j＋1]＝b[j＋1]，b[j]
上述程序段中方框处可选代码为： ①a[j]>a[j＋1]
②a[j]＝＝a[j＋1] ③a[j]b[j＋1]则(1)(2)(3)处代码依次为( )
A.③②④ B.①⑤⑥ C.③②⑥ D.①⑤④
11.某 Python 程序如下：
s＝[2，3，4，9，7，8，5]
n＝len(s)
for i in range(n－1)：
for j in range(n－1，i，－1)：
if s[j] s[j]，s[j－1]＝s[j－1]，s[j]
下列说法正确的是( )
A.整个加工过程总的交换次数为 21
B.该程序段执行后，s 的值为[9，8，7，5，4，3，2]
C.若s的初始值已有序，则该算法的时间复杂度为 O(1)
D.每一遍加工中，最小的元素“上浮”
二、能力提升
12.火车调度台是实现火车车厢整理的平台，当相邻2节车厢序号不符合整理要求时，可以对调2节车厢，实现序号顺序调整。相邻2个进行符合目标的交换，和我们学习的冒泡排序思想一致，所以这个调度过程可以用冒泡排序实现。为了提高效率，对冒泡排序做了优化，请完善下列代码：
nums＝[3，1，2，4，5，6]
①____________
k＝n－1
for i in range(n－1)：
②______________
for j in range(k)：
if (nums[j]>nums[j＋1])：
nums[j]，nums[j＋1]＝nums[j＋1]，nums[j]
③____________
ex_flag＝True
if ex_flag：
break
print(nums)
13.小明基于冒泡排序思想设计了一个改进的排序算法。该算法先用冒泡法将列表b中奇数位置的元素、偶数位置的元素分别进行排序，然后再进行后续处理。算法的Python程序段如下，请回答下列问题。
b＝[26，12，30，23，32，28，49，35，38]
n＝len(b)
for i in range(1，(n－1)∥2)：
for j in range(0，n－i*2)：
if ①________________：
b[j]，b[j＋2]＝b[j＋2]，b[j]
for i in range(1，n∥2＋1)：
j＝2*i－1
if b[j] b[j]，b[j－1]＝b[j－1]，b[j]
for i in range( )：
t＝b[i]
j＝i－1
while t b[j＋1]＝b[j]
j－＝1
②____________________
print(″处理后的数据序列为：″，b)
(1)加框处的代码有误，请改正。
(2)请在程序划线处填入合适的代码。
14.小明为了研究冒泡排序过程中数据的“移动”情况，编写了一个Python程序，功能如下：第一行显示排序前的数据，输入初始位置(即下标值)后，输出指定初始位置的数据在排序过程中的位置变化情况，最后一行输出排序后的数据。程序运行示例如图所示。
请输入初始位置(索引值)：2 排序前数据序列为：[43，23，65，12，26，33，58，19] 位置变化情况：2→1→0 排序后的数据序列为：[65，58，43，33，26，23，19，12]
实现上述功能的Python程序如下，请回答下列问题。
a＝[43，23，65，12，26，33，58，19]
n＝len(a)
pos＝int(input(″请输入初始位置(索引值)：″))
①________________
print(″排序前数据序列为：″，a)
for i in range(1，n)：
for j in range(0，n－i)：
if ②________________：
a[j]，a[j＋1]＝a[j＋1]，a[j]
if pos＝＝j：
pos＝j＋1
s＝s＋″→″＋str(pos)
elif ③________________：
pos＝j
s＝s＋″→″＋str(pos)
print(″位置变化情况：″＋s)
print(″排序后的数据序列为：″，a)
(1)请在程序划线处填入合适的代码。
(2)程序运行样例如图所示，若输入的初始位置(索引值)为4，则输出的位置变化情况为__________________。
15.要向可容纳88966名观众的卢赛尔球场派送外卖是一项艰巨的任务，为了方便外卖派送，将球场观众席划分为A、B、C、D、E、F、G、H共8 个区，派单平台可以根据各区域订单数量安排派送人员，以提高外卖派送效率(一个派送人员只安排一个区域)，平台根据订单总量与空闲派送人员数量计算人均派单量，按平均派单数计算各区域所需派送人员，但按此方法分配派送人员，人员总数可能超过空闲派送人员数，则删除超额派送人数，删除规则如下：每个有订单的区域至少保留一个派送人员，每个区域最多减去一个派送人员，优先删除派单尾数最少的区域中的派送人员，如果派单尾数相同，则在分配到派送人员数最多的区域中去掉一个派单人员，例如：A～H区域的订单数量分别为[468，329，392，247，38，180，263，82]，此时空闲派单人员数为30人，人均派单数为67，则各区域分配的派单人员数量分别为7、5、6、4、1、3、4、2，合计32个派送人员，需减掉2超额派送人员，即从D区和H区派送人员中各减去1个。如下表所示：
球场 区域 A B C D E F G H 合计
订单 数量 468 329 392 247 38 180 263 82 1999
所需派 送人员 7 5 6 4 1 3 4 2 32
派单 尾数 66 61 57 46 38 46 62 15 391
去除派 单人员 －1 －1 －2
实际派送 人员数 7 5 6 3 1 3 4 1 30
(1)数据如上表所示，如果F区退掉2份订单，重新计算并分配派送人员(整体调整)，F区派送人员的人均派单量是________。
(2)实现上述功能的Python程序如下，请在画线处填写正确的代码。
#从数据库中读取各订单所在区域，如
a＝['A'，'B'，'H'，'F'，……]
qyn＝8 #区域数量
psryn＝30 #配送人员数量
rs＝round(len(a)/psryn)
b＝[]
for i in range(qyn)：
c＝chr(i＋65) #A的ASCII码是65
b.append([c，0，0]) #生成二维列表b＝[['A'，0，0]，['B'，0，0]……]
for i in a： #统计各区域订单数量
①________
s＝0
for i in range(qyn) ：
②________
if b[i][1]%rs！＝0：
b[i][2]＋＝1
s＋＝b[i][2]
k＝s－psryn
i＝0
while k>0：
for j in range(qyn－1，i，－1)：
if ③______：
b[j－1]，b[j]＝b[j]，b[j－1]
if b[i][2]>1：
b[i][2]－＝1
k－＝1
i＋＝1
(3)若函数中语句“s＋＝b[i][2]”缩进到了“if b[i][1]%rs！＝0：”模块内，题中所给的样例数据运行结果__________(是/否)受到影响，将样例“E”区订单数量38修改为__________能测出程序存在的问题。
16.学校物品室有n个箱子(箱子上分别有编号1、2、3…n)，箱子里存有数量不一的物品。有m位学生前来领取物品(物品总量足够领取)，每位学生优先从物品数量最多的箱子领取，数量不够时，再从下一个数量最多的箱子领取。小郑设计了一个程序，按箱子编号从小到大依次输入每个箱子的物品数量，依次输入每位学生需要领取物品的数量，按顺序显示每个学生领取物品的箱子编号，并显示领取结束后非空箱子的编号和剩余物品数量。运行界面如图所示。
物品数量：[12，9，5，5，3，2] 箱子编号：[4，2，1，6，5，3] 领取数量：[20，6，7，2] 第1位学生领取物品的箱子编号依次为：4 2 第2位学生领取物品的箱子编号依次为：1 6 第3位学生领取物品的箱子编号依次为：6 5 第4位学生领取物品的箱子编号依次为：3 剩余物品数量：2号箱子：1
回答下面问题：
(1)如果1号到5号箱子的物品数量分别是25，16，9，5，3，每位学生需要的物品数量分别是19，18，10，3，则第3位学生领取物品的箱子编号按顺序依次是3号、________(填整数)号。
(2)实现上述功能的程序如下，请在划线处填入合适的代码。
#依次输入物品数量存入列表a，箱子上的编号(1 到 n)依次存入列表bh，箱子数量存入变量 n，并按物品数量从多到少对箱子排序，代码略。
#依次输入学生需要领取物品的数量存入数组 b，学生人数存入变量 m，代码略
p＝0；q＝0
for i in range(m)：
num＝0
while numnum＋＝a[q]
a[q]＝0
①________________
s＝″第″＋str(i＋1)＋″位学生领取物品的箱子编号依次为：″
for j in range(p，q)：
s＋＝str(bh[j])＋″″
print(s)
if num>b[i]：
a[q－1]＝②________________
q＝q－1
for j in range(③________________): #维护非空箱子降序序列(按箱子中剩余物品数量)
if a[j] a[j]，a[j＋1]＝a[j＋1]，a[j]
bh[j]，bh[j＋1]＝bh[j＋1]，bh[j]
p＝q
s＝″剩余物品数量：″
for i in range(0，n)：
if a[i]>0：
s＝s＋str(bh[i])＋″号箱子：″＋str(a[i])
print(s)
课时3 数据排序
1.C [冒泡排序进行时，相邻元素的比较和交换可以从前往后进行，也可以从后往前进行，因此答案为C。]
2.C [例如排序方向从前往后进行，排序过程如下：
原始数据 9，8，7，6，5，2，3，4 交换次数
第1遍完成后的数据为 8，7，6，5，2，3，4，9 交换7次
第2遍完成后的数据为 7，6，5，2，3，4，8，9 交换6次
第3遍完成后的数据为 6，5，2，3，4，7，8，9 交换5次
第4遍完成后的数据为 5，2，3，4，6，7，8，9 交换4次
第5遍完成后的数据为 2，3，4，5，6，7，8，9 交换3次
第6遍完成后的数据为 2，3，4，5，6，7，8，9 不交换
第7遍完成后的数据为 2，3，4，5，6，7，8，9 不交换
排序完成时，共进行7＋6＋5＋4＋3＝25次，因此，答案为C。]
3.D [观察第1遍和第2遍排序可知，排序是从后往前进行的，排序方式为升序，因此容易得出第3遍的排序结果为48.5，50.5，52.1，60.8，61.3，65.6，80.8，70.2，答案为D。]
4.A [根据交换语句b[j]，b[j＋1]＝b[j＋1]，b[j]可知，排序方向为从前往后进行的，因此①处应为0，n－i－1, ②处代码为b[j]5.D [本题考查冒泡排序算法。相邻两个数据a[j]6.C [本题主要考查的是冒泡排序算法的程序实现。该程序段的功能是：采用冒泡排序算法对后7个数据进行2趟降序排序，数据比较是从前往后进行的，需注意的是列表b中的第1个元素(索引位置0)不参与排序，第1遍排序后列表b中的元素为[5，32，22，17，36，41，55，15]，第2遍排序后的数据序列为[5，32，22，36，41，55，17，15]。因此，答案为C。]
7.C [本题考查冒泡排序的变形。根据 if 条件s[j]＝＝'a' and s[j－1]！＝'a'可以看出，取字符串 s 中字符时，若当前字符 s[j]为'a'但 s[j－1]不为'a'，交换s[j－1]与s[j]的位置。因此，该程序段的功能为将字符'a'前移，其他字符保持原位置不变，交换后的结果为C.['a'，'a'，'a'，'b'，'c'，'b'，'c']。]
8.A [本题考查冒泡排序。经过一轮后最小数在最前面，可知，该冒泡排序是从后往前冒泡，升序。A选项原始数据最小数2不在最前面，一定会发生交换。若原始数据就是一趟排序结果，9在中间，无论是从后往前，还是从前往后，都要发生数据交换。B选项若原始数据如果为“2，3，5，9，6，7”，那么就发生了一次交换。C选项从一趟结果来看，是升序排列。D选项数据的交换取决于逆序对的个数，与排序方向无关。]
9.C [本题考查双关键字排序。主关键字为a数组，次关键字为b数组，当a[j]>a[j＋1]就交换数据，表示升序。当a[j]＝＝a[j＋1] and b[j]10.C [本题考查冒泡排序。从 for j in range(0，n－i)可知，从前向后冒泡，相邻两数两两比较；比较规则如下：第 j 个比 j＋1 个成绩小则交换，选语句 ③。第 j 个和第 j＋1 个成绩相同，选语句②，且第 j 个考号比第 j＋1 个大，选语句⑥。]
11.D [本题考查排序算法。当条件s[j]12.①n＝len(nums) ②ex_flag＝False ③k＝j
解析 本题主要考查冒泡排序算法的优化。题目中实现优化的方法是，当某趟排序过程中没有发生数据的交换时，说明数据已经有序，结束数据的排序；同时，通过记录最后发生数据交换的位置，缩小数据排序的范围。空①处n＝len(nums)，获得数据的规模，空②处ex_flag＝False，当发生数据交换时，ex_flag会被赋值为True，空③处k＝j表示记录最后发生数据交换的位置。
13.(1)2，n，2 (2)①b[j]>b[j＋2] ②b[j＋1]＝t
解析 本题主要考查排序的综合应用。本题在排序过程中，使用到了冒泡排序和插入排序算法，本题的算法思想是：首先利用改进的冒泡排序分别对数列b中奇数位置和偶数位置上的元素进行升序排序，排序结束后的数据序列特点为：奇数位置上的元素已升序排列，偶数位置上的元素已升序排列；然后从第2个元素(索引位置1)开始，让偶数位置上的元素和它前面奇数位置上的元素比较，通过数据交换使得它们变为升序，此时奇偶数据对也已升序排列；最后从第3个元素位置，将奇数位置上的元素插入到前面有序的数列中，从而实现整个数列的升序排序。因此，加框处的代码修改为2，n，2，划线①处应填入的语句为b[j]>b[j＋2]。在插入排序中需注意的是当前元素应插入的位置为j＋1，因此，划线②处应填入的语句为b[j＋1]＝t。
14.(1)①s＝str(pos) ②a[j](2)4→3→2→3→4
解析 本题主要考查的是冒泡排序算法的综合应用。(1)字符串s记录的是初始位置元素的位置变化情况，显然，其初值为pos，需注意的是应先将pos转换为字符串后再赋值于s，因此①处代码为s＝str(pos)；数据的比较和交换是从左往右进行的，根据运行示例可知，是进行降序排序，因此②处语句为a[j](2)若输入的初始位置(索引值)为4，即研究列表中第5个数据(26)的位置变化，在排序过程中，26的位置变化情况为4→3→2→3→4。
15.(1)89 (2)①b[ord(i)－65][1]＋＝1 ②b[i][2]＝b[i][1]∥rs ③b[j－1][1]%rs>b[j][1]%rs or b[j－1][1]%rs＝＝b[j][1]%rs and b[j－1][2]解析 本题考查二维数组应用和冒泡排序算法。(1)优先删除派单尾数最少区域中的派送人员，F区退掉2份订单，尾单数量为44，实际派送人员为2人，人均派单量为178/2＝89。(2)①统计各区域订单数量，从条件b[i][1]%rs！＝0来看，b[i][1]存储的是各区域的订单数量，数据库中读取各订单所在区域，需先将a数组中A－H转换成0－7的索引号，再对b数组进行累加计数。②计算所需派送人员。从语句k＝s－psryn来看，s是所需派送人员人数之和，每个区域产生尾单后，所需派送人员增加1人，因此先计算整数倍的值。③找到去除派单人员的条件。k是需去除派单人员，按尾单人数采用冒泡降序排序，找出符合条件最大的k个值，优先删除派单尾数最少的区域中的派送人员，如果派单尾数相同，则在分配到派送人员数最多的区域中去掉一个派单人员，因此是一个双关键字排序算法。(3)样题给出数据的尾单数均不为0，因此条件b[i][1]%rs！＝0始终成立，是否缩进不影响结果，只有当尾单出现为0时，影响结果。
16.(1)1 (2)①q＝q＋1 ②num－b[i] ③q，n－1
解析 (1)第1位学生在1号箱子里领取19，第2位学生在2号中领取16，在3号中领取2。剩下箱子中数量依次为6，0，7，5，3，因此第3位同学领取3号箱子和1号箱子。(2)循环for i in range(m)中，变量i表示第几个学生，他应该领取的数量为按物品数量b[i]，变量num表示他已经领取的数量，当条件num>b[i]成立时，②num－b[i]。③从多到少对箱子排序，比较对象为a[j]和a[j＋1]，因此从位置q到n－2，当j＝n－2时，j＋1达到终点。课时4 顺序查找
一、基础巩固
1.在数组d中存储的数据依次为“17，11，36，48，19，22，39，56，17，100”。现使用顺序查找算法在数组d中查找数据17，共需查找的次数为( )
A.0次 B.1次 C.9次 D.10次
2.在数组d中存储的数据依次为“10，22，16，80，19，35，41，88，66，71”。现使用顺序查找算法在数组d中查找数据99，共需查找的次数为( )
A.0次 B.10次 C.11次 D.无穷次
3.有如下Python程序段：
a＝″import trutle as t″
key＝input(″Please input key：″)
s＝″″
c＝0
for i in a：
if i＝＝key：
s＝s＋i
c＋＝1
if c>0：
print(s，c)
程序执行时，输入key的值为t，则输出的内容为( )
A.t 3 B.tttt 3 C.t 4 D.tttt 4
4.有如下Python程序段：
b＝[12，45，76，3，43，45，34，64，75，45，1]
n＝len(b)
key＝int(input(″key＝″))
i，c＝n－1，0
while i>＝0：
if b[i]＝＝key：
c＋＝1
ans＝i
i－＝1
if c>0：
print(″Find！pos＝″，ans)
else：
print(″Not found！″)
程序执行时，输入key的值为45，则输出的内容为( )
A.Not found! B.Find！pos＝1
C.Find！pos＝5 D.Find！pos＝9
5.有如下Python程序段：
key＝input(″Please input：″)
wordlist＝[″playsome″，″some″，″handsome″，″somethings″，″fulsomes″，″airsome″，″adventuresome″，″fearsome″]
n＝len(wordlist)
pos＝－1
maxlen＝0
i＝0
while iif key in wordlist[i]：
if maxlen maxlen＝len(wordlist[i])
pos＝i
i＝i＋1
if pos！＝－1：
print(wordlist[pos])
else：
print(″Fail！″)
程序执行时，输入字符内容为“some”(不包含引号)，则输出的内容为( )
A.some B.somethings
C.fulsomes D.adventuresome
二、能力提升
6.编写一个Python程序，功能为：输入关键字后，在书目清单列表中查找书名中包含关键字的书，并统计数量，然后在所有找到的书目中找出价格最贵的书。
书目清单存储在列表book中，每本书包含三个内容：书名、作者和价格。
程序运行示例如图所示：
节目清单为：
['Python编程从入门到实践'，'埃里克·马瑟斯'，89.0] ['C语言程序设计入门教程'，'史蒂芬·普拉达'，187.0] ['Javascript高级程序设计'，'马特·弗里斯比'，129] ['R语言实战'，'卡巴科弗'，99.0] ['Java核心技术卷Ⅰ'，'凯·S·霍斯特曼'，149.0] ['Python基础教程'，'Magnus Lie Hetland'，99.0] ['零基础学C＋＋'，'明日科技'，79.8] ['Python学习手册'，'马克·卢茨'，219.0] ['Python数据结构与算法分析'，'布拉德利·米勒'，79.0] 请输入关键词：Python 符合要求的书单有： ['Python编程从入门到实践'，'埃里克·马瑟斯'，89.0] ['Python基础教程'，'Magnus Lie Hetland'，99.0] ['Python学习手册'，'马克·卢茨'，219.0] ['Python数据结构与算法分析'，'布拉德利·米勒'，79.0] 共找到4本 价格最贵是：['Python学习手册'，'马克·卢茨'，219.0]
实现上述功能的Python程序如下，请在程序划线上填入合适的代码。
#列表book中存储了书本的信息，列表内容略
n＝len(book)
print(″书目清单为：″)
for i in range(0，n，3)：
print(book[i：i＋3])
keyword＝input(″请输入关键词：″)
i＝0
print(″符合要求的书单有：″)
count，maxprice，posi＝0，0，－1
while ①________________：
if ②________________：
print(book[i：i＋3])
count＋＝1
if maxprice maxprice＝book[i＋2]
③________________
i＝i＋3
print(″共找到″，count，″本″)
if posi＝＝－1：
print(″对不起，没有找到你要的书！″)
else：
print(″价格最贵是：″，book[posi：posi＋3])
7.列表a中相邻两个数据无重复，现要查找连续最大步长的升序段。具体描述如下：
(1)步长指的是升序段中最后元素和最初元素的差值；
(2)有相同步长的升序段则输出最先找到的升序段。
程序运行效果如图所示。
数据序列为：[1，24，1，2，16，25，33，4，10，32，46，47，56，23，50] 最大步长的升序段为：[4，10，32，46，47，56]
实现上述功能的Python代码如下，请回答下列问题。
#读入数据并存储在列表a中，代码略
print(″数据序列为：″，a)
n＝len(a)
maxp＝1
mstep＝ans＝t＝maxt＝0
if a[1]>a[0]：
flag＝True
else：
flag＝False
else False
for i in range(0，n－1)：
if a[i＋1]>a[i]：
if flag＝＝True：
①________________
t＋＝1
if mstep>ans：
ans，maxp，maxt＝mstep，i＋1，t
else：
mstep＝a[i＋1]－a[i]
t＝1
if mstep>ans：
ans，maxp＝mstep，i＋1
②________________
flag＝True
else：
flag＝False
st＝[]
for i in range(③______________)：
st.append(a[i])
print(″最大步长的升序段为：″，st)
(1)若数据序列为“12，15，20，25，50，2，8，19，45，18，20，25，30，36，38，11，30”则最大步长的升序段为____________________。
(2)请在划线处填入适当的代码。
8.利用某火车购票系统购票，购买者输入“出发站”、“目的站”，系统会统计两站之间的占座情况，根据空座数量(出发站至目的站之前一直是空的座位即为空座)返回余票情况，购买者根据余票信息购买车票，获得具体座位号。
根据上述功能，小王编写了一个Python程序模拟该购票系统，以“杭台高铁”为例，全线共设9个车站，某趟列车共有8节车厢，每节车厢共有17排，每排5个座位(编号分别是A、B、C、D、F)，共680个座位，某时刻的占座情况如图所示。具体设计如下：从数据库中读取占座情况存储在列表seat中(例如：序号为84座位各站点占座情况，在seat[84]中表示为[1，1，0，0，0，0，1，1]，索引号2至5的值都为0，则当出发站为临海站，目的站为上虞南站，该座位为空座)，然后根据购买者输入的出发站和目的站的站点名称，统计空座数量及相应的座位序号，根据购票信息，输出购票的具体座位(其中连票数量尽可能多)
杭台高铁某—时刻占座情况—览表
(0表示空座，1表示占座)
(1)主程序，根据购票步骤，请在划线处填入合适的代码。
#获取列车每个座位号及其在各站点占座情况，存储在二维列表 sat 中，代码略
site＝[″温岭″，″台州″，″临海″，″天台山″，″嵊州新昌″，″嵊州北″，″上虞南″，″绍兴北″，″杭州东″]
begin＝site.index(input(″输入出发站：″)) #index 方法用于获取列表的索引号
end＝site.index(input(″输入目的站：″))
tic＝gethavet((begin，end)) #获取基于出发站和目的站前的所有空座座位序号列表
if len(tic)>0：
num＝int(input(″尚有余票″＋①________＋″张，请输入购买的数量：″))
if num<＝len(tic)：
seatno，ser＝assignment(num，tic) #获取相应座位序号及连票数量
#seatno 列表存储格式如：[4，5，6，7，8]或[4，5，6，8，9]
print(″购票″＋str(num)＋″张，其中连票数量″＋str(ser)＋″张！座位信息如下：″)
snum＝['A'，'B'，'C'，'D'，'F'] #每排座位的编号
for k in seatno：
coach，row＝k∥85＋1，k % 85∥5＋1
②________________
print(str(coach)＋″车厢″＋str(row)＋″排″＋number＋″座″) #将新的占座数据写入数据库，代码略
else：
print((″购买数量不得大于余票数量！″))
else：
print(″余票不足！″)
(2)获取余票数据，如下的 gethavet 函数，获取出发站至目的站前的空座座位序号，保存在列表 s 中并返回。请在划线处填入合适的代码。
def gethavet(x，y)：
s＝0
for i in range(680)：
nows＝seat[i] #nows 存储当前序号各个站点的占座情况
if ③________________：
s.append(i)
return s
(3)座位分配，如下的 assignment 函数，按序号查找连票，如果找到一组连票数量等于购买的数量，则退出查找并返回相应信息，若连票数量不足，则补充座位数量后返回。请在划线处填入合适的代码。
def assignment(n，tic)：
maxs，head，tmp＝1，0，1
for i in range(1，len(tic))：
if ④________________：
tmp＋＝1
if tmp>maxs：
maxs＝tmp
head＝i－maxs＋1 #记录连票的开始位置
if maxs＝＝n：
break #满足需要的数量，结束查找
else：
tmp＝1
#将连票的座位序号存于列表 slist，若连票数量不足则补充座位数量，代码略
return [slist，maxs]
课时4 顺序查找
1.B [本题主要考查的是顺序算法。数组d中有2个17，顺序查找默认只找到第一个满足条件的数据就结束查找，因此找到第1个17后就结束查找，即查找1次，答案为B。]
2.B [本题主要考查的是顺序算法。数组d中没有数据99，因此需要全部查找一遍才结束。故共查找10次，答案为B。]
3.D [本题主要考查的是顺序算法的程序实现。本题程序的功能是在字符串a中查找key的值，若找到，则将key的值拼接在字符串s中，并统计个数，因此输出结果为tttt 4，答案为D。]
4.B [本题主要考查的是顺序算法的程序实现。本题程序的功能是在列表b中查找key的值，若找不到，则输出“Not found！”；如果找到且有多个时，记录的是最后一个与key相等的元素的索引位置，需注意的是，本题是从列表最后一个元素往前进行查找，因此输入key为45时，找到最后一个45在列表b中的位置为1，故答案为B。]
5.D [本题主要考查的是顺序查找算法的程序实现。本程序的功能是在列表wordlist中查找包含some的单词中长度为最长的单词，因此，答案为D。]
6.①i<＝n－3 ②keyword in book[i] ③posi＝i
解析 本题主要考查的是顺序查找算法的综合应用。每本书包含三个信息：书名、作者和价格，即最后一本书的书名book[n－3]，因此①处代码为i<＝n－3；本题中查找是书名中包含的关键字的书，因此可用in运算实现，即②处代码keyword in book[i]；当找到当前价格最高的书时，修改maxprice的值，还要记录当前的书在列表中的索引位置，因此，③处代码为posi＝i。
7.(1)[2，8，19，45] 或 2，8，19，45 或2 8 19 45 (2)①mstep＋＝a[i＋1]－a[i] 或 mstep＝mstep＋a[i＋1]－a[i] ②maxt＝1或maxt＝t ③maxp－maxt，maxp＋1
解析 (1)根据连续最大步长的升序段的含义，数据序列中的最大步长升序段为[2，8，19，45]或2，8，19，45或2 8 19 45；(2)题目中描述的步长是指升序段中最后元素和最初元素的差值，即升序段中相邻两个元素的差值之和，变量mstep记录当前升序段的步长，变量ans则记录最大步长，因此①处代码为mstep＋＝a[i＋1]－a[i]，或写为 mstep＝mstep＋a[i＋1]－a[i]；若当前相邻两个元素为升序(a[i＋1]>a[i])，且它们的差值为之前所有升序段中的最大步长，则修改ans、maxp的值分别为mstep和i＋1，同时初始化maxt的值为1，因此②处代码为maxt＝1；划线③处的循环表示输出将最大步长升序段的数据存放在列表st中，最大步长升序段的数据的索引位置为maxp－maxt～maxp，因此③处代码为maxp－maxt，maxp＋1。
8.(1)①str(len(tic)) ②number＝snum[k%5] (2)sum(nows[x：y])＝＝0或nows[x：y].count(1)＝＝0或nows[x：y].count(0)＝＝y－x或not 1 in nows[x：y] (3)tic[i]＝＝tic[i－1]＋1
解析 (1)tic存储可用的空座序号列表。第①空要求表示可用空座的数量，即len(tic)。输出座位时，分别使用conch、row、number变量存储当前座位的车厢、排、座位编号。对于每个座位序号kinsentno，通过对85的整除和模运算计算了车厢和排序号，很多学生会思维惯性地用85继续当作主要参数计算number，而实际上座位编号是在A～F上循环编号的。(2)完善主程序中调用的gethavet函数。函数功能是计算空座列表。nows[x：y]表示当前座位在出发站到终点站前的空座情况，只要该连续站上均为空座即可售票。(3)寻找连续的座位，观察代码for i in range(1，len(tic))，应该是当前项与前一项比较。课时5 二分查找
一、基础巩固
1.列表b中存储了8个元素，依次为60、50、40、30、25、20、15、10，下列选项中不正确的是( )
A.使用对分查找查找数据60，共查找了3次
B.使用顺序查找查找数据60，共查找了1次
C.使用对分查找查找数据35，共查找了3次
D.使用顺序查找查找数据35，共查找了8次
2.列表数组a中存储了6个元素，依次为105、110、112、118、120、126，若采用二分查找算法在该列表中查找数据126，则在查找126的过程中依次被访问到的元素为( )
A.118、126 B.118、120、126
C.112、120、126 D.112、120、118、126
3.某二分查找算法的Python程序段如下：
list1＝[2，6，8，9，12，15，18，20]
key＝int(input(″请输入待查找的数据：″))
s＝″″
c，i，j＝0，0，7
while i<＝j：
c＋＝1
m＝(i＋j)∥2
if list1[m]＝＝key：
s＝s＋str(m)
break
if list1[m]>key：
j＝m－1
else：
i＝m＋1
s＝s＋str(m)＋″→″
print(s)
执行该程序段，输入待查找的数key为12，则输出的结果是( )
A.4→5→ B.4→6→5
C.3→5→4→ D.3→5→4
4.某二分查找算法的Python程序段如下：
list1＝['Carrot'，'Celery'，'Garlic'，'Lettuce', 'Mooli', 'Onion'，'Potato'，'Tomato']
key＝list1[2]
left，right＝0，len(list1)－1
c＝0
while left<＝right：
m＝(left＋right)∥2
c＝c＋1
if list1[m]>key：
right＝m－1
else：
left＝m＋1
print(list1[left])
程序执行后，下列说法正确的是( )
A.变量c的值为4
B.程序输出的结果为Lettuce
C.变量left的值为2
D.变量right的值为3
5.某二分查找算法的Python程序段如下：
key＝int(input(″请输入查找键：″))
i＝0
j＝8
f＝[0]*9
while i<＝j：
m＝(i＋j)∥2
f[m]＝1
if a[m]＝＝key：
break
if a[m]>key：
j＝m－1
else
i＝m＋1
整型数组a存储了一个升序序列，执行该程序后，输入待查找数，下列选项中，f数组中各元素值不可能是( )
A.1，1，0，0，1，0，0，0，0
B.0，0，0，0，1，0，0，0，0
C.0，0，0，0，1，1，1，1，0
D.0，1，1，1，1，0，0，0，0
6.有如下对分查找程序，A为按非降序排序的整型数组。
import random
key＝random.randint(0，4)*2＋20
a＝[12，14，15，15，19，x，20，24，y，26]
c＝0；n＝10；ans＝0
i＝0；j＝n－1
while i<＝j：
m＝(i＋j)∥2
if a[m]<＝key ：
i＝m＋1
else：
j＝m－1
c＋＝1
测试所有可能的key值，程序执行后c均等于4，下列正确的x，y值可以为( )
A.19，25 B.20，26 C.20，25 D.20，24
7.有如下Python程序：
import random
nums＝[11，23，35，44，57，68，76，89]
target＝random.randint(20，70) #随机生成[20，70]区间内的一个正整数
lst＝[]
left，right＝0，len(nums)－1
while left<＝right：
lst.append([left，right]) #为 lst追加一个元素
mid＝(left＋right)∥2
if nums[mid]＝＝target:
break
elif nums[mid] left＝mid＋1
elif nums[mid]>target:
right＝mid－1
该程序段运行后，列表lst的长度不可能为( )
A.1 B.2 C.3 D.4
8.有如下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
9.某对分查找算法的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]
10.有如下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 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
二、能力提升
11.有如 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
12.有如下 Python 程序段：
import random
a＝[90，15，40，72，59，32，81，6]
b＝[7，1，5，2，4，3，6，0]
i，j＝0，len(a)－1
key＝random.randint(30，60)
p＝－1
while i<＝j：
m＝(i＋j)∥2
if a[b[m]]＝＝key:
p＝b[m]
break
elif a[b[m]] i＝m＋1
else：
j＝m－1
print(p)
程序运行后，变量 p 的值不可能是( )
A.2 B.3 C.4 D.5
13.某二分查找算法的程序段如下：
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
14.已知一无序数组a，通过引入数组b，使得a[b[0]]≤a[b[1]]≤a[b[2]]……≤a[b[n－1]](示例如下图所示)，对这些有序数据可进行对分查找。则第一次查找时，中点位置m与中点值分别是( )
A.m的值是(n－1)∥2，中点值是a[m]
B.m的值是(n－1)∥2，中点值是a[b[m]]
C.m的值是(b[0]＋b[n－1])∥2，中点值是a[m]
D.m的值是(b[0]＋b[n－1])∥2，中点值是a[b[m]]
15.生成并输出二分查找树。在有序序列中查找某个数据，常使用二分查找算法。当待寻找的数据为随机值时，需要使用二分查找树列举所有可能情况。所谓二分查找树，是指按照二分查找的顺序，按层次输出以各中点元素为节点的二叉树。例如，当递增数组a＝[1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16]时，其对应的二分查找树如图所示。
下列代码能够生成并输出二分查找树，请回答下列问题：
(1)当有序数组a＝[2，23，40，45，60，65，68，83，86，95]时，对应的二分查找树中第3行第3个数为________。
(2)请在划线处填入合适的代码。
def create_bs(a)： #生成并输出二分查找树
max_cnt＝0
n＝len(a)
pos＝[0]*n #pos[i]表示元素a[i]查找的次数
for p in range(n)：
L，R＝0，n－1
cnt＝0
while L<＝R：
m＝①________
cnt＋＝1
if cnt>max_cnt：
max_cnt＝cnt
if m＝＝p：
pos[m]＝②________
break
elif m L＝m＋1
else：
R＝③________
for i in range(1，max_cnt＋1)：
s＝″″
for j in range(n)：
if pos[j]＝＝i： #找到节点a[j]
s＝s＋str(a[j])
else：
s＝s＋″ ″
print(s)
a＝list(range(1，17))
print(″有序数组：″，a)
print(″二分查找树：″)
create_bs(a)
16.小明学了排序和查找算法后，编写了一个处理成绩的程序，功能如下：程序运行时，首先从Excel文件中读取n个学生的技术成绩存储在列表b中，并对列表中的数据按升序进行排序；输入成绩 key，统计并输出共有多少位同学的成绩大于该成绩。
实现上述功能的Python程序如下，请在程序划线处填入合适的代码。
#从Excel文件中读取n个学生的技术成绩存储在列表b中，代码略
n＝len(b)
#对列表b中的元素进行升序排序
for i in range(1，n)：
tmp＝b[i]
j＝0
while ①________________：
j＝j＋1
if j！＝i：
for k in range(i，j，－1)：
b[k]＝b[k－1]
②________________
print(b)
key＝int(input(″please input key：″))
i，j＝0，n－1
while i<＝j：
m＝(i＋j)∥2
if keyj＝m－1
else：
i＝m＋1
print(″共有″＋③________________＋″位同学大于等于该成绩。″)
课时5 二分查找
1.C [本题主要考查的是顺序查找和二分查找算法思想。使用二分查找算法查找数据35，需要的查找次数为4次，因此C选项不正确，答案为C。]
2.C [本题主要考查的是二分查找的算法思想。使用二分查找算法查找数据126的过程中，首先被访问到的元素为112，第二次被访问到的元素为120，第三次被访问到的元素为126，因此，答案为C。]
3.D [本题主要考查的是二分查找的程序实现。使用二分查找算法查找数据12的过程中，第一次访问的是索引号为3的元素9，第二次访问的是索引号为5的元素15，第三次访问的是索引号为4的元素12，查找结束，因此，答案为D。]
4.B [本题主要考查的是二分查找的变式。本题的功能是在列表list1中查找第1个大于key的元素。c表示共查找的次数，共查找了3次，因此A选项错误；查找结束时，left＝3，right＝2，因此CD选项错误；查找结束时，因为left＝3，因此程序输出的结果为Lettuce，答案为B。]
5.C [本题主要考查的是二分查找的过程。数组f中元素为1，表示查找过数组a对应位置上元素，f中元素为0，表示数组a对应位置上元素没有查找过；选项C查找的路径不符合二分查找算法的过程，答案为C。]
6.D [由C始终等于4得，查找次数必定为4次，该对分查找并没有找到即break结束循环的语句，所以可以把该对分查找程序看作不断排除的过程，即i＞j表示排除完所有的数据节点，则程序结束，即对应的二叉排序树根据条件遍历到叶子节点为止。根据随机函数产生的key最小为20，若x为19，key＝20，则C等于3，排除A；若y是26，key＝24，则C为3，排除B；若y是25，key＝24，则C为3，排除C。 ]
7.D [本题考查二分查找。列表长度就是二分查找的查找次数。列表共 8 个元素，最少 1 次，最多 4 次。查找到 76 时，不可能继续往右查找，所以 4 次是不可能的。]
8.C [本题考查二分查找。程序的功能是数组a的i索引前找一个数，满足a[i]*a[m]＝＝n的个数，因此分别是9*4、12*3、18*2。]
9.D [本题考查二分算法以及二分判定树。根据本题代码m＝(i＋j＋1)∥2，画出二分判定树，位于二分判定树第4层的节点下标分别是1、4、7、9、12、14、17、19。所以key的值不可能是a[16]。]
10.B [考查二分查收算法思想。Key是[40，70]区间的偶数，n是循环次数。画出相应的二叉树。最多查找3次；a[1]为37，查找的位置不可能是1。若查找2次，说明查找的数是50，中间退出循环，满足条件i<＝j。]
11.B [本题考查二分查找、自定义函数的综合应用。由“key＝random.choice(a)”可知查找键 key 是一定可以找得到的，由题中算法可知，找到最少找 1 次，最多找 int(log2n)＋1 次，本题中序列 a 中共有 8 个成员，则最多找 4 次。]
12.B [本题考查索引排序和二分查找算法。key 值在 30－60，在列表 a 中只有 40、 59、32 符合范围，对应的索引值为2，4，5。]
13.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个。]
14.B [本题主要考查的是对分查找算法。常见的错误思想为：根据a[b[0]]≤a[b[1]]…≤a[b[n－1]]可知数据是有序，因而想当然地认为：m的值为((b[0]＋b[n－1]∥2)，中点值是a[m]。其实，中间数据为a[b[(0＋n－1)∥2]]，例如 a[b[0]]≤a[b[1]]≤a[b[2]]，中点值为a[b[(0＋2)∥2))即a[b[1]]。因此，答案为B。]
15.(1)65 (2)①(L＋R)∥2 ②cnt ③m－1
解析 (1)按照题意画出二分查找树，可知第3行第3个数为65；(2)中点m表示式左偏，即m＝(L＋R)∥2；程序遍历数组a，计算当a[p]作为中点元素时，需要查找的次数，存储到数组pos中，即pos[p]表示元素a[p]查找的次数，则pos[m]＝cnt；按照二分查找算法思想，第③空为m－1。
16.①jb[j]或jb[j]
②b[k－1]＝tmp或b[j]＝tmp ③str(n－i)
解析 本题主要考查的是排序算法和二分查找算法。本题采用插入排序的方法对列表中的元素进行升序排序，划线①处while循环的功能是查找当前元素b[i]在前i－1个数中的插入位置，因为是升序排序，因此①处代码为jb[j]；
②处代码的功能是将当前元素(bmp)存储在插入位置(k－1)，因此②处代码为b[k－1]＝tmp；然后使用二分查找算法在列表b中查找大于key的第一个元素的位置，因为数据是升序排序，因此大于key的元素个数为n－i，由于print命令中使用“＋”运算符，因此需将“n－i”转换为字符类型，即划线③处代码为str(n－i)。
展开更多......
收起↑
