资源简介

专题12　链　表
学业要求 知　识　点 学业水平等级
1.能结合链表的应用案例，掌握链表的概念，了解链表组织、存储结构的原理与特性 3
2.能根据问题特点规划节点的数据域和指针域，完成创建链表、访问、删除、插入链表节点的操作 4
知识点一　链表的遍历
【知识梳理】
1.链表是将需要处理的数据对象以________的形式，通过指针串联在一起的一种数据结构。
2.同一个链表中每个节点的________均相同，由数据区域和指针区域组成。
3.每个链表都有一个________指针head，是链表的入口，也便于循环链表在数据处理时的边界判断和处理。
4.链表可以根据每个节点中指针的数量分为________向链表和________向链表。
5.若链表data每个节点只有一个值和一个指针，当前节点为q，则他的后继节点即下一个节点的索引是________。
6.前节点q初值为头指针head，通过语句q＝data[q][1]遍历整个链表，当q的值为________时结束链表遍历。
7.当链表遍历结束后，q的值为－1，其前驱为________节点。
【经典案例】
单向链表是由节点构成，head指针指向第一个成为表头节点，而终止于最后一个指向－1的指针。对链表的访问要通过顺序读取从头部开始。链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表的遍历必须从头节点开始，每个节点包含数据区域和指针区域，数据区域可能有多个值，指针区域值往往在节点最后一个位置。若当前q指向头指针head，那么a[q]是整个节点的值，a[q][0]是数据区域的值，a[q][1]是下一节点的索引，通过语句q＝a[q][1]，实现指针向后移动。
【例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时，表示遍历完了
听课笔记：____________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
【变式1】 某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
【例2】 使用链表结构模拟某景区游玩路线，链表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.②④③
思维点拨
明考向 本题考查多条链表的遍历
精点拨 3条链表构建在数组a中，头指针存储在数组head中，需遍历头指针数组，从而来遍历3条链表。(1)处为当前节点赋值为头指针head[i]，变量s存储所有节点游览总时间。(2)(3)遍历链表，并统计各个节点游览时间和，由于当前节点已经计入总时间，因此先要跳转到下一点，将下一节点的时间加入到总时间，注意遍历结束的条件是当遍历到尾节点时，终止遍历
听课笔记：___________________________________________________________
______________________________________________________________________
______________________________________________________________________
______________________________________________________________________
【变式2】 实现在链表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.②④
知识点二　链表节点的删除
【知识梳理】
1.链表占用的空间不稳定，可根据需求增删________，提高空间的利用率。
2.删除链表头节点往往修改头指针的值，将头指针指向原头指针的________即可。
3.若链表data每个节点只有一个值和一个指针，其头指针为head，则删除头指针的语句为head＝________。
4.删除链表其他节点含尾节点的方法是：修改删除节点的前驱节点指针区域值，使其前驱节点直接指向删除节点的________。
5.若链表data每个节点只有一个值和一个指针，当前节点q的前驱节点为pre，则删除当前节点q的语句为________________。
【经典案例】
在数组中删除某个节点，往往需把该节点后面的值往前移，时间复杂度为线性阶O(n)。链表节点的删除分为头节点的删除和其他节点的删除，头节点的删除只要移动头指针到下一节点，即head＝a[head][1]即可，其他节点的删除，只要修改该节点的前驱节点的指针区域值为该节点的后继节点索引即可，时间复杂度为常量阶O(1)。
【例题】 有如下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
思维点拨
明考向 本题考查链表节点的删除
精点拨 在自定义函数guess中，当前节点p从cur节点的后继开始，如果后面的元素与cur节点元素值相等，则删除节点p，因此是从当前节点链表中删除重复的元素
听课笔记：___________________________________________________________
______________________________________________________________________
______________________________________________________________________
【变式】 已知链表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]
知识点三　链表节点的插入
【知识梳理】
1.新节点插入往往通过append方法，将新增加节点添加到数组data最后位置，其节点索引值为________。
2.可以在原链表的头节点前插入一个值为x的新节点，步骤一新增一个节点并让该节点的指针区域值为原________节点data.append([x，head])，步骤二修改头指针head的值为新节点索引head＝len(data)－1。
3.在当前节点q(q不是头节点)前插入一个值为x的新节点，步骤一新增一个节点并让该节点的指针区域值为该节点索引data.append([x，q])，步骤二修改当前节点的________节点指针区域值为新节点索引data[pre][1]＝len(data)－1。
4.在实现链式队列时，往往增加一个尾指针来指向链表最后一个节点，若有新节点增加到尾节点后面时，只要将原________节点指向新增节点，同时修改尾指针即可，语句分为data.append([x，－1])，data[tail][1]＝len(data)－1。
【经典案例】
在数组中插入节点的时间复杂度为线性阶O(n)，与数组相比，只能通过头指针进入链表，链表节点的访问效率较低，但是插入节点的时间复杂度为常量阶O(1)。链表节点的插入分为在头节点前的插入和其他节点前插入两种，头节点前插入新节点，该节点指向原头节点，并要修改head指针。在当前节点q前插入新节点，该新节点的后续是q，将修改q的前驱节点指针区域值。
【例1】 某电影演员表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.②③①
思维点拨
明考向 本题考查链表的基本操作
精点拨 遍历链表，将找到的女演员节点依次链接形成一个单独的链表，同时将女演员节点从原链表删除。操作完成后，原链表就是一个只有男演员的单向链表。指针q、r指向p的前驱和女演员链表的尾节点。将节点从原链表删除前，先要链接到女演员链表尾节点
听课笔记：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
【变式】 有如下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)
【例2】 某编程兴趣小组设计了一个点歌模拟程序，功能如下：
运行程序后，从键盘输入“A”，则显示已点的歌曲列表(歌单)；输入“B”则可以自行输入歌曲并添加到歌单以完成点歌；输入“C”则可以将指定的歌曲置顶等待播放；输入“D”则播放当前第一首歌曲，并将该歌曲从列表中删除；输入“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成立表示链表中只有一个节点，否则将头指针向后移动，删除头节点
听课笔记：_____________________________________________________________
______________________________________________________________________
______________________________________________________________________
1.对于链表的描述，下列说法不正确的是(　　)
A.同一链表中每个节点的结构均相同
B.每个链表必定有一个头指针
C.链表占用的空间不固定
D.创建的新链表中至少要有一个节点
2.使用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″
3.利用列表模拟非循环链表a(可能存在已被删除的节点)，下列程序运行完毕后，变量p表示尾节点的节点位置是(　　)
A.head＝0
p＝head
while p！＝－1：
t＝p
p＝a[p][1]
B.head＝0
p＝head
while a[p][1]！＝－1：
p＝a[p][1]
C.head＝0
p＝head
while a[a[p][1]][1]！＝－1：
p＝a[p][1]
D.head＝0；p＝head
n＝len(a)
while n>1：
p＝a[p][1]
n－1＝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
5.有如下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
6.用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.②①③
7.小张准备去多个城市旅游，他设计的行程若采用链表结构表示，如图a所示。
若行程有变，需在“上海”与“成都”之间增加一站“杭州”，链表修改为如图b所示，有以下可选操作：
①“上海”所在节点的next值赋为“杭州”节点的next值
②“上海”所在节点的next值赋为5
③“杭州”所在节点的next值赋为“上海”所在节点的next值
④“杭州”所在节点的next值赋为－1链表更新顺序正确的是(　　)
A.③① B.③② C.①④ D.②④
8.有两个降序序列的链表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.②⑥③
9.在一个单向链表(如图)中，若在尾指针tail所指节点之后插入新节点(r所指节点)，则执行的操作是(　　)
A.tail所指节点的data3值赋为r所指节点的data4值
B.r所指节点的next值赋为tail
C.r所指节点的next值赋为－1
D.tail所指节点的next赋为r，r所指节点的next值赋为－1
10.将两个链表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.②③⑤
专题12　链　表
知识点一
知识梳理
1.节点　2.结构　3.头　4.单　双　5.data[q][1] 6.－1　7.尾
经典案例
例1　A
变式1　C　[本题考查循环链表的遍历。h表示头节点，值为0，在链表中有一个节点指向0，因此判定该链表为循环链表。当前节点p从头节点开始遍历，若当前节点指针区域值为头节点，结束遍历，即遍历到尾节点终止循环，没有输出尾节点的值，循环结束后，再次输出尾节点的值。]
例2　D
变式2　D　[本题考查链表遍历和最值查找。当前节点从头节点开始遍历，最小值的初值为头节点大小，因此需先移动到下一节点，再与最值进行比较，同时终止遍历的条件是遍历到尾节点马上结束。]
知识点二
知识梳理
1.节点　2.后继　3.data[head][1]　4.后继 5.data[pre][1]＝data[q][1]
经典案例
例题　A
变式　D　[本题考查链表节点的删除。①循环遍历整个链表。②q为当前元素指针，p是当前节点q的前驱，要删除q节点，只需要修改p的指针为q的后继。]
知识点三
知识梳理
1.len(data)－1　2.头　3.前驱　4.尾
经典案例
例1　D
变式　B　[本题考查链表的插入。①自定义函数lnkid的功能是查找n在链表中插入位置，head在不断地向后移动，因此n将和a[head][0]进行比较，当比a[head][0]小时，不断地向后查找位置。②语句p＝lnkid(n，head)将返回在节点p的后面插入新的数n，因此将修改a[p]节点指针区域值为当前插入点索引。]
例2　①data[tail][1]＝len(data)－1　②data[pre][1]＝data[cur][1]　③tail＝pre　④head＝data[head][1]
当堂过关检测
1.D　[本题考查链表的基本性质。A选项链表节点包含数据区域和指针区域，每个节点中的数据区域中数据类型是相同的。B选项访问链表的某一节点，只能从头指针开始，依次访问。C选项链表通过指针相连，相信节点存储时不需要连续空间，因此链表空间是不固定的。D选项可以是空链表，数据区域为空，头指针为－1。]
2.D　[本题主要考查链表的操作。head＝3，即对应列表索引3，其值为“rabbit”，指向索引为0的节点，其值为“cat”，依次类推，依次输出各节点数据域的值，内容为″rabbit″，″cat″，″dog″，″pig″。]
3.B　[本题考查链表的遍历。A选项当前节点为p，当遍历到节点为空时停止遍历，因此遍历结束后，p节点为空，其前驱t为尾节点。B选项当前节点为p，若当前节点的指针区域值为－1，结束遍历，那么当前节点p为尾节点。C选项当前节点从头节点开始遍历，a[a[p][1]]指当前节点的后继节点，若该节点的指针区域值为－1，表示该节点为尾节点，当前节点为尾节点的前驱。D选项链表a可能存在已被删除的节点，因此len(a)的值可能大于节点总数。]
4.C　[本题考查链表的遍历。条件a[p][1]！＝－1表示当前节点的指针区域值为－1，即当前节点为尾节点。当遍历到尾节点时，结束循环。]
5.A　[本题考查链表的操作。当a[q]节点上的值与a[p]节点上的值相同时，q指针往后移一位。程序的功能是将与p指针所指示的节点值相同的a[q]节点删除。指针t的作用是维护了去重后链表最后一个节点的位置。输出链表的所有非重复节点。]
6.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]。]
7.B　[本题考查的知识点是链表元素的插入。链表中插入新元素并不需要进行元素位置移动，只需要进行节点指针域的更改即可。在“上海”与“成都”之间增加一站“杭州”，需要先将新元素“杭州”的指针域设置为“成都”所在位置，再更改节点“上海”的指针域至节点“杭州”所在位置。]
8.A　[(1)将链表b中的数据合并到链表a，两个节点数据区域值比较，如果链表a中值大于等于链表b中值，无需合并。(2)将链表b中的数据添加到链表a时，添加数据区域值为b[p][0]，指向p。(3)将前驱指向新增节点位置。]
9.D　[本题主要考查链表的操作。链表中尾结点的next指针为－1，若在尾指针tail所指节点之后插入新节点(r所指节点)，则执行的操作是：tail所指节点的next赋为r，r所指节点的next值赋为－1。]
10.B　[本题考查链表节点的插入操作。程序将节点q插入到节点p的后面，因此q的指针域的值将发生变化，为了链表b正常遍历，应先保存q的后继。插入过程中，由于已经保存了q的后继，因此可以先修改q的指向，再修改p的指向，最后将p移动到原插入节点q的后继。]

展开更多......

收起↑