资源简介

专题17　链　表
学习目标　1.掌握链表的概念和链表的遍历方法；
2.掌握链表头节点的插入和删除操作；
3.掌握链表除头节点外的其他节点的插入和删除操作.
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表每个节点的结构是相同的，由数据区域和指针区域组成，其中指针区域指向下一个节点的索引。链表的访问必须从头节点开始，因此头指针是链表必不可少的元素。
(2024年1月浙江省选考)使用列表d模拟链表结构(节点数大于0)，每个节点包含数据区域和指针区域，h为头指针。链表中各节点已按数据区域中数值的绝对值由小到大排列，如图a所示。现要修改该链表各节点的链接关系，使链表各节点按数据区域中的数值由小到大排列，结果如图b所示。实现该功能的程序段如下，方框中应填入的正确代码为(　　)
t＝h
p＝d[h][1]
while p ！＝ －1 ：
　 q＝d[p][1]
　　
　　p＝q
d[t][1]＝－1
重难点1　链表的遍历
链表的遍历必须从头节点开始，每个节点包含数据区域和指针区域，数据区域可能有多个值，指针区域值往往在节点最后一个位置。若当前q指向头指针head，那么a[q]是整个节点的值，a[q][0]是数据区域的值，a[q][1]是下一节点的索引，通过语句q＝a[q][1]，实现指针向后移动。
例题 某公交路线的站点名称、经度、纬度和下一个站点序号(经纬度已转换为平面坐标数据)存储在数组 a 中，现计算相邻两个站点距离的总和。
import math
a＝[[″廊桥″，3，2，3]，[″徐岙″，6，11，2]，[″北门″，13，8，－1]，[″上通″，3，7，1]]
head＝0 ; s＝0
p＝a[head][3]
while(1)________：
　　s＋＝math.sqrt((a[p][1]－a[head][1])**2＋(a[p][2]－a[head][2])**2)
　　(2)________
　　(3)________
print(s)
上述程序段划线处可选的代码为(　　)
①a[head][3]！＝－1　②head＝p　③p＝a[head][3]　④head！＝－1，则(1)、(2)、(3)处的代码依次为(　　)
A.①②③ B.④②③ C.④③② D.①③②
变式 使用链表结构模拟某景区游玩路线，链表a中每一个节点包含3个数据，第1个为景点名称，第2个为预计游玩时间(单位：分钟)，第3个为下一个景点指针。景区可以从多个景点的大门进入，但只能从″天梯″离开，输出显示各大门进入路线及预计总时间的代码如下。
a＝[[″迎客松″，21，2]，[″激流勇进″，40，2]，[″天空栈道″，50，5]，[″一线天″，30，4]，[″飞来峰″，60，5]，[″天梯″，20，－1]]
head＝[0，1，3]
for i in range(len(head))：
　 (1)________
　 s＝a[p][1]
　 while a[p][2]！＝－1：
　　　 print(a[p][0], end＝″→″)
　　　 (2)________
　　　 (3)________
　 print(a[p][0])
print(″预计时间：″，s，″分钟″)
上述程序划线处的可选代码有： ①p＝head ②p＝head[i]　③s＋＝a[p][1]　④p＝a[p][2]，则(1)(2)(3)处代码依次为(　　)
A.①③④ B.①④③ C.②③④ D.②④③
重难点2　链表节点的删除
在数组中删除某个节点，往往需把该节点后面的值往前移，时间复杂度为线性阶O(n)。链表节点的删除分为头节点的删除和其他节点的删除，头节点的删除只要移动头指针到下一节点，即head＝a[head][1]即可，其他节点的删除，只要修改该节点的前驱节点的指针区域值为该节点的后继节点索引即可，时间复杂度为常量阶O(1)。
例题 使用列表a模拟链表结构(节点数大于0)，每个节点包含数据区域和指针区域，head为头指针，链表中各节点已按数据区域中数值的由小到大排列。现要修改该链表各节点的链接关系，删除链表中数据区域数值相同的节点，使得链表各节点的数据区域值不重复。
实现该功能的程序段如下，方框中应填入的代码段可行的是(　　)
p ＝ head
q ＝ a[p][1]
while q！＝－1：
　　
a[p][1]＝－1
A .if a[p][0]！＝a[q][0]:
a[p][1]＝q
p ＝ q
else：
p ＝ q
q＝a[q][1]
B .if [p][0]！＝a[q][0]：
a[p][1]＝q
p ＝ q
q＝a[q][1]
C .if a[p][0]＝＝a[q][0]：
p ＝ q
q＝a[q][1]
else：
a[p][1]＝q
p ＝ q
q＝a[q][1]
D .if [p][0]＝＝a[q][0]：
q＝a[q][1]
else：
p ＝ q
a[p][1]＝q
变式 使用列表模拟单向链表，链表中p节点的a[p][0]存储数据，a[p][1]存储其后继节点的指针。编写Python程序删除链表中所有偶数项(头节点为该链表的第1项)，部分代码如下：
p＝head
while p！＝－1：
　　q＝a[p][1]
　　if ①________：
　 a[p][1]＝a[q][1]
　　②________
上述程序段划线处可选语句为(　　)
A.①q！＝－1　　　 ②q＝a[q][1]
B.①q！＝－1　　　 ②p＝a[p][1]
C.①a[q][1]！＝－1　②q＝a[q][1]
D.①a[q][1]！＝－1　②p＝a[p][1]
例题 使用列表da和db模拟2个链表结构(节点数均大于0)，每个节点包含数据区域和指针区域，ha和hb分别为2个链表的头指针。链表中各节点已按数据区域中数值由小到大排列，且链表da头节点值小于链表db头节点值。现要将链表db中数据合并到链表da中，且保持升序排列。实现该功能的程序段如下，方框中应填入的正确代码为(　　)
t＝ha
while hb！＝－1：
　　q＝da[t][1]
　　
A.if q＝＝－1 or da[q][0]>db[hb][0]：
　　 da.append([db[hb][0]，q])
　　 da[t][1]＝len(da)－1
　　 hb＝db[hb][1]
t＝da[t][1]
B.if q＝＝－1 or da[q][0]>db[hb][0]：
　　 da.append([db[hb][0]，q])
　　 da[t][1]＝len(da)－1
　　 hb＝db[hb][1]
　　 t＝da[t][1]
C.if q＝＝－1 or da[q][0]>db[hb][0]：
　　 da.append([db[hb][0]，q])
　　 da[t][1]＝len(da)－1
　　 hb＝db[hb][1]
t＝q
D.if q＝＝－1 or da[q][0]>db[hb][0]：
　　 da.append([db[hb][0]，q])
　　 da[t][1]＝len(da)－1
hb＝db[hb][1]
t＝da[q][1]
变式 列表a存储了两个升序链表的节点，每个节点包含数据区域和指针区域，头指针分别为ha、hb，且a[ha][0]q ＝ h ＝ ha
p ＝ a[ha][1]
k ＝ hb
while p ！＝ －1 and k ！＝ －1：
　 if a[p][0] <＝ a[k][0]：
　 q ＝ p
　 p ＝ a[q][1]
else：
　
if k！＝－1：
　 a[q][1] ＝ k
方框中应填入的正确代码为(　　)
重难点4　循环链表及链表的简单应用
循环链表是一种特殊的链式存储结构，其中最后一个节点的指针指向头节点，形成一个环。
例1 报数游戏。已知班上有n名学生(用编号1，2，3，……，n分别表示)，学生按照编号由小到大顺时针围成一个圆圈，从编号为1的学生开始顺时针报数，报到m的同学出列；下一名同学又从1开始报数，报数为m的同学继续出列；以此规律重复下去，直到剩下最后一位同学为止。
(1)当n＝6，m＝3时，最后留下的同学的编号是________。
(2)下列代码通过构造一个循环单向链表，模拟报数的过程，逐一删除报数为m的节点，直到剩下一个节点为止。请在划线处填入合适的代码。
n＝int(input(″n＝″))
m＝int(input(″m＝″))
lst＝[]
for i in range(n－1):
　 lst.append([i＋1，i＋1])
lst.append(①________)　#将尾节点的指针指向头节点，构成循环单向链表
p＝len(lst)－1
while n>1：
　　for i in ②________：　 #从1至m－1依次报数
　 p＝lst[p][1]
　　out＝lst[p][1]
　　③________
　　n＝n－1
print(″最后留下的同学的编号是：″，lst[p][0])
变式1 有如下Python程序段：
a＝[4，5，3]
d＝[[3，″A″，2]，[6，″B″，0]，[3，″C″，1]]
q＝head＝1
t，n＝2，3
ans＝″″
i＝0
while n>0 and i　 if d[q][0]>a[i]：
　　　d[q][0]－＝a[i]
　　　t＝d[t][2]
　　　i＋＝1
　 else：
　　　a[i]－＝d[q][0]
　　　d[t][2]＝d[q][2]
　　　n－＝1
　　　ans＋＝d[q][1]
　 q＝d[q][2]
执行该程序段后，ans的值是(　　)
A.″ABC″ B.″ACB″ C.″BAC″ D.″CBA″
例2 某编程兴趣小组设计了一个点歌模拟程序，功能如下：
运行程序后，从键盘输入“A”，则显示已点的歌曲列表(歌单)；输入“B”则可以自行输入歌曲并添加到歌单以完成点歌；输入“C”则可以将指定的歌曲置顶等待播放；输入“D” 则播放当前第一首歌曲，并将该歌曲从列表中删除；输入“E”则关闭程序并退出。程序运行界面如图所示。
请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A God Is a Girl　十年　年少有为　七里香　淡季动物园 请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：B 请输入歌曲：兰亭序 请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：B 请输入歌曲：想自由 请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A God Is a Girl　十年　年少有为　七里香　淡季动物园　兰亭序　想自由 请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：C 请输入歌曲：七里香 请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A 七里香　God Is a Girl　十年　年少有为　淡季动物园　兰亭序　想自由 请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：C 请输入歌曲；想自由 请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A 想自由　七里香　God Is a Girl　十年　年少有为　淡季动物园　兰亭序 请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：D 请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A 七里香　God Is a Girl　十年　年少有为　淡季动物园　兰亭序 请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：E
Python代码如下所示，请在划线处填入合适的代码。
data＝[[″十年″，4], [″淡季动物园″，－1], [″God Is a Girl″，0], [″七里香″，1], [″年少有为″，3]]
head＝2
tail＝1
while True：
　 cmd ＝input(″请输入指令 A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：″)
　　if cmd＝＝″A″：
　 cur＝head
　 while cur！＝－1:
　　　　　print(data[cur][0]，end＝″″)
　　　　　cur＝data[cur][1]
　 print()
　　elif cmd＝＝″B″：
　 song＝input(″请输入歌曲：″)
　 data.append([song，－1])
　 if head＝＝－1：
　　　　　head＝tail＝len(data)－1
　 else：
　　　　　①________
　　　　　tail＝len(data)－1
　　elif cmd＝＝″C″：
　 song＝input(″请输入歌曲：″)
　 cur＝head
　 while cur！＝－1 and data[cur][0]！＝song:
　　　　　pre＝cur
　　　　　cur＝data[cur][1]
　if cur！＝－1 and cur！＝head：
　　　②________
　　　data[cur][1]＝head
　　　head＝cur
　　　if cur＝＝tail：
　　　 ③________
elif cmd＝＝″D″：
　if head＝＝tail:
　　 head＝tail＝－1
　else：
　　　④________
elif cmd＝＝″E″：
　break
变式2 已知一个有7个节点的单向链表，设有头指针head和尾指针tail，如图所示，下列操作需要遍历多个节点的是(　　)
A.删除该链表中的最后一个节点
B.删除该链表中的第一个节点
C.在该链表第一个节点前插入一个新节点
D.在该链表最后一个节点后插入一个新节点
重难点1　链表的遍历
1.下列关于单向链表的说法正确的是(　　)
A.必定有头指针和尾指针
B.每个节点都有一个后继节点
C.删除一个节点，需要修改两个指针
D.查找任一节点的算法时间复杂度为O(n)
2.使用列表模拟单链表，其存储结构如图所示，遍历该链表，将访问到的节点的数据域的字符依次连接，得到字符串‘LOVE’，则指针域中的索引值依次为(　　)
A.0 1 2 3 B.3 1 0 2
C.2 0 －1 1 D.2 0 1 －1
3.使用Python的二维列表来模拟单向链表，如下代码创建一个拥有4个节点的链表a
a＝[[″cat″，1]，[″dog″，2]，[″pig″，－1]，[″rabbit″，0]]
head＝3
依次输出各节点数据域的值，内容为(　　)
A.″cat″，″dog″，″pig″，″rabbit″
B.″pig″，″rabbit″，″cat″，″dog″
C.″pig″，″dog″，″cat″，″rabbit″
D.″rabbit″，″cat″，″dog″，″pig″
4.实现在链表c中找出最小值m的Python程序如下：
head＝3；p＝head；m＝c[head][0]
while (1)________：
　　(2)________
　　if c[p][0]　 m＝c[p][0]
上述程序段中划线处可选代码为：①p！＝－1　②c[p][1]！＝－1　③p＝p＋1　④p＝c[p][1]
则程序段中(1)、(2)处代码依次为(　　)
A.①③ B.②③ C.①④ D.②④
5.使用列表a模拟链表结构(节点数大于0)，每个节点包含数据区域和指针区域，head为头指针。链表中各节点已按数据区域中的数值由小到大排列。现要计算链表中的中位数，处在链表最中间位置的数叫做中位数。说明：当数据元素为奇数个时中位数为最中间的数，偶数个时中位数为最中间两个数的平均数。实现功能的Python程序如下，划线处应填入的正确代码为(　　)
fast＝slow＝head
while fast！＝－1 and ①________：
　 p＝slow
　 slow＝a[slow][1]
　 fast＝ a[a[fast][1]][1]
if ②________：
　 mid＝(a[p][0]＋a[slow][0])/2
else：
　 mid＝a[slow][0]
print(″中位数是：″， mid)
A.①slow！＝－1　　　 ②fast！＝－1
B.①a[slow][1]！＝－1 ②fast＝＝－1
C.①a[fast][1]！＝－1 ②fast！＝－1
D.①a[fast][1]！＝－1 ②fast＝＝－1
重难点2　链表节点的删除
1.某单向链表如下图所示，若要将数据 data3 和data4 同时从链表中移除，至少需要修改节点指针的数量是(　　)
A.1 B.2 C.3 D.4
2.有下列Python程序段：
a＝[[1，3]，[1，0]，[7，1]，[4，5]，[1，－1]，[6，4]]
x＝1
p＝pre＝head＝2
if x＝＝a[head][0]：
　 head＝a[head][1]
else：
　 while p！＝－1 ：
if x＝＝a[p][0]：
　　　 a[pre][1]＝a[p][1]
else：
　　　 pre＝p
p＝a[p][1]
运行该段程序后，a[2][1]的值为(　　)
A.－1 B.0 C.1 D.3
3.使用Python程序在链表a中删除一个数据data，代码如下：
import random
a＝[[87，1]，[93，3]，[97，5]，[95，2]，[80，0]，[98，－1]]
head＝4
x＝random.randint(0，len(a)－1) #randint(a，b)返回[a，b]区间内的一个随机整数
data＝①________
q＝head
while q！＝－1：
　 if ②________：
　 if q＝＝head：
　　　　head＝a[q][1]
　 else：
　　　　a[p][1]＝a[q][1]
　 break
else：
　 ③________
q＝a[q][1]
则划线处的代码为(　　)
A.①a[0][x]　②data＝＝a[q][0]　③p＝q
B.①a[0][x]　②data！＝a[q][0]　③p＝head
C.①a[x][0]　②data＝＝a[q][0]　③p＝q
D.①a[x][0]　②data！＝a[q][0]　③q＝head
4.用Python程序实现删除链表的倒数第n(n不大于链表长度)个节点，如n＝2时，链表
更新为
部分代码如下：
#读入链表存储在列表s中，head存储链表的头节点，代码略
n ＝ int(input())
p1＝p2＝ head
while p2！＝ －1：
　 if n >＝ 0：
　(1)________
　 n －＝ 1
　　else：
　 (2)________
　 p2 ＝ s[p2][1]
if p1 ＝＝ head and n>＝0：
　 head ＝ s[head][1]
else：
　　 (3)________
上述程序段中划线处可选的语句为：
①p1＝s[p1][1]　②p2＝s[p2][1]　③s[p1][1]＝s[s[p1][1]][1]　④s[p2][1]＝s[s[p2][1]][1]
则(1)～(3)划线处语句依次为(　　)
A.①③④ B.①④③ C.②①④ D.②①③
重难点3　链表节点的插入
1.小张准备去多个城市旅游，他设计的行程若采用链表结构表示，如图a所示。若行程有变，需在“上海”与“成都”之间增加一站“杭州”，链表修改为如图b所示，有以下可选操作：
①“上海”所在节点的next值赋为“杭州”节点的next值
②“上海”所在节点的next值赋为5
③“杭州”所在节点的next值赋为“上海”所在节点的next值
④“杭州”所在节点的next值赋为－1
链表更新顺序正确的是(　　)
A.③① B.③② C.①④ D.②④
2.有如下Python程序：
def lnkid(n，head):
　 p＝head
　 while head ！＝－1 and ①________：
　 p＝head
　 head＝a[head][1]
　 return p
a＝[[2，2]，[5，3]，[1，－1]，[3，0]，[7，1]]
head＝4
n＝int(input())
p＝lnkid(n，head)
if n>a[head][0]：
　 a.append([n，head])
　 head＝len(a)－1
else：
　 a.append([n，a[p][1]])
　 ②________
用列表a模拟一个降序链表，运行程序，输入自然数n，则链表增加一个新的节点，要使链表保持降序，则划线①②处代码分别为(　　)
A.①nB.①nC.①nD.①n>a[head][0] ②a[p][1]＝len(a)
3.有两个降序序列的链表 a，b。现将链表 b 中的数据合并到链表 a，形成一个新的降序序列存于链表 a，实现数据合并的代码段如下：
a ＝ [[98，1]，[96，2]，[95，3]，[93，4]，[90，－1]]
b ＝ [[99，1]，[97，2]，[94，3]，[93，4]，[92，－1]]
head_a ＝ head_b ＝ 0
pre ＝ p ＝ head_a；q ＝ head_b
while q！＝－1：
　 if p！＝－1 and ：
　 pre＝p
　 p＝a[p][1]
　 else：
　 a.append()
　 if p＝＝head_a：
　　　 pre＝head_a＝len(a)－1
　 else：
　　　 a[pre][1]＝
　　　 pre＝len(a)－1
　 q＝b[q][1]
上述程序段中可选填的语句为：①a[p][0]>＝ b[q][0]　②a[p][0]<＝ b[q][0]　③q　④len(a)－1　⑤[b[p][0]，q]　⑥[b[q][0]，p]
则加框处填写的语句依次为(　　)
A.①⑥④ B.①⑤④ C.①⑥③ D.②⑥③
4.将两个链表a(A→B→C)和b(D→E)按照间隔次序合并为一个链表，并将结果保存到链表a(A→D→B→E→C)中，部分程序如下：
#读取链表a和b，均存储在列表data中，其中ha表示a的头指针，hb表示b的头指针
p，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，则下列选项中，代码顺序正确的是(　　)
A.①④⑤ B.②③⑥ C.①④⑥ D.②③⑤
5.用链表模拟队列操作(队列长度大于1)，链表的每个节点包含数据区域和指针区域。指针head指向队列的第一个元素，指针tail指向队列的最后一个元素，如图所示。现执行n次“出队后立即入队”操作，实现该功能的Python程序段如下：
k＝1
while k<＝n：
　　p＝head
　　
　　tail＝p
　　k＋＝1
上述程序段中方框处可选代码有
①head＝que[head][1]　②que[tail][1]＝head
③que[head][1]＝－1　④que[p][1]＝－1
则方框内应填入的正确代码顺序为(　　)
A.①②③ B.①②④ C.②①③ D.②①④
重难点4　循环链表及链表的简单应用
1.有如下程序段：
people＝[[1，1]，[2，2]，[3，3]，[4，4]，[5，5]，[6，0]]
k＝int(input())
n＝len(people)
q＝head＝0
i＝1
while n>1：
　　i＋＝1
　　if i＝＝k：
　 p＝people[q][1]
　 people[q][1]＝people[p][1]
　 if p＝＝head：
　　　 head＝people[q][1]
　 i＝1
　 n－＝1
　　q＝people[q][1]
print(people[head][0])
该程序段运行后，若输入2，则输出的结果为(　　)
A.3 B.5 C.6 D.2
2.将A－K共13张黑桃扑克牌洗好后，把牌面朝下。第一张牌翻过来A，第2次将最上面第1张牌放到这叠牌的最下面，将第2张牌翻开，是黑桃2；第3次数将最上面第1、2张牌放到这叠牌的最下面，将第3张牌翻开，是黑桃3；依次类推将13张牌按从小到大的顺序翻出。求这叠牌洗好后，从上到下的原始顺序。
(1)程序运行结果如图所示，结合下面代码，当输入扑克牌数量num为6时，扑克牌从上到下的初始顺序最后输出结果为：________。
请输入扑克牌数量(1—13)：13 扑克牌从上到下的初始顺序为： A，8，2，5，10，3，Q，J，9，4，7，6，K，
(2)实现题中所述功能的Python程序如下，请在程序中划线处填入合适的代码。
num ＝ int(input(″请输入扑克牌数量(1－13)：″))
poker ＝ [[i ＋ 1，(i ＋ 1) % num　] for i in range(num)]　#创建循环链表
①________
cur ＝ poker[pre][1]
result ＝ []
for i in range(num)：
　 for j in ②________：
　 pre ＝ cur
　 cur ＝ poker[cur][1]
　 result.append(poker[cur][0])
　 poker[pre][1] ＝③________
　 cur ＝ poker[pre][1]
initial ＝ [0] * num
for k in range(num)：
　 initial[result[k]－1]＝④________
print(″扑克牌从上到下的初始顺序为：″)
ajqk ＝ {1：″A″， 11：″J″， 12：″Q″， 13：″K″}
for m in initial：
　 if m > 10 or m ＝＝ 1：
　 print(ajqk[m], end＝″，″)
　 else：
　 print(m, end＝″，″)
重难点1　链表的遍历
1.链表不具备的特点是(　　)
A.所需存储空间与存储元素个数成正比
B.插入、删除操作不需要移动元素
C.无须事先估计存储空间的大小
D.可随机访问任何一个元素
2.某Python程序如下：
head ＝ 4
a ＝[[2，2]，[5，3]，[3，1]，[6，－1]，[1，0]]
p＝head
while a[p][1]！＝－1:
　　print(a[p][0]，end＝″→″)
　　p ＝ a[p][1]
程序运行后，输出的结果是(　　)
A.1→2→3→5
B.1→2→3→5→
C.1→2→3→5→6
D.1→2→3→5→6→
3.王老师用链表模拟某次比赛中运动员的出场次序，运动员号码存储如下： a＝[[″e56″，4]，[″134″，－1]，[″215″，5]，[″098″，0]，[″144″，2]，[″024″，1]]。假设head＝3，小明同学的号码是“215”，则他的出场次序是(　　)
A.2 B.4 C.5 D.6
4.有如下Python程序段：
a＝[[2，2]，[5，3]，[3，1]，[6，－1]，[1, 0]，[4，2]]
p＝5
while a[p][1]！＝－1：
　　print(a[p][0]，end＝″→″)
　　p＝a[p][1]
则运行程序后，控制台输出的结果是(　　)
A.4→3→5 B.4→3→2→5→
C.4→3→5→ D.4→3→2→5
5.利用列表模拟非循环链表a(可能存在已被删除的节点)，下列程序运行完毕后，变量p表示尾节点的节点位置是(　　)
6.某Python程序如下：
data＝[]
for i in range(len(a))：
　 data.append([a[i]，i＋1])
data[－1][1]＝－1
la＝head＝0
t＝data[head][1]
key，c＝2，0
while c<3 and t！＝－1：
　　if data[t][0]－data[la][0]　 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]
7.通过以下Python程序段，将原链表转换为逆序链表。如原链表为'A'→'B'→'C'，转换为逆序链表后，'C'→'B'→'A'。
L ＝ [['尚书'，4]，['春秋'，－1]，['诗经'，0]，['周易'，1]，['礼记'，3]]
head ＝ 2　#head 为原链表头指针
q ＝ －1
p ＝ head
while p ！＝ －1：
　　tmp ＝ L[p][1]
　　
head ＝ q
程序段中方框处可选的语句是：①p＝tmp　②q＝p　③L[p][1]＝q为实现上述功能，方框处语句依次是(　　)
A.③①② B.③②① C.①③② D.①②③
8.接力比赛男女生人数相等，男女队员交替接力，实现该功能的Python程序段如下：
a＝[[″1号″，″女″]，[″2号″，″女″]，[″3号″，″男″]，[″4号″，″男″]，[″5号″，″男″]，[″6号″，″女″]，[″7号″，″女″]，[″8号″，″男″]]
print(a[0])　#输出第一棒
pre＝0；i＝1
que＝[－1]*len(a)
head＝tail＝0
while i　 if head！＝tail：
if a[que[head]][1]！＝a[pre][1]:
　　　 print(a[que[head]])
　　　 pre＝que[head]
　　　 head＋＝1
　　①________ :
print(a[i])
pre＝i
　 else：　#性别与前一棒相同时则进入等待队列
que[tail]＝i
tail＋＝1
　 i＋＝1
if head！＝tail：
　 print(②________)
上述程序段中划线处应填写的代码是(　　)
A.①elif a[pre][1]！＝a[i][1]　②que[head])
B.①if a[pre][1]！＝a[i][1] ②que[head]
C.①elif a[pre][1]！＝a[i][1] ②a[que[head]]
D.①if a[pre][1]！＝a[i][1] ②a[que[head]]
9.将链表中的奇数节点和偶数节点分别排在一起，奇数节点和偶数节点的相对顺序不变。如原始链表为，新链表为。部分程序如下：
#读入链表，存储在列表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.③①④②
重难点2　链表节点的删除
1.由n个节点链接成的单链表如图所示，其中head为头指针。
使用列表link模拟该链表结构，每个节点包含数据域和指针域，如图中最后一个节点可以表示为[98，－1]。现要删除指针p所指向的节点，可以实现该操作的语句有(　　)
①link[p][1]＝－1　②link[head][1]＝q　③link[head][1]＝link[p][1]　④head＝link[p][1]
A.①② B.①③ C.②③ D.②④
2.有如下Python程序段：
a ＝ [[3，1], [2，2], [3，3], [3，4], [17，5], [2，6], [3，－1]]
p ＝ head ＝ 0
while p ！＝ －1:
　 q ＝ p
　　while q ！＝ －1:
　 t ＝ q
　 q ＝ a[q][1]
　 if q ！＝ －1 and a[q][0] ＝＝ a[p][0]：
　　　 a[t][1] ＝ a[q][1]
　　　　　 q ＝ t
　　p ＝ a[p][1]
p ＝ head
while p ！＝ －1：
　　print(a[p][0], end＝' ')
　　p ＝ a[p][1]
运行后程序的输出结果是(　　)
A.3 2 17 B.3 2 17 2
C.3 2 17 2 3 D.17
3.有如下Python程序段：
def guess(cur)：
　 q＝cur
　 p＝a[cur][1]
　 while p！＝－1：
　　　 if a[p][0]＝＝a[cur][0]：
　　　 a[q][1]＝a[p][1]
　　　 else：
　　　 q＝p
　　　 p＝a[p][1]
a＝[[1，3]，[1，2]，[2，4]，[2，5]，[4，－1]，[3，1]]
head＝0；cur＝head
while cur！＝－1：
　　print(a[cur][0]，end＝″″)
　　if a[cur][1]！＝－1：
　　 guess(cur)
　　cur＝a[cur][1]
运行后，则输出的结果是(　　)
A.1234 B.1122 C.11223 D.11224
4.已知链表a中的每个节点包含数据区域和指针区域两部分，下列Python程序段的功能是在链表a中删除数据值为key的所有节点。
key＝int(input(″输入要删除的数据：″))
head＝0
while head！＝－1 and a[head][0]＝＝key ：
　 head＝a[head][1]
p＝q＝head
if head！＝－1:
　 q＝a[q][1]
　 while ①________：
　　　 if a[q][0]＝＝key：
　　　 ②________
　　　else：
　　　 p＝a[p][1]
　　　q＝a[q][1]
则划线①②处的代码分别为(　　)
A.①a[q][1]！＝－1　②a[p][1]＝a[q][1]
B.①a[q][1]！＝－1 ②a[q][1]＝a[p][1]
C.①q！＝－1 ②a[q][1]＝a[p][1]
D.①q！＝－1 ②a[p][1]＝a[q][1]
5.现用链表lb存储了一批会员信息，链表每个节点中的数据依次为会员名、手机号、会员积分和节点指针，数据存储形式如[[“张三”，“13282825678”，280，1]，[“小明”，“13256787678”，500，3]，...]。现要实现删除某个手机号的会员节点，已知链表头指针head与要删除会员手机号phone，实现删除节点的代码如下：
p＝head
q＝p
while p！＝－1：
　　if b[p][1]＝＝phone：
　 if p＝＝head：
　　　　①________
　 else：
　　　　②________
　　q＝p
　　③________
划线处的代码由以下代码组成：
①head＝lb[p][3]　②p＝lb[p][3]　③lb[p][3]＝lb[q][3]　④lb[q][3]＝lb[p][3]
下列选项中顺序正确的是(　　)
A.①③② B.②④① C.①④② D.③④②
6.使用列表 d 模拟链表结构(节点数大于 1)，每个节点包含数据区域(数据均为整型，范围为 0～9)和指 针区域，h 为头指针，如图a所示。现要对该链表节点进行去重操作，只保留最后一次出现的节 点，结果如图b所示。实现该功能的程序段如下，方框中应填入的正确代码为(　　)
lst ＝ [0]*10
p ＝ h
while p ！＝ －1：
　　lst[d[p][0]] ＋＝ 1
　　p ＝ d[p][1]
q, p ＝ h, h
while d[p][1] ！＝ －1：
　　
　　p ＝ d[p][1]
7.使用列表d模拟链表结构(节点数大于0)，每个节点包含数据区域和指针区域，head为头指针。现要删除链表中数据值在[begin，end]范围的节点，实现该功能的部分程序段如下，方框中应填入的正确代码为：(　　)
d＝[[4，5]，[10，2]，[12，4]，[1，0]，[16，－1]，[7，1]]
head＝3
q＝head；p＝head
while p！＝－1：
　　if d[p][0]end：
　　　 q＝ p
　　　 p＝d[p][1]
　　else：
　　　
8.有如下Python程序，其功能为删除无序链表(元素个数大于等于2)中的重复元素。
def dele (a, head) ：
　 pre＝head; p＝a[head][1]
　 while p！＝－1：
　　　 q＝head
　　　 flag＝False
　　　 while　(1)________：
　　　　　 if a[q][0]＝＝a[p][0]：
　　　　　 (2)________
　　　　　 p＝a[p][1]
　　　　　 flag＝True
　　　　　 break
　　　　　 q＝a[q][1]
　　　 if not flag：
　　　　　pre＝p
　　　　　p＝a[p][1]
a＝[[0，3]，[1，2]，[1，4]，[0，1]，[0，5]，[2，－1]]
dele(a, 0)
①q！＝－1　②q！＝p　③a[pre][1]＝a[p][1]　④a[pre][1]＝a[q][1]
方框中填入的正确代码依次为(　　)
A.②④ B.②③ C.①④ D.①③
重难点3　链表节点的插入
1.下列Python程序的功能是：在链表中插入一个整数，链表中的数据仍保持有序。
data＝int(input(″请输入一个整数：″))
link＝[[8，3]，[6，0]，[2，1]，[11，4]，[15，－1]]
head＝2
q＝head
if data<＝link[head][0]：
　 link.append([data，head])
　 ①________________
else：
　 while ②________：
　 p＝q
　 q＝link[q][1]
　 link.append([data，q])
　 link[p][1]＝len(link)－1
q＝head
while ③________：
　 print(link[q][0]，end＝″″)
　 q＝link[q][1]
划线处应填入的代码是(　　)
A.①head＝q　　②q！＝－1 and data>link[q][0] ③q！＝－1
B.①head＝q　②link[q]！＝－1 and data>link[q][0] ③link[q][1]！＝－1
C.①head＝len(link)－1　②link[q]！＝－1 and data>link[q][0]　③link[q][1]！＝－1
D.①head＝len(link)－1　②q！＝－1 and data>link[q][0]　③q！＝－1
2.有如下Python程序段：
a＝[[6，6]，[5，0]，[1，3]，[2，5]，[2，1]，[2，4]，[9，－1]]
key＝int(input())
p＝q＝head ＝2
while p！＝－1 and a[p][0]<＝key：
　 q＝p
　　p＝a[p][1]
if p＝＝head：
　　a.append([key，head] )
　　head＝len(a)－1
else：
　　a.append([key，p] )
　　a[q][1] ＝len(a)－1
print(a[－1])
程序段运行后，若输入2，则输出的结果是(　　)
A.[2，－1] B.[2，1]
C.[2，4] D.[2，5]
3.有如下Python程序段：
n＝int(input(″输入一个数：″))
a＝[]；head＝－1
while n>0：
　　r＝1－n%2
　　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
4.已知链表结构a[i][0]表示元素，a[i][1]表示下一个元素的下标，head表示头元素，在已知有序的链表a中插入数值pb(pb>a[head][0])。代码如下，
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]
a.append([p，②________ ])
a[tmp][1]＝len(a)－1
划线处合适的代码依次为(　　)
①a[tmp][0]A.①③ B.①④ C.②③ D.②④
5.找出序列中的最大数，并将其放到序列的最后面。实现上述功能的代码如下：
#链表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
6.在升序链表a中插入一个不重复数据data，仍保持链表的升序状态。使用Python程序实现插入操作，代码如下：
data＝[[20，4]，[6，3]，[35，5]，[18，0]，[27，2]，[59，－1]]
p＝head＝1
data＝int(input())
if data<＝a[head][0]:
　 a.append([data，head])
　 head＝len(a)－1
else：
　 q＝a[p][1]
　 while ①________and data>a[q][0]：
　 p＝q
　 q＝a[p][1]
　 ②________
　 a.append([data，q])
则划线处的代码为(　　)
A.①p！＝－1　②a[p][1]＝len(a)－1
B.①q！＝－1 ②a[p][1]＝len(a)
C.①q！＝－1 ②a[q][1]＝len(a)－1
D.①p！＝－1 ②a[q][1]＝len(a)
7.有如下Python程序段：
a＝[[7，3]，[5，0]，[2，1]，[9，－1]]
head＝2
key＝int(input(″输入一个数字″))
p＝q＝head
while p！＝－1 and a[p][0]　 q＝p
　 p＝a[p][1]
if p＝＝head：
　 a.append([key，head])
　 head＝len(a)－1
else：
　 a.append([key，p])
　 a[q][1]＝len(a)－1
print(a[－1])
程序段运行后，若输入2，则输出的结果是(　　)
A.[2, －1] B.[2, 1] C.[2, 2] D.[2, 3]
8.某个正整数的每位数依次存储在链表d中各节点的数据区域中。例如，正整数572存储情况如图a所示，h为d的头指针。将该正整数翻倍后的计算结果(如572翻倍后的结果为1144)仍以这个链表存储，最高位存储于头节点中，如图b所示。实现该功能的程序段如下：
if d[h][0] > 4：
　 d.append([0，h])　#链表d新增一个节点
　 h ＝ len(d) － 1
p ＝ h
while p ！＝ －1：
　　d[p][0] ＝ d[p][0] * 2 % 10
　　cur ＝ d[p][1]
　　
　　p ＝ d[p][1]
方框中应填入的正确代码为(　　)
A.if cur ！＝ －1 and d[cur][0] > 4：
　　 d[p][0] ＋＝ 1
B.if cur ！＝ －1 and d[p][0] > 4：
　　 d[cur][0]＝(d[p][0]*2＋1)∥10
C.if cur ！＝ －1 and d[cur][0] > 4：
　　 d[p][0]＋＝(d[cur][0]*2＋1)%10
D.if cur ！＝ －1 and d[p][0] > 4：
　　 d[cur][0] ＋＝ 1
9.流浪地球2演员表lnk是一个链表，对链表lnk处理成男女演员两条链表。算法如下，遍历链表，如果是第1位女演员则从男演员链表删除该节点，如果不是第1位女演员，把该节点加入女演员链表的尾部，同时从男演员链表中删除，最后输出两条链表，代码如下：
lnk＝[['吴*'，'男'，1]，['刘**'，'男'，3]，['郭*'，'男'，4]，['朱***'，'女'，2]，['李**'，'男'，6]，['王*'，'女'，8]，['佟**'，'女'，7]，['沙*'，'男'，5]，['宁*'，'男'，－1]]
p＝q＝headA＝0　#headA为男演员链表头指针
r＝headB＝3　#headB为女演员链表头指针，r为尾指针
while p！＝－1：
　　if lnk[p][1]＝＝'男'：
　 q＝p　
　　elif headB！＝p：　#把p节点链入女性演员链表尾部
　　　
　　else：
　　　 lnk[q][2]＝lnk[p][2]
　　p＝lnk[p][2]
lnk[r][2]＝－1
#使用headA，headB分别作为男性演员、女性演员链表头指针，遍历输出lnk，代码略
加框处代码由下列语句组成①lnk[q][2]＝lnk[p][2]
②lnk[r][2]＝p　③r＝lnk[r][2]　④lnk[q][2]＝－1则合适的顺序是(　　)
A.④②③ B.③①② C.③②① D.②③①
重难点4　循环链表及链表的简单应用
1.n个人排成一圈，从某个人开始，按顺时针方向从No.1开始依次编号至No.n。从No.1的人开始顺时针“1，2，3，…，m，1，2，3，…”报数，报到m(m>1)的人退出圈子。这样不断循环下去，输出最后剩下的一个人的初始编号。实现该功能的Python程序段如下：
n＝int(input())
m＝int(input())
a＝[]
for i in range(n)：
　 a.append([″No.″＋str(i＋1)，(i＋1)%n])
head＝0；p＝head；cnt＝1
while p！＝a[p][1]：
　 pre＝p
　 p＝a[p][1]
　 cnt＋＝1
　 if cnt＝＝m：
　
print(a[p][0])
上述程序段中方框处可选代码为
①a[p][1]＝a[pre][1]　②a[pre][1]＝a[p][1]　③p＝a[pre][1]　④p＝a[p][1]　⑤cnt＝1　⑥cnt＝0
则应填入的代码依次为(　　)
A.①③⑤ B.②④⑤ C.①③⑥ D.②③⑥
2.某Python程序段如下：
b＝[[92，2]，[98，4]，[91，1]，[88，0]，[95，3]]
h＝p＝0
while b[p][1]！＝h：
　　print(b[p][0]，end＝″，″)
　　p＝b[p][1]
print(b[p][0])
运行该程序段，输出的内容为(　　)
A.88，91，92，95，98 B.98，95，92，91，88
C.92，91，98，95，88 D.98，95，88，92，91
3.有如下Python程序：
from random import *
a＝[[″e″，4]，[″g″，8]，[″h″，5]，[″h″，0]，[″n″，1]，[″o″，7]，[″S″，3]，[″u″，6]，[″Z″，2]]
k＝randint(1，4)*2＋1
p＝q＝6
while k>0：
　　p＝a[p][1]
　　k－＝1
while p！＝1：
　　q＝a[q][1]
　　p＝a[p][1]
print(a[q][0])
运行后，输出值不可能是(　　)
A.g B.h C.u D.o
4.小明设计了一个中华小曲库，其中导入了10000首歌曲，包含4种类型(编号从0－3)，每首歌曲都有自己的歌曲编号，歌曲编号的第一位是其类型，比如某歌曲编号为00041，代表这是类型0的第42首歌。已知本曲库有一个最近点播榜，分别记录每种类型最近点播的5首歌，当点播歌曲时记录规则如下：
①若榜单内不足5首歌，且被点播歌曲不在榜单上，则将其记录在该类型乐曲榜单首位，如图a所示，点播歌曲编号为20005，则在类型2的榜单榜首添加歌曲；若已在榜单上，则将其移至榜单首位，如图b所示点播歌曲00021。
②若榜单内已有5首歌，则将榜尾的乐曲删除，在榜首添加被点播歌曲，如图c所示点播歌曲00006。
现有榜单： 00092##00008##00015##00001##00021## 10004##10018##10298##10022## 20001## 30065## 请输入点播的歌曲：20005 现有榜单： 00092##00008##00015##00001##00021## 10004##10018##10298##10022## 20005##20001## 30065##
图a
现有榜单： 00092##00008##00015##00001##00021## 10004##10018##10298##10022## 20005##20001## 30065## 请输入点播的歌曲：00021 现有榜单： 00021##00092##00008##00015##00001## 10004##10018##10298##10022## 20005##20001## 30065##
图b
现有榜单： 00021##00092##00008##00015##00001## 10004##10018##10298##10022## 20005##20001## 30065## 请输入点播的歌曲：00006 现有榜单： 00006##00021##00092##00008##00015## 1000#10018##10298##10022## 20005##20001## 30065##
图c
(1)如在图c的基础上继续点播“00005，10002，00008，00005”，类型0的榜单中第2首歌的编号为________。
(2)已知列表lst中存放曲库中每种类型歌曲的原始信息，列表中每一个数据元素由2个部分组成，如lst[7]＝[″消愁″，0]，第一个部分为歌曲名称，第二个为歌曲类型(用数字0－3表示)，为了方便对所有歌曲进行管理与编号，现在需要以类型为主关键字，歌曲名称为次关键字进行升序排序，代码实现如下：
n＝ len(lst)
num ＝ 0
for i in range(n－1)：
　 for j in range(n－i－1)：
　 if lst[j][1]>lst[j＋1][1]：
　　　　 lst[j]，lst[j＋1] ＝ lst[j＋1]，lst[j]
　　　 num ＋＝1
　 elif lst[j][1]＝＝ lst[j＋1][1] and lst[j][0]>lst[j＋1][0]：
　　　　 lst[j]，lst[j＋1]＝lst[j＋1]，lst[j]
　　　　 num＋＝1
为测试程序正确性，小明设置测试了数据lst＝[[″bc″，2]，[″abc″，2]，[″aac″，1]，[″c″，2]，[″ac″，1]]，则程序运行后，num的值为________。
(3)程序“最近点播榜”代码实现如下，请补全划线处代码。
def select(name，kind)：
　 head ＝ leader[kind][0]
　 if head ＝＝－1：
　 data.append([name，－1])
　 leader[kind][0]＝ len(data)－1
　 leader[kind][1]＋＝ 1
　 return
　 elif data[head][0]！＝ name：
　 q＝p＝head
　 ①________
　 while data[p][1]！＝－1:
　　　 if name ＝＝ data[data[p][1]][0]：
　　　　　 tmp＝ data[p][1]
　　　　　 data[p][1]＝data[tmp][1]
　　　　　 data[tmp][1]＝ head
　　　　　 leader[kind][0]＝ tmp
　　　　　 flag ＝ False
　　　　　 break
　　　 q＝p；p＝data[p][1]
　 if　②________：
　　　 data.append([name，head])
　　　 leader[kind][0] ＝ len(data)－1
　　　 leader[kind][1]＋＝1
　 elif flag：
　　　 data[q][1]＝－1
　　　 data[p][0]＝ name
　　 ③__________
　　 leader[kind][0]＝ p
　　return
leader ＝[]
for i in range(4)：
　　　leader.append([－1，0])
data＝[]
while True：
　　　#输出各类型音乐点播榜单，代码略
　　　name＝input(″请输入点播的歌曲″)
　　　kind＝ int(name[0])
　　　select(name，kind)
5.某学校举办社团节，在一条直路的同侧依次有n个社团展位，按展位到入口距离从1至n依次编号。从入口处走到第1个展位需要花费dis[0]单位时间，从第i个展位走到第i＋1个展位需要花费dis[i]单位时间。每个展位举行若干活动，每参加一个活动需要5单位时间。对于第i个展位，第一次参加活动获得a[i－1]个积分，第二次参加活动获得a[i－1]－b[i－1]个积分，第三次参加活动获得a[i－1]－2*b[i－1]个积分……以此类推。现在小明从入口处出发，他共有m单位时间自主选择参与社团的活动并回到入口处。编写程序实现规定时间内获得最多积分的活动方案及获得的积分数。
例：
展位 1 2 3
首次活动积分 10 15 20
每次下降的积分 4 6 4
与前一展位之间步行所花时间 1 3 4
若小明可用时间为28，部分方案如下：
方案1：参加前1个展位活动，有5次活动机会，可得积分为10＋6＋2＝18
方案2：参加前2个展位活动，有4次活动机会，可得积分为15＋10＋9＋6＝40
方案3：参加前3个展位活动，有2次活动机会，可得积分为20＋16＝36
则可获得的最多积分为40，运行界面如图所示。
展位数：3 可用时间：28 各展位首次参加活动可获得的积分：10 15 20 各展位每次下降的积分：4 6 4 相邻展位之间步行花费时间：1 3 4 能获得的最多积分是：40 各展位参加的活动次数分别为：[2，2，0]
(1)若小明可用时间为32，按上表数据可得最多积分为________。
(2)定义如下insert(head, r)函数，功能是在首节点下标为head的链表中插入下标为r的节点，返回新的链首节点下标。data[i]存储下标为i的节点数据，data[i][0]存储目前参加活动能获得的积分，data[i][1]存储参加活动后要下降的积分，data[i][2]存储后继节点下标。
def insert(head, r)：
　 p ＝ q ＝ head
　 while ：
p ＝ q
q ＝ data[q][2]
　 if q ＝＝ head：
data[r][2] ＝ head
head ＝ r
　else：
data[p][2] ＝ r
data[r][2] ＝ q
　return head
若函数加框处代码误写为″ data[r][0] < data[q][0]″，会导致某些情况下无法得到符合函数功能的结果。调用insert(head, r)函数，下列4组数据中能测试出这一问题的是________(单选，填字母)。
A.data＝[[6，6，－1]，[10，3，3]，[2，11，－1]，[7，5，2]]; head＝1; r＝0
B.data＝[[6，6，－1]，[10，3，3]，[2，11，－1]，[7，5，0]]; head＝1; r＝2
C.data＝[[6，6，2]，[10，3，0]，[2，11，－1]，[7，5，－1]]; head＝1; r＝3
D.data＝[[6，6，2]，[10，3，－1]，[2，11，－1]，[7，5，0]]; head＝3; r＝1
(3)实现上述功能的Python程序如下，请在划线处填入合适的代码。
'''
展位数存入变量n，可用时间存入变量m，各展位首次参加活动可获得的积分存入a列表，各展位每参加一次活动要下降的积分存入b列表，相邻展位之间步行花费时间存入dis列表，dis[0]为入口到第1个展位步行花费时间，dis[i](i>0)为第i个展位到第i＋1个展位步行花费时间，代码略
'''
for i in range(1, n):
　 dis[i] ＝ ①________
data ＝ []
for i in range(n):
　 data.append([a[i], b[i], －1])
ans ＝ 0　#记录能够获得的最多积分
best ＝ []　#记录一种能够获得最多积分的活动方案
for i in range(n)：
　 head ＝ －1
　 for j in range(i ＋ 1)：
　 data[j][0] ＝ a[j]
　 head ＝ insert(head, j)
　 t ＝ (m － 2 * dis[i]) ∥ 5
　 if t <＝ 0: break
　 total ＝ 0
　 count ＝ [0] * n　#记录临时方案
　 while　②________ ：
p ＝ head
head ＝ data[head][2]
total ＋＝ data[p][0]
count[p] ＋＝ 1
data[p][0] ＝③________
if data[p][0] > 0：
　　　　　head ＝ insert(head, p)
　　　t －＝ 1
　 if total > ans：
#更新ans和best代码略
#输出代码略
6.某工程的A项目有n个任务组(编号为0～n－1)，供料商每小时只提供1份原料，各组按到达时刻(到达时刻各不相同)陆续加入领料队列，领取1份原料后到队列末尾重新等待，直至领完所需原料，离开队列。若多组同时入队，则到达时刻早的优先入队。编写程序模拟领料过程，先筛选出属于A项目的任务组，再计算每个任务组完成领料的时刻(时间单位：小时)，请回答下列问题：
任务组别 到达时刻 原料需求量
第0组 0 3
第1组 1 2
第2组 2 1
图a
时刻 领料队列 轮到领料的组别
0 0 0
1 0，1 0
2 1，0，2 1
3 0，2，1 0
4
5 1 1
注：领料队列中数字代表任务组编号
图b
(1)某项目任务组信息如图a所示，部分领料过程如图b所示，结合题意，第 4 时刻的领料队列是________(单选，填字母：A.2，1，0/B.2，1/C.2，0，1)。
(2)定义如下 filte(task，st)函数：
def filte(task，st)：
　 i ＝ 0 ; j ＝ 0 ; n ＝ len(task)－1
　 while j <＝ n：
　　　 if task[j][0] ＝＝ st:
　　　 task[i] ＝ task[j]
　　　 i ＋＝ 1
　　　 j ＋＝ 1
　 return i
若task的值是[['A'，0，3]，['B'，1，3], ['B'，2，6], ['A'，3，4], ['A'，4，5]]，st 的值是'A'，执行语句 m＝ filte(task，st)后，m的值是________。
(3)编写程序模拟任务组领料过程，输出每个任务组完成领料的时刻，部分Python 程序如下，请在划线处填入合适的代码。
def proc(task, st)：
　 m ＝ filte(task, st)
　 for i in range(m)：
　 task[i].append(－1)
　 order ＝ [0] * m
　 i ＝ 0；ct ＝ 0；t＝0
　 while i < m or t　　　if i < m and task[i][1] <＝ ct:
　　　 if i＝＝t：
　　　　　 ①________
　　　　　 task[p][3] ＝ i
　　　 else：
　　　　　 task[i][3] ＝ task[p][3]
　　　　　　 task[p][3] ＝ i
　　　　 p ＝ i
　　　 i ＋＝ 1
　 if i>t：
　　　 ②______
　　　 task[k][2] ＝ task[k][2] － 1
　　　 if task[k][2]＝＝ 0：
　　　　　　 order[k] ＝ ct
　　　　　　 ③________
　　　　　　 t＋＝1
　　　 else：
　　　　　　 p ＝ task[p][3]
　 ct ＋＝ 1
　 return order
'''每个任务初始数据存入 task 列表，task[i]包含 3 项，task[i][0]为该组项目名称，task[i][1]为该组到达时刻，task[i][2]为该组原料需求量，数据按到达时刻升序排列，代码略'''
st ＝″A″
print(proc(task，st))　#输出该项目中每个任务组完成领料的时刻
专题17　链　表
学习目标　1.掌握链表的概念和链表的遍历方法；
2.掌握链表头节点的插入和删除操作；
3.掌握链表除头节点外的其他节点的插入和删除操作.
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表每个节点的结构是相同的，由数据区域和指针区域组成，其中指针区域指向下一个节点的索引。链表的访问必须从头节点开始，因此头指针是链表必不可少的元素。
(2024年1月浙江省选考)使用列表d模拟链表结构(节点数大于0)，每个节点包含数据区域和指针区域，h为头指针。链表中各节点已按数据区域中数值的绝对值由小到大排列，如图a所示。现要修改该链表各节点的链接关系，使链表各节点按数据区域中的数值由小到大排列，结果如图b所示。实现该功能的程序段如下，方框中应填入的正确代码为(　　)
t＝h
p＝d[h][1]
while p ！＝ －1 ：
　 q＝d[p][1]
　　
　　p＝q
d[t][1]＝－1
答案　C
解析　本题考查链表的头插法和尾插法。程序实现的功能是从第2个节点开始，将遍历到节点插入新链表的头部或尾部。题图a按绝对值升序排序数据，链表中数据依次为－11，14，16，17，－18，要求改变链接关系，使链表各节点按数据区域中的数值由小到大排列。若链表中只有1个节点，其值无论是正数还是负数，均是最小的数。同时他既是头节点h，也是尾节点t。因此变量p从链表第2个节点开始遍历各个节点，若遍历到负数，则该数绝对值越大，其值就越小，需将该节点从原链表中删除，并移动到头节点的前面，进行的操作是将该前节点p指向原头节点h，同时修改当前位置为头指针。若为正数，将该节点链接到尾节点t的后面。
重难点1　链表的遍历
链表的遍历必须从头节点开始，每个节点包含数据区域和指针区域，数据区域可能有多个值，指针区域值往往在节点最后一个位置。若当前q指向头指针head，那么a[q]是整个节点的值，a[q][0]是数据区域的值，a[q][1]是下一节点的索引，通过语句q＝a[q][1]，实现指针向后移动。
例题 某公交路线的站点名称、经度、纬度和下一个站点序号(经纬度已转换为平面坐标数据)存储在数组 a 中，现计算相邻两个站点距离的总和。
import math
a＝[[″廊桥″，3，2，3]，[″徐岙″，6，11，2]，[″北门″，13，8，－1]，[″上通″，3，7，1]]
head＝0 ; s＝0
p＝a[head][3]
while(1)________：
　　s＋＝math.sqrt((a[p][1]－a[head][1])**2＋(a[p][2]－a[head][2])**2)
　　(2)________
　　(3)________
print(s)
上述程序段划线处可选的代码为(　　)
①a[head][3]！＝－1　②head＝p　③p＝a[head][3]　④head！＝－1，则(1)、(2)、(3)处的代码依次为(　　)
A.①②③ B.④②③ C.④③② D.①③②
思维点拨
明考向 本题考查链表的遍历
精点拨 从当前链表的头节点开始遍历，与下一个节点p的距离，因此head要不断地后移，head＝p，而p为新节点的后继节点。当头指针节点的后继为－1时，表示遍历完了
答案　A
变式 使用链表结构模拟某景区游玩路线，链表a中每一个节点包含3个数据，第1个为景点名称，第2个为预计游玩时间(单位：分钟)，第3个为下一个景点指针。景区可以从多个景点的大门进入，但只能从″天梯″离开，输出显示各大门进入路线及预计总时间的代码如下。
a＝[[″迎客松″，21，2]，[″激流勇进″，40，2]，[″天空栈道″，50，5]，[″一线天″，30，4]，[″飞来峰″，60，5]，[″天梯″，20，－1]]
head＝[0，1，3]
for i in range(len(head))：
　 (1)________
　 s＝a[p][1]
　 while a[p][2]！＝－1：
　　　 print(a[p][0], end＝″→″)
　　　 (2)________
　　　 (3)________
　 print(a[p][0])
print(″预计时间：″，s，″分钟″)
上述程序划线处的可选代码有： ①p＝head ②p＝head[i]　③s＋＝a[p][1]　④p＝a[p][2]，则(1)(2)(3)处代码依次为(　　)
A.①③④ B.①④③ C.②③④ D.②④③
答案　D
解析　本题考查多条链表的遍历。3条链表构建在数组a中，头指针存储在数组head中，需遍历头指针数组，从而来遍历3条链表。(1)处为当前节点赋值为头指针head[i]，变量s存储所有节点游览总时间。(2)(3)遍历链表，并统计各个节点游览时间和，由于当前节点已经计入总时间，因此先要跳转到下一点，将下一节点的时间加入总时间，注意遍历结束的条件是当遍历到尾节点时，终止遍历。
重难点2　链表节点的删除
在数组中删除某个节点，往往需把该节点后面的值往前移，时间复杂度为线性阶O(n)。链表节点的删除分为头节点的删除和其他节点的删除，头节点的删除只要移动头指针到下一节点，即head＝a[head][1]即可，其他节点的删除，只要修改该节点的前驱节点的指针区域值为该节点的后继节点索引即可，时间复杂度为常量阶O(1)。
例题 使用列表a模拟链表结构(节点数大于0)，每个节点包含数据区域和指针区域，head为头指针，链表中各节点已按数据区域中数值的由小到大排列。现要修改该链表各节点的链接关系，删除链表中数据区域数值相同的节点，使得链表各节点的数据区域值不重复。
实现该功能的程序段如下，方框中应填入的代码段可行的是(　　)
p ＝ head
q ＝ a[p][1]
while q！＝－1：
　　
a[p][1]＝－1
A .if a[p][0]！＝a[q][0]:
a[p][1]＝q
p ＝ q
else：
p ＝ q
q＝a[q][1]
B .if [p][0]！＝a[q][0]：
a[p][1]＝q
p ＝ q
q＝a[q][1]
C .if a[p][0]＝＝a[q][0]：
p ＝ q
q＝a[q][1]
else：
a[p][1]＝q
p ＝ q
q＝a[q][1]
D .if [p][0]＝＝a[q][0]：
q＝a[q][1]
else：
p ＝ q
a[p][1]＝q
思维点拨
明考向 本题考查链表节点的删除
精点拨 当前节点q从第2个节点开始遍历，节点p是一段连续重复的开始位置，若a[p][0]与a[q][0]相等，则q向后遍历，否则让p的直接指向q，同时更新当前p的值为q。如链表数据1，2，2，2，3，3，3，有多个2时，让p指向第1个2位置，当q遍历到值为3时，让p直接指向3，删除中间的2。若最后出现多个重复的值时，语句a[p][1]＝－1的功能是删除后面重复的数据
答案　B
变式 使用列表模拟单向链表，链表中p节点的a[p][0]存储数据，a[p][1]存储其后继节点的指针。编写Python程序删除链表中所有偶数项(头节点为该链表的第1项)，部分代码如下：
p＝head
while p！＝－1：
　　q＝a[p][1]
　　if ①________：
　 a[p][1]＝a[q][1]
　　②________
上述程序段划线处可选语句为(　　)
A.①q！＝－1　　　 ②q＝a[q][1]
B.①q！＝－1　　　 ②p＝a[p][1]
C.①a[q][1]！＝－1　②q＝a[q][1]
D.①a[q][1]！＝－1　②p＝a[p][1]
答案　B
解析　本题考查链表节点的删除。 p是当前节点，也是奇数节点，q是偶数节点。若q不为－1，采用语句a[p][1]＝a[q][1]删除q节点，同时更改p的值为q的后继。
重难点3　链表节点的插入
在数组中插入节点的时间复杂度为线性阶O(n)。链表节点的插入分为在头节点前的插入和其他节点前插入两种，头节点前插入新节点，该节点指向原头节点，并要修改head指针。在当前节点q前插入新节点，该新节点的后续是q，将修改q的前驱节点指针区域值。
例题 使用列表da和db模拟2个链表结构(节点数均大于0)，每个节点包含数据区域和指针区域，ha和hb分别为2个链表的头指针。链表中各节点已按数据区域中数值由小到大排列，且链表da头节点值小于链表db头节点值。现要将链表db中数据合并到链表da中，且保持升序排列。实现该功能的程序段如下，方框中应填入的正确代码为(　　)
t＝ha
while hb！＝－1：
　　q＝da[t][1]
　　
A.if q＝＝－1 or da[q][0]>db[hb][0]：
　　 da.append([db[hb][0]，q])
　　 da[t][1]＝len(da)－1
　　 hb＝db[hb][1]
t＝da[t][1]
B.if q＝＝－1 or da[q][0]>db[hb][0]：
　　 da.append([db[hb][0]，q])
　　 da[t][1]＝len(da)－1
　　 hb＝db[hb][1]
　　 t＝da[t][1]
C.if q＝＝－1 or da[q][0]>db[hb][0]：
　　 da.append([db[hb][0]，q])
　　 da[t][1]＝len(da)－1
　　 hb＝db[hb][1]
t＝q
D.if q＝＝－1 or da[q][0]>db[hb][0]：
　　 da.append([db[hb][0]，q])
　　 da[t][1]＝len(da)－1
hb＝db[hb][1]
t＝da[q][1]
思维点拨
明考向 本题考查链表节点的插入
精点拨 t是新链表的尾指针，hb是链表db的当前节点指针。链表da头节点是值最小的，成为新链表的头节点，将链表db和原链表da第2个节点及后面所有节点采用尾插法合并到新链表da中。将链表db节点插入到新链表方法：当完成遍历da链表或者da链表尾指针后面节点值比db链表当前节点值的大时，①将链表db当前节点值添加到链表da中，成为最后一个元素，新节点指向原链表da尾节点t的后继q；②将尾节点t指向新添加的节点len(da)－1；③更新链表db的当前节点指针hb和链表da尾节点指针t。将链表da节点插入到新链表方法：由于链表的链接关系已经建立，只要更新尾节点t即可。新链表的尾节点无论是来自da还是db，均需要更新尾指针t，因此只要把这条语句放在判断结构的下方即可
答案　A
变式 列表a存储了两个升序链表的节点，每个节点包含数据区域和指针区域，头指针分别为ha、hb，且a[ha][0]q ＝ h ＝ ha
p ＝ a[ha][1]
k ＝ hb
while p ！＝ －1 and k ！＝ －1：
　 if a[p][0] <＝ a[k][0]：
　 q ＝ p
　 p ＝ a[q][1]
else：
　
if k！＝－1：
　 a[q][1] ＝ k
方框中应填入的正确代码为(　　)
答案　B
解析　本题考查链表节点的插入。由于a[ha][0]小于a[hb][0]，因此p从ha所在链表第2个节点开始遍历，q为p的前驱，k遍历hb所在链表。当条件a[p][0]<＝ a[k][0]成立时，q和p继续遍历；若条件不成立，将节点k插入到节点p的前面。
重难点4　循环链表及链表的简单应用
循环链表是一种特殊的链式存储结构，其中最后一个节点的指针指向头节点，形成一个环。
例1 报数游戏。已知班上有n名学生(用编号1，2，3，……，n分别表示)，学生按照编号由小到大顺时针围成一个圆圈，从编号为1的学生开始顺时针报数，报到m的同学出列；下一名同学又从1开始报数，报数为m的同学继续出列；以此规律重复下去，直到剩下最后一位同学为止。
(1)当n＝6，m＝3时，最后留下的同学的编号是________。
(2)下列代码通过构造一个循环单向链表，模拟报数的过程，逐一删除报数为m的节点，直到剩下一个节点为止。请在划线处填入合适的代码。
n＝int(input(″n＝″))
m＝int(input(″m＝″))
lst＝[]
for i in range(n－1):
　 lst.append([i＋1，i＋1])
lst.append(①________)　#将尾节点的指针指向头节点，构成循环单向链表
p＝len(lst)－1
while n>1：
　　for i in ②________：　 #从1至m－1依次报数
　 p＝lst[p][1]
　　out＝lst[p][1]
　　③________
　　n＝n－1
print(″最后留下的同学的编号是：″，lst[p][0])
思维点拨
明考向 本题考查循环链表的算法实现
精点拨 (1)3号和6号先出列，剩余编号为1245，4号和2号出列，接着5号出列，剩余1号。(2)①尾节点值为n，指向头节点0。②从 1至m－1依次报数，共循环了m－1次。③当前节点指针从尾节点开始，连续进行m－1次报数后，下一个节点out将要被删除，因此语句lst[p][1]＝lst[out][1]实现了删除out节点的操作
答案　(1)1　(2)①[n，0]　②range(1，m)或range(m－1)　③lst[p][1]＝lst[out][1]
变式1 有如下Python程序段：
a＝[4，5，3]
d＝[[3，″A″，2]，[6，″B″，0]，[3，″C″，1]]
q＝head＝1
t，n＝2，3
ans＝″″
i＝0
while n>0 and i　 if d[q][0]>a[i]：
　　　d[q][0]－＝a[i]
　　　t＝d[t][2]
　　　i＋＝1
　 else：
　　　a[i]－＝d[q][0]
　　　d[t][2]＝d[q][2]
　　　n－＝1
　　　ans＋＝d[q][1]
　 q＝d[q][2]
执行该程序段后，ans的值是(　　)
A.″ABC″ B.″ACB″ C.″BAC″ D.″CBA″
答案　A
解析　本题考查循环链表以及队列的算法实现。链表d构成一个循环链表，队列依次为BAC，若a[i]的值能分配给队首，则队首元素出队，否则更新剩余部分，再重新入队。变量t是链表的尾指针，指针q从头节点2开始遍历，若当前节点d[q][0]大于a[i]，a[i]不够分配，更新d[q][0]和尾指针t，同时i向后移动。若当前节点d[q][0]小于等于a[i]，删除当前节点q，同时n的值减少1个，表示完成一个元素的分配，同时更新a[i]。″B″更新为2后入队；″A″出队，″C″更新为2后入队；″B″出队，″C″出队。
例2 某编程兴趣小组设计了一个点歌模拟程序，功能如下：
运行程序后，从键盘输入“A”，则显示已点的歌曲列表(歌单)；输入“B”则可以自行输入歌曲并添加到歌单以完成点歌；输入“C”则可以将指定的歌曲置顶等待播放；输入“D” 则播放当前第一首歌曲，并将该歌曲从列表中删除；输入“E”则关闭程序并退出。程序运行界面如图所示。
请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A God Is a Girl　十年　年少有为　七里香　淡季动物园 请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：B 请输入歌曲：兰亭序 请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：B 请输入歌曲：想自由 请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A God Is a Girl　十年　年少有为　七里香　淡季动物园　兰亭序　想自由 请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：C 请输入歌曲：七里香 请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A 七里香　God Is a Girl　十年　年少有为　淡季动物园　兰亭序　想自由 请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：C 请输入歌曲；想自由 请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A 想自由　七里香　God Is a Girl　十年　年少有为　淡季动物园　兰亭序 请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：D 请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A 七里香　God Is a Girl　十年　年少有为　淡季动物园　兰亭序 请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：E
Python代码如下所示，请在划线处填入合适的代码。
data＝[[″十年″，4], [″淡季动物园″，－1], [″God Is a Girl″，0], [″七里香″，1], [″年少有为″，3]]
head＝2
tail＝1
while True：
　 cmd ＝input(″请输入指令 A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：″)
　　if cmd＝＝″A″：
　 cur＝head
　 while cur！＝－1:
　　　　　print(data[cur][0]，end＝″″)
　　　　　cur＝data[cur][1]
　 print()
　　elif cmd＝＝″B″：
　 song＝input(″请输入歌曲：″)
　 data.append([song，－1])
　 if head＝＝－1：
　　　　　head＝tail＝len(data)－1
　 else：
　　　　　①________
　　　　　tail＝len(data)－1
　　elif cmd＝＝″C″：
　 song＝input(″请输入歌曲：″)
　 cur＝head
　 while cur！＝－1 and data[cur][0]！＝song:
　　　　　pre＝cur
　　　　　cur＝data[cur][1]
　if cur！＝－1 and cur！＝head：
　　　②________
　　　data[cur][1]＝head
　　　head＝cur
　　　if cur＝＝tail：
　　　 ③________
elif cmd＝＝″D″：
　if head＝＝tail:
　　 head＝tail＝－1
　else：
　　　④________
elif cmd＝＝″E″：
　break
明考向 本题考查链表的操作
精点拨 ①输入“B”则可以自行输入歌曲并添加到歌单，新节点插入在尾节点的后面，因此原尾节点应指向新插入的节点，同时更新尾节点。②输入“C”则可以将指定的歌曲置顶，data[cur][0]值为song表示找到节点cur，pre为cur节点的前驱，将cur移动到头节点前面，因此需要3步，第1步是将cur的前驱pre指向cur的后继，第2步是将cur指向原头节点，第3步是设置新的头节点为cur。③若cur是原尾节点tail，将cur修改为头节点后，新的尾节点为cur的前驱。④输入“D” 则播放当前第一首歌曲，并将该歌曲从列表中删除，条件head＝＝tail成立表示链表中只有一个节点，否则将头指针向后移动，删除头节点
答案　①data[tail][1]＝len(data)－1
②data[pre][1]＝data[cur][1]　③tail＝pre
④head＝data[head][1]
变式2 已知一个有7个节点的单向链表，设有头指针head和尾指针tail，如图所示，下列操作需要遍历多个节点的是(　　)
A.删除该链表中的最后一个节点
B.删除该链表中的第一个节点
C.在该链表第一个节点前插入一个新节点
D.在该链表最后一个节点后插入一个新节点
答案　A
解析　本题考查链表的遍历、插入和删除操作。A选项删除该链表中的最后一个节点，需修改最后一个节点的前驱节点指针域，因此需遍历多个节点。B选项只需修改头指针。C选项修改当前节点的指针值指向原头节点，并修改头指针为当前节点。D选项让原尾节点指向当前节点，并修改尾节点为当前节点。
重难点1　链表的遍历
1.下列关于单向链表的说法正确的是(　　)
A.必定有头指针和尾指针
B.每个节点都有一个后继节点
C.删除一个节点，需要修改两个指针
D.查找任一节点的算法时间复杂度为O(n)
答案　D
解析　本题考查链表相关知识。A选项单向链表必定有头指针，不一定要有尾指针。B选项尾结点没有后继节点。C选项单向链表删除一个节点，只需修改删除节点的前驱节点的后继指针即可。D选项链表的访问比较低效，每次遍历都需要从 head 头结点开始，故算法时间复杂度为 O(n)。
2.使用列表模拟单链表，其存储结构如图所示，遍历该链表，将访问到的节点的数据域的字符依次连接，得到字符串‘LOVE’，则指针域中的索引值依次为(　　)
A.0 1 2 3 B.3 1 0 2
C.2 0 －1 1 D.2 0 1 －1
答案　C
解析　本题考查链表的构建和遍历。L的后继节点为O，因此其指针区域值为1；O的后续为V，指针区域值为0; V的后续为E，指针区域值为2；E为尾节点，因此指针区域值为－1。
3.使用Python的二维列表来模拟单向链表，如下代码创建一个拥有4个节点的链表a
a＝[[″cat″，1]，[″dog″，2]，[″pig″，－1]，[″rabbit″，0]]
head＝3
依次输出各节点数据域的值，内容为(　　)
A.″cat″，″dog″，″pig″，″rabbit″
B.″pig″，″rabbit″，″cat″，″dog″
C.″pig″，″dog″，″cat″，″rabbit″
D.″rabbit″，″cat″，″dog″，″pig″
答案　D
解析　本题主要考查链表的操作。head＝3，即对应列表索引3，其值为“rabbit”，指向索引为0的节点，其值为“cat”，依此类推，依次输出各节点数据域的值，内容为″rabbit″，″cat″，″dog″，″pig″，故本题选D选项。
4.实现在链表c中找出最小值m的Python程序如下：
head＝3；p＝head；m＝c[head][0]
while (1)________：
　　(2)________
　　if c[p][0]　 m＝c[p][0]
上述程序段中划线处可选代码为：①p！＝－1　②c[p][1]！＝－1　③p＝p＋1　④p＝c[p][1]
则程序段中(1)、(2)处代码依次为(　　)
A.①③ B.②③ C.①④ D.②④
答案　D
解析　本题考查链表遍历和最值查找。当前节点从头节点开始遍历，最小值的初值为头节点大小，因此需先移动到下一节点，再与最值进行比较，同时终止遍历的条件是遍历到尾节点马上结束。
5.使用列表a模拟链表结构(节点数大于0)，每个节点包含数据区域和指针区域，head为头指针。链表中各节点已按数据区域中的数值由小到大排列。现要计算链表中的中位数，处在链表最中间位置的数叫做中位数。说明：当数据元素为奇数个时中位数为最中间的数，偶数个时中位数为最中间两个数的平均数。实现功能的Python程序如下，划线处应填入的正确代码为(　　)
fast＝slow＝head
while fast！＝－1 and ①________：
　 p＝slow
　 slow＝a[slow][1]
　 fast＝ a[a[fast][1]][1]
if ②________：
　 mid＝(a[p][0]＋a[slow][0])/2
else：
　 mid＝a[slow][0]
print(″中位数是：″， mid)
A.①slow！＝－1　　　 ②fast！＝－1
B.①a[slow][1]！＝－1 ②fast＝＝－1
C.①a[fast][1]！＝－1 ②fast！＝－1
D.①a[fast][1]！＝－1 ②fast＝＝－1
答案　D
解析　fast和slow分别表示快慢指针，fast每次遍历2个节点，若遍历完成后，fast的值为－1，表示节点数量为偶数，当a[fast][1]值为－1，遍历到尾节点，节点数量为奇数，遍历完成。
重难点2　链表节点的删除
1.某单向链表如下图所示，若要将数据 data3 和data4 同时从链表中移除，至少需要修改节点指针的数量是(　　)
A.1 B.2 C.3 D.4
答案　A
解析　只需修改data2的指针区域值修改为data4的指针区域值。
2.有下列Python程序段：
a＝[[1，3]，[1，0]，[7，1]，[4，5]，[1，－1]，[6，4]]
x＝1
p＝pre＝head＝2
if x＝＝a[head][0]：
　 head＝a[head][1]
else：
　 while p！＝－1 ：
if x＝＝a[p][0]：
　　　 a[pre][1]＝a[p][1]
else：
　　　 pre＝p
p＝a[p][1]
运行该段程序后，a[2][1]的值为(　　)
A.－1 B.0 C.1 D.3
答案　D
解析　本题考查链表的基本操作。如果链表头节点值为1，直接删除头节点，否则遍历链表，语句a[pre][1]＝a[p][1]的作用让节点p的前驱指向他的后继，即删除p节点。程序的功能是删除元素值为1的节点。
3.使用Python程序在链表a中删除一个数据data，代码如下：
import random
a＝[[87，1]，[93，3]，[97，5]，[95，2]，[80，0]，[98，－1]]
head＝4
x＝random.randint(0，len(a)－1) #randint(a，b)返回[a，b]区间内的一个随机整数
data＝①________
q＝head
while q！＝－1：
　 if ②________：
　 if q＝＝head：
　　　　head＝a[q][1]
　 else：
　　　　a[p][1]＝a[q][1]
　 break
else：
　 ③________
q＝a[q][1]
则划线处的代码为(　　)
A.①a[0][x]　②data＝＝a[q][0]　③p＝q
B.①a[0][x]　②data！＝a[q][0]　③p＝head
C.①a[x][0]　②data＝＝a[q][0]　③p＝q
D.①a[x][0]　②data！＝a[q][0]　③q＝head
答案　C
解析　本题考查遍历链表及删除节点操作。①x是链表中一个节点位置，从链表中被删除的数据a[x][0]。②判断当前节点a[q]的值是否是要删除的数据data。③遍历链表，如果当前节点是要删除的数据，且该节点是头节点，需要更新头指针head的值，若不是头节点，需让前驱节点p指向当前节点q的后继节点。若当前节点的数据域不是 data，则将当前节点 p 更新为前驱节点 q，并继续检查下一个节点。
4.用Python程序实现删除链表的倒数第n(n不大于链表长度)个节点，如n＝2时，链表
更新为
部分代码如下：
#读入链表存储在列表s中，head存储链表的头节点，代码略
n ＝ int(input())
p1＝p2＝ head
while p2！＝ －1：
　 if n >＝ 0：
　(1)________
　 n －＝ 1
　　else：
　 (2)________
　 p2 ＝ s[p2][1]
if p1 ＝＝ head and n>＝0：
　 head ＝ s[head][1]
else：
　　 (3)________
上述程序段中划线处可选的语句为：
①p1＝s[p1][1]　②p2＝s[p2][1]　③s[p1][1]＝s[s[p1][1]][1]　④s[p2][1]＝s[s[p2][1]][1]
则(1)～(3)划线处语句依次为(　　)
A.①③④ B.①④③ C.②①④ D.②①③
答案　D
解析　本题考查链表的删除。while循环查找待删除节点的前驱节点位置。通过p1和p2遍历链表，前n次只遍历p2，后续同时遍历p1和p2，当p2遍历结束时，p1刚好指向倒数第n＋1个节点。所以(1)处选p2＝s[p2][1]，(2)处选p1＝s[p1][1]。确定p1位置后，执行删除操作。如果p1指向头节点head，要删除头节点，即更新head指向原头节点指针区域对应的节点；否则删除p1的后继节点，即p1的指针区域更新为p1后继节点的指针区域，(3)处应选s[p1][1]＝s[s[p1][1]][1]。
重难点3　链表节点的插入
1.小张准备去多个城市旅游，他设计的行程若采用链表结构表示，如图a所示。若行程有变，需在“上海”与“成都”之间增加一站“杭州”，链表修改为如图b所示，有以下可选操作：
①“上海”所在节点的next值赋为“杭州”节点的next值
②“上海”所在节点的next值赋为5
③“杭州”所在节点的next值赋为“上海”所在节点的next值
④“杭州”所在节点的next值赋为－1
链表更新顺序正确的是(　　)
A.③① B.③② C.①④ D.②④
答案　B
解析　本题考查的知识点是链表元素的插入。链表中插入新元素并不需要进行元素位置移动，只需要进行节点指针域的更改即可。在“上海”与“成都”之间增加一站“杭州”，需要先将新元素“杭州”的指针域设置为“成都”所在位置，再更改节点“上海”的指针域至节点“杭州”所在位置。
2.有如下Python程序：
def lnkid(n，head):
　 p＝head
　 while head ！＝－1 and ①________：
　 p＝head
　 head＝a[head][1]
　 return p
a＝[[2，2]，[5，3]，[1，－1]，[3，0]，[7，1]]
head＝4
n＝int(input())
p＝lnkid(n，head)
if n>a[head][0]：
　 a.append([n，head])
　 head＝len(a)－1
else：
　 a.append([n，a[p][1]])
　 ②________
用列表a模拟一个降序链表，运行程序，输入自然数n，则链表增加一个新的节点，要使链表保持降序，则划线①②处代码分别为(　　)
A.①nB.①nC.①nD.①n>a[head][0] ②a[p][1]＝len(a)
答案　B
解析　本题考查链表的插入。①自定义函数lnkid的功能是查找n在链表中插入位置，head在不断地向后移动，因此n将和a[head][0]进行比较，当比a[head][0]小时，不断地向后查找位置。②语句p＝lnkid(n，head)将返回在节点p的后面插入新的数n，因此将修改a[p]节点指针区域值为当前插入点索引。
3.有两个降序序列的链表 a，b。现将链表 b 中的数据合并到链表 a，形成一个新的降序序列存于链表 a，实现数据合并的代码段如下：
a ＝ [[98，1]，[96，2]，[95，3]，[93，4]，[90，－1]]
b ＝ [[99，1]，[97，2]，[94，3]，[93，4]，[92，－1]]
head_a ＝ head_b ＝ 0
pre ＝ p ＝ head_a；q ＝ head_b
while q！＝－1：
　 if p！＝－1 and ：
　 pre＝p
　 p＝a[p][1]
　 else：
　 a.append()
　 if p＝＝head_a：
　　　 pre＝head_a＝len(a)－1
　 else：
　　　 a[pre][1]＝
　　　 pre＝len(a)－1
　 q＝b[q][1]
上述程序段中可选填的语句为：①a[p][0]>＝ b[q][0]　②a[p][0]<＝ b[q][0]　③q　④len(a)－1　⑤[b[p][0]，q]　⑥[b[q][0]，p]
则加框处填写的语句依次为(　　)
A.①⑥④ B.①⑤④ C.①⑥③ D.②⑥③
答案　A
解析　本题考查链表元素的遍历和插入操作。程序的功能将链表b中的数据合并到链表a，形成一个新的降序序列存于链表a。分别遍历两个链表，若链表a当前元素值a[p][0]大于等于链表b当前元素值b[q][0]，则链表a向后遍历，否则把链表b当前元素值b[q][0]插入到链表a当前元素前面。由于是要把链表b中的数据合并到链表a，因此链表b遍历完成后，结束程序。
4.将两个链表a(A→B→C)和b(D→E)按照间隔次序合并为一个链表，并将结果保存到链表a(A→D→B→E→C)中，部分程序如下：
#读取链表a和b，均存储在列表data中，其中ha表示a的头指针，hb表示b的头指针
p，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，则下列选项中，代码顺序正确的是(　　)
A.①④⑤ B.②③⑥ C.①④⑥ D.②③⑤
答案　B
解析　本题考查链表节点的插入操作。程序将节点q插入到节点p的后面，因此q的指针域的值将发生变化，为了链表b正常遍历，应先保存q的后继。插入过程中，由于已经保存了q的后继，因此可以先修改q的指向，再修改p的指向，最后将p移动到原插入节点q的后继。
5.用链表模拟队列操作(队列长度大于1)，链表的每个节点包含数据区域和指针区域。指针head指向队列的第一个元素，指针tail指向队列的最后一个元素，如图所示。现执行n次“出队后立即入队”操作，实现该功能的Python程序段如下：
k＝1
while k<＝n：
　　p＝head
　　
　　tail＝p
　　k＋＝1
上述程序段中方框处可选代码有
①head＝que[head][1]　②que[tail][1]＝head
③que[head][1]＝－1　④que[p][1]＝－1
则方框内应填入的正确代码顺序为(　　)
A.①②③ B.①②④ C.②①③ D.②①④
答案　D
解析　先采用尾插法将原头节点链接入链表，接着更新尾头节点，同时将新尾节点的指针区域值设置为1。
重难点4　循环链表及链表的简单应用
1.有如下程序段：
people＝[[1，1]，[2，2]，[3，3]，[4，4]，[5，5]，[6，0]]
k＝int(input())
n＝len(people)
q＝head＝0
i＝1
while n>1：
　　i＋＝1
　　if i＝＝k：
　 p＝people[q][1]
　 people[q][1]＝people[p][1]
　 if p＝＝head：
　　　 head＝people[q][1]
　 i＝1
　 n－＝1
　　q＝people[q][1]
print(people[head][0])
该程序段运行后，若输入2，则输出的结果为(　　)
A.3 B.5 C.6 D.2
答案　B
解析　本题考查循环链表的算法实现。每遍历一次，i增加1，实现计数。第1次删除节点2，第2次删除节点4，第3、4、5分别删除节点6、3、1，链表中只剩下节点5。
2.将A－K共13张黑桃扑克牌洗好后，把牌面朝下。第一张牌翻过来A，第2次将最上面第1张牌放到这叠牌的最下面，将第2张牌翻开，是黑桃2；第3次数将最上面第1、2张牌放到这叠牌的最下面，将第3张牌翻开，是黑桃3；依次类推将13张牌按从小到大的顺序翻出。求这叠牌洗好后，从上到下的原始顺序。
(1)程序运行结果如图所示，结合下面代码，当输入扑克牌数量num为6时，扑克牌从上到下的初始顺序最后输出结果为：________。
请输入扑克牌数量(1—13)：13 扑克牌从上到下的初始顺序为： A，8，2，5，10，3，Q，J，9，4，7，6，K，
(2)实现题中所述功能的Python程序如下，请在程序中划线处填入合适的代码。
num ＝ int(input(″请输入扑克牌数量(1－13)：″))
poker ＝ [[i ＋ 1，(i ＋ 1) % num　] for i in range(num)]　#创建循环链表
①________
cur ＝ poker[pre][1]
result ＝ []
for i in range(num)：
　 for j in ②________：
　 pre ＝ cur
　 cur ＝ poker[cur][1]
　 result.append(poker[cur][0])
　 poker[pre][1] ＝③________
　 cur ＝ poker[pre][1]
initial ＝ [0] * num
for k in range(num)：
　 initial[result[k]－1]＝④________
print(″扑克牌从上到下的初始顺序为：″)
ajqk ＝ {1：″A″， 11：″J″， 12：″Q″， 13：″K″}
for m in initial：
　 if m > 10 or m ＝＝ 1：
　 print(ajqk[m], end＝″，″)
　 else：
　 print(m, end＝″，″)
答案　(1)A，4，2，5，6，3　(2)①pre＝num－1　②range(i)　③poker[cur][1]或poker[poker[pre][1]][1]　④k ＋ 1
解析　本题考查循环链表的算法实现。(1)若输入6张牌，那么每次翻牌的位置依次是1, 3, 6, 2, 4, 5。将这些位置依次填入数字1－6，
位置 1 3 6 2 4 5
牌 A 4 2 5 6 3
可以得到原始的位置牌的点数。(2)①pre是当前节点cur的前驱，其初始值为尾节点位置。②变量i从0循环至，第i次循环时，翻了i张牌，因此需循环i次。③每次循环结束，获取当前翻开牌的位置，并依次存入数组result。变量k从0循环至num－1，result[k]表示第k＋1张牌的位置，result[k]－1表示原始位置数组initial的索引位置，其值为k＋1。
重难点1　链表的遍历
1.链表不具备的特点是(　　)
A.所需存储空间与存储元素个数成正比
B.插入、删除操作不需要移动元素
C.无须事先估计存储空间的大小
D.可随机访问任何一个元素
答案　D
解析　本题考查链表相关知识点。链表的访问必须从头节点开始。通过指针依次访问，不能随机访问任何一个元素。
2.某Python程序如下：
head ＝ 4
a ＝[[2，2]，[5，3]，[3，1]，[6，－1]，[1，0]]
p＝head
while a[p][1]！＝－1:
　　print(a[p][0]，end＝″→″)
　　p ＝ a[p][1]
程序运行后，输出的结果是(　　)
A.1→2→3→5
B.1→2→3→5→
C.1→2→3→5→6
D.1→2→3→5→6→
答案　B
解析　没有输出尾结点，输出前面4个节点的数据域，并以″→″结束，故答案为1→2→3→5→，选B。
3.王老师用链表模拟某次比赛中运动员的出场次序，运动员号码存储如下： a＝[[″e56″，4]，[″134″，－1]，[″215″，5]，[″098″，0]，[″144″，2]，[″024″，1]]。假设head＝3，小明同学的号码是“215”，则他的出场次序是(　　)
A.2 B.4 C.5 D.6
答案　B
解析　本题考查链表的遍历。head值为3，[″098″，0]为头节点，接着是[″e56″，4] [″144″，2] ，[″215″，5], [″024″，1], [″134″，－1]。
4.有如下Python程序段：
a＝[[2，2]，[5，3]，[3，1]，[6，－1]，[1, 0]，[4，2]]
p＝5
while a[p][1]！＝－1：
　　print(a[p][0]，end＝″→″)
　　p＝a[p][1]
则运行程序后，控制台输出的结果是(　　)
A.4→3→5 B.4→3→2→5→
C.4→3→5→ D.4→3→2→5
答案　C
解析　本题考查链表的遍历。条件a[p][1]！＝－1表示当前节点的指针区域值为－1，即当前节点为尾节点。当遍历到尾节点时，结束循环。
5.利用列表模拟非循环链表a(可能存在已被删除的节点)，下列程序运行完毕后，变量p表示尾节点的节点位置是(　　)
答案　B
解析　本题考查链表的遍历。A选项当前节点为p，当遍历到节点为空时停止遍历，因此遍历结束后，p节点为空，其前驱t为尾节点。B选项当前节点为p，若当前节点的指针区域值为－1，结束遍历，那么当前节点p为尾节点。C选项当前节点从头节点开始遍历，a[a[p][1]]指当前节点的后继节点，若该节点的指针区域值为－1，表示该节点为尾节点，当前节点为尾节点的前驱。D选项链表a可能存在已被删除的节点，因此len(a)的值可能大于节点总数。
6.某Python程序如下：
data＝[]
for i in range(len(a))：
　 data.append([a[i]，i＋1])
data[－1][1]＝－1
la＝head＝0
t＝data[head][1]
key，c＝2，0
while c<3 and t！＝－1：
　　if data[t][0]－data[la][0]　 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指针从链表的第二个节点开始遍历，1a指针是t节点的前驱，t节点减去前驱节点la的值小于key时，c计数，c的初值为0，计数到3时结束，也就是整个过程计数3次就结束，执行程序后t的值为6，也就是遍历到最后一个节点时程序才结束。
7.通过(共172张PPT)
专题17　链表
第三部分　数据的存储与逻辑结构
1.掌握链表的概念和链表的遍历方法；
2.掌握链表头节点的插入和删除操作；
3.掌握链表除头节点外的其他节点的插入和删除操作.
目 录
CONTENTS
体系构建
01
真题再现
02
考点精练
03
当堂检测
04
课后练习
05
体系构建
1
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表每个节点的结构是相同的，由数据区域和指针区域组成，其中指针区域指向下一个节点的索引。链表的访问必须从头节点开始，因此头指针是链表必不可少的元素。
真题再现
2
(2024年1月浙江省选考)使用列表d模拟链表结构(节点数大于0)，每个节点包含数据区域和指针区域，h为头指针。链表中各节点已按数据区域中数值的绝对值由小到大排列，如图a所示。现要修改该链表各节点的链接关系，使链表各节点按数据区域中的数值由小到大排列，结果如图b所示。实现该功能的程序段如下，方框中应填入的正确代码为(　　)
答案　C
解析　本题考查链表的头插法和尾插法。程序实现的功能是从第2个节点开始，将遍历到节点插入新链表的头部或尾部。题图a按绝对值升序排序数据，链表中数据依次为－11，14，16，17，－18，要求改变链接关系，使链表各节点按数据区域中的数值由小到大排列。若链表中只有1个节点，其值无论是正数还是负数，均是最小的数。同时他既是头节点h，也是尾节点t。因此变量p从链表第2个节点开始遍历各个节点，若遍历到负数，则该数绝对值越大，其值就越小，需将该节点从原链表中删除，并移动到头节点的前面，进行的操作是将该前节点p指向原头节点h，同时修改当前位置为头指针。若为正数，将该节点链接到尾节点t的后面。
考点精练
3
重难点1　链表的遍历
链表的遍历必须从头节点开始，每个节点包含数据区域和指针区域，数据区域可能有多个值，指针区域值往往在节点最后一个位置。若当前q指向头指针head，那么a[q]是整个节点的值，a[q][0]是数据区域的值，a[q][1]是下一节点的索引，通过语句q＝a[q][1]，实现指针向后移动。
上述程序段划线处可选的代码为(　　)
①a[head][3]！＝－1　②head＝p　③p＝a[head][3]　④head！＝－1，则(1)、(2)、(3)处的代码依次为(　　)
A.①②③ B.④②③ C.④③② D.①③②
A
思维点拨
明考向 本题考查链表的遍历
精点拨 从当前链表的头节点开始遍历，与下一个节点p的距离，因此head要不断地后移，head＝p，而p为新节点的后继节点。当头指针节点的后继为－1时，表示遍历完了
D
解析　本题考查多条链表的遍历。3条链表构建在数组a中，头指针存储在数组head中，需遍历头指针数组，从而来遍历3条链表。(1)处为当前节点赋值为头指针head[i]，变量s存储所有节点游览总时间。(2)(3)遍历链表，并统计各个节点游览时间和，由于当前节点已经计入总时间，因此先要跳转到下一点，将下一节点的时间加入总时间，注意遍历结束的条件是当遍历到尾节点时，终止遍历。
重难点2　链表节点的删除
在数组中删除某个节点，往往需把该节点后面的值往前移，时间复杂度为线性阶O(n)。链表节点的删除分为头节点的删除和其他节点的删除，头节点的删除只要移动头指针到下一节点，即head＝a[head][1]即可，其他节点的删除，只要修改该节点的前驱节点的指针区域值为该节点的后继节点索引即可，时间复杂度为常量阶O(1)。
答案　B
思维点拨
明考向 本题考查链表节点的删除
精点拨 当前节点q从第2个节点开始遍历，节点p是一段连续重复的开始位置，若a[p][0]与a[q][0]相等，则q向后遍历，否则让p的直接指向q，同时更新当前p的值为q。如链表数据1，2，2，2，3，3，3，有多个2时，让p指向第1个2位置，当q遍历到值为3时，让p直接指向3，删除中间的2。若最后出现多个重复的值时，语句a[p][1]＝－1的功能是删除后面重复的数据
B
解析　本题考查链表节点的删除。 p是当前节点，也是奇数节点，q是偶数节点。若q不为－1，采用语句a[p][1]＝a[q][1]删除q节点，同时更改p的值为q的后继。
重难点3　链表节点的插入
在数组中插入节点的时间复杂度为线性阶O(n)。链表节点的插入分为在头节点前的插入和其他节点前插入两种，头节点前插入新节点，该节点指向原头节点，并要修改head指针。在当前节点q前插入新节点，该新节点的后续是q，将修改q的前驱节点指针区域值。
答案　A
思维点拨
明考向 本题考查链表节点的插入
精点拨 t是新链表的尾指针，hb是链表db的当前节点指针。链表da头节点是值最小的，成为新链表的头节点，将链表db和原链表da第2个节点及后面所有节点采用尾插法合并到新链表da中。将链表db节点插入到新链表方法：当完成遍历da链表或者da链表尾指针后面节点值比db链表当前节点值的大时，①将链表db当前节点值添加到链表da中，成为最后一个元素，新节点指向原链表da尾节点t的后继q；②将尾节点t指向新添加的节点len(da)－1；③更新链表db的当前节点指针hb和链表da尾节点指针t。将链表da节点插入到新链表方法：由于链表的链接关系已经建立，只要更新尾节点t即可。新链表的尾节点无论是来自da还是db，均需要更新尾指针t，因此只要把这条语句放在判断结构的下方即可
变式 列表a存储了两个升序链表的节点，每个节点包含数据区域和指针区域，头指针分别为ha、hb，且a[ha][0]方框中应填入的正确代码为(　　)
B
解析　本题考查链表节点的插入。由于a[ha][0]小于a[hb][0]，因此p从ha所在链表第2个节点开始遍历，q为p的前驱，k遍历hb所在链表。当条件a[p][0]<＝ a[k][0]成立时，q和p继续遍历；若条件不成立，将节点k插入到节点p的前面。
重难点4　循环链表及链表的简单应用
循环链表是一种特殊的链式存储结构，其中最后一个节点的指针指向头节点，形成一个环。
例1 报数游戏。已知班上有n名学生(用编号1，2，3，……，n分别表示)，学生按照编号由小到大顺时针围成一个圆圈，从编号为1的学生开始顺时针报数，报到m的同学出列；下一名同学又从1开始报数，报数为m的同学继续出列；以此规律重复下去，直到剩下最后一位同学为止。
(1)当n＝6，m＝3时，最后留下的同学的编号是________。
(2)下列代码通过构造一个循环单向链表，模拟报数的过程，逐一删除报数为m的节点，直到剩下一个节点为止。请在划线处填入合适的代码。
思维点拨
明考向 本题考查循环链表的算法实现
精点拨 (1)3号和6号先出列，剩余编号为1245，4号和2号出列，接着5号出列，剩余1号。(2)①尾节点值为n，指向头节点0。②从 1至m－1依次报数，共循环了m－1次。③当前节点指针从尾节点开始，连续进行m－1次报数后，下一个节点out将要被删除，因此语句lst[p][1]＝lst[out][1]实现了删除out节点的操作
答案　(1)1　(2)①[n，0]　②range(1，m)或range(m－1)　③lst[p][1]＝lst[out][1]
A
解析　本题考查循环链表以及队列的算法实现。链表d构成一个循环链表，队列依次为BAC，若a[i]的值能分配给队首，则队首元素出队，否则更新剩余部分，再重新入队。变量t是链表的尾指针，指针q从头节点2开始遍历，若当前节点d[q][0]大于a[i]，a[i]不够分配，更新d[q][0]和尾指针t，同时i向后移动。若当前节点d[q][0]小于等于a[i]，删除当前节点q，同时n的值减少1个，表示完成一个元素的分配，同时更新a[i]。″B″更新为2后入队；″A″出队，″C″更新为2后入队；″B″出队，″C″出队。
例2 某编程兴趣小组设计了一个点歌模拟程序，功能如下：
运行程序后，从键盘输入“A”，则显示已点的歌曲列表(歌单)；输入“B”则可以自行输入歌曲并添加到歌单以完成点歌；输入“C”则可以将指定的歌曲置顶等待播放；输入“D” 则播放当前第一首歌曲，并将该歌曲从列表中删除；输入“E”则关闭程序并退出。程序运行界面如图所示。
请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A
God Is a Girl　十年　年少有为　七里香　淡季动物园
请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：B
请输入歌曲：兰亭序
请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：B
请输入歌曲：想自由
请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A
God Is a Girl　十年　年少有为　七里香　淡季动物园　兰亭序　想自由
请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：C
请输入歌曲：七里香
请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A
七里香　God Is a Girl　十年　年少有为　淡季动物园　兰亭序　想自由
请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：C
请输入歌曲；想自由
请输入指令A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A
想自由　七里香　God Is a Girl　十年　年少有为　淡季动物园　兰亭序
请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：D
请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：A
七里香　God Is a Girl　十年　年少有为　淡季动物园　兰亭序
请输入指令　A－显示歌单/B－点歌/C－置顶/D－唱歌/E－退出：E
思维点拨
明考向 本题考查链表的操作
精点拨 ①输入“B”则可以自行输入歌曲并添加到歌单，新节点插入在尾节点的后面，因此原尾节点应指向新插入的节点，同时更新尾节点。②输入“C”则可以将指定的歌曲置顶，data[cur][0]值为song表示找到节点cur，pre为cur节点的前驱，将cur移动到头节点前面，因此需要3步，第1步是将cur的前驱pre指向cur的后继，第2步是将cur指向原头节点，第3步是设置新的头节点为cur。③若cur是原尾节点tail，将cur修改为头节点后，新的尾节点为cur的前驱。④输入“D” 则播放当前第一首歌曲，并将该歌曲从列表中删除，条件head＝＝tail成立表示链表中只有一个节点，否则将头指针向后移动，删除头节点
答案　①data[tail][1]＝len(data)－1
②data[pre][1]＝data[cur][1]　③tail＝pre
④head＝data[head][1]
A.删除该链表中的最后一个节点
B.删除该链表中的第一个节点
C.在该链表第一个节点前插入一个新节点
D.在该链表最后一个节点后插入一个新节点
A
解析　本题考查链表的遍历、插入和删除操作。A选项删除该链表中的最后一个节点，需修改最后一个节点的前驱节点指针域，因此需遍历多个节点。B选项只需修改头指针。C选项修改当前节点的指针值指向原头节点，并修改头指针为当前节点。D选项让原尾节点指向当前节点，并修改尾节点为当前节点。
当堂检测
4
重难点1　链表的遍历
重难点2　链表节点的删除
重难点3　链表节点的插入
重难点4　循环链表及链表的简单应用
1.下列关于单向链表的说法正确的是(　　)
A.必定有头指针和尾指针
B.每个节点都有一个后继节点
C.删除一个节点，需要修改两个指针
D.查找任一节点的算法时间复杂度为O(n)
D
解析　本题考查链表相关知识。A选项单向链表必定有头指针，不一定要有尾指针。B选项尾结点没有后继节点。C选项单向链表删除一个节点，只需修改删除节点的前驱节点的后继指针即可。D选项链表的访问比较低效，每次遍历都需要从 head 头结点开始，故算法时间复杂度为 O(n)。
C
解析　本题考查链表的构建和遍历。L的后继节点为O，因此其指针区域值为1；O的后续为V，指针区域值为0; V的后续为E，指针区域值为2；E为尾节点，因此指针区域值为－1。
2.使用列表模拟单链表，其存储结构如图所示，遍历该链表，将访问到的节点的数据域的字符依次连接，得到字符串‘LOVE’，则指针域中的索引值依次为(　　)
A.0 1 2 3 B.3 1 0 2
C.2 0 －1 1 D.2 0 1 －1
D
解析　本题主要考查链表的操作。head＝3，即对应列表索引3，其值为“rabbit”，指向索引为0的节点，其值为“cat”，依此类推，依次输出各节点数据域的值，内容为″rabbit″，″cat″，″dog″，″pig″，故本题选D选项。
3.使用Python的二维列表来模拟单向链表，如下代码创建一个拥有4个节点的链表a
a＝[[″cat″，1]，[″dog″，2]，[″pig″，－1]，[″rabbit″，0]]
head＝3
依次输出各节点数据域的值，内容为(　　)
A.″cat″，″dog″，″pig″，″rabbit″ B.″pig″，″rabbit″，″cat″，″dog″
C.″pig″，″dog″，″cat″，″rabbit″ D.″rabbit″，″cat″，″dog″，″pig″
D
解析　本题考查链表遍历和最值查找。当前节点从头节点开始遍历，最小值的初值为头节点大小，因此需先移动到下一节点，再与最值进行比较，同时终止遍历的条件是遍历到尾节点马上结束。
4.实现在链表c中找出最小值m的Python程序如下：
head＝3；p＝head；m＝c[head][0]
while (1)________：
　　 (2)________
　　 if c[p][0]　 m＝c[p][0]
上述程序段中划线处可选代码为：①p！＝－1　②c[p][1]！＝－1　③p＝p＋1　④p＝c[p][1]
则程序段中(1)、(2)处代码依次为(　　)
A.①③ B.②③ C.①④ D.②④
答案　D
解析　fast和slow分别表示快慢指针，fast每次遍历2个节点，若遍历完成后，fast的值为－1，表示节点数量为偶数，当a[fast][1]值为－1，遍历到尾节点，节点数量为奇数，遍历完成。
A
解析　只需修改data2的指针区域值修改为data4的指针区域值。
1.某单向链表如下图所示，若要将数据 data3 和data4 同时从链表中移除，至少需要修改节点指针的数量是(　　)
A.1 B.2 C.3 D.4
D
解析　本题考查链表的基本操作。如果链表头节点值为1，直接删除头节点，否则遍历链表，语句a[pre][1]＝a[p][1]的作用让节点p的前驱指向他的后继，即删除p节点。程序的功能是删除元素值为1的节点。
C
解析　本题考查遍历链表及删除节点操作。①x是链表中一个节点位置，从链表中被删除的数据a[x][0]。②判断当前节点a[q]的值是否是要删除的数据data。③遍历链表，如果当前节点是要删除的数据，且该节点是头节点，需要更新头指针head的值，若不是头节点，需让前驱节点p指向当前节点q的后继节点。若当前节点的数据域不是 data，则将当前节点 p 更新为前驱节点 q，并继续检查下一个节点。
D
解析　本题考查链表的删除。while循环查找待删除节点的前驱节点位置。通过p1和p2遍历链表，前n次只遍历p2，后续同时遍历p1和p2，当p2遍历结束时，p1刚好指向倒数第n＋1个节点。所以(1)处选p2＝s[p2][1]，(2)处选p1＝s[p1][1]。确定p1位置后，执行删除操作。如果p1指向头节点head，要删除头节点，即更新head指向原头节点指针区域对应的节点；否则删除p1的后继节点，即p1的指针区域更新为p1后继节点的指针区域，(3)处应选s[p1][1]＝s[s[p1][1]][1]。
1.小张准备去多个城市旅游，他设计的行程若采用链表结构表示，如图a所示。若行程有变，需在“上海”与“成都”之间增加一站“杭州”，链表修改为如图b所示，有以下可选操作：
①“上海”所在节点的next值赋为“杭州”节点的next值
②“上海”所在节点的next值赋为5
③“杭州”所在节点的next值赋为“上海”所在节点的next值
④“杭州”所在节点的next值赋为－1
链表更新顺序正确的是(　　)
A.③① B.③② C.①④ D.②④
B
解析　本题考查的知识点是链表元素的插入。链表中插入新元素并不需要进行元素位置移动，只需要进行节点指针域的更改即可。在“上海”与“成都”之间增加一站“杭州”，需要先将新元素“杭州”的指针域设置为“成都”所在位置，再更改节点“上海”的指针域至节点“杭州”所在位置。
B
解析　本题考查链表的插入。①自定义函数lnkid的功能是查找n在链表中插入位置，head在不断地向后移动，因此n将和a[head][0]进行比较，当比a[head][0]小时，不断地向后查找位置。②语句p＝lnkid(n，head)将返回在节点p的后面插入新的数n，因此将修改a[p]节点指针区域值为当前插入点索引。
A
解析　本题考查链表元素的遍历和插入操作。程序的功能将链表b中的数据合并到链表a，形成一个新的降序序列存于链表a。分别遍历两个链表，若链表a当前元素值a[p][0]大于等于链表b当前元素值b[q][0]，则链表a向后遍历，否则把链表b当前元素值b[q][0]插入到链表a当前元素前面。由于是要把链表b中的数据合并到链表a，因此链表b遍历完成后，结束程序。
已知链表b的长度不超过链表a，则下列选项中，代码顺序正确的是(　　)
A.①④⑤ B.②③⑥ C.①④⑥ D.②③⑤
B
解析　本题考查链表节点的插入操作。程序将节点q插入到节点p的后面，因此q的指针域的值将发生变化，为了链表b正常遍历，应先保存q的后继。插入过程中，由于已经保存了q的后继，因此可以先修改q的指向，再修改p的指向，最后将p移动到原插入节点q的后继。
5.用链表模拟队列操作(队列长度大于1)，链表的每个节点包含数据区域和指针区域。指针head指向队列的第一个元素，指针tail指向队列的最后一个元素，如图所示。现执行n次“出队后立即入队”操作，实现该功能的Python程序段如下：
上述程序段中方框处可选代码有
①head＝que[head][1]　②que[tail][1]＝head
③que[head][1]＝－1　④que[p][1]＝－1
则方框内应填入的正确代码顺序为(　　)
A.①②③ B.①②④ C.②①③ D.②①④
D
解析　先采用尾插法将原头节点链接入链表，接着更新尾头节点，同时将新尾节点的指针区域值设置为1。
B
解析　本题考查循环链表的算法实现。每遍历一次，i增加1，实现计数。第1次删除节点2，第2次删除节点4，第3、4、5分别删除节点6、3、1，链表中只剩下节点5。
2.将A－K共13张黑桃扑克牌洗好后，把牌面朝下。第一张牌翻过来A，第2次将最上面第1张牌放到这叠牌的最下面，将第2张牌翻开，是黑桃2；第3次数将最上面第1、2张牌放到这叠牌的最下面，将第3张牌翻开，是黑桃3；依次类推将13张牌按从小到大的顺序翻出。求这叠牌洗好后，从上到下的原始顺序。
(1)程序运行结果如图所示，结合下面代码，当输入扑克牌数量num为6时，扑克牌从上到下的初始顺序最后输出结果为：________。
请输入扑克牌数量(1—13)：13
扑克牌从上到下的初始顺序为：
A，8，2，5，10，3，Q，J，9，4，7，6，K，
解析　本题考查循环链表的算法实现。(1)若输入6张牌，那么每次翻牌的位置依次是1, 3, 6, 2, 4, 5。将这些位置依次填入数字1－6，
位置 1 3 6 2 4 5
牌 A 4 2 5 6 3
可以得到原始的位置牌的点数。(2)①pre是当前节点cur的前驱，其初始值为尾节点位置。②变量i从0循环至，第i次循环时，翻了i张牌，因此需循环i次。③每次循环结束，获取当前翻开牌的位置，并依次存入数组result。变量k从0循环至num－1，result[k]表示第k＋1张牌的位置，result[k]－1表示原始位置数组initial的索引位置，其值为k＋1。
课后练习
5
重难点1　链表的遍历
重难点2　链表节点的删除
重难点3　链表节点的插入
重难点4　循环链表及链表的简单应用
D
解析　本题考查链表相关知识点。链表的访问必须从头节点开始。通过指针依次访问，不能随机访问任何一个元素。
B
解析　没有输出尾结点，输出前面4个节点的数据域，并以″→″结束，故答案为1→2→3→5→，选B。
3.王老师用链表模拟某次比赛中运动员的出场次序，运动员号码存储如下： a＝[[″e56″，4]，[″134″，－1]，[″215″，5]，[″098″，0]，[″144″，2]，[″024″，1]]。假设head＝3，小明同学的号码是“215”，则他的出场次序是(　　)
A.2 B.4 C.5 D.6
B
解析　本题考查链表的遍历。head值为3，[″098″，0]为头节点，接着是[″e56″，4] [″144″，2] ，[″215″，5], [″024″，1], [″134″，－1]。
4.有如下Python程序段：
a＝[[2，2]，[5，3]，[3，1]，[6，－1]，[1, 0]，[4，2]]
p＝5
while a[p][1]！＝－1：
　 print(a[p][0]，end＝″→″)
　 p＝a[p][1]
则运行程序后，控制台输出的结果是(　　)
A.4→3→5 B.4→3→2→5→
C.4→3→5→ D.4→3→2→5
C
解析　本题考查链表的遍历。条件a[p][1]！＝－1表示当前节点的指针区域值为－1，即当前节点为尾节点。当遍历到尾节点时，结束循环。
B
5.利用列表模拟非循环链表a(可能存在已被删除的节点)，下列程序运行完毕后，变量p表示尾节点的节点位置是(　　)
解析　本题考查链表的遍历。A选项当前节点为p，当遍历到节点为空时停止遍历，因此遍历结束后，p节点为空，其前驱t为尾节点。B选项当前节点为p，若当前节点的指针区域值为－1，结束遍历，那么当前节点p为尾节点。C选项当前节点从头节点开始遍历，a[a[p][1]]指当前节点的后继节点，若该节点的指针区域值为－1，表示该节点为尾节点，当前节点为尾节点的前驱。D选项链表a可能存在已被删除的节点，因此len(a)的值可能大于节点总数。
已知执行上述程序后，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指针从链表的第二个节点开始遍历，1a指针是t节点的前驱，t节点减去前驱节点la的值小于key时，c计数，c的初值为0，计数到3时结束，也就是整个过程计数3次就结束，执行程序后t的值为6，也就是遍历到最后一个节点时程序才结束。
解析　本题考查链表的遍历。p为当前节点，从头节点开始遍历链表，将遍历的新节点以头插法的形式重新构建链表。q为新链表的头节点，保存当前节点p的后续索引为tmp，先让新链表的头节点指向新链表的头节点，再将头指针指向p，p从原后续继续遍历原链表。
上述程序段中划线处应填写的代码是(　　)
A.①elif a[pre][1]！＝a[i][1]　②que[head])
B.①if a[pre][1]！＝a[i][1] ②que[head]
C.①elif a[pre][1]！＝a[i][1] ②a[que[head]]
D.①if a[pre][1]！＝a[i][1] ②a[que[head]]
D
解析　程序借助队列结构完成接力比赛男女队员的交替接力。对队列队首队员的性别和最近进入接力序列队员的性别进行比较，若不同，则将队列队首元素出队，否则继续对a数组进行遍历，若取到符合性别要求的元素则设定为下一趟性别比较的前驱，若性别与前一棒相同时则将该元素的索引置入等待队列。
上述程序段中方框处可选的语句为：
①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
解析　本题考查链表的插入。先分别获取奇数节点连接而成的链表和偶数节点连接而成的链表；再连接两个链表得到新链表。
1.由n个节点链接成的单链表如图所示，其中head为头指针。
C
解析　删除指针p所指向的节点需修改其前驱head的指针区域，将该指针区域修改为p的后继。
使用列表link模拟该链表结构，每个节点包含数据域和指针域，如图中最后一个节点可以表示为[98，－1]。现要删除指针p所指向的节点，可以实现该操作的语句有(　　)
①link[p][1]＝－1　②link[head][1]＝q　③link[head][1]＝link[p][1]　④head＝link[p][1]
A.①② B.①③ C.②③ D.②④
A
解析　本题考查链表的操作。当a[q]节点上的值与a[p]节点上的值相同时，q指针往后移一位。程序的功能是将与p指针所指示的节点值相同的a[q]节点删除。指针t的作用是维护了去重后链表最后一个节点的位置。输出链表的所有非重复节点。
A
解析　本题考查链表节点的删除。在自定义函数guess中，当前节点p从cur节点的后继开始，如果后面的元素与cur节点元素值相等，则删除节点p，因此是从当前节点链表中删除重复的元素。
D
解析　本题考查链表节点的删除。①循环遍历整个链表 。②q为当前元素指针，p是当前节点q的前驱，要删除q节点，只需要修改p的指针为q的后继。
C
解析　本题考查链表元素的删除操作。该程序的算法思想为：遍历链表，查找待删除节点，找到后根据该节点为第一个节点或中间节点执行不同的删除操作。
6.使用列表 d 模拟链表结构(节点数大于 1)，每个节点包含数据区域(数据均为整型，范围为 0～9)和指 针区域，h 为头指针，如图a所示。现要对该链表节点进行去重操作，只保留最后一次出现的节 点，结果如图b所示。实现该功能的程序段如下，方框中应填入的正确代码为(　　)
答案　B
解析　考查链表节点的删除。先遍历将链表元素按数值放入 lst 数组中，lst 数组实现统计每个元素出现的个数。若个数小于 2 个，则保留，若大于等于两个，则通过链表元素删除，保留最后一次出现的节点。删除链表节点分为两种情况：1.删除头节点，通过修改头指针为 h＝ d[h][1]实现；删除非头指针，q 为前驱节点，p 为当前节点，通过修改前驱节点指针域 d[q][1] ＝ d[p][1]，删除当前 p 指向的节点。
答案　A
解析　当前节点p从头节点开始遍历链表d，q为节点p的前驱，若d[p][0]不在[begin，end]范围内，更新当前指针p和前驱指针q。若d[p][0]在[begin，end]范围内，分是否是头节点两种情况。如果是头节点，更新head p的后继d[p][1]，否则采用语句d[q][1]＝d[p][1]删除当前节点p。无论删除的是否是头节点，均需要更新当前指针p。
B
解析　p的初值为第2个节点，因此程序的功能是若p节点前面存在一个节点的值与他相等，将他前面的节点删除，因此(1)q从头节点开始，遍历到节点p为止。(2)如果两个节点的数据区域值相等，删除节点q。
D
解析　①处采用头插法新增一个节点，头指针为len(link)－1。②当前节点q从头节点开始，不断地向后查找小于或等于data的第1个节点。③当前节点q从头节点开始遍历，直到q为－1时，停止遍历。
B
解析　原链表a存储一个升序的数列，值依次为1，2，2，2，5，6，9，输入一个数key，先在链表中查找大于key的第一个位置，并将该数插入到链表中，求插入的节点。
D
解析　本题考查链表的插入和进制转换。程序的功能是十进制数转成二进制数，并把结果取反。代码a.append([r，head]); head＝len(a)－1的功能利用头插法生成链表。
D
解析　先遍历链表，找到pb的位置，tmp指向头指针，pb>0表示不可能是头指针，因此要和他下一个节点的值a[a[tmp][1]][0]进行比较。插入节点指向tmp的后继。
D
解析　本题考查链表。先查找序列中最大数的位置maxp和该节点的前驱节点maxpre，pre为最后一个节点位置。再删除最大数节点，分两种情况，最大数节点为第一个节点或其他位置节点。如果是其他位置节点，需将该最大数节点的前驱节点指针区域指向该最大数节点的后继节点位置，即a[maxpre][1]＝a[maxp][1]。最后将最大数节点插入链尾，原最后一个节点指针区域需指向最大数节点，最大数节点为新的最后一个节点，其指针区域为－1，即p，所以②a[maxp][1]＝p。
B
解析　考查链表中数据查找和插入操作。p、q 是二个前后相邻的节点。根据 data>a[q][0]，可以推测出①为q！＝－1。循环结束后，应该在p节点之后插入节点，所以②处代码是：a[p][1]＝len(a)。
解析　本题考查链表的相关知识。先建立了一个升序链表，接下来从head开始，查找key插入的位置。若key>a[p][0]则继续向后找。本题key＝2，一开始就不满足循环条件，2应插到链表头部。首先向列表中追加key，并将指针指向head，同时调整head指针位置，故a[－1][0]＝2，指针a[－1][1]＝2。
C
8.某个正整数的每位数依次存储在链表d中各节点的数据区域中。例如，正整数572存储情况如图a所示，h为d的头指针。将该正整数翻倍后的计算结果(如572翻倍后的结果为1144)仍以这个链表存储，最高位存储于头节点中，如图b所示。实现该功能的程序段如下：
A
解析　当最高位数d[p][0]大于4(即5以上)时，其翻倍后的数将产生进位，因此需要新增加一个节点(默认在数据域插入0)，并将其作为新的头节点h。p为高位节点，cur为p的后继节点(节点cur是节点p的低位)。该利用链表实现的乘法算法的顺序和常规乘法是相反的：先计算高位p然后再计算低位cur。p节点的数据域是本位数d[p][0]的2倍然后%10后的值，但这还不是d[p][0]的终值，还要看p的低位cur有没有产生进位，若cur的数据域d[cur][0]大于4，则还会向p节点的数据域产生进位，由于最大的单位数9的2倍，其进位也只是1，因此每次在p节点原先的数据域d[p][0]基础上加1。
D
解析　考查链表的基本操作。遍历链表，将找到的女演员节点依次链接形成一个单独的链表，同时将女演员节点从原链表删除。操作完成后，原链表就是一个只有男演员的单向链表。指针q、r指向p的前驱和女演员链表的尾节点。将节点从原链表删除前，先要链接到女演员链表尾节点。
B
解析　pre是p的前驱节点，p向后遍历，当遍历到第m个节点，需用语句a[pre][1]＝a[p][1]将节点p删除。同时节点p需向后再遍历一个节点，否则该节点将不存在，同时将计数器恢复至1。条件p！＝a[p][1]成立，表示链表中只剩下一个节点。
C
解析　本题考查循环链表的遍历。h表示头节点，值为0，在链表中有一个节点指向0，因此判定该链表为循环链表。当前节点p从头节点开始遍历，若当前节点指针区域值为头节点，结束遍历，即遍历到尾节点终止循环，没有输出尾节点的值，循环结束后，再次输出尾节点的值。
D
解析　本题考查循环链表的操作，根据p＝q＝6可以得出链表为S－h－e－n－g－Z－h－o－u，k的范围为[3，5，7，9]，p和q相差k个节点，p为1时输出a[q][0]，即p指向g，q的可能有h、u、g。
4.小明设计了一个中华小曲库，其中导入了10000首歌曲，包含4种类型(编号从0－3)，每首歌曲都有自己的歌曲编号，歌曲编号的第一位是其类型，比如某歌曲编号为00041，代表这是类型0的第42首歌。已知本曲库有一个最近点播榜，分别记录每种类型最近点播的5首歌，当点播歌曲时记录规则如下：
①若榜单内不足5首歌，且被点播歌曲不在榜单上，则将其记录在该类型乐曲榜单首位，如图a所示，点播歌曲编号为20005，则在类型2的榜单榜首添加歌曲；若已在榜单上，则将其移至榜单首位，如图b所示点播歌曲00021。
②若榜单内已有5首歌，则将榜尾的乐曲删除，在榜首添加被点播歌曲，如图c所示点播歌曲00006。
现有榜单：
00092##00008##00015##00001##00021##
10004##10018##10298##10022##
20001##
30065##
请输入点播的歌曲：20005
现有榜单：
00092##00008##00015##00001##00021##
10004##10018##10298##10022##
20005##20001##
30065##
图a
现有榜单：
00092##00008##00015##00001##00021##
10004##10018##10298##10022##
20005##20001##
30065##
请输入点播的歌曲：00021
现有榜单：
00021##00092##00008##00015##00001##
10004##10018##10298##10022##
20005##20001##
30065##
图b
现有榜单：
00021##00092##00008##00015##00001##
10004##10018##10298##10022##
20005##20001##
30065##
请输入点播的歌曲：00006
现有榜单：
00006##00021##00092##00008##00015##
1000#10018##10298##10022##
20005##20001##
30065##
图c
答案　(1)00008　(2)6　(3)①flag＝True
②flag and leader[kind][1]<5　③data[p][1]＝head
解析　(1)00005不在榜单中，且已有5首，删除00015；00008和00005在榜单内，因此依次移到榜首，第2首歌的编号为0008。(2)num表示交换的次数，排序后的结果为[['ac'，1]，['ac'，1]，['abc'，2]，['bc'，2]，['c'，2]]，只要找出逆序对就可以求得num的值。[″bc″，2]与后面[″abc″，2]，[″ac″，1]，[″ac″，1]三对数据是逆序的。[″abc″，2]与[″c″，2]，[″ac″，1]是逆序对，[″c″，2]，[″ac″，1]是逆序对，因此需交换6次。(3)①自定义函数select中参数name表示点播歌曲名称，kind表示类型，每种类型的歌曲建立一个链表，leader数组存储每条链表的头指针。点播歌曲时，首先要查找点播的歌曲是否在榜间内。若在榜单首位，不用任何操作，否则当前p从头节点开始遍历当前类型的链表，
判断后继data[data[p][1]]节点是否是当前点播歌曲name，若在榜单，则将该节点移到队首，对flag赋值为False，因此①处应对flag赋初值为True。②满足条件将该歌曲插入到榜单队首，同时该类型的歌曲数量leader[kind][1]，那么其条件是当前歌曲不在榜单且该类型的歌曲数量小于5。③若歌曲不在榜单且该类型的歌曲已经超过5首，那么循环条件data[p][1]！＝－1不成立时，p节点是尾节点，q为尾节点前驱，语句data[q][1]＝－1功能是删除尾节点p，将尾节点的值修改为当前点播歌曲，并指向原队首head，更新leader[kind][0]后，该歌曲成为榜单的队首节点。
5.某学校举办社团节，在一条直路的同侧依次有n个社团展位，按展位到入口距离从1至n依次编号。从入口处走到第1个展位需要花费dis[0]单位时间，从第i个展位走到第i＋1个展位需要花费dis[i]单位时间。每个展位举行若干活动，每参加一个活动需要5单位时间。对于第i个展位，第一次参加活动获得a[i－1]个积分，第二次参加活动获得a[i－1]－b[i－1]个积分，第三次参加活动获得a[i－1]－2*b[i－1]个积分……以此类推。现在小明从入口处出发，他共有m单位时间自主选择参与社团的活动并回到入口处。编写程序实现规定时间内获得最多积分的活动方案及获得的积分数。
例：
展位 1 2 3
首次活动积分 10 15 20
每次下降的积分 4 6 4
与前一展位之间步行所花时间 1 3 4
若小明可用时间为28，部分方案如下：
方案1：参加前1个展位活动，有5次活动机会，可得积分为10＋6＋2＝18
方案2：参加前2个展位活动，有4次活动机会，可得积分为15＋10＋9＋6＝40
方案3：参加前3个展位活动，有2次活动机会，可得积分为20＋16＝36
则可获得的最多积分为40，运行界面如图所示。
展位数：3
可用时间：28
各展位首次参加活动可获得的积分：10 15 20
各展位每次下降的积分：4 6 4
相邻展位之间步行花费时间：1 3 4
能获得的最多积分是：40
各展位参加的活动次数分别为：[2，2，0]
(1)若小明可用时间为32，按上表数据可得最多积分为________。
答案　(1)51　(2)B　(3)① dis[i] ＋ dis[i － 1]
②t > 0 and head ！＝ －1　③data[p][0] – data[p][1]或者data[p][0]－b[p]
解析　(1)第3个展台距离入口所花时间为1＋3＋4＝8，往返需16，还可以有32－16＝16的时间用于活动，即可以完成3个活动，积分最大的20＋16＋15＝51。(2)insert函数功能是在首节点下标为head的链表中插入下标为r的节点，返回新的链首节点下标。当节点r数据区域值小于尾节点，条件data[r][0] < data[q][0]恒成立，q将越界。B选项链表的值依次为10，7，6，现将2插入到链表中。(3)①相邻展位之间步行花费时间存入dis列表，从入口先到展位1，再到展位2，再到展位3，因此第i个展位需累加前面各个dis列表的值。②可用时间m减去返回时间2 * dis[i]得到可以参加活动时间，因此t表示参加活动数量。各展位首次参加活动可获得的积分存入a列表，各展位每参加一次活动要下降的积分存入b列表，data数组中保存这两组数据。并形成一个降序排列的链表。临时方案是data数组中查找t个活动，因此需要2个条件。③每次在i个展位中找到一个最大的积分，因此将头节点的值累加到total，同时去除该链表的头节点。展位p每参加一次该活动，下一次参加该活动所得的积分减少b[p]，修改该节点的值，并重新生成一个新的降序链表。
6.某工程的A项目有n个任务组(编号为0～n－1)，供料商每小时只提供1份原料，各组按到达时刻(到达时刻各不相同)陆续加入领料队列，领取1份原料后到队列末尾重新等待，直至领完所需原料，离开队列。若多组同时入队，则到达时刻早的优先入队。编写程序模拟领料过程，先筛选出属于A项目的任务组，再计算每个任务组完成领料的时刻(时间单位：小时)，请回答下列问题：
任务组别 到达时刻 原料需求量
第0组 0 3
第1组 1 2
第2组 2 1
图a
时刻 领料队列 轮到领料的组别
0 0 0
1 0，1 0
2 1，0，2 1
3 0，2，1 0
4
5 1 1
注：领料队列中数字代表任务组编号
图b
答案　(1)B　(2)3　(3)①p＝i　②k＝task[p][3]
③task[p][3]＝task[k][3]
解析　本题考查循环队列的链式存储运算。(1)领料组0已经完成领料，不再入队，因此队列中为2，1，正在领料的是2。(2)变量j从0开始遍历，当条件task[j][0] ＝＝ st成立时，执行i ＋＝ 1，因此i表示st 的值是'A'的数量。(3)①ct表示当前时间，当条件task[i][1] <＝ ct成立，表示将索引i的task元素入队。从条件task[k][2]＝＝ 0来看，表示该组任务完成，因此t表示完成任务的数量。当i和t相等时，表示链表队列中数量为0，task[i]入队后，当前队列中只有一个元素，语句task[p][3] ＝ i表示节点p的后继是i，访元素的后继是本身，这就符合循环队列的特征，队尾指向队首。单向队列中若已知队尾可以得到队首位置，已知队首须遍历链表才能得到队尾，因此p为队尾，初值为i。②当i大于t时，表示入队的元素数量大于完成数量，需进行出队操作，k为队首指针，其值为队尾p的后继。③当队首完成领料后，需从链表中删除头节点。

展开更多......

收起↑