资源简介

5.2　迭代算法思想——冒泡排序
学习目标　
1.了解冒泡排序本质是相邻两个数进行比较和交换,让较大的数“下沉(上冒)”,较小的数“上冒(下沉)”的一种排序技术。
2.写出每趟排序的结果,掌握每趟的比较次数、每趟的排序区间和每趟排序实现的功能。
3.列出排序序列中的逆序对,掌握总共需要的交换次数。
4.外循环实现排序的趟数,内循环决定排序的方向和区间,比较条件决定排序的方式。
5.根据外循环变量i,画出待排序区间,在待排序区间的两端写出4个比较的位置,从而确定内循环的初始和结束位置。
　　　　　　 　　　　　 　　　　　
(2023年6月浙江省选考)列表s包含8个互不相等的元素,即s[0],s[1],s[2],……,s[7],有如下Python程序段:
n=8
for i in range(1,n-1):
　　for j in range(1,n-i-1):
　　　　if s[j]>s[j-1]:
　　　　　　s[j],s[j-1]=s[j-1],s[j]
该程序段实现的是(　　)
A.s[0]到s[5]的降序排列
B.s[1]到s[6]的降序排列
C.s[1]到s[7]的升序排列
D.s[2]到s[6]的升序排列
答案　A
解析　本题考查冒泡排序算法思想。外循环变量i控制排序趟数。内循环变量j取值范围是[1,5],条件s[j]>s[j-1]表示当后一个数大于前一个数时要发生交换,实现降序排列。参加排序元素仅s[0]~s[5]。
　　冒泡排序的特征是相邻两个对象进行比较和交换,可以从前往后冒泡,实现后面数据先有序,也可以从后往前冒泡,实现前面数据先有序。当某趟排序过程中没有发生数据交换,表示整个序列数据有序,可以提前结束排序。冒泡排序可以用双重循环来实现,其算法复杂度为O(n2),外循环表示循环的趟数,内循环实现第i趟排序的方向和区间,比较语句实现了升降序的方式。
例1 列表lst中共有n个整数,若下列程序段实现将数组元素lst[st]至lst[ed]升序排列,则划线处的代码为(　　)
for i in range(st,ed):
　　for j in range(st,　　　　):
　　　　if lst[j]>lst[j+1]:
　　　　　　lst[j],lst[j+1]=lst[j+1],lst[j]
A.n-i B.ed-i
C.ed+st-i D.st+ed
思维点拨
明考向 本题考查冒泡排序的算法实现。从前往后冒泡排序,后面的数据先有序,每趟待排序区右端点将则缩小
精 点 拨 A 将i的初值代入,最终比较位置为n-1和n,越界
B 当j为ed-st-1时,最终比较位置为ed-st-1和ed-st,只有当st为0时符合要求
C 第一趟排序时,变量i的值为st,有序的索引位置为ed,若j要取到ed-1,则终值须为ed+st-i-1,由于range是左闭右开的区间,因此终值为ed+st-i
D 随着i的增大,排序区间会变化,但该项中没有体现终值的变化
答案　C
变式1 列表s包含8个互不相等的元素,即s[0],s[1],s[2],...s[7],有如下Python程序段:
n=8
for i in range(1,5):
　　for j in range(n-2,i,-1):
　　　　if s[j]　　　　　　s[j],s[j+1]=s[j+1],s[j]
该程序段实现的是(　　)
A.s[0]到s[3]的升序排列
B.s[4]到s[7]的升序排列
C.s[2]到s[5]的降序排列
D.s[1]到s[4]的降序排列
答案　C
解析　本题考查冒泡排序算法思想。从后往前冒泡,前面的数据先有序,有序区间的左端点是i+1,比较对象是s[j]例2 有如下Python程序段:
for i in range(0,len(a)-1,2):
　　if i>0 and a[i]　　　　a[i],a[i-1]=a[i-1],a[i]
　　if a[i]　　　　a[i],a[i+1]=a[i+1],a[i]
列表a有6个元素,运行该程序段后,a可能的值是(　　)
A.[2,9,8,6,9,3] B.[9,9,8,6,3,2]
C.[9,3,6,2,8,9] D.[6,3,9,2,9,8]
思维点拨
明考向 本题考查冒泡排序算法的变式
精点拨 变量i的值依次为0,2,4,若i为0,只执行第二个选择结构,因此a[0]必定大于等于a[1]。当变量i的值为2,4时,先升序再降序,即a[i]的值大于其前后两个数据
答案　D
变式2 对一组数进行错位排序,即从前往后依次是最小的,最大的,第二小的,第二大的……以此类推。如“77,52,32,82,43,21,90,28,46”经过排序后,结果为“21,90,28,82,32,77,43,52,46”。实现该功能的Python程序段如下:
#随机生成n个2位的正整数,存储于a列表,代码略
tmp=1
for i in range(n-1):
　　for j in range(n-1,①　　　　　　,-1):
　　　　if ②　　　　　　:
　　　　　　a[j],a[j-1]=a[j-1],a[j]
　　tmp=-tmp
则划线处应填入的代码为(　　)
A.①i+1　　②tmp*(a[j]-a[j-1])<0
B.①i　　　②tmp*(a[j]-a[j-1])<0
C.①i　　　②tmp*(a[j]-a[j-1])>0
D.①i+1　　②tmp*(a[j]-a[j-1])>0
答案　B
解析　本题考查冒泡排序算法的变式。实现从后往前冒泡排序,前面的数据先有序,第1趟排序时,i的值为0,有序的索引位置是0,比较对象是a[j]和a[j-1],即a[1]和a[0],j取值为1,但在rangk函数中,还需加是步长-1,因此排除选项A和D。第1趟是降序,此时tmp的值为1,因此当a[j]-a[j-1]小于0时,需交换。
1.采用冒泡排序算法对数据序列“22,35,43,56,19,8”完成升序排序,需要交换的次数为(　　)
A.9次 B.12次
C.15次 D.21次
答案　A
解析　找出各个逆序对。比22小且在右侧的数有19和8共2个。同理比35、43和56小且在右侧的数各有2个。比19小的数有1个。
2.某升序冒泡排序算法的Python程序段如下:
#生成n个随机整数,依次存入数组a,代码略
for i in range(1,n):
　　for j in range(　　　　　　):
　　　　if a[j]>a[j+1]:
　　　　　　a[j],a[j+1]=a[j+1],a[j]
为实现程序功能,划线处可填入的代码是(　　)
A.n-i-1 B.n-i
C.n-i+1 D.n
答案　B
解析　冒泡排序的特征是一端固定,相邻两个数据两两比较和交换,使得另一端的数据不断地有序。若步长为正值,初始值为0,终值为x-i,当i的值为1时,终值j将取到n-2,若要取到n-2,则x-i的值必须为n-1,因此x的值为n。
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]的升序排列
答案　C
解析　本题考查冒泡排序的算法思想。一共排了n-1趟,从内循环来看,实现从后往前冒泡排序。当i为0时,终值能取到2。第1次为s[7]和s[6]比较,最后一次为s[2]和s[1]比较,因此实现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.③⑥
答案　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,-1),若i的范围是[1,n-1],则待排序的右端点为[i-1],则j的range为(n-1,i+1,-1)。
5.有如下Python程序段:
a=[6,-9,-6,8,7,4,-3,-1]
n=len(a)
for i in range(n-1):
　　for j in range(n-1,i,-1):
　　　　if a[j]>a[j-1]:
　　　　　　a[j],a[j-1]=a[j-1],a[j]
　　if a[i]<0:
　　　　break
执行该程序段后,变量i的值为(　　)
A.3 B.4
C.5 D.6
答案　B
解析　程序的功能是找出大于等于0的数据并按降序排列。
6.有以下Python程序段:
s=[5,9,8,6,7,1,4,2]
n=len(s)
for i in range(1,n//2):
　　for j in range(　　　　):
　　　　if s[j]　　　　　　s[j],s[j-1]=s[j-1],s[j]
执行该程序段后实现数据部分有序,结果s的值为[5,9,1,6,7,8,4,2],则划线处的代码是(　　)
A.n-3,i+1,-1 B.i+1,n-i-1
C.n-1,i-1,-1 D.2,n-i+1
答案　A
解析　只需对a[2]到a[5]范围进行排序,排除选项C。range的第1个参数为定值,因此排除选项B。若从前往后冒泡,被比较的是a[j]与a[j-1],当i的值为1时,n-i+1的值为8,导致后面的数据也会参加排序,排除选项D。若从后往前冒泡,每次总是从n-3开始,第1趟最后1次比较的对象为s[3]和s[2],即j的值为3,因此第2个参数为i+1。
7.已知列表a中存储了n个整型数据,小孙设计了一个算法可以删除列表a中重复的数据,并将去重后的数据升序排序。实现该功能的程序段如下,方框中应填入的正确代码为(　　)
bottom=len(a);i=0
while i　　flag=False;j=bottom-2
　　while j>=i:
　　　　if a[j+1]　　　　　　a[j],a[j+1]=a[j+1],a[j]
　　　　　　flag=True
　　　　elif a[j]==a[j+1]:
　　　　　　　　　　　　
　　　　　　flag=True
　　　　j-=1
　　if not flag:
　　　　break
　　i+=1
A.a[j],a[bottom-1]=a[bottom-1],a[j]
bottom-=1
B.a[j],a[bottom-1]=a[bottom-1],a[j];j+=1
C.a[j+1],a[bottom-1]=a[bottom-1],a[j+1]
bottom-=1
D.a[j+1],a[bottom-1]=a[bottom-1],a[j+1]
j+=1
答案　C
解析　bottom表示没有重复数的个数,第2个while语句的功能是对位置i后面的数据进行一轮升序排列,把最大的数据交换到bottom-1的位置,若条件a[j]==a[j+1]成立,将a[j+1]交换到bottom-1的位置,不重复的个数bottom将减少一个。
8.某Python程序如下:
from random import randint
a=[9,12,1,4,7,8]
n=randint(1,len(a)-1)
for i in range(n):
　　for j in range(len(a)-1,i,-1):
　　　　if a[j]%3>=a[j-1]%3:
　　　　　　a[j],a[j-1]=a[j-1],a[j]
print(a)
程序运行后,输出结果不可能的是(　　)
A.[12,9,8,7,1,4] B.[8,9,12,1,4,7]
C.[8,7,4,1,12,9] D.[8,7,4,9,12,1]
答案　A
解析　本题考查冒泡排序算法的变式。外循环决定排序的趟数,程序实现从后往前冒泡排序,比较的是除3的余数,且相等时还要交换。A选项各个元素除3后的余数依次为[0,0,2,1,1,1]不是降序排列的。B选项除3后的余数依次为[2,0,0,1,1,1],只排了一趟。C选项除3后的余数依次为[2,1,1,1,0,0],所有数据都有序,n的值为5。D选项除3后的余数依次为[2,1,1,0,0,1],3个数据都有序,n的值为3。
9.使用列表a和列表b分别存储学生的总分和考号,已知考号为b[i]的学生的总分为a[i],使用Python编程实现如下功能:将成绩数据“按总分降序排序、总分相同按学号升序排序”,代码如下。
n=len(a)
for i in range(1,n):
　　for j in range(0,n-i):
　　　　if (1)　　 or (2)　　 and (3)　　:
　　　　　　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.①⑤④
答案　C
解析　本题考查双关键字冒泡排序。程序实现从前向后冒泡,第一关键字③:第j个比 j+1个成绩小则交换。第二关键字②⑥:第j个和第j+1个成绩相同且第j个考号比第j+1个大则交换。
10.有如下Python程序段:
s="ccbbac"
a=[i for i in range(6)]
for i in range(5):
　　for j in range(5-i):
　　　　if s[a[j]]>s[a[j+1]]:
　　　　　　a[j],a[j+1]=a[j+1],a[j]
print(a)
运行该程序段输出的结果为(　　)
A.[4,3,2,5,1,0] B.[4,5,3,2,1,0]
C.[4,2,3,0,1,5] D.[4,3,2,5,0,1]
答案　C
解析　本题考查索引排序。数组a存储的0-5的索引位置,程序实现从前往后冒泡,当条件s[a[j]]>s[a[j+1]]成立时交换,实现升序排列,因此排序后的结果是abbccc,找到这些字母的索引位置。
11.列表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]分别升序排序
答案　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]依次比较和交换,形成有序序列。
12.有如下程序段:
#随机生成5个正整数并存入列表s中,代码略
n=len(s)
y=[i for i in range(n)]　#生成序列0 ~ n-1
for i in range(n-1):
　　for j in range(n-i-1):
　　　　if s[y[j]]>=s[y [j+1]]:
　　　　　　y [j],y [j+1]=y [j+1],y[j]
执行上述程序后,运行的结果为[2,1,0,4,3],列表s中各元素值可能的是(　　)
A.[3,2,1,5,4] B.[4,2,1,5,3]
C.[5,2,1,3,4] D.[3,2,5,1,4]
答案　A
解析　考查冒泡排序及其变式。函数通过冒泡排序的方式对y进行调整,使得y中的每个元素代表s中按升序排列的元素在原始列表中的位置。推理可得A选项对[3,2,1,5,4]的排序结果为[2,1,0,4,3]。
13.列表lst中共有n个整数,若下列程序段实现将数组元素lst[st]至lst[ed]升序排列,则划线处的代码为(　　)
while st!=ed:
　　last=　　　　　
　　for j in range(st,ed):
　　　　if m[j]>m[j+1]:
　　　　　　m[j],m[j+1]=m[j+1],m[j]
　　　　　　last=j
　　ed=last
A.st B.st+1
C.ed D.ed+1
答案　A
解析　该程序实现从前往后冒泡,后面的数据先有序,ed表示无序区间的右边界,last记录了无序区间最后一个位置,即排序的右边界,当右边界与左边界相等时,这个无序区间只剩下一个数据,该数据肯定是有序的。
1.采用冒泡排序算法对数据序列“3,9,7,0,8,5”完成升序排序,则需要交换的次数为(　　)
A.9次 B.8次
C.6次 D.5次
答案　B
解析　本题考查冒泡排序的算法思想。数列中存在3和0(1对)、9和7,0,8,5(4对),7和0,5(2对),8和5(1对),共8对逆序对,需交换8次。
2.互不相等的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]的升序排列
答案　C
解析　本题考查冒泡排序算法思想。分析冒泡排序内循环的代码,是从左(前)向右(后)冒泡、降序。外循环只进行了5次,所以只有最后5个数(s[5]到s[9])是有序的。
3.小杨编写了一个Python程序,部分代码如下:
#输入数据,存储到列表d中,代码略
for i in range(1,len(d)):
　　for j in range(i,len(d)):
　　　　if d[j]　　　　　　d[j],d[j-1]=d[j-1],d[j]
执行该程序段,输入下列数据,列表d中元素未按升序排列的是(　　)
A.1,2,4,3,5 B.4,1,2,3,5
C.5,2,1,4,3 D.5,1,2,3,4
答案　C
解析　程序错误之处在内层循环range范围,应该为range(1,len(d)-i+1)。A、B、D选项在第一轮排序后,数据均有序,所以无法测试出代码中存在的问题,C选项运行结果为2,1,3,4,5,数据无序,可以测试出错误。
4.执行下列Python程序段后,c[1]的值是(　　)
a=[12,5,24,6,9,18]
n=len(a);c=[0]*n
for i in range(1,n):
　　for j in range(n-1,i-1,-1):
　　　　if a[j]>a[j-1]:
　　　　　　a[j],a[j-1]=a[j-1],a[j]
　　　　　　c[i]+=1
A.1 B.2
C.3 D.4
答案　D
解析　外循环控制排序趟数,因此c[i]表示第i趟交换的次数。第1趟元素18与9和6交换,元素24与5和12交换。
5.有如下Python程序:
a=[""]*10;s="51267878172012"
n=0;a[0]=s[0]
for i in range(1,len(s)):
　　if s[i]<=s[i-1]:
　　　　n+=1
　　a[n]=a[n]+s[i]
for i in range(n):
　　for j in range(n,i,-1):
　　　　if len(a[j])>len(a[j-1]):
　　　　　　a[j],a[j-1]=a[j-1],a[j]
执行该程序段,a[2]的值是(　　)
A."2" B."78"
C."012" D."5"
答案　B
解析　当条件s[i]<=s[i-1]成立时,n的值增加1,将依次将该位置开始的字符串连接入a[n],程序的功能是将字符串s划分成若干个升序段,再按升序段的长度进行降序排列。
6.有如下Python程序段:
L=[21,12,13,17,16,15,20,28,11]
def shengxu(a,b):
　　for i in range(0,b-a):
　　　　for j in range(　　　　　　):
　　　　　　if L[j]>L[j+1]:
　　　　　　　　L[j],L[j+1]=L[j+1],L[j]
shengxu(3,7)
若要实现列表L中L[a]到L[b]之间的数升序排列(不改变其余元素的位置),划线处的代码应为(　　)
A.i,b B.0,b-i
C.a,b-i D.b-1,a-i-1,-1
答案　C
解析　外循环控制排序的次数,也与排序的区间位置有关。冒泡排序必须是一端固定,另一端随着排序的过程将不断地缩短。若从前往后冒泡,则排序的初值必须为a,第一趟排序的区间是最长的,此时i的值为0,最后位置为b,而j+1到过b时,j的值为b-1,若要取到b-1,则终值必须为b,结合i的值,终值为b-i。
7.小明编写程序实现数据排序功能,部分程序如下:
n=len(d)
for i in range(1,n):
　　for j in range(n-i-1,-1,-1):
　　　　if d[j]> d [j+ 1]:
　　　　　　d[j],d[j+1]=d[j+1],d[j]
print(d)
此程序存在问题,不适合作为测试数据的是(　　)
A.d=[9,6,5,8] B.d=[9,8,6,5]
C.d=[8,9,5,6] D.d=[6,5,9,8]
答案　D
解析　实现从后往前冒泡升序排列,前面的数据先有序,但右端没有固定,每趟都在缩减,因此有些数据是排不到的。AB选项排序后均为5,6,9,8,无序,可以检测。C选项排序后为5,8,9,6,无序,可以检测。D选项排序为升序,与正确算法结果相同,无法检测。
8.有如下Python程序段:
s=[2,3,8,7,5]
for i in range(len(s)-1):
　　for j in range(len(s)-1,i,-1):
　　　　if s[j]　　　　　　s[j],s[j-1]=s[j-1],s[j]
执行该程序段,加框处语句被执行的次数是(　　)
A.3 B.6
C.8 D.10
答案　A
解析　加框处语句表示交换次数,从条件s[j]9.有如下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]
答案　A
解析　程序的功能是从后往前冒泡,排了3趟,实现前3个数据有序。
10.某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.每一遍加工中,最小的元素“上浮”
答案　D
解析　本题考查排序算法。当条件s[j]11.某排序算法的Python程序段如下:
#读取n个整数,依次存入a[1]到a[n]中,代码略
for i in range(1,n-1):
　　for j in range(n,i+1,-1):
　　　　if a[j]>a[j-1]:
　　　　　　a[j],a[j-1]=a[j-1],a[j-1]
执行上述程序段,下列说法正确的是(　　)
A.交换过位置的数据,可能会再回到其初始位置
B.执行完成后,数组元素a[1]到a[n]从小到大排列
C.若n为6,整个排序过程总的比较次数是30
D.整个排序过程总的交换次数至少为1
答案　A
解析　考查冒泡排序算法思想。算法实现从左往右降序排列。A选项例如某个数后面有2个数,且一个数大他小,一个数比他大,当大的数往前交换后,第2次比他小的数又换回来了。总的比较次数为n*(n-1)/2=15。D选项如果原数据已经有序了,不会发生交换。
12.下列代码采用冒泡排序对a列表中的n个数据升序排序,则①②两处不可用的选项是(　　)
for i in range(①　　　　　　):
　　for j in range(②　　　　　　):
　　　　if a[j] 　　　　　　a[i],a[j-1]=a[j-1],a[j]
A.①1,n　　　　②n-1,i-1,-1
B.①n,1,-1　　　②1,i-1
C.①1,n　　　　②1,n-i+1
D.①0,n-1　　　②n-1,i,-1
答案　B
解析　本题考查冒泡排序的算法思想。当i=n时,j in range(1,n-1),当j为最后一个值n-2时(range右边为开区间,n-1取不到),a[n-2]与a[n-3]比较大小,缺少a[n-1]与a[n-2]比较大小,不能完成所有n个数据的升序排序。
13.如下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']
答案　C
解析　本题考查冒泡排序的变形。根据if条件s[j]=='a' and s[j-1]!='a'可以看出,取字符串s中字符时,若当前字符 s[j]为'a'但 s[j-1]不为'a',交换 s[j-1]与s[j]的位置。因此,该程序段的功能为将字符'a'前移,其他字符保持原位置不变,交换后的结果为['a','a','a','b','c','b','c']。
14.数组a包含10个不同的元素,即a[0],a[1],…a[9],有如下Python程序段:
n=len(a)
for i in range(0,n,2):
　　for j in range(n-2,i+1,-2):
　　　　if a[j]　　　　　　a[j],a[j-2]=a[j-2],a[j]
该程序段实现的功能是(　　)
A.仅对偶位元素a[0],a[2],…a[8]升序排列
B.仅对奇位元素a[1],a[3],…a[9]升序排列
C.偶位元素 a[0],a[2],…a[8]升序,奇位元素降序排列
D.偶位元素 a[0],a[2],…a[8]降序,奇位元素升序排列
答案　A
解析　本题考查冒泡排序的算法思想。内循环j,初值为n-2=8,步长为-2,因此j的值为8至2的偶数。比较对象也是这些位置中的数,因此仅实现这些数的升序排列。
15.有如下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]
答案　C
解析　本题考查冒泡排序算法思想。外循环i表示排序趟数,决定了有序元素的个数,内循环j决定了排序的区间和方向。从后往前冒泡,前面的数据先有序,从条件a[j] >a[j-1]来看,实现降序排列。A选项至少排4趟,B选项只排2趟,D选项未排序,C选项第1趟排序过程中,17和19要交换位置。
16.有如下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
答案　C
解析　本题考查双关键字排序。数组a中数据升序,当a数组中值相等时,以b数组对应的值为依据,即b数组中数据降序。数组a中最小有2个2,b数组分别对应为7和4,b中7排在前面。
17.有如下Python程序段:
a=list(map(int,input().split()))　#将输入的数据转换成列表
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]
答案　C
解析　本题考查程序冒泡排序。从右往左(从后往前)进行了2趟排序,排序比较是元素%3后,最前面的2个元素除3余数一定是所有元素中最大的。
18.有如下Python程序段:
m=3
lst=[7,3,4,3,1,6,3]
for i in range(len(lst)-1):
　　for j in range(len(lst)-1,i,-1):
　　　　if lst[j]　　　　　　lst[j],lst[j-1]=lst[j-1],lst[j]
　　if i>=m and lst[i]!=lst[i-1]:
　　　　break
执行该程序段,加框处语句被执行的次数是(　　)
A.3 B.4
C.5 D.6
答案　C
解析　本题考查冒泡排序的算法思想。提前结束排序的条件必须满足两个,其一大于等于m,其二是最后的数据与前面的数据不能相等。如要排出前3名,且有很多并列第3名(排好序[1,3,3,3,4,7,6],需要找到4即最后一个不符合条件的数据,才能终止循环。
19.某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]
答案　C
解析　本题考查冒泡排序,当a[i]是偶数时排序,因此3不参与排序,第一趟结果为[3,8,6,2,3],再依次进行排序。
20.有如下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
答案　D
解析　本题考查冒泡排序的算法思想。比较对象是相邻两个数,比较条件f[i]21.数组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.奇数位元素降序,偶数位元素升序排列
答案　A
解析　本题考查冒泡排序算法思想。外循环决定排序趟数,内循环决定排序方向和区间,内循环初值为n-2,步长为负2,因此仅对奇数位置排序。
22.数组元素s[0]~s[5]为随机正整数,执行如下Python程序段后,s[0]~s[5]的值可能为(　　)
for i in range(5):
　　for j in range(5,i,-1):
　　　　if s[j] % 2　　　　　　s[j],s[j-1]=s[j-1],s[j]
A.6,2,1,3,7,7 B.1,3,5,7,9,2
C.10,8,6,3,2,1 D.1,2,5,5,6,7
答案　A
解析　程序的功能是按每个元素除2后的余数进行升序排列。A选项实际比较的值为0,0,1,1,1,1。B选项实际比较的值为1,1,1,1,1,0。C选项实际比较的值为0,0,0,1,0,1。D选项实际比较的值为1,0,1,1,0,1。
23.有如下Python程序段:
d=[3,9,2,0,2,4];n=len(d)
s=[0,1,2,3,4,5]
for i in range(n-1):
　　for j in range(n-1,i,-1):
　　　　if d[s[j]]　　　　　　s[j],s[j-1]=s[j-1],s[j]
print(s)
执行该程序段后,输出的结果是(　　)
A.[3,4,2,0,5,1] B.[3,2,4,0,5,1]
C.[1,5,0,4,2,3] D.[1,5,0,2,4,3]
答案　B
解析　数组s存储数组d中各元素的索引位置,d数组数据并未发生交换,从比较条件来看,程序实现升序排列,因此最小数据的索引位置是3,最大数据的索引位置是1,当两个数据相等时,按原来的位置排列。
24.有实现冒泡排序的python程序段:
a=[4,6,3,9,1,2]
n=len(a);i=n-1
while i>=1:
　　k=0
　　for j in range(i):
　　　　if a[j]　　　　　　a[j],a[j+1]=a[j+1],a[j]
　　　　　　k=j
　　　　　　　
则划线处的语句应为(　　)
A.i=k-1 B.i=k
C.i=k+1 D.i=j
答案　B
解析　本题考查冒泡排序的算法思想。从内循环来看,实现从前往后冒泡排序,后面的数据先有序,用变量k记录最右边有序的数据位置j+1,则有序区间为[j+1,n-1],待排序区间为[0,j],用变量k指向j,下趟排序只要j+1指向k就可以终止本趟排序。第1趟结果为[6,4,9,3,2,1],下趟排序终点为4;第2趟结果为[6,9,4,3,2,1],下趟排序终点为1;第3趟结果为[9,6,4,3,2,1],下趟排序终点为0。
25.有如下Python程序段:
d=[12,8,6,3,8,10]
i=0;q=0;flag=False
while i　　flag=True
　　for j in range(len(d)-1,q,-1):
　　　　if d[j]>d[j-1]:
　　　　　　d[j],d[j-1]=d[j-1],d[j]
　　　　　　q=j
　　　　　　flag=False
　　i=i+1
程序运行后,加框处语句执行次数为(　　)
A.15 B.12
C.9 D.8
答案　C
解析　程序实现从后往前降序排序,q记录有序数据的个数,第1趟比较了5次,第2趟比较了3次,d的值为[12,10,8,8,6,3],q的值为4,排序后,数据有序,第3趟只比较1次,数据无交换,结束排序,比较次数分别为5+3+1=9。5.2　迭代算法思想——冒泡排序
学习目标　
1.了解冒泡排序本质是相邻两个数进行比较和交换,让较大的数“下沉(上冒)”,较小的数“上冒(下沉)”的一种排序技术。
2.写出每趟排序的结果,掌握每趟的比较次数、每趟的排序区间和每趟排序实现的功能。
3.列出排序序列中的逆序对,掌握总共需要的交换次数。
4.外循环实现排序的趟数,内循环决定排序的方向和区间,比较条件决定排序的方式。
5.根据外循环变量i,画出待排序区间,在待排序区间的两端写出4个比较的位置,从而确定内循环的初始和结束位置。
　　　　　　 　　　　　 　　　　　
(2023年6月浙江省选考)列表s包含8个互不相等的元素,即s[0],s[1],s[2],……,s[7],有如下Python程序段:
n=8
for i in range(1,n-1):
　　for j in range(1,n-i-1):
　　　　if s[j]>s[j-1]:
　　　　　　s[j],s[j-1]=s[j-1],s[j]
该程序段实现的是(　　)
A.s[0]到s[5]的降序排列
B.s[1]到s[6]的降序排列
C.s[1]到s[7]的升序排列
D.s[2]到s[6]的升序排列
　　冒泡排序的特征是相邻两个对象进行比较和交换,可以从前往后冒泡,实现后面数据先有序,也可以从后往前冒泡,实现前面数据先有序。当某趟排序过程中没有发生数据交换,表示整个序列数据有序,可以提前结束排序。冒泡排序可以用双重循环来实现,其算法复杂度为O(n2),外循环表示循环的趟数,内循环实现第i趟排序的方向和区间,比较语句实现了升降序的方式。
例1 列表lst中共有n个整数,若下列程序段实现将数组元素lst[st]至lst[ed]升序排列,则划线处的代码为(　　)
for i in range(st,ed):
　　for j in range(st,　　　　):
　　　　if lst[j]>lst[j+1]:
　　　　　　lst[j],lst[j+1]=lst[j+1],lst[j]
A.n-i B.ed-i
C.ed+st-i D.st+ed
变式1 列表s包含8个互不相等的元素,即s[0],s[1],s[2],...s[7],有如下Python程序段:
n=8
for i in range(1,5):
　　for j in range(n-2,i,-1):
　　　　if s[j]　　　　　　s[j],s[j+1]=s[j+1],s[j]
该程序段实现的是(　　)
A.s[0]到s[3]的升序排列
B.s[4]到s[7]的升序排列
C.s[2]到s[5]的降序排列
D.s[1]到s[4]的降序排列
例2 有如下Python程序段:
for i in range(0,len(a)-1,2):
　　if i>0 and a[i]　　　　a[i],a[i-1]=a[i-1],a[i]
　　if a[i]　　　　a[i],a[i+1]=a[i+1],a[i]
列表a有6个元素,运行该程序段后,a可能的值是(　　)
A.[2,9,8,6,9,3] B.[9,9,8,6,3,2]
C.[9,3,6,2,8,9] D.[6,3,9,2,9,8]
变式2 对一组数进行错位排序,即从前往后依次是最小的,最大的,第二小的,第二大的……以此类推。如“77,52,32,82,43,21,90,28,46”经过排序后,结果为“21,90,28,82,32,77,43,52,46”。实现该功能的Python程序段如下:
#随机生成n个2位的正整数,存储于a列表,代码略
tmp=1
for i in range(n-1):
　　for j in range(n-1,①　　　　　　,-1):
　　　　if ②　　　　　　:
　　　　　　a[j],a[j-1]=a[j-1],a[j]
　　tmp=-tmp
则划线处应填入的代码为(　　)
A.①i+1　　②tmp*(a[j]-a[j-1])<0
B.①i　　　②tmp*(a[j]-a[j-1])<0
C.①i　　　②tmp*(a[j]-a[j-1])>0
D.①i+1　　②tmp*(a[j]-a[j-1])>0
1.采用冒泡排序算法对数据序列“22,35,43,56,19,8”完成升序排序,需要交换的次数为(　　)
A.9次 B.12次
C.15次 D.21次
2.某升序冒泡排序算法的Python程序段如下:
#生成n个随机整数,依次存入数组a,代码略
for i in range(1,n):
　　for j in range(　　　　　　):
　　　　if a[j]>a[j+1]:
　　　　　　a[j],a[j+1]=a[j+1],a[j]
为实现程序功能,划线处可填入的代码是(　　)
A.n-i-1 B.n-i
C.n-i+1 D.n
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.有如下Python程序段:
a=[6,-9,-6,8,7,4,-3,-1]
n=len(a)
for i in range(n-1):
　　for j in range(n-1,i,-1):
　　　　if a[j]>a[j-1]:
　　　　　　a[j],a[j-1]=a[j-1],a[j]
　　if a[i]<0:
　　　　break
执行该程序段后,变量i的值为(　　)
A.3 B.4
C.5 D.6
6.有以下Python程序段:
s=[5,9,8,6,7,1,4,2]
n=len(s)
for i in range(1,n//2):
　　for j in range(　　　　):
　　　　if s[j]　　　　　　s[j],s[j-1]=s[j-1],s[j]
执行该程序段后实现数据部分有序,结果s的值为[5,9,1,6,7,8,4,2],则划线处的代码是(　　)
A.n-3,i+1,-1 B.i+1,n-i-1
C.n-1,i-1,-1 D.2,n-i+1
7.已知列表a中存储了n个整型数据,小孙设计了一个算法可以删除列表a中重复的数据,并将去重后的数据升序排序。实现该功能的程序段如下,方框中应填入的正确代码为(　　)
bottom=len(a);i=0
while i　　flag=False;j=bottom-2
　　while j>=i:
　　　　if a[j+1]　　　　　　a[j],a[j+1]=a[j+1],a[j]
　　　　　　flag=True
　　　　elif a[j]==a[j+1]:
　　　　　　　　　　　　
　　　　　　flag=True
　　　　j-=1
　　if not flag:
　　　　break
　　i+=1
A.a[j],a[bottom-1]=a[bottom-1],a[j]
bottom-=1
B.a[j],a[bottom-1]=a[bottom-1],a[j];j+=1
C.a[j+1],a[bottom-1]=a[bottom-1],a[j+1]
bottom-=1
D.a[j+1],a[bottom-1]=a[bottom-1],a[j+1]
j+=1
8.某Python程序如下:
from random import randint
a=[9,12,1,4,7,8]
n=randint(1,len(a)-1)
for i in range(n):
　　for j in range(len(a)-1,i,-1):
　　　　if a[j]%3>=a[j-1]%3:
　　　　　　a[j],a[j-1]=a[j-1],a[j]
print(a)
程序运行后,输出结果不可能的是(　　)
A.[12,9,8,7,1,4] B.[8,9,12,1,4,7]
C.[8,7,4,1,12,9] D.[8,7,4,9,12,1]
9.使用列表a和列表b分别存储学生的总分和考号,已知考号为b[i]的学生的总分为a[i],使用Python编程实现如下功能:将成绩数据“按总分降序排序、总分相同按学号升序排序”,代码如下。
n=len(a)
for i in range(1,n):
　　for j in range(0,n-i):
　　　　if (1)　　 or (2)　　 and (3)　　:
　　　　　　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.①⑤④
10.有如下Python程序段:
s="ccbbac"
a=[i for i in range(6)]
for i in range(5):
　　for j in range(5-i):
　　　　if s[a[j]]>s[a[j+1]]:
　　　　　　a[j],a[j+1]=a[j+1],a[j]
print(a)
运行该程序段输出的结果为(　　)
A.[4,3,2,5,1,0] B.[4,5,3,2,1,0]
C.[4,2,3,0,1,5] D.[4,3,2,5,0,1]
11.列表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]分别升序排序
12.有如下程序段:
#随机生成5个正整数并存入列表s中,代码略
n=len(s)
y=[i for i in range(n)]　#生成序列0 ~ n-1
for i in range(n-1):
　　for j in range(n-i-1):
　　　　if s[y[j]]>=s[y [j+1]]:
　　　　　　y [j],y [j+1]=y [j+1],y[j]
执行上述程序后,运行的结果为[2,1,0,4,3],列表s中各元素值可能的是(　　)
A.[3,2,1,5,4] B.[4,2,1,5,3]
C.[5,2,1,3,4] D.[3,2,5,1,4]
13.列表lst中共有n个整数,若下列程序段实现将数组元素lst[st]至lst[ed]升序排列,则划线处的代码为(　　)
while st!=ed:
　　last=　　　　　
　　for j in range(st,ed):
　　　　if m[j]>m[j+1]:
　　　　　　m[j],m[j+1]=m[j+1],m[j]
　　　　　　last=j
　　ed=last
A.st B.st+1
C.ed D.ed+1
1.采用冒泡排序算法对数据序列“3,9,7,0,8,5”完成升序排序,则需要交换的次数为(　　)
A.9次 B.8次
C.6次 D.5次
2.互不相等的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]的升序排列
3.小杨编写了一个Python程序,部分代码如下:
#输入数据,存储到列表d中,代码略
for i in range(1,len(d)):
　　for j in range(i,len(d)):
　　　　if d[j]　　　　　　d[j],d[j-1]=d[j-1],d[j]
执行该程序段,输入下列数据,列表d中元素未按升序排列的是(　　)
A.1,2,4,3,5 B.4,1,2,3,5
C.5,2,1,4,3 D.5,1,2,3,4
4.执行下列Python程序段后,c[1]的值是(　　)
a=[12,5,24,6,9,18]
n=len(a);c=[0]*n
for i in range(1,n):
　　for j in range(n-1,i-1,-1):
　　　　if a[j]>a[j-1]:
　　　　　　a[j],a[j-1]=a[j-1],a[j]
　　　　　　c[i]+=1
A.1 B.2
C.3 D.4
5.有如下Python程序:
a=[""]*10;s="51267878172012"
n=0;a[0]=s[0]
for i in range(1,len(s)):
　　if s[i]<=s[i-1]:
　　　　n+=1
　　a[n]=a[n]+s[i]
for i in range(n):
　　for j in range(n,i,-1):
　　　　if len(a[j])>len(a[j-1]):
　　　　　　a[j],a[j-1]=a[j-1],a[j]
执行该程序段,a[2]的值是(　　)
A."2" B."78"
C."012" D."5"
6.有如下Python程序段:
L=[21,12,13,17,16,15,20,28,11]
def shengxu(a,b):
　　for i in range(0,b-a):
　　　　for j in range(　　　　　　):
　　　　　　if L[j]>L[j+1]:
　　　　　　　　L[j],L[j+1]=L[j+1],L[j]
shengxu(3,7)
若要实现列表L中L[a]到L[b]之间的数升序排列(不改变其余元素的位置),划线处的代码应为(　　)
A.i,b B.0,b-i
C.a,b-i D.b-1,a-i-1,-1
7.小明编写程序实现数据排序功能,部分程序如下:
n=len(d)
for i in range(1,n):
　　for j in range(n-i-1,-1,-1):
　　　　if d[j]> d [j+ 1]:
　　　　　　d[j],d[j+1]=d[j+1],d[j]
print(d)
此程序存在问题,不适合作为测试数据的是(　　)
A.d=[9,6,5,8] B.d=[9,8,6,5]
C.d=[8,9,5,6] D.d=[6,5,9,8]
8.有如下Python程序段:
s=[2,3,8,7,5]
for i in range(len(s)-1):
　　for j in range(len(s)-1,i,-1):
　　　　if s[j]　　　　　　s[j],s[j-1]=s[j-1],s[j]
执行该程序段,加框处语句被执行的次数是(　　)
A.3 B.6
C.8 D.10
9.有如下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]
10.某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.每一遍加工中,最小的元素“上浮”
11.某排序算法的Python程序段如下:
#读取n个整数,依次存入a[1]到a[n]中,代码略
for i in range(1,n-1):
　　for j in range(n,i+1,-1):
　　　　if a[j]>a[j-1]:
　　　　　　a[j],a[j-1]=a[j-1],a[j-1]
执行上述程序段,下列说法正确的是(　　)
A.交换过位置的数据,可能会再回到其初始位置
B.执行完成后,数组元素a[1]到a[n]从小到大排列
C.若n为6,整个排序过程总的比较次数是30
D.整个排序过程总的交换次数至少为1
12.下列代码采用冒泡排序对a列表中的n个数据升序排序,则①②两处不可用的选项是(　　)
for i in range(①　　　　　　):
　　for j in range(②　　　　　　):
　　　　if a[j] 　　　　　　a[i],a[j-1]=a[j-1],a[j]
A.①1,n　　　　②n-1,i-1,-1
B.①n,1,-1　　　②1,i-1
C.①1,n　　　　②1,n-i+1
D.①0,n-1　　　②n-1,i,-1
13.如下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']
14.数组a包含10个不同的元素,即a[0],a[1],…a[9],有如下Python程序段:
n=len(a)
for i in range(0,n,2):
　　for j in range(n-2,i+1,-2):
　　　　if a[j]　　　　　　a[j],a[j-2]=a[j-2],a[j]
该程序段实现的功能是(　　)
A.仅对偶位元素a[0],a[2],…a[8]升序排列
B.仅对奇位元素a[1],a[3],…a[9]升序排列
C.偶位元素 a[0],a[2],…a[8]升序,奇位元素降序排列
D.偶位元素 a[0],a[2],…a[8]降序,奇位元素升序排列
15.有如下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]
16.有如下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
17.有如下Python程序段:
a=list(map(int,input().split()))　#将输入的数据转换成列表
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]
18.有如下Python程序段:
m=3
lst=[7,3,4,3,1,6,3]
for i in range(len(lst)-1):
　　for j in range(len(lst)-1,i,-1):
　　　　if lst[j]　　　　　　lst[j],lst[j-1]=lst[j-1],lst[j]
　　if i>=m and lst[i]!=lst[i-1]:
　　　　break
执行该程序段,加框处语句被执行的次数是(　　)
A.3 B.4
C.5 D.6
19.某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]
20.有如下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
21.数组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.奇数位元素降序,偶数位元素升序排列
22.数组元素s[0]~s[5]为随机正整数,执行如下Python程序段后,s[0]~s[5]的值可能为(　　)
for i in range(5):
　　for j in range(5,i,-1):
　　　　if s[j] % 2　　　　　　s[j],s[j-1]=s[j-1],s[j]
A.6,2,1,3,7,7 B.1,3,5,7,9,2
C.10,8,6,3,2,1 D.1,2,5,5,6,7
23.有如下Python程序段:
d=[3,9,2,0,2,4];n=len(d)
s=[0,1,2,3,4,5]
for i in range(n-1):
　　for j in range(n-1,i,-1):
　　　　if d[s[j]]　　　　　　s[j],s[j-1]=s[j-1],s[j]
print(s)
执行该程序段后,输出的结果是(　　)
A.[3,4,2,0,5,1] B.[3,2,4,0,5,1]
C.[1,5,0,4,2,3] D.[1,5,0,2,4,3]
24.有实现冒泡排序的python程序段:
a=[4,6,3,9,1,2]
n=len(a);i=n-1
while i>=1:
　　k=0
　　for j in range(i):
　　　　if a[j]　　　　　　a[j],a[j+1]=a[j+1],a[j]
　　　　　　k=j
　　　　　　　
则划线处的语句应为(　　)
A.i=k-1 B.i=k
C.i=k+1 D.i=j
25.有如下Python程序段:
d=[12,8,6,3,8,10]
i=0;q=0;flag=False
while i　　flag=True
　　for j in range(len(d)-1,q,-1):
　　　　if d[j]>d[j-1]:
　　　　　　d[j],d[j-1]=d[j-1],d[j]
　　　　　　q=j
　　　　　　flag=False
　　i=i+1
程序运行后,加框处语句执行次数为(　　)
A.15 B.12
C.9 D.8

展开更多......

收起↑