數(shù)據(jù)排序（分層作業(yè)）高中信息技術選修1數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)（浙教版2019）

5.3數(shù)據(jù)排序2課時（分層作業(yè)）【基礎達標】1.排序是將無序數(shù)據(jù)按照某種規(guī)則(遞增或遞減)，重新排列使其變成。2.待排序數(shù)據(jù)的存儲方式一般有兩種：、。3.在排序的過程中，序列里的數(shù)據(jù)元素的值，但其排列順序。4.Python中，對列表進行排序的方法有兩種：一種是，只適用于列表；另外一種是。5.冒泡排序是在一系列數(shù)據(jù)中對相鄰兩個數(shù)依次進行比較和調(diào)整，讓較大的數(shù)，較小的數(shù)的一種排序技術。6.常見的排序算法有：、、、、、等。7.某場籃球聯(lián)賽中，有5個班級的比賽積分依次為14,11,13,8,9。若采用冒泡排序算法從右到左對其進行升序排序，則第二輪排序后的結(jié)果是()A.8,11,13,14,9 B.8,9,13,14,11C.8,9,14,11,13 D.14,13,11,9,88.籃球聯(lián)賽中，有5個班級的比賽積分依次為14，11，13，8，9.若采用冒泡排序算法對其進行從大到小排序，需要排幾遍交換幾次（）A.12 B.42 C.18 D.489.采用冒泡排序算法對數(shù)據(jù)序列18,13,15,2,1,20進行排序，第一輪排序后的結(jié)果為20,18,13,15,2,1,則完成整個序列的排序需要進行數(shù)據(jù)交換的次數(shù)總共是()A.6 B.7 C.8 D.910.采用冒泡排序算法對數(shù)據(jù)序列“7，3，8，2，1，9”進行排序，第一輪排序后的結(jié)果為“3，7，2，1，8，9”則完成整個排序需要交換的次數(shù)是()A.6次B.7次C.8次D.9次11.下列關于冒泡排序的敘述，正確的是()A.10個數(shù)冒泡排序每一趟都要進行9次數(shù)據(jù)比較B.冒泡排序相鄰的數(shù)據(jù)一定要比較并交換C.冒泡排序相鄰的數(shù)據(jù)一定要比較，但不一定交換D.冒泡排序是所有排序算法最快的一種算法【鞏固提升】1.用冒泡排序算法對12、34、45、56、66五個數(shù)進行升序排序，下列敘述正確的是（）A.每一趟都不需要進行數(shù)據(jù)比較B.整個冒泡排序的過程都沒有數(shù)據(jù)被交換C.冒泡排序只能從小到大排序D.5個數(shù)一趟比較4次，要進行4趟比較，所以共進行16次比較2.采用冒泡排序算法對數(shù)據(jù)序列“8，3，5，2，0，9”進行排序，第一輪排序后的結(jié)果為“0，8，3，5，2，9”，則整個序列完成排序的交換次數(shù)是()A.6次B.7次C.8次D.9次3.對“842715”中的數(shù)字進行選擇排序中的兩遍“加工”即為某密碼鎖的密碼，則該密碼可能是()A.842715B.142785C.872415D.1245784.對5個數(shù)字“2、8、6、1、7”進行兩遍冒泡排序后即為某密碼鎖的密碼，該密碼可能是（）A.12687B.12867C.28617D.126785.下面關于冒泡排序說法正確的是（）A、只能從小到大排序B、可以一次比較三個以上的元素C、當比較的兩個數(shù)逆序時，交換順序D、只能比較數(shù)據(jù)6.對下列一組原始數(shù)組:13，15，2，11，8，18進行選擇排序，第一趟排序介紹，數(shù)組的狀態(tài)不可能是（）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]程序運行后，數(shù)組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]經(jīng)過該程序段“加工”后，數(shù)組元素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.實現(xiàn)某排序算法的部分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)經(jīng)過該程序段“加工”后,輸出的結(jié)果是()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]程序段運行后,數(shù)組a中的數(shù)據(jù)依次為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)數(shù)組元素a（1）到a（6）的數(shù)據(jù)依次為“50，31，18，42，37，23”，則此程序運行完成后數(shù)組元素的數(shù)據(jù)依次是（）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執(zhí)行該程序段后，下列說法正確的是()A.該程序?qū)崿F(xiàn)將數(shù)組a升序排序B.元素14在程序運行過程中被交換2次C.該程序的時間復雜度為〇(n)D.程序結(jié)束后，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,若采用冒泡排序算法對其進行排序，第一輪排序結(jié)果是68,103,77,95,71,89.則第三輪排序中共進行次數(shù)據(jù)交換。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)為實現(xiàn)n個數(shù)的升序排序，劃線處應填入的代碼是。7.分組冒泡排序。分別對數(shù)組a的奇數(shù)和偶數(shù)位置的元素進行冒泡排序，即采用“跳躍式冒泡”的方法，每次跳躍的步長為2,將數(shù)組分成2個子序列，分別對這2個子序列進行排序。例如，對數(shù)組a=[6,3,5,4,1,2,8,7]進行分組跳躍式升序冒泡排序，排序后的數(shù)組a=[1,2,5,3,6,4,8,7]。(1)對數(shù)組a=[4,5,2,9,6,7,10,3,8,1]進行分組跳躍式升序冒泡排序，則排序后的數(shù)組a=。(2)實現(xiàn)上述功能的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的情形，例如對數(shù)組a=[6,3,5,4,1,2,8,7]進行分組跳躍式升序冒泡排序，當m=3時，排序后的數(shù)組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.某會務組根據(jù)參會者到達指定上車點時間和每位參會者可以等待的時間信息，安排車輛接送參會者去賓館(不考慮車子座位數(shù)量)，參會者到達上車點的時間和可以等待的時間用長度為7的字符串表示，例如“08:152”表示參會者當天8點15分到達上車點，最多等待2分鐘(每個人的等待時間都小于10)，那么該參會者最晚8點17分出發(fā)去賓館(若8點17分剛到的參會者也一同出發(fā))。編寫Python程序，統(tǒng)計接送n個參會者所需的最少車輛數(shù)。運行程序，顯示所有參會者提交的信息，按到達時間先后排列，再顯示所需的最少車輛數(shù)，程序運行結(jié)果如圖所示。08:12208:14308:15208:15408:17108:17108:17308:19408:21408:234接送所有參與者最少需要3輛車(1)若將圖中第4行“08:154”數(shù)據(jù)改為08:151”，程序輸出的結(jié)果是否會發(fā)生改變(A.會改變B.不會改變)。(2)實現(xiàn)上述功能的部分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.有序數(shù)據(jù)2.數(shù)組、鏈表3.保持不變、可能改變4.列表自帶的sort方法、內(nèi)建函數(shù)sorted方法5.下沉（上冒）、上冒（下沉）6.選擇排序、插入排序、快速排序、堆排序、歸并排序、桶排序7.答案：C[解析]據(jù)題意:該數(shù)組進行從小到大排序第1種情況:從數(shù)組第1個到最后一個元素向后走訪數(shù)組，進行數(shù)據(jù)比較，則:第一趟:14與11比較并交換，14與13比較并交換，14與8比較并交換，14與9比較并交換，數(shù)組順序為:11，13，8，9，14。第二趟:11與13比較，13與8比較并交換，13與9比較并交換，13與14比較，數(shù)組順序為:11，8，9，13，14.這種情況，選項里沒有答案，故放棄。第2種情況:從數(shù)組最后一個到第1個元素向前走訪數(shù)組，進行數(shù)據(jù)比較，則:第一趟:9與8比較，8與13比較并交換，8與11比較并交換，8與14比較并交換，數(shù)組順序為:8，14，11，13，9。第二趟:9與13比較并交換，9與11比較并交換，9與14比較并交換，9與8比較，數(shù)組順序為:8，9，14，11，13。故選:C。8.答案：A[解析]據(jù)題意:該數(shù)組進行從大到小排序，有兩種情況:第1種情況:從數(shù)組第1個到最后一個元素向后走訪數(shù)組，進行數(shù)據(jù)比較，則:第一趟:11與13交換，數(shù)組順序為:14，13，11,8，9,第二趟:8與9交換，數(shù)組順序為:14，13，11，9，8，排序完成;所以第1種情況共排序2遍，交換2次。第2種情況:從數(shù)組最后一個到第1個元素向前走訪數(shù)組，進行數(shù)據(jù)比較，則:第一趟:9與8交換，13與11交換，數(shù)組順序為:14，13，11，9，8，排序完成，所以第2種情況共排序1遍，交換2次。故選:A。9.答案：D[解析]數(shù)據(jù)序列“18，13，15，2，1，20”進行排序，第一輪排序后的結(jié)果為“1，18，13，15，2，20”，可知冒泡算法的思想進行升序排列數(shù)組，要完成最終的排序需要進行9輪比較最終完成故選:D。10.答案：C[解析]本題的6個數(shù)據(jù)“7，3，8，2，1，9”，第一次:“3，7，2，1，8，9”，交換次數(shù)為3次，第二次:“3，2，1，7，8，9”，交換次數(shù)為2次，第三次，“2，1，3，7，8，9”交換次數(shù)為2次，第四次1，2，3，7，8，9，交換次數(shù)為1次，總次數(shù)為3+2+2+1=8次。故選:C。11.答案：C[解析]由冒泡排序算法基本思想知:依次比較兩個相鄰的數(shù)據(jù)，如果順序錯誤就交換它們，所以相鄰的數(shù)據(jù)一定會比較，但不一定交換，所以B錯誤，C正確;冒泡排序中，幾個數(shù)要進行n1次比較，在第j趟中要進行nj趟比較，所以A錯誤;在排序算法中，根據(jù)原始數(shù)據(jù)的不同，不同算法的效率不一樣，速度也不一樣，所以D錯誤。故選C。【鞏固提升】1.答案：B[解析]題中五個數(shù)已經(jīng)是升序數(shù)列了，所以在進行冒泡排序時雖然還進行比較，但是不會進行數(shù)據(jù)的交換.5個數(shù)只有第一趟比較4此，找到了最小值后比較就會少一次.故選:B.2.答案：D[解析]本題的6個數(shù)據(jù)，835209第一次:083529，交換次數(shù)為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，交換次數(shù)為3次(“0，3，2，5，9”，“0，8，2，3，5，9”，2，8，3，5，9”)，第三次，023859，交換次數(shù)為1次(“0，23，8，5，9”)第四次，023589，交換次數(shù)為1次(“0，23，5，8，9”)，總次數(shù)為4+3+1+1=9次。故選:D。3.答案：.C[解析]如果選擇升序排序,第1遍后為142785.找到最小的值與第1個位置交換,其他不動。第2遍后為124785。如果選擇是降序排序,第1遍后為842715.因為第1個位置數(shù)本身是最大,不用交換。第2遍后為872415。第二大的數(shù)與第2位置數(shù)交換。4.答案：A[解析]據(jù)題意:從4個答案可以看出這密碼是從小到大排列的，有兩種情況:第1種情況:從數(shù)組第1個到最后一個元素向后走訪數(shù)組，進行數(shù)據(jù)比較，則:第一趟:2與8比較，8與6比較并交換，8與1比較并交換，8與7比較并交換，數(shù)組順序為:2、6、1、7、8；第二趟:2與6比較，6與1比較并交換，6與7比較，7與8比較，數(shù)組順序為:2、1、6、7、8，選項中沒有次序列，故此種情況放棄。第2種情況:從數(shù)組最后一個到第1個元素向前走訪數(shù)組，進行數(shù)據(jù)比較，則:第一趟:7與1比較，1與6比較并交換，1與8比較并交換，1與2比較并交換，數(shù)組順序為:1、2、8、6、7；第二趟:7與6比較，6與8比較并交換，6與2比較，2與1比較，數(shù)組順序為:1、2、6、8、7，這是選項A的數(shù)組。故選:A。5.答案：C[解析]冒泡排序是在一系列數(shù)據(jù)中對相鄰兩個數(shù)依次進行比較和調(diào)整，讓較大的數(shù)“下沉（上冒）”，較小的數(shù)“上冒（下沉）”的一種排序技術。冒泡排序算法把待排序的n個元素的數(shù)組看成是垂直堆放的一列數(shù)據(jù)，對相鄰兩個數(shù)進行比較，將較小的數(shù)據(jù)換到上面的一個元素中（或?qū)⑤^大的數(shù)據(jù)換到下面的一個元素中）。6.答案：C[解析]如果該數(shù)組升序排列，會有兩種排序情況:①第一趟排序要在所有數(shù)里選擇最小數(shù)2，把它與第一個數(shù)13交換位置，放在數(shù)組最前面，得到數(shù)組為:2，15，13，11，8，18，故A選項正確;②第一趟排序要在所有數(shù)里選擇最大數(shù)18，即數(shù)組最后一個數(shù)，所以不發(fā)生數(shù)字交換，故第一趟排序結(jié)束后，數(shù)組還是原來的順序，如果該數(shù)組降序排列，也會有兩種排序情況:①第一趟排序要在所有數(shù)里選擇最小數(shù)2，把它與最后一個數(shù)18交換位置，放在數(shù)組最后面，得到數(shù)組:13，15，18，11，8，2，故D正確;②第一趟排序要在所有數(shù)里選擇最大數(shù)18，把它與數(shù)組第一個數(shù)13交換位置，放在數(shù)組最前面，得到數(shù)組:18，15，2，11，8，13，故B正確;綜上:第一趟排序后，選項A、B、D，或者數(shù)組原來順序4種情況會出現(xiàn)，只有C的數(shù)組不會出現(xiàn);故選C。7.答案：B[解析]程序功能是使用冒泡排序算法對數(shù)組a進行降序排序。注意比較的兩個相鄰元素是a[j}和a[j+1],故變量j的取取值范圍為range(n2,i2,1)。8.答案：A[解析].foriinrange(0,2):外循環(huán)次數(shù)=2，內(nèi)循環(huán)forjinrange(4,i,1):，內(nèi)循環(huán)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[解析]閱讀程序段可知，程序?qū)崿F(xiàn)的是列表中元素的降序排列，各元素下標的交換次數(shù)，已知列表[76,88,84,91,99,80]中76為最小的元素，所以需要比較5次，故a中對應的元素為5，同理分析后面的元素得到[5,2,3,1,0,4]。故選:A。10.答案：B[解析]閱讀程序可知，外循環(huán)i的取值分別為0，2，4，6。當i=2時，內(nèi)循環(huán)j的取值范圍最大為[7，2]，此時的排序適用于整個數(shù)組，根據(jù)a[j]<a[j2]的條件進行交換a[j]，a[j2]=a[j2]，a[j]的值后，最終得到a[4]的值為4，因為第一個元素的下標為0。故選:B。11.答案：C[解析]觀察代碼“foriinrange(1,3)”,變量i只執(zhí)行兩次,循環(huán)體是利用冒泡排序,從前往后比較實現(xiàn)降序。i=1執(zhí)行完后a的狀態(tài)為[8,6,4,3,7,2],i=2執(zhí)行完后a的狀態(tài)為[8,6,4,7.3,2],所以答案選C。12.答案：B[解析]該程序中,兩數(shù)bubble_sort(L)是利用冒泡排序的思想對數(shù)組L按從前往后比較方式進行降序排序,一趟加工完成后最后面的元素是當前的最小數(shù)據(jù),將該元素添加進數(shù)組ans,所以第一趟完成后數(shù)組ans中的元素是[1],觀察到i的循環(huán)范圍是1~4,即只進行4趟比較與交換,數(shù)組ans中依次記錄[1,2,2,3],因此正確答案是B。13.答案：C[解析]本題主要考查的是冒泡排序。本題的功能是將數(shù)組a中的數(shù)據(jù)進行升序排序,求排序兩遍后的數(shù)據(jù)序列情況，第一遍排序后的結(jié)果為“15,11,6.12.8,7,3,20”,第二遍排序后的結(jié)果為“11,6,12.8.7,3,15,20”,因此等案為C。14.答案：C[解析]第一步：ifa（j）＞a（j+1）→從小到大排序，現(xiàn)在確定最大→排除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?！炬溄痈呖肌?.答案：B[解析]本題考查的python程序的調(diào)試與運行。Por語句是循環(huán)語句，它的格式是:For變量=初值To終值|Step步長]循環(huán)體Nert變量。Range(start,stop[,step])start:計數(shù)從start開始。默認是從0開始。例如range(5)等價于range(0,5);stop:計數(shù)到stop結(jié)束，但不包括stop。閱讀程序可知，本程序段實現(xiàn)的是數(shù)據(jù)的升序排列，需要交換的元素只有94，88，所以共執(zhí)行一次交換，得到cnt的值為1。故選:B。2.答案：D[解析]本題主要考查排序算法及Python程序?qū)崿F(xiàn)。該程序?qū)崿F(xiàn)將數(shù)組a降序排序;元素14在程序運行過程中被交換3次;該程序的時間復雜度為0(n2);當i3時，a已有序，因此程序結(jié)束后，i的值為3，故本題選D選項。3.答案：B[解析]循環(huán)變量i的范圍為2~11,若12能被i整除,則將i的值賦給變量mn，并使用break退出循環(huán),所以變量mn存儲的是12除1以外的最小因數(shù),結(jié)果為2.4.答案：1[解析]第一輪排序結(jié)果是68,103,77,95,71,89.第二輪排序結(jié)果是68,71,103,77,95,89.第三輪排序結(jié)果是68,71,77,103,95,89.則第三輪排序中共進行了1次數(shù)據(jù)交換綜上所述，答案:1。5.答案：4[解析]閱讀程序可知，外循環(huán)i的取值分別為0，2，4，6。當i=2時，內(nèi)循環(huán)的取值范圍最大為[7,2，此時的排序適用于整個數(shù)組，根據(jù)a[j]<a[j2]的條件進行交換a[j],aj2]=aj2]，a|j]的值后，最終得到a[4]的值為4，因為第一個元素的下標為0。故填:4。6.答案：range(n2,i1,1)[解析]本題主要考查冒泡排序算法。分析程序,外層循環(huán)變量i的范圍是0~n1,該程序?qū)崿F(xiàn)升序排序,比較的是索引j與j+1,內(nèi)層循環(huán)可以從左往右比較,每次將一個最大值放到最右邊,代碼為ange(ni1);也可以從右往左比較交換,每次將一個最小