第07讲 数组与链表（复习讲义)（浙江专用）2027年高考信息技术一轮复习讲练测（浙江专用）
|
2份
|
54页
|
112人阅读
|
1人下载
精品
内容正文：
第07讲 数组与链表
内容导航
01
命题透视·考情前瞻
对标素养，研判高考命题趋势
02
思维建模·脉络梳理
搭建知识框架，构建系统思维
03
考点精讲·靶向突破
拆解核心考点，归纳解题范式
考点一 数组的创建、访问、插入、删除
知识解构 知识点1 一维数组操作
知识点2 二维数组操作
考向破译 考向1 数组访问与操作结果的推演
考向2 基于数组的数据移位与综合算法填空
考点二 单链表的访问
知识解构 知识点1 链表的结构
知识点2 链表的遍历、访问
考向破译 考向1 结合程序片段，考查链表遍历的轨迹与结果推演
考向2 结合链表特征，考查遍历终止条件与边界处理的代码实现
考点三 单链表的插入与删除操作
知识解构 知识点 链表指针更新逻辑
考向破译 考向1 结合流程图或代码，考查指针更新顺序
考向2 结合真实情境，考查头节点与中间节点的分类处理
考点四 双向链表的访问
知识解构 知识点 双向链表的访问
考向破译 考向 结合图形或代码，考查前驱与后继指针的同步更新
04
真题溯源·考向感知
溯源真题逻辑，感知高考考向
命题透视·考情前瞻
——对标素养，研判高考命题趋势
考点要求
考查形式
2026年
2025年
2024年
数组访问与操作结果的推演
选择题
非选择题
浙江卷1月卷T7，2分；浙江卷1月卷T10，2分；浙江卷1月卷T12，2 分；浙江卷6月卷T9，2 分；浙江卷6月卷T10，2 分；浙江卷6月卷 T11，2分
浙江卷1月卷 T11，2 分；浙江卷1月卷 T12，2 分；浙江卷 6月卷T10，2 分；浙江卷 6月卷 T12，2 分
浙江卷1月卷T9，2分；浙江卷1月卷T10，2分；浙江卷1月卷 T11，2 分；浙江卷6月卷T10，2 分；浙江卷6月卷 T11，2 分
基于数组的数据移位与综合算法填空
选择题
非选择题
浙江卷6月卷 T15，9 分
浙江卷1月卷T10，2 分；浙江卷1月卷T13，7 分；浙江卷6月卷T15，9 分
浙江卷1月卷 T15，9 分
链表的遍历与节点操作
选择题
非选择题
浙江卷1月卷T15，9 分；浙江卷6月卷 T12，2 分
浙江卷1月卷 T15，9 分；浙江卷6月卷 T11，2 分
浙江卷1月卷 T12，2 分；浙江卷6月卷 T12，2 分
考情分析：
1．浙江选考对数组、链表的考查，重在结合算法逻辑推演元素、指针状态变化。选择题常考数组移位、链表特征辨析、指针修改顺序；综合题（非选择题）常通过 Python 代码，考查数组元素移动、链表节点遍历、插入、删除，重点考察指针更新的先后顺序。
2．从命题思路上看：
（1）数组命题思路：聚焦数组元素移位、局部区间处理，侧重循环边界 命题不会单纯考数组概念，一般给出一段业务规则 + 残缺 Python 代码，要求读懂算法功能，补全循环体内赋值语句。
选择题特点：给出简短程序片段，手动模拟循环执行，判断运行结果或者补全方框代码；
易错点：循环边界、赋值左右方向（a[i]=a[i+1]与a[i+1]=a[i]区分）。
大题中数组常和 pandas 区分开：算法大题里的数组是 Python 普通列表，侧重底层下标操作；pandas 属于数据分析，不考察数组移位逻辑。
（2）链表命题思路：以列表模拟链表，核心抓指针域更新的先后次序 真题统一用 Python 列表模拟链表：d[p][0]存数据，d[p][1]存后继指针。
典型陷阱：修改d[t][1]、d[p][1]之前，先用临时变量保存后继q = d[p][1]；如果直接覆盖指针，会丢失后续节点地址。
（3）数组 vs 链表的命题对比，选项辨析经常同时出现 选择题偶尔出现辨析题：数组随机访问快，插入删除中间元素需要大量移位；链表随机访问慢，只适合顺序遍历，插入删除只需要修改指针，不需要移动大量数据。真题极少直接默写特点，都是嵌入代码情景间接考察。
复习目标：
1．理解数组（顺序存储）与链表（链式存储）的物理结构与逻辑结构差异；
2．熟练掌握链表节点的数据结构表示（如Python中的二维列表或字典）；
3．能够根据流程图或代码，准确推演指针的移动与节点之间的挂载关系（如断链、重连）。
思维建模·脉络梳理
——搭建知识框架，构建系统思维
考点精讲·靶向突破
——拆解核心考点，归纳解题范式
考点一 数组的创建、访问、插入、删除
知●识●解●构
知识点1 一维数组
1.一维数组的创建
直接定义
间接定义
a=[0,0,0,0,0]
a=[0 for i in range(5)]
或
a=[0]*5（常见写法）
测试结果
[0,0,0,0,0]
[0,0,0,0,0]
2.一维数组元素的访问：
数组名+下标（python中用列表模拟数组，故可以用列表名+索引的方式访问）
例：a[0]
3.一维数组的插入和删除
插入数组元素:数组中所有元素向后移
删除数组元素：数组中所有元素向前移
n=9
a=[0 for i in range(n)]
pos=int(input("请输入插入位置："))
data=int(input("请输入插入内容："))
for i in range(n-1,pos-2,-1):
a[i]=a[i-1]
a[pos-1]=data
print(a)
from random import randint
n=9
a=[0 for i in range(n)]
for i in range(n):
a[i]=randint(1,10)
print(a)
pos=int(input("请输入删除位置："))
for i in range(pos,n-1):
a[i]=a[i+1]
print(a)
运行结果：
运行结果：
得分速记
1.数组的特性
①数组元素的数据类型 。
②通过 和 对数组元素的值进行访问。
③存储空间 。
2.在 Pythor中可以使用列表来创建数组。例如，创建一个长度为8的随机整数数组，元素值在1到8之间，代码为: 。
基础巩固
1.下列关于Python一维数组（列表）的叙述，正确的是（）
A. 一维数组内存空间不一定连续
B. 数组元素必须为同一种数据类型
C. 通过下标访问数组元素，时间复杂度为O(1)
D. 下标最小值一定为1
2.在Python中，已有数组arr=[12,35,7,9,22]，下列说法错误的是（）
A. len(arr)得到数组元素个数为5
B. 第一个元素访问方式为arr[0]
C. arr[3]的值为9
D. arr[5]可以正常访问数组最后一个元素
3.一维数组区别于链表，下列属于一维数组特点的是（）
A. 插入删除中间元素效率高，不需要移动数据
B. 支持下标随机访问任意位置元素
C. 存储空间不需要预先连续分配
D. 数组长度只能动态增长，不能固定
4.执行a = [5,1,8,4]创建一维数组，下面说法不正确的是（）
A. 数组a由4个数组元素组成
B. 数组元素分别是a[0]、a[1]、a[2]、a[3]
C. a[2]=10语句可以修改数组第三个元素的值
D. a[4]=6可以直接在数组末尾新增元素
知识点2 二维数组
1.二维数组（矩阵）的创建：
直接定义
间接定义
a=[[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]]
a=[[0 for i in range(5)] for j in range(5)]
测试结果
调整格式
——5*5二维数组可看成5行5列的矩阵
*矩阵间接定义语句拆解
r=int(input('请输入矩阵行数：'))
c=int(input('请输入矩阵列数：'))
n=c
a=[[j*n+i+1 for i in range(c)] for j in range(r)]
print(a)
r=int(input('请输入矩阵行数：'))
c=int(input('请输入矩阵列数：'))
n=c
a=[]；a1=[]
for j in range(r):
for i in range(c):
a1.append(j*n+i+1)
a.append(a1)
a1=[]
print(a)
运行结果：
格式调整：
2.二维数组元素的访问：
数组名+下标（python中用列表模拟数组，故可以用列表名+索引的方式访问）
例：a[0]
3.二维数组元素的存储：
分为行优先与列优先。
（1）以行优先为例：首先将第一行（行下标为0）数组元素按照列下标顺序依次存储，再将下一行（行下标为1）数组元素按照列下标顺序依次存储，直至所有行存储完毕。
设二维数组a[6][9]，若按行优先的顺序存放数组的元素，则a[4][6]元素前面共有元素的个数为_______________个。
（2）以列优先为例：首先将第一列（列下标为0）数组元素按照行下标顺序依次存储，再将下一列（列下标为1）数组元素按照列下标顺序依次存储，直至所有列存储完毕。
设二维数组a[6][9]，若按列优先的顺序存放数组的元素，则a[4][6]元素前面共有元素的个数为________________个。
4.二维数组的插入和删除
插入数组元素:数组中所有元素向后移
删除数组元素
n=9
a=[0 for i in range(n)]
pos=int(input("请输入插入位置："))
data=int(input("请输入插入内容："))
for i in range(n-1,pos-2,-1):
a[i]=a[i-1]
a[pos-1]=data
print(a)
from random import randint
n=9
a=[0 for i in range(n)]
for i in range(n):
a[i]=randint(1,10)
print(a)
pos=int(input("请输入删除位置："))
for i in range(pos,n-1):
a[i]=a[i+1]
print(a)
运行结果：
运行结果：
函数
append()
在当前列表尾部追加元素,把添加的元素作为一个整体来操作
extend()
在当前列表尾部追加元素,把添加内容包含的元素逐个添加到列表中
insert()
在当前列表的指定位置插入元素,它会把添加的元素为一个整体插入到列表中
del
根据目标元素所在位置的索引进行删除
pop()
根据目标元素所在位置的索引进行删除,默认会删除列表中的最后一个元素
remove()
根据元素本身的值进行删除,该方法只会删除第一个和指定值相同的元素
易混易错
1.元素向后移动（腾出下标 x 位置，元素往下标大的方向挪）
· 必须逆序循环，从最靠后的元素开始往前处理。
· 赋值：a[i+1] = a[i] ，把 i 位置的值复制到后一个位置。
· 易错：写成a[i]=a[i+1]；或者写成正序循环，会把值覆盖，数据丢失。
2.元素向前移动（元素往下标更小方向挪，覆盖前面位置）
· 必须正序循环，从前往后处理。
· 赋值：a[i] = a[i+1]。
· 易错：逆序循环，数据被覆盖。
口诀：后移逆序，前移正序；谁是源写在等号右边，谁是目标写左边。
考●向●破●译
考向1 数组访问与操作结果的推演
例1 【26.04温州二模-11题】
st=i=0
while i<len(d) - 1:
if d[i]>=d[i+1]:
if i-st+1>2:
st=i+1
i+=1
d=[1,3,5,5,2,4,4,6]
若"d=[1,3,5,5,2,4,4,6]"，执行该程序段后，"st"的值为
A.3 B.5 C.6 D.7
【变式1】 有如下python程序段：
n=4
a=[[j*n+i+1 for i in range(n)]for j in range(n)]
for i in range(1,n,2):
for j in range(n//2):
a[i][j],a[i][n-j-1]=a[i][n-j-1],a[i][j]
则程序执行后，a[1][1]和a[2][1]的值分别为：
A.6和10 B.7和10 C.6和11 D.7和11
考向2 基于数组的数据移位与综合算法填空
例1 【26.04杭州二模-15题】
某物流仓库提供货物搬运功能，每件货物规格相同，仓库内共有 n 辆叉车 (编号为 1~n)。现收到若干个订单，每个订单包括装货时间 (从 0 开始编号) 和货物数量。根据叉车调度规则，要求在截止时间 t 前完成所有订单的货物搬运，计算需要的最少叉车数量。 已知每辆叉车一次处理一个订单的货物，且一次最多装载 10 件货物。叉车获取每件货物需花费 1 个单位时间，每次将叉车上的所有货物搬运至货车中需花费 3 个单位时间。叉车调度规则如下： 1. 选择最早空闲叉车：若空闲叉车有多辆，则选择编号最小的叉车。 2. 若一辆叉车无法在截止时间 t 前完成搬运，则在每辆叉车尽可能多装货物 (一次不超过 10 件) 的前提下，安排最少数量的叉车在截止时间 t 前完成；若不能，则输出 "订单无法完成！"。
def findi(cars):
mini=0
for j in range(len(cars)):
if cars[j]<cars[mini]:
mini=j
return mini
def check(data,m,v,t):
cars=[0]*m
for i in range(len(data)):
①___________
while count>0:
mini =findi(cars)
stime =max(cars[mini],data[i][0])
remain =t-3 -stime
if remain<=0:
return False
load =min(count,remain,v)
②___________
count -=load
return True
#取截止时间t、叉车数量n;读取订单数据表存入data列表，每个元素包含2个数据项，依次为装货时间和货物数量。代码略。
data =psort(data)
v=10
left,right =1,n
while left<=right:
m=(left +right)//2
if check(data,m,v,t):
right=m-1
else:
③___________
if left>n:
print("订单无法完成!")
else:
print("最少需要",left,"辆叉车")
(1) 若data=[[0,15],[4,12]]，t 为 15，则完成所有订单至少需要____辆叉车。 (2) 请在①、②、③划线处填入合适代码。
【变式1】数组的插入与删除：
①构建原始数组：
from random import randint
a=[0]*9
for i in range(__________):
a[i]=randint(1,10)
print(a)
运行结果：
②在第五个位置插入数组元素11：
from random import randint
a=[0]*9
for i in range(8):
a[i]=randint(1,10)
print(a)
for i in range(8,4,-1):
_____________________
____________________
print(a)
运行结果：
③在第五个位置删除原有数组元素：
from random import randint
a=[0]*9
for i in range(9):
a[i]=randint(1,10)
print(a)
for i in range(4,8):
______________________
print(a)
运行结果：
考点二 单链表的访问
知●识●解●构
知识点1 链表的结构
1.链表指的是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。
2.链表节点的结构：
（数据区域保存数据元素，指针区域相邻节点的存储地址）
3.头指针（head）作用：
①作为链表的入口，只有通过头指针才能进入链表
②为循环链表设立一个边界，便于数据处理时的边界判断和处理
4.根据每个节点中指针的数量分为：
（1）单向链表： （2） 双向链表：
（3）循环链表：
第一个节点和最后一个点使用指针链接，这样就形成了循环链表。
基础巩固
1.关于链表的叙述，正确的是（）
A. 链表的所有节点在内存中一定是连续存放
B. 链表节点由数据区域和指针区域两部分组成
C. 头指针存储链表第一个节点的数据
D. 单向链表节点包含 prev 和 next 两个指针
2.下列关于头指针 head 的说法，错误的是（）
A. 头指针是链表的入口，通过头指针访问链表
B. 循环链表中，头指针可以用于边界判断
C. 头指针保存第一个节点的存储地址
D. 头指针就是链表的第一个节点
3.链表和一维数组对比，下面说法正确的是（）
A. 链表支持下标随机访问任意节点，时间复杂度 O (1)
B. 链表插入中间节点，不需要移动大量数据，只修改指针
C. 链表物理内存必须连续
D. 链表访问元素速度一定快于数组
知识点2 链表的遍历、访问
1.链表中的某一节点，只能从头指针开始，通过指针链接依次访问，不能像数组那样通过下标直接引用。
链表节点的访问：
运行结果
list=[['王林',2],['李丰',-1],['黄刚',1],['吴坚',0]]
head=3
p=head
while p!=-1:
print(list[p][0])
p=list[p][1]
基础巩固
1.关于单向链表的遍历访问，下列说法正确的是（）
A. 可以通过下标直接随机访问链表中的任意节点
B. 遍历单向链表必须从头指针 head 出发，顺着 next 指针依次访问各个节点
C. 遍历单向链表时，可以从中间某个节点直接跳转到前面的节点
D. 单向链表遍历时间复杂度一定为 O (1)
2.遍历单向链表，终止遍历的条件一般是（）
A. 当前节点的数据为 0
B. 当前节点的 next 指针为 None（空）
C. 访问到链表第 5 个节点
D. 头指针 head 的值变为 None
3.对比一维数组和链表的访问、遍历，下列叙述正确的是（）
A. 数组随机访问 O (1)；链表遍历全部节点 O (n)
B. 数组和链表都可以通过下标随机访问
C. 数组遍历需要移动元素；链表遍历需要移动节点
D. 链表访问第 k 个元素速度快于数组
考●向●破●译
考向1 结合程序片段，考查链表遍历的轨迹与结果推演
例1【26.04金华十校-11题】
某班成员分成男生女生两个链表`linka`，`linkb`，男生人数比女生多，需要将两个链表合成一个链表，合并后的链表顺序为男 1 女 1 男 2 女 2… 男 n，实现该操作的程序代码如下：
```
p,q = heada,headb
while p!=-1 and q!=-1:
temp = linkb[q][1]
#此处填入3句代码完成节点插入
q=temp
```
加框处可选的代码：
```
(1) linka[p][1]=linkb[q][1]
(2) linkb[q][1]=linka[p][1]
(3) linka[p][1]=q
(4) linkb[q][1]=p
(5) p= linka[p][1]
(6) p= linkb[q][1]
```
下列选项中，代码顺序正确的（）
A.(2)(3)(6) B.(1)(4)(5) C.(2)(3)(5) D.(1)(3)(5)
【变式1】
有如下程序运行后输出 cnt 的值为（ ）？
d=[[8,3],[15,4],[3,-1],[10,2],[6,0]]
h=1
cnt = 0
p = h
while p != -1:
if d[p][0] > 7:
cnt += 1
p = d[p][1]
print(cnt)
A.1 B.2 C.3 D.4
【变式2】
d=[[4,-1],[9,0],[2,4],[6,1],[11,0]]
h=3
p = h
while p != -1:
d[p][0] = d[p][0] * 2
p = d[p][1]
p = h
res = ""
while p != -1:
res = res + str(d[p][0]) + " "
p = d[p][1]
print(res)
程序运行后输出结果是（）
A. 12 18 22 8 B. 6 9 11 4 C. 12 22 18 8 D. 8 18 22 12
考向2 结合链表特征，考查遍历终止条件与边界处理的代码实现
例1【26.04绍兴卷-15题】
现有 m 台 A 型机器 (编号 0‑m‑1)，n 台 B 型机器 (编号 m~m+n‑1)，需处理当天提交的 w 项作业。每项作业包含开始时间、结束时间、作业类型 (A、B 两类)。
规则：
1. A 类作业可分配至 A 型或 B 型机器，B 类作业只能分配至 B 型机器。
2. 每次分配优先选择最先结束先前作业的机器；多台同时满足，优先编号最小。
3. 选中机器未空闲，则作业延期到机器空闲后立刻执行；作业时长 (结束‑开始) 保持不变。
```
def allocate(data, m,n):
#data为排序完成的作业列表
seatcount = m+n
seats=[]
for i in range(seatcount):
seats.append([-1,i+1]) #seats[i][0]机器空闲时刻，seats[i][1]后继下标
seats[seatcount-1][1] = -1
head = 0
for d in data:
start, end, ptype = d[0], d[1], d[2]
duration = end - start
p = head
pre = idx = -1
while p!= -1:
if ①________ or (ptype == "B" and p >= m):
idx = p
break #找到目标机器，退出遍历
pre = p
p = seats[p][1]
#从链表摘下idx节点
if pre == -1:
head = seats[idx][1]
else:
seats[pre][1] = seats[idx][1]
#更新该机器的空闲时刻
if seats[idx][0] <= start:
seats[idx][0] = end
else:
②________
#把idx重新插入链表，维持链表按机器空闲时刻升序
pre, p = -1, head
while p!=-1:
v, k = seats[p][0], seats[idx][0]
if v < k or (v == k and p < idx):
pre = p
p = seats[p][1]
else:
break
③________
if pre == -1:
head = idx
else:
seats[pre][1]= idx
#计算全部作业完成最大时间，代码略
return maxt
```
(1)①处填入条件：________________
(2)②处填入代码：________________
(3)③处填入代码：________________
【变式1】
d=[[2,1],[4,2],[6,-1]]，头指针h=0
p = h
lst=[]
while p != -1:
p = d[p][1]
lst.append(d[p][0])
print(lst)
程序运行后输出列表 lst 是（）
A. [2,4,6] B. [4,6] C. [4,6, 报错] D. [2,4]
易混易错
1.错误 1：循环条件写成 while d[p][1]!=-1，会漏掉最后一个节点，尾节点不参与处理。
正确循环条件：p != -1，p 代表当前正在处理的节点。
2.错误 2：处理节点逻辑写在p=d[p][1]之后，第一个节点直接跳过。
顺序：先处理p，再执行p = d[p][1]移动指针。
3.易错：修改p的时候，忘记保留前驱节点t。很多题目重组链表，既要当前节点p，也要它的上一个节点t。
一定要用q保存后继，不要直接p=d[p][1]，因为操作中d[p][1]的值会被改写。
考点三 单链表的插入与删除操作
知●识●解●构
知识点1 链表指针更新逻辑
插入节点：要在节点 p 之后插入新节点 q。必须先连新节点的线，再改旧节点的线（先连后断）。
d[q][1] = d[p][1]
d[p][1] = q
删除节点：要删除节点 p 之后的节点 q。直接让 p 绕过 q。
q = d[p][1]
d[p][1] = d[q][1]
头节点操作：如果删除的是头节点，需要将 head 指向下一个节点（head = d[head][1]）。
链表节点的插入与删除：（修改指针）
例1：在有4个节点的单向链表中插入头节点
list=[['王林',2],['李丰',-1],['黄刚',1],['吴坚',0]]
head=3
list.append(['张三',head])
head=len(list)-1
p=head
while p!=-1:
print(list[p][0])
p=list[p][1]
例2：在单向链表的末尾插入一个新节点
list=[['王林',2],['李丰',-1],['黄刚',1],['吴坚',0]]
head=3
p=head
q=0
while p!=-1:
q=p
p=list[p][1]
list.append(['张三',-1])
list[q][1]=len(list)-1
p=head
while p!=-1:
print(list[p][0])
p=list[p][1]
例3：在单向链表王林和黄刚所处节点的中间位置插入一个新节点
list = [['黄刚',1], ['王林',3], ['李丰',0], ['吴坚',-1]]
head=2
p=head
t=0
w=int(input('请输入要插入的节点位置：'))
while p!=-1 and t!=w-1:
q=p
p=list[p][1]
t+=1
list.append(['张三',p])
list[q][1]=len(list)-1
p = head
while p != -1:
print(list[p][0])
p = list[p][1]
在有4个节点的单向链表中删除头节点
list=[['王林',2],['李丰',-1],['黄刚',1],['吴坚',0]]
head=3
head=list[head][1]
p=head
while p!=-1:
print(list[p][0])
p=list[p][1]
在有4个节点的单向链表中删除尾节点
list=[['王林',2],['李丰',-1],['黄刚',1],['吴坚',0]]
head=3
p=head
t=0
q=-1
while p!=-1:
x=q
q=p
p=list[p][1]
list[x][1]=list[q][1]
p = head
while p != -1:
print(list[p][0])
p = list[p][1]
例3：在单向链表的输入位置删除节点
list=[['王林',2],['李丰',-1],['黄刚',1],['吴坚',0]]
head=3
p=head
t=0
w=int(input('请输入要删除的节点：'))
while p!=-1 and t!=w-1:
q=p
p=list[p][1]
t+=1
list[q][1]=list[p][1]
p = head
while p != -1:
print(list[p][0])
p = list[p][1]
易混易错
链表操作（插入、头插、删除、重组）必须先保存后继节点，再修改指针。一旦直接修改指针，后继节点地址直接丢失，链表断裂。
口诀：先存后继，再改链接；新节点指针赋值要在旧指针被覆盖之前。
考●向●破●译
考向1 结合流程图或代码，考查指针更新顺序
例1 (2024·浙江1月选考，第12题) 使用列表 d 模拟链表结构（节点数大于0），每个节点包含数据区域和指针区域，h 为头指针。链表中各节点已按数据区域中数值的绝对值由小到大排列。现要修改该链表各节点的链接关系，使链表各节点按数据区域中的数值由小到大排列。实现该功能的程序段如下，方框中应填入的正确代码为（ ）
t = h
p = d[h][1]
while p != -1:
q = d[p][1]
if d[p][0] > 0:
if d[t][0] > 0:
# (1)
else:
# (2)
else:
# (3)
p = q
A. d[q][1]=p d[t][1]=q d[t][1]=q
B. d[p][1]=t d[t][1]=q d[q][1]=p
C. d[t][1]=q d[t][1]=p d[p][1]=h
D. d[q][1]=p d[p][1]=h d[t][1]=q
【变式1】(2024·浙江6月选考，第12题) 使用列表 d 模拟链表结构（节点数n>0），每个节点包含数据区域和指针区域，h 为头指针。现要按链表顺序将这n个节点中的数据依次存放到 d[0][0]、d[1][0]…d[n-1][0] 中，最终保持节点链接关系不变。实现上述功能的Python程序段如下，方框中应填入的正确代码为（ ）
p, i = h, 0
while p != -1:
tp = d[p][1]
if p == i:
i += 1
elif p > i:
d[i][0], d[p][0] = d[p][0], d[i][0]
i += 1
# (1)
p = tp
# 调整头指针h及指针区域，保持节点链接关系不变，代码略
A. d[i][1]=d[p][1] d[p][1]=i
B. d[p][1]=d[i][1] d[i][1]=p
C. d[i][1]=p d[p][1]=d[i][1]
D. d[p][1]=i d[i][1]=d[p][1]
考点四 双向链表的访问
知●识●解●构
知识点1 双向链表基本概念
1. 定义
双向链表的每个结点有两个指针域：一个指向后继结点 (next)，一个指向前驱结点 (prev)；还有数据域 (data)。既可以向后遍历，也可以向前遍历。
单向链表：只能从表头向后遍历，找前驱结点必须从头遍历。
双向链表：已知某结点，可以直接访问前驱、后继。
2.结点结构
【prev | data | next】
prev：指向前一个结点
data：存储数据
next：指向后一个结点
3. 双向链表优缺点
优点：
① 可正向、反向双向遍历
② 已知某结点，删除该结点不需要从头找前驱，效率高
缺点：
① 每个结点多一个指针域，占用更多存储空间
② 插入、删除结点时，要修改 4 处指针（单向链表只改 2 处），指针顺序写错极易出错。
知识点2 双向链表节点访问
双向链表节点的访问（顺向访问）
list=[['b',3,2],['d',2,-1],['c',0,1],['a',-1,0]]
head=3
p=head
while list[p][2]!=-1:
print(list[p][0],end=”→”)
p=list[p][2]
print(list[p][0])
运行结果：
考●向●破●译
考向1 结合流程图或代码，考查指针更新顺序
例1（改编·Z20联盟）关于双向链表的结构与遍历，下列程序逻辑说法正确的是（）
A. 双向链表可以通过下标随机访问任意节点
B. 正向遍历双向链表的核心语句为：p = p.next
C. 反向遍历需要从 head 节点开始，不断执行 p = p.prev
D. 双向链表遍历的时间复杂度为 O(1)
【变式1】改编·金华十校）遍历双向链表完整所有节点，下列代码逻辑正确的正向遍历是（）
A.p = head B.p = tail
while p != None: while p != None:
p = p.next p = p.prev
C.p = head D.p = tail
while p != None: while p != None:
p = p.prev p = p.next
真题溯源·考向感知
——溯源真题逻辑，感知高考考向
1．【2024·浙江1月选考，第9题】
数组元素 a [0] 至 a [n‑1] 依次存放着 n 个数据，现需要将元素 a [n‑1] 插入在下标为 x (0 ≤x<n‑1) 的位置。
例：n 为 5，数组 a 为 [0,3,4,6,7]，x 为 2，插入操作后 a 为 [0,3,7,4,6]。
实现该功能的程序段如下，方框中应填入的正确代码为
temp = a [n‑1]
for i in range (n‑2, x‑1, ‑1):
a[x] = temp
A. a[i+1]=a[i] B. a[i‑1]=a[i] C. a[i]=a[i+1] D. a[i]=a[i‑1]
2. 【2024·浙江1月选考，第12题】 使用列表 d 模拟链表结构（节点数大于0），每个节点包含数据区域和指针区域，h 为头指针。链表中各节点已按数据区域中数值的绝对值由小到大排列，如图a所示。现要修改该链表各节点的链接关系，使链表各节点按数据区域中的数值由小到大排列，结果如图b所示。实现该功能的程序段如下，方框中应填入的正确代码为（ ）
t = h
p = d[h][1]
while p != -1:
q = d[p][1]
if d[p][0] > 0:
if d[t][0] > 0:
# (1)
else:
# (2)
else:
# (3)
p = q
A. d[q][1]=p d[t][1]=q d[t][1]=q
B. d[p][1]=t d[t][1]=q d[q][1]=p
C. d[t][1]=q d[t][1]=p d[p][1]=h
D. d[q][1]=p d[p][1]=h d[t][1]=q
3.(2024·浙江6月选考，第12题)使用列表 d 模拟链表结构（节点数 n>0），每个节点 d [p][0] 存数据，d [p][1] 存后继指针，h 为头指针。需要顺着链表遍历顺序，把链表节点的数据依次存放到数组下标 0,1,2…n1 位置，链表节点链接关系保持不变。 部分代码：
p,i = h,0
while p != -1:
tp = d [p][1]
if p == i:
i +=1
elif p > i:
d [i][0], d [p][0] = d [p][0], d [i][0]
i +=1
p = tp
#调整头指针h及指针区域，保持节点链接关系不变，代码略
A. d[i][1]= d[p][1] d[p][1]=i B.d[p][1]=d[i][1] d[i][1]=p
C.d[i][1]=p d[p][1]= d[i][1] D.d[p][l]=i d[i][1]= d[p][1]
4.(2025·浙江6月选考，第11题) 有如下 Python 程序段：
tag=[0]*len (data)
p=i=0
while i<len (data):
if tag [p]==0 and data [p][1]!=-1:
tag [i]+=1
p=data[p][1]
else:
tag [i]+= tag [p]
i+=1
p=i
若 data = [[11,3],[23,-1],[15,0],[26,1],[63,2]]，运行该程序段后，tag [4] 的值为( )
A.1 B.2 C.3 D.4
5.(2026·浙江1月选考，第15题) 某中转站负责转运物品，每个物品规格相同且有唯一的正整数编号。物品送达中转站的时间先后与编号大小无关，每次运走的物品编号均需连续。将中转站中的现有物品编号划分为若干序列，连续的编号按升序置于同一序列，不连续的编号置于不同序列。当需要运走x个物品时，检查当前时间现有序列中是否存在长度≥x的序列，若存在，则选择长度最短的序列（若最短序列有多个，则选择起始编号最小的序列），运走从其起始编号开始的x个连续编号的物品。
(1) 若物品按如图所示的时间送达中转站，第一次需要运走的物品个数为3，时间为09:15，则该次运走物品的起始编号为______。
(2) 定义如下函数 check(reqs, m)，用于判断列表 reqs 中是否存在下列情况：任意连续60分钟内，需要运走的物品数量总和超过 m。列表 reqs 中的每个元素包含两个数据项，依次为需要运走的时间（已转换为分钟数）和物品数量，已按时间升序排列。
def check(reqs, m):
i = j = 0
s = 0
while j < len(reqs):
s += reqs[j][1]
if s > m:
return True
j += 1
while s > m and i < j:
s -= reqs[i][1]
i += 1
return False
① 若 reqs 为 [[6,1],[19,13],[35,3],[70,2],[75,7]]，m 为20，则返回值为______。
② 若 reqs 的长度为100，函数返回值为False，则while语句中循环体的执行次数最多是______次。
2 / 3
学科网（北京）股份有限公司
学科网（北京）股份有限公司
学科网（北京）股份有限公司
$
第07讲 数组与链表
内容导航
01
命题透视·考情前瞻
对标素养，研判高考命题趋势
02
思维建模·脉络梳理
搭建知识框架，构建系统思维
03
考点精讲·靶向突破
拆解核心考点，归纳解题范式
考点一 数组的创建、访问、插入、删除
知识解构 知识点1 一维数组操作
知识点2 二维数组操作
考向破译 考向1 数组访问与操作结果的推演
考向2 基于数组的数据移位与综合算法填空
考点二 单链表的访问
知识解构 知识点1 链表的结构
知识点2 链表的遍历、访问
考向破译 考向1 结合程序片段，考查链表遍历的轨迹与结果推演
考向2 结合链表特征，考查遍历终止条件与边界处理的代码实现
考点三 单链表的插入与删除操作
知识解构 知识点 链表指针更新逻辑
考向破译 考向1 结合流程图或代码，考查指针更新顺序的逻辑推断
考向2 结合真实情境，考查头节点与中间节点的分类处理
考点四 双向链表的访问
知识解构 知识点 双向链表的访问
考向破译 考向 结合图形或代码，考查前驱与后继指针的同步更新
04
真题溯源·考向感知
溯源真题逻辑，感知高考考向
命题透视·考情前瞻
——对标素养，研判高考命题趋势
考点要求
考查形式
2026年
2025年
2024年
数组访问与操作结果的推演
选择题
非选择题
浙江卷1月卷T7，2分；浙江卷1月卷T10，2分；浙江卷1月卷T12，2 分；浙江卷6月卷T9，2 分；浙江卷6月卷T10，2 分；浙江卷6月卷 T11，2分
浙江卷1月卷 T11，2 分；浙江卷1月卷 T12，2 分；浙江卷 6月卷T10，2 分；浙江卷 6月卷 T12，2 分
浙江卷1月卷T9，2分；浙江卷1月卷T10，2分；浙江卷1月卷 T11，2 分；浙江卷6月卷T10，2 分；浙江卷6月卷 T11，2 分
基于数组的数据移位与综合算法填空
选择题
非选择题
浙江卷6月卷 T15，9 分
浙江卷1月卷T10，2 分；浙江卷1月卷T13，7 分；浙江卷6月卷T15，9 分
浙江卷1月卷 T15，9 分
链表的遍历与节点操作
选择题
非选择题
浙江卷1月卷T15，9 分；浙江卷6月卷 T12，2 分
浙江卷1月卷 T15，9 分；浙江卷6月卷 T11，2 分
浙江卷1月卷 T12，2 分；浙江卷6月卷 T12，2 分
考情分析：
1．浙江选考对数组、链表的考查，重在结合算法逻辑推演元素、指针状态变化。选择题常考数组移位、链表特征辨析、指针修改顺序；综合题（非选择题）常通过 Python 代码，考查数组元素移动、链表节点遍历、插入、删除，重点考察指针更新的先后顺序。
2．从命题思路上看：
（1）数组命题思路：聚焦数组元素移位、局部区间处理，侧重循环边界 命题不会单纯考数组概念，一般给出一段业务规则 + 残缺 Python 代码，要求读懂算法功能，补全循环体内赋值语句。
选择题特点：给出简短程序片段，手动模拟循环执行，判断运行结果或者补全方框代码；
易错点：循环边界、赋值左右方向（a[i]=a[i+1]与a[i+1]=a[i]区分）。
大题中数组常和 pandas 区分开：算法大题里的数组是 Python 普通列表，侧重底层下标操作；pandas 属于数据分析，不考察数组移位逻辑。
（2）链表命题思路：以列表模拟链表，核心抓指针域更新的先后次序 真题统一用 Python 列表模拟链表：d[p][0]存数据，d[p][1]存后继指针。
典型陷阱：修改d[t][1]、d[p][1]之前，先用临时变量保存后继q = d[p][1]；如果直接覆盖指针，会丢失后续节点地址。
（3）数组 vs 链表的命题对比，选项辨析经常同时出现 选择题偶尔出现辨析题：数组随机访问快，插入删除中间元素需要大量移位；链表随机访问慢，只适合顺序遍历，插入删除只需要修改指针，不需要移动大量数据。真题极少直接默写特点，都是嵌入代码情景间接考察。
复习目标：
1．理解数组（顺序存储）与链表（链式存储）的物理结构与逻辑结构差异；
2．熟练掌握链表节点的数据结构表示（如Python中的二维列表或字典）；
3．能够根据流程图或代码，准确推演指针的移动与节点之间的挂载关系（如断链、重连）。
思维建模·脉络梳理
——搭建知识框架，构建系统思维
考点精讲·靶向突破
——拆解核心考点，归纳解题范式
考点一 数组的创建、访问、插入、删除
知●识●解●构
知识点1 一维数组
1.一维数组的创建
直接定义
间接定义
a=[0,0,0,0,0]
a=[0 for i in range(5)]
或
a=[0]*5（常见写法）
测试结果
[0,0,0,0,0]
[0,0,0,0,0]
2.一维数组元素的访问：
数组名+下标（python中用列表模拟数组，故可以用列表名+索引的方式访问）
例：a[0]
3.一维数组的插入和删除
插入数组元素:数组中所有元素向后移
删除数组元素：数组中所有元素向前移
n=9
a=[0 for i in range(n)]
pos=int(input("请输入插入位置："))
data=int(input("请输入插入内容："))
for i in range(n-1,pos-2,-1):
a[i]=a[i-1]
a[pos-1]=data
print(a)
from random import randint
n=9
a=[0 for i in range(n)]
for i in range(n):
a[i]=randint(1,10)
print(a)
pos=int(input("请输入删除位置："))
for i in range(pos,n-1):
a[i]=a[i+1]
print(a)
运行结果：
运行结果：
得分速记
1.数组的特性
①数组元素的数据类型相同。
②通过数组名和下标对数组元素的值进行访问。
③存储空间固定不变。
2.在 Python中可以使用列表来创建数组。例如，创建一个长度为8的随机整数数组，元素值在1到8之间，代码为:a=[random.randint(1,8) for i in range(8)]。
基础巩固
1.下列关于Python一维数组（列表）的叙述，正确的是（）
A. 一维数组内存空间不一定连续
B. 数组元素必须为同一种数据类型
C. 通过下标访问数组元素，时间复杂度为O(1)
D. 下标最小值一定为1
【答案】C
【解析】A错误，标准一维数组物理内存连续；B错误，Python列表（数组）可存储不同类型数据；C正确，数组支持随机下标访问，单次访问效率为O(1)；D错误，Python数组下标从0开始。
2.在Python中，已有数组arr=[12,35,7,9,22]，下列说法错误的是（）
A. len(arr)得到数组元素个数为5
B. 第一个元素访问方式为arr[0]
C. arr[3]的值为9
D. arr[5]可以正常访问数组最后一个元素
【答案】D
【解析】该数组共5个元素，下标范围为0-4，arr[5]属于下标越界，无法正常访问，D错误；ABC表述均正确。
3.一维数组区别于链表，下列属于一维数组特点的是（）
A. 插入删除中间元素效率高，不需要移动数据
B. 支持下标随机访问任意位置元素
C. 存储空间不需要预先连续分配
D. 数组长度只能动态增长，不能固定
【答案】B
【解析】一维数组核心优势是支持下标随机访问；插入、删除中间元素需要移动大量数据，效率低，A错误；数组需要连续内存空间，C错误；数组可固定长度也可动态变化，D错误。
4.执行a = [5,1,8,4]创建一维数组，下面说法不正确的是（）
A. 数组a由4个数组元素组成
B. 数组元素分别是a[0]、a[1]、a[2]、a[3]
C. a[2]=10语句可以修改数组第三个元素的值
D. a[4]=6可以直接在数组末尾新增元素
【答案】D
【解析】Python中不能直接对不存在的下标赋值新增数组元素，会触发下标越界错误，新增元素需使用append()方法；ABC表述均正确。
知识点2 二维数组
1.二维数组（矩阵）的创建：
直接定义
间接定义
a=[[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]]
a=[[0 for i in range(5)] for j in range(5)]
测试结果
调整格式
——5*5二维数组可看成5行5列的矩阵
*矩阵间接定义语句拆解
r=int(input('请输入矩阵行数：'))
c=int(input('请输入矩阵列数：'))
n=c
a=[[j*n+i+1 for i in range(c)] for j in range(r)]
print(a)
r=int(input('请输入矩阵行数：'))
c=int(input('请输入矩阵列数：'))
n=c
a=[]；a1=[]
for j in range(r):
for i in range(c):
a1.append(j*n+i+1)
a.append(a1)
a1=[]
print(a)
运行结果：
格式调整：
2.二维数组元素的访问：
数组名+下标（python中用列表模拟数组，故可以用列表名+索引的方式访问）
例：a[0]
3.二维数组元素的存储：
分为行优先与列优先。
（1）以行优先为例：首先将第一行（行下标为0）数组元素按照列下标顺序依次存储，再将下一行（行下标为1）数组元素按照列下标顺序依次存储，直至所有行存储完毕。
设二维数组a[6][9]，若按行优先的顺序存放数组的元素，则a[4][6]元素前面共有元素的个数为_______________个。
a[6][9]表示二维矩阵为6行9列，a[4][6]表示当前为第5行第7列，前4行共有4*9=36个元素，当前列之前共有6个元素，因此共有36+6=42个元素。
（2）以列优先为例：首先将第一列（列下标为0）数组元素按照行下标顺序依次存储，再将下一列（列下标为1）数组元素按照列下标顺序依次存储，直至所有列存储完毕。
设二维数组a[6][9]，若按列优先的顺序存放数组的元素，则a[4][6]元素前面共有元素的个数为________________个。
a[6][9]表示二维矩阵为6行9列，a[4][6]表示当前为第5行第7列，前6列共有6*6=36个元素，当前行之前共有4个元素，因此共有36+4=40个元素。
4.二维数组的插入和删除
插入数组元素:数组中所有元素向后移
删除数组元素
n=9
a=[0 for i in range(n)]
pos=int(input("请输入插入位置："))
data=int(input("请输入插入内容："))
for i in range(n-1,pos-2,-1):
a[i]=a[i-1]
a[pos-1]=data
print(a)
from random import randint
n=9
a=[0 for i in range(n)]
for i in range(n):
a[i]=randint(1,10)
print(a)
pos=int(input("请输入删除位置："))
for i in range(pos,n-1):
a[i]=a[i+1]
print(a)
运行结果：
运行结果：
函数
append()
在当前列表尾部追加元素,把添加的元素作为一个整体来操作
extend()
在当前列表尾部追加元素,把添加内容包含的元素逐个添加到列表中
insert()
在当前列表的指定位置插入元素,它会把添加的元素为一个整体插入到列表中
del
根据目标元素所在位置的索引进行删除
pop()
根据目标元素所在位置的索引进行删除,默认会删除列表中的最后一个元素
remove()
根据元素本身的值进行删除,该方法只会删除第一个和指定值相同的元素
易混易错
1.元素向后移动（腾出下标 x 位置，元素往下标大的方向挪）
· 必须逆序循环，从最靠后的元素开始往前处理。
· 赋值：a[i+1] = a[i] ，把 i 位置的值复制到后一个位置。
· 易错：写成a[i]=a[i+1]；或者写成正序循环，会把值覆盖，数据丢失。
2.元素向前移动（元素往下标更小方向挪，覆盖前面位置）
· 必须正序循环，从前往后处理。
· 赋值：a[i] = a[i+1]。
· 易错：逆序循环，数据被覆盖。
口诀：后移逆序，前移正序；谁是源写在等号右边，谁是目标写左边。
考●向●破●译
考向1 数组访问与操作结果的推演
例1 【26.04温州二模-11题】
st=i=0
while i<len(d) - 1:
if d[i]>=d[i+1]:
if i-st+1>2:
st=i+1
i+=1
d=[1,3,5,5,2,4,4,6]
若"d=[1,3,5,5,2,4,4,6]"，执行该程序段后，"st"的值为
A.3 B.5 C.6 D.7
【参考答案与解析】
答案：C
解析：
初始 st=0，i=0，d = [1,3,5,5,2,4,4,6]，len (d)=8，i 从 0 循环到 6。
i=0：d [0]=1，d [1]=3，1>=3 不成立，i 自增为 1，st 保持 0。
i=1：d [1]=3，d [2]=5，3>=5 不成立，i 自增为 2，st 保持 0。
i=2：d [2]=5，d [3]=5，5>=5 成立；i‑st+1 = 2‑0+1 =3>2，条件成立，st 更新为 3；i 自增为 3。
i=3：d [3]=5，d [4]=2，5>=2 成立；i‑st+1 =3‑3+1=1>2 不成立，st 不变；i 自增为 4。
i=4：d [4]=2，d [5]=4，2>=4 不成立，i 自增为 5，st 保持 3。
i=5：d [5]=4，d [6]=4，4>=4 成立；i‑st+1 =5‑3+1=3>2，条件成立，st 更新为 6；i 自增为 6。
i=6：d [6]=4，d [7]=6，4>=6 不成立，i 自增为 7，循环结束。
最终 st = 6。
【变式1】 有如下python程序段：
n=4
a=[[j*n+i+1 for i in range(n)]for j in range(n)]
for i in range(1,n,2):
for j in range(n//2):
a[i][j],a[i][n-j-1]=a[i][n-j-1],a[i][j]
则程序执行后，a[1][1]和a[2][1]的值分别为：
A.6和10 B.7和10 C.6和11 D.7和11
【参考答案与解析】
答案：B
解析：
1.生成二维数组j=0行：[1, 2, 3, 4]
j=1行：[5, 6, 7, 8]
j=2行：[9,10,11,12]
j=3行：[13,14,15,16]
1． for i in range(1,n,2) → i=1（只处理第1行，i=3）
i=1（第二行 [5,6,7,8]），n//2=2，j=0、j=1
j=0：交换a[1][0]与a[1][3] → [8,6,7,5]
j=1：交换a[1][1]与a[1][2] → [8,7,6,5]
处理后：
• a[1] = [8,7,6,5]，所以a[1][1]=7
• i=2没有参与循环，a[2]不变，a[2][1]=10
a[1][1]=7，a[2][1]=10
答案：B
考向2 基于数组的数据移位与综合算法填空
例1 【26.04杭州二模-15题】
某物流仓库提供货物搬运功能，每件货物规格相同，仓库内共有 n 辆叉车 (编号为 1~n)。现收到若干个订单，每个订单包括装货时间 (从 0 开始编号) 和货物数量。根据叉车调度规则，要求在截止时间 t 前完成所有订单的货物搬运，计算需要的最少叉车数量。 已知每辆叉车一次处理一个订单的货物，且一次最多装载 10 件货物。叉车获取每件货物需花费 1 个单位时间，每次将叉车上的所有货物搬运至货车中需花费 3 个单位时间。叉车调度规则如下： 1. 选择最早空闲叉车：若空闲叉车有多辆，则选择编号最小的叉车。 2. 若一辆叉车无法在截止时间 t 前完成搬运，则在每辆叉车尽可能多装货物 (一次不超过 10 件) 的前提下，安排最少数量的叉车在截止时间 t 前完成；若不能，则输出 "订单无法完成！"。
def findi(cars):
mini=0
for j in range(len(cars)):
if cars[j]<cars[mini]:
mini=j
return mini
def check(data,m,v,t):
cars=[0]*m
for i in range(len(data)):
①___________
while count>0:
mini =findi(cars)
stime =max(cars[mini],data[i][0])
remain =t-3 -stime
if remain<=0:
return False
load =min(count,remain,v)
②___________
count -=load
return True
#取截止时间t、叉车数量n;读取订单数据表存入data列表，每个元素包含2个数据项，依次为装货时间和货物数量。代码略。
data =psort(data)
v=10
left,right =1,n
while left<=right:
m=(left +right)//2
if check(data,m,v,t):
right=m-1
else:
③___________
if left>n:
print("订单无法完成!")
else:
print("最少需要",left,"辆叉车")
(1) 若data=[[0,15],[4,12]]，t 为 15，则完成所有订单至少需要____辆叉车。 (2) 请在①、②、③划线处填入合适代码。
答案
(1) 3 ① count = data[i][1] ② cars[mini] = stime + load + 3 ③ left = m + 1
解析
check 函数用来判断 m 辆叉车是否可以把全部订单在 t 时刻前完成。cars 数组保存每一台叉车的空闲时刻。 ①取出当前订单的货物总数存入 count。 findi (cars) 遍历 cars 数组，找到空闲时间最早的叉车下标 mini。 stime 是叉车真正开始干活的时刻，取叉车空闲时间、订单装货时间两者的较大值。 remain = t3stime 代表留给搬运货物的最大可用时间，搬运完货物还要预留 3 单位的卸货时间。 load = min (count, remain, v)，该叉车本轮最多搬运件数，不能超过剩余货物 count，不能超过剩余可用时间 remain，不能超过最大装载 v=10。 ②更新该叉车下一次空闲时刻：开始时间 + 搬运 load 件耗时 load + 卸货耗时 3。 count -= load，循环直到该订单全部货物分配完毕。
外层是二分查找： check (m) 返回 True，代表 m 台叉车够用，尝试更小数量，right=m1。 check (m) 返回 False，m 台不够，要增加叉车，left = m+1。 循环结束 left 就是满足条件的最小叉车数；left>n 代表全部 n 台叉车也无法完成，输出订单无法完成。
小问推演：订单 1：0 时刻 15 件；订单 2：4 时刻 12 件，t=15。每台叉车最多一次搬 10 件，搬 x 件耗时 x，再加 3 卸货，推演得到最少需要 3 台叉车。
【变式1】数组的插入与删除：
①构建原始数组：
from random import randint
a=[0]*9
for i in range(__________):
a[i]=randint(1,10)
print(a)
运行结果：
②在第五个位置插入数组元素11：
from random import randint
a=[0]*9
for i in range(8):
a[i]=randint(1,10)
print(a)
for i in range(8,4,-1):
_____________________
____________________
print(a)
运行结果：
③在第五个位置删除原有数组元素：
from random import randint
a=[0]*9
for i in range(9):
a[i]=randint(1,10)
print(a)
for i in range(4,8):
______________________
print(a)
运行结果：
【参考答案与解析】
答案：①9 ②a[i] = a[i-1] a[4]=11 ③a[i]=a[i+1]
解析：①数组长度是9，下标 0~8，所以填：9，range(9) 生成0,1,2,…,8
②插入思路：从后往前，把下标大于等于4的元素全部后移一位，循环内语句：a[i] = a[i-1]把前一个位置的值，挪到当前i位置，元素后移。下标：4第五个位置对应下标4，a[4]=11
③删除思路：从下标4的后一位开始，逐个向前覆盖，把后面元素往前挪 填空：a[i] = a[i+1] i从4到7，a[4]=a[5]，a[5]=a[6]……依次向前覆盖，删掉下标4（第五个位置）的元素
考点二 单链表的访问
知●识●解●构
知识点1 链表的结构
1.链表指的是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。
2.链表节点的结构：
（数据区域保存数据元素，指针区域相邻节点的存储地址）
3.头指针（head）作用：
①作为链表的入口，只有通过头指针才能进入链表
②为循环链表设立一个边界，便于数据处理时的边界判断和处理
4.根据每个节点中指针的数量分为：
（1）单向链表： （2） 双向链表：
（3）循环链表：
第一个节点和最后一个点使用指针链接，这样就形成了循环链表。
基础巩固
1.关于链表的叙述，正确的是（）
A. 链表的所有节点在内存中一定是连续存放
B. 链表节点由数据区域和指针区域两部分组成
C. 头指针存储链表第一个节点的数据
D. 单向链表节点包含 prev 和 next 两个指针
【答案】B
【解析】A 错误，链表节点内存离散存储，不需要连续空间；B 正确；C 错误，头指针存放第一个节点的地址，不是数据；D 错误，单向链表只有 next 指针，prev 是双向链表才有。
2.下列关于头指针 head 的说法，错误的是（）
A. 头指针是链表的入口，通过头指针访问链表
B. 循环链表中，头指针可以用于边界判断
C. 头指针保存第一个节点的存储地址
D. 头指针就是链表的第一个节点
【答案】D
【解析】头指针是指针变量，存放首节点地址，本身不是节点；ABC 描述均正确。
3.链表和一维数组对比，下面说法正确的是（）
A. 链表支持下标随机访问任意节点，时间复杂度 O (1)
B. 链表插入中间节点，不需要移动大量数据，只修改指针
C. 链表物理内存必须连续
D. 链表访问元素速度一定快于数组
【答案】B
【解析】A 错误，链表只能顺着指针顺序遍历，不能随机访问；B 正确，链表插入删除只修改指针；C 错误，链表内存离散；D 错误，数组随机访问更快。
知识点2 链表的遍历、访问
1. 链表中的某一节点，只能从头指针开始，通过指针链接依次访问，不能像数组那样通过下标直接引用。
链表节点的访问：
运行结果
list=[['王林',2],['李丰',-1],['黄刚',1],['吴坚',0]]
head=3
p=head
while p!=-1:
print(list[p][0])
p=list[p][1]
基础巩固
1.关于单向链表的遍历访问，下列说法正确的是（）
A. 可以通过下标直接随机访问链表中的任意节点
B. 遍历单向链表必须从头指针 head 出发，顺着 next 指针依次访问各个节点
C. 遍历单向链表时，可以从中间某个节点直接跳转到前面的节点
D. 单向链表遍历时间复杂度一定为 O (1)
【答案】B
【解析】A 错误，链表没有下标，不支持随机访问；B 正确，单向链表只能从 head 开始，依靠 next 向后遍历；C 错误，单向链表只有 next 指针，无法回退访问前面节点；D 错误，遍历 n 个节点链表时间复杂度是 O (n)。
2.遍历单向链表，终止遍历的条件一般是（）
A. 当前节点的数据为 0
B. 当前节点的 next 指针为 None（空）
C. 访问到链表第 5 个节点
D. 头指针 head 的值变为 None
【答案】B
【解析】单向链表的尾节点 next 指针为空，代表链表结束，以此作为遍历终止条件；A 错误，节点数据可以是任意值，不能作为结束标志；D 错误，头指针 head 始终保存首节点地址，遍历过程不会改变。
3.对比一维数组和链表的访问、遍历，下列叙述正确的是（）
A. 数组随机访问 O (1)；链表遍历全部节点 O (n)
B. 数组和链表都可以通过下标随机访问
C. 数组遍历需要移动元素；链表遍历需要移动节点
D. 链表访问第 k 个元素速度快于数组
【答案】A
【解析】A 正确；B 错误，链表无下标；C 错误，遍历只是读取数据，数组、链表遍历都不需要移动元素 / 节点；D 错误，数组随机访问速度远快于链表。
考●向●破●译
考向1 结合程序片段，考查链表遍历的轨迹与结果推演
例1【26.04金华十校-11题】
某班成员分成男生女生两个链表`linka`，`linkb`，男生人数比女生多，需要将两个链表合成一个链表，合并后的链表顺序为男 1 女 1 男 2 女 2… 男 n，实现该操作的程序代码如下：
```
p,q = heada,headb
while p!=-1 and q!=-1:
temp = linkb[q][1]
#此处填入3句代码完成节点插入
q=temp
```
加框处可选的代码：
```
(1) linka[p][1]=linkb[q][1]
(2) linkb[q][1]=linka[p][1]
(3) linka[p][1]=q
(4) linkb[q][1]=p
(5) p= linka[p][1]
(6) p= linkb[q][1]
```
下列选项中，代码顺序正确的（）
A.(2)(3)(6) B.(1)(4)(5) C.(2)(3)(5) D.(1)(3)(5)
答案A
解析
链表存储规则：`linka[p][0]`为节点数据，`linka[p][1]`存后继节点下标；`‑1`代表链表结束。
目标：把女生节点`q`插入当前男生节点`p`的后面。
原始状态：`p(男) → next_m`；`q(女) → temp(下一个女生)`。
1. 语句`(2) linkb[q][1]=linka[p][1]`：女生节点 q 的后继指向 p 原来的后继`next_m`。
2. 语句`(3) linka[p][1]=q`：男生节点 p 的后继改为女生节点 q。
此时链表片段：`p(男) → q(女) → next_m`。
3. 语句`(6) p= linkb[q][1]`：p 移动到`next_m`，定位到下一个男生节点。
4. `q=temp`：q 移动到下一个女生节点，进入下一轮循环。
循环条件`p!=-1 and q!=-1`，女生链表遍历结束后，剩余男生节点保留在链表尾部，最终合并序列：**男 1 女 1 男 2 女 2…… 男 n**。
【变式1】
有如下程序运行后输出 cnt 的值为（ ）？
d=[[8,3],[15,4],[3,-1],[10,2],[6,0]]
h=1
cnt = 0
p = h
while p != -1:
if d[p][0] > 7:
cnt += 1
p = d[p][1]
print(cnt)
A.1 B.2 C.3 D.4
答案：C
解析：
遍历轨迹 p=1 →4 →0 →3 →2 →-1
p=1，d [1][0]=15>7，cnt=1；p=d [1][1]=4
p=4，d [4][0]=6>7 不成立；p=d [4][1]=0
p=0，d [0][0]=8>7，cnt=2；p=d [0][1]=3
p=3，d [3][0]=10>7，cnt=3；p=d [3][1]=2
p=2，d [2][0]=3>7 不成立；p=d [2][1]=-1
循环结束，cnt=3
【变式2】
d=[[4,-1],[9,0],[2,4],[6,1],[11,0]]
h=3
p = h
while p != -1:
d[p][0] = d[p][0] * 2
p = d[p][1]
p = h
res = ""
while p != -1:
res = res + str(d[p][0]) + " "
p = d[p][1]
print(res)
程序运行后输出结果是（）
A. 12 18 22 8 B. 6 9 11 4 C. 12 22 18 8 D. 8 18 22 12
答案：A
解析： 初始头指针 p = h = 3 链表原始遍历轨迹：3 →1 →4 →0 →-1 第一轮循环修改每个结点数据： p=3：d [3][0]=62=12，p=d[3][1]=1 p=1：d[1][0]=92=18，p=d[1][1]=0 p=4：d[4][0]=112=22，p=d[4][1]=0 p=0：d[0][0]=42=8，p=d [0][1]=-1，第一轮结束。
第二轮从头 h=3 再次遍历链表：依次取出 12、18、22、8。输出字符串：12 18 22 8。
考向2 结合链表特征，考查遍历终止条件与边界处理的代码实现
例1【26.04绍兴卷-15题】
现有 m 台 A 型机器 (编号 0‑m‑1)，n 台 B 型机器 (编号 m~m+n‑1)，需处理当天提交的 w 项作业。每项作业包含开始时间、结束时间、作业类型 (A、B 两类)。
规则：
1. A 类作业可分配至 A 型或 B 型机器，B 类作业只能分配至 B 型机器。
2. 每次分配优先选择最先结束先前作业的机器；多台同时满足，优先编号最小。
3. 选中机器未空闲，则作业延期到机器空闲后立刻执行；作业时长 (结束‑开始) 保持不变。
```
def allocate(data, m,n):
#data为排序完成的作业列表
seatcount = m+n
seats=[]
for i in range(seatcount):
seats.append([-1,i+1]) #seats[i][0]机器空闲时刻，seats[i][1]后继下标
seats[seatcount-1][1] = -1
head = 0
for d in data:
start, end, ptype = d[0], d[1], d[2]
duration = end - start
p = head
pre = idx = -1
while p!= -1:
if ①________ or (ptype == "B" and p >= m):
idx = p
break #找到目标机器，退出遍历
pre = p
p = seats[p][1]
#从链表摘下idx节点
if pre == -1:
head = seats[idx][1]
else:
seats[pre][1] = seats[idx][1]
#更新该机器的空闲时刻
if seats[idx][0] <= start:
seats[idx][0] = end
else:
②________
#把idx重新插入链表，维持链表按机器空闲时刻升序
pre, p = -1, head
while p!=-1:
v, k = seats[p][0], seats[idx][0]
if v < k or (v == k and p < idx):
pre = p
p = seats[p][1]
else:
break
③________
if pre == -1:
head = idx
else:
seats[pre][1]= idx
#计算全部作业完成最大时间，代码略
return maxt
```
(1)①处填入条件：________________
(2)②处填入代码：________________
(3)③处填入代码：________________
答案
① ptype == "A"
② seats[idx][0] += duration
③ seats[idx][1] = p
解析
链表核心考查点（遍历终止条件 + 边界处理）
1. **遍历循环：`while p!=-1`**
`p`为当前遍历节点下标；`‑1`是链表结束标记。**循环终止两种情况：p 走到链表末尾 (p==‑1)，或者`break`提前找到目标机器 idx 退出循环**。
`pre`变量保存**当前节点 p 的前驱下标**，专门处理边界：
- 如果`pre == -1`：代表`idx`是链表**头节点**，摘下节点时直接移动`head`头指针；
- 如果`pre !=‑1`：普通中间节点，修改前驱节点`seats[pre][1]`跳过 idx；
> 这是链表经典边界：区分「删头节点、删中间、删尾节点」，尾节点时`p==‑1`退出 while 循环。
2. ①条件：A 类作业，机器可以选全部；B 类作业，只能选编号 >=m 的 B 型机器。`ptype=="A" or (ptype=="B" and p>=m)`满足条件就找到了可用机器，break 终止 while 遍历。
3. ②：机器当前还没有空闲 (`seats[idx][0]>start`)，作业要延期；机器新空闲时刻 = 当前空闲时刻 + 作业时长。
4. ③重新插入 idx 节点：`seats[idx][1]=p`；p 是插入位置的后继。
> 边界：若`pre ==‑1`，插入到链表最开头，head=idx；否则`seats[pre][1]=idx`，前驱指向新节点。
【变式1】
d=[[2,1],[4,2],[6,-1]]，头指针h=0
p = h
lst=[]
while p != -1:
p = d[p][1]
lst.append(d[p][0])
print(lst)
程序运行后输出列表 lst 是（）
A. [2,4,6] B. [4,6] C. [4,6, 报错] D. [2,4]
答案：B
解析： 初始 p=0 第 1 轮：p≠-1，p=d [0][1]=1，append (d [1][0]=4) → lst=[4] 第 2 轮：p≠-1，p=d [1][1]=2，append (d [2][0]=6) → lst=[4,6] 第 3 轮：p≠-1，p=d [2][1]=-1，append (d [-1][0])，此时 p=-1，下一轮循环条件p!=-1不成立，循环终止。append 不会执行。 最终 lst=[4,6]
易混易错
1.错误 1：循环条件写成 while d[p][1]!=-1，会漏掉最后一个节点，尾节点不参与处理。
正确循环条件：p != -1，p 代表当前正在处理的节点。
2.错误 2：处理节点逻辑写在p=d[p][1]之后，第一个节点直接跳过。
顺序：先处理p，再执行p = d[p][1]移动指针。
3.易错：修改p的时候，忘记保留前驱节点t。很多题目重组链表，既要当前节点p，也要它的上一个节点t。
一定要用q保存后继，不要直接p=d[p][1]，因为操作中d[p][1]的值会被改写。
考点三 单链表的插入与删除操作
知●识●解●构
知识点1 链表指针更新逻辑
插入节点：要在节点 p 之后插入新节点 q。必须先连新节点的线，再改旧节点的线（先连后断）。
d[q][1] = d[p][1]
d[p][1] = q
删除节点：要删除节点 p 之后的节点 q。直接让 p 绕过 q。
q = d[p][1]
d[p][1] = d[q][1]
头节点操作：如果删除的是头节点，需要将 head 指向下一个节点（head = d[head][1]）。
链表节点的插入与删除：（修改指针）
例1：在有4个节点的单向链表中插入头节点
list=[['王林',2],['李丰',-1],['黄刚',1],['吴坚',0]]
head=3
list.append(['张三',head])
head=len(list)-1
p=head
while p!=-1:
print(list[p][0])
p=list[p][1]
例2：在单向链表的末尾插入一个新节点
list=[['王林',2],['李丰',-1],['黄刚',1],['吴坚',0]]
head=3
p=head
q=0
while p!=-1:
q=p
p=list[p][1]
list.append(['张三',-1])
list[q][1]=len(list)-1
p=head
while p!=-1:
print(list[p][0])
p=list[p][1]
例3：在单向链表王林和黄刚所处节点的中间位置插入一个新节点
list = [['黄刚',1], ['王林',3], ['李丰',0], ['吴坚',-1]]
head=2
p=head
t=0
w=int(input('请输入要插入的节点位置：'))
while p!=-1 and t!=w-1:
q=p
p=list[p][1]
t+=1
list.append(['张三',p])
list[q][1]=len(list)-1
p = head
while p != -1:
print(list[p][0])
p = list[p][1]
在有4个节点的单向链表中删除头节点
list=[['王林',2],['李丰',-1],['黄刚',1],['吴坚',0]]
head=3
head=list[head][1]
p=head
while p!=-1:
print(list[p][0])
p=list[p][1]
在有4个节点的单向链表中删除尾节点
list=[['王林',2],['李丰',-1],['黄刚',1],['吴坚',0]]
head=3
p=head
t=0
q=-1
while p!=-1:
x=q
q=p
p=list[p][1]
list[x][1]=list[q][1]
p = head
while p != -1:
print(list[p][0])
p = list[p][1]
例3：在单向链表的输入位置删除节点
list=[['王林',2],['李丰',-1],['黄刚',1],['吴坚',0]]
head=3
p=head
t=0
w=int(input('请输入要删除的节点：'))
while p!=-1 and t!=w-1:
q=p
p=list[p][1]
t+=1
list[q][1]=list[p][1]
p = head
while p != -1:
print(list[p][0])
p = list[p][1]
易混易错
链表操作（插入、头插、删除、重组）必须先保存后继节点，再修改指针。一旦直接修改指针，后继节点地址直接丢失，链表断裂。
口诀：先存后继，再改链接；新节点指针赋值要在旧指针被覆盖之前。
考●向●破●译
考向1 结合流程图或代码，考查指针更新顺序
例1 (2024·浙江1月选考，第12题) 使用列表 d 模拟链表结构（节点数大于0），每个节点包含数据区域和指针区域，h 为头指针。链表中各节点已按数据区域中数值的绝对值由小到大排列。现要修改该链表各节点的链接关系，使链表各节点按数据区域中的数值由小到大排列。实现该功能的程序段如下，方框中应填入的正确代码为（ ）
t = h
p = d[h][1]
while p != -1:
q = d[p][1]
if d[p][0] > 0:
if d[t][0] > 0:
# (1)
else:
# (2)
else:
# (3)
p = q
A. d[q][1]=p d[t][1]=q d[t][1]=q
B. d[p][1]=t d[t][1]=q d[q][1]=p
C. d[t][1]=q d[t][1]=p d[p][1]=h
D. d[q][1]=p d[p][1]=h d[t][1]=q
【参考答案与解析】
答案：C
解析：本题考查单链表及分支语句和数据排序等知识。由于数据区域中数值的绝对值由小到大排列，由代码可知，原先的节点关系是：t → p → q。
若数据区域 d[p][0] 的数值为正数，则原链表节点关系不变，只需将各节点关系往下迭代即可，即 t 变为 p，p 变为 q。
若数据区域 d[p][0] 的数值为负数，则原先的链表各节点关系需要重新指向。由于原数据是按照绝对值大小排序的，因此越往后面绝对值数越大，其相反数（负数）就越小，因此每一个当前节点 p 的负数肯定是当前链表中最小的数，应该变为最小的头节点，采用头插法可以实现，即将当前节点 p 的指针域指向原先的头节点 h，然后再将头节点 h 变为当前节点 p。故本题选C。
【变式1】(2024·浙江6月选考，第12题) 使用列表 d 模拟链表结构（节点数n>0），每个节点包含数据区域和指针区域，h 为头指针。现要按链表顺序将这n个节点中的数据依次存放到 d[0][0]、d[1][0]…d[n-1][0] 中，最终保持节点链接关系不变。实现上述功能的Python程序段如下，方框中应填入的正确代码为（ ）
p, i = h, 0
while p != -1:
tp = d[p][1]
if p == i:
i += 1
elif p > i:
d[i][0], d[p][0] = d[p][0], d[i][0]
i += 1
# (1)
p = tp
# 调整头指针h及指针区域，保持节点链接关系不变，代码略
A. d[i][1]=d[p][1] d[p][1]=i
B. d[p][1]=d[i][1] d[i][1]=p
C. d[i][1]=p d[p][1]=d[i][1]
D. d[p][1]=i d[i][1]=d[p][1]
【参考答案与解析】
答案：B
解析：本题考查链表的算法实现。调整头指针 h 及指针区域，保持节点链接关系不变，具体代码如下：h=i=0; while i<len(d): d[i][1]=i+1; d[-1][1]=-1。链表中数据的顺序为 [18,15,19,12,29,23]，对应节点索引 p 的值依次为 [1,0,4,2,5,3]，变量 i 从0开始，若当前节点索引 p 与 i 不相等，索引 p 必定大于 i，将当前节点 p 与索引 i 节点值交换。语句 d[p][1]=d[i][1] 删除节点 i，然后将节点 i 插入到 p 节点的前面。故选B。
考点四 双向链表的访问
知●识●解●构
知识点1 双向链表基本概念
1. 定义
双向链表的每个结点有两个指针域：一个指向后继结点 (next)，一个指向前驱结点 (prev)；还有数据域 (data)。既可以向后遍历，也可以向前遍历。
单向链表：只能从表头向后遍历，找前驱结点必须从头遍历。
双向链表：已知某结点，可以直接访问前驱、后继。
2.结点结构
【prev | data | next】
prev：指向前一个结点
data：存储数据
next：指向后一个结点
3. 双向链表优缺点
优点：
① 可正向、反向双向遍历
② 已知某结点，删除该结点不需要从头找前驱，效率高
缺点：
① 每个结点多一个指针域，占用更多存储空间
② 插入、删除结点时，要修改 4 处指针（单向链表只改 2 处），指针顺序写错极易出错。
知识点2 双向链表节点访问
双向链表节点的访问（顺向访问）
list=[['b',3,2],['d',2,-1],['c',0,1],['a',-1,0]]
head=3
p=head
while list[p][2]!=-1:
print(list[p][0],end=”→”)
p=list[p][2]
print(list[p][0])
运行结果：
考●向●破●译
考向1 结合流程图或代码，考查指针更新顺序
例1（改编·Z20联盟）关于双向链表的结构与遍历，下列程序逻辑说法正确的是（）
A. 双向链表可以通过下标随机访问任意节点
B. 正向遍历双向链表的核心语句为：p = p.next
C. 反向遍历需要从 head 节点开始，不断执行 p = p.prev
D. 双向链表遍历的时间复杂度为 O(1)
【答案】B
【解析】所有链表均不支持下标随机访问，A 错；正向遍历从 head 出发，不断后移 next，B 正确；反向遍历需要从 tail 出发，C 错；完整遍历 n 个节点时间复杂度为 O(n)，D 错。
【变式1】改编·金华十校）遍历双向链表完整所有节点，下列代码逻辑正确的正向遍历是（）
A.p = head B.p = tail
while p != None: while p != None:
p = p.next p = p.prev
C.p = head D.p = tail
while p != None: while p != None:
p = p.prev p = p.next
【答案】A
【解析】正向遍历：起点 head，循环条件 p 非空，每次 p 指向后继 next；B 为反向遍历，C、D 指针逻辑完全错误，会直接提前结束或越界。
真题溯源·考向感知
——溯源真题逻辑，感知高考考向
1．【2024·浙江1月选考，第9题】
数组元素 a [0] 至 a [n‑1] 依次存放着 n 个数据，现需要将元素 a [n‑1] 插入在下标为 x (0 ≤x<n‑1) 的位置。
例：n 为 5，数组 a 为 [0,3,4,6,7]，x 为 2，插入操作后 a 为 [0,3,7,4,6]。
实现该功能的程序段如下，方框中应填入的正确代码为
temp = a [n‑1]
for i in range (n‑2, x‑1, ‑1):
a[x] = temp
A. a[i+1]=a[i] B. a[i‑1]=a[i] C. a[i]=a[i+1] D. a[i]=a[i‑1]
答案：A
解析：
功能是把末尾元素 a [n‑1] 插入下标 x，下标 x 到 n‑2 的元素整体向后移动一位，腾出 x 位置。后移操作语句 a [i+1]=a [i]，把 i 位置的值复制给 i+1。range (n‑2, x‑1,‑1) 逆序循环，从后往前处理，防止数据被提前覆盖。易错：等号左右写反、使用正序循环。
2. 【2024·浙江1月选考，第12题】 使用列表 d 模拟链表结构（节点数大于0），每个节点包含数据区域和指针区域，h 为头指针。链表中各节点已按数据区域中数值的绝对值由小到大排列，如图a所示。现要修改该链表各节点的链接关系，使链表各节点按数据区域中的数值由小到大排列，结果如图b所示。实现该功能的程序段如下，方框中应填入的正确代码为（ ）
t = h
p = d[h][1]
while p != -1:
q = d[p][1]
if d[p][0] > 0:
if d[t][0] > 0:
# (1)
else:
# (2)
else:
# (3)
p = q
A. d[q][1]=p d[t][1]=q d[t][1]=q
B. d[p][1]=t d[t][1]=q d[q][1]=p
C. d[t][1]=q d[t][1]=p d[p][1]=h
D. d[q][1]=p d[p][1]=h d[t][1]=q
【参考答案与解析】
答案：C
解析要点：
分析数据特征：原链表按绝对值由小到大排列，要改为按数值由小到大排列。
判断分支逻辑：
若 d[p][0] > 0 且 d[t][0] > 0：当前节点 p 为正数，且前驱节点 t 也为正数，说明当前节点应保持在原位置，只需将 t 的指针指向 q（d[t][1]=q）。
若 d[p][0] > 0 且 d[t][0] <= 0：前驱节点 t 为负数，当前节点 p 为正数，需要将 p 接到 t 之后（d[t][1]=p）。
若 d[p][0] <= 0：当前节点为负数，应将其移动到链表头部，采用头插法（d[p][1]=h）。
综合判断，故选C。
3.(2024·浙江6月选考，第12题)使用列表 d 模拟链表结构（节点数 n>0），每个节点 d [p][0] 存数据，d [p][1] 存后继指针，h 为头指针。需要顺着链表遍历顺序，把链表节点的数据依次存放到数组下标 0,1,2…n1 位置，链表节点链接关系保持不变。 部分代码：
p,i = h,0
while p != -1:
tp = d [p][1]
if p == i:
i +=1
elif p > i:
d [i][0], d [p][0] = d [p][0], d [i][0]
i +=1
p = tp
#调整头指针h及指针区域，保持节点链接关系不变，代码略
A. d[i][1]= d[p][1] d[p][1]=i B.d[p][1]=d[i][1] d[i][1]=p
C.d[i][1]=p d[p][1]= d[i][1] D.d[p][l]=i d[i][1]= d[p][1]
答案：B
解析： p 为原链表当前节点下标，i 为目标位置下标。p>i 时交换 d [i] 与 d [p] 的数据域 d [][0]；题目要求保持链表链接不变，因此两个节点的指针域 d [][1] 也需要交换。 正确顺序：d [p][1] = d [i][1]，将 i 节点原来的后继赋给 p；d [i][1]=p，i 节点的后继指向 p。对应 B。 A 会制造自环；C 先执行 d [i][1]=p 会直接覆盖 i 原有后继，信息丢失；D 制造自环，链表断裂。 易错提醒：节点整体交换，只交换数据域不够，指针域也要处理；操作前不能覆盖原有指针值。tp=d [p][1] 是保存外层遍历的后继，和节点内部指针交换无关。
4.(2025·浙江6月选考，第11题) 有如下 Python 程序段：
tag=[0]*len (data)
p=i=0
while i<len (data):
if tag [p]==0 and data [p][1]!=-1:
tag [i]+=1
p=data[p][1]
else:
tag [i]+= tag [p]
i+=1
p=i
若 data = [[11,3],[23,-1],[15,0],[26,1],[63,2]]，运行该程序段后，tag [4] 的值为( )
A.1 B.2 C.3 D.4
答案：D
解析： data [x][1] 是指针域。链表链接：0→3→1 (-1)；2→0；4→2。节点 4 完整链条 4 → 2 →0 →3 →1，共 4 个节点，tag [4]=4。p 顺着指针 data [p][1] 向后走，统计整条链表节点个数存入 tag [i]。易错：混淆数据域与指针域；区分 p!=-1 和 d [p][1]!=-1 两个条件。
5.(2026·浙江1月选考，第15题) 某中转站负责转运物品，每个物品规格相同且有唯一的正整数编号。物品送达中转站的时间先后与编号大小无关，每次运走的物品编号均需连续。将中转站中的现有物品编号划分为若干序列，连续的编号按升序置于同一序列，不连续的编号置于不同序列。当需要运走x个物品时，检查当前时间现有序列中是否存在长度≥x的序列，若存在，则选择长度最短的序列（若最短序列有多个，则选择起始编号最小的序列），运走从其起始编号开始的x个连续编号的物品。
(1) 若物品按如图所示的时间送达中转站，第一次需要运走的物品个数为3，时间为09:15，则该次运走物品的起始编号为______。
【参考答案与解析】
答案：206
解析：在09:15时，送达中转站的物品编号有202、206、203、201、208、207、204。将连续的编号按升序置于同一序列，得到序列 201, 202, 203, 204 和序列 206, 207, 208。若需要运走的物品个数为3，则选择长度大于等于3的序列中长度最短的序列，即序列 206, 207, 208，起始编号为206。
(2) 定义如下函数 check(reqs, m)，用于判断列表 reqs 中是否存在下列情况：任意连续60分钟内，需要运走的物品数量总和超过 m。列表 reqs 中的每个元素包含两个数据项，依次为需要运走的时间（已转换为分钟数）和物品数量，已按时间升序排列。
def check(reqs, m):
i = j = 0
s = 0
while j < len(reqs):
s += reqs[j][1]
if s > m:
return True
j += 1
while s > m and i < j:
s -= reqs[i][1]
i += 1
return False
① 若 reqs 为 [[6,1],[19,13],[35,3],[70,2],[75,7]]，m 为20，则返回值为______。
② 若 reqs 的长度为100，函数返回值为False，则while语句中循环体的执行次数最多是______次。
【参考答案与解析】
答案：① True ② 199
解析：
① 遍历 reqs：j=0 时 s=1；j=1 时 s=14；j=2 时 s=17；j=3 时 s=19；j=4 时 s=26 > 20，返回 True。
② 当函数返回 False 时，外层 while 循环需要遍历所有元素，执行100次。内层 while 循环在最坏情况下（即所有元素累加后都不超过 m）不会执行，但 i 仍然会随着 j 的增加而增加。外层循环执行100次，每次 j += 1，内层循环最多执行99次（当 i 从0增加到99），因此循环体总执行次数最多为 100 + 99 = 199 次。
2 / 3
学科网（北京）股份有限公司
学科网（北京）股份有限公司
学科网（北京）股份有限公司
$
资源预览图
