高效作业17 第17课 排序2——其他常见排序算法-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固PPT课件（浙教版2019）

高效作业17 [第17课　排序2—— 其他常见排序算法] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 【A级　新教材落实与巩固】 1．有如下Python程序段： a＝[16，19，8，20，4，12，6，15] n＝i＝0；s＝”” while i<＝2： k＝i；j＝i＋1 while j<＝7： if a[j]<a[k]： k＝j j＝j＋1 if k！＝i： a[i]，a[k]＝a[k]，a[i] n＋＝1 s＝s＋str(a[i]) i＝i＋1 s＝str(n)＋”：”＋s print(s) 执行该程序段后，输出的值为(　 　) A． 2：468　　　　B．2：864 C． 3：468 D．3：864 A 【解析】 选择排序，由“while i<＝2”可知，排序3次；n表示交换的次数；排序过程为： 第1次：4，19，8，20，16，12，6，15　n＝1 第2次：4，6，8，20，16，12，19，15　n＝2 第3次：4，6，8，20，16，12，19，15　n＝2 选项A正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 2．有如下Python 程序段： import random a＝[] k＝random.randint(5，10) for i in range(k)： if i %2＝＝0： a．append(random.randint(10，20)*2) else： a.append(random.randint(10，20)*2＋1) n＝len(a) for i in range(n－1)： t＝i for j in range(i＋2，n，2)： if a[t]<a[j]： t＝j if t！＝i： a[t]，a[i]＝a[i]，a[t] 执行程序段后，列表a 的值可能为(　 　) A．[24，39，20，37] B．[38，41，36，31，28，29，26，27，24，11] C．[38，33，30，31，24，29] D．[36，32，30，31，22，25] C 【解析】 程序首先产生一个有k(5≤k≤10)个元素的列表，奇数位(i为偶数)放偶数([20，40])，偶数位(i为奇数)放奇数([21，41])。接下来奇偶位分别做降序排序，排序后不改变原数列的奇偶排列。可以看出，选项A 长度不够，选项错误；选项B 最后一个元素为11，而偶数位放奇数的范围应为[21，41]，不可能是11，选项错误；选项D，偶数位应为奇数，32 不符合要求，选项错误。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 3．2023·长兴中学检测列表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]的升序排列 【解析】 由j循环可知，由后向前比较，每次的结果固定在前；由“range(n－1，i＋1，－1)”可知，当i＝0时，j为2，则s[2]、s[1]，s[0]不参与排序，排除选项A、B；由“s[j]>s[j－1]”可知，是降序，选项C正确。 C 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 4．有如下Python程序段： a＝[19，9，48，32，5，17，23，8] max＝0 for i in range(8)： k＝i for j in range(i＋1，8)： if a[k]<a[j]： k＝j if k！＝i： a[i]，a[k]＝a[k]，a[i] if max<k－i： max＝k－i print(max) 数组元素a[0]到a[7]的值依次为：19，9，48，32，5，17，23，8，执行该程序段后max 的值为(　 　) A．3　　 B．4　　 C．5　 　D．6 B 【解析】 选择排序，实现降序排序，并在交换时记下k与i之间最大位置差，执行过程： 第1次：48，9，19，32，5，17，23，8　max＝2 第2次：48，32，19，9，5，17，23，8　max＝2 第3次：48，32，23，9，5，17，19，8　max＝4 第4次：48，32，23，19，5，17，9，8　max＝4 之后的长度不可能大于4，选项B正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 5．2023·仙居中学检测有如下Python程序段： import random a＝[1，2，3，4，5] k＝random.randint(0，3) m＝k print(k) for i in range(m)： if k！＝i： if a[i]<a[k]： a[i]，a[k]＝a[k]，a[i] if k <4： k＋＝1 print(a) 执行该段程序段后，数组元素a[0]～a[4]的值依次不可能为(　 　) A．1，2，3，4，5 B．2，3，1，4，5 C．4，5，3，1，2 D．3，4，1，2，5 B 【解析】 k的取值范围为：[0，1，2，3]， k＝0时，a＝[1，2，3，4，5]； k＝1时，a＝[2，1，3，4，5]； k＝2时，a＝[3，4，1，2，5]； k＝3时，a＝[4，5，3，1，2]。 选项B符合题意。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 6．有如下Python程序段： a＝[18，34，56，23，29，39，72] flag＝[0]*7 n＝7 k＝(0＋n－1)//2 for i in range(n)： for j in range(n)： if a[j]>a[k] and flag[j]＝＝0： a[j]，a[k]＝a[k]，a[j] flag[k]＝1 k＝(k＋6)%7 print(a) 执行该程序段后，数组元素a[0]到a[6]的值为(　 　) A．29，23，18，72，56，39，34 B．39，56，72，18，23，29，34 C．34，39，56，72，18，23，29 D．34，29，23，18，72，56，39 C 【解析】 选择排序，由于比较范围是全部，引入列表flag标记是否已经确定位置；从k＝(0＋n－1)//2＝3开始排序；由“a[j]>a[k]”可知，k位置存放最大值；语句“k＝(k＋6)%7”，k前移1位，选项C正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 7．有如下Python 程序段： import random a＝[－1]*5 for i in range(len(a))： a[i]＝random.randint(1，10) for i in range(2，4)： key＝a[i] j＝i－1 while j>＝1 and key<a[j]： a[j＋1]＝a[j] j－＝1 a[j＋1]＝key 执行该程序段后，数组a 的值可能为(　 　) A．[1，0，3，6，7] B．[3，2，6，7，1] C．[1，3，2，5，7] D．[3，5，6，2，7] B 【解析】 随机数是范围[1，10]之间的整数，不会出现0，选项A错误；插入排序实现升序，由于“j>＝1”，0位置不参与排序；由于“range(2，4)”，4位置不参与排序，选项B正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 8．2023·书生中学检测下述代码段用于实现在数组a 中将新数据k 插入到下标为j(0<＝j<＝8)的位置 a＝[8，6，12，3，5，7，11，2，10，0] i＝8 while i>＝j： 上述程序段中加框处可选的代码有： ①a[i＋1]＝k　 ②a[i]＝k　 ③a[i＋1]＝a[i] ④a[i]＝a[i－1]　 ⑤i＝i－1 下列选项中，代码顺序正确的是(　 　) A．③⑤① B．③⑤② C．④⑤② D．⑤③① A 【解析】 当需要将数据k 插入到数组中第j 个位置时，必须先将该位置及其后的所有数据向后移动一个位置，在保证顺序不变的前提下保存这些数据，最后再修改该位置上的数据为新数据。首先将最后一个数据到第j 个数据依次向后移动，第一空为a[i＋1]＝a[i]，第二空为i＝i－1，再将新元素k 放在第j 个位置上，i 的终值为j－1，第三空为a[i＋1]＝k，选项A正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 9． 有如下Python程序段： a＝[6，1，5，7，4，8，3，2] for i in range(8)： k，f＝i，(－1)**i for j in range(i，7)： if a[j]*f>a[k]*f： k＝j if i！＝k： a[i]，a[k]＝a[k]，a[i] 执行该程序段后，a的值为(　 　) A．[1，6，5，7，4，8，3，2] B．[1，8，2，7，3，6，4，5] C．[8，1，5，7，4，6，3，2] D．[8，1，7，2，6，3，5，4] 【解析】 程序通过变量f实现的是：奇数趟排序中，把最大的值移至最前面；偶数趟排序中把最小的值移至最前面。故最终得到的数据序列是[8，1，7，2，6，3，5，4]，选项D正确。 D 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 10．有如下两个Python程序段： 程序段1 i＝cnt＝0 flag＝True while i＜n－1and flag： flag＝False 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] flag＝True cnt＝cnt＋1 i＝i＋1 程序段2 i＝cnt＝0 flag＝True while I<n－1 And flag： flag＝False k＝i for j in range(i＋1，n－1)： if a[j]<a[k]： k＝j if k！＝i： a[k]，a[i]＝a[i]，a[k] flag＝True cnt＝cnt＋1 关于这两段程序的说法有： ①程序段1一定可以实现对数组a中n个元素的升序排序 ②程序段2一定可以实现对数组a中n个元素的升序排序 ③程序段1中cnt最大值可能为n(n－1)//2 ④程序段2中cnt最大值可能为n－1 以上说法正确的有(　 　) A．①②③④ B．①②③ C．①③④ D．②③④ C 【解析】 程序段1采用的是冒泡排序，如果某一遍排序没有发生数据的交换，说明数据已经有序；程序段2采用是的选择排序算法，如果某一遍排序没有发生数据的交换，并不能说明数据已经有序，因此②不正确。选项C正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 11．左右交替上升序列。即将最小值放在最左端，次小值放在最右端，以此类推，直至形成左右交替的序列。例如数组a＝[4，8，2，3，6，1，7，5]，排序后a＝[1，3，5，7，8，6，4，2]。 (1)已知排序前a＝[6，2，5，1，1，3，8，4]时，排序后的a为 ___________________________。 (2)为实现上述功能，请在横线处填入合适的代码。 import random n＝8 a＝[random.randint(1，9) for i in range(n)] [1，2，4，6，8，5，3，1] L，R＝0，n－1 while L＜R： k＝L for i in range(L＋1，①_________)： if a[i]<a[k]： k＝i if k！＝L： a[L]，a[k]＝a[k]，a[L] k＝R for i in range(L＋1，R)： R＋1 if a[i]<a[k]： k＝②_____ if k！＝R： a[R]，a[k]＝a[k]，a[R] L＝L＋1 ③_____________ 【解析】 按照题意，排序的结果是[1，2，4，6，8，5，3，1]；程序实现的选择排序的过程为：找出最小的数据移至最左端位置，找出次小的数据移至最右端位置，每一遍的排序实现左右两端数据有序。 i R＝R－1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 12．文本文件“score.txt”中保存着某次考试所有考生的测试成绩，部分界面如图1所示。现编写Python 程序，从文件“score.txt”中读取数据，查找并输出本次考试中每种选课组合成绩第一名的学号、选课组合及总分，若有同分则输出第一个查找到的数据。程序代码如下，程序运行后输出的结果如图2所示，请回答下列问题。 f＝open('cj.txt'，'r') #以只读的方式打开文件 a＝[] line＝f.readline() #从文件中读取一行 while line: #当line 非空(从文件中读取到数据) line＝line.strip() #把末尾的' '去掉 b＝line.split() #把空白字符去掉，变成包含三个str 的list a．append(b) #append()方法用于在列表末尾添加新的对象 line＝f.readline() f．close() ①_____________ n＝len(a) i＝1；k＝0 c＝[] while i<n： t＝i c．append(a[i][1]) for j in range(i＋1，n)： 　　 if a[i][1]＝＝a[j][1] and a[i][2]<a[j][2]： 　 ②_______ print(a[t]) while i<n and ③______________： t＝j a[i][1] in c i＋＝1 ④_________ print('共有'＋str(k)＋'种选课组合') (1)请在横线处填入合适的代码。 (2)若图1中所示的“score.txt”中将学号为“20190002”与“20190008”的整行数据互换，其他数据不变，则程序运行后，输出数据的前三行为______ (单选，填字母)。 A．[' 20190955'，'物化生'，'614'] [' 20190902'，'政史地'，'565'] [' 20190003'，'物化技'，'660'] k＋＝1 C B．[' 20190955'，'物化生'，'614'] [' 20190003'，'物化技'，'660'] [' 20190902'，'政史地'，'565'] C．[' 20190955'，'物化生'，'614'] [' 20190008'，'物化技'，'660'] [' 20190952'，'物化地'，'612'] D．[' 20190955'，'物化生'，'614'] [' 20190003'，'物化技'，'660'] [' 20190952'，'物化地'，'612'] 【解析】 (1)①结合上下程序，n需要赋初值，答案为n＝len(a)；②接下来是选择排序，第1次遇到的组合放入列表c中，再往后查找相同组合的分数，找到最高分，并用t记下位置；答案为t＝j；③内层while循环，将已经遇到过的组合跳过，已经查询的组合存储在列表c中，答案为a[i][1] in c；④k是组合数，遇到新组合k增加1，答案为k＋＝1。 (2)将学号为“20190002”与“20190008”的整行数据互换，其他数据不变，则先遇到“物化技”，选项C正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 【B级　素养形成与评价】 13．某分段排序算法描述如下： ①将原始数据按非降序(a[1]<＝a[2]<＝a[3]…)分成两个有序段。 ②将两个有序段进行合并，使得合并后的数据依然有序，得到新的非降序段。 如原始数据：1，3，4，5，7，9，2，6 合并后的结果：1，2，3，4，5，6，7，9 编写Python 程序，实现分段排序功能：读取“数据．txt”文件，如图所 示，文件中每一行有两段非降序数据，将每一行处理成一段非降序数据。请回答下列问题。 (1)请在横线处填入合适的代码。 (2)程序段中加框处代码有误，请改正： _____________________________________________________________。 i<p＋1 and a[i]<a[j] 或 i<＝p and a[i]<＝a[j] 或其他等价答案 #按行读取“数据．txt”文件，每次读一行文字存入字符串变量line中 f＝open(”数据．txt”) line＝f.readline() while line: sj＝line.split(”，”)　 # 将字符串以“，”为间隔分割成成多个字符串组成的列表 a＝[0]*len(sj)；b＝[0]*len(sj) for i in range(len(sj))： a[i]＝①__________ k＝0 int(sj[i]) for k in range(len(a)－1)： if a[k]>a[k＋1]： break else： k＝len(a)－1 p＝k ②_____________ t＝0；i＝0 while i<p＋1 or j<len(a)： j＝p＋1 b[t]＝a[i]；i＝i＋1 else： b[t]＝a[j]；j＝j＋1 ③_____________ print(b) line＝f.readline()　 #读取下一行 f．close() t＝t＋1 【解析】 (1)①将字符串列表转换成为数值，并存入列表a，答案为int(sj[i])。②i是第1段的下标，初始值为0；j是第2段的下标，初始值为p＋1，答案为j＝p＋1。③t是列表b的下标，则每存入一个元素，t往后移动，答案为t＝t＋1。 (2)当i<p＋1 and j<len(a)时，a[i]<a[j]，则将a[i]存入列表b中，答案为i<p＋1 and a[i]<a[j]或 i<＝p and a[i]<＝a[j]。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 14．2023·缙云中学检测小北根据网上选课系统的报名导出了数据并存放在“社团选课．xlsx”文件中(如图1所示)，同时设计了程序对该名单做了进一步处理，生成了以班级名称为名(如图1所示)和以社团名称为名(如图2所示)的电子表格文件，以便分发给对应的社团指导老师和各班班主任。生成图2所示名单的Python程序如下，该程序的功能为：先对导出数据按社团名称进行分类，再对选报同一社团的学生按班级为关键字进行升序排序，最后生成相应的社团名单。请在横线处填入合适的代码。 import pandas as pd def read_file(filename)： #读入电子表格文件，并将表中的数据转换成列表，代码略 def save_file(a)：#保存名单至电子表格文件 df＝pd.DataFrame(a，columns＝[”班级”，”姓名”，”选报社团”]) df.to_excel(a[0][2]＋”．xlsx”，index＝False) a＝read_file(”社团选课．xlsx”) n＝len(a) for i in range(1，n)：#按社团名称(参照字符的编码大小)进行升序排序 for j in range(0，n－i)： if a[j][2]>a[j＋1][2]： a[j]，a[j＋1]＝a[j＋1]，a[j] #统计各社团人数，存放在列表rs中，rs＝[[”SDV”，32]，…]，代码略 s＝0 for i in range(len(rs))： ①_______________ left，right＝s，s＋num－1 while left<right： imin＝imax＝left for k in range(left＋1，right＋1)： num＝rs[i][1] if a[k][0]<a[imin][0]： 　 imin＝k elif a[k][0]>a[imax][0]： imax＝k if imin！＝left： a[imin]，a[left]＝a[left]，a[imin] if imax＝＝left： ②_______________ if imax！＝right： a[imax]，a[right]＝a[right]，a[imax] imax＝imin left＝left＋1 right＝right－1 ③_______________________ s＝s＋num save_file(a[s：]) save file(a[s：s＋num]) 【解析】 rs＝[[”SDV”，32]，…]是一个二维列表；“for i in range(len(rs))”主要是对选报同一社团的学生按班级为关键字进行升序排序。①由上下代码可知，num需要赋初值，left，right是某个社团的开始位置和结束位置，则num为社团人数，答案为num＝rs[i][1]；②头尾同时排序，当条件imax＝＝left成立时，由于a[imin]，a[left]交换，需要将imax重新指向最大值，答案为imax＝imin；③将排序的好的社团输出到EXCEL文件中，由于left，right在循环中发生了变化，答案为save_file(a[s：s＋num])。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 15．某银行在取号机上统计了当天人流的进入时间和预计的业务办理时间并存储在“record.xlsx”文件中，银行营业时间为8：00—17：00。每个客户进入时会选择能最早轮到办理的窗口去办理业务。现要求根据当天窗口的开放情况，合理安排客户办理，输出各个窗口客户办理的情况。 图1 为“record.xlsx”文件中的数据(数据未完全显示)，其中“进入时间”为字符串类型，“办理时间”为整数类型，例如“08：00－15”表示进入银行时间为08 点00 分，预计业务办理时间为15 分钟；图2 中显示添加了“办理结束时间”后的数据； 图3 中显示当开放20 个窗口时各个窗口的客户办理信息(客户编号和窗口编号都从1 开始)，例如第1 号窗口办理的第一个人为编号为1 的客户，占用窗口时间为08：00—08：15(数据未完全显示)。 (1)请在横线处填入合适的代码。 import random import pandas as pd t＝[] def endtime(st): #计算客户办理结束时间，返回时刻HH：MM s＝'00' minute＝int(st[0][0：2])*60＋int(st[0][3：5])＋st[1] et＝s[len(str(minute//60))：]＋str(minute//60)＋'：'＋ s[len(str(minute%60))：]＋str(minute%60) return et df＝pd.read_excel(”record.xlsx”) n＝len(df) for i in range(n)： t．append([df[”进入时间”][i]，df[”办理时间”][i]]) ①_______________________________．append(endtime (t[－1])) # 增加办理结束时间 m＝int(input(”请输入窗口数”)) endt＝[””]*m #记录各个窗口上一客户业务办结时间 num＝[[]for i in range(m)] #记录各个窗口客户办理信息 start＝”” #记录每个人的开始办理时间 t[－1] 或t[i] 或其他等价答案 for i in range(n)： minm＝0 for j in range(②____________________________________ )： if endt[j]<＝endt[minm]： minm＝j if ③ ________________________________________________________： start＝t[i][0] endt[minm]＝t[i][2] else： m－1，－1，－1 或其他等价答案 t[i][0]>＝endt[minm] 或 t[i][0]>endt[minm] 或其他等价答案 ④___________________________________ endt[minm]＝endtime([endt[minm]，t[i][1]]) num[minm].append([i＋1，start＋”－－－”＋endt[minm]]) #按窗口编号输出客户办理信息，如图3 for i in range(m)： print(”第”＋str(i＋1)＋”号窗口”) for j in range(len(num[i]))： print(num[i][j]) start＝endt[minm] 或其他等价答案 (2)假设原始时间数据为[[”08：00”，15], [”08：03”，11]，[ ”08：11”，18]，[ ”08：13”，22]，[”08：25”，11], [”08：25”，5]，[”08：27”，7]，[ ”08：30”，15]]，开设了3 个窗口(编号为1～3 号)，程序运行完成后请问在2 号窗口办理的人数为_____(选填：1/2/3/4)。 【解析】 (1)①增加办理结束时间，位置是列表t 第i 个元素(元素值是一个列表)，第i 个元素同时也是列表t 最后一个元素，也可通过索引号－1 指定，确定答案为t[－1] 或t[i] 或其他等价答案；②遍历各个窗口，查找结束时间最早的窗口； 2 ③当前客户业务开始时间如果大于或等于m 个窗口中最早结束的时间，则到该窗口办理，确定此处答案为t[i][0]>＝endt[minm] 或t[i][0]>endt[minm] ；否则将最早结束窗口，结束时间做为当前客户的开始时间，结束时间重新计算，确定④答案为start＝endt[minm]。 (2)程序运行完成后在2 号窗口办理的人数为2，分析过程如下表： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 16．2023·遂昌中学检测学期就要接近尾声了，某班级要评出学习积极分子若干名，班级管理小组为了营造“公开、透明、平等、和谐”的学习生活氛围，开学初期就制订了评优评先进的标准，学业总分前5 名(保证班级学生数量多于5 人)；若有多位学生跟第5 名同分，则通过抽奖的形式确定评奖的同学。 已知所有学生信息存放在“德智体成绩．csv”文件中，如图1所示，有4 位同学学业总分均是88 分，因为人数限制最后只能通过抽奖从中选出部分优秀学生，结果如图2所示。 实现上述功能的Python 程序如下，请在横线处填入合适的代码。 from random import randint #从”德智体成绩．csv”文件读取数据存储到数组a 中，a[0]存储标题行，a[i][2](i>＝1)存储每名学生学业总分，代码略 left1＝1；left2＝2 while left1<＝len(a)－1： max1＝left1；max2＝left2 if int(a[max1][2])<int(a[max2][2])： a[max1]，a[max2]＝a[max2]，a[max1] for i in range(left2＋1，len(a))： if int(a[max1][2])<int(a[i][2])： ①_______________ max1＝i elif int(a[max2][2])<int(a[i][2])： max2＝i if max1！＝left1： a[max1]，a[left1]＝a[left1]，a[max1] if ②_________________： max2＝max1 if max2！＝left2： max2＝max1 max2＝＝left1 a[max2]，a[left2]＝a[left2]，a[max2] left1＝left2＋1；left2＝left1＋1 m＝5 #优秀人数 b＝[]；k＝0；st＝0 for i in range(1，len(a))： if ③ ____________________________________________________________： break if i >1 and a[i][2]！＝a[i－1][2]： st＝i－1 k>＝m and a[i][2]！＝a[i－1][2]或k>＝5 and a[i][2]！＝a[i-1][2] k＋＝1 b．append(a[i]) #输出满足条件的优秀人员，代码略 #输出最终优秀人员 print(”最终优秀人员：　”) for i in range(st)： print(b[i]) luck＝['0']*k #最后分数同分的同学，用抽奖的方式确定优秀人选 d＝m－st while d>0： cj＝④_______________________________________ #在最后同分的同 学中随机抽取编号 if luck[cj]＝＝'0'： print(b[cj]) luck[cj]＝'1' d－＝1 randint(st，k－1)或randint(st，len(b)－1) 【解析】 每次循环找出最大值max1和次大值max2，交换到正确的位置left1和left2上，第一次比较时，先把前两个中的最大值用max1标记，次大值用max2标记，接下来用left2＋1到后面的所有数进行比较，如果比最大值max1大，就更换max1，如果比最大值小，而比次大值max2大，就更换max2，因为比较的过程中每个位置只遍历一次，所以当有一个数比当前max1位置的数还要大时，原来的max1的位置就有可能是第三大的数， 确定了最大与次大的位置后，首先把max1与left1交换，如果max2正好指向left1的位置，而left1又被交换到max1的位置，那么现在max1的位置就是原来max2的位置，示意图如下： 接下来要找出前m大的数，如果第m名有多个则都要记录，从第2名开始与前一个进行比较，st记录前m－1名的最后一个的位置，k记录筛选出的总人数，如果当前人数已经超过m且与前一个值不相同，则退出循环；退出循环的前一次st记录了倒数第二名的最后一个位置， 最后同分的同学共有d＝m－st个，从其中随机抽取在列表b中的位置，被抽中的把标记luck设置为“1”。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 17． 要向可容纳88966名观众的卢赛尔球场派送外卖是一项艰巨的任务，为了方便外卖的派送，将球场观众席划分为A、B、C、D、E、F、G、H等8个区。派单平台可以根据各区域的订单数量安排派送人员，以提高外卖派送效率(一名派送人员只安排一个区域)，平台根据订单总量与空闲派送人员数量计算人均派单量，按平均派单数计算各区域所需派送人员。但按此方法分配派送人员，人员总数可能超过空闲派送人员数，则删除超额派送人数。删除规则如下：每个有订单的区域至少保留一名派送人员；每个区域最多减去一名派送人员，优先删除派单尾数最少的区域中的派送人员； 如果派单尾数相同，则在分配到派送人员数最多的区域中删除一名派送人员。例如： A ～ H 区域的订单数量分别为[468，329，392，247，38，180，263，82]，此时空闲派送人员数为30人，人均派单数为67，则各区域分配的派送人员数量分别为7、5、6、4、1、3、4、2，合计32名派送人员，需减掉2名超额派送人员，即从D 区和H 区派送人员中各减去1名。如下表所示： (1)数据如上表所示，如果F 区退掉2份订单，重新计算并分配派送人员(整体调整)，F区的派送人员的人均派单量是______。 球场区域 A B C D E F G H 合计 订单数量 468 329 392 247 38 180 263 82 1999 所需派送 人员 7 5 6 4 1 3 4 2 32 派单尾数 66 61 57 46 38 46 62 15 391 删除派送人员       －1       －1 －2 实际派送 人员数 7 5 6 3 1 3 4 1 30 89 (2)实现上述功能的Python程序如下，请在横线处填入合适的代码。 #从数据库中读取各订单所在区域，如a＝['A'，'B'，'H'，'F', ] qyn＝8 #区域数量 psryn＝30 #配送人员数量 rs＝round(len(a)/psryn) b＝[] for i in range(qyn)： c＝chr(i＋65) # “A”的ASCII码值是65 b．append([c，0，0]) #生成二维列表b＝[['A'，0，0]，['B'，0， 0]，…] for i in a： ①_______________________ #统计各区域订单数量 s＝0 for i in range(qyn)： ②___________________________________ if b[i][1]%rs！＝0： b[i][2]＋＝1 s＋＝b[i][2] k＝s－psryn i＝0 b[ord(i)－65][1]＋＝1 b[i][2]//＝rs(或者b[i][2]＝b[i][2]//rs) while k>0： for j in range(qyn－1，i，－1)： ③_______________________________________________________ _____________________： b[j－1]，b[j]＝b[j]，b[j－1] if b[i][2]>1： b[i][2]－＝1 k—＝1 i＋＝1 if b[j][1]%rs <b[j－1]%rs or b[j][1]%rs＝＝b[j－1]%rs and b[j][2]>b[j－1][2] (3)若程序中语句“s＋＝b[i][2]”缩进到了“if b[i][1]%rs！＝0：”模块内，题中所给的样例数据运行结果________(选填：有/没有)受到影响，将样例“E”区订单数量38修改为__________________能测出程序存在的问题。 【解析】 (1)根据题目图表中的数据，如果F区退掉2份订单，则F区的派单尾数为44。按照删除规则，F区会删除1名派送人员，则F区人均派单量为(180－2)/(3－1)＝89份，答案为89。 没有 67(或67 的倍数) (2)①此处为桶计数。需要统计各区域订单数量，结合下面的程序“if b[i][1]%rs！＝0”可知b[0][1]存储的是对应的“A”区域的订单数量，“B”区域则是存储在b[1][1]中，依次类推。“A”对应0，“B”对应1，“C”对应2……，列表a出现相应的区域字母，则相应的列表b对应数据计数增加1。所以答案为b[ord(i)－65][1]＋＝1。 ②此处遍历列表b，根据各区域的订单数量计算所需的派送人员。通过分析题目要求及表格数据可知，计算所需的派送人员的方法为：订单数量//人均派单数(rs)，如果派单尾数大于零，则再＋1。结合程序下文可知，所需的派送人员的数据存储在b[i][2]中，所以此处答案为b[i][2]//＝rs(或者b[i][2]＝b[i][2]//rs)。 ③此处为冒泡排序。结合程序上下文可知，此处是要依照规则删除派送人员。根据删除规则有两种情况：一是优先删除派单尾数最少的；二是如果派单尾数相同，则在派送人员多的区域删除。规则中的两种情况都要考虑到。这里有三个问题先要明确：问题一，要实现派单尾数最少的区域交换到列表的最前面，所以是升序排序；问题二，计算该区域的派单尾数方法为区域订单除以人均派单数取余，即b[j][1]%rs；问题三，所需的派送人员的数据存储在b[j][2]中。所以答案为if b[j][1]%rs<b[j－1]%rs or b[j][1]%rs＝＝b[j－1]%rs and b[j][2]>b[j－1][2]。 (3)如果“s＋＝b[i][2]”缩进了，则该语句只有在b[i][1]%rs！＝0 为真(即派单尾数不为“0”)时才执行，而题目中的样例数据都是派单尾数不为“0”，所以运行结果不受影响，答案为“没有”。从以上分析可知：因为缩进了，所以“s＋＝b[i][2]”只有在派单尾数不为“0”时才执行。当派单尾数为“0”时，该语句无法执行，派送人员总数s的计算就会有误。所以只要出现人均派单数67，或者是67的倍数，派单尾数就会为“0”，就能测出程序中的错误。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 18．2023·普陀中学检测某工厂收到了n 个产品的订单，这n 个产品分别在A、B 两个车间加工，并且必须先在A 车间加工后才可以送到B 车间加工。为了使总加工时间最短，我们可以将这n 个产品分为两类，第一类在A车间加工的时长少于在B 车间加工的时长，第二类在A 车间加工的时长不少于在B 车间加工的时长。第一类应将在A 车间花费时间少的产品排在前面，第二类应将在B 车间花费时间少的产品排在后面，然后先处理所有第一类产品，再处理第二类产品。可以证明，这样排序后所有产品加工完成花费的总时间最少。例如有4 种产品，它们在A 车间加工的时长分别为3、5、8、4， 在B 车间加工的时长分别为6、1、2、7，产品分类、排序、合并、计算时长的过程如图所示，最后得出总时长为21(每个产品在B 车间开始加工需同时满足它在A 车间加工完并且B 车间已加工完上一个产品这两个条件)。 编写程序模拟工厂对这n 个产品的处理过程，计算总加工时间。请回答下列问题： (1)由题意可知，若3 种产品在A 车间加工的时长分别为5、7、3，在B 车间加工的时长分别为6、1、2，则总加工时长为______。 (2)小华编写了如下函数，用于将第一类产品排序。 def sort1(a，b)：#参数a、b 的元素分别表示每个产品在A、B 车间的加工时长 n＝len(a) for i in range(n－1)： 16 if a[j]>a[j＋1]： a[j]，a[j＋1]＝a[j＋1]，a[j] b[j]，b[j＋1]＝b[j＋1]，b[j] 加框处可以填写的代码有_______(多选，填字母)。 A．range(n－1－i) B．range(n－1，i，－1) C．range(i，n－1) D．range(n－2，i－1，－1) AD (3)小强编写了如下函数，用于将第二类产品排序。 def sort2(a，b)：#参数a、b 的元素分别表示每个产品在A、B 车间的加工时长 n＝len(a) for i in range(1，n)： k1，k2＝a[i]，b[i] j＝i－1 while ____________________： a[j＋1]，b[j＋1]＝a[j]，b[j] j－＝1 j>＝0 and k2>b[j] a[j＋1]，b[j＋1]＝k1，k2 ①此程序时间复杂度为______(单选，填字母)。 A． O(1) B．O(n) C．O(n2) D．O(nlog2n) ②请在横线处填入合适的代码。 (4)小张结合前两位同学的程序，编写了一段Python程序用于计算产品加工总时长。请在横线处填入合适的代码。 ''' C 读取n 个产品在A、B 两车间加工的时长，根据题目要求分为两类，第一类产品在A、B 两车间加工的时长分别存储在列表a1 和列表b1 中，并通过sort1()函数排序，第二类产品在A、B 两车 间加工的时长分别存储在列表a2 和列表b2 中，并通过sort2()函数排序，代码略 ''' a＝a1＋a2 b＝b1＋b2 n＝len(a) k，t＝0，0 #k 为在A车间加工的时长，t 为在B 车间加工的时长 for i in range(n)： k＋＝a[i] if ①_______： t＝k ②____________ print(”总加工时长最短为：　”，t) t<k t＋＝b[i] 【解析】 (1)根据题意将3 种产品分类，属于第一类的为①，属于第二类的为②、③。按要求排序之后，①在A 车间加工后进入B 车间，③即可开始在A 车间加工，③在A 车间加工完毕时长为5＋3＝8，此时①还在B 车间加工，故③需要等待，A 车间空余，②可以进入加工，当②在A 车间加工完毕时长为5＋3＋7＝15；B 车间在时长为11 的时候加工完毕①，在时长为13 的时候加工完毕③。此时②还在A 车间加工，最后总时长为②加工完毕的时长＋在B 车间的时长＝16。 (2)根据题意，该部分的功能为对第一类产品按照A 车间的加工时长进行升序排序。给的比较为a[j]和a[j＋1]，比较的范围为[0，n－1]。冒泡排序可以从后往前或从前往后完成该功能，若从后往前即优先排好的为前面的数据，此时比较数据的右端点不变、左端点后移(排好的不需要参与 后续排序)，得到选项D。若从前往后即优先排好的为后面的数据，此时比较数据的左端点不变、右端点前移，得到选项A。综合得出答案为AD。 (3)根据题意，该部分的功能为对第二类产品按照在B 车间加工的时长进行降序排序。该部分使用的是插入排序的方式实现功能，一共有n 个元素，排序的时间复杂度为n2，在这条件应该为当前要排的产品在B 车间加工的时长k2 与其前面排好的产品进行比较，如果比当前的加工时长要长，就继续跟前面的比较。直到找到对应要排的位置，故k2>b[j]，注意需要考虑极端情况即当前的k2 比之前排好的b[j]都大，需要防越界。综合考虑得到②为j>＝0 and k2>b[j]。 (4)此处代码的作用为计算总的加工时长，通过for 循环，逐个进行累加产品时长，根据注释k 为A 加工时间，t 为B 加工时间；根据输出最后的结果为t 即为总时长，如果当前产品在A 车间加工的时长大于在B车间加工的时长，那当前产品进入B 车间开始加工的时间即t＝k，故①处为t<k；t 需要累加上在B 车间加工的时长，故②处为t＋＝b[i]。 感谢聆听，再见！ if j>＝len(a) or ： for j in： $$