第16课 排序1——冒泡排序及变形-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参（浙教版2019）

第16课　排序1——冒泡排序及变形(见学生用书P124) ——5.3　数据排序，教材P139～146 1.理解排序的概念和基本方法。　2.理解冒泡排序的思想，能利用冒泡排序算法设计程序解决实际问题。 1． 排序 (1)排序(sorting)是使数据序列中的元素按照某个值的递增(或递减)的次序　重新排列　的操作。在排序的过程中，数据元素的　值　保持不变，但其在序列中的　顺序　可能会改变。 (2)待排序数据的存储方式一般有　数组　和　链表　两种方式： ①利用数组存储数据，在排序时需要对数据本身进行物理重排，可能需要移动数据的　位置　。 ②利用链表存储数据，仅需要　修改指针　即可。 (3)Python中的排序函数： ①列表自带的sort()方法，直接对列表进行排序，只适用于列表，不会产生新的序列，如a.sort()。 ②内建函数sorted()方法，返回一个新的序列，而原来的序列依然存在，如b＝sorted(a)。 (4)常见的排序算法有：　冒泡排序　、　选择排序　、　插入排序　、快速排序、堆排序、归并排序、　桶排序　等。 2．冒泡排序 (1)冒泡排序(Bubble Sort)是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉(上冒)”，较小的数“上冒(下沉)”的一种排序技术。 (2)冒泡排序算法把待排序的n个元素的数组看成是垂直堆放的一列数据，对相邻两个数进行比较，将较小的数据换到上面的一个元素中(或将较大的数据换到下面的一个元素中)。重复这一过程，直到处理完最后两个元素中的数据，称为　一遍加工　。当第一遍加工完成时，　最小　的数据已经“　上浮　”到第一个元素的位置(或最大的数据“下沉”到最后一个元素的位置)。然后对余下的n－1个元素重复上述处理过程，直至最后进行余下两个数据的比较和交换。 (3)对于n个元素的数组，共需要　n－1　遍加工，第一遍加工的比较次数为n－1次，第二遍加工的比较次数为n－2次，以此类推，最后一遍加工的比较只需1次。所以用冒泡排序算法进行排序时，共需比较　n(n－1)/2　(次)，其时间复杂度为　O(n2)　。 (4)冒泡排序的Python代码实现。 ①程序代码 a＝[87，77，59，94，46，65] n＝len(a) for i in range(1，n)：　　　　　　　　#排序趟数，n个数排序n－1趟 for j in range(0，n－i)： #比较次数，i＝1时，比较n－1次，共n(n－1)/2次 if a[j]>a[j＋1]： #交换次数，最多n(n－1)/2次，可以判断升降序 a[j]，a[j＋1]＝a[j＋1]，a[j] print(”第”＋str(i)＋”遍：　”，a) print(”最终结果：　”，a) ②运行结果： 第1遍： [77，59，87，46，65，94] 第2遍： [59，77，46，65，87，94] 第3遍： [59，46，65，77，87，94] 第4遍： [46，59，65，77，87，94] 第5遍： [46，59，65，77，87，94] 最终结果： [46，59，65，77，87，94] 1．冒泡排序基本变型形：在确定趟数变化的前提下(range(1，n))。 排序方法 遍历方向 数据交换形式 程序代码举例 升序 从前向后 相邻两个元素，大的后移 for i in range(1，n)： for j in range(0，n－i)： if a[j]>a[j＋1]： a[j]，a[j＋1]＝a[j＋1]，a[j] 从后向前 相邻两个元素，小的前移 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] 降序 从前向后 相邻两个元素，小的后移 for i in range(1，n)： for j in range(0，n－i)： if a[j]<a[j＋1]： a[j]，a[j＋1]＝a[j＋1]，a[j] 从后向前 相邻两个元素，大的前移 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] 2．冒泡排序优化：在某一遍加工过程中没有数据交换时，说明数据已经有序，排序可以提前结束。 优化1：引入flag标识是否有交换 优化2：记下每趟最后一次交换的位置 n＝len(a) i＝1 flag＝True while i<n and flag： flag＝False for j in range(0，n－i)： if a[j]>a[j＋1]： a[j]，a[j＋1]＝a[j＋1]，a[j] flag＝True i＋＝1 print(”最终结果：　”，a) n＝len(a) i＝1 while i<n： start＝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] start＝j i＝start＋1 print(”最终结果：　”，a) 3．双关键字排序 (1)按成绩降序排序，当成绩相同时，按学号升序排序 ①Python程序： a＝[[”005”，86]，[”004”，86]，[”006”，87]，[”007”，90]，[”010”，93]] print(”排序前：　”，a) n＝len(a) for i in range(0，n－1)： for j in range(n－1，i，－1)： if a[j][1]>a[j－1][1] or a[j][1]＝＝a[j－1][1] and a[j][0]<a[j－1][0]： a[j]，a[j－1]＝a[j－1]，a[j] print(”排序后：　”，a) ②运行结果： 排序前： [['005'，86]，['004'，86]，['006'，87]，['007'，90]，['010'，93]] 排序后： [['010'，93]，['007'，90]，['006'，87]，['004'，86]，['005'，86]] (2)男生在前，女生在后，按身高升序排序 ①Python程序： a＝[[”005”，178，”男”]，[”004”，146，”女”]，[”006”，190，”男”]，[”007”，160，”女”]，[”010”，178，”男”]] print(”排序前：　”，a) n＝len(a) for i in range(0，n－1)： for j in range(n－1，i，－1)： if a[j][2]＝＝”男” and a[j－1][2]＝＝”女” or a[j][2]＝＝a[j－1][2] and a[j][1]<a[j－1][1]： 　　　a[j]，a[j－1]＝a[j－1]，a[j] print(”排序后：　”，a) ②运行结果： 排序前： [['005'，178，'男']，['004'，146，'女']，['006'，190，'男']，['007'，160，'女']， ['010'，178， '男']] 排序后： [['005'，178，'男']，['010'，178，'男']，['006'，190，'男']，['004'，146，'女']，['007'，160，'女']] 4．奇偶位置排序 (1)Python程序： a＝[52，30，40，20，70，7，89，65，5] print(”排序前：　”，a) n＝len(a) for i in range(0，n－1，2)： for j in range(0，n－2，1)： if a[j]>a[j＋2]： a[j]，a[j＋2]＝a[j＋2]，a[j] print(”排序后：　”，a) (2)运行结果： 排序前： [52，30，40，20，70，7，89，65，5] 排序后： [5，7，40，20，52，30，70，65，89] 5．前几名排序 (1)Python程序： 实现程序举例1 实现程序举例2 a＝[[”001”，95]，[”002”，80]，[”003”，97]，[”004”，70]，[”005”，78]，[”006”，96]，[”007”，95]，[”008”，95]，[”009”，94]，[”010”，80]，[”011”，93]，[”012”，60]，[”013”，79]] n＝len(a) print(”排序前：　”，a) m＝int(input(”输入获取的前m名：　”)) for i in range(m)： 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] k＝j＝m while j<n： if a[j][1]＝＝a[m－1][1]： a[k]，a[j]＝a[j]，a[k] k＋＝1 j＋＝1 print(a[：k]) a＝[[”001”，95]，[”002”，80]，[”003”，97]，[”004”，70]，[”005”，78]，[”006”，96]，[”007”，95]，[”008”，95]，[”009”，94]，[”010”，80]，[”011”，93]，[”012”，60]，[”013”，79]] n＝len(a) print(”排序前：　”，a) m＝int(input(”输入获取的前m名：　”)) for i in range(n)： 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] if i>＝m and a[i][1]！＝a[m－1][1]： break print(a[：i]) (2)运行结果： 排序前： [['001'，95]，['002'，80]，['003'，97]，['004'，70]，['005'，78]，['006'，96]，['007'，95]，['008'，95]，['009'，94]，['010'，80]，['011'，93]，['012'，60]，['013'，79]] 输入获取的前m名：　3 [['003'，97]，['006'，96]，['001'，95]，['007'，95]， ['008'，95]] 　　采用冒泡排序算法对一组数据进行排序，第一遍排序后的结果为2，30，18，21，6，9，65，那么该组数据的原始顺序可能是(　C　) A．2，30，18，21，65，6，9　　　　　B．30，2，18，21，6，9，65 C．30，18，21，6，9，65，2 D．30，18，2，21，6，9，65 【解析】 通过第一遍排序发现最小值2 在最左边，可以确定该冒泡排序是升序且从后往前冒，把小的从后往前推。选项A，冒泡一遍的数据为2，6，30，18，21，65，9，不符合题意；选项B，冒泡一遍的数据为2，30，6，18，21，9，65，不符合题意；选项D，冒泡一遍的数据为2，30，18，6，21，9，65，不符合题意。 变式1采用冒泡排序对一组数据进行排序，第一遍排序后的结果为2，19，4，55，6，7，11，13，32，那么该数组的原始顺序不可能是(　B　) A．19，4，55，6，7，11，2，13，32 B．2，19，4，55，13，11，32，6，7 C．19，4，55，2，6，7，11，13，32 D．19，4，55，6，7，11，13，32，2 【解析】 根据题目的第一遍排序的结果，利用冒泡排序的思想对选项的数据进行排序处理，排序后的数据对比题目的排序结果，选项B正确。 变式2某超市水果区有5 种水果，其价格依次为“9.2，4.0，8.5，1.8，2.5”，若采用冒泡排序算法对其进行升序排序，需要交换的总次数是(　A　) A．8次　　　　　B．6次　　　　　C．10次　　　　　D．2次 【解析】 根据冒泡排序算法思想，数据交换即为逆序对的个数，数据序列中存在8对逆序对，选项A正确。 　　2023·浙江1月选考列表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　) A．s[0]到s[5]的降序排列 B．s[1]到s[6]的降序排列 C．s[1]到s[7]的升序排列 D．s[2]到s[6]的升序排列 【解析】 易知外循环变量i 的取值范围是[1，6]。当第一轮比较(i 为1)时，内循环变量j 的取值范围是[1，5]，由于参与比较的两元素下标分别是j 和j－1，故列表中仅元素s[0]～s[5]从前向后进行比较，此时已可选出答案A。再观察分支语句条件s[j]>s[j－1]可知，当后一个数大于前一个数时要发生交换，故最终排序结果是降序。 变式1有如下Python程序段： a＝[19，3，10，9，15，12，10，18，10，20] n＝len(a) for i in range(n－1)： for j in range(i＋2，n，2)： if a[i]<a[j]： a[i]，a[j]＝a[j]，a[i] 执行该程序段后，列表a的内容是(　C　) A．[20，19，18，15，12，10，10，10，9，3] 　　B．[3，9，10，10，10，12，15，18，19，20] C．[19，20，15，18，10，12，10，9，10，3] 　　D．[20，15，19，10，18，10，12，10，9，3] 【解析】 由语句“for j in range(i＋2，n，2)”得知步长为2，实现奇偶位置分别排序；由语句“a[i]<a[j]”得知，这是降序排序，选项C正确。 变式22023·龙游中学检测有如下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－1]： s[j]，s[j－1]＝s[j－1]，s[j] 下列说法正确的是(　D　) A．整个加工过程总的交换次数为21 B．执行该程序段后，s 的值为[9，8，7，5，4，3，2] C．若s 的初始值已有序，则该算法的时间复杂度为O(1) D．每一遍加工中，最小的元素“上浮” 【解析】 根据s[j]<s[j－1]，可知该程序为升序排序、交换次数为5 次、时间复杂度为O(n2)，故选项D正确。 变式3有如下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) 执行该程序段后，输出的结果是(　C　) 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] 【解析】 由语句for j in range(5－i)可知由左到右冒泡，由s[a[j]]>s[a[j＋1]]可知， 把字符串s＝”ccbbac”中的字符升序排列， 相同时不交换位置， 排序结束后的字符串是”abbccc”，所以第一个位置是4， 而第二个位置是第一个”b”的位置2， 故选项C正确。 　　列表s 中包含n 个互不相等的元素，用Python 编程实现如下功能： s[0]到s[n－1]降序排序，当序列已经有序时结束排序，Python程序段如下： n＝len(s) for i in range(1，n)： for j in range()： if ： 　s[j]，s[j－1]＝s[j－1]，s[j] flag＝True if flag＝＝False： break 上述程序段中加框处可选的代码有： ①flag＝True　②flag＝False　③1，n－i＋1　④1，n－i　⑤s[j]<s[j－1]　⑥s[j]>s[j－1] 下列选项中，代码顺序正确的是(　B　) A．②④⑥　　　　B．②③⑥　　　　C．①④⑤　　　　D．①③⑥ 【解析】 根据该遍排序中是否有进行数据交换，利用逻辑变量flag 控制是否提前结束循环排序。由填空(3)处下方的代码“flag＝True”可知，当条件成立时，交换相邻数据，逻辑变量flag 赋值为True，故每遍排序开始前应将flag 赋值为False，故填空(1)处应填入“flag＝False”；填空(2)确定每次排序时比较的范围，因外循环变量i 的范围为[1，n)，当i＝1 时，比较的范围应为[1，n)，当i＝2 时，比较的范围应为[1，n－1)，以此类推，随着i 值的增加，排序范围的终值在缩小，故填空(2)处应填入“1，n－i＋1”；填空(3)处确定排序方式是“升序”或“降序”，由于比较的元素为s[j]与s[j－1]，若要实现降序排序，应将较大值换到前面，故填空(3)处应填入“s[j]>s[j－1]”，故本题选项B正确。 变式1下列Python代码采用冒泡排序对列表a中的n 个数据进行升序排序，则①②两处不可用的选项是(　B　) for i in range(①　　　　　)： for j in range(②　　　　　)： if a[j]<a[j－1]： 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 个数据的升序排序。 变式22023·开化中学检测小明对某校立定跳远的测试成绩进行排序，要求女生在前，男生在后，同性别按成绩降序排序。实现该功能的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] 则①、②处填入的代码分别为(　C　) 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]＝＝”女” 【解析】 根据题意可知，要求女生在前，男生在后，同性别按成绩降序排序。因此交换的标准是①(if 语句的第一个分支)：若性别相同按照成绩降序排序；②(if 语句的第二个分支)：若相邻的两个同学，女生在后，男生在前，则无论成绩如何也进行交换。因此②处代码的肯定在选项A、C 中选择。另外考虑到外循环变量i 的取值范围是从0 开始的，且代码是a[j]和a[j－1]的交换，若此时j 的取值选A，则数组a 中最后一名同学不能参与排序，从而排除选项A，故选项C正确。 　　小丁是一位电影爱好者，尤其钟爱喜剧片和动作片。他设计了一个程序，根据某部电影的镜头数据预测出影片类型，这类操作可利用K—— 近邻分类算法来实现，该算法的核心思想是：一个样本在特征空间中的K 个最相邻的样本中的大多数属于某一类别，则该样本也属于这个类别。小丁读取“movie.csv”数据集文件，如图1 所示，是一些电影的搞笑镜头和打斗镜头数目及类型。现要实现如下功能：输入某部电影的搞笑镜头和打斗镜头数目后，输出可能的类型，如图3 所示，并绘制该数据集文件和输入的电影在平面直角坐标系的分布特点图，如图2 所示。 例如，输入搞笑镜头40 和打斗镜头40，判断属于哪类，可通过以下步骤实现： ①计算点(40，40)和其余所有点的距离(两点间的距离计算公式： d12＝)； ②将所有样本按照距离升序排序； ③假设K＝3，取前K 个距离的样本； ④统计出在前K 个距离中，出现频次最多的类别，则(40，40)就属于该类别，可能是喜剧片。 (1)若输入的搞笑镜头为20，输入的打斗镜头为80，则该影片可能是　动作片　(选填：喜剧片/动作片)。 (2)实现上述功能的Python 程序如下，请在横线处填入合适的代码。 import pandas as pd import numpy as np from math import sqrt movie＝pd.read_csv(”movie.csv”) x＝int(input(”请输入搞笑镜头：　”)) y＝int(input(”请输入打斗镜头：　”)) dist＝[] for i in range(len(movie))： d＝sqrt((x－movie.funny[i])**2＋①　(y－movie.action[i])**2 或(y－movie[”action”][i])**2或(y－movie.at[i，”action”])**2　) dist.append(d) movie[”dis”]＝dist movie_list＝np.array(movie).tolist() #将df 对象转成列表，如图4 所示 K＝3 for i in range(K)： for j in range(len(movie_list)－1，i，－1)： if ②　movie_list[j][3]<movie_list[j－1][3] 或movie_list[j][－1]<movie_list[j－1][－1]　： movie_list[j]，movie_list[j－1]＝movie_list[j－1]，movie_list[j] funny＝0；action＝0 for i in range(K)： if ③　movie_list[i][2]＝＝”喜剧片” 或 ”喜剧片” in movie_list[i]　： 　funny＋＝1 else： action＋＝1 if funny>action： print(”该影片可能是喜剧片”) else： print(”该影片可能是动作片”) #绘图代码略 【解析】 (1)根据题图2可知，该影片是动作片。 (2)①这里是计算两点间的距离，根据题目给出的公式，这里代码为：(y－movie.action[i])**2，根据转换后的DataFrame 数据特点，y 点坐标还可以写成：movie.at[i，'action'] 或者movie['action'][i]。 ②这里是根据距离升序进行排序，根据前后代码，应该是冒泡排序，填写的代码是：movie_list[j][3]<movie_list[j－1][3] #距离数据在索引为3 的位置。 ③统计前K 个样本中“喜剧片”和“动作片”的数量，根据后面的代码和相关的变量名，变量funny 代表“喜剧片”的数量，action 代表“动作片”的数量，所以这里应该填入的代码是movie_list[i][2]＝＝”喜剧片”。 变式1拼接最大数字问题。有n(n<100)个非负整数，将其按照字符串拼接的方式拼接为1 个整数。小赵设计了一个算法，使得拼接得到的整数最大。例如：“32，94，128，1286，6，71” 可以拼接得到的最大整数为“94716321286128”。请回答下列问题： (1)121，12，3拼接得到的最大整数为　312121　。 (2)实现上述功能的Python程序如下，请在横线处填入合适的代码。 def bubble_sort(a)： for i in range(len(a)－1)： for j in range(①　len(a)－1，i　，－1)： if judge(a[j]，a[j－1])： a[j]，a[j－1]＝a[j－1]，a[j] def judge(x，y)： if ： 　　return True else： return False n＝int(input(”n＝”)) #产生n 个0～1000的随机整数存入列表a中，代码略 bubble_sort(a) ans＝”” for i in a： ans＋＝②　str(i)　 print(”拼接得到的最大整数为：　”，ans) (3)上述程序中加框处代码有误，请改正：　str(x)＋str(y)>str(y)＋str(x)或 str(x)＋str(y)>＝str(y)＋str(x)　。 【解析】 (1)要拼接得到最大整数， 则字符“3”一定放在最前面， 接着将剩余两个字符串拼接后进行大小比较，“12121”＞“12112”，所以拼接得到的最大整数为312121。 (2)①空考查冒泡排序每趟边界值的推导，由步长为－1可以推断出此处冒泡排序的方向为从后往前冒。每趟进行比较的元素为j号位和j－1号位，可推出第一趟的排序边界为len(a)－1到1， 0号位元素就位；此处需要注意range函数左取右不取这一特点， 可以得到填空处答案为len(a)－1，i；②空根据题意，要将整数按照字符串拼接的方式进行连接， 因此需将i转换为字符串， 因此填入str(i)。 (3)根据题意， 要将整数按照字符串拼接的方式进行连接， 因此需将x和y转换为字符串连接后再进行大小比较。故加框处程序应该修改为str(x)＋str(y)>str(y)＋str(x)或str(x)＋str(y)>＝str(y)＋str(x)。 变式22023·衢州二中检测小明所在的班级共有20名男生，要参加学校举办的拔河比赛，赛前根据体重分成AB两组进行训练，要求每组10人，且每组男生的体重之和尽量接近。小明设计了如下算法： ①初步分组：将所有男生按体重从高到低排序，并以ABAB… 进行初步分组； ②计算体重差：计算每组对应两个男生的体重差； ③交换学生：按体重差从高到低判断是否交换学生。 例如，20名男生的体重(单位：kg)从高到低为：95，93，93，90，90，90，84，83，83，78，77，75，74，69，64，61，61，60，56，55。 步骤 体重 体重和 初步分组 A组 95 93 90 84 83 77 74 64 61 56 777 B组 93 90 90 83 78 75 69 61 60 55 754 体重差 2 3 0 1 5 2 5 3 1 1 23 交换学生 否 否 否 是 是 否 是 否 否 否 最终分组 A组 95 93 90 83 78 77 69 64 61 56 766 B组 93 90 90 84 83 75 74 61 60 55 765 　　小明按照以上算法编写Python程序如下，请在横线处填入合适的代码。 def group(student)：　　#初步分组 a＝[]；b＝[] i＝0 while i<len(student)： a．append(student[i]) b．append(student[i＋1]) ①　i＋＝2　 return a，b def cal_diff(a，b)：　　 #计算体重差并降序排序 d＝[] for i in range(len(a))： d．append([i，a[i]－b[i]]) for i in range(len(d)－1)： for j in range(0，len(d)－i－1)： if ②　d[j][1]<d[j＋1][1]　 　　d[j]，d[j＋1]＝d[j＋1]，d[j] return d def change(d，a，b)：　　 #标记是否交换 k＝(sum(a)－sum(b))//2 f＝[0]*len(d)　　 ssum＝0 for i in range(len(d))： ssum＋＝d[i][1] if ssum>k： ssum－＝d[i][1] else： ③　f[d[i][0]]＝1　 if ssum＝＝k： break return f student＝[95，93，93，90，90，90，84，83，83，78，77，75，74，69，64，61，61，60，56，55] qA，qB＝group(student) print(”初步分组后A组体重：　”，qA，”和为：　”，sum(qA)) print(”初步分组后B组体重：　”，qB，”和为：　”，sum(qB)) diff＝cal_diff(qA，qB) flag＝④　change(diff，qA，qB)　 for i in range(len(flag))：　　#交换 if flag[i]＝＝1： qA[i]，qB[i]＝qB[i]，qA[i] print(”交换后A组体重：　”，qA，”和为：　”，sum(qA)) print(”交换后B组体重：　”，qB，”和为：　”，sum(qB)) 【解析】 ①group()函数的功能是将已经排序好的学生分为A、B组， 每次循环取两个值，故i的值每次加2。②考查冒泡排序，由列表d中体重差值存在索引值为1处，题干也说了体重差值从高到低判断，故应填入d[j][1]<d[j＋1][1]。③结合题目给的例子： 步骤 体重 体重和 初步 分组 A组 95 93 90 84 83 77 74 64 61 56 777 B组 93 90 90 83 78 75 69 61 60 55 754 体重差 2 3 0 1 5 2 5 3 1 1 23 交换学生 否 否 否 是 是 否 是 否 否 否 最终 分组 A组 95 93 90 83 78 77 69 64 61 56 766 B组 93 90 90 84 83 75 74 61 60 55 765 初步分组后A，B组的体重差为23，要让两组平均，就需要A组取23//2＝11(即变量K)的体重值到B组。在cal_cliff()中已经根据体重差降序排序，change()函数则是从d中逐个取值并累加到ssum中，被ssum统计时用到的位置就是需要交换的位置， 需要将f中对应的位置标记为1 。故结果为f[d[i][0]]＝1。 ④调用自定义函数change()， 返回需要交换的位置， 根据change参数列表，可得答案为change(diff，qA，qB)。 |随|堂|检|测| 1．篮球联赛中，有5个班级的比赛积分依次为14，11，13，8，9，若采用冒泡排序算法对其进行从小到大的排序，则完成第二遍时的结果是(　C　) A．8，11，13，14，9　　B．8，9，13，14，11　　C．8，9，14，11，13　　D．14，13，11，9，8 【解析】 利用冒泡排序的思想对数组按从后往前比较方式进行升序排序，一遍排序使得最小的数据排至最前端位置，第二遍排序使第二小的数据排至第二个位置，故选项C正确。 2． 有如下Python 程序段： import random n＝random.randint(1，4) a＝[7，2，7，3，9，4] for i in range(1，n)： for j in range(0，6－i)： if a[j]<a[j＋1]： a[j]，a[j＋1]＝a[j＋1]，a[j] 执行该程序段后，数组 a 中的元素不可能是(　A　) A．9，7，7，4，3，2 B．7，7，3，9，4，2 C．7，9，7，4，3，2 D．7，2，7，3，9，4 【解析】 n 的范围是[1，4]，当n＝1 时，range(1，1)，1－1＝0， 循环次数为0。把n＝2，3，4，循环1、2、3 次的结果分别写出来，故选项A符合题意。 3．数组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－2]： a[j]，a[j－2]＝a[j－2]，a[j] 该程序段实现的功能是(　A　) A．仅对奇数位元素升序排列 B．仅对偶数位元素升序排列 C．奇数位元素升序，偶数位元素降序排列 D．奇数位元素降序，偶数位元素升序排列 【解析】 根据代码“a[j]<a[j－2]”以及后面的数据交换可知，这是冒泡升序排序，方向是从后往前冒泡，且中间隔着一个数进行冒泡排序，最前面一个有序的是元素a[0]，然后是a[2]，a[4]，…。根据题目描述，这属于奇数位元素，因此排序结束仅有奇数位元素实现升序，而偶数位置元素未被处理，依然保持原始状态。故选项A正确。 4．2023·温岭中学检测列表中有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 下列选项中，代码顺序正确的是(　D　) A．①④ B．①⑥ C．②⑤ D．③⑥ 【解析】 排序遍数可从①②③中选择，每遍的比较范围可从④⑤⑥中选择。若有n 个元素，①③都可以保证排序n－1 遍，但②只能排序n－2遍，故②不合理。④⑤⑥选项均实现从前向后排序，每遍排序需要先比较第0 号与第1 号元素，由“s[j]>s[j－1]”可知，第一遍的比较范围要为1～n－1，因此应为①⑤组合或③⑥组合，故选项D 正确。 5． 银行技术部继续编写风险控制算法，根据申请贷款公司的收益率和信用度，从多个申请公司中挑选前n名公司发放贷款，发放对象必须同时满足以下两个条件： 条件1：公司的收益率大于rate%； 条件2：公司的信用度在rank 等级及以上(A 等高于B 等，B 等高于C 等……)。 则将满足条件1 和条件2 的公司信息按收益率降序输出。 如所有公司信息为： [[1，20.0，'C']，[2，32.0，'A']，[3，46.0，'B']，[4，44.0，'A']] 满足等级为A，且收益率大于20的输出情况为：[[4，44.0，'A']，[2，32.0，'A']] (1)实现上述功能的Python 程序如下，请在横线处填入合适的代码。 (2)程序中加框处代码有误，请改正：　info[i][1]<＝rate or info[i][2]>rank　。 #info＝[[1，30.0，'C']， [2，44.0，'B']，…] 其中[1，30.0，'C']分别表示公司编号、收益率及信用度等级，代码略 m＝len(info) rate＝float(input('输入收益率要求：　')) rank＝input('输入等级要求：　') for i in range(m)： for j in range(m－1，①　i，－1　)： if info[j][2]<＝rank： if info[j][1]>info[j－1][1] and info[j－1][2]<＝rank or ②　info[j－1][2]>rank　： 　　　info[j]，info[j－1]＝info[j－1]，info[j] if ： 　m＝i 　break if i>0： 　　print(”符合要求的公司为：　”，③　info[：m]或info[0：m]　) else： print(”当前无符合要求的公司！　”) 【解析】 (1)①根据冒泡排序算法的知识点，观察内循环，冒泡的方向为从后往前，结合range函数左闭右开的原则，终值应为1，且步长为－1。②对排序做筛选，若info[j－1][2]>rank，则不符合等级要求，不用比大小直接交换到后面。③根据冒泡排序算法，有序的已经交换到最前面，切片遵循左闭右开。 (2)结束循环除了收益率不满足要求，也可能是等级不符合要求，这两项任何一项不满足，排序就可以结束了。 学科网（北京）股份有限公司 $$