资源简介

专题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])

展开更多......

收起↑