資源簡介

第五章　數據結構與算法
課時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)。

展開更多......

收起↑