資源簡介

專題17　排序算法
知識點一　冒泡排序算法思想
1.有一個數組，采用冒泡排序，第一遍排序后的結果為：4，10，5，32，6，7，9，17，24該數組的原始順序不可能的是(　　)
A.10，5，32，6，7，9，17，24，4
B.10，5，32，6，7，9，4，17，24
C.10，5，32，4，6，7，9，17，24
D.4，10，5，32，17，9，24，6，7
2.有一個數組采用冒泡排序，第1遍排序后的結果為：3，18，5，35，8，9，11，13，32，那么該數組的原始順序不可能是(　　)
A.18，5，35，8，9，11，3，13，32
B.3，18，5，35，13，11，32，8，9
C.18，5，35，3，8，9，11，13，32
D.18，5，35，8，9，11，13，32，3
3.列表s包含8個互不相等的元素，即s[0]，s[1]，s[2]，…，s[7]，有如下Python程序段：
n＝8
for i in range(n－1)：
　 for j in range(n－1，i＋1，－1)：
　 　　if s[j]>s[j－1]：
　 　　　　s[j]，s[j－1]＝s[j－1]，s[j]
該程序段實現的是(　　)
A.s[0]到s[7]的降序排列 B.s[0]到s[7]的升序排列
C.s[1]到s[7]的降序排列 D.s[1]到s[7]的升序排列
4.列表中有n個互不相等的元素，即s[0]，s[1]，s[2]，…s[n－1]，有如下Python程序段：
for i in range ((1)________)：
　 for j in range ((2)________)：
　 　　if s[j]>s[j－1]：
　　 s[j]，s[j－1]＝s[j－1]，s[j]
上述程序段中劃線處可選代碼為：
①0，n－1　②1，n－1　③1，n　④1，n－i－1 ⑤1，n－i　⑥1，n－i＋1
為完成元素的排序，(1)(2)處代碼依次為(　　)
A.①④ B.①⑥
C.②⑤ D.③⑥
5.互不相等的10個列表元素s[0]，s[1]，s[2]…s[9]，有如下Python程序段：
n＝10
for i in range( 5)：
　 for j in range(1，n－i)：
　 if s[j]>s[j－1]：
　　　s[j]，s[j－1]＝s[j－1]，s[j]
該程序段實現的是(　　)
A.s[0]到s[5]的降序排列 B.s[0]到s[5]的升序排列
C.s[5]到s[9]的降序排列 D.s[5]到s[9]的升序排列
6.列表a中存儲了8個元素，即a[0]，a[1]，…a[7]，有如下Python程序段：
n＝8
for i in range(n－1)：
for j in range(n－1，i，－1)：
if a[j]a[j－1]，a[j]＝a[j]，a[j－1]
該程序段實現的是(　　)
A.a[0]到a[7]升序排序
B.a[4]到a[7]升序排序
C.a[0]到a[7]的數據對4取余之后升序排序
D.a[0]到a[3]、a[4]到a[7]分別升序排序
7.有如下Python程序段：
#輸入若干數據存儲在數組a中，代碼略
n＝len(a)
for i in range(2)：
for j in range(n－1，i，－1)：
if a[j] % 3>a[j－1] % 3：
a[j]，a[j－1]＝a[j－1]，a[j]
print(a)
以下運行結果不可能的是(　　)
A.[20，50，10，40，30，60] B.[5，8，1，3，4，6]
C.[9，17，16，4，12，5] D.[17，11，1，4，9，6]
8.有如下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
9.有如下兩段Python程序：
s＝' ' for i in range(5)： 　 for j in range(0，6－i－1)： 　 　　if a[j]s＝' ' for i in range(5)： 　 for j in range(5，i，－1)： 　 　　if a[j]>a[j－1]： 　 　　　　a[j]，a[j－1]＝a[j－1]，a[j] 　 s＋＝str(a[i])＋'，' print(s)
若數組a的元素為[34，33，25，46，17，77]，則下列說法不正確的是(　　)
A.兩段程序的比較次數一樣
B.兩段程序的交換次數一樣
C.兩段程序的輸出結果一樣
D.兩段程序都能實現數組a降序排序
10.數組a中存儲著全校學生的學號和BMI信息，格式為[['0101'，19.2]，['0102'，18.5]，['0103'，20.1]，…]。其中每條數據的第一項為學號，第二項為BMI值。數組a已經按學號升序排序，現要求按照BMI值進行降序排序，BMI相同情況下仍然按照學號保持升序。則下列程序段可以實現該功能的是(　　)
A.for i in range(1，n)：
for j in range(n－i)：
　 if a[j＋1]>a[j]：
　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
B.for i in range(1，n)：
　 for j in range(n－i)：
　 　　 if a[j][1]>a[j＋1][1]：
　 　　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
C.for i in range(1，n)：
　 for j in range(n－1，i－1，－1)：
　 　 　if a[j][1]<＝a[j－1][1]：
　 　　　 　a[j]，a[j－1]＝a[j－1]，a[j]
D.for i in range(1，n)：
　 for j in range(n－1，i－1，－1)：
　 　 　if a[j][1]>a[j－1][1]：
　 　　　　 a[j]，a[j－1]＝a[j－1]，a[j]
知識點二　冒泡排序的應用
1.有以下Python程序段：
n＝6
s＝[5，9，8，6，7，1]
for i in range(3)：
　 for j in range(________)：
　 　　if s[j]　　　s[j]，s[j－1]＝s[j－1]，s[j]
執行該程序段后，數據s的值為[5，6，8，9，7，1]，則劃線處的代碼是(　　)
A.n－2，i，－1 B.1，n－i－1
C.1，n－i－2 D.n－1，i，－1
2.小明對某校立定跳遠測試成績進行排序，要求女生在前，男生在后，同性別按成績降序排序。實現功能的Python程序如下：
a＝[[″俞凱睿″，235，'男']，[″張佳妮″，210，'女']，[″王靜怡″，220，'女']，[″顧筱楊″，260，'男']，[″李臣武″，250，'男']，[″陳丹祺″，230，'女']，[″李鴻慧″，240，'女']]
n＝len(a)
for i in range(n－1)：
　 for j in range(①________)：
　 　　if int(a[j][1])>int(a[j－1][1]) and a[j][2]＝＝a[j－1][2]：
　 　　　　a[j]，a[j－1]＝a[j－1]，a[j]
　 　　elif ②________：
　 　　　　a[j]，a[j－1]＝a[j－1]，a[j]
A.①1，n－i－1 ②a[j][2]＝＝″女″and a[j－1][2]＝＝″男″
B.①n－1，i，－1 ②a[j][2]＝＝″男″and a[j－1][2]＝＝″女″
C.①1，n－I ②a[j][2]＝＝″女″and a[j－1][2]＝＝″男″
D.①n－1，i＋1，－1 ②a[j][2]＝＝″男″and a[j－1][2]＝＝″女″
3.某Python程序如下：
a＝[3，8，6，2，3]
for i in range(len(a)－1，－1，－1)：
if a[i]%2＝＝0：
　 for j in range(i)：
　 　　if a[j]>a[j＋1]：
　 　 　　　a[j]，a[j＋1]＝a[j＋1]，a[j]
print(a)
程序運行后，輸出的結果是(　　)
A.[2，6，8，3，3] B.[3，3，2，6，8]
C.[2，3，6，8，3] D.[2，3，3，6，8]
4.有如下Python程序段：
a＝int(input(″輸入參數a：″))
b＝int(input(″輸入參數b：″))
c＝int(input(″輸入參數c：″))
for i in range(a，b，c)：
　 if f[i]　 　　f[i]，f[i＋1]＝f[i＋1]，f[i]
print(f)
執行該程序段后，若數組f中元素值依次為“7，4，6，5，3，2”，則數組f中元素初始值不可能是(　　)
A.7，2，4，6，5，3 B.4，7，5，6，3，2
C.7，4，5，6，2，3 D.4，6，7，2，3，5
5.有如下Python程序：
a＝[1，5，2，9，6，7]
n＝len(a)
for i in range(n//2)：
for j in range(n－1，i，－1)：
if a[j]>a[j－1]：
　　　 　a[j]，a[j－1]＝a[j－1]，a[j]
執行該程序段后，a的值是(　　)
A.[9，7，6，1，5，2] B.[9，7，6，5，2，1]
C.[1，2，5，6，7，9] D.[9，6，7，5，2，1]
6.有如下Python程序段：
lst＝[74，32，66，46，38，28，85]
k＝1
for i in range(len(lst)－1)：
if lst[i]*k　 　　 print(lst[i]，end＝″ ″)
　 　　 k＝－k
執行完以上程序段后，輸出的內容為(　　)
A.74 66 38 B.74 32 66 38 28
C.74 32 66 46 38 28 D.46
7.有如下Python程序段
d＝[11，9，23，4，8，10，9，7]
n＝len(d)
p＝q＝0；cnt＝0
for i in range(1，n)：
cnt＝cnt＋1
for j in range(n－1，p，－1)：
if d[j]>d[j－1]：
　　　 　d[j]，d[j－1]＝d[j－1]，d[j]
　　　　 p＝j
if q＝＝p：
break
q＝p
print(cnt)
運行該程序段后，變量cnt的值為(　　)
A.8 B.7
C.6 D.5
8.數組a包含10個互不相同的元素，即a[0]，a[1]，…a[9]，其中a[0]，a[2]，…a[8]稱為奇數位元素，a[1]，a[3]，…a[9]稱為偶數位元素。有如下Python程序段：
n＝len(a)
for i in range(n//2－1)：
　 for j in range(n－2，2*i，－2)：
　 　　if a[j]　 　　　　a[j]，a[j－2]＝a[j－2]，a[j]
該程序段實現的功能是(　　)
A.僅對奇數位元素升序排列
B.僅對偶數位元素升序排列
C.奇數位元素升序，偶數位元素降序排列
D.奇數位元素降序，偶數位元素升序排列
9.有如下Python程序段：
import random
a＝[34，17，19，13，10，6，26，21]
x＝(random.randint(1，4))*2
for i in range(8－x)：
　 for j in range(7，i，－1)：
　 　　if a[j] >a[j－1]：
　 　　　　a[j]，a[j－1]＝a[j－1]，a[j]
print(a[0：4])
程序段執行后，輸出的結果不可能是(　　)
A.[34，26，21，19] B.[34，26，21，17]
C.[34，26，17，19] D.[34，17，19，13]
10.拍畢業照時需要兩邊低，中間高的隊形。例如有身高數據a為[157，165，172，179，182]，最后的隊形為：[165，179，182，172，157]。有如下Python程序段實現了該功能，①②兩處代碼正確的是(　　)
n＝len(a)
for i in range(n－1)：
if ①________：
for j in range(i//2，n－i//2－1)：
　　　 if a[j]　 　　　　　　a[j]，a[j＋1]＝a[j＋1]，a[j]
else：
for j in ②________：
　 　　　　if a[j]　 　　　　a[j]，a[j－1]＝a[j－1]，a[j]
A.①i%2＝＝0　②range(n－i//2－1，i//2，－1)
B.①i%2＝＝0 ②range(n－i//2－2，i//2，－1)
C.①i%2＝＝1 ②range(n－i//2－1，i//2，－1)
D.①i%2＝＝1 ②range(n－i//2－2，i//2，－1)
11.有如下Python程序段：
from random import randint
n＝8
L＝[randint(10，99) for i in range(n)]
for i in range(n－1)：
for j in range(i＋2，len(L)，2)：
if i%2＝＝1 and L[i]>L[j] or i%2＝＝0 and L[i]　　　 L[i]，L[j]＝L[j]，L[i]
執行以上程序段，數組L的值不可能的是(　　)
A.[93，15，60，62，40，65，16，90]
B.[80，20，79，41，19，88，18，99]
C.[50，84，44，39，41，50，19，11]
D.[96，11，69，16，29，46，28，80]
12.小明編寫Python程序對本校跳高測試成績進行排序，規則如下：按照性別分別對成績進行降序排序并輸出名次(女生排前，男生排后，同分同名次)，計算結果如圖所示。
(1)程序中加框處代碼有錯，請改正。
(2)請在劃線處填入合適的代碼。
#把文件中的原始數據導入到數組a中，其中a[0][0]存儲姓名，a[0][1]存儲跳高成績，a[0][2]存儲性別，a[1][0]到a[1][2]存儲第一位學生的相關信息，以此類推。代碼略
for i in range(1，①________)：
for j in range(1，len(a)－i)：
if int(a[j][1])　　　 a[j]，a[j＋1]＝a[j＋1]，a[j]
elif ：
　　 　 a[j]，a[j＋1]＝a[j＋1]，a[j]
a[1][3]＝1
for i in range(2，len(a))：
　 if a[i][1]！＝a[i－1][1]：
　a[i][3]＝i
　 else：
　 　　②________
t＝0
for i in range(1，len(a))：
　 if a[i][2]＝＝″女″：
　 　　③________
　 else：
　 　　a[i][3]＝a[i][3]－t
#輸出數據 a 到文件中，代碼略
專題17　排序算法
知識點一
1.D　[冒泡的方向可以從前往后排序，后面的數據先有序；也可以從后往前排序，前面的數據先有序。第一遍排序后的結果把最小的數排到了最前面，因此可以推斷是升序排列。]
2.B　[本題主要考查冒泡排序。第1趟排序后最大值在中間，最小值在最左側，是對原始數據進行了從后往前的升序排列，按此排序方式，只有B項符合要求。]
3.C　[本題考查冒泡排序的算法思想。一共排了n－1趟，從內循環來看，實現從后往前冒泡排序。當i為0時，終值能取到2。第1次為s[7]和s[6]比較，最后一次為s[2]和s[1]比較，因此實現s[1]到s[7]的降序排列。]
4.D　[本題考查冒泡排序的程序實現。內循環決定排序的方向的區間，從前往后冒泡，后面的數據先有序，若i的范圍是[0，n－2]，則待排序的右端點為[n－1－i]，則j的range為(1，n－1－i＋1)，若i的范圍是[1，n－1]，則待排序的右端點為[n－i]，則j的range為(1，n－i＋1)。從后往前冒泡，前面的數據先有序，若i的范圍是[0，n－2]，則待排序的左端點為[i]，則j的range為(n－1，i＋1－1)，若i的范圍是[1，n－1]，則待排序的右端點為[i－1]，則j的range為(n－1，i＋1)。]
5.C　[本題考查冒泡排序算法思想。分析冒泡排序內循環的代碼，是從左(前)向右(后)冒泡、降序。外循環只進行了5次，所以只有最后5個數(s[5]到s[9])是有序的。]
6.D　[a[7]和a[6]、a[6]和a[5]、a[5]和a[4]依次比較，實現a[4]到a[7]升序，j為4時，并沒有和a[3]比較和交換，但a[3]和a[2]、a[2]和a[1]、a[1]和a[0]依次比較和交換，形成升序序列。]
7.C　[本題考查程序冒泡排序。從右往左(從后往前)進行了2趟排序，排序比較是元素%3后，最前面的2個元素除3余數一定是所有元素中最大的。]
8.C　[本題考查雙關鍵字排序。數組a中數據升序，當a數組中值相等時，以b數組對應的值為依據，即b數組中數據降序。數組a中最小有2個2，b數組分別是對應為7和4，b中7排在前面。]
9.C　[本題考查冒泡算法實現。兩段程序功能是一樣的，但左邊的算法先輸出第1個有序的值，即顯示的結果是從小到大，而右邊的是顯示排好序以后的順序，即從大到小顯示。]
10.D　[本題考查冒泡排序算法實現。A選項比較的關鍵字應為：if a[j＋1][1]>a[j][1]。B選項位置0不參與排序。C選項題干要求BMI相同的情況下仍然按照學號保持升序，加了等號學號大的會排在前面。]
知識點二
1.C　[本題考查冒泡排序。該算法實現前4個數據的升序排列，因此排序的區間為[0，4]，若要從后往前排序，第1項為n－3，結束位置為i＋1。若要從前往后排序，則j的初值為1，當i為0時，最后的索引為n－3，因此j的終值為n－i－3，但終值必須為n－i－2才可以取到n－i－3。]
2.C　[本題考查冒泡排序算法思想。①排序的方向和區間。若從前往后排序，后面的數據先有序，第i趟排序的區間為[0，n－1－i]，比較對象位置為j和j－1，因此range的初值為1，終值為n－1－i＋1。若從后往前排序，前面的數據先有序，第i趟排序的區間為[n－1，i]，因此range的初值為n－1，終值為i＋1－1，步長為－1。②交換的條件。要求女生在前，男生在后，同性別按成績降序排序。女生在后，男生在前需進行交換。]
3.C　[本題考查冒泡排序，當a[i]是偶數時排序，因此3不參與排序，第一趟結果為[3，8，6，2，3]，再依次進行排序。]
4.D　[本題考查冒泡排序的算法思想。比較對象是相鄰兩個數，比較條件f[i]5.A　[從后往前冒泡，排了3趟。第1趟結果為9，1，5，2，7，6；第2趟結果為9，7，1，5，2，6；第3趟結果為9，7，6，1，5，2。]
6.D　[本題主要考查Python程序的執行。分析程序可知，每次循環k都變號，如果滿足lst[i]*k32，－32>－66，66>46，－46<－38，38>28，－28>－85，故滿足if判斷的只有－46<－38，故輸出的內容為46。]
7.D　[從后往前冒泡排序，前面的數據先有序，p記錄最后一次交換的位置，如果一趟中沒有數據交換，則排序結束。變量cnt統計排序趟數。]
8.A　[本題考查冒泡排序算法思想。外循環決定排序趟數，內循環決定排序方向和區間，內循環初值為n－2，步長為負2，因此僅對奇數位置排序。]
9.C　[本題考查冒泡排序算法思想。外循環i表示排序趟數，決定了有序元素的個數，內循環j決定了排序的區間和方向。從后往前冒泡，前面的數據先有序，從條件a[j]>a[j－1]來看，實現降序排列。A選項至少排4趟，B選項只排2趟，D選項未排序，C選項第1趟排序過程中，17和19要交換位置。]
10.B　[變量i表示排序的趟數也表示位置。奇數趟從前往后排，偶數趟從后往前排。]
11.C　[本題考查冒泡排序算法。算法實現偶數位升序，奇數位降序排列。]
12.(1)a[j＋1][2]＝＝″女″ and a[j][2]＝＝″男″ (2)①len(a)－1　②a[i][3]＝a[i－1][3] ③t＝t＋1或t＋＝1
解析　本題考查雙關鍵字排序和順序查找算法。(1)先按照性別和成績進行降序排序，發生數據交換的情況有兩種情況：一是性別相同，成績大的在后，二是男生在前，女生在后。a[0][1]存儲跳高成績，a[0][2]存儲性別，條件“int(a[j][1])

展開更多......

收起↑