资源简介

四、 冒泡排序算法及程序实现
1. 采用冒泡排序算法对9个数据进行升序排序,则排序共需要进行的轮(遍)数是(　B　)
A. 1 B. 8
C. 9 D. 10
【解析】 n个数据共需要进行n－1轮(遍)冒泡才能实现有序,B正确。
2. 对7个数据采用冒泡排序算法进行升序排序,第一遍加工后的结果为1,70,53,57,28,30,77,则原始数据可能是(　C　)
A. 1,70,53,57,77,28,30
B. 70,1,53,57,28,30,77
C. 70,53,57,28,30,77,1
D. 70,53,1,57,28,30,77
【解析】 本题给出7个数据采用冒泡排序第一遍加工后的结果来判定原始数据的可能情况。由于原始数据的情况可能不唯一。所以本题适合采用排除法来解决。选项A、B、D如果是原始数据,采用冒泡排序第一遍加工后的结果分别是“1,28,70,53,57,77,30”“1,70,28,53,57,30,77”和“1,70,53,28,57,30,77”,均不符合题意,而选项C通过冒泡升序排序第1遍加工后的结果如题意所述,符合题意。
3. 对3,7,5,8,2,6,14,12,13,21这10个数据进行从小到大的冒泡排序,第一遍加工需要进行的数据交换次数是(　A　)
A. 5 B. 6
C. 7 D. 8
【解析】 本题给出待排序的10个数据,并采用冒泡排序进行从小到大排序,要求统计第一遍加工数据的比较和交换次数。根据冒泡排序思想,在比较中,如果发生逆序现象,就需要发生交换。经过模拟发现第一轮冒泡中,发生数据交换5次。A正确。
4. 有如下Python程序:
a= [19, 4, 1, 0, 2, 1, 9, 3]
cnt=0
n=len(a)
for i in range(n－1):
　　flag=False
　　for j in range(n－i－1):
　　　　if a[j]>a[j＋1]:
　　　　　　a[j],a[j＋1]=a[j＋1],a[j]
　　　　　　flag=True
　　cnt＋=1
　　if not flag:
　　　　break
print(cnt)
则程序运行结束后,变量cnt的值为(　B　)
A. 3 B. 4
C. 5 D. 7
【解析】 本题考查冒泡排序的改进算法。在每一轮冒泡排序中,若未发生交换,则标记flag为false,提前结束冒泡排序,cnt用于记录总共进行的轮数。根据题意,第一轮冒泡排序结果为[4, 1, 0, 2, 1, 9, 3, 19],发生过交换,cnt=1;第2轮冒泡排序结果为[1, 0, 2, 1, 4, 3, 9, 19],发生过交换,cnt=2;第3轮冒泡排序结果为[0, 1, 1, 2, 3, 4, 9, 19],虽然此时冒泡排序结果已经有序,但是发生过交换,cnt=3,还需进行第4轮冒泡排序,结果依旧为[0, 1, 1, 2, 3, 4, 9, 19],cnt=4,这一轮没有发生交换,冒泡排序结束。 B正确。
5. 某冒泡排序算法的Python程序段如下:
a = [66,34,12,59,21,26,18,45,20,16]
for i in range(1,3):
　　for j in range(len(a)－1, i, －1):
　　　　if a[j] < a[j－1]:
　　　　　　a[j],a[j－1]= a[j－1],a[j]
执行该程序段后,列表a中的值为(　B　)
A. [66, 59, 45, 34, 12, 26, 21, 20, 18, 16]
B. [66, 12, 16, 34, 18, 59, 21, 26, 20, 45]
C. [12, 16, 18, 20, 21, 26, 21, 20, 18, 16]
D. [12, 16, 18, 66, 34, 20, 59, 21, 26, 45]
【解析】 本题考查冒泡排序算法。根据内循环的判断条件可知,数据按照从小到大,且上冒的排列。但由于外层循环变量i从1开始,因此数据a[0]未参与排序。第一轮排序后a=[66, 12, 34, 16, 59, 21, 26, 18, 45, 20],第二轮排序后a=[66, 12, 16, 34, 18, 59, 21, 26, 20, 45]。B正确。
6. 有如下Python程序段:
a=[111,64,9,12,34,25,22]
for i in range(len(a)－1):#①
　　for j in range(len(a)－i－1):#②
　　　　if a[j]　　　　　　a[j],a[j＋1]=a[j＋1],a[j]
print(a)
下列说法中,错误的是(　B　)
A. 若①加框处改为“2”,程序运行结果不变
B. 若②加框处改为“len(a)－2,i－1,－1”,总交换次数会发生变化
C. 该程序执行结束后,总的比较次数为21
D. 该程序执行结束后,数组a结果为[111,64,34,25,22,12,9]
【解析】 本题考查冒泡排序算法知识。根据给出的数据以及冒泡方向,两遍即可完成,所以改为2,结果不变,A不符合题意。冒泡排序的交换次数和逆序对有关,和冒泡方向无关,B符合题意。比较次数为1＋2＋3＋4＋5＋6=21,C不符合题意。本题代码是降序,结果正确,D不符合题意。
7. 有如下Python程序段:
import random
a=[54,36,69,11,3,46]
t=(random.randint(1,3))*2
for i in range(6－t):
　　for j in range(5,i,－1):
　　　　if a[j]　　　　　　t=a[j]
　　　　　　a[j]=a[j－1]
　　　　　　a[j－1]=t
print(a)
执行该程序段后,输出的结果不可能是(　C　)
A. [3,11,36,46,54,69]
B. [3,11,54,36,69,46]
C. [3,54,36,69,11,46]
D. [54,36,69,11,3,46]
【解析】 首先t是一个[2,6]之间的随机偶数,即[2,4,6], C选项的结果是冒泡排序一趟后的结果,就是t=1时才能有的结果,所以不可能,C符合题意。
8. 有如下Python程序段:
a = ["Java ", "VB ", "Delphi ", "Pascal ", "Python ", "C "]
for i in range(0,3):
　　for j in range(0,5－i):
　　　　if a[j] > a[j ＋ 1]:
　　　　　　　　a[j],a[j＋1] = a[j＋1],a[j]
print(a)
执行该程序段后,列表元素a的数据为(　B　)
A. ["C ", "Delphi ","Java " , "Pascal ", "Python ", "VB "]
B. ["Delphi ", "Java ", "C ", "Pascal ", "Python ", "VB "]
C. ["VB ", "Python ", "Pascal ", "Java ", "Delphi ", "C "]
D. ["VB ", "Python ", "Pascal ", "C ", "Java ", "Delphi "]
【解析】 本题考查冒泡排序。由代码可知,冒泡进行3次,将最大的值往后推,由于是字符串的比较,先比较每个单词的首字母,若相同则比较第二个字符,ASCII码值大的为大。因此列表中,后三个数据肯定是最大的三个值,模拟后结果是B。B正确。
9. 有如下Python程序段:
import random
a=[0]*6
i = 0
while i<= 5:
　　a[i] = int(random.random()* 10)＋ 1
　　if a[i] % 2 == i % 2:
　　　　　i=i＋1
for i in range(0,2):
　　k = 1
　　for j in range(0,4 － i * 2):
　　　　　if a[j] * k > a[j ＋ 2] * k:
　　　　　　a[j],a[j ＋ 2]=a[j ＋ 2] ,a[j]
　　　　　k = －k
执行该程序段后,列表a各元素的值不可能是(　C　)
A. [4, 9, 6, 7, 10, 3]
B. [6, 9, 10, 9, 10, 1]
C. [2, 3, 4, 4, 8, 9]
D. [4, 9, 6, 5, 8, 5 ]
【解析】 本题考查冒泡排序的变形。在生成列表元素阶段,奇数位是奇数,偶数位肯定是偶数。代码中k值在1和－1间摆动,奇数位和奇数位单独进行排序,排序后偶数位升序,奇数位降序。而选项C中全部都是升序,且奇偶性也不对,所以不可能,C符合题意。
10. 如下Python程序段实现对数组元素a[0]到a[5]的升序排序:
a = [27,34,53,54,55,42]
n=len(a)
start=0
while start!=n－1: #语句①
　　　　last=n－1
for j in range(n－1,start,－1):
　　　　if a[j]　　　　　　a[j],a[j－1]=a[j－1],a[j] #语句③
　　　　　　last=j
　　start=last
print(a)
下列关于运行该程序段后的说法,错误的是(　C　)
A. 加框处代码第一次执行结束后，start的值为3
B. 语句①可以修改为while startC. 语句②执行了6次
D. 语句③执行了3次
【解析】 本题考查冒泡排序以及相关优化。根据数组a的元素,第一遍冒泡过程,最后交换的是42和53,此时j=4,A不符合题意。根据代码,start的最大取值为n－1,所以这两个条件等价,B不符合题意。循环语句执行了2遍,第一遍if语句执行了5(5－>1)次,第二遍2(5－>4)次,共7次,C符合题意。数组a中只有3对逆序对,所以交换语句执行3次,D不符合题意。
11. 生成n个随机整数,并用优化的冒泡排序将其升序排列后输出。实现上述功能的Python代码如下,运行界面如图所示。请在画线处填入合适的代码。
[28,83,93,38,37,44,59,86,68,14]
[14,28,37,38,44,59,68,83,86,93]
#生成n个不重复的随机整数并赋值给列表a,代码略
def bub_sort(d):
　　①　n=len(d)　
　　i=0
　　while i<=n－1:
　　　　　k=i;i=n
　　　　　for j in range(n－1,k,－1):
　　　　　　　if d[j－1]>d[j]:
　　　　　　　　　　d[j],d[j－1]=d[j－1],d[j]
　　　　　　　　　　②　i=j　
bub_sort(a)
print(a)
【解析】 本题考查冒泡排序的优化。①结合代码上下文,此处需要n的初始化,根据逻辑可知,应该是列表d的长度。②冒泡排序可以进行优化,例如在某一轮冒泡中,没有数据交换,则意味着下一轮冒泡不需要继续进行,可以结束。考虑到最后发生数据交换的位置是d[j－1]和d[j],因此有序区应该是d[0]至d[j－1],从d[j]开始后面的是无序区,下一趟排序的数据区域缩小为[j,n－1]即可。故答案为i=j。
12. 小张从网上获取了2022年北京冬奥会奖牌榜数据,如图所示。要求输出金牌数最高的10个国家或地区，并按金牌数降序排序,若金牌数相同,则按银牌数降序排序。为实现上述功能,小张编写了如下Python程序。请回答下列问题:
(1)请在画线处填入合适的代码。
(2)加框处的代码有错误,请改正。
【答案】 a[j][1]>a[j－1][1]or a[j][1]==a[j－1][1]and a[j][2]>a[j－1][2]a=[]
f=open("2022冬奥会奖牌榜.txt", r ,encoding= UTF－8 )
flag=True
for line in f.readlines():
　　if flag: 　#处理首行标题数据
　　　　print(line)
　　　　①　flag=False　
　　else:
　　　　t=line.split( , )
　　　　for i in range(1,len(t)):
　　　　　　t[i]=int(t[i])
　　　　a.append(t)
print("冒泡排序:")
n=len(a)
for i in range(10):
　　for j in ②　range(n－1,i,－1)　:
　　　　if a[j][1]>a[j－1][1] :
　　　　　　a[j],a[j－1]=a[j－1],a[j]
for i in range(10):
　　print(a[i])
【解析】 (1)①flag为True时,需要处理首行标题,之后flag置为False,后续数据进入else分支处理,因此此处填flag=False。②根据冒泡排序的核心程序,外层循环控制冒泡的遍数,本题控制排序进行10遍(只需要排名前10的数据),每一遍排序都有一个元素有序,而内层循环控制冒泡排序的范围,由于a[j]需要与前一个元素a[j－1]比较,金牌数多的前移,可见该冒泡排序为从后往前的按金牌数降序冒泡排序,因此j的范围是[n－1,i＋1]闭区间,步长为－1,因此此处填range(n－1,i,－1)。(2)要求按照金牌数进行降序排序,在金牌相等的情况下,再按照银牌数降序排序,因此冒泡排序时,有两种情况需要交换元素位置:①a[j][1]>a[j－1][1],即后一个元素的金牌数比前一个元素的金牌数多;②a[j][1]==a[j－1][1]and a[j][2]>a[j－1][2],即后一个元素的金牌数与前一个元素的金牌数相等,但是后一个元素的银牌更多。
13. 小王基于冒泡排序的思想设计了一个排序算法。先生成n个1~99之间的随机整数,然后用冒泡算法将列表中奇数位置的元素按照升序、偶数位置的元素按照降序分别进行排序。实现上述功能的Python程序代码如下,请回答下列问题:
原始数据是:[21,13,96,23,66,58,64,48,6,14]
排序后数据:[6,58,21,48,64,23,66,14,96,13]
(1)请在画线处填入合适的代码。
(2)将加框处的代码修改为“(n－1)//2＋1”,程序功能　不会　(填“会”或“不会”)发生改变。
import random
n=10
a=[random.randint(1,99)for i in range(n)]
print("原始数据是:",a)
for i in range(0,(n－1)//2):
　　k=1
　　for j in range(0,n－i*2－2):
　　　　if k*a[j]>k*a[j＋2]:
　　　　　　a[j], a[j＋2] = ①　a[j＋2], a[j]　
　　　　②　k=－k　
print("排序后数据:",a)
【解析】 本题考查冒泡排序算法的变形。(1)①根据代码可知,此处是将a[j]和a[j＋2]两个元素进行交换。②奇数位和偶数位升序和降序要实现交替进行,不等式变向,需要通过k实现,因此k的值必须在1和－1两者之间交替变化,因此k=－k。(2)冒泡排序中,外循环增加一次,不影响程序的功能。
14. 双向冒泡排序:经典冒泡排序是单向的,始终从第一个(或最后一个)元素开始扫描。小王对冒泡排序进行了改进,从两端进行扫描,首先从数组的左端到右端进行扫描,把最大的数往后交换(以升序为例),再从右端往左端扫描,把最小的数往前交换,多次扫描后,得到一个有序的序列。于是定义了left和right两个指针,每一遍排序,left右移一位,right左移一位。一趟排序,将最大值下沉到最后一位,最小值上浮到最前一位,最终使整个数组有序。运行界面如图所示,实现上述功能的Python代码如下。请回答下列问题:
排序前数据:[73,21,98,49,96,82,99,14,48,92]
排序后数据:[14,21,48,49,73,82,92,96,98,99]
(1)请在画线处填入合适的代码。
(2)加框处代码有错误,请改正。
import random
n = 10
a = [random.randint(10,99)for i in range(n)]
print("排序前数据:",a)
left,right = 0,n－1
while left　for j in range(①　left, right　):
　　if a[j]>a[j＋1]:
　　　 a[j],a[j＋1]=a[j＋1],a[j]
　right－=1
　for j in range(②　right,left,－1　):
　　if a[j]>a[j－1]:
　　　 a[j],a[j－1]=a[j－1],a[j]
　③　left＋=1　
print("排序后数据:",a)
【答案】 a[j]【解析】 本题考查双向冒泡排序。(1)left和right分别扫描的左右边界,有序区位于左右两端,每次扫描后,无序区边界缩小,因此left每次加1,而right每次减1。(2)升序排序,故代码为a[j]15. 某大学演唱会以评委投票方式评选最优秀的歌曲,每张选票仅填一个作品编号,得票数过半的作品获“最佳作品奖”。小李同学和小王同学负责收集全部选票,其中小李同学已将收集的选票按作品编号升序排序,小王同学收集的选票未排序。现要求将全部选票按作品编号进行非降序排序,找出获“最佳作品奖”的作品编号。编写程序,实现上述功能。运行程序,在数组a中存储全部选票,小李收集的选票在前,小王收集的选票在后。先按作品编号对全部选票进行非降序排序,最后找出“最佳作品奖”的作品编号并输出显示。运行结果如图所示,请回答下列问题:
(1)实现上述功能的部分程序如下,请在画线处填入合适的代码。
(2)程序中加框处的代码有错误,请改正。
【答案】 (0,n//2＋1)
# m为一常数
#将n张选票的作品编号存入列表a,a[0]~a[m－1]、a[m]~a[n－1]分别为小李同学和小王同学#收集选票的作品编号,代码略
n=len(a)
c=[""]*n
for i in range(n,m,－1):
　　for j in ①　range (m,n－2)或 range (m,i－1) 或 range (n－2,m－1,－1)　:
　　　　if a[j＋1] < a[j]:
　　　　　　a[j],a[j＋1] = a[j＋1],a[j]
i=0
②　j=m　
for k in range(0,n):
　　if j > n－1 or ③　i　　　　c[k] = a[i]; i = i ＋ 1
　　else:
　　　　c[k] = a[j]; j = j ＋ 1
for i in range(0,n//2):
　　if c[i] == c[i ＋ n // 2]:
　　　　print(c[i])
　　　　break
【解析】 本题考查冒泡排序及归并排序知识。(1)①考虑到冒泡排序的边界条件及外循环的范围,答案如上。②由代码可知,j是小王同学的数据范围,故j=m。③把列表a中两段合并成有序结果,利用双指针策略有序放置于列表c中,使用了归并排序的策略。初始时i指向第一段数据的起始位置1,j指向第二段数据的起始位置m。可知,i的取值范围为1~m－1,j的取值范围为m~n－1,当我们控制两个指针移动时,需要注意i、j的取值区间,避免越界。因此答案是i16. 小王为了挑选出符合自己要求的相机,从某电商平台上获取了相关产品的一系列数据,数据格式如图所示。在挑选过程中,他的第一考虑要素是价格实惠,而对于价格相同的,他的次要考虑因素是销售量。现请你帮助他实现下列排序和筛选过程:按照商品价格升序排序,商品价格相同的,根据销售量进行降序排序,在排序的过程中对数据进行整理,剔除重复数据。
(1)根据题中的算法描述,结合程序代码分析,将商品价格和销售量按题目要求采用的算法是　冒泡排序　(填“选择排序”或“冒泡排序”),其时间复杂度为　C　(单选,填字母)。
A. O(n)/ B. O(log2n)/
C. O(n2))
(2)请在画线处填入合适的代码。
import csv
a=[]
f=open("camera.csv","r")
reader=csv.reader(f)
for item in reader:　#读取文件添加到列表a中
　　a.append(item)
f.close()
n=len(a)
for i in range(1,n):　#将列表a中的“销售量”和“价格”转换为整型数据
　　a[i][2]=int(a[i][2])
　　a[i][3]=int(a[i][3])
i=1; m=n－1
while i　for j in range(①　m, i, －1　):
　　　if ②　a[j][3]a[j－1][2]　:
　　　　　a[j],a[j－1]=a[j－1],a[j]
　　　elif a[j]==a[j－1]:
　　　　　③　a[j]=a[m]　
　　　　　m－=1
　i＋=1
for i in range (m＋1):
　　print (a[i])
(3)按照上述要求排序后,小王希望筛选出每档售价的销售量的前两名的产品数据。加框处的代码有错误,请改正。
def sx(x,y):
　　if　y－x＋1>2 :　　　　#①
　　　　print(a[x])
　　　　print(a[x＋1])
　　else:
　　　　print(a[x])
i=0
j=0
for i in range(1,m):
　　if a[i][3]==a[i－1][3] :　　#②
　　　　sx(j,i－1)
　　　　j=i
sx(j,i－1)
【答案】 ①y－x＋1>=2或y－x>=1　②a[j][3]==a[i－1][3]
【解析】 本题考查多条件冒泡排序和程序实现过程。(1)从排序代码可知,比较和交换的是相邻的元素,属于冒泡排序算法。根据代码双重循环可知,其时间复杂度为O(n2),C正确。(2)①根据代码“a[j],a[j－1]=a[j－1],a[j]”可知,该程序实现从后往前的冒泡排序,所以①处填入的代码为m, i, －1。②排序的首要关键字为商品价格升序,次要关键字为销售量降序,所以此处填入的代码为a[j][3]a[j－1][2]。③该部分实现去重功能,当a[j]=a[j－1]时,用当前队尾元素a[m]覆盖a[j],以实现删除a[j]的功能,同时更新对尾指针m。(3)①题目要求筛选出“每档售价销售量前两名”,所以应填入的代码为y－x＋1>=2,当前代码实现的功能是当每档售价销售量存在3个及以上时才进行输出,不符合题目要求。②由后面的代码可知,应该是j和i－1的两个价格进行比较。(共37张PPT)
四、 冒泡排序算法及程序实现
第五章　数据结构与算法
信息技术 选择性必修1 数据与数据结构
必备知识练
1. 采用冒泡排序算法对9个数据进行升序排序,则排序共需要进行的轮(遍)数是(　　)
A. 1 B. 8
C. 9 D. 10
【解析】 n个数据共需要进行n－1轮(遍)冒泡才能实现有序,B正确。
B
2. 对7个数据采用冒泡排序算法进行升序排序,第一遍加工后的结果为1,70,53,57,28,
30,77,则原始数据可能是(　　)
A. 1,70,53,57,77,28,30
B. 70,1,53,57,28,30,77
C. 70,53,57,28,30,77,1
D. 70,53,1,57,28,30,77
【解析】 本题给出7个数据采用冒泡排序第一遍加工后的结果来判定原始数据的可能情况。由于原始数据的情况可能不唯一。所以本题适合采用排除法来解决。选项A、B、D如果是原始数据,采用冒泡排序第一遍加工后的结果分别是“1,28,70,53,57,77,30” “1,70,28,53,57,30,77”和“1,70,53,28,57,30,77”,均不符合题意,而选项C通过冒泡升序排序第1遍加工后的结果如题意所述,符合题意。
C
3. 对3,7,5,8,2,6,14,12,13,21这10个数据进行从小到大的冒泡排序,第一遍加工需要进行的数据交换次数是(　　)
A. 5 B. 6
C. 7 D. 8
【解析】 本题给出待排序的10个数据,并采用冒泡排序进行从小到大排序,要求统计第一遍加工数据的比较和交换次数。根据冒泡排序思想,在比较中,如果发生逆序现象,就需要发生交换。经过模拟发现第一轮冒泡中,发生数据交换5次。A正确。
A
4. 有如下Python程序:
a= [19, 4, 1, 0, 2, 1, 9, 3]
cnt=0
n=len(a)
for i in range(n－1):
　　flag=False
　　for j in range(n－i－1):
　　　　if a[j]>a[j＋1]:
　　　　　　a[j],a[j＋1]=a[j＋1],a[j]
　　　　　　flag=True
　　cnt＋=1
　　if not flag:
　　　　break
print(cnt)
则程序运行结束后,变量cnt的值为(　　)
A. 3 B. 4
C. 5 D. 7
B
【解析】 本题考查冒泡排序的改进算法。在每一轮冒泡排序中,若未发生交换,则标记flag为false,提前结束冒泡排序,cnt用于记录总共进行的轮数。根据题意,第一轮冒泡排序结果为[4, 1, 0, 2, 1, 9, 3, 19],发生过交换,cnt=1;第2轮冒泡排序结果为[1, 0, 2, 1, 4, 3, 9, 19],发生过交换,cnt=2;第3轮冒泡排序结果为[0, 1, 1, 2, 3, 4, 9, 19],虽然此时冒泡排序结果已经有序,但是发生过交换,cnt=3,还需进行第4轮冒泡排序,结果依旧为[0, 1, 1, 2, 3, 4, 9, 19], cnt=4,这一轮没有发生交换,冒泡排序结束。 B正确。
5. 某冒泡排序算法的Python程序段如下:
a = [66,34,12,59,21,26,18,45,20,16]
for i in range(1,3):
　　for j in range(len(a)－1, i, －1):
　　　　if a[j] < a[j－1]:
　　　　　　a[j],a[j－1]= a[j－1],a[j]
执行该程序段后,列表a中的值为(　　)
A. [66, 59, 45, 34, 12, 26, 21, 20, 18, 16]
B. [66, 12, 16, 34, 18, 59, 21, 26, 20, 45]
C. [12, 16, 18, 20, 21, 26, 21, 20, 18, 16]
D. [12, 16, 18, 66, 34, 20, 59, 21, 26, 45]
【解析】 本题考查冒泡排序算法。根据内循环的判断条件可知,数据按照从小到大,且上冒的排列。但由于外层循环变量i从1开始,因此数据a[0]未参与排序。第一轮排序后a=[66, 12, 34, 16, 59, 21, 26, 18, 45, 20],第二轮排序后a=[66, 12, 16, 34, 18, 59, 21, 26, 20, 45]。B正确。
B
6. 有如下Python程序段:
a=[111,64,9,12,34,25,22]
for i in range( len(a)－1 ):#①
　　for j in range( len(a)－i－1 ):#②
　　　　if a[j]　　　　　　a[j],a[j＋1]=a[j＋1],a[j]
print(a)
下列说法中,错. 误. 的是(　　)
A. 若①加框处改为“2”,程序运行结果不变
B. 若②加框处改为“len(a)－2,i－1,－1”,总交换次数会发生变化
C. 该程序执行结束后,总的比较次数为21
D. 该程序执行结束后,数组a结果为[111,64,34,25,22,12,9]
B
【解析】 本题考查冒泡排序算法知识。根据给出的数据以及冒泡方向,两遍即可完成,所以改为2,结果不变,A不符合题意。冒泡排序的交换次数和逆序对有关,和冒泡方向无关,B符合题意。比较次数为1＋2＋3＋4＋5＋6=21,C不符合题意。本题代码是降序,结果正确,D不符合题意。
7. 有如下Python程序段:
import random
a=[54,36,69,11,3,46]
t=(random.randint(1,3))*2
for i in range(6－t):
　　for j in range(5,i,－1):
　　　　if a[j]　　　　　　t=a[j]
　　　　　　a[j]=a[j－1]
　　　　　　a[j－1]=t
print(a)
执行该程序段后,输出的结果不. 可. 能. 是(　　)
A. [3,11,36,46,54,69] B. [3,11,54,36,69,46]
C. [3,54,36,69,11,46] D. [54,36,69,11,3,46]
【解析】 首先t是一个[2,6]之间的随机偶数,即[2,4,6], C选项的结果是冒泡排序一趟后的结果,就是t=1时才能有的结果,所以不可能,C符合题意。
C
关键能力练
8. 有如下Python程序段:
a = ["Java ", "VB ", "Delphi ", "Pascal ", "Python ", "C "]
for i in range(0,3):
　　for j in range(0,5－i):
　　　　if a[j] > a[j ＋ 1]:
　　　　　　　　a[j],a[j＋1] = a[j＋1],a[j]
print(a)
执行该程序段后,列表元素a的数据为(　　)
A. ["C ", "Delphi ","Java " , "Pascal ", "Python ", "VB "]
B. ["Delphi ", "Java ", "C ", "Pascal ", "Python ", "VB "]
C. ["VB ", "Python ", "Pascal ", "Java ", "Delphi ", "C "]
D. ["VB ", "Python ", "Pascal ", "C ", "Java ", "Delphi "]
B
【解析】 本题考查冒泡排序。由代码可知,冒泡进行3次,将最大的值往后推,由于是字符串的比较,先比较每个单词的首字母,若相同则比较第二个字符,ASCII码值大的为大。因此列表中,后三个数据肯定是最大的三个值,模拟后结果是B。B正确。
9. 有如下Python程序段:
import random
a=[0]*6
i = 0
while i<= 5:
　　a[i] = int(random.random()* 10)＋ 1
　　if a[i] % 2 == i % 2:
　　　　　i=i＋1
for i in range(0,2):
　　k = 1
　　for j in range(0,4 － i * 2):
　　　　　if a[j] * k > a[j ＋ 2] * k:
　　　　　　a[j],a[j ＋ 2]=a[j ＋ 2] ,a[j]
　　　　　k = －k
执行该程序段后,列表a各元素的值不. 可. 能. 是(　　)
A. [4, 9, 6, 7, 10, 3]
B. [6, 9, 10, 9, 10, 1]
C. [2, 3, 4, 4, 8, 9]
D. [4, 9, 6, 5, 8, 5 ]
【解析】 本题考查冒泡排序的变形。在生成列表元素阶段,奇数位是奇数,偶数位肯定是偶数。代码中k值在1和－1间摆动,奇数位和奇数位单独进行排序,排序后偶数位升序,奇数位降序。而选项C中全部都是升序,且奇偶性也不对,所以不可能,C符合题意。
C
10. 如下Python程序段实现对数组元素a[0]到a[5]的升序排序:
a = [27,34,53,54,55,42]
n=len(a)
start=0
while start!=n－1: #语句①
　　　　last=n－1
for j in range(n－1,start,－1):
　　　　if a[j]　　　　　　a[j],a[j－1]=a[j－1],a[j] #语句③
　　　　　　last=j
　　start=last
print(a)
下列关于运行该程序段后的说法,错. 误. 的是(　　)
A. 加框处代码第一次执行结束后，start的值为3
B. 语句①可以修改为while startC. 语句②执行了6次
D. 语句③执行了3次
【解析】 本题考查冒泡排序以及相关优化。根据数组a的元素,第一遍冒泡过程,最后交换的是42和53,此时j=4,A不符合题意。根据代码,start的最大取值为n－1,所以这两个条件等价,B不符合题意。循环语句执行了2遍,第一遍if语句执行了5(5－>1)次,第二遍2(5－>4)次,共7次,C符合题意。数组a中只有3对逆序对,所以交换语句执行3次,D不符合题意。
C
11. 生成n个随机整数,并用优化的冒泡排序将其升序排列后输出。实现上述功能的Python代码如下,运行界面如图所示。请在画线处填入合适的代码。
#生成n个不重复的随机整数并赋值给列表a,代码略
def bub_sort(d):
　　①______________
　　i=0
　　while i<=n－1:
　　　　　k=i;i=n
　　　　　for j in range(n－1,k,－1):
　　　　　　　if d[j－1]>d[j]:
　　　　　　　　　　d[j],d[j－1]=d[j－1],d[j]
　　　　　　　　　　②__________
bub_sort(a)
print(a)
[28,83,93,38,37,44,59,86,68,14]
[14,28,37,38,44,59,68,83,86,93]
n=len(d)
i=j
【解析】 本题考查冒泡排序的优化。①结合代码上下文,此处需要n的初始化,根据逻辑可知,应该是列表d的长度。②冒泡排序可以进行优化,例如在某一轮冒泡中,没有数据交换,则意味着下一轮冒泡不需要继续进行,可以结束。考虑到最后发生数据交换的位置是
d[j－1]和d[j],因此有序区应该是d[0]至d[j－1],从d[j]开始后面的是无序区,下一趟排序的数据区域缩小为[j,n－1]即可。故答案为i=j。
12. 小张从网上获取了2022年北京冬奥会奖牌榜数据,如图所示。要求输出金牌数最高的10个国家或地区，并按金牌数降序排序,若金牌数相同,则按银牌数降序排序。为实现上述功能,小张编写了如下Python程序。请回答下列问题:
(1)请在画线处填入合适的代码。
(2)加框处的代码有错误,请改正。
【答案】 a[j][1]>a[j－1][1]or a[j][1]==a[j－1][1]and a[j][2]>a[j－1][2]a=[]
f=open("2022冬奥会奖牌榜.txt", r ,encoding= UTF－8 )
flag=True
for line in f.readlines():
　　if flag: 　#处理首行标题数据
　　　　print(line)
　　　　①_______________
　　else:
　　　　t=line.split( , )
　　　　for i in range(1,len(t)):
　　　　　　t[i]=int(t[i])
　　　　a.append(t)
print("冒泡排序:")
n=len(a)
for i in range(10):
　　for j in ②___________________:
　　　　if a[j][1]>a[j－1][1] :
　　　　　　a[j],a[j－1]=a[j－1],a[j]
for i in range(10):
　　print(a[i])
flag=False
range(n－1,i,－1)
【解析】 (1)①flag为True时,需要处理首行标题,之后flag置为False,后续数据进入else分支处理,因此此处填flag=False。②根据冒泡排序的核心程序,外层循环控制冒泡的遍数,本题控制排序进行10遍(只需要排名前10的数据),每一遍排序都有一个元素有序,而内层循环控制冒泡排序的范围,由于a[j]需要与前一个元素a[j－1]比较,金牌数多的前移,可见该冒泡排序为从后往前的按金牌数降序冒泡排序,因此j的范围是[n－1,i＋1]闭区间,步长为－1,因此此处填range(n－1,i,－1)。(2)要求按照金牌数进行降序排序,在金牌相等的情况下,再按照银牌数降序排序,因此冒泡排序时,有两种情况需要交换元素位置:①a[j][1]>a[j－1][1],即后一个元素的金牌数比前一个元素的金牌数多;②a[j][1]==a[j－1][1]and a[j][2]>a[j－1][2],即后一个元素的金牌数与前一个元素的金牌数相等,但是后一个元素的银牌更多。
13. 小王基于冒泡排序的思想设计了一个排序算法。先生成n个1~99之间的随机整数,然后用冒泡算法将列表中奇数位置的元素按照升序、偶数位置的元素按照降序分别进行排序。实现上述功能的Python程序代码如下,请回答下列问题:
原始数据是:[21,13,96,23,66,58,64,48,6,14]
排序后数据:[6,58,21,48,64,23,66,14,96,13]
(1)请在画线处填入合适的代码。
(2)将加框处的代码修改为“(n－1)//2＋1”,程序功能__________(填“会”或“不会”)发生改变。
不会
import random
n=10
a=[random.randint(1,99)for i in range(n)]
print("原始数据是:",a)
for i in range(0, (n－1)//2 ):
　　k=1
　　for j in range(0,n－i*2－2):
　　　　if k*a[j]>k*a[j＋2]:
　　　　　　a[j], a[j＋2] = ①________________
　　　　②__________
print("排序后数据:",a)
a[j＋2], a[j]
k=－k
【解析】 本题考查冒泡排序算法的变形。(1)①根据代码可知,此处是将a[j]和a[j＋2]两个元素进行交换。②奇数位和偶数位升序和降序要实现交替进行,不等式变向,需要通过k实现,因此k的值必须在1和－1两者之间交替变化,因此k=－k。(2)冒泡排序中,外循环增加一次,不影响程序的功能。
14. 双向冒泡排序:经典冒泡排序是单向的,始终从第一个(或最后一个)元素开始扫描。小王对冒泡排序进行了改进,从两端进行扫描,首先从数组的左端到右端进行扫描,把最大的数往后交换(以升序为例),再从右端往左端扫描,把最小的数往前交换,多次扫描后,得到一个有序的序列。于是定义了left和right两个指针,每一遍排序,left右移一位,right左移一位。一趟排序,将最大值下沉到最后一位,最小值上浮到最前一位,最终使整个数组有序。运行界面如图所示,实现上述功能的Python代码如下。请回答下列问题:
排序前数据:[73,21,98,49,96,82,99,14,48,92]
排序后数据:[14,21,48,49,73,82,92,96,98,99]
(1)请在画线处填入合适的代码。
(2)加框处代码有错误,请改正。
import random
n = 10
a = [random.randint(10,99)for i in range(n)]
print("排序前数据:",a)
left,right = 0,n－1
while left　for j in range(①_______________):
　　if a[j]>a[j＋1]:
　　　 a[j],a[j＋1]=a[j＋1],a[j]
　right－=1
　for j in range(②__________________):
　　if a[j]>a[j－1] :
　　　 a[j],a[j－1]=a[j－1],a[j]
　③______________
print("排序后数据:",a)
【答案】 a[j]left, right
right,left,－1
left＋=1
【解析】 本题考查双向冒泡排序。(1)left和right分别扫描的左右边界,有序区位于左右两端,每次扫描后,无序区边界缩小,因此left每次加1,而right每次减1。(2)升序排序,故代码为a[j]15. 某大学演唱会以评委投票方式评选最优秀的歌曲,每张选票仅填一个作品编号,得票数过半的作品获“最佳作品奖”。小李同学和小王同学负责收集全部选票,其中小李同学已将收集的选票按作品编号升序排序,小王同学收集的选票未排序。现要求将全部选票按作品编号进行非降序排序,找出获“最佳作品奖”的作品编号。编写程序,实现上述功能。运行程序,在数组a中存储全部选票,小李收集的选票在前,小王收集的选票在后。先按作品编号对全部选票进行非降序排序,最后找出“最佳作品奖”的作品编号并输出显示。运行结果如图所示,请回答下列问题:
(1)实现上述功能的部分程序如下,请在画线处填入合适的代码。
(2)程序中加框处的代码有错误,请改正。
【答案】 (0,n//2＋1)
# m为一常数
#将n张选票的作品编号存入列表a,a[0]~a[m－1]、a[m]~a[n－1]分别为小李同学和小王同学#收集选票的作品编号,代码略
n=len(a)
c=[""]*n
for i in range(n,m,－1):
　　for j in ①_____________________________________________________:
　　　　if a[j＋1] < a[j]:
　　　　　　a[j],a[j＋1] = a[j＋1],a[j]
i=0
②__________
for k in range(0,n):
　　if j > n－1 or ③___________________________________________:
　　　　c[k] = a[i]; i = i ＋ 1
　　else:
　　　　c[k] = a[j]; j = j ＋ 1
for i in range(0,n//2):
　　if c[i] == c[i ＋ n // 2]:
　　　　print(c[i])
　　　　break
range (m,n－2)或 range (m,i－1) 或 range (n－2,m－1,－1)
j=m
i【解析】 本题考查冒泡排序及归并排序知识。(1)①考虑到冒泡排序的边界条件及外循环的范围,答案如上。②由代码可知,j是小王同学的数据范围,故j=m。③把列表a中两段合并成有序结果,利用双指针策略有序放置于列表c中,使用了归并排序的策略。初始时i指向第一段数据的起始位置1,j指向第二段数据的起始位置m。可知,i的取值范围为1~m－1,j的取值范围为m~n－1,当我们控制两个指针移动时,需要注意i、j的取值区间,避免越界。因此答案是i16. 小王为了挑选出符合自己要求的相机,从某电商平台上获取了相关产品的一系列数据,数据格式如图所示。在挑选过程中,他的第一考虑要素是价格实惠,而对于价格相同的,他的次要考虑因素是销售量。现请你帮助他实现下列排序和筛选过程:按照商品价格升序排序,商品价格相同的,根据销售量进行降序排序,在排序的过程中对数据进行整理,剔除重复数据。
(1)根据题中的算法描述,结合程序代码分析,将商品价格和销售量按题目要求采用的算
法是___________(填“选择排序”或“冒泡排序”),其时间复杂度为__________(单选,填字母)。
A. O(n)/ B. O(log2n)/
C. O(n2))
冒泡排序
C
(2)请在画线处填入合适的代码。
import csv
a=[]
f=open("camera.csv","r")
reader=csv.reader(f)
for item in reader:　#读取文件添加到列表a中
　　a.append(item)
f.close()
n=len(a)
for i in range(1,n):　#将列表a中的“销售量”和“价格”转换为整型数据
　　a[i][2]=int(a[i][2])
　　a[i][3]=int(a[i][3])
i=1; m=n－1
while i　for j in range(①_____________):
　　　if ②______________________________________________________________:
　　　　　a[j],a[j－1]=a[j－1],a[j]
　　　elif a[j]==a[j－1]:
　　　　　③______________
　　　　　m－=1
　i＋=1
for i in range (m＋1):
　　print (a[i])
m, i, －1
a[j][3]a[j－1][2]
a[j]=a[m]
(3)按照上述要求排序后,小王希望筛选出每档售价的销售量的前两名的产品数据。加框处的代码有错误,请改正。
def sx(x,y):
　　if　y－x＋1>2 :　　　　#①
　　　　print(a[x])
　　　　print(a[x＋1])
　　else:
　　　　print(a[x])
i=0
j=0
for i in range(1,m):
　　if a[i][3]==a[i－1][3] :　　#②
　　　　sx(j,i－1)
　　　　j=i
sx(j,i－1)
【答案】 ①y－x＋1>=2或y－x>=1　②a[j][3]==a[i－1][3]
【解析】 本题考查多条件冒泡排序和程序实现过程。(1)从排序代码可知,比较和交换的是相邻的元素,属于冒泡排序算法。根据代码双重循环可知,其时间复杂度为O(n2),C正确。(2)①根据代码“a[j],a[j－1]=a[j－1],a[j]”可知,该程序实现从后往前的冒泡排序,所以①处填入的代码为m, i, －1。②排序的首要关键字为商品价格升序,次要关键字为销售量降序,所以此处填入的代码为a[j][3]a[j－1][2]。③该部分实现去重功能,当a[j]=a[j－1]时,用当前队尾元素a[m]覆盖a[j],以实现删除a[j]的功能,同时更新对尾指针m。(3)①题目要求筛选出“每档售价销售量前两名”,所以应填入的代码为y－x＋1>=2,当前代码实现的功能是当每档售价销售量存在3个及以上时才进行输出,不符合题目要求。②由后面的代码可知,应该是j和i－1的两个价格进行比较。

展开更多......

收起↑