資源簡介

課時4　順序查找
課時目標(biāo)
1.通過實例分析，理解順序查找的基本思想，掌握使用順序查找的一般方法。
2.能根據(jù)不同的應(yīng)用場景，選擇合適的數(shù)據(jù)結(jié)構(gòu)，能靈活使用順序查找算法編寫程序。
1.查找(Search)
查找也稱檢索，計算機根據(jù)所給條件查找出____________的對象，即在存儲的一批數(shù)據(jù)中尋找出一個________的數(shù)據(jù)，或者確定在該批數(shù)據(jù)內(nèi)是否________這樣的數(shù)據(jù)。
常見的查找算法主要有：____________和____________(也稱對分查找)
2.順序查找(Sequential Search)
順序查找又稱線性查找，是指從順序表的一端開始，__________________將每個元素的關(guān)鍵字與給定值key(查找鍵)進(jìn)行比較。若某個元素的__________________，則表明查找成功；若所有元素都比較完畢仍找不到，則表明查找失敗。
3.順序查找算法基本框架
假設(shè)：要查找的數(shù)據(jù)為key，n個待查找的數(shù)存放在數(shù)組d中。
for循環(huán)條件：
find＝False
for i in range(0，n)：
if d[i]＝＝key：　#則表示找到，
　　　　#修改find的值為True，并做相應(yīng)處理
　　 if find＝＝False：
#表示未找到
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
While循環(huán)實現(xiàn)：
i＝0
while i<＝n－1：
if d[i]＝＝key：　#則表示找到，
　　　#修改find的值為True，并做相應(yīng)處理
i＝i＋1
if i＝＝n：
　　　#表示未找到
4.順序查找算法程序?qū)崿F(xiàn)
假設(shè)：要查找的數(shù)據(jù)為key，n個待查找的數(shù)存放在數(shù)組d中，本程序找到滿足條件的第一個數(shù)據(jù)就結(jié)束。
for循環(huán)條件：
find＝False
for i in range(n)：
　　 if key＝＝d[i]：
　 　　　find＝True
　　 　　print(″find，索引號為：″，i)
　　　 　break
if not find：
　　　 print(″未找到″)
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
while循環(huán)條件：
i＝0
while i<＝n－1：
if key＝＝d[i]：
　　　print(″find，索引號為：″，i)
　　　break
else：
　　　i＝i＋1
if i＝＝n：
print(″未找到″)
(1)使用for循環(huán)查找時，需要設(shè)置一個邏輯變量，表示找到與否。
(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 在數(shù)組a中存儲的數(shù)據(jù)依次為“3，6，5，11，15，20，13，32”。現(xiàn)使用順序查找算法在數(shù)組a中查找數(shù)據(jù)20，共需查找的次數(shù)為(　　)
A.5次 B.6次 C.7次 D.8次
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓(xùn)練　在數(shù)組a中存儲的數(shù)據(jù)依次為“3，6，5，11，15，20，13，32”。現(xiàn)使用順序查找算法在數(shù)組a中查找數(shù)據(jù)8，共需查找的次數(shù)為(　　)
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，輸出結(jié)果為(　　)
A.未找到
B.找到，索引位置： 1
C.找到，索引位置： 5
D.找到，索引位置： 1　5
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓(xùn)練　有如下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(″沒有找到″)
程序執(zhí)行時，輸入key的值為20，程序執(zhí)行后，變量c和i的值分別為(　　)
A.c為6，i為11 B.c為6，i為10
C.c為5，i為11 D.c為5，i為10
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓(xùn)練　有如下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，輸出結(jié)果為(　　)
A.1　2 B.1　6 C.1，2 D.1，6
1.在數(shù)組d中存儲的數(shù)據(jù)依次為“15，23，25，12，8，5，29，30，88，100”。現(xiàn)使用順序查找算法在數(shù)組d中查找數(shù)據(jù)88，共需查找的次數(shù)為(　　)
A.7次 B.8次 C.9次 D.10次
2.在數(shù)組d中存儲的數(shù)據(jù)依次為″if″，″for″，″range″，″while″，″def″，″True″，″False″，″print″，″input″。現(xiàn)使用順序查找算法在數(shù)組d中查找數(shù)據(jù)″false″，共需查找的次數(shù)為(　　)
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，輸出結(jié)果為(　　)
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，輸出結(jié)果為(　　)
A.'str'，'abs'，'install'
B.'str'，'abs'，'Some'，'install'
C.['str'，'abs'，'Some'，'install']
D.['str'，'abs'，'install']
課時4　順序查找
知識梳理
1.滿足條件　特定　存在　順序查找　二分查找
2.依次　關(guān)鍵字等于key
例題精析
例1　B　[本題主要考查的是順序查找的算法思想。20位于數(shù)組d中第6個位置(索引號為5)，因此共查找6次，答案為B。]
變式訓(xùn)練　B　[本題主要考查的是順序查找算法的算法思想。數(shù)組a中沒有數(shù)據(jù)8，因此需要全部查找一遍才結(jié)束。故共查找8次，答案為B。]
例2　B　[本題主要考查的是順序查找的程序?qū)崿F(xiàn)。本程序的功能是只找到第一個滿足條件的值就結(jié)束查找，即找到第1個9時(索引位置為1)就結(jié)束查找，因此，答案為B。]
變式訓(xùn)練　D　[本題主要考查的是順序查找的程序?qū)崿F(xiàn)。本程序的功能是找到所有滿足條件的值，即找到3個9，索引位置分別為1、3、6，因此，答案為D。]
例3　C　[本題主要考查的是順序查找算法的程序?qū)崿F(xiàn)。本題程序的功能是在列表d中查找大于key的元素，并將大于key的元素添加在列表pos中，同時進(jìn)行計數(shù)，計數(shù)結(jié)果存放在變量c中，循環(huán)結(jié)束時，i的值為11，c為5。因此，答案為C。]
變式訓(xùn)練　D　[本題主要考查的是順序查找算法的程序?qū)崿F(xiàn)。本程序的功能是在列表d中查找與key的差值最小的元素，根據(jù)程序中的代碼if abs(d[i]－key)<＝ans：可知，若有多個元素的值與key的差值相等，則記錄的是最后一個滿足條件的元素的索引位置。因此，答案為D。]
隨堂檢測
1.C　[本題主要考查的是順序查找算法的算法思想。88是數(shù)組d中第9個數(shù)據(jù)，因此，共查找9次，答案為C。]
2.C　[本題主要考查的是順序查找算法的算法思想。數(shù)組d中沒有數(shù)據(jù)″false″，因此，共查找次數(shù)為d數(shù)組中數(shù)據(jù)的總數(shù)，即查找9次，答案為C。]
3.C　[本題主要考查的是順序查找的程序?qū)崿F(xiàn)。本題程序的功能是在列表d中查找大于key的元素，并記錄其在列表中的索引位置，字符串的比較是比較其ASCII碼，列表中的元素″len″、″str″、″min″、″ord″、″int″、″max″大于key(″max″)，這些元素在列表中的索引位置分別為0、1、4、5、6、7，因此答案為C。]
4.D　[本題主要考查的是順序查找的程序?qū)崿F(xiàn)。本題程序的功能是在列表d中查找包含字符s的元素，并將這些元素記錄在列表b中，需注意的是字符串的字母是區(qū)分大小寫的，輸出結(jié)果是列表中的內(nèi)容，因此答案為D。](共57張PPT)
課時4　順序查找
第五章　數(shù)據(jù)結(jié)構(gòu)與算法
1.通過實例分析，理解順序查找的基本思想，掌握使用順序查找的一般方法。
2.能根據(jù)不同的應(yīng)用場景，選擇合適的數(shù)據(jù)結(jié)構(gòu)，能靈活使用順序查找算法編寫程序。
目 錄
CONTENTS
知識梳理
01
例題精析
02
隨堂檢測
03
鞏固與提升
04
知識梳理
1
1.查找(Search)
查找也稱檢索，計算機根據(jù)所給條件查找出____________的對象，即在存儲的一批數(shù)據(jù)中尋找出一個______的數(shù)據(jù)，或者確定在該批數(shù)據(jù)內(nèi)是否______這樣的數(shù)據(jù)。
常見的查找算法主要有：____________和____________(也稱對分查找)
滿足條件
特定
存在
順序查找　
二分查找
2.順序查找(Sequential Search)
順序查找又稱線性查找，是指從順序表的一端開始，______將每個元素的關(guān)鍵字與給定值key(查找鍵)進(jìn)行比較。若某個元素的________________________，則表明查找成功；若所有元素都比較完畢仍找不到，則表明查找失敗。
依次
關(guān)鍵字等于key
3.順序查找算法基本框架
假設(shè)：要查找的數(shù)據(jù)為key，n個待查找的數(shù)存放在數(shù)組d中。
for循環(huán)條件：
find＝False
for i in range(0，n)：
if d[i]＝＝key：　#則表示找到，
　　　　#修改find的值為True，并做相應(yīng)處理
　　 if find＝＝False：
#表示未找到
4.順序查找算法程序?qū)崿F(xiàn)
假設(shè)：要查找的數(shù)據(jù)為key，n個待查找的數(shù)存放在數(shù)組d中，本程序找到滿足條件的第一個數(shù)據(jù)就結(jié)束。
for循環(huán)條件：
find＝False
for i in range(n)：
　　 if key＝＝d[i]：
　 　　　find＝True
　　 　　print(″find，索引號為：″，i)
　　　 　break
if not find：
　　　 print(″未找到″)
(1)使用for循環(huán)查找時，需要設(shè)置一個邏輯變量，表示找到與否。
(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 在數(shù)組a中存儲的數(shù)據(jù)依次為“3，6，5，11，15，20，13，32”。現(xiàn)使用順序查找算法在數(shù)組a中查找數(shù)據(jù)20，共需查找的次數(shù)為(　　)
B
解析　本題主要考查的是順序查找的算法思想。20位于數(shù)組d中第6個位置(索引號為5)，因此共查找6次，答案為B。
A.5次 B.6次 C.7次 D.8次
變式訓(xùn)練　在數(shù)組a中存儲的數(shù)據(jù)依次為“3，6，5，11，15，20，13，32”。現(xiàn)使用順序查找算法在數(shù)組a中查找數(shù)據(jù)8，共需查找的次數(shù)為(　　)
A.0次 B.8次 C.9次 D.無窮次
解析　本題主要考查的是順序查找算法的算法思想。數(shù)組a中沒有數(shù)據(jù)8，因此需要全部查找一遍才結(jié)束。故共查找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，輸出結(jié)果為(　　)
A.未找到 B.找到，索引位置： 1
C.找到，索引位置： 5 D.找到，索引位置： 1　5
解析　本題主要考查的是順序查找的程序?qū)崿F(xiàn)。本程序的功能是只找到第一個滿足條件的值就結(jié)束查找，即找到第1個9時(索引位置為1)就結(jié)束查找，因此，答案為B。
B
變式訓(xùn)練　有如下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
解析　本題主要考查的是順序查找的程序?qū)崿F(xiàn)。本程序的功能是找到所有滿足條件的值，即找到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(″沒有找到″)
程序執(zhí)行時，輸入key的值為20，程序執(zhí)行后，變量c和i的值分別為(　　)
A.c為6，i為11 B.c為6，i為10
C.c為5，i為11 D.c為5，i為10
解析　本題主要考查的是順序查找算法的程序?qū)崿F(xiàn)。本題程序的功能是在列表d中查找大于key的元素，并將大于key的元素添加在列表pos中，同時進(jìn)行計數(shù)，計數(shù)結(jié)果存放在變量c中，循環(huán)結(jié)束時，i的值為11，c為5。因此，答案為C。
C
變式訓(xùn)練　有如下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，輸出結(jié)果為(　　)
A.1　2 B.1　6 C.1，2 D.1，6
解析　本題主要考查的是順序查找算法的程序?qū)崿F(xiàn)。本程序的功能是在列表d中查找與key的差值最小的元素，根據(jù)程序中的代碼if abs(d[i]－key)<＝ans：可知，若有多個元素的值與key的差值相等，則記錄的是最后一個滿足條件的元素的索引位置。因此，答案為D。
D
隨堂檢測
3
1.在數(shù)組d中存儲的數(shù)據(jù)依次為“15，23，25，12，8，5，29，30，88，100”。現(xiàn)使用順序查找算法在數(shù)組d中查找數(shù)據(jù)88，共需查找的次數(shù)為(　　)
A.7次 B.8次 C.9次 D.10次
C
解析　本題主要考查的是順序查找算法的算法思想。88是數(shù)組d中第9個數(shù)據(jù)，因此，共查找9次，答案為C。
2.在數(shù)組d中存儲的數(shù)據(jù)依次為″if″，″for″，″range″，″while″，″def″，″True″，
″False″，″print″，″input″。現(xiàn)使用順序查找算法在數(shù)組d中查找數(shù)據(jù)″false″，共需查找的次數(shù)為(　　)
A.0次 B.7次 C.9次 D.10次
C
解析　本題主要考查的是順序查找算法的算法思想。數(shù)組d中沒有數(shù)據(jù)″false″，因此，共查找次數(shù)為d數(shù)組中數(shù)據(jù)的總數(shù)，即查找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，輸出結(jié)果為(　　)
A.12567 B.125678
C.014567 D.0145678
解析　本題主要考查的是順序查找的程序?qū)崿F(xiàn)。本題程序的功能是在列表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，輸出結(jié)果為(　　)
A.'str'，'abs'，'install‘ B.'str'，'abs'，'Some'，'install'
C.['str'，'abs'，'Some'，'install'] D.['str'，'abs'，'install']
解析　本題主要考查的是順序查找的程序?qū)崿F(xiàn)。本題程序的功能是在列表d中查找包含字符s的元素，并將這些元素記錄在列表b中，需注意的是字符串的字母是區(qū)分大小寫的，輸出結(jié)果是列表中的內(nèi)容，因此答案為D。
4
鞏固與提升
基礎(chǔ)鞏固
能力提升
1.在數(shù)組d中存儲的數(shù)據(jù)依次為“17，11，36，48，19，22，39，56，17，100”。現(xiàn)使用順序查找算法在數(shù)組d中查找數(shù)據(jù)17，共需查找的次數(shù)為(　　)
A.0次 B.1次 C.9次 D.10次
B
解析　本題主要考查的是順序算法。數(shù)組d中有2個17，順序查找默認(rèn)只找到第一個滿足條件的數(shù)據(jù)就結(jié)束查找，因此找到第1個17后就結(jié)束查找，即查找1次，答案為B。
2.在數(shù)組d中存儲的數(shù)據(jù)依次為“10，22，16，80，19，35，41，88，66，71”。現(xiàn)使用順序查找算法在數(shù)組d中查找數(shù)據(jù)99，共需查找的次數(shù)為(　　)
A.0次 B.10次 C.11次 D.無窮次
B
解析　本題主要考查的是順序算法。數(shù)組d中沒有數(shù)據(jù)99，因此需要全部查找一遍才結(jié)束。故共查找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
程序執(zhí)行時，輸入key的值為t，則輸出的內(nèi)容為(　　)
A.t 3 B.tttt 3 C.t 4 D.tttt 4
解析　本題主要考查的是順序算法的程序?qū)崿F(xiàn)。本題程序的功能是在字符串a(chǎn)中查找key的值，若找到，則將key的值拼接在字符串s中，并統(tǒng)計個數(shù)，因此輸出結(jié)果為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
程序執(zhí)行時，輸入key的值為45，則輸出的內(nèi)容為(　　)
A.Not found! B.Find！pos＝1
C.Find！pos＝5 D.Find！pos＝9
解析　本題主要考查的是順序算法的程序?qū)崿F(xiàn)。本題程序的功能是在列表b中查找key的值，若找不到，則輸出“Not found！”；如果找到且有多個時，記錄的是最后一個與key相等的元素的索引位置，需注意的是，本題是從列表最后一個元素往前進(jìn)行查找，因此輸入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！″)
解析　本題主要考查的是順序查找算法的程序?qū)崿F(xiàn)。本程序的功能是在列表wordlist中查找包含some的單詞中長度為最長的單詞，因此，答案為D。
程序執(zhí)行時，輸入字符內(nèi)容為“some”(不包含引號)，則輸出的內(nèi)容為(　　)
A.some B.somethings
C.fulsomes D.adventuresome
6.編寫一個Python程序，功能為：輸入關(guān)鍵字后，在書目清單列表中查找書名中包含關(guān)鍵字的書，并統(tǒng)計數(shù)量，然后在所有找到的書目中找出價格最貴的書。
書目清單存儲在列表book中，每本書包含三個內(nèi)容：書名、作者和價格。
程序運行示例如圖所示：
節(jié)目清單為：
['Python編程從入門到實踐'，'埃里克·馬瑟斯'，89.0]
['C語言程序設(shè)計入門教程'，'史蒂芬·普拉達(dá)'，187.0]
['Javascript高級程序設(shè)計'，'馬特·弗里斯比'，129]
['R語言實戰(zhàn)'，'卡巴科弗'，99.0]
['Java核心技術(shù)卷Ⅰ'，'凱·S·霍斯特曼'，149.0]
['Python基礎(chǔ)教程'，'Magnus Lie Hetland'，99.0]
['零基礎(chǔ)學(xué)C＋＋'，'明日科技'，79.8]
['Python學(xué)習(xí)手冊'，'馬克·盧茨'，219.0]
['Python數(shù)據(jù)結(jié)構(gòu)與算法分析'，'布拉德利·米勒'，79.0]
請輸入關(guān)鍵詞：Python
符合要求的書單有：
['Python編程從入門到實踐'，'埃里克·馬瑟斯'，89.0]
['Python基礎(chǔ)教程'，'Magnus Lie Hetland'，99.0]
['Python學(xué)習(xí)手冊'，'馬克·盧茨'，219.0]
['Python數(shù)據(jù)結(jié)構(gòu)與算法分析'，'布拉德利·米勒'，79.0]
共找到4本
價格最貴是：['Python學(xué)習(xí)手冊'，'馬克·盧茨'，219.0]
實現(xiàn)上述功能的Python程序如下，請在程序劃線上填入合適的代碼。
#列表book中存儲了書本的信息，列表內(nèi)容略
n＝len(book)
print(″書目清單為：″)
for i in range(0，n，3)：
print(book[i：i＋3])
keyword＝input(″請輸入關(guān)鍵詞：″)
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])
解析　本題主要考查的是順序查找算法的綜合應(yīng)用。每本書包含三個信息：書名、作者和價格，即最后一本書的書名book[n－3]，因此①處代碼為i<＝n－3；本題中查找是書名中包含的關(guān)鍵字的書，因此可用in運算實現(xiàn)，即②處代碼keyword in book[i]；當(dāng)找到當(dāng)前價格最高的書時，修改maxprice的值，還要記錄當(dāng)前的書在列表中的索引位置，因此，③處代碼為posi＝i。
答案　①i<＝n－3　②keyword in book[i] ③posi＝i
7.列表a中相鄰兩個數(shù)據(jù)無重復(fù)，現(xiàn)要查找連續(xù)最大步長的升序段。具體描述如下：
(1)步長指的是升序段中最后元素和最初元素的差值；
(2)有相同步長的升序段則輸出最先找到的升序段。
程序運行效果如圖所示。
數(shù)據(jù)序列為：[1，24，1，2，16，25，33，4，10，32，46，47，56，23，50]
最大步長的升序段為：[4，10，32，46，47，56]
實現(xiàn)上述功能的Python代碼如下，請回答下列問題。
#讀入數(shù)據(jù)并存儲在列表a中，代碼略
print(″數(shù)據(jù)序列為：″，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)若數(shù)據(jù)序列為“12，15，20，25，50，2，8，19，45，18，20，25，30，36，38，11，30”則最大步長的升序段為____________________。
(2)請在劃線處填入適當(dāng)?shù)拇a。
答案　(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)根據(jù)連續(xù)最大步長的升序段的含義，數(shù)據(jù)序列中的最大步長升序段為[2，8，19，45]或2，8，19，45或2 8 19 45；(2)題目中描述的步長是指升序段中最后元素和最初元素的差值，即升序段中相鄰兩個元素的差值之和，變量mstep記錄當(dāng)前升序段的步長，變量ans則記錄最大步長，因此①處代碼為mstep＋＝a[i＋1]－a[i]，或?qū)憺?mstep＝mstep＋a[i＋1]－a[i]；若當(dāng)前相鄰兩個元素為升序(a[i＋1]>a[i])，且它們的差值為之前所有升序段中的最大步長，則修改ans、maxp的值分別為mstep和i＋1，同時初始化maxt的值為1，因此②處代碼為maxt＝1；劃線③處的循環(huán)表示輸出將最大步長升序段的數(shù)據(jù)存放在列表st中，最大步長升序段的數(shù)據(jù)的索引位置為maxp－maxt～maxp，因此③處代碼為maxp－maxt，maxp＋1。
8.利用某火車購票系統(tǒng)購票，購買者輸入“出發(fā)站”、“目的站”，系統(tǒng)會統(tǒng)計兩站之間的占座情況，根據(jù)空座數(shù)量(出發(fā)站至目的站之前一直是空的座位即為空座)返回余票情況，購買者根據(jù)余票信息購買車票，獲得具體座位號。
根據(jù)上述功能，小王編寫了一個Python程序模擬該購票系統(tǒng)，以“杭臺高鐵”為例，全線共設(shè)9個車站，某趟列車共有8節(jié)車廂，每節(jié)車廂共有17排，每排5個座位(編號分別是A、B、C、D、F)，共680個座位，某時刻的占座情況如圖所示。具體設(shè)計如下：從數(shù)據(jù)庫中讀取占座情況存儲在列表seat中(例如：序號為84座位各站點占座情況，在seat[84]中表示為[1，1，0，0，0，0，1，1]，索引號2至5的值都為0，則當(dāng)出發(fā)站為臨海站，目的站為上虞南站，該座位為空座)，然后根據(jù)購買者輸入的出發(fā)站和目的站的站點名稱，統(tǒng)計空座數(shù)量及相應(yīng)的座位序號，根據(jù)購票信息，輸出購票的具體座位(其中連票數(shù)量盡可能多)
杭臺高鐵某—時刻占座情況—覽表
(0表示空座，1表示占座)
(1)主程序，根據(jù)購票步驟，請在劃線處填入合適的代碼。
#獲取列車每個座位號及其在各站點占座情況，存儲在二維列表 sat 中，代碼略
site＝[″溫嶺″，″臺州″，″臨海″，″天臺山″，″嵊州新昌″，″嵊州北″，″上虞南″，″紹興北″，″杭州東″]
begin＝site.index(input(″輸入出發(fā)站：″)) #index 方法用于獲取列表的索引號
end＝site.index(input(″輸入目的站：″))
tic＝gethavet((begin，end))　#獲取基于出發(fā)站和目的站前的所有空座座位序號列表
if len(tic)>0：
　 num＝int(input(″尚有余票″＋①________＋″張，請輸入購買的數(shù)量：″))
　 if num<＝len(tic)：
　seatno，ser＝assignment(num，tic)　#獲取相應(yīng)座位序號及連票數(shù)量
　 #seatno 列表存儲格式如：[4，5，6，7，8]或[4，5，6，8，9]
　 print(″購票″＋str(num)＋″張，其中連票數(shù)量″＋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＋″座″) #將新的占座數(shù)據(jù)寫入數(shù)據(jù)庫，代碼略
　 else：
　print((″購買數(shù)量不得大于余票數(shù)量！″))
else：
　 print(″余票不足！″)
(2)獲取余票數(shù)據(jù)，如下的 gethavet 函數(shù)，獲取出發(fā)站至目的站前的空座座位序號，保存在列表 s 中并返回。請在劃線處填入合適的代碼。
def gethavet(x，y)：
　 s＝0
　 for i in range(680)：
　nows＝seat[i] #nows 存儲當(dāng)前序號各個站點的占座情況
　if ③________________：
　　　　s.append(i)
　 return s
(3)座位分配，如下的 assignment 函數(shù)，按序號查找連票，如果找到一組連票數(shù)量等于購買的數(shù)量，則退出查找并返回相應(yīng)信息，若連票數(shù)量不足，則補充座位數(shù)量后返回。請在劃線處填入合適的代碼。
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　#滿足需要的數(shù)量，結(jié)束查找
　 else：
　　 　tmp＝1
　 #將連票的座位序號存于列表 slist，若連票數(shù)量不足則補充座位數(shù)量，代碼略
　 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(tǒng)－x或not 1 in nows[x：y]　(3)tic[i]＝＝tic[i－1]＋1
解析　(1)tic存儲可用的空座序號列表。第①空要求表示可用空座的數(shù)量，即len(tic)。輸出座位時，分別使用conch、row、number變量存儲當(dāng)前座位的車廂、排、座位編號。對于每個座位序號kinsentno，通過對85的整除和模運算計算了車廂和排序號，很多學(xué)生會思維慣性地用85繼續(xù)當(dāng)作主要參數(shù)計算number，而實際上座位編號是在A～F上循環(huán)編號的。(2)完善主程序中調(diào)用的gethavet函數(shù)。函數(shù)功能是計算空座列表。nows[x：y]表示當(dāng)前座位在出發(fā)站到終點站前的空座情況，只要該連續(xù)站上均為空座即可售票。(3)尋找連續(xù)的座位，觀察代碼for i in range(1，len(tic))，應(yīng)該是當(dāng)前項與前一項比較。

展開更多......

收起↑