高效作业6 第6课 链表2——链表综合-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参（浙教版2019）

高效作业6[第6课　链表2——链表综合](见学生用书P185) 【A级　新教材落实与巩固】 1．用二维列表来模拟双向链表，用包含3个元素存储数据，第二、三个元素分别存储前驱指针和后继指针，下列代码创建了一个拥有4个节点的双链表a： a＝[[2，2，3]，[8，3，－1]，[0，－1，0]，[4，0，1]]head＝2 则其头节点和尾节点数据域的值分别为(　C　) A．2和4　　　　B．0和8 C．8和0 D．3和－1 【解析】 head＝2，头节点是[8，3，－1]，尾节点是[0，－1，0]，选项C正确。 2． 有如下Python程序段： a＝[[1，2，3]，[3，－1，2]，[5，1，4]，[7，4，－1]，[9，2，3]] head＝1 a[a[head][2]][1]＝－1 head＝a[head][2] 执行该程序段后，链表a有几个节点(　C　) A．2　　B．3　　C．4　　D．5 【解析】 程序删除了头节点，选项C正确。 3． 有如下Python程序段： a＝[[2，2，3]，[8，3，－1]，[0，－1，0]，[4，0, 1]] head＝2 p＝3 a[a[p][1]][2]＝a[p][2] a[a[p][2]][1]＝a[p][1] 执行该程序段后，双向链表的结构可以表示为(　C　) A．2→8→0→4 B．0→2→4→8 C．0→2→8 D．2→4→8 【解析】 程序的任务是删除p节点，再从头节点开始输出，选项C正确。 4． 有如下Python程序段： a＝[[3，4，2]，[4，2，3]，[8，4，1]，[6，1，4]，[5，3，2]] p＝head＝2 while a[p][1]！＝head： print(a[p][0]，end＝”－>”) p＝a[p][1] print(a[p][0]) 执行该程序段后，双向链表的结构可以表示为(　B　) A．3→8→5→6→4 B．8→5→6→4 C．4→8→5→6 D．8→4→6→5 【解析】 程序从头节点开始输出，选项B正确。 5． 有如下Python程序段： a＝[[4，2，－1]，[0，－1，2]，[2，－1，0]，[4，0，1]] head＝1 a．append([8，－1，－1]) p＝head while a[p][2]！＝－1： p＝a[p][2] a[p][2]＝len(a)－1 a[len(a)－1][1]＝p 执行该程序段后，双向链表的结构可以表示为(　C　) A．4→0→2→8 B．8→4→0→2 C．0→2→4→8 D．8→0→2→4 【解析】 程序功能是将链表中尾节点替换为新插入新节点，再从头节点开始输出，选项C正确。 6．2023·金华一中检测某学校的话剧社团成员表lnk是一个链表，如果希望对lnk内部进行修改，分别形成男生和女生的链表，并进行输出(如图所示)，代码如下： lnk＝[['吴景'，'男'，1]，['刘德银'，'男'，3]，['郭凯'，'男'，4]，['朱颜'，'女'，2]，['吴雪健'，'男'，6]，['王芹'，'女'，8]，['张丽娅'，'女'，7]，['沙丘'，'男'，5]，['宁康'，'男'，－1]] p＝q＝headA＝0　#headA为男生链表头指针 r＝headB＝3　#headB为女生链表头指针 while p！＝－1： if lnk[p][1]＝＝'男'： q＝p p＝lnk[p][2] elif headB！＝p： lnk[q][2]＝lnk[p][2] else： lnk[q][2]＝lnk[p][2] p＝lnk[p][2] #使用headA，headB分别作为男生、女生链表头指针，遍历输出lnk，代码略 上述程序段中加框处的代码由以下四个部分组成： ①p＝lnk[p][2]　②lnk[r][2]＝－1 ③lnk[r][2]＝p　④r＝lnk[r][2] 下列选项中，代码顺序正确的是(　A　) A．③④①② B．④③①② C．③④②① D．③①④② 【解析】 本题是要将1个单向链表根据数据域的内容(男、女)分成男生、女生2个独立的单向链表。具体算法：遍历原链表，将找到的女生节点依次链接形成一个单独的链表，同时将女生节点从原链表删除。操作完成后，原链表就是一个只有男生的单向链表。分析分支语句的相应条件，要补充完善部分代码的分支满足的条件是：链表指针p所指向的节点，其数据域内容为女生且不是女生链表的头节点。分析q、r，链表指针q指向p的前驱节点，该节点数据为男生。链表指针r指向女生链表的尾节点。操作原则：为了防止断链，将节点从原链表删除前，先要链接到女生链表的尾节点。根据以上分析，可以依次确定：代码③修改r节点的指针域，指向p节点，一定是给出的代码中最先执行的，排除选项B；p指针后移的代码①必定在已有的代码：lnk[q][2]＝lnk[p][2](将p指向的节点从原链表删除)之后，排除选项D；r指针向后移动的代码必定在②之前，执行④操作后，r、p指向同一节点；由于r、p指向同一节点，必须先①后②，选项A正确。 7．将两个链表a 和b 按照间隔次序合并为一个链表，并将结果保存到链表a 中，具体合并方式为： 原始链表a：原始链表b： 合并后的链表a： 部分Python程序段如下： # 读取链表a 和b，均存储在列表data 中，其中ha 表示a 的头指针，hb 表示b 的头指针 p，q＝ha，hb while p！＝－1 and q！＝－1： r＝data[q][1] Ｋ q＝r 上述程序段中加框处可选的代码有： ①data[p][1]＝data[q][1] ②data[q][1]＝data[p][1] ③data[p][1]＝q ④data[q][1]＝p ⑤p＝data[p][1] ⑥p＝data[q][1] 已知链表b 的长度不超过链表a，则下列选项中，代码顺序正确的是(　B　) A．①④⑤ B．②③⑥ C．①④⑥ D．②③⑤ 【解析】 链表代码的基本原则：不能断链。有了r＝data[q][1]，可以排除①，这样就只能在选项B、D中选择。根据题目要求，此时p应该往下移动2个节点，⑥正确。选项B正确。 8．在Python 中用列表模拟链表结构，某程序段如下： a＝[['H'，1]，['a'，2]，['n'，3]，['g'，4]，['2'，5]，['0'，6]，['2'，7]，['2'，0]] p，head＝3，3；q，c＝－1，0；m，n＝3，0 while n<4： c＝c＋1 if c＝＝m： n＝n＋1；c＝0 if p＝＝head： head＝a[p][1] a[q][1]＝head p＝a[p][1] else： a[q][1]＝a[p][1] p＝a[p][1] else： q＝p p＝a[p][1] #从头节点开始遍历链表a 逻辑顺序的所有节点，并依次输出节点的数据，代码略 执行该程序段后，输出的结果是(　D　) A． ng02　　B． g02n　　C． 2an2　　D．22an 【解析】 在循环链表中按计数删除节点，依次删除的节点有0、H、g、2；次数head＝4；依次输出结果为22an，选项D正确。 9． 2023·东阳中学检测分词是文本数据处理中的步骤之一。基于词典的分词，所采用的词典需要经常更新。编写一个在词典中删除单词的程序，功能为：输入要删除的单词，在词典中查找并将其删除。 (1)组织字典中的单词，链表相比较数组的优势有__C__(单选，填字母：A.可快速查找任何一个单词/B.占用存储空间比要少得多/C.插入、删除操作无需频繁移动单词)。 (2)实现上述功能的部分Python程序如下，请在横线处填入合适的代码。 head＝0 #头指针为head word＝[”yellow”，”accent”，”call”，”excel”，”tea”，”little”，”brother”] #存储节点的数据区域 turn＝[4，－1，6，2，5，3，1] #存储节点的指针区域 del_word＝input(”请输入要删除的单词：　”) pre_point＝－1 ①__point＝head__或point＝0__ k＝0 while point！＝－1: if ②__word[point]＝＝del_word__： point＝turn[point] break　 #break退出当前循环 pre_point＝point point＝turn[point] if pre_point＝＝－1: #删除头节点 head＝point elif point＝＝－1: #删除尾节点 turn[pre_point]＝－1 else: turn[pre_point]＝point point＝head print(”删除单词后词典为：　”) while point！＝－1: print(word[point]，end＝” ”) ③__point＝turn[point]__ print(' ') 【解析】 (1)数组的特点是可快速查找任何一个单词，链表的特点是插入、删除操作无需频繁移动单词，选项C正确。 (2)①从头节点开始遍历链表。 ②由break可知，找到删除单词，则判断条件为当前节点单词word[point]是否与删除单词del_word相同。 ③遍历输出链表，指向下一个节点位置。 10．小明为班级编写了一个随机不重复抽奖程序，导入的数据如图1所示，程序运行界面如图2所示。 (1)程序中加框处代码有误，请改正：__cj[n－1].append(1)__或cj[－1].append(1)__或其他等价答案__。 (2)实现上述功能的Python 程序如下，请在横线处填入合适的代码。 import csv import random csvFile＝open('15.csv'，'r') reader＝csv.reader(csvFile) cj＝[] for i in reader： cj.append(i) csvFile.close() n＝len(cj) for i in range(1，n－1)： cj[i].append(①__i＋1__ ) 　# 将尾节点的指针指向头节点，构成循环单向链表 m＝int(input(”请输入抽奖人数(M) ：　”)) head＝1 p＝head；q＝n－1 for i in range(m)： x＝random.randint(1，n－1) i＝1 while i！＝x： q＝p ②__p＝cj[p][2]__或p＝cj[p]－1]__或其他等价答案__ i＝i＋1 print('幸运学生姓名为：'＋cj[p][1]) ③__cj[q][2]＝cj[p][2]__或cj[q][－1]＝cj[p][－1]__或其他等价答案__ p＝cj[p][2] n＝n－1 【解析】 (1)构建循环单向链表，将尾节点的指针指向头节点，尾节点指针为n－1；由head＝1可知，头节点指针为1。 (2)①构建链表，指向下一节点的位置。②遍历链表，指向下一个节点位置。③删除当p节点后，更新q节点的指针。 【B级　素养形成与评价】 11．移动信号塔系统由一系列建立在山顶上的基站依次连接构成，现使用程序设计模拟选址过程。现有n个连续的山顶供选择建设基站。山顶编号依次为0到n－1，其中编号为0的山顶作为起点，编号为n－1的山顶作为终点，起点和终点必须建有基站，并将每个山顶的海拔高度存入列表a。从起点开始依次确定基站高度，并用链表的形式存储基站编号。选择的规则为： ①相邻两个基站的高度差的绝对值不能超过设定值d。 ②若最后一个选择的山顶与终点的高度差超过d，则需要在两座山峰之间建增加一个辅助基站，高度为两座山峰的平均值，编号为n。 例如有7座山顶，海拔高度为a＝[100，80，90，88，80，66，60]，设定值d＝10。则依次选择的山顶的编号为0，2，3，4，7，6，海拔高度依次为100，90，88，80，70，60，其中山顶4高度为80，与终点山顶7的高度60超过d，则需增加一个编号为7，高度为70的辅助基站。程序运行界面如下图所示。 (1)如果编号0到4的山顶的海拔高度依次为60，50，30，40，60，且d＝10，则选定的基站的高度依次为__60__50__40__50__60__。 (2)请在横线处填入合适的代码。 a＝list(map(int，input(”请输入山顶高度：　”). split(”，”))) d＝int(input(”请输入限制高度差d：”)) n＝len(a)；link＝[] for i in range(n＋1): #初始化链表link，用于存储选址方案 link.append([i，－1]) head＝p＝0；i＝1 #参考规则①，依次考虑编号1到 n－2的每个山峰 while i<n－1： if abs(a[i]－a[p])<＝d： link[i][1]＝－1 link[p][1]＝i p＝i ①__i＋＝1__ if abs(a[p]－a[n－1])>d: #参考规则②，判断最后一次选择的山顶和终点高度差 　　　a．append((a[p]＋a[n－1])//2) link[n][1]＝n－1 ②__link[p][1]＝n__ p＝n #遍历链表输出基站选择方案 print(”基站选择方案为：　”) tmp＝head while link[tmp][1]！＝－1： print(a[tmp]，end＝”，”) ③__tmp＝link[tmp][1]__ print(a[tmp]) 【解析】 (1)50，30之间高度差大于10，30处不设基站，50，40之间高度差符合要求，40处设基站；40与终点60之间高度差大于10，则需要在两座山峰之间建增加一个辅助基站，高度为两座山峰的平均值，50。 (2)①while循环的特色是循环变量需要改变(后移)。 ②由abs(a[p]－a[n－1])>d可知，判断最后一个选择的山顶与终点的高度差是否超过d，条件成立需要新增节点(a.append((a[p]＋a[n－1])//2)，该节点指向终点(link[n][1]＝n－1)，则最后一个选择的山顶节点的指向新增节点(link[p][1]＝n)。 ③遍历链表，指向下一个节点位置。 12． 2023·东海中学检测猴子选大王问题：有n 只猴子挑选大王。挑选规则如下： (1)将这n 只猴子围成一圈。从某一只猴子开始，按顺时针方向依次编号为1～n； (2)给定一个初始值k，从1 号猴子开始，沿顺时针方向从1 开始报数，报到k 的猴子退出； (3)将k 值增1，从刚才退出的猴子逆时针方向的第1 只猴子开始，从1 开始沿逆时针方向报数，报到k 的猴子退出； (4)将k 值增1，从刚才退出的猴子顺时针方向的第1 只猴子开始，从1 开始沿顺时针方向报数，报到k 的猴子退出； (5)按上述(3)(4)两步，反复报数，直到圈中只剩下1 只猴子。这只猴子就是大王。 现要求输入猴子的总只数n和初始值k，即可输出大王的编号。同学们在程老师的指导下，利用如下数据结构来表示猴子和圆圈：1 只猴子用包含3 个元素的列表表示，其中第1 个元素表示猴子的编号，第2 个元素表示当前猴子的前1 只没有退出圆圈的猴子的索引号，第3 个元素表示当前猴子的后1 只没有退出圆圈的猴子的索引号。圈中猴子用列表元素表示。比如，[[1，2，1]，[2，0，2]，[3，1，0]]表示包含3 只猴子的圆圈，这也是3 只猴子在挑选大王之前的初始状态。根据上面的数据结构，小李同学设计的算法并实现的Python 代码如下，请回答下列问题。 n＝int(input(”请输入猴子的数量：　”)) k＝int(input(”请输入k 值：　”)) monkey＝[] for i in range(n)： tmp＝[i＋1，i－1，i＋1] #tmp 表示索引号为i 的猴子节点 if i＝＝n－1： tmp[2]＝0 elif i＝＝0： ①__tmp[1]＝n－1__ monkey.append(tmp) p＝0；cnt＝1；flag＝0 while monkey[p][2]！＝p： p＝monkey[p][2－flag%2] cnt＋＝1 if cnt＝＝k： ②__monkey[monkey[p][1]][2]＝monkey[p][2]__ monkey[monkey[p][2]][1]＝monkey[p][1] cnt＝0 k＋＝1 ③__flag＝1－flag__或其他等价答案__ print('大王是：　'，monkey[p][0]，'号') (1)根据上述算法，如输入猴子数量n 为3，k 的值为2，则大王编号为__3__号。 (2)请在横线处填入合适的代码。 【解析】 (1)分析题干可知，当猴子数量n为3，k值为2时，依次退出的猴子为2、1，大王编号为3。 (2)①此空为构造双向循环链表中，修正第一个节点的前驱节点索引，第一个节点的前驱节点为最后一个节点，索引号为n－1。 ②结合上下文，此空是报到k的猴子出圈，循环链表中元素的出列，并不是删除元素，而是让其余节点无法再访问到当前节点所在位置索引。解决这个问题，就是让待出圈节点的后继节点的前驱直接指向当前待出圈节点的前驱节点，让待出圈节点的前驱节点的后继直接指向待出圈节点的后继节点。 ③结合题干，猴子要顺时针、逆时针来回报数，双向链表通过二维列表实现，每个元素第一个值表示猴子编号，第二个值表示当前猴子前驱节点，第三个值表示当前猴子的后继节点。flag要实现1/0两个值循环。 13． 临近年关，学校为活跃新年气氛，准备举办迎新年联欢活动，最后一个节目为“我是大赢家”抽奖活动，为增强互动效果，最后中大奖的中奖者由教师们自已互动产生，游戏规则是：全校所有教工，每人获得一个随机编号，编号不得重复，然后按照编号大小顺时针手拉手围成一个圈，最后一个老师与第一个老师手拉手，接下来由第1个人指定m 的值，从编号为1的人开始报数(1，2，3…)，报到m 的人出圈，不再参加互动游戏，接着再由出圈人的上一位老师指定新的m 的值，并重新开始报数，逆时针报到m 的人出列，游戏过程中出圈的人由老师们自己决定，如此继续，顺时针出一个人，逆时针出一个人，直到圈中只剩下一个人，他就是今天的最大赢家。小明编写了一个Python程序实现上述功能，程序运行时，输入参加游戏的人数，每次有人出圈后，再输入下一个要出圈的人数。请在横线处填入合适的代码。 #删除索引为p的游戏者 def delete(a，head，p)： if a[p][1]！＝－1： a[a[p][1]][2]＝a[p][2] if a[p][2]！＝－1： ①__a[a[p][2]][1]＝a[p][1]__或其他等价答案__ if head＝＝p： head＝a[head][2] return head n＝int(input(”请输入参加游戏的人数”)) a＝[[i＋1，i－1，i＋1] for i in range(n)] a[0][1]＝n－1 a[n－1][2]＝0 p＝head＝0 while ②__a[head][2]！＝head或len(a)！＝1__或其他等价答案__： m＝int(input(”请输入顺时针数第几位人出局”)) for i in range(m－1)： ③__p＝a[p][2]__或其他等价答案__ head＝delete(a，head，p) p＝a[p][1] #退回到上一位游戏者 if a[head][1]！＝head： m＝int(input(”请输入逆时针数第几位人出局”)) for i in range(m－1)： p＝a[p][1] head＝delete(a，head，p) ④__p＝a[p][2]__或其他等价答案__ #退回到上一位游戏者 print(a[head]) 【解析】 程序第①空考查双向链表的节点删除操作，“删除索引为p的游戏者”。初始化的列表生成式“[[i＋1，i－1，i＋1] for i in range(n)]”说明了当前节点的前驱节点、后继节点与列表索引之间的关系——初始时，若当前节点p 在列表中的索引为i，则它的前驱节点索引为i－1，后继节点的索引为i＋1。若当前节点p 的后继节点不为空时，将p 的后继节点的前驱节点更新为p 的前驱节点，答案为a[a[p][2]][1]＝a[p][1]。 程序第②空可以结合题意以及输出来完成，题目要求“直到圈中只剩下一个人”，即链表中只剩一个节点，那么len(a)>1 或len(a)！＝1 等描述链表长度的表达式都是可行的答案。另一方面，如果从双向链表的特征角度思考，当只剩1个节点时，头节点的前驱节点和后继节点都是自己，此时一定满足a[head][2]！＝head。 程序第③空模拟顺时针链表访问，p＝a[p][2]，难点是注释中的“退回”操作。由于“报到m 的人出圈”，则经过m－1 次报数后，当前节点p 恰好是第m 个报数的人，删除节点p 后，由于p 不再参加后续的报数，所以要逆着报数的方向“回退”一次，回退后的p 的后继节点是下一轮报数的第一人。同理，在第④空中，逆时针报数后也需要做一次“回退”，而此时回退的方向为顺时针，答案为p＝a[p][2]。 14． “最小波动值”是经济管理学上的一种衡量营业情况是否稳定的概念，当“最小波动值”越大时，就说明营业情况越不稳定。经济管理学上对“最小波动值”的定义如下： 某一天的“最小波动值”＝min(该天以前某一天的营业额—该天营业额)，第一天的“最小波动值”为第一天的营业额。 若要分析某个店铺的营业情况是否稳定，只需要把一段时间内每一天的“最小波动值”加起来即可。现根据某个店铺一段时间内每一天的营业额，如图所示(说明：支出为0表示该天不营业)，设计程序计算该店铺的“最小波动值”之和。 (1)若营业额数据为“13，10，14，15，3，11”，则“最小波动值”之和是__26__。 (2)实现上述功能的Python 程序如下，请在横线处填入合适的代码。 import pandas as pd num＝[] #数组num 按经营时间顺序存储每天的营业额 numy＝[] #数组numy 按营业额降序存储每天的营业额 item＝[] #根据数组numy 构造链表item df＝pd.read_excel(”yye.xlsx”) df＝①__df[df.支出！＝0]__或df[df[”支出”]！＝0]__ #筛选出营业的记录 df[”营业额”]＝df.sum(axis＝1) #在df 对象最后一列插入“营业额”列 df1＝df.sort_values(”营业额”，ascending＝False) for i in df.index： num.append(df[”营业额”][i]) for i in df1.index： numy.append(df[”营业额”][i]) n＝1 for i in numy： item.append([i，n]) n＋＝1 item[n－2][1]＝－1 head＝0 k＝0 ②__tot＝num[0]__ for i in num[－1：－len(num)：－1]： p＝head while item[p][0]！＝i： k＝p p＝item[p][1] f＝item[p][1] if f＝＝－1： tot＋＝abs(item[k][0]－item[p][0]) elif p＝＝head： tot＋＝abs(item[f][0]－item[p][0]) else： tot＋＝min(abs(item[k][0]－item[p][0])，abs(item[f][0]－item[p][0])) if p＝＝head： head＝item[head][1] else： ③__item[k][1]＝f__或item[k][1]＝item[p][1]__ print(”该店铺的最小波动值之和是”，tot) 【解析】 (1)根据题干描述，第一天的值为13，其余数据在该数据左侧找一个最接近的数据，求值即可。 “最小波动值”之和如下图所示，结果为26。 (2)根据程序的大框架，可以分成： 第一部分：用pandas 处理数据并存储数据。先读取数据，创建DataFrame，取名为df。再筛选出营业的记录，替换df。根据题干描述“支出为0 表示该天不营业”，因此①处答案为df[df.支出！＝0]或df[df[”支出”]！＝0]，或者支出一定为0 或负数，等价答案为df[df.支出<0] 或df[df[”支出”]<0]。接着对数据进行排序后存入一个新的DataFrame，名为df1，依次遍历df 和df1，将“营业额”列的数据存入列表num 和numy，目的是构建两个数组，一个为原始营业额数组，一个为降序排序后的营业额数组。以数据“13，10，14，15，3，11”为例，num 数组内容为[13，10，14，15，3，11]，numy 数组内容为[15，14，13，11，10，3]。 第二部分：创建链表。迭代遍历numy 元素，将降序的营业额数组用二维列表item 模拟链表，每个链表节点组成格式为[数据区域，指针区域]，i 表示营业额的值，n 表示指针区域，将最后一个节点的指针区域更改为－1。创建好的链表的数据格式为：[[15，1], [14，2], [13，3], [11，4], [10，5], [3，－1]]。 第三部分：遍历链表查找数值、求和、删除链表节点。第一天的“最小波动值”为第一天的营业额，因此for i in num[－1：－len(num)：－1]：在遍历时排除了第一个数据，num[－1：－len(num)：－1] 的值为[11，3，15，14，10]。变量总和tot 的初值为第一天的营业额num[0]，②处答案为tot＝num[0]。变量p 从头指针head 开始遍历，查找num[－1：－len(num)：－1]中的数据值，p 为查找到的数据的当前节点，k 为前驱节点，f 为后继节点。求和部分中，再分情况求和，如果是头节点，对头节点及其后继节点做差求绝对值，如果是尾节点，对尾节点及其前驱节点做差求绝对值，如果是中间节点，则将当前节点和前驱节点做差求绝对值，当前节点和后继节点做差求绝对值后，取较小值。删除链表节点分两种情况，若是头节点，则更新head 指针为item[head][1]。若是中间节点或尾节点， 则将前驱节点的指针区域更新为后继节点即可。因此③处答案为item[k][1]＝f 或item[k][1]＝item[p][1]。 15．2023·缙云中学检测某学校工会举行飞镖大赛， 共有n位老师报名参赛， 每位选手共掷5支镖， 每镖得分为0至10分， 选手总分为5镖成绩之和， 每位选手的比赛数据记录在文本文件中， 如图1所示。 处理要求：数据读入数组data中， 计算出每位选手的总分， 在不改变数据在原数组data中的位置的条件下， 按总分从高到低输出选手的编号和总分。 (1)主程序。采用链表结构处理数据。程序运行界面如图2所示。请在横线处填入合适的代码。 data＝readdata(”scores.txt”)　#读取数据， 计算总分 print(”处理前的数据为：　 ”，data) n＝len(data) flag＝[True]*n　#标记数据被使用情况 head＝findmax()　#返回data中可使用状态最大数的位置 k＝head for i in range(1，n)： posi＝findmax() data[k].append(posi) __k＝posi__或__k＝data[k][2]__ # data[k].append(－1) print(”处理后的数据为： ”，data) print(”从高分到低分依次输出选手的编号和总分为： ”) output(head) (2)编写readdata()函数， 功能为从文本文件读取数据，计算出总分，返回列表。代码如下，请在横线处填入合适的代码。 def readdata(filename)： f＝open(filename) line＝f.readline(　) lst＝[] while line：　#获取每位选手数据 line＝line.split(”，”) s＝0 for i in range(1，len(line))： __s＋＝int(line[i])__# lst.append([line[0]，s]) line＝f.readline() return lst (3)编写findmax()函数，功能为返回data中可使用状态最大数的位置pos，并设置该数的使用状态为False。请在横线处填入合适的代码。 def findmax()： maxnum＝0 for i in range (n)： if ①__maxnum<data[i][1]__and__flag[i]__： 　　　maxnum＝data[i][1] 　　　pos＝i ②__flag[pos]＝False__ return pos (4)编写output()函数， 功能为从高分到低分输出选手的信息。代码如下， 程序中加框处代码有误，请改正：__q！＝－1__。 def output (q)： while ： print (data[q][0：2]，end＝”>>” q＝data[q][2] print(”NULL”)#表示结束 【解析】 (1)主程序采用结构化编程思想，各功能都设计成自定义函数，思路清晰，可读性强。主程序首先调用readdata()函数读取文本数据，并将处理后的结果存储到变量data中。接下来，程序调用findmax()函数，从所有选手中找出成绩最高的，将其标记为链表头head。然后，程序采用尾插法的方式，创建降序链表。创建降序链表过程中， k表示已建链表中的最后一个节点。每创建一个新节点， 都需要链接到k 节点之后，节点创建完成后，新节点成为当前已创建链表的最后一个节点，需要更新变量k，故此空应填k＝posi。程序最后调用output()函数按高分到低分输出数据。 (2)readdata()函数的功能是从文本文件中读取数据，计算总分后，将结果存储到列表中。每位选手的总分为五次成绩之和，由lst.append([line[0]，s])语句可知s存放的是选手总分，又因line[i]为数字字符，故横线处应填s＋＝int(line[i])。 (3)flag数组用于标记每个节点是否已用于创建链表， 未使用过标记为True, 已使用标记为False。findmax()函数的功能是找到当前未使用过数据中最大的一个，并返回其下标，因此需要在所有flag值为True的节点中寻找最大值。maxnum用于存放本轮已寻找过的节点中的最大值，当当前值data[i][1] 大于maxnum，且该节点未使用时更新maxnum和pos。故条件判断为：data[i][1]>maxnum and flag[i]；找出最大值后，需要将最大值对应的flag值标记为已使用，故②空为：flag[pos]＝False。 (4)output()函数的功能为输出链表中所有元素的编号和总分。如按加框处条件执行，则链表中最后一个节点数据不会输出，需改为q！＝－1。 学科网（北京）股份有限公司 $$