第四章 排序-浙江高中信息技术高三复习作业本

陶小波编写 96 第四章 排序 第一题 【来源 2022 年 12 月精诚联盟】 某校开设了 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)以下程序先从报名表中读入学生填报的志愿数据，然后按每人的得分降序排列，同时维 护好每个学生原始的序号，以便完成后续的查询操作。程序的最后是从高分开始按志愿录取。 排好序的部分数据如下文右侧所示，请完善程序。 陶小波编写 97 (3)完成选修课录取工作后，需要查询某学生被哪门选修课录取了。以下算法实现了输入学 号查询该生被录取的课程编号，运行结果如下所示，请完善程序。 陶小波编写 98 第二题 【来源 2022 年 12 月强基联盟】 运动会趣味项目乒乓拍托球比赛，每班各出男女生一名，记录每个班级男女选手在规定时间 内的失误次数并分男女生各按次数从少到多排名，分别排出第 1～8 名，分值如第 2 题图 1 所示，共 8 个班 16 个人参加，各班男女生分数之和作为本班团体分，小明编写程序计算每 班最终所得分数。已知本次比赛辅以其他规则，不可能会出现同成绩的情况，因此程序设计 中无需考虑同名次情况，程序输出如第 2 题图 2。 图 1 男女选手均按排名依据该表得分 图 2 (1)虚线方框处程序的时间复杂度是 (单选，填字母：A.O(logn)/B.O(n2)/C.O(n)/ D.O(n—1)) (2)在①②③划线处填入合适的代码。 #a 列表元素说明：如[2 班，15,14]表示 2 班男生失误 15 次，女生失误 14 次 a=[[1 班，5,16],[2 班，15,14],[3 班，19,17],[4 班，23,6],[5 班，8,23],[6 班， 22,5],[7 班，17,8],[8 班，10,11]] 陶小波编写 99 （3） 实线方框处代码是对有关男女选手分数的变量 x 进行赋值，正确的选项是 多 选，填字母) 陶小波编写 100 第三题 【来源 2022 年 12 月北斗联盟】 小明所在的班级共有 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。 陶小波编写 101 陶小波编写 102 第四题 【来源 2024 年 3 月 9+1 联盟】 大家期盼的大雪终于来了，孩子们欢快地在雪地里滚起了雪球。现有 n个小朋友滚了 n 个小雪球，小明决 定把所有的小雪球滚成一个大雪球。每次可以把任意两个小雪球滚到一起，消耗的体力等于这两个雪球的 重量之和。n 个雪球经过 n-1 次滚合之后，最终变成了一个大雪球。小明在滚合雪球时消耗的总体力等于 每次滚合所耗体力之和。你的任务是设计出滚合的次序方案，使小明耗费的体力最少，并输出这个最小的 体力耗费值。例如有 5个雪球，重量依次为 1,2,3,4,5。可以先将重量为 1、2两个雪球滚合，新雪球的重 量为 3,耗费体力 3。一次滚合之后，五个雪球变成了四个，数目依次为 3,3,4,5,接下来将重量为 3、3的 两个雪球滚合，耗费体力 6,接下来再将重量 4、5的两个雪球滚合，耗费体力 9,最后将重量为 6、9的两个 雪球滚合，耗费体力 15,小明耗费的总体力为 3+6+9+15,即 33。请回答下列问题： (1)现有 6 个小雪球，它们的重量依次为“1,3,5,7,2,6”,则滚成一个大雪球所耗费的总体力 为 。 (2)定义如下 sort(lst)函数参数 Ist 存储了每个雪球的重量。函数的功能是对 lst 中的元素进行升序排序 (3)主程序如下，请在程序划线处填入合适的代码。 #读入所有雪球的重量，并存入列表 a中，代码略 陶小波编写 103 第五题 【来源 2024 年 3 月高三宁波十校】 某学校举行游园活动，有 n 个限时活动项目(如 5 分钟夹珠),活动项目编号为 1～n,每个活 动项目从上午 8:30 开始，结束时间不一定相同。考虑到活动场地间的距离，活动规定：参 加前一个活动后，需间隔 10 分钟再参加下一个活动，每个同学不能同时进行两个及两个以 上的活动。小波同学对 n个游园活动项目都非常感兴趣，但是时间有限，他最多可以参加几 个活动项目?编写程序模拟计算过程，从结束时间最早的活动项目开始选择，如果完成该项 活动的时间不超过该项目结束时间，选择该活动，如果超出结束时间，则考虑是否可以替换 之前选中的某个活动，使完成已选项目的时间尽可能少。请回答下列问题： (1)若活动项目数据如下图所示，则最多可以参加的活动项目数量为___________________。 (2)定义如下函数 time(),将结束时间(格式：时:分)转换为分钟请在划线处填入合适的代码。 (3)定义如下 sort(x)函数，参数 x为活动项目数据，按照结束时间进行升序排序。 陶小波编写 104 (4)实现程序功能的部分代码如下，请在划线处填上合适的代码。 读取 n个活动项目的数据，存储在列表 activity 中，每个元素有四个数据项，分别为编号， 名称，限时，结束时间，如[1,"夹珠",5,"9:20"],代码略。 … 陶小波编写 105 第六题 【来源 2024 年 3 月高三金丽衢】 某商超周年庆典，面向消费者发放不同金额的现金抵扣券。消费者在该商超消费时可以使用 已获取的抵扣券进行现金抵扣。规则是每次消费只能使用一张抵扣券，且抵扣券金额必须小 于该次的消费金额； 例如小明获取到的抵扣券面值与数量如第 15 题图所示。若干次消费金额分别为 “45,85,60,15”,小明则可以分别选择面值为“30,50,20,10”的抵扣券，所以实际付款 95, 抵扣券优惠 110。 编写程序：给定小明获取到的抵扣券面值与数量，以及每次的消费金额，输出实际 支付金额与抵扣券优惠金额。请回答下列问题： (1)由题意可知，若仅将第 15 题图中的 30 元面值数量修改为 2,则对于题面中的消费 “45,85,60,15”,实际付款为________________。 (2) 定义如下 b_sort(lst)函数，参数 Ist 的每个元素由优惠券面值和对应的优惠券数量 2 个数据项组成。函数的功能是根据优惠券面值，对 Ist 进行升序排序。 调用该函数，若 Ist 为[[30,1],[50,1],[20,3],[10,2]],请回答①和②两个问题。 ①虚线框中的程序段第 1次执行后，关于 Ist 中的抵扣券面值，下列说法正确的是____ (单 选，填字母)。 A.Ist[0][0]数值最小 B.Ist[0][0]数值最大 C.Ist[3][0]数值最小 D.Ist[3][0]数值最大 ②虚线框中的程序段执行的次数为__________________。 (3)实现题面描述功能的部分 Python 程序如下，请在程序中划线处填入合适的代码。 陶小波编写 106 (4)若仅将 b_sort(lst)函数功能修改为根据优惠券面值，对 Ist 进行降序排序，能否正确 实现题目描述功能? ________________(单选，填字母：A.能/B.不能) 陶小波编写 144 ②i+=1 ③sum+=curtime-datat[p][1] （3）HeadA!=tailA or headB!=tailB 第四题 【来源 2022 年 12 月学军】 （1）47 （2）finish+=P[i-1][0] （3）①P[i][1]<=cur_time ②wait_time+=cur_time-min_p[1] 第五题 【来源 2022 年 12 月 Z20】 （1）8 （2） ①h[st[top]]>=h[i] ②L[i]=st[top] ③(R[i]-L[i]-1)*h[i] 第四章 排序 第一题 【来源 2022 年 12 月精诚联盟】 （1）6 （2） ①a[j][2]>a[k][2] ②break （3） ①index=idx[m] ② a[index][1]<key 第二题 【来源 2022 年 12 月强基联盟】 （1）B （2） ①a[i][0:b+2:b+1] ②res[j][1]<res[j-1][1] ③(i+1)*n （3）ABC 第三题 【来源 2022 年 12 月北斗联盟】 （1） ①i+=2 ②d[j][1]<d[j+1][1] ③f[d[i][0]]=1 ④change(diff,qA,qB) 第四题 【来源 2024 年 3 月 9+1 联盟】 (1)57 (2)8 陶小波编写 145 (2) ①headB+1<tailB 或 headB<n-2 ②2 ③a[tailB]=t 第五题 【来源 2024 年 3 月高三宁波十校】 (1)3 (2)int(y[:j])*60+int(y[j+1:])或 int(y[0:j])*60+int(y[j+1:len(y)])或其他等价答案 (3)C. (4)①total+=activity[i][2]-que[head][2]或其他等价答案 ②j>=head and temp[2]>que[j][2] 或 j>=head and temp[2]>=que[j][2]或其他等价答案 第六题 【来源 2024 年 3 月高三金丽衢】 (1)85 (2)①D ②3 (3)①a[i][0]>=x or a[i][1]==0 等其他合理答案②a[t][1]+=1 或 a[j][1]+=1 ③ans+=p-k (4)B 第五章 13 题专项 第一题 【来源 2023 年 11 月温州一模】 （1）5 （2） ①m=m+1 ②lst[i+1]-lst[i] ③st-dis 第二题 【来源 2023 年 11 月宁波一模】 （1）列表 name_list 中的数据不包括标题行 （2） ①n=len(name_list) ②0 ③n-1 ④grade[bj-1]-=1 第三题 【来源 2023 年 11 月湖丽衢一模】 （1）3 （2） ①t>=ans ②t=0 ③end-ans+1 第四题 【来源 2023 年 11 月杭州一模】 （1）6 （2） ①n=len(s) ②i<=n-1 and “0”<=s[i]<=“9”