高效作业19 第19课 数据查找2——二分查找应用-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固PPT课件（浙教版2019）

高效作业 19 [第19课　数据查找2——二分查找应用] 1 2 3 4 5 6 7 8 9 【A级　新教材落实与巩固】 1．数组a中存储的是左右交替上升的n个正整数，如下表表示： 依据二分查找思想在数组a中查找数据key，实现程序如下，请在横线处填入合适的代码。 n＝len(a)－1 key＝int(input(＂请输入待查数据：　＂)) i＝0；j＝n//2；flag＝False while ①____________________： m＝(i＋j)//2 if key＝＝a[m]： flag＝True elif②____________： j＝m－1 else： i<＝j and not flag key<a[m] i＝m＋1 if not flag and j>＝0： ③____________ if key＝＝a[m]： flag＝True if flag： print(＂数组元素a[＂＋str(m)＋＂]即为所求！　＂) else： print(＂未找到＂) m＝n－j 【解析】 数组a的元素是交替上升的，由代码“j＝n//2”可知，二分查找的范围为左半边的数据，为常规的二分查找．左边如果查找失败，根据左右两边的数据排序次位对称，比a[j]大的右边数组中，也就是a[n－1－j]，若相等则查找成功。 1 2 3 4 5 6 7 8 9 2． 在数学中高次方程的求解是个难题，比如现要求方程x3－4x2＋x＋5＝0 的解。一般可以通过以下思路来求一近似解：设f(x)＝x3－4x2＋x＋5，若有区间[a，b]，使f(a)与f(b)异号，则该区间内必存在该方程的一个解。小明编写的程序实现如下功能，输入区间值a 和b(a<b)，若该区间有解，则求解出该区间内的一个近似解(精确到10－5)，否则输出无解信息。 (1)实现上述功能的Python 代码如下，但加框处代码有误，请改正：__________________。 (2)请在横线处填入合适的代码。 a, b＝map(int，input(”输入二个用，分隔的整数”).split(”，”)) abs(ym)<0.00001 if a>b： ①_______________ a1，b1＝a，b while a<b： m＝(a＋b)/2 ym＝m**3－4*m**2＋m＋5 yb＝b**3－4*b**2＋b＋5 a，b＝b，a break if ②____________： 　　　b＝m else： a＝m if a！＝b： print(”方程在区间[%d，%d]的近似解为%f”%(a1，b1，m)) else： print(”方程在区间[%d，%d]无解”%(a1，b1)) yb*ym>0 【解析】 (1)此处是判断当前区间的中点位置是不是近似解，更正为abs(ym)<0.00001。 (2)①根据题意，以及循环条件while a<b，如果a>b，应该交换a、b 值，保证a<b，所以填写的代码：a，b＝b，a。②这里是区间收缩的条件，根据b＝m，说明近似解不在[m, b]区间，再看题目提示，如果f(a)与f(b)异号，必存在一个解。这里的条件应该是ym 与yb 同号，代码：ym*yb>0。 1 2 3 4 5 6 7 8 9 3． 已知数组元素由正数、负数或0 构成，且无重复数据。编写程序实现在一个升序排列的数组中查找绝对值最小的元素。若绝对值相等，则输出较小数。例如：数组元素值为[27，17，16，－5，13，8，2，－9]，该数组中绝对值最小的数为2。小明编写了Python 程序实现上述功能，程序运行界面如下。 (1)若输入序列[3，－6，5，1，－1，－4]，执行程序后，输出结果为_______。 (2)实现上述功能的Python 程序如下，请在横线处填入合适的代码。 #产生n 个由正数、负数或0 构成的元素，存储在数组a 中，并升序排列，代码略 def dmin(x，y)： min＝x if abs(x)>abs(y)： min＝y －1 return min #查找绝对值最小的数 i＝0；j＝n－1；flag＝False while ①_______________________________________________________： m＝(i＋j)//2 if a[m]＝＝0： flag＝True absmin＝a[m] flag＝＝False 或i<＝j and flag＝＝False 或其他等价答案 break elif a[m]>0： if ②__________________________________________________： j＝m－1 else： flag＝True absmin＝dmin(a[m－1]，a[m]) else： if a[m＋1]<0： a[m]>abs(a[m－1]) 或a[m－1]>0 或其他等价答案 i＝m＋1 else： flag＝True ③____________________________________________________ _______________ print(”绝对值最小的元素是：　”＋str(absmin)) absmin＝dmin(a[m]，a[m＋1]) (注：a[m]，a[m＋1]顺序 交换不给分) 【解析】 (1)升序排列的数组中查找绝对值最小的元素，若绝对值相等，则输出较小数，序列[3，－6, 5，1，－1，－4]，排序后[－6，－4，－1, 1，3, 5]，－1 和1 绝对值相等，较小的为－1。 (2)由题干中“已知数组元素由正数、负数或0 构成”，所以查找时绝对值最小的数只能在0 或者正负交替时产生且一定存在，由于数据为升序，当a[m]>0 ，且a[m－1]>0时继续二分查找，如果a[m－1]<0时，即为正负交替时，只需比较a[m－1]与a[m]；当a[m]<0 时，且a[m＋1]<0 继续二分查找，如果a[m＋1]>0 时，即为正负交替时，只需比较a[m]与a[m＋1]。 ①程序中当查找到时，逻辑值flag 均会赋值为True，所以继续查找的条件为flag＝＝False；②此处为a[m]>0 时，由上面分析继续二分查找的条件是a[m－1]>0 时，确定答案为a[m－1]>0 或其他等价答案；③此处是当a[m]<0 时，a[m＋1]>0 时，即为正负交替时，只需比较a[m]与a[m＋1]确定最小值，确定答案为absmin＝dmin(a[m]，a[m＋1])。 1 2 3 4 5 6 7 8 9 4．2023·义乌中学检测某老师经常研究各高校的招生及录取分数线情况。每年考试结束后，都有许多同学拿着估分成绩来咨询该老师，了解自己比较适合填报哪所大学。该老师会结合以往各高校的录取情况和今年的试卷难度等因素后预估出各高校的录取分数线，并给每位来咨询的学生推荐一所学校供其参考，要求推荐学校的预估录取分数线与学生的估分成绩尽可能接近，这所学校的预估录取分数线和这个学生估分成绩的最小差值称为不满意度。请编程求出所有学生的不满意度之和。如现有A、B、C、D 四所学校，预估录取分数线依次为522、597、567、680。X、Y、Z 三位考生的估分成绩依次为500、600、540。将学校A 推荐给X， 不满意度为22，将学校B 推荐给Y，不满意度为3，学校A 推荐给Z，不满意度为18，则所有学生的不满意度之和为43。请回答下列问题。 (1)若A、B、C、D 四所学校预估录取分数线依次为522、597、567、680。X、Y、Z 三位考生的估分成绩依次为550、600、681，则所有学生的不满意度之和为______。 (2)加框处代码有误，请改正：_______________________________。 (3)实现上述功能的Python 代码如下，请在横线处填入合适的代码。 a＝list(map(int，input().split())) #输入各学校的预估录取分数线至数组a，各数之间用空格分隔 21 j＝＝0 and a[j]>x 或a[j]>x b＝list(map(int，input().split())) #输入各学生的估分成绩至数组b，各数之间用空格分隔 for i in range(1，len(a)，1): #将数组a 从小到大排序 ①___________ for j in range(i－1，－1，－1)： if a[j]<＝x： ②__________ a[j＋1]＝a[j] x＝a[i] break a[j]＝x else： a[j＋1]＝x ans＝0 for i in range(len(b))： left＝0；right＝len(a)－1 while left<＝right： mid＝(left＋right)//2 if a[mid]<＝b[i]： left＝mid＋1 else： right＝mid－1 if left＝＝0： ans＋＝abs(a[left]－b[i]) elif right＝＝len(a)－1： ans＋＝abs(a[right]－b[i]) else： ans＋＝③__________________________________________ print(”所有学生的不满意度之和为：　”，ans) min(abs(a[left]－b[i])，abs(a[right]－b[i])) 【解析】 第(1)小题中，与550 最接近的值是567，不满意度为17；与600 最接近的值是597，不满意度为3；与681 最接近的值是680，不满意度为1，相加可得到不满意度之和为21。程序代码主要分为两部分，第一部分排序，第二部分对分查找。第一部分根据代码注释，需要对列表a升序排序，从代码a[j＋1]＝a[j]的元素后移，可以推测为插入排序。内循环j 的作用为将元素x 插入到前i－1 项中，使得前i 项保持升序。因此在满足a[j]>x 时元素a[j]后移至a[j＋1]的位置。在第②空中，a[j]<＝x 时找到了插入的位置：j＋1，退出循环。因此第②空答案为break。而第①空显然是对x 的更新，x 的含义既然是待插入的元素，那么x 的赋值就为 a[i]，即x＝a[i]。在程序退出内循环后，需要将元素x 插入到正确的位置a[j＋1]上。Python 的for 循环在迭代到序列最后一个元素后结束，不会超过序列元素之外，因此对于循环for i in range(i－1，－1，－1)，当循环结束后j＝＝0 时，无法判断是在循环内退出还是在循环后结束。若是在循环内退出的，说明此时a[j]<＝x，当前x 应该插入在a[j＋1]，而如果是循环正常结束的，那么此时应满足a[j]>x，此时应该插入在a[j]。根据以上分析，内循环结束后，若要将x 插入在a[j]，需满足：j＝＝0 and a[j]>x。 在最后的对分查找中，对分代码非常的标准。对于元素b[i]的查找结果，在非端点位置的情况下，a[left]和a[right]是最接近b[i]的元素。即学生的不满意度为min(abs(b[i]－a[left])，abs(b[i]，－a[right]))，该表达式即为答案。 1 2 3 4 5 6 7 8 9 5．将十进制数n(264≥n≥3)转化为k(k≥2)进制数，若所有数位全为1，则称k 是n 的一个好进制数。例如，十进制数31 可以转化为(11)30 和(11111)2，因此30 和2 均是31 的好进制数，其中2 为31 的最小好进制数。请回答下列问题。 (1)十进制数“21”的最小好进制数k 是_____。 (2)小明编写了一个Python程序，用于找出n 的最小好进制数k，请在横线处填入合适的代码。 n＝int(input(”输入一个十进制数： ”)) 4 def check(k，m): #计算m 位全为1 的k 进制数的十进制值，如(111)2 的十进制值为7 ans＝0 for i in range(m)： ①_______________________________________________________ return ans ans＝n for length in range(2，65)： ②________ ans＝ans*k＋1 或ans＝ans＋k**I 或ans＝ans＋k**(m－i－1) i＝2 j＝n－1 while i<＝j： mid＝(i＋j)//2 tmp＝check(mid，length) if tmp＝＝n： if ans>mid： ans＝mid break elif ③__tmp<n__： i＝mid＋1 else： j＝mid－1 print(n，”的最小好进制数是”， ans) 【解析】 (1)21＝16＋4＋1＝(111)4，故最小的好进制数是4。(2)①处实现k 进制、m 位1 转换为十进制数的过程，此处可采用累乘相加，即ans＝ans*k＋1或ans＝ans＋k**(m－i－1)等。②处结合后面的语句：可知此处应填i 的初始值。已知函数check 的第1 个参数为进制，第2 个参数为1 的位数，结合“tmp＝check(mid，length)”可知，mid 为进制。本题 的进制最小值为2，进制最大值为n－1(例如64＝63＋1＝(11)63)，故②处填：i＝2。外循环枚举所有可能的位数，循环中采用对分法测试结果，即先找到进制的中位数mid，计算mid 进制下，length 位个1 转换为十进制数的tmp。若tmp＝＝n，则保留mid 的最小值，进入下一轮大循环，查找更长的位数(位数越长意味着进制越小)。若tmp<n ，说明对应的十进制值太小，那么在长度length 固定不变的前提下，接下来应该增大进制(i＝mid＋1)，故③处填：tmp<n。 1 2 3 4 5 6 7 8 9 【B级　素养形成与评价】 6．2023·东阳中学检测为分析数据中各元素的变化情况，进行如下定义： 若在数组d 中满足d[a]<…<d[i－1]<d[i]>d[i＋1]>…>d[b]，则从下标a 到下标b 区间的数据称为一个波峰， 下标a 到b 的距离即为一个波峰的长度(长度≥3)。例如：数组d 元素为“ 78，46，50，37，5，42，6，6，23”，存在2 个波峰，分别是从d[1]到d[4]和d[4]到d[6]，波峰长度分别为4 和3。编写程序分析数据，找出所有波峰，按波峰长度降序排序(若波峰长度相同，则按开始下标升序排序)，并输出波峰长度和开始到结束元素下标；若不存在，则输出“不存在波峰”，程序运行界面如图所示。 请回答下列问题。 (1)根据题意，若数组d 元素为“23，14，35，31，13，20，3，40，10，10，9”，则最长的波峰长度为_____。 (2)实现上述功能的Python程序如下，请在横线处填入合适的代码。 def search(pos，dire)： if dire＝＝1： 4 end＝len(d)－1 else： ①__________ while pos*(－dire)>end *(－dire) and d[pos]－d[pos＋dire]>0： pos＋＝dire return pos def insert(ln，st)： mt.append([]) #为mt 追加一个列表元素 head＝0 end＝0 tail＝len(mt)－1 p＝tail－1 for j in range(②________________________________________________)： while head<＝p： m＝(head＋p)//2 if mt[m][0]<ln： p＝m－1 else： head＝m＋1 tail，head，－1 或 tail，p＋1，－1 或其他等价答案 mt[j]＝mt[j－1] mt[head]＝[ln，st] #读取待处理数据，保存在数组d 中，并将其输出，代码略 n＝len(d)；i＝1；mt＝[] while i<n－1： if ③________________________________________________________ ___________： st＝search(i－1，－1) ed＝search(i＋1，1) d[i]>d[i－1] and d[i]>d[i＋1] 或 d[i－1]<d[i]<d[i＋1] 或其他 等价答案 ln＝ed－st＋1 insert(ln，st) i＝ed else： i＋＝1 if len(mt)＝＝0： print(”不存在波峰”) else： print (”输出结果(　长度：　开始下标～结束下标)　：　”) for i in range(len(mt))： print(mt[i][0]，”：”，mt[i][1]，”～”，mt[i][1]＋mt[i][0]－1) (3)执行该程序，若数组d 元素为“1，2，3，1，2”，则search()函数调用的次数是_____次。 (4)若列表mt 中有n 个元素，加框处代码执行的时间复杂度是______(单选，填字母)。 A．O(1)　　　　 B．O(log2n) C．O(n) D．O(n2) 【解析】 (1)最长波峰为14，35，31，13，长度为4。 2 B (2)③如果存在某个点满足d[i－1]<d[i]<d[i＋1]，则向两边查找峰的开始位置和结束位置，答案为d[i]>d[i－1] and d[i]>d[i＋1] 或 d[i－1]<d[i]<d[i＋1]。①search()函数实现向某一方向查找峰的低谷处，pos为开始位置，dire为查找方向；“dire＝＝1”表示向右查找，“dire＝＝－1”表示向左查找，答案为end＝0。②将查找到的峰利用函数insert()插入到列表mt中去(采用插入排序算法)，加框处代码查找插入位置，当head>p时，循环结束；插入排序从最后后移，留出插入位置，答案为tail，head ，－1 或 tail，p＋1，－1。 (3)2，3 两次。 (4)m＝(head＋p)//2，属于对分的思维，选项B正确。 1 2 3 4 5 6 7 8 9 7．某校开设了10门选修课，用编号1～10表示。学校根据每位学生的问卷调查得分及选课报名志愿进行分班，每班(即每门课)最多30人。如某同学的报名志愿表为4，1，2，7，3，5，8，10，9，6，表示他最想选报的课编号是4(第一志愿)，其次为1(第二志愿)，以此类推。 选修课分班方法：优先满足问卷得分最高的同学的第一志愿，如果该同学的第一志愿课程的报名人数已满30人，则尝试满足他的第二志愿，第二志愿若也无法满足，则再尝试其第三志愿……以此类推，直至该同学选课成功为止。 假设报名人数是n(n<300)，所有人都能选上选修课，且同一个学生的十个志愿都是不同的(不会重复选报同一个课程)。部分学生的选报情况如表所示，数据已按学号升序排序。 (1)若某人的报名志愿表为7，3，2，5，1，9，8，6，4，10，目前只剩编号4和6的课程未录取满，则该同学最终被录取课程编号是______。 (2)以下程序先从报名表中读入学生填报的志愿数据，然后按每人的得分降序排列，同时维护好每个学生原始的序号，以便完成后续的查询操作。程序的最后是从高分开始按志愿录取。排好序的部分数据如图2，请在横线处填入合适的代码。 a＝[] n＝0 # idx[]存储原序列排序后的新位置 6 idx＝[i for i in range(n)] f＝open(”报名志愿．csv”) for s in f．readlines()[1：]: a．append(list(map(int，s.split('，')))) #将s中的字符以“，”为分割 符并转换为整型量 a[n][1]＝str(a[n][1]) n＋＝1 for i in range(n－1): k＝i for j in range(i＋1，n): if ①________________： k＝j if k！＝i: a[i]，a[k]＝a[k]，a[i] idx[a[i][0]]＝i # 原始序号排序后会跑到第i号位置上 b＝[0]*10 for i in range(n): for t in a[i][3：]: a[j][2]>a[k][2] if b[t－1]<30: b[t－1]＋＝1 a[i].append(t) ②__________ (3)完成选修课录取工作后，需要查询某学生被哪门选修课录取了。以下算法实现了输入学号查询该生被录取的课程编号，运行示例如下，请在横线处填入合适的代码。 运行示例1： break 运行示例2： key＝input('请输入学号查询录取情况：　') i，j＝0，n－1 flag＝False while i<＝j and not flag: m＝(i＋j)//2 ③________________ 请输入学号查询录取情况：2219900 找不到学号2219900，请确认学号是否有误！ index＝idx[m] if a[index][1]＝＝key: print('%s已被第%d号选修课录取'% (key，a[index][－1])) flag＝True elif ④__a[index][1]<key__： i＝m＋1 else： j＝m－1 if not flag: print('找不到学号%s，　请确认学号是否有误　！　' %key) 【解析】 本题考查排序、二分查找算法的应用。 (1)该生的志愿表7，3，2，5，1，9，8，6，4，10中只有4和6号课程未录取满，而6号课程比4号课程更靠前，因此先被6号课程录取。 (2)题目要求按得分升序排序，因此第①空需要记录比第k号更大的值，即a[j][2]>a[k][2]。而后文的数组b的比较b[t－1]<30可以得知它保存了第t门课程的录取人数，小于30时，录取人数加1，同时在数组a的第i行增加第i个人录取的课程编号t，那么此时该同学录取结束，因此需要break结束循环语句。 (3)此处二分查找是查学生的学号，而之前已经按得分排序后，学号值已经乱序，无法完成二分查找。注意到题目指明的idx[]数组的功能和排序过程中idx[]数组的变化，它记录了原先排在第i位的学生，按得分排序后的位置，因此通过索引数组的中介，学号还是升序的，二分查找也能完成，下表给出了学生数据排序前和排序后的变化(序号、学号、得分)： 然后再跟踪idx[]数组的值及其含义如表右侧所示。也就是说当i按顺序取0，1，2，3，…时，idx[0]，idx[1]，idx[2]，idx[3]，…对应的a数组的学号还是和原始一样升序的，即：a[idx[0]]，a[idx[1]]，a[idx[2]]，a[idx[3]]，…对应的学号是升序的，因此可以通过在idx[]数组中二分查找即可，二分查找比较的元素是idx[]数组所指示的a[]数组中的元素。因此第③空是取得索引值idx[m]，它对应的学号还是升序的。由于经过索引之后的学号还是升序的，i指向了序列的后半部分，因此第④空是目前的序号比待查找的序号要小，答案是a[index][1] <key。 1 2 3 4 5 6 7 8 9 8．2023·柯桥中学检测小林发现他的鱼缸里的观赏鱼越来越少了。仔细观察才发现，即使按时喂鱼，一些大鱼也会争着吃小鱼——但是不会吃比它小太多的鱼。准确地讲，若一条大小是ai 的鱼，当存在另外一条鱼aj个头比它小，但个头差不超过整数k时(即ai－aj≤k)，ai会吃掉aj，吃掉后，ai会变大，aj会消失。 如：当鱼的大小是[101，53，42，102，101，55，54] 且k＝1 时，一种可能的掠食过程是(画线数字表示被吃)：[101, 53, 42, 102, 101,55, 54] →[101, 53,42, 102, 55, 54] →[101,42, 102, 55, 54] →[42, 102, 55, 54] →[42, 102, 55]，最后只剩下3 条鱼。小林想用Python 程序模拟研究一下， 对于给定的鱼大小和k 的值，最坏情况下会剩几条鱼。 (1)若a＝[20，15，10，15，31，20，25], k＝5，则最坏情况下会剩_____条鱼。 (2)研究前，小林先对a 中所有数据进行升序排序，请在横线处填入合适的代码。 a＝[101，53，42，102，101，55，54] k＝int(input())　 # k的含义如题所述 last＝len(a)－1 flag＝True 2 while last>0 and flag： flag＝False for j in range(①___________________)： if a[j]>a[j＋1]： a[j]，a[j＋1]＝a[j＋1]，a[j] last＝j flag＝True (3)以下程序从最小的鱼儿开始模拟，让较大的鱼吃较小的鱼，无法吃掉的鱼保存在st变量中，结束后st中剩余的元素个数就是最坏情况下所剩鱼的数量。请在横线处填入合适的代码。 last 或 0，last n＝len(a) st＝[None]*n top＝－1 for i in range(n)： while top>＝0 and st[top]<a[i] and a[i]－st[top]<＝k： top－＝1 top＋＝1 ②_______________ print(”最坏情况下会剩下%d条鱼”%(top＋1)) st[top]＝a[i] (4)小林想知道剩下的鱼中，是否还存在某种大小的鱼儿。以下程序的功能为：输入鱼的大小，查询该尺寸的鱼儿是否还存在。请在横线处填入合适的代码。 size＝int(input())#输入要查询的鱼的尺寸 i＝0 j＝top while i<＝j： m＝(i＋j)//2 if #若size值与第m号元素相等，则结束循环，此处关系表达式略： break elif ③_____________： i＝m＋1 else： j＝m－1 if ④__i<＝j__或__st[m]＝＝size__： print(”大小为%d的鱼还在！　”%size) else： print(”大小为%d的鱼不存在，　可能已经被吃了”%size) st[m]<size 【解析】 (1)由a＝[20，15，10，15，31，20，25]，k＝5，从小到大看，10 能被15 吃，15 能被20 吃，20 能被25 吃，因此最后只剩25 与31 两条鱼。 (2)last 变量记录的是交换的位置j，flag 为True时记录的是有数据发生交换，再结合第6 行的条件知last＝0 或者flag 为False 时排序结束。因此，当第8～12 行的循环结束时，last 应该记录的是最后交换的位置，如以下数据中，54 和42 交换位置后，last 应该记录了最后交换的位置3，由于第3 号之后的位置都没有发生元素交换，因此第3 号后面的元素都已经有序，因此这也是下一次循环最后需要比较的位置。 第①空应该填写last，表示j 从0 循环到last－1。 (3)由循环范围可以猜测是要扫描每个已排序的数组元素a[i], while 循环的条件st[top]<a[i] and a[i]－st[top]<＝k 实现了题目中描述的“大鱼吃小鱼，且大小差不超过k”，此时有条鱼要被吃掉，但显然不是a[i]被吃，由“top－＝1”可知，被吃的是st[top]，当while 循环结束时，st[top]就是剩余无法吃的鱼，那么此时a[i]要放到st 中，然后“准备被下一个a[i]吃”，因此第②空应该填写st[top]＝a[i]，变量st 的变化也可以看出栈的操作。最后输出的top＋1 表示从0 号到top 号的鱼都是剩余的鱼。 (4)size 是要查找的值，查找的范围是数组st。由于a 是原始排过序的数组，而st 是模拟大鱼吃小鱼吃完后剩余的鱼儿，因此st 才是查找范围。那么第③空由i 的变化就可以得到答案st[m]<key，因为st 中的数值也是递增的。最后第④空应该填写查找是否成功的标记，答案是st[m]＝＝size，或者边界值i<＝j 成立。 1 2 3 4 5 6 7 8 9 9．2023·金华一中检测某校对高一新生按分班考试总分进行平行分班，具体分班规则如下：将高一年级学生按女生在前、男生在后并分别按总分进行降序排序，然后按名次序号进行蛇形分班，例如分成6个班的分班示意如图1所示。 实现上述功能的Python 程序如下，程序运行界面如图2所示。请回答下列问题。 (1)女生名次序号为100 的同学按上述规则分班到_____班 (共12 个班)。 (2)要保证程序功能不变，程序中加框处①代码________(填：能/不能)替换为range(n－i－1，0，－1)。 (3)程序中加框处②代码有误，请改正： ________________________________________________。 (4)在横线③④处填入合适的代码。 4 不能 elif d[bj[j]][2]＝＝”男” and d[bj[j＋1]][2]＝＝”女” #从文件“15.csv” 中读取学生分班数据(已按考号升序排序)，保存在列表d 中 #其中d[0]数据为['考号'，'姓名'，'性别'，'总分']，变量w 存储女生人数，代码略 n＝len(d); bj＝[0]*n for i in range(n)： bj[i]＝i for i in range(1，n＋1)： if d[bj[j]][2]＝＝d[bj[j＋1]][2] and int(d[bj[j]][3])<int(d[bj[j＋ 1]][3])： bj[j]，bj[j＋1]＝bj[j＋1], bj[j] 　　　 bj[j]，bj[j＋1]＝bj[j＋1]，bj[j] cla＝0；k＝1 for i in range(1，n)： cla＋＝k if ③________________________________________________________ _________________： 　　　cla＝12；k＝－1 elif cla>12： cla＝12；k＝－1 elif cla<1： cla＝1；k＝1 d[bj[i]].append(cla) for i in range(n)： i＝＝w＋1 或d[bj[i]][2]＝＝”男” and d[bj[i－1]][2]＝＝”女” 或其他等价答案 print(d[bj[i]]) no＝input(”请输入查找的学生考号：　(　输入End 结束)　”) while no！＝”End”： i＝1；j＝n－1 while i<＝j： m＝(i＋j)//2 if d[m][0]＝＝no： print(”学号：　”＋no＋””＋d[m][1]＋”同学在”＋str(d[m][4])＋” 班”) break elif ④____________________________： i＝m＋1 else： j＝m－1 if i>j： print(”没有找到该同学”) no＝input(”请输入查找的学生考号：　(　输入End 结束)　”) d[m][0]<no 或其他等价答案 【解析】 (1)女生名次序号为100 的同学分到12 个班之一，则100//12＝8，结果为偶数则下一组由左至右分班，当为奇数时，由右至左分班，100%8＝4，则对应班级为4。 (2)单向冒泡排序内循环比较方向可以是由前至后比较，将较小的向后交换或由后至前，将较大的向前交换，比较条件无需改变，但在内循环遍历时，初值应保持不变，否则在第2 遍排序时会出现数据未进行比较情况，通过改变终值缩小比较范围(有序数据不再参与比较)，如果改为range(n－1，i－1，－1)与range(1，n－i)排序结果相同。 (3)双关键字排序，当主要关键字相同时(即同性别时)，才比较次要关键字(总分)。结合下表，可以得出当主要关键字不同时，d[bj[i]][2]＝＝”男”and d[bj[i－1]][2]＝＝”女”时需要交换。确定答案为elif d[bj[j]][2]＝＝”男” and d[bj[j＋1]][2]＝＝”女”。 (4)③在蛇形分班时，当同性别分班时，当cla>12时，由12 至1 班分班，当cla<1时，由1至12 班分班，这里还要判断当女生分班完成时，即当分班人数比女生人数w 多1 时，男生是由12 至1 班分班。确定答案为i＝＝w＋1，也可以通过当前性别为男，前1 个分班学生性别为女来判断，确定答案为d[bj[i]][2]＝＝”男”and d[bj[i－1]][2]＝＝”女”。④在排序时是利用逻辑索引对分组数据的排序，学生分班数据依旧是按考号升序排序，在对分查找时，当d[m][0]<no 时在下半区查找，确定答案为d[m][0]<no。 感谢聆听，再见！ if if ： #② for j in ： #① $$