数据排序（分层作业）高中信息技术选修1数据与数据结构（浙教版2019）

5.3数据排序2课时（分层作业）【基础达标】1.排序是将无序数据按照某种规则(递增或递减)，重新排列使其变成。2.待排序数据的存储方式一般有两种：、。3.在排序的过程中，序列里的数据元素的值，但其排列顺序。4.Python中，对列表进行排序的方法有两种：一种是，只适用于列表；另外一种是。5.冒泡排序是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数，较小的数的一种排序技术。6.常见的排序算法有：、、、、、等。7.某场篮球联赛中，有5个班级的比赛积分依次为14,11,13,8,9。若采用冒泡排序算法从右到左对其进行升序排序，则第二轮排序后的结果是()A.8,11,13,14,9 B.8,9,13,14,11C.8,9,14,11,13 D.14,13,11,9,88.篮球联赛中，有5个班级的比赛积分依次为14，11，13，8，9.若采用冒泡排序算法对其进行从大到小排序，需要排几遍交换几次（）A.12 B.42 C.18 D.489.采用冒泡排序算法对数据序列18,13,15,2,1,20进行排序，第一轮排序后的结果为20,18,13,15,2,1,则完成整个序列的排序需要进行数据交换的次数总共是()A.6 B.7 C.8 D.910.采用冒泡排序算法对数据序列“7，3，8，2，1，9”进行排序，第一轮排序后的结果为“3，7，2，1，8，9”则完成整个排序需要交换的次数是()A.6次B.7次C.8次D.9次11.下列关于冒泡排序的叙述，正确的是()A.10个数冒泡排序每一趟都要进行9次数据比较B.冒泡排序相邻的数据一定要比较并交换C.冒泡排序相邻的数据一定要比较，但不一定交换D.冒泡排序是所有排序算法最快的一种算法【巩固提升】1.用冒泡排序算法对12、34、45、56、66五个数进行升序排序，下列叙述正确的是（）A.每一趟都不需要进行数据比较B.整个冒泡排序的过程都没有数据被交换C.冒泡排序只能从小到大排序D.5个数一趟比较4次，要进行4趟比较，所以共进行16次比较2.采用冒泡排序算法对数据序列“8，3，5，2，0，9”进行排序，第一轮排序后的结果为“0，8，3，5，2，9”，则整个序列完成排序的交换次数是()A.6次B.7次C.8次D.9次3.对“842715”中的数字进行选择排序中的两遍“加工”即为某密码锁的密码，则该密码可能是()A.842715B.142785C.872415D.1245784.对5个数字“2、8、6、1、7”进行两遍冒泡排序后即为某密码锁的密码，该密码可能是（）A.12687B.12867C.28617D.126785.下面关于冒泡排序说法正确的是（）A、只能从小到大排序B、可以一次比较三个以上的元素C、当比较的两个数逆序时，交换顺序D、只能比较数据6.对下列一组原始数组:13，15，2，11，8，18进行选择排序，第一趟排序介绍，数组的状态不可能是（）A.2，15，13，11，8，18B.18，15，2，11，8，13C.13，15，2，11，18，8D.13，15，18，11，8，27.某Python程序如下：a=[3,1,9,7,6,3]n=len(a)foriinrange(1,n):forjinrange(n2,i2,1):ifa[jka[j+1]:a[j],a[j+1]=a[j+1],a[j]程序运行后，数组a的值是（）A.[9,3,1,7,6,3]B.[9,7,6,3,3,1]C.[1,3,3,9,7,6]D.[1,3,3,6,7,9]8.有如下python程序段:a=[33,24,45,16,77foriinrange(0,2):forjinrange(4,i,1):ifa|j]>a[i]:a|j],a[i]=a[i],alj]经过该程序段“加工”后，数组元素a的值依次为()A.77，45，33，16，24B.77，33，45，16，24C.77，24，45，16，33D.77，45，33，24，169.有如下python程序段:a=[0]*6b=[76,88,84,91,99,80]foriinrange(6):forjinrange(i+1,6):ifb[j]>b[:a[i]+=1else:a[j]+=1print(a)该程序段运行后，列表a的值为()A.[5,2,3,1,0,4B.[0,3,2,4,5,1]C.[10,6,4,8,12,2]D.[6,3,4,2,1,5]10.有如下程序段a=[8，1，2，6，3，4，7，5]n=len(a)foriinrange(0，n，2)forjinrange(n1,i*2+1,1):ifaj]<a[j2]:a[j]，a[j2]=a[j2]，a[j]则程序运行后，a[4]的值为()A.3B.4C.7D.811.运行以下程序段后,输出的列表为（）defbubble_sort(L):length=len(L)foriinrange(l,3):forjinrange(0,lengthi):ifL[j]<L[j+1]:temp=L[j]L[j]=L[j+1]L[j+1]=tempA=[6,8,2,4,3,7]bubble_sort(a)print(a)A.[2.3.4.6.7,8]B.[8,7.6.4.3,2]C.[8,6.4.7.3.2]D.16,8.7,4.3,2]12.实现某排序算法的部分Python程序段如下defbubble_sort(L):length=len(L)foriinrange(1,5):forjinrange(0,lengthi):ifL[j]<L[j+1]:temp=L[j]L[j]=L[j+1]L[j+1]=tempans.append(L[lengthi])a=[3,9,2,1,5,2,6]ans=[]bubble_sort(a)print(ans)经过该程序段“加工”后,输出的结果是()A.[9,6,5,3] B.[1,2,2,3]C.[3,9,2,1] D.[6,2,5,1]13.有如下Python程序段:A=[15,20,11,6,12,8,7,3]foriinrange(1,3):forjinrange(0,8i):ifa[j]>a[j+1]:a[j],a[j+1]=a[j+1],a[j]程序段运行后,数组a中的数据依次为A.3,6,7.8.11.12.15,20B15,11.6,12,8,7.3,20C.11,6,12,8.7,3,15,20D.6,11,8.7.3.12.15.2014.有如下python程序段：n=6a=[]foriinrange(3):forjinrange(ni1):ifa[j]>a[j+1]:a[j],a[j+1]=a[j+1],a[j]print(a)数组元素a（1）到a（6）的数据依次为“50，31，18，42，37，23”，则此程序运行完成后数组元素的数据依次是（）A.50，42，37，31，23，18B.18，23，31，50，37，42C.18，31，23，37，42，50D.18，23，31，37，42，50【链接高考】1.有如下Python程序段a=51,73,74,85,94,88cnt=0foriinrange(len(a)1,0,1):flag=Falseforjinrange(i):ifa[j]>alj+1]:alj],a[j+1]=a[j+1],a[j]flag=Truecnt+=1ifnotflag:break则程序运行后，cnt的值为()A.0 B.1 C.2 D.32.有如下Python程序段:a=[40，14，10，19，24，45];n=len(a)foriinrange(n1):Flag=Falseforjinrange(n1,i,1):ifa[j]>a[j1]:a[j],a[j1]=a[j1],a[j]Flag=Trueifnotflag:break执行该程序段后，下列说法正确的是()A.该程序实现将数组a升序排序B.元素14在程序运行过程中被交换2次C.该程序的时间复杂度为〇(n)D.程序结束后，i的值为33.某Python程序如下foriinrange(2,12):if12%i==0:Mn=ibreak程序运行后,变量mn的值是()A.1 B.2 C.6 D.124.在某篮球赛季中，明星队6场比赛得分依次为103,77,95,71,68,89,若采用冒泡排序算法对其进行排序，第一轮排序结果是68,103,77,95,71,89.则第三轮排序中共进行次数据交换。5.有如下程序段a=[8,1,2,6,3,4,7,5]n=len(a)foriinrange(0,n,2):forjinrange(nl,i*2+1,1):ifa|j]<a[j2]:a[j],a[j2]=a[j2],a[j]则程序运行后，a[4]的值为。6.某Python程序如下：a=[92,22,11,98,96,71]n=len(a)foriinrange(n):forjinrange():ifa[j]>a[j+1]:a[j],a[j+1]=a[j+1],a[j]print(a)为实现n个数的升序排序，划线处应填入的代码是。7.分组冒泡排序。分别对数组a的奇数和偶数位置的元素进行冒泡排序，即采用“跳跃式冒泡”的方法，每次跳跃的步长为2,将数组分成2个子序列，分别对这2个子序列进行排序。例如，对数组a=[6,3,5,4,1,2,8,7]进行分组跳跃式升序冒泡排序，排序后的数组a=[1,2,5,3,6,4,8,7]。(1)对数组a=[4,5,2,9,6,7,10,3,8,1]进行分组跳跃式升序冒泡排序，则排序后的数组a=。(2)实现上述功能的Python程序如下，请在划线处填入合适的代码。importrandomn=8a=[random.randint(l,9)foriinrange(n)]foriinrange(0,n,____)①forjinrange()②:ifa[j]<a[j2]:a[j],a[j2]=a[j2],a[j](3)将分组跳跃式冒泡排序推广到每次跳跃的步长为m的情形，例如对数组a=[6,3,5,4,1,2,8,7]进行分组跳跃式升序冒泡排序，当m=3时，排序后的数组a=[4,1,2,6,3,5,6,7]。相关代码如下，请在划线处填入合适的代码。importrandomm=int(input(“请输入步长m:”))n=8a=[random.randint(1,9)foriinrange(n)]print(“排序前”,a)foriinrange():①forjinrange()②:ifa[j]<a[jm]:a[j],a[jm]=a[jm],a[j]8.某会务组根据参会者到达指定上车点时间和每位参会者可以等待的时间信息，安排车辆接送参会者去宾馆(不考虑车子座位数量)，参会者到达上车点的时间和可以等待的时间用长度为7的字符串表示，例如“08:152”表示参会者当天8点15分到达上车点，最多等待2分钟(每个人的等待时间都小于10)，那么该参会者最晚8点17分出发去宾馆(若8点17分刚到的参会者也一同出发)。编写Python程序，统计接送n个参会者所需的最少车辆数。运行程序，显示所有参会者提交的信息，按到达时间先后排列，再显示所需的最少车辆数，程序运行结果如图所示。08:12208:14308:15208:15408:17108:17108:17308:19408:21408:234接送所有参与者最少需要3辆车(1)若将图中第4行“08:154”数据改为08:151”，程序输出的结果是否会发生改变(A.会改变B.不会改变)。(2)实现上述功能的部分Python程序如下，请在横线处填入合适的代码。A=['08:154','08:143,'08:234','08:152','08:122',08:171','08:173','08:194','08:214','08:171']deftran(strl):ss=int(strl[:2])*60+int(str1[3:6])returnssforiinrange(len(a)1):forjinrange(len(a)1,i,1):ifa|j]<a[j1]:a[j],a[j1]=a[j1],a[j]n=len(a)b=c=foriinrange(n):b.append(tran(a[i][:5]))c.append(b[1]+int(a[i][6:]))forjinrange(i,0,1):①ifc[k]>c[j]: b[k],b[j]=b[j],b[k]c[k],c[j]=c[j],c[k]else:breaksum=0flag=[Falseforiinrange(n)]foriinrange(n):Ifflag[i]==False:Forjinrange(i,n):if②flag[j]=True③print(“接送所有参会者最少需要%d辆车%sum)参考答案【基础达标】1.有序数据2.数组、链表3.保持不变、可能改变4.列表自带的sort方法、内建函数sorted方法5.下沉（上冒）、上冒（下沉）6.选择排序、插入排序、快速排序、堆排序、归并排序、桶排序7.答案：C[解析]据题意:该数组进行从小到大排序第1种情况:从数组第1个到最后一个元素向后走访数组，进行数据比较，则:第一趟:14与11比较并交换，14与13比较并交换，14与8比较并交换，14与9比较并交换，数组顺序为:11，13，8，9，14。第二趟:11与13比较，13与8比较并交换，13与9比较并交换，13与14比较，数组顺序为:11，8，9，13，14.这种情况，选项里没有答案，故放弃。第2种情况:从数组最后一个到第1个元素向前走访数组，进行数据比较，则:第一趟:9与8比较，8与13比较并交换，8与11比较并交换，8与14比较并交换，数组顺序为:8，14，11，13，9。第二趟:9与13比较并交换，9与11比较并交换，9与14比较并交换，9与8比较，数组顺序为:8，9，14，11，13。故选:C。8.答案：A[解析]据题意:该数组进行从大到小排序，有两种情况:第1种情况:从数组第1个到最后一个元素向后走访数组，进行数据比较，则:第一趟:11与13交换，数组顺序为:14，13，11,8，9,第二趟:8与9交换，数组顺序为:14，13，11，9，8，排序完成;所以第1种情况共排序2遍，交换2次。第2种情况:从数组最后一个到第1个元素向前走访数组，进行数据比较，则:第一趟:9与8交换，13与11交换，数组顺序为:14，13，11，9，8，排序完成，所以第2种情况共排序1遍，交换2次。故选:A。9.答案：D[解析]数据序列“18，13，15，2，1，20”进行排序，第一轮排序后的结果为“1，18，13，15，2，20”，可知冒泡算法的思想进行升序排列数组，要完成最终的排序需要进行9轮比较最终完成故选:D。10.答案：C[解析]本题的6个数据“7，3，8，2，1，9”，第一次:“3，7，2，1，8，9”，交换次数为3次，第二次:“3，2，1，7，8，9”，交换次数为2次，第三次，“2，1，3，7，8，9”交换次数为2次，第四次1，2，3，7，8，9，交换次数为1次，总次数为3+2+2+1=8次。故选:C。11.答案：C[解析]由冒泡排序算法基本思想知:依次比较两个相邻的数据，如果顺序错误就交换它们，所以相邻的数据一定会比较，但不一定交换，所以B错误，C正确;冒泡排序中，几个数要进行n1次比较，在第j趟中要进行nj趟比较，所以A错误;在排序算法中，根据原始数据的不同，不同算法的效率不一样，速度也不一样，所以D错误。故选C。【巩固提升】1.答案：B[解析]题中五个数已经是升序数列了，所以在进行冒泡排序时虽然还进行比较，但是不会进行数据的交换.5个数只有第一趟比较4此，找到了最小值后比较就会少一次.故选:B.2.答案：D[解析]本题的6个数据，835209第一次:083529，交换次数为4次(“8，3，5，0，2，9”，“8，3，0，5，2，9”，，0，3，5，2，9”，“0，8，3，5，2，9第二次:028359，交换次数为3次(“0，3，2，5，9”，“0，8，2，3，5，9”，2，8，3，5，9”)，第三次，023859，交换次数为1次(“0，23，8，5，9”)第四次，023589，交换次数为1次(“0，23，5，8，9”)，总次数为4+3+1+1=9次。故选:D。3.答案：.C[解析]如果选择升序排序,第1遍后为142785.找到最小的值与第1个位置交换,其他不动。第2遍后为124785。如果选择是降序排序,第1遍后为842715.因为第1个位置数本身是最大,不用交换。第2遍后为872415。第二大的数与第2位置数交换。4.答案：A[解析]据题意:从4个答案可以看出这密码是从小到大排列的，有两种情况:第1种情况:从数组第1个到最后一个元素向后走访数组，进行数据比较，则:第一趟:2与8比较，8与6比较并交换，8与1比较并交换，8与7比较并交换，数组顺序为:2、6、1、7、8；第二趟:2与6比较，6与1比较并交换，6与7比较，7与8比较，数组顺序为:2、1、6、7、8，选项中没有次序列，故此种情况放弃。第2种情况:从数组最后一个到第1个元素向前走访数组，进行数据比较，则:第一趟:7与1比较，1与6比较并交换，1与8比较并交换，1与2比较并交换，数组顺序为:1、2、8、6、7；第二趟:7与6比较，6与8比较并交换，6与2比较，2与1比较，数组顺序为:1、2、6、8、7，这是选项A的数组。故选:A。5.答案：C[解析]冒泡排序是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉（上冒）”，较小的数“上冒（下沉）”的一种排序技术。冒泡排序算法把待排序的n个元素的数组看成是垂直堆放的一列数据，对相邻两个数进行比较，将较小的数据换到上面的一个元素中（或将较大的数据换到下面的一个元素中）。6.答案：C[解析]如果该数组升序排列，会有两种排序情况:①第一趟排序要在所有数里选择最小数2，把它与第一个数13交换位置，放在数组最前面，得到数组为:2，15，13，11，8，18，故A选项正确;②第一趟排序要在所有数里选择最大数18，即数组最后一个数，所以不发生数字交换，故第一趟排序结束后，数组还是原来的顺序，如果该数组降序排列，也会有两种排序情况:①第一趟排序要在所有数里选择最小数2，把它与最后一个数18交换位置，放在数组最后面，得到数组:13，15，18，11，8，2，故D正确;②第一趟排序要在所有数里选择最大数18，把它与数组第一个数13交换位置，放在数组最前面，得到数组:18，15，2，11，8，13，故B正确;综上:第一趟排序后，选项A、B、D，或者数组原来顺序4种情况会出现，只有C的数组不会出现;故选C。7.答案：B[解析]程序功能是使用冒泡排序算法对数组a进行降序排序。注意比较的两个相邻元素是a[j}和a[j+1],故变量j的取取值范围为range(n2,i2,1)。8.答案：A[解析].foriinrange(0,2):外循环次数=2，内循环forjinrange(4,i,1):，内循环i.fa[j]>al]:a|j]与a[]交换，i=0，第一次比较完成后a=[77,24,45,16,33]，i=1第二次比较完成后，a=[77,45,33,16,24，A选项正确。故选:A。9.答案：A[解析]阅读程序段可知，程序实现的是列表中元素的降序排列，各元素下标的交换次数，已知列表[76,88,84,91,99,80]中76为最小的元素，所以需要比较5次，故a中对应的元素为5，同理分析后面的元素得到[5,2,3,1,0,4]。故选:A。10.答案：B[解析]阅读程序可知，外循环i的取值分别为0，2，4，6。当i=2时，内循环j的取值范围最大为[7，2]，此时的排序适用于整个数组，根据a[j]<a[j2]的条件进行交換a[j]，a[j2]=a[j2]，a[j]的值后，最终得到a[4]的值为4，因为第一个元素的下标为0。故选:B。11.答案：C[解析]观察代码“foriinrange(1,3)”,变量i只执行两次,循环体是利用冒泡排序,从前往后比较实现降序。i=1执行完后a的状态为[8,6,4,3,7,2],i=2执行完后a的状态为[8,6,4,7.3,2],所以答案选C。12.答案：B[解析]该程序中,兩数bubble_sort(L)是利用冒泡排序的思想对数组L按从前往后比较方式进行降序排序,一趟加工完成后最后面的元素是当前的最小数据,将该元素添加进数组ans,所以第一趟完成后数组ans中的元素是[1],观察到i的循环范围是1~4,即只进行4趟比较与交换,数组ans中依次记录[1,2,2,3],因此正确答案是B。13.答案：C[解析]本题主要考查的是冒泡排序。本题的功能是将数组a中的数据进行升序排序,求排序两遍后的数据序列情况，第一遍排序后的结果为“15,11,6.12.8,7,3,20”,第二遍排序后的結果为“11,6,12.8.7,3,15,20”,因此等案为C。14.答案：C[解析]第一步：ifa（j）＞a（j+1）→从小到大排序，现在确定最大→排除A；第二步：50，31，18，42，37，23（i=1）→31，18，42，37，23，50（i=2）→18，31，37，23，42,50（i=3）→18，31，23，37，42,50。故选C。【链接高考】1.答案：B[解析]本题考查的python程序的调试与运行。Por语句是循环语句，它的格式是:For变量=初值To终值|Step步长]循环体Nert变量。Range(start,stop[,step])start:计数从start开始。默认是从0开始。例如range(5)等价于range(0,5);stop:计数到stop结束，但不包括stop。阅读程序可知，本程序段实现的是数据的升序排列，需要交换的元素只有94，88，所以共执行一次交换，得到cnt的值为1。故选:B。2.答案：D[解析]本题主要考查排序算法及Python程序实现。该程序实现将数组a降序排序;元素14在程序运行过程中被交换3次;该程序的时间复杂度为0(n2);当i3时，a已有序，因此程序结束后，i的值为3，故本题选D选项。3.答案：B[解析]循环变量i的范围为2~11,若12能被i整除,则将i的值赋给变量mn，并使用break退出循环,所以变量mn存储的是12除1以外的最小因数,结果为2.4.答案：1[解析]第一轮排序结果是68,103,77,95,71,89.第二轮排序结果是68,71,103,77,95,89.第三轮排序结果是68,71,77,103,95,89.则第三轮排序中共进行了1次数据交换综上所述，答案:1。5.答案：4[解析]阅读程序可知，外循环i的取值分别为0，2，4，6。当i=2时，内循环的取值范围最大为[7,2，此时的排序适用于整个数组，根据a[j]<a[j2]的条件进行交换a[j],aj2]=aj2]，a|j]的值后，最终得到a[4]的值为4，因为第一个元素的下标为0。故填:4。6.答案：range(n2,i1,1)[解析]本题主要考查冒泡排序算法。分析程序,外层循环变量i的范围是0~n1,该程序实现升序排序,比较的是索引j与j+1,内层循环可以从左往右比较,每次将一个最大值放到最右边,代码为ange(ni1);也可以从右往左比较交换,每次将一个最小