高效作业5 第5课 链表1——单向链表-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固PPT课件（浙教版2019）

高效作业5 [第5课　链表1——单向链表] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19  【A级　新教材落实与巩固】 1．单向链表和数组都属于线性表，它们都用于存储具有相同属性的数据，下列说法不正确的是(　 　) A．对于需要频繁插入和删除元素的情况，使用单向链表比使用数组更合适 B．数组适用于最大元素个数容易确定的情况 C．查找特定元素，使用单向链表比使用数组更方便 D．存储相同的元素，使用单向链表比使用数组更方便 C 【解析】 链表元素的访问只能通过头指针，其他节点通过节点间的指针依次访问，没有数组直接通过下标访问方便，选项C错误。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2． 下列关于链表的说法中，正确的是(　 　) A．线性链表中的各元素在存储空间中的位置必须是连续的 B．线性链表中的表头元素一定存储在其他元素的前面 C．线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面 D．线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的 【解析】 链表中的各个节点在内存中可以非顺序存储，通过指针指向后继节点连接各节点数据，选项D正确。 D 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 3．如图，这是一个单向链表，在data2与data3之间插入一个新节点data4(p指向data2，r指向data4。列表data来记录链表数据域，列表next来记录指针域)， ①next[p]＝next[r]　 ②next[r]＝p ③next[p]＝r　 ④next[r]＝－1 ⑤next[p]＝－1　 ⑥next[r]＝next[p] 在下列选项中选择正确的执行步骤(　 　) A．⑤②④　　　　 B．⑤② C．①④ D．⑥③ 【解析】 在p节点之后插入节点r, 先将r节点指向p的下一节点，语句为next[r]＝next[p]；再将p节点指向r节点，语句为next[p]＝r，选项D正确。 D 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 4．在Python中可以使用列表模拟单向链表，如链表中的节点p，a[p][0]存储p节点的数据，a[p][1]存储p指向后继节点的指针。若要在p节点之后插入新的节点x(x作为p的新后继节点)，需要执行的语句是(　 　) A．a[p][1]＝x；a[x][1]＝a[p][1] B．a[x][1]＝a[p][1]；a[p][1]＝x C．a[p][0]＝x；a[x][0]＝a[p][0] D．a[x][0]＝a[p][0]；a[p][0]＝x 【解析】 在p节点之后插入节点r, 先将r节点指向p的下一节点，语句为a[x][1]＝a[p][1]；再将p节点指向r节点，语句为a[p][1]＝x，选项B正确。 B 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 5．在Python中可以使用二维列表来模拟单向链表，用包含两个元素的列表来表示每一个节点，其中第一个元素存储数据，第二个元素存储指针(即后继节点在二维列表中的索引)。下列代码创建了一个拥有3个节点的链表a： a＝[[7，2]，[8，－1]，[9，1]] head＝0 则其头节点和尾节点数据域的值分别为(　 　) A．7和8 B．7和9 C．8和9 D．2和－1 【解析】 根据head＝0，可知头节点是[7，2]，下一个节点是[9，1]，尾节点是[8，－1]，故头节点和尾节点数据域的值分别为7和8，选项A正确。 A 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 6．在Python中可以使用二维列表来模拟单向链表，下列代码创建了一个拥有4个节点的链表a： a＝[[7，1]，[8，2]，[9，－1]，[6，0]] head＝3 依次输出各节点数据域的值，则输出内容为(　 　) A．7，8，9，6 B．6，7，8，9 C．9，8，7，6 D．9，6，7，8 【解析】 根据head＝3可知，头节点是[6，0]，依次访问的节点顺序是[7，1]，[8，2]，[9，－1]，因此输出内容是6，7，8，9，选项B正确。 B 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 7．小张准备去多个城市旅游，他设计的行程若采用链表结构表示，如图1所示。 若行程有变，需在“上海”与“成都”之间增加一 站“杭州”，链表修改为如图2所示，有以下可选操作： ①“上海”所在节点的next 值赋为“杭州”节点的next 值；　 ②“上海”所在节点的next 值赋为5； ③“杭州”所在节点的next 值赋为“上海”所在节点的next 值；　④“杭州”所在节点的next 值赋为－1 链表更新顺序正确的是(　 　) A．③①　　 B．③②　　 C．①④　 　D．②④ 【解析】 链表中插入新元素并不需要进行元素位置移动，只需要进行节点指针域的更改即可。在“上海”与“成都”之间增加一站“杭州”，需要先将新元素“杭州”的指针域设置为“成都”所在位置，再更改节点“上海”的指针域至节点“杭州”所在位置。即先将“上海”所在节点的next 值赋值给“杭州”所在节点，使“成都”所在节点成为“杭州”所在节点的后继；再让“杭州”所在节点成为“上海”所在节点的后继，即“上海”所在节点的next 值为“杭州”所在节点的索引5。选项B正确。 B 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 8． 采用列表模拟单向链表，data[p][0]为数据区域，data[p][1]为指针区域。在单向链表指针为p的节点之后插入指针为s 的节点，正确的操作是(　 　) A．data[s][1]＝p data[p][1]＝data[s][1] B．data[p][1]＝s data[s][1]＝data[p][1] C C．data[s][1]＝data[p][1] data[p][1]＝s D．data[p][1]＝data[s][1] data[s][1]＝p 【解析】 插入过程如下：节点s 的指针区域指向节点p 的后继节点，即data[s][1]＝data[p][1]，节点p 的指针区域指向节点s，即data[p][1]＝s。选项C正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 9．已知一个有7个节点的单向链表，设有头指针head和尾指针tail，如图所示，下列操作需要遍历多个节点的是(　 　) A．删除该链表中的最后一个节点 B．删除该链表中的第一个节点 C．在该链表第一个节点前插入一个新节点 D．在该链表最后一个节点后插入一个新节点 【解析】 删除该链表中的最后一个节点，需要找到该节点的前一个节点，需要从头节点开始遍历，选项A正确。 A 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 10．2023·柯桥中学检测有如下Python程序段： n＝int(input()) a＝[]；head＝－1 while n>0： r＝1－n%2 n＝n//2 a．append ([r，head]) head＝len(a)－1 p＝head while p！＝－1： print(a[p][0]，end＝””) p＝a[p][1] 执行上述程序段后， 如果输入11, 则输出的结果是(　 　) A． 1101 B． 1011 C． 0010 D．0100 【解析】 分析代码， 可知第一段while循环用于创建链表， 即将每个节点插入到链表中， 第二段while循环对链表进行遍历。将最后结果输出。 第一段while循环中运行结果如下： D 链表创建完成后， 头节点p的值为3。 第二段while循环遍历链表，从最后一个节点依次往前遍历，即结果为0100。选项D正确。   初始值 第一遍 第二遍 第三遍 第四遍 r   0 0 1 0 n 11 5 2 1 0 a [] [[0，－1]] [[0，－1]， [0，0]] [[0，－1]， [0，0]， [1，1]] [[0，－1], [0.0][1， 1]，[0，2]] head －1 0 1 2 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 11．有如下Python 程序段： data＝[] key＝2 c＝0 for i in range(len(a))： data.append([a[i]，i＋l]) data[－1][l]＝－1 la＝head＝0 t＝data[head][1] while c<3 and t！＝－l： if data[t][0]－data[la][0]<key： c＋＝1 la＝t t＝data[t][1] 执行该程序段后，若t的值为6, 则数组a的值可能是(　 　) A． [4，3，1，6，3，9，3] B． [2，6，5，1，6，4，0] C．[7，5，2，3，2，7，5] D．[2，4，0，1，0，8，4] B 【解析】 data是一个链表，t指针从链表的第三个节点开始遍历，la指针是t节点的前驱，t节点减去前驱节点la的值小于key时(小于2 ) , c计数，c的初值为0，计数到3时遍历结束，也就是整个过程计数3次就结束，执行程序后t的值为6，也就是遍历到最后一个节点时程序才结束。选项A和D，t＝5时退出；选项C，t＝4时退出。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 12．有如下Python程序段： a＝[[1，1]，[2，2]，[3，3]，[4，－1]] head＝0 cur＝a[head][1] a[head][1]＝－1 while cur！＝－1： next＝a[cur][1] a[cur][1]＝head head，cur＝cur，next 执行该程序段后，a的值为(　 　) A．a＝[[1，1]，[2，2]，[3，3]，[4，－1]] B．a＝[[1，－1]，[2，0]，[3，1]，[4，2]] C．a＝[[4，1]，[3，2]，[2，3]，[1，－1]] D．a＝[[4，－1]，[3，0]，[2，1]，[1，2]] 【解析】 语句a[head][1]＝－1把第一个节点设为尾节点，并依次设置后面的节点指针区域的值，实现链表的逆序。选项B正确。 B 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 【B级　素养形成与评价】 13．已知链表结构a[i][0]表示元素，a[i][1]表示下一个元素的下标，head表示开头元素，在已知有序的链表a中插入数值p。Python程序段如下： a＝[[0，1]，[3，2]，[5，3]，[6，－1]] head＝0 p＝4 tmp＝head while a[tmp][1]！＝－1 and ____________： tmp＝a[tmp][1] (1) a．append([p，____________]) a[tmp][1]＝len(a)－1 上述程序段中横线处可选的代码有： ①a[tmp][0]<p　 ②a[a[tmp][1]][0]<p ③tmp　 ④a[tmp][1] 下列选项中，代码顺序正确的是(　 　) A． ①③ B． ①④ C． ②③ D．②④ (2) D 【解析】 由题意可知链表的逻辑结构是：0→3→5→6，数值按升序排序。while循环从head开始查找第一个比数值p大的节点位置，而由语句a[tmp][1]＝len(a)－1可知，指针tmp指向的是p的前一个节点，所以当循环结束的时候，指针tmp指向链表中第一个比p大的节点的前一个节点， 故在while循环中的条件应该是a[a[tmp][1]][0]<p，选项D正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 14．2023·丽水中学检测某公交路线的站点名称、经度、纬度和下一个站点序号(经纬度已转换为平面坐标数据)存储在数组a 中，现计算相邻两个站点距离的总和。 import math a＝[[”廊桥”，3，2，3]，[”徐岙”，6，11，2]，[”北门”，13，8，－1]，[”上通”，3，7，1]] head＝0；s＝0 p＝a[head][3] 上述程序段中加框处可选的代码有： ①a[head][3]！＝－1　 ②head＝p ③p＝a[head][3] 　④head！＝－1 下列选项中，代码顺序正确的是(　 　) A．①②③ B．④②③ C．④③② D．①③② 【解析】 题干中p 已经指向head 的后继节点，链表的访问只需让head 访问到尾节点的前驱节点即可。故(1)处填写 a[head][3]！＝－1，(2)(3)处实现链表的跳转，即 head跳到 p 的位置 head＝p，p 跳到下一个位置p＝a[head][3]，选项A正确。 A 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 15． 有如下Python 程序段： def bianli(head)： pt＝head while pt！＝－1： print(data[pt][0]，data[pt][1]，”－>”，end＝”) pt＝data[pt][1] print() data＝[['A'，1]，['B'，2]，['C'，3]，['D'，－1]] head＝0 bianli(head) #遍历链表，显示初始状态为“A 1－>B 2－>C 3－>D －1－>” qt＝head pt＝data[qt][1] bianli(head) #遍历链表，显示最终状态为“A 2－>C 1－>B 3－>D －1－>” 执行该程序段后，链表遍历结果由初始状态变为最终状态，上述程序段中加框处可选的代码有： ①data[data[qt][1]][1]＝pt ②data[qt][1]＝data[pt][1] ③data[pt][1]＝data[data[pt][1]][1] 下列选项中，代码顺序正确的是(　 　) A．①②③ B．①③② C．②①③ D．②③① 【解析】 本程序考查的是链表的重新链接，程序实现的效果是A 1→B 2→C 3→D －1→，变为A 2→C 1→B 3→D －1→，qt指前一指针，pt指后一指针，故“A”要指向“C”，“B”要指向“D”，然后“C”要指向“B”，选项D正确。 D 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 16．将链表中的奇数节点和偶数节点分别排在一起，奇数节点和偶数节点的相对顺序不变。如原始链表为 新链表为 。部分程序如下： #读入链表，存储在列表a 中，head 存储链表的头节点 odd＝head even＝a[odd][1] tmp＝even while a[odd][1]！＝－1 and a[even][1]！＝－1： a[odd][1]＝tmp 上述程序段中加框处的代码由以下四部分组成： ①odd＝a[odd][1] 　②even＝a[even][1]　 ③a[odd][1]＝a[even][1]　 ④a[even][1]＝a[odd][1] 下列选项中，代码顺序正确的是(　 　) A．①③②④ B．①②③④ C．③②④① D．③①④② 【解析】 该程序的算法思想为：先分别获取奇数节点连接而成的链表和偶数节点连接而成的链表，再连接两个链表得到新链表，选项D正确。 D 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 17．执行下列代码，程序运行界面如图所示： def travel(lnk，head): p＝head s＝”” while ①____________： s＋＝str(lnk[p][0])＋”－>” p＝lnk[p][1] s＋＝str(lnk[p][0]) print(s) user＝[[7，2]，[15，0]，[5，3]，[1，－1]] head＝1 num＝int(input(”请输入一个整数：　”).strip()) p＝head if head＝＝－1 or num>user[p][0]: user.append([num，head]) head＝len(user)－1 else： while user[p][1]！＝－1 and ②__________： p＝user[p][1] user.append([num，user[p][1]]) ③__________ travel(user，head) 若要实现上图所示的功能，则①、②、③处填入的代码应为(　 　) A．①lnk[p][1]！＝－1 ②num<＝user[p][0] ③user[p][1]＝len(user)－1 B B．①lnk[p][1]！＝－1 ②num<＝user[user[p][1]][0] ③user[p][1]＝len(user)－1 C． ①p！＝－1 ②num<＝user[user[p][1]][0] ③user[p][1]＝len(user)－1 D．①p！＝－1 ②num<＝user[p][0] ③user[p][1]＝len(user) 【解析】 自定义函数travel 的功能为链表的遍历输出，由于最后一个元素不需要添加“－>”，所以①处此循环条件应该为遍历到的链表元素不是最后一个元素，即指针区域lnk[p][1]不等于－1，排除选项C、D。主程序部分为链表的插入，如果链表为空或待插入元素大于头节点元素，则插入元素为新的链表头节点，向链表user 中添加元素后修改头节点位置为len(user)－1；否则，遍历链表，查找插入位置，遍历结束的标志有两种，一种是遍历到最后一个元素，即user[p][1]＝1，另一种是找到一个节点的后继节点数据区域user[user[p][1]][0]小于待插入元素，②处应填写num<＝user[user[p][1]][0]，排除选项A。插入位置为节点p 的后继节点，向链表user 中添加元素后修改节点p 的指针区域user[p][1]，指向新添加的元素，即len(user)－1，③处应为user[p][1]＝len(user)－1。选项B正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 18．2023·衢州二中检测找出序列中的最大数，并将其放到序列的最后面。实现上述功能的Python程序段如下： # 链表a 中存储了序列数据，head 为其头指针，代码略 pre＝p＝head maxpre＝maxp＝head while p！＝－1： if a[p][0]>a[maxp][0]： maxp＝p；maxpre＝pre pre＝p p＝a[p][1] if maxp＝＝head： head＝a[head][1] elif maxp！＝pre： ①____________ a[pre][1]＝maxp ②______________ # 遍历输出链表a 则①、②处填入的代码应为(　 　) A．①a[maxp][1]＝a[maxpre][1] ②a[maxp][1]＝a[p][1] B．①a[maxp][1]＝a[maxpre][1] ②a[maxp][1]＝p C．①a[maxpre][1]＝a[maxp][1] ②a[maxp][1]＝a[p][1] D．①a[maxpre][1]＝a[maxp][1] ②a[maxp][1]＝p D 【解析】 第一段程序的功能为遍历链表，查找序列中最大数的位置。循环结束后，maxp 即为最大数节点的索引位置，maxpre 为该节点的前驱节点位置，pre 为最后一个节点位置，p 为最后一个节点指针区域－1。第二段程序要删除最大数节点，有两种情况，最大数节点为第一个节点或其他位置节点。如果是其他位置节点，需将该最大数节点的前驱节点指针区域指向该最大数节点的后继节点位置，即a[maxpre][1]＝a[maxp][1]。第三段程序将最大数节点插入链尾，原最后一个节点指针区域需指向最大数节点，最大数节点为新的最后一个节点，其指针区域为－1，即p，所以②a[maxp][1]＝p。选项D正确。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 19．生成一个元素个数为6、元素的值在1～9之间且不重复的数组a，Python代码如下： import random n＝9 b＝[[1，1]，[2，2]，[3，3]，[4，4]，[5，5]，[6，6]，[7，7]，[8，8]，[9，－1]] head＝0 a＝[] for i in range(6): 44 k＝random.randint(0，n－i－1) if k＝＝0: a．append(b[head][0]) ①____________ else： p＝head for j in range(k)： pre＝p p＝b[p][1] a．append(b[p][0]) ②______________ 则①、②处填入的代码应为(　 　) A． ①head＝b[head][1]　 ②b[pre][1]＝p B． ①head＝b[0][1]　 ②b[pre][1]＝p C． ①head＝b[0][1]　 ②b[pre][1]＝b[p][1] D．①head＝b[head][1]　 ②b[pre][1]＝b[p][1] D 【解析】 变量k随机生成[0，n－i－2]范围内的整数。当k＝＝0时，在数组a末尾添加元素b[head][0]，即数字1，为生成不重复的数组a，头指针head要移到下一个链表节点，故①处代码为head＝b[head][1]。当k！＝0时， 指针p从头指针head处开始遍历到第k个节点，将该节点数字区域的值添加到数组a的末尾，然后删除指针p所指节点，即将前驱节点的pre指针指向后继节点， 故②处代码为b[pre][1]＝b[p][1]。 感谢聆听，再见！ while ： s＋＝math.sqrt((a[p][1]－a[head][1])**2＋(a[p][2]－ a[head][2])**2) print(s) # # $$