资源简介

课时4　顺序查找
课时目标
1.通过实例分析，理解顺序查找的基本思想，掌握使用顺序查找的一般方法。
2.能根据不同的应用场景，选择合适的数据结构，能灵活使用顺序查找算法编写程序。
1.查找(Search)
查找也称检索，计算机根据所给条件查找出____________的对象，即在存储的一批数据中寻找出一个________的数据，或者确定在该批数据内是否________这样的数据。
常见的查找算法主要有：____________和____________(也称对分查找)
2.顺序查找(Sequential Search)
顺序查找又称线性查找，是指从顺序表的一端开始，__________________将每个元素的关键字与给定值key(查找键)进行比较。若某个元素的__________________，则表明查找成功；若所有元素都比较完毕仍找不到，则表明查找失败。
3.顺序查找算法基本框架
假设：要查找的数据为key，n个待查找的数存放在数组d中。
for循环条件：
find＝False
for i in range(0，n)：
if d[i]＝＝key：　#则表示找到，
　　　　#修改find的值为True，并做相应处理
　　 if find＝＝False：
#表示未找到
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
While循环实现：
i＝0
while i<＝n－1：
if d[i]＝＝key：　#则表示找到，
　　　#修改find的值为True，并做相应处理
i＝i＋1
if i＝＝n：
　　　#表示未找到
4.顺序查找算法程序实现
假设：要查找的数据为key，n个待查找的数存放在数组d中，本程序找到满足条件的第一个数据就结束。
for循环条件：
find＝False
for i in range(n)：
　　 if key＝＝d[i]：
　 　　　find＝True
　　 　　print(″find，索引号为：″，i)
　　　 　break
if not find：
　　　 print(″未找到″)
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
while循环条件：
i＝0
while i<＝n－1：
if key＝＝d[i]：
　　　print(″find，索引号为：″，i)
　　　break
else：
　　　i＝i＋1
if i＝＝n：
print(″未找到″)
(1)使用for循环查找时，需要设置一个逻辑变量，表示找到与否。
(2)while顺序查找还可以写为：
i＝0
find＝False
while i<＝n－1 and not flag：
if key＝＝d[i]：
print(″find，索引号为：″，i)
find＝True
else：
i＝i＋1
if i＝＝n：
print(″未找到″)
例1 在数组a中存储的数据依次为“3，6，5，11，15，20，13，32”。现使用顺序查找算法在数组a中查找数据20，共需查找的次数为(　　)
A.5次 B.6次 C.7次 D.8次
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　在数组a中存储的数据依次为“3，6，5，11，15，20，13，32”。现使用顺序查找算法在数组a中查找数据8，共需查找的次数为(　　)
A.0次 B.8次 C.9次 D.无穷次
例2 有如下Python程序段：
d＝[3，9，1，2，6，9，0]
n＝len(d)
key＝int(input(″please input key：″))
flag＝True
i＝0
while i<＝n－1 and flag：
if key＝＝d[i]：
pos＝i
flag＝False
else：
i＝i＋1
if i＝＝n：
print(″未找到″)
else：
print(″找到，索引位置：″，pos)
程序运行时，输入key的值为9，输出结果为(　　)
A.未找到
B.找到，索引位置： 1
C.找到，索引位置： 5
D.找到，索引位置： 1　5
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　有如下Python程序段：
d＝[3，9，1，9，6，8，9]
n＝len(d)
key＝int(input(″please input key：″))
i＝0
c＝0
flag＝True
s＝″″
while i<＝n－1：
if key＝＝d[i]：
flag＝False
s＝s＋str(i)＋″，″
i＝i＋1
if flag：
print(″未找到″)
else：
print(″找到，索引位置为：″，s[0：len(s)－1])
程序运行时，输入key的值为9，程序运行后，变量i的值为(　　)
A.未找到
B.找到，索引位置为： 1
C.找到，索引位置为： 1，3
D.找到，索引位置为： 1，3，6
例3 有如下Python程序段：
d＝[13，19，21，29，36，18，32，20，55，6，8]
n＝len(d)
key＝int(input(″please input key：″))
pos＝[]
i＝c＝0
while i<＝n－1：
if d[i]>key：
pos.append(d[i])
c＝c＋1
i＝i＋1
if c>0：
print(pos)
else：
print(″没有找到″)
程序执行时，输入key的值为20，程序执行后，变量c和i的值分别为(　　)
A.c为6，i为11 B.c为6，i为10
C.c为5，i为11 D.c为5，i为10
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　有如下Python程序段：
d＝[13，9，21，29，36，18，23，20，25，6，8]
n＝len(d)
key＝int(input(″please input key：″))
ans＝max(d)
posi＝i＝0
while i<＝n－1：
if abs(d[i]－key)<＝ans：
ans＝abs(d[i]－key)
posi＝i
i＝i＋1
print(ans，″，″，posi)
程序运行时，输入key的值为22，输出结果为(　　)
A.1　2 B.1　6 C.1，2 D.1，6
1.在数组d中存储的数据依次为“15，23，25，12，8，5，29，30，88，100”。现使用顺序查找算法在数组d中查找数据88，共需查找的次数为(　　)
A.7次 B.8次 C.9次 D.10次
2.在数组d中存储的数据依次为″if″，″for″，″range″，″while″，″def″，″True″，″False″，″print″，″input″。现使用顺序查找算法在数组d中查找数据″false″，共需查找的次数为(　　)
A.0次 B.7次 C.9次 D.10次
3.有如下Python程序段：
d＝[″len″，″str″，″abs″，″chr″，″min″，″ord″，″int″，″max″]
n＝len(d)
key＝input(″please input key：″)
i＝0
s＝″″
while i<＝n－1：
if d[i]>key：
s＝s＋str(i)
i＝i＋1
print(s)
程序运行时，输入float，输出结果为(　　)
A.12567 B.125678
C.014567 D.0145678
4.有如下VB程序段：
d＝[″len″，″str″，″chr″，″abs″，″min″，″Some″，″ install″，″max″]
n＝len(d)
b＝[]
key＝input(″please input key：″)
i＝0
while i<＝n－1：
if key in d[i]：
b.append(d[i])
i＝i＋1
print(b)
程序运行时，输入s，输出结果为(　　)
A.'str'，'abs'，'install'
B.'str'，'abs'，'Some'，'install'
C.['str'，'abs'，'Some'，'install']
D.['str'，'abs'，'install']
课时4　顺序查找
知识梳理
1.满足条件　特定　存在　顺序查找　二分查找
2.依次　关键字等于key
例题精析
例1　B　[本题主要考查的是顺序查找的算法思想。20位于数组d中第6个位置(索引号为5)，因此共查找6次，答案为B。]
变式训练　B　[本题主要考查的是顺序查找算法的算法思想。数组a中没有数据8，因此需要全部查找一遍才结束。故共查找8次，答案为B。]
例2　B　[本题主要考查的是顺序查找的程序实现。本程序的功能是只找到第一个满足条件的值就结束查找，即找到第1个9时(索引位置为1)就结束查找，因此，答案为B。]
变式训练　D　[本题主要考查的是顺序查找的程序实现。本程序的功能是找到所有满足条件的值，即找到3个9，索引位置分别为1、3、6，因此，答案为D。]
例3　C　[本题主要考查的是顺序查找算法的程序实现。本题程序的功能是在列表d中查找大于key的元素，并将大于key的元素添加在列表pos中，同时进行计数，计数结果存放在变量c中，循环结束时，i的值为11，c为5。因此，答案为C。]
变式训练　D　[本题主要考查的是顺序查找算法的程序实现。本程序的功能是在列表d中查找与key的差值最小的元素，根据程序中的代码if abs(d[i]－key)<＝ans：可知，若有多个元素的值与key的差值相等，则记录的是最后一个满足条件的元素的索引位置。因此，答案为D。]
随堂检测
1.C　[本题主要考查的是顺序查找算法的算法思想。88是数组d中第9个数据，因此，共查找9次，答案为C。]
2.C　[本题主要考查的是顺序查找算法的算法思想。数组d中没有数据″false″，因此，共查找次数为d数组中数据的总数，即查找9次，答案为C。]
3.C　[本题主要考查的是顺序查找的程序实现。本题程序的功能是在列表d中查找大于key的元素，并记录其在列表中的索引位置，字符串的比较是比较其ASCII码，列表中的元素″len″、″str″、″min″、″ord″、″int″、″max″大于key(″max″)，这些元素在列表中的索引位置分别为0、1、4、5、6、7，因此答案为C。]
4.D　[本题主要考查的是顺序查找的程序实现。本题程序的功能是在列表d中查找包含字符s的元素，并将这些元素记录在列表b中，需注意的是字符串的字母是区分大小写的，输出结果是列表中的内容，因此答案为D。](共57张PPT)
课时4　顺序查找
第五章　数据结构与算法
1.通过实例分析，理解顺序查找的基本思想，掌握使用顺序查找的一般方法。
2.能根据不同的应用场景，选择合适的数据结构，能灵活使用顺序查找算法编写程序。
目 录
CONTENTS
知识梳理
01
例题精析
02
随堂检测
03
巩固与提升
04
知识梳理
1
1.查找(Search)
查找也称检索，计算机根据所给条件查找出____________的对象，即在存储的一批数据中寻找出一个______的数据，或者确定在该批数据内是否______这样的数据。
常见的查找算法主要有：____________和____________(也称对分查找)
满足条件
特定
存在
顺序查找　
二分查找
2.顺序查找(Sequential Search)
顺序查找又称线性查找，是指从顺序表的一端开始，______将每个元素的关键字与给定值key(查找键)进行比较。若某个元素的________________________，则表明查找成功；若所有元素都比较完毕仍找不到，则表明查找失败。
依次
关键字等于key
3.顺序查找算法基本框架
假设：要查找的数据为key，n个待查找的数存放在数组d中。
for循环条件：
find＝False
for i in range(0，n)：
if d[i]＝＝key：　#则表示找到，
　　　　#修改find的值为True，并做相应处理
　　 if find＝＝False：
#表示未找到
4.顺序查找算法程序实现
假设：要查找的数据为key，n个待查找的数存放在数组d中，本程序找到满足条件的第一个数据就结束。
for循环条件：
find＝False
for i in range(n)：
　　 if key＝＝d[i]：
　 　　　find＝True
　　 　　print(″find，索引号为：″，i)
　　　 　break
if not find：
　　　 print(″未找到″)
(1)使用for循环查找时，需要设置一个逻辑变量，表示找到与否。
(2)while顺序查找还可以写为：
i＝0
find＝False
while i<＝n－1 and not flag：
if key＝＝d[i]：
print(″find，索引号为：″，i)
find＝True
else：
i＝i＋1
if i＝＝n：
print(″未找到″)
例题精析
2
例1 在数组a中存储的数据依次为“3，6，5，11，15，20，13，32”。现使用顺序查找算法在数组a中查找数据20，共需查找的次数为(　　)
B
解析　本题主要考查的是顺序查找的算法思想。20位于数组d中第6个位置(索引号为5)，因此共查找6次，答案为B。
A.5次 B.6次 C.7次 D.8次
变式训练　在数组a中存储的数据依次为“3，6，5，11，15，20，13，32”。现使用顺序查找算法在数组a中查找数据8，共需查找的次数为(　　)
A.0次 B.8次 C.9次 D.无穷次
解析　本题主要考查的是顺序查找算法的算法思想。数组a中没有数据8，因此需要全部查找一遍才结束。故共查找8次，答案为B。
B
例2 有如下Python程序段：
d＝[3，9，1，2，6，9，0]
n＝len(d)
key＝int(input(″please input key：″))
flag＝True
i＝0
while i<＝n－1 and flag：
if key＝＝d[i]：
pos＝i
flag＝False
else：
i＝i＋1
if i＝＝n：
print(″未找到″)
else：
print(″找到，索引位置：″，pos)
程序运行时，输入key的值为9，输出结果为(　　)
A.未找到 B.找到，索引位置： 1
C.找到，索引位置： 5 D.找到，索引位置： 1　5
解析　本题主要考查的是顺序查找的程序实现。本程序的功能是只找到第一个满足条件的值就结束查找，即找到第1个9时(索引位置为1)就结束查找，因此，答案为B。
B
变式训练　有如下Python程序段：
d＝[3，9，1，9，6，8，9]
n＝len(d)
key＝int(input(″please input key：″))
i＝0
c＝0
flag＝True
s＝″″
while i<＝n－1：
if key＝＝d[i]：
flag＝False
s＝s＋str(i)＋″，″
i＝i＋1
if flag：
print(″未找到″)
else：
print(″找到，索引位置为：″，s[0：len(s)－1])
程序运行时，输入key的值为9，程序运行后，变量i的值为(　　)
A.未找到 B.找到，索引位置为： 1
C.找到，索引位置为： 1，3 D.找到，索引位置为： 1，3，6
解析　本题主要考查的是顺序查找的程序实现。本程序的功能是找到所有满足条件的值，即找到3个9，索引位置分别为1、3、6，因此，答案为D。
D
例3 有如下Python程序段：
d＝[13，19，21，29，36，18，32，20，55，6，8]
n＝len(d)
key＝int(input(″please input key：″))
pos＝[]
i＝c＝0
while i<＝n－1：
if d[i]>key：
pos.append(d[i])
c＝c＋1
i＝i＋1
if c>0：
print(pos)
else：
print(″没有找到″)
程序执行时，输入key的值为20，程序执行后，变量c和i的值分别为(　　)
A.c为6，i为11 B.c为6，i为10
C.c为5，i为11 D.c为5，i为10
解析　本题主要考查的是顺序查找算法的程序实现。本题程序的功能是在列表d中查找大于key的元素，并将大于key的元素添加在列表pos中，同时进行计数，计数结果存放在变量c中，循环结束时，i的值为11，c为5。因此，答案为C。
C
变式训练　有如下Python程序段：
d＝[13，9，21，29，36，18，23，20，25，6，8]
n＝len(d)
key＝int(input(″please input key：″))
ans＝max(d)
posi＝i＝0
while i<＝n－1：
if abs(d[i]－key)<＝ans：
ans＝abs(d[i]－key)
posi＝i
i＝i＋1
print(ans，″，″，posi)
程序运行时，输入key的值为22，输出结果为(　　)
A.1　2 B.1　6 C.1，2 D.1，6
解析　本题主要考查的是顺序查找算法的程序实现。本程序的功能是在列表d中查找与key的差值最小的元素，根据程序中的代码if abs(d[i]－key)<＝ans：可知，若有多个元素的值与key的差值相等，则记录的是最后一个满足条件的元素的索引位置。因此，答案为D。
D
随堂检测
3
1.在数组d中存储的数据依次为“15，23，25，12，8，5，29，30，88，100”。现使用顺序查找算法在数组d中查找数据88，共需查找的次数为(　　)
A.7次 B.8次 C.9次 D.10次
C
解析　本题主要考查的是顺序查找算法的算法思想。88是数组d中第9个数据，因此，共查找9次，答案为C。
2.在数组d中存储的数据依次为″if″，″for″，″range″，″while″，″def″，″True″，
″False″，″print″，″input″。现使用顺序查找算法在数组d中查找数据″false″，共需查找的次数为(　　)
A.0次 B.7次 C.9次 D.10次
C
解析　本题主要考查的是顺序查找算法的算法思想。数组d中没有数据″false″，因此，共查找次数为d数组中数据的总数，即查找9次，答案为C。
3.有如下Python程序段：
d＝[″len″，″str″，″abs″，″chr″，″min″，″ord″，″int″，″max″]
n＝len(d)
key＝input(″please input key：″)
i＝0
s＝″″
while i<＝n－1：
if d[i]>key：
s＝s＋str(i)
i＝i＋1
print(s)
C
程序运行时，输入float，输出结果为(　　)
A.12567 B.125678
C.014567 D.0145678
解析　本题主要考查的是顺序查找的程序实现。本题程序的功能是在列表d中查找大于key的元素，并记录其在列表中的索引位置，字符串的比较是比较其ASCII码，列表中的元素″len″、″str″、″min″、″ord″、″int″、″max″大于key(″max″)，这些元素在列表中的索引位置分别为0、1、4、5、6、7，因此答案为C。
4.有如下VB程序段：
d＝[″len″，″str″，″chr″，″abs″，″min″，″Some″，″ install″，″max″]
n＝len(d)
b＝[]
key＝input(″please input key：″)
i＝0
while i<＝n－1：
if key in d[i]：
b.append(d[i])
i＝i＋1
print(b)
D
程序运行时，输入s，输出结果为(　　)
A.'str'，'abs'，'install‘ B.'str'，'abs'，'Some'，'install'
C.['str'，'abs'，'Some'，'install'] D.['str'，'abs'，'install']
解析　本题主要考查的是顺序查找的程序实现。本题程序的功能是在列表d中查找包含字符s的元素，并将这些元素记录在列表b中，需注意的是字符串的字母是区分大小写的，输出结果是列表中的内容，因此答案为D。
4
巩固与提升
基础巩固
能力提升
1.在数组d中存储的数据依次为“17，11，36，48，19，22，39，56，17，100”。现使用顺序查找算法在数组d中查找数据17，共需查找的次数为(　　)
A.0次 B.1次 C.9次 D.10次
B
解析　本题主要考查的是顺序算法。数组d中有2个17，顺序查找默认只找到第一个满足条件的数据就结束查找，因此找到第1个17后就结束查找，即查找1次，答案为B。
2.在数组d中存储的数据依次为“10，22，16，80，19，35，41，88，66，71”。现使用顺序查找算法在数组d中查找数据99，共需查找的次数为(　　)
A.0次 B.10次 C.11次 D.无穷次
B
解析　本题主要考查的是顺序算法。数组d中没有数据99，因此需要全部查找一遍才结束。故共查找10次，答案为B。
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)
D
程序执行时，输入key的值为t，则输出的内容为(　　)
A.t 3 B.tttt 3 C.t 4 D.tttt 4
解析　本题主要考查的是顺序算法的程序实现。本题程序的功能是在字符串a中查找key的值，若找到，则将key的值拼接在字符串s中，并统计个数，因此输出结果为tttt 4，答案为D。
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！″)
B
程序执行时，输入key的值为45，则输出的内容为(　　)
A.Not found! B.Find！pos＝1
C.Find！pos＝5 D.Find！pos＝9
解析　本题主要考查的是顺序算法的程序实现。本题程序的功能是在列表b中查找key的值，若找不到，则输出“Not found！”；如果找到且有多个时，记录的是最后一个与key相等的元素的索引位置，需注意的是，本题是从列表最后一个元素往前进行查找，因此输入key为45时，找到最后一个45在列表b中的位置为1，故答案为B。
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]：
D
if maxlen　　　　maxlen＝len(wordlist[i])
　　　　pos＝i
i＝i＋1
if pos！＝－1：
print(wordlist[pos])
else：
print(″Fail！″)
解析　本题主要考查的是顺序查找算法的程序实现。本程序的功能是在列表wordlist中查找包含some的单词中长度为最长的单词，因此，答案为D。
程序执行时，输入字符内容为“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])
解析　本题主要考查的是顺序查找算法的综合应用。每本书包含三个信息：书名、作者和价格，即最后一本书的书名book[n－3]，因此①处代码为i<＝n－3；本题中查找是书名中包含的关键字的书，因此可用in运算实现，即②处代码keyword in book[i]；当找到当前价格最高的书时，修改maxprice的值，还要记录当前的书在列表中的索引位置，因此，③处代码为posi＝i。
答案　①i<＝n－3　②keyword in book[i] ③posi＝i
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)请在划线处填入适当的代码。
答案　(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.利用某火车购票系统购票，购买者输入“出发站”、“目的站”，系统会统计两站之间的占座情况，根据空座数量(出发站至目的站之前一直是空的座位即为空座)返回余票情况，购买者根据余票信息购买车票，获得具体座位号。
根据上述功能，小王编写了一个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]
答案　(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))，应该是当前项与前一项比较。

展开更多......

收起↑