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

高效作业16 [第16课　排序1——冒泡排序及变形] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 【A级　新教材落实与巩固】 1．对某数据序列进行冒泡排序，第一轮排序后的结果是 31，24，23，15，20，10，那么原数据序列不可能的是(　 　) A．24，23，15，31，10，20 B．23，24，15，20，31，10 C．24，31，23，15，10，20 D．24，23，15，20，31，10 B 【解析】 从经过第一轮排序后的结果可知，这是降序排序，但排序方向未知，从前向后排序和从后向前排序都可以；选项A，从后向前实现；选项C，从前向后实现；选项D，从后向前实现；选项B不可行。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2． 采用冒泡排序算法，对某数组数据进行排序，经过一轮排序后的结果是“2，3，9，5，6，7”，那么下列说法不正确的是(　 　) A．这轮排序有可能没发生数据交换 B．这轮排序有可能只发生了1 次数据交换 C．排序结束后，数据是升序的 D．完成全部排序后，数据交换的次数和冒泡的方向无关 A 【解析】 从经过一轮排序后的结果是“2，3，9，5，6，7”可知，最小数在最前面，故该冒泡排序是从后往前冒泡，升序排序。如果原始数据的最小数2 不在最前面，那么经过冒泡一定会发生交换， 如果初始数据为“2，3，9，5，6，7”，此数据是无序的，那么经过第一轮冒泡，肯定也会发生交换，故第一轮一定发生了交换，选项A错误。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 3．2023·温州中学检测有互不相等的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]的升序排列 【解析】 分析冒泡排序内循环的代码，是从左(前)向右(后)冒泡、降序。外循环只进行了5次，所以只有最后5个数(s[5]到s[9])是有序的。选项C正确。 C 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 4．有如下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]<b[j＋1]： 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 【解析】 由交换条件“a[j]>a [j＋1] and a[j]＝＝a[j＋1] and b[j]<b[j＋1]”可知，优先按数组a升序排序， 当数组a的值相等时，再按照数组b降序排序，排序过程无特殊情况，选项C正确。 C 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 5．有如下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'] 【解析】 根据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']，选项C正确。 C 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 6．有如下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] 【解析】 本题的关键是注意排序的条件“a[i]%2＝＝0”，以及排序的范围和方向“for j in range(i)”，从左往右。最后一个3 不参与排序，倒数第二个数排序后应该是8，选项C正确。 C 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 7．执行以下的Python 程序后，列表 a不可能是(　 　) from random import * a＝[] for i in range(6)： a．append(randint(1，9)) n＝len(a) k＝randint(0，2) for i in range(2)： for j in range(n－1－k－i)： C if a[j]>a[j＋1]： a[j]，a[j＋1]＝a[j＋1]，a[j] print(a) A．[2，1，6，8，8，6] B．[1，4，4，8，9，9] C．[2，3，8，7，8，6] D．[1，2，5，7，4，5] 【解析】 产生6 个[1，9]范围内的随机数据，k 的范围为[0，2]，冒泡一共执行2 趟排序，k 的作用为设置比较范围。当a[j]>a[j＋1]时交换数据可得出排序为大数下沉的升序排序，执行二次，排序范围内最后二个数有序。即a[5]、a[4]或a[4]、a[3]或a[3]、a[2]有序，选项C符合题意。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 8．某排序算法的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]＝a[j－1]，a[j－1] 执行该程序段后，下列说法正确的是(　 　) A．交换过位置的数据，可能会再回到其初始位置 B．执行完成后，数组元素a[1]到a[n]从小到大排列 C．若n 为6，整个排序过程总的比较次数是30 D．整个排序过程总的交换次数至少为1 A 【解析】 分析代码，基本的冒泡排序，排序方向从左往右，降序；选项A，冒泡排序，数据可能会再回到其初始位置，选项正确；选项B，数组元素a[1]到a[n]从大到小排列，选项错误；选项C, 比较次数为(1＋2＋3＋4＋5)＝15，选项错误；选项D，如果原数据已经有序了，不会发生交换，选项错误。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 9．2023·天台中学检测最近，小蓝所在的学校进行了体检，获得了全校学生的身高和体重信息。小蓝利用该信息计算全校学生的身体质量指数BMI。公式为BMI＝体重/身高2，其中身高单位为m，体重单位为kg。若BMI值小于18，则偏瘦；若BMI值在18到24之间，则正常；若BMI值大于24，则偏胖。数组a中存储着全校学生的学号和BMI信息，格式为[['0101'，19.2]，['0102'，18.5]，['0103'，20.1]，…]。其中每条数据的第一项为学号，第二项为BMI值。数组a已经按学号升序排序，现要求按照BMI值进行降序排序，BMI相同情况下仍然按照学号保持升序。则下列Python程序段可以实现该功能的是(　 　) D A．for i in range(1，n)： for j in range(n－i)： if a[j＋1]>a[j]： a[j]，a[j＋1]＝a[j＋1]，a[j] B．for i in range(1，n)： for j in range(n－i)： if a[j][1]>a[j＋1][1]： a[j]，a[j＋1]＝a[j＋1]，a[j] C．for i in range(1，n)： for j in range(n－1, i－1，－1)： if a[j][1]<＝a[j－1][1]： a[j]，a[j－1]＝a[j－1]，a[j] D．for i in range(1，n)： for j in range(n－1，i－1，－1)： if a[j][1]>a[j－1][1]： a[j]，a[j－1]＝a[j－1]，a[j] 【解析】 选项A，比较的关键字错误，条件表达式应该修改为：if a[j＋1][1]>a[j][1]，选项错误；选项B，按照BMI 升序排序，与题干要求不符，选项错误；选项C，题干要求BMI 相同的情况下仍然按照学号保持升序，条件表达式应该修改为：if a[j][1]<a[j－1][1]，选项错误。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 10．有如下Python 程序段： m＝2；lst＝[7，5，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－1]： lst[j]，lst[j－1]＝lst[j－1], lst[j] 　 break 执行该程序段，加框处语句被执行的次数是(　 　) A．2 B ．3 C．4 D．6 C 【解析】 根据代码可知，这是冒泡升序排序，方向是从后往前冒泡。但是由于加上了加框处的if 语句后，满足条件“i >＝m and lst[i]！＝lst[i－1]”后，排序过程将会终止。当i＝0 时，进行第一遍冒泡，结束后lst＝[1，7，5，4，3，3，6]，然后执行了加框处代码一次，但由于不满足条件，因此继续进行排序。第二轮排序，i＝1，结束后，lst＝[1，3，7，5，4，3，6]，此时执行加框处代码，不满足条件，继续下一轮排序。第三轮排序，i＝2，结束后，lst＝[1，3，3，7，5，4，6]，执行加框处代码后，由于lst[2]＝＝lst[1]，因此继续下一轮排序。第四轮排序后，i＝3，lst＝[1，3，3，4，7，5，6]，第四次执行加框处代码，此时条件满足，执行break 后退出循环，排序结束。选项C正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 11．使用列表a和列表b分别存储学生的总分和考号，已知考号为b[i]的学生的总分为a[i]，使用Python编写程序实现如下功能：将成绩数据按总分降序排序、总分相同按学号升序排序，代码如下。 n＝len(a) for i in range(1，n)： for j in range(0，n－i)： 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]<a[j＋1]　 ④b[j]<b[j＋1] ⑤b[j]＝＝b[j＋1]　 ⑥b[j]>b[j＋1] 下列选项中，代码顺序正确的是(　 　) A．③②④ B．①⑤⑥ C．③②⑥ D．①⑤④ C 【解析】 题目要求为“将成绩数据按总分降序排序、总分相同按学号升序排序”，而填空处所需填入的条件为需要交换的情况。因此可知，第一种情况，j号位的总分小于j＋l号位，此时需要交换，转换为表达式为： a[j]<a[j＋1]；第二种情况，j号位的总分和j＋l号位的总分相同，此时若j号位的学号大于j＋l号位，则需要交换，转换为表达式为a[i]＝a[j＋1] and b[j]>b[j＋l]。选项C正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 12．下列程序段的功能对数组a进行升序排序： a＝[3，10，8，5，7 ] for i in range(1，len(a))： a[j]，a[j＋1]＝a[j＋1]，a[j] 上述程序段中加框处可选的代码有： ①0，len(a)－i，1　 ②1，len(a)－i＋1，1 ③len(a)－1, i－2，－1　 ④a[j]>a[i＋1] ⑤a[j]<a[i＋1] 下列选项中，代码顺序正确的是(　 　) A． ①④ B． ②④ C． ③⑤ D．①⑤ A 【解析】 程序段中，外循环1的初值从1开始，交换的是j和j＋1位置的数据。题目要求升序，既可以采用“上浮”，也可以采用“下沉”的方式。如果采用“下沉”，则每一趟比较都需要从a[0]和a[1]开始比较，因此j的初值为0，终值为len(a)－i－1，故(1)空填①，“下沉”过程中将大的数交换到底部，a[j]>a[j＋1]时交换数据，(2)空填④，选项A正确。如果采用“上浮”，则每－趟比较都需要从a[len(a)－2]和a[len(a)－1]开始，因此j的初值为len(a)－2，终值为i－1 ，因此j的取值范围为(len(a)－2，i－2，－1)。“上浮”过程中将小的数据交换到顶部，a[j]>a[j＋1]时交换数据。答案中无“上浮”组合，故选项A正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 13．2023·丽水中学检测双调冒泡：对n个元素的数组a进行升序排序，第一遍将最小的数移至第1个位置，将第二小的数移到第n个位置；第二遍将余下元素中的最小数和次小数分别移至第2个和第n－1个位置，以此类推，直到所有数组元素都完成排列。Python程序实现部分代码如下： m，n＝0，len(a)－1 while m<n： for i in range(n，m，－1)： a[i]，a[i－1]＝a[i－1]，a[i] m＋＝1 if a[i]<a[i＋1]： a[i]，a[i＋1]＝a[i＋1]，a[i] n－＝1 上述程序段中加框处可选的代码有： ①a[i]>a[i－1]　 ②a[i]<a[i－1] ③range(m－1，n)　 ④range(m，n) ⑤range(m，n＋1) 下列选项中，代码顺序正确的是(　 　) A．②④　　 B．②③　　 C．①⑤　　 D．①③ A 【解析】 m、n是列表边界，当m＝＝n时排序结束；第1个for循环实现将最小值交换到m位置，后一项小于前一项时交换，(1)处为a[i]<a[i－1]；第2个for循环实现将剩下最小值交换到n位置，前一项小于后一项时交换，(2)处为range(m，n)。选项A正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 【B级　素养形成与评价】 14．为了研究冒泡排序过程中数据元素的“移动”情况，有如下程序，其功能如下：先输出排序前的数据(存储在数组a 中)，然后输入初始位置(即下标值)，程序显示制定初始位置的数据在排序过程中的位置变化情况，并输出排序后的数据。程序运行界面如下： 请输入数据的规模：10 排序前的数组状态：[75，66，90，76，45，56，18，67，24，71] 请输入需要观察的下标：3 排序后的数组状态：[18，24，45，56，66，67，71，75，76，90] 排序过程中的指定位置数值的变化情况：3－－>4－－>5－－>6－－>7－－>8－－>9－－>8 a＝[] n＝int(input(”请输入数据的规模：　”)) for i in range(0，n)： x＝random.randint(10，99) a．append(x) print(”排序前的数组状态：　”，a) pos＝int(input(”请输入需要观察的下标：　”)) ans＝str(pos) for i in range(0，n－1)： for j in range(n－1，i，－1)： if a[j]<a[j－1]： tmp＝a[j] ①____________ a[j－1]＝tmp if pos＝＝j： pos＝j－1 ans＝ans＋”－－>”＋str(pos) ②______________： pos＝j ans＝ans＋”－－>”＋str(pos) print(”排序后的数组状态：　”，a) print(”排序过程中的指定位置数值的变化情况：　”，ans) (1)程序中横线①处应填写的代码为_______________； 横线②处应填写的代码为___________________。 (2)若数据规模为5，且数组a 中的原始数据为[21，5，36，8，7]，然后输入下标3，则该程序运行后输出的结果是_______________________ 。 a[j]＝a[j－1] elif pos＝＝j－1 3－－>4－－>3－－>2 【解析】 (1)①实现a[j]与a[j－1]的交换。②因为进行了交换，如果pos＝＝j，则pos变为j－1；如果pos＝＝j－1，则pos变为j。 (2)题目实现由后往前进行交换，排序过程为： 第1趟：5 21 7 36 8 第2趟：5 7 21 8 36 第3趟：5 7 8 21 36 下标3的值为8，变化过程为：3－－>4－－>3－－>2。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 15．小萌通过“问卷星”收集到了一些学生数据，如图1所示。在按关键字“用户名”进行排序的过程中，对数据进行整理、删除重复数据的操作，处理结果如图2所示。 (1)在数据整理时，常见的数据问题有___________(多选，填字母)。 A．数据缺失 B．数据重复 C．逻辑错误 D．格式不一致 (2)实现上述功能的Python程序如下，请在横线处填入合适的代码。 a＝[] csv_file＝open(”xuehao.csv”，”r”，encoding＝'utf——8') flines＝csv_file.readlines() # 将文件中所有数据按行读入flines 中 csv_file.close() # 关闭文件 ABCD #将每个数据行中的各项信息以“，”作为分隔符切割成字串存入列表a中 for line in flines： tmp＝list(line.strip(” ”).split(”，”)) a．append(tmp) n＝len(a) i＝1；m＝n－1 #变量 m表示删除重复数据后的实际个数 while i<n： for j in range(m，i，－1)： if ①_____________________________________： 　　　tmp＝a[j]；a[j]＝a[j－1]；a[j－1]＝tmp elif a[j][4]＝＝a[j－1][4]: a[j]＝a[m] ②______________________ i＋＝1 for i in range(m＋1)： print(a[i]) a[j][4]<a[j－1][4] 或 a[j－1][4] > a[j][4] m－＝1 或 m＝m－1 【解析】 (1)常见的数据问题有数据缺失、数据重复、数据异常、逻辑错误、格式不一致等，全部选项正确。 (2)列表a的存储结构为：a＝[[”高二”，”3班”，”xxx”，”2018xxxxx”，”xyzxxxxxx”]，[”高二”，”2班”，”xxx1”，”2018xxxxx1”，”xyzxxxxxx1”]…]，按照用户名升序排序，①处答案为a[j][4]<a[j－1][4] 或 a[j－1][4]>a[j][4]；② 条件“a[j][4]＝＝a[j－1][4]”成立说明有重复用户名，需要去重，总数减少，答案为m－＝1或 m＝m－1。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 16．2023·慈溪中学检测期末考试临近，许多学生要找陈老师答疑，陈老师将学生答疑的时间段用“time.txt”文件保存，数据如图所示。若一个学生的答疑开始时间为19：20，结束时间为19：50，另一个学生的答疑开始时间为19：50，结束时间为20：00，则陈老师可以为这两个学生答疑，由于有些学生报名的答疑时间有冲突，陈老师想要知道自己最多能为几名学生答疑，编写了如下Python程序。 (1)观察如图所示的数据，陈老师最多能为_____名学生答疑。 (2)请在横线处填入合适的代码。 def convert(a)：#将时间格式转为分钟，如将20：10转为1210，存储到变量t中后返回 for i in range(len(a))： if a[i]＝＝”：”： break 　　　①_______________________________ 　　　return t 4 t＝int(a[：i])*60＋int(a[i＋1：]) def sort(tm)：　 #排序 for i in range(len(tm))： for j in range(0，len(tm)－i－1)： if tm[j][2]>tm[j＋1][2]： ②__________________________________ return tm def solve(tm)： ans＝0；t＝－1 for i in tm： tm[j]，tm[j＋1]＝tm[j＋1]，tm[j] if ③_____________： 　 ans＋＝1 　 t＝i[2] return ans f＝open(”time.txt”，”r”，encoding＝”utf——8”) tm＝[]；flag＝False for i in f： if flag： i[1]>＝t i＝i.strip().split(”，”)#以，为分隔符分割字符串 i[1]＝convert(i[1])；i[2]＝convert(i[2]) tm.append(i) flag＝True tm＝sort(tm) ans＝solve(tm) print(”最多能为”，ans，”名学生答疑　！　”) 【解析】 (1)从截图看，第一名解答的学生为张**, 结束时间为18：20；第二名解答的学生为张*，结束时间为19：35；第三名解答的学生为施*, 结束时间为20：08；第四名解答的学生为马**, 结束时间为20：20。合计共4名同学完成答疑， 其他同学时间冲突无法答疑。 (2)①自定义函数convert()将时间字符串格式转为分钟数值，并存储到变量t后返回。遍历字符串，找到“：”的下标位置， 前面的小时数乘以60得到分钟数值， ②处为冒泡排序，通过“tm[j][2]>tm[j＋l][2] ”(答疑结束时间先后)比较大小，按升序排列，故交换tm[j]、tm[j＋l]的值。 ③在二维列表f中，每个数据元素的0号位置存储姓名，1号位置存储答疑开始时间，2号位置存储答疑结束时间。依次遍历已完成排序的列表f, 第一名同学肯定进入答疑状态， 完成后(即答疑结束时间)，新同学的答疑开始时间大于等于前一名同学答疑的结束时间， 则该同学进入答疑状态， 故收集上一名同学答疑的结束时间并存入t中， 若当前遍历的同学答疑开始时间小于等于t，更换新的答疑同学， 计数器加1, 并更新结束时间为t＝i[2]。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 17． 校园文化节开展诗词比武大会。每个参赛学生需要参加两轮比拼，即初赛和复赛。初赛成绩分为笔试和面试两个部分，笔试和面试结束后分别将成绩降序排列后进行公示，如表1所示。而后根据规则计算得到初赛成绩(初赛成绩计算规则为：初赛成绩＝笔试成绩×60%＋面试成绩×40%)。根据初赛成绩的高低，排名位于所有参赛选手前10%的同学进入复赛。复赛将进行现场才艺表演，以评委、观众打分的形式最终决出优胜名单。 计算得到进入复赛学生名单的部分Python程序代码如下，请在横线处填入合适的代码。 #分别将笔试和面试公示成绩存入链表a和链表b中，其中链表a和链表b的每个节点都含有三个数据项，即参赛者编号、成绩得分和后继指针，如表2所示；变量n表示参赛的总人数，代码略 cj＝[[”” for i in range(2)] for j in range(n)] head＝0 p＝head m＝0 while p！＝－1： q＝head while q！＝－1： if b[q][0]！＝a[p][0]： ①_____________ else： q＝b[q][2] cj[m][1]＝str(a[p][1]*0.6＋b[q][1]*0.4) cj[m][0]＝a[p][0] m＝m＋1 break p＝a[p][2] for i in range(n)： for j in range(n－1，0，－1)： if ②_______________________： 　 cj[j]，cj[j－1]＝cj[j－1]，cj[j] if ③_____________________________________： cj[j][1] >＝cj[j－1][1] i>＝n*0.1 and cj[i][1]<cj[i－1][1] break j＝0 while j<i： print(cj[j][0]) j＝j＋1 【解析】 ①双重while循环将遍历链表a和链表b，找到同一参赛选手的笔试和面试成绩，计算总成绩，并存储到列表cj中，cj的结构为 [[”scXXX”，89.5]，[”scXXy”，84.2]…]；填空处遍历链表b，当编号不同，则链表b访问下一节点，答案为q＝b[q][2]。双重for循环实现按成绩降序排序，且求解前10%的同学；②处为比较条件，答案为cj[j][1]>＝cj[j－1][1]；③处求解前10%的同学，由于是全排序且存在同分的现象，使用“i>＝n*0.1”时，可能有选手满足条件也保留；但当i>＝n*0.1时，如果当前位置i处的分数小于i－1位置成绩时，排序结束，答案为 i>＝n*0.1 and cj[i][l]<cj[i－1][1]。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 18．字符串分段。输入一串仅由小写字母组成的字符串s，将这个字符串划分为尽可能多的小片段，要求同一个字母只出现在其中的一个片段中，并按照分段顺序逐行输出分段结果。程序运行界面如下图所示。 (1)实现上述功能的Python 程序如下，请在横线处填入合适的代码。 s＝input(”请输入一串仅包含小写字母的字符串：　”) c＝0 p＝[－1]*52 #数组p 用来记录各个小写字母出现的起始位置和结束位置 #a[0]记录a 出现的起始位置，a[1]记录a 出现的结束位置，依次类推 for i in range(0，len(s)): #记录各字符第一次和最后一次出现的位置 a＝①__________________________________ if p[2*a]＝＝－1： p[2*a]＝i else： p[2*a＋1]＝i for i in range(0，26)： if p[2*i]>p[2*i＋1]： ord(s[i])－97 或ord(s[i])－ord(”a”) p[2*i＋1]＝p[2*i] #只出现一次的字符，起始位置就是结束位置 if p[2*i]！＝－1： c＋＝1 for i in range(0，c): #将字符位置按照出现的起始位置升序排序 for j in range(25，i，－1)： if p[2*j]>－1： if p[2*(j－1)]>p[2*j] or②______________________： p[2*(j－1)]，p[2*j]＝p[2*j]，p[2*(j－1)] p[2*(j－1)＋1]，p[2*j＋1]＝p[2*j＋1]，p[2*(j－1)＋1] t1，t2＝p[0]，p[1] #字符串分段 p[2*(j－1)]＝＝－1 for i in range(1，c)： if p[2*i]<t2 and p[2*i＋1]>t2： ③_________________ elif p[2*i]>t2： print(s[t1：t2＋1]) t1，t2＝p[2*i]，p[2*i＋1] print(s[t1：t2＋1]) (2)运行程序后，若输入的字符串s 为“hshjhqueeqabaa”，输出的结果一共有_____行，其中，第二行显示结果为_________。 t2＝p[2*i＋1] 3 queeq 【解析】 (1)①根据注释“记录各字符第一次和最后一次出现的位置”和相应的代码“if p[2*a]＝＝－1: p[2*a]＝i”可知，此处代码应该是将相应字符转换为对应的数组索引(下标)，即a＝ord(s[i])－97；②程序代码采用冒泡排序。根据题意和前后代码，此时除了按起始位置升序排序外，还应该将没有出现过的字符通过排序放到数组的尾部。所以往后移动的除了“p[2*(j－1)]> p[2*j]”外，另外满足“p[2*(j－1)]＝＝－1”(没有出现过的字符)的也要后移；③根据题意，再根据输出语句“print(s[t1：t2＋1])”和输出条件“p[2*i]>t2”可知，此处代码是要确定某个片段的起点t1 和终点t2。 而题目中对某个片段的要求是：同一个字母只出现在其中的一个片段中。所以当片段的终点t2介于后一个字符的起点和终点之间时，要将片段的结束位置更新为后一个字符的结束位置：t2＝p[i*2＋1]，依次类推。直到t2 小于下一个字符的起点(p[i*2]>t2)时，输出片段并更新下一个片段的起点和终点。 (2)根据题意要求，字符串“hshjhqueeqabaa”可以分成三段：“hshjh”“queeq”“abaa”，第2 段是“queeq”。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 19．2023·杭四中学检测某群以投票方式评选优秀作品，每张选票仅填一个作品编号，得票数过半的获最具人气奖。小李和小王收集了全部选票，其中小李已将收集的选票按作品编号非降序排序，小王收集的选票未排序。现要求将全部选票按作品编号非降序排序，找出获最具人气奖的作品编号。 编写Python 程序，实现上述功能。运行程序，首先分别从文件(如图所示)中读取两位同学收集的选票编号并显示在屏幕上，小李收集的选票在前，小王收集的选票在后；接着按作品编号非降序显示全部选票；最后在屏幕末行显示最具人气奖的作品编号。 65 (1)实现上述功能的部分Python程序如下，请在横线处填入合适的代码。 (2)程序中加框处代码有误，请改正：____________。 a＝[””] c＝[””]*100 m＝n＝0 for line in open(＂vote——A.txt＂，＂r＂)： #读取小李收集的选票数据 a．append(line.strip(＂ ＂)) m＋＝1 print(a[m]) print(”从A 中读取”，m，”条数据，　END ”) (n＋1)//2 for line in open(”vote——B.txt”，”r”)：　 #读取小王收集的选票数据 a．append(line.strip(” ”)) n＋＝1 print(a[m＋n]) print(”从B 中读取”，n，”条数据，　END ”) n＋＝m for i in range(m＋1，n)： for j in range(n－1，i－1，－1)： ①_____________ k＝j＋1 if a[k]<＝a[j]： a[k]，a[j]＝a[j]，a[k] print(”排序后全部选票： ”) for i in range(1，n＋1)： print(a[i]) i＝1 ②_____________ for k in range(1，n＋1)： if j＞n： c[k]＝a[i] j＝m＋1 i＋＝1 elif ③_______________________： c[k]＝a[i] i＋＝1 else： c[k]＝a[j] j＋＝1 print(c[k]) ans＝”无” i＜＝m and a[i]＜a[j] if c[i]＝＝c[i＋n//2]： ans＝” 最具人气奖： ”＋c[i] break print(ans) 【解析】 (1)①外循环表示排序次数，内循环表示每次排序的比较次数，本段代码是对小王收集的选票号进行排序。在内循环中，每次循环的k值未曾定义，而j的范围每次都从n－1开始，所以内循环中比较的两个对象应为j和j＋1，以保证所有数据有序排序， 所以①处答案为k＝j＋1。②、③处需要将数组a中分别有序的1～m、m＋1～n数据段合并至新数组c中，使其完全升序排序。i表示小李收集的选票，j表示的是小王收集的选票，所以②处的答案为j＝m＋1。小李的选票数据赋值给数组c，并且比小王的选票要小，所以③处的答案为：i＜＝m and a[i]＜＝a[j]。 (2)此处表示得票数过半的获最具人气奖，所以只要遍历一半的数据，例如共有7张选票，枚举至第四张时才能完全确定，所以本空答案为：(n＋1)//2。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 20． 某会务组根据参会者到达指定上车点的时间和每位参会者可以等待的时间信息，安排车辆接送参会者去宾馆(不考虑车的座位数量)。参会者到达上车点的时间和可以等待的时间用长度为7 的字符串表示，例如“ 08：15 2”表示参会者当天8 点15 分到达上车点，最多等待2 分钟(每个人的等待时间都小于10)，那么该参会者最晚8 点17 分出发去宾馆(若8 点17 分刚到的参会者也一同出发)。编写Python 程序，统计接送n 个参会者所需的最少车辆数。运行程序，显示所有参会者提交的信息，按到达的时间先后排列，再显示所需的最少车辆数，程序运行结果如图所示。 (1)若将图中第4 行“08：15 4”数据改为“08：15 1”，程序输出的结果______(单选，填字母：A.会/B.不会)发生改变。 (2)实现上述功能的部分Python 程序如下，请在横线处填入合适的代码。 a＝['08：15 4'，'08：14 3'，'08：23 4'，'08：15 2'，'08：12 2'，'08： A 17 1'，'08：17 3'，'08：19 4'，'08：21 4'，'08：17 1'] def tran(str1)： ss＝int(str1[：2 ])*60＋int(str1 [3：6] ) return ss for i in range(len(a)－1)： 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] n＝len(a) b＝[ ] c＝[ ] for i in range(n)： b．append(tran(a[i][：5])) c.append(b[－1]＋int(a[ i ][6：])) for j in range(i，0，－1)： ①___________ if c[k]>c[j]： b[k]，b[j]＝b[j]，b[k] c[k]，c[j]＝c[j]，c[k] else： k＝j－1 break sum＝0 flag＝[False for i in range(n)] for i in range(n)： if flag[i]＝＝False： for j in range(i，n)： if ②____________________________________________： 　 flag[j]＝True ③_____________ print('接送所有参会者最少需要%d 辆车'%sum) b[j]<＝c[i] 或flag[j]＝＝False and b[j]<＝c[i] sum＋＝1 【解析】 算法分析：要实现最少车辆数，也就是每辆车要尽可能载最多的人数。按题目要求，以某位参会者最晚必须出发的时间为基准，在这个时间点可以到达等待地点的人都安排乘坐同一辆车。这样就可以实现最少车辆的要求。代码分析：列表b 保存的是参会者到达等待地点的时间，列表c 保存的是参会者必须出发的最晚时间。将列表c 的时间按升序进行排序，此时同步调整列表b 的顺序。根据排序的条件“c[k]>c[j]”以及每趟排序的区间范围“range(i，0，－1)”，这里排序代码实质是插入排序：0～i－1区间的元素已经有序，将i 位置上的元素通过类似冒泡的方式(相邻元素比较，不满足升序的交换)放到合适的位置。 当c[k]<＝c[j]时，本趟排序结束(break)。比较之前应该对变量k 赋值，根据以上分析①：k＝j－1 排序之后，就可以遍历列表c，只要是满足条件②：b[j]<＝c[i]的都乘坐同一辆车，同时将参会者是否乘车的状态改为已乘(flag[j]＝True)，每找到一个还未乘车的参会者，车辆数加1，③：sum＋＝1(1) “08：15 4” 改为“08：15 1”之前，安排车的时间点分别是08：14、08：17、08：23，改之后要增加08：16 这个时间点，必须增加一辆。 感谢聆听，再见！ iforand： for j in range()： if ： if： for i in： for i in range(1，)： $$