资源简介

4.6　链　表
学习目标　
1.掌握链表的概念和链表的遍历方法。
2.掌握链表头节点、尾节点的插入和删除操作。
3.掌握链表除头尾节点外的其他节点的插入和删除操作。
(2024年6月浙江选考)使用列表d模拟链表结构(节点数n>0),如图a所示,每个节点包含数据区域和指针区域,h为头指针。现要按链表顺序将这n个节点中的数据依次存放到d[0][0]、d[1][0]…d[n-1][0]中,最终保持节点链接关系不变,结果如图b所示。实现上述功能的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
　　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　　链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表每个节点的结构是相同的,由数据区域和指针区域组成,其中指针区域指向下一个节点的索引。链表的访问必须从头节点开始,因此头指针是链表必不可少的元素。在数组中删除某个节点,往往需把该节点后面的值往前移,时间复杂度为线性阶O(n)。链表节点的删除分为头节点的删除和其他节点的删除,头节点的删除只要移动头指针到下一节点,即head=a[head][1]即可,其他节点的删除,只要修改该节点的前驱节点的指针区域值为该节点的后继节点索引即可,时间复杂度为常量阶O(1)。
例1 有如下链表操作Python程序段:
a=[[2,2],[4,4],[8,3],[3,-1],[5,0],[1,1]]
head=5
q=random.randint(0,5)
while head!=q:
　　t=head
　　head=a[head][1]
　　a[t][1]=a[q][1]
　　a[q][1]=t
#按链表顺序输出元素,代码略
执行上述程序后,下列输出结果不可能的是(　　)
A.145283 B.382541
C.825413 D.254813
思维点拨
明考向 本题考查链表节点删除和插入的算法实现
精点拨 算法的功能将头节点至节点q之前的节点依次插入到q节点之后。链表a的逻辑顺序为:1→4→5→2→8→3。依次列举6种可能。若q为1,不发生改变;若q为4,结果为4-1-5-2-8-3;若q为5,结果为5-4-1-2-8-3;若q为2,结果为2-5-4-1-8-3;若q为8,结果为8-2-5-4-1-3;若q为3,结果为3-8-2-5-4-1
答案　D
变式1 有如下Python程序段:
a=[4,5,3]
d=[[3,"A",2],[6,"B",0],[3,"C",1]]
head=1;p=2
n=3;ans=""
i=0
while n>0 and i　　q=d[p][2]
　　if d[q][0]>a[i]:
　　　　d[q][0]-=a[i]
　　　　i+=1
　　else:
　　　　ans+=d[q][1]
　　　　a[i]-=d[q][0]
　　　　d[p][2]=d[q][2]
　　　　n-=1
　　p=d[p][2]
执行该程序段后,ans的值是(　　)
A."ABC" B."ACB"
C."BAC" D."CBA"
答案　A
解析　本题考查循环链表以及队列的算法实现。链表d构成一个循环链表的队列,队列依次为BAC,若a[i]的值能分配给队首,则队首元素出队,否则更新剩余部分,再重新入队。变量p是链表的尾指针,指针q从头节点开始遍历,若当前节点d[q][0]大于a[i],a[i]不够分配,更新d[q][0],同时i向后移动。若当前节点d[q][0]小于等于a[i],删除当前节点q,同时n的值减少1个,表示完成一个元素的分配,同时更新a[i]。语句p=d[p][2]的功能是继续向后遍历。"B"更新为2后入队;"A"出队,"C"更新为2后入队;"B"出队,"C"出队。
例2 使用列表d模拟链表结构(节点数大于0),每个节点包含数据区域和指针区域,h为头指针。链表中各节点已按数据区域中数值的绝对值由小到大排列,如图a所示。现要修改该链表各节点的链接关系,使链表各节点按数据区域中的数值由小到大排列,结果如图b所示。实现该功能的程序段如下,方框中应填入的正确代码为(　　)
t=h
p=d[h][1]
while p!=-1:
　　q=d[p][1]
　　　　　　　　
　　p=q
d[t][1]=-1
A.if d[p][0]>0:
　　d[q][1]=p
　　d[t][1]=q
else:
　　d[h][1]=q
　　h=p
B.if d[p][0]>0:
　　d[t][1]=q
　　t=q
else:
　　h=p
　　d[p][1]=t
C.if d[p][0]>0:
　　d[t][1]=p
　　t=p
else:
　　d[p][1]=h
　　h=p
D.if d[p][0]>0:
　　d[t][1]=q
　　d[q][1]=p
else:
　　d[p][1]=h
　　h=q
思维点拨
明考向 本题考查链表节点删除和插入的算法实现
精点拨 实现程序的功能是从第2个节点开始,将遍历到节点插入新链表的头部或尾部。题图a按绝对值升序排序数据,链表中数据依次为-11,14,16,17,-18,要求改变链接关系,使链表各节点按数据区域中的数值由小到大排列。若链表中只有1个节点,其值无论是正数还是负数,均是最小的数。同时他既是头节点h,也是尾节点t。因此变量p从链表第2个节点开始遍历各个节点,若遍历到负数,则该数绝对值越大,其值就越小,需将该节点从原链表中删除,并移动到头节点的前面,进行的操作是将该前节点p指向原头节点h,同时修改当前位置为头指针。若为正数,将该节点链接到尾节点t的后面
答案　C
变式2 使用列表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
解析　本题考查链表节点删除和插入的算法实现。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,因此只要把这条语句放在判断结构的下方即可。
1.采用Python二维列表模拟链表,
a=[['A',1],['B',2],['C',3],['D',4],['E',5],['F',-1]]
head=0;p=a[head][1]
a[head][1]=-1
while p!=-1:
　　p=a[p][1]
　　if p==-1:
　　　　break
　　t=a[p][1];a[p][1]=head
　　head=p;p=t
执行以上程序后,以head为首的链表结构为(　　)
A.E→C→A B.A→C→E
C.B→D→F D.F→D→B
答案　A
解析　本题考查链表的基本操作。只提取奇数位的链表元素,并逆序输出。p的初值为a[head][1],即head的后继,进入循环后,语句p=a[p][1]的功能是向后遍历,让该节点指向头节点,p再向后遍历。A后继的后继是C,当前头节点为C,C指向A;C后继的后继是E,当前头节点为E,E指向C。
2.将链表中的奇数节点和偶数节点分别排在一起,奇数节点和偶数节点的相对顺序不变。如原始链表为,新链表为。部分程序如下:
#读入链表,存储在列表a中,head存储链表的头节点
odd=head;even=a[odd][1]
tmp=even
while a[odd][1]!=-1 and a[even][1]!=-1:
　　　　　　　　
a[odd][1]=tmp
上述程序段中方框处可选的语句为:
①odd=a[odd][1]
②even=a[even][1]
③a[odd][1]=a[even][1]
④a[even][1]=a[odd][1]
则方框处语句依次为(　　)
A.①③②④ B.①②③④
C.③②④① D.③①④②
答案　D
解析　本题考查链表的插入。先分别获取奇数节点连接而成的链表和偶数节点连接而成的链表;再连接两个链表得到新链表。
3.某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
答案　C
解析　本题考查循环链表的遍历。h表示头节点,值为0,在链表中有一个节点指向0,因此判定该链表为循环链表。当前节点p从头节点开始遍历,若当前节点指针区域值为头节点,结束遍历,即遍历到尾节点终止循环,没有输出尾节点的值,循环结束后,再次输出尾节点的值。
4.链表中有两个不同节点指向同一个节点,构成一个环,编写程序检验链表指针设置是否合理的代码如下,请将空白处补充完整
#将链表数据存储在列表d中,每个节点第1个元素为值,第2个元素为指针
slow,fast=head,head
while ①　　　　　　:
　　slow=d[slow][1]
　　fast=d[d[fast][1]][1]
　　if ②　　　　　　:
　　　　print("链表中有环,指针设置不合理!")
　　　　break
　　else:
　　　　print("链表指针设置合理!")(　　)
A.①fast=-1 and a[fast][1]=-1
②fast!=slow
B.①fast=-1 and a[fast][1]=-1
②fast==slow
C.①fast=-1 or a[fast][1]=-1
②fast!=slow
D.①fast=-1 or a[fast][1]=-1
②fast==slow
答案　D
解析　使用两个指针,一个移动得较慢slow(每次移动一步),另一个指针fast移动得较快(每次移动两步)。如果链表中存在环,这两个指针最终会相遇。如果链表没有环,快指针会先到达链表的末尾,若链表节点数为奇数,则fast到达尾节点时结束。
5.有如下程序段:
people=[[1,1],[2,2],[3,3],[4,4],[5,5],[6,0]]
k=2;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])
运行该程序段,输出的结果为(　　)
A.3 B.5
C.6 D.2
答案　B
解析　本题考查循环链表的算法实现。每遍历一次,i增加1,实现计数。第1次删除节点2,第2次删除节点4,第3、4、5分别删除节点6、3、1,链表中只剩下节点5。
6.删除升序链表link中重复的数据,仅保留下不重复的数据的部分Python程序段如下:
link=[[2,1],[2,2],[2,3],[5,4],[6,-1]]
pre=head=0
cur=link[pre][1]
while cur!=-1:
　　if link[pre][0]!=link[cur][0]:
　　　　(1)　　　　　　
　　else:
　　　　(2)　　　　　　
　　(3)　　　　　　
上述程序中加框处可选语句为①cur=link[cur][1]
②pre=cur　③link[pre][1]=link[cur][1]则(1)、(2)、(3)处正确的语句顺序是(　　)
A.③②① B.③①②
C.②①③ D.②③①
答案　D
解析　pre与cur表示前后相邻两个指针,link[pre][0]!=link[cur][0]表示相邻两个数据不相等,不相等时,pre与cur都需往后移动,相等时,通过link[pre][1]=link[cur][1]删除cur指向节点,并将cur往后移动。
7.使用列表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]
A.if lst[d[p][0]]>=2:
　　if p==h:
　　　　h=d[h][1]
　　else:
　　　　d[q][1]=d[p][1]
　　　　lst[d[p][0]]-=1
else:
　　q=p
B.if lst[d[p][0]]<2:
　　q=p
elif p==h:
　　lst[d[p][0]]-=1
　　h=d[h][1]
else:
　　lst[d[p][0]] -=1
　　d[q][1]=d[p][1]
C.if lst[d[p][0]]>=2:
　　if p==h:
　　　　h=d[h][1]
　　else:
　　　　d[d[p][1]][1]=q
　　　　lst[d[p][0]]-=1
else:
　　q=d[q][1]
D.if lst[d[p][0]]<2:
　　q=d[p][1]
else:
　　if p!=h:
　　　　d[q][1]=p
　　else:
　　　　h=d[h][1]
　　lst[d[p][0]] -=1
答案　B
解析　遍历链表元素并统计各个元素出现次数(存储在lst数组中)。再次遍历链表,若个数小于2个,则保留,否则删除当前节点p。删除链表节点p分两种情况:若节点p为头节点,修改头指针h为d[h][1];删除非头节点时,修改前驱节点指针域d[q][1]值为节点p的后继d[p][1]。
8.使用列表a模拟链表结构(节点数n>0且n为偶数),每个节点包含数据区域和指针区域,head为头指针。若要计算该链表中两个中点位置节点的数据区域的平均值。实现上述功能的Python程序段如下所示,方框中应填入的正确代码为(　　)
s=f=head
while f!=-1:
　　　　　　　　
num=(num+a[s][0])/2
print("平均值为",num)
A.if a[f][1]==-1:
　　num=a[s][0]
s=a[s][1]
f=a[a[f][1]][1]
B.s=a[s][1]
f=a[a[f][1]][1]
if a[f][1]==-1:
　　num=a[s][0]
C.if a[a[f][1]][1]==-1:
　　num=a[s][0]
s=a[s][1]
f=a[a[f][1]][1]
D.s=a[s][1]
f=a[a[f][1]][1]
if a[a[f][1]][1]==-1:
　　num=a[s][0]
答案　C
解析　指针s和f均从头节点开始遍历链表,s每次向后移动一个节点,f每次向后移动2个节点。以6个节点为例,当条件a[a[f][1]][1]==-1成立,表示节点f已经移动3次,指向第5个节点,再次移动后,f将为-1。此时s指向第3个节点,将该节点值存储到num中,指针s和f向后移动,循环结束后,再累加a[s][0]并计算平均值。
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.②③①
答案　D
解析　考查链表的基本操作。遍历链表,将找到的女演员节点依次链接形成一个单独的链表,同时将女演员节点从原链表删除。操作完成后,原链表就是一个只有男演员的单向链表。指针q、r指向p的前驱和女演员链表的尾节点。将节点从原链表删除前,先要链接到女演员链表尾节点。
10.使用链表结构模拟某校游览路线,链表a中每一个节点包含三个数据,第1个为地点名称,第2个为预计停留时间(单位:分钟),第3个为指向下一个地点指针。可以从多个地点开始浏览,但只能从“南大门”离开,输出显示从各景点进入路线及预计总时间的代码如下。
a=[["校训石",15,2],["教学楼",30,2],["风雨操场",25,5],["科技楼",40,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=s+a[p][1]　④p=a[p][2]
则(1)、(2)、(3)处代码依次为(　　)
A.①③④ B.①④③
C.②③④ D.②④③
答案　D
解析　head列表有3个元素,依次遍历这些元素,当前节点p从每个头指针head[i]开始遍历各条链表的各个节点,累加各个节点的时间值s=s+a[p][1],并向后移动指针p=a[p][2]。
1.通过以下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.①②③
答案　B
解析　本题考查链表的遍历。p为当前节点,从头节点开始遍历链表,将遍历的新节点以头插法的形式重新构建链表。q为新链表的头节点,保存当前节点p的后续索引为tmp,先让新链表的头节点指向新链表的头节点,再将头指针指向p,p从原后续继续遍历原链表。
2.使用列表d模拟链表结构,每个节点包含数据区域和指针区域。如图所示,ha和hb分别为两个链表的头指针,现要找出并返回两个链表相交的起始节点,并输出该节点的数据域值。实现该功能的程序段如下:
d=[]
qa,qb=ha,hb
while qa!=-1:
　　(1)　　　　　
　　qa=data[qa][1]
while qb!=-1:
　　(2)　　　　　
　　　　print(data[qb][0])
　　　　break
　　qb=data[qb][1]
else:
　　print("两个链表不相交")
上述程序段中可选语句为:
①d.append(data[qa][0])　②d.append(qa)
③if qb in d　④if data[qb][0] in d
则(1)(2)处语句依次可为(　　)
A.①③ B.②④
C.①④ D.②③
答案　D
解析　遍历链表a,将整个节点添加到列表d中,在遍历链表b的过程,若当前节点qb在列表d中,则输出第1个相交的节点信息,并结束遍历。
3.使用列表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,遍历到尾节点,节点数量为奇数,遍历完成。
4.利用列表模拟链表,有如下Python程序:
a=[[0,3],[1,2],[-2,-1],[11,4],[2,2],[5,6],[8,1],[10,-1],[6,1],[3,3],[-4,9],[9,2],[4,10]]
maxn=0
for i in range(len(a)):
　　n=0;p=i
　　while p!=-1:
　　　　n+=1;p=a[p][1]
　　if maxn　　　　maxn=n;h=i
p=h;s=0
while p!=-1:
　　if a[p][0]>0:
　　　　s+=a[p][0]
　　p=a[p][1]
程序运行后,变量s的值为(　　)
A.10 B.15
C.20 D.25
答案　C
解析　多个链表共用某一部分节点,类似多条小河汇聚到主干中。程序运行的输出是最长链路中大于0的所有节点的和。最长链路是(12)4>(10)-4>(9)3>(3)11>(4)2>(2)-2,括号内为列表索引,结果为:4+3+11+2=20。
5.有如下Python程序段:
link=[[1,3],[3,2],[7,-1],[5,1],[4,3]]
head=0;n=2
length=1;curr=head
while link[curr][1]!=-1:
　　length+=1
　　curr=link[curr][1]
index=head;count=0
target_index=length-n-1
if target_index < 0:
　　head=link[head][1]
else:
　　while count < target_index:
　　　　count+=1;index=link[index][1]
　　link[index][1]=link[link[index][1]][1]
执行该程序后,link的值是(　　)
A.[[1,3],[3,2],[7,-1],[5,1],[4,3]]
B.[[1,3],[3,2],[7,-1],[5,2],[4,3]]
C.[[1,1],[3,2],[7,-1],[5,1],[4,3]]
D.[[1,3],[3,-1],[7,-1],[5,1],[4,3]]
答案　B
解析　程序的功能是删除链表倒数第n个元素。先采用while循环统计链表元素个数,target_index把原倒数第n个改为正向head开始数的第target_index个节点,再找到第target_index个节点并修改指针跳过该节点。length的值为4,index的值为3,target_index的值为1。执行link[index][1]=link[link[index][1]][1],link[index][1]=link[3][1]=1。link[link[index][1]][1]=link[1][1]=2。因此,link[3][1]=2;修改后,link[3]从[5,1]变为[5,2]。输出结果为[[1,3],[3,2],[7,-1],[5,2],[4,3]]。
6.使用列表d模拟链表结构(节点数大于0),每个节点包含数据区域和指针区域,h为头指针。下列程序段实现了删除数据区域为奇数的节点。
q=p=h=2
while p!=-1:
　　if d[h][0]%2==1:
　　　　(1)　　　　　
　　　　q=p=h
　　elif d[p][0]%2==1:
　　　　(2)　　　　　
　　　　p=d[p][1]
　　else:
　　　　q=p
　　　　p=d[p][1]
划线处可选代码如下:
①h=d[h][1]　②p=d[p][1]
③d[p][1]=d[q][1]　④d[q][1]=d[p][1]
下列选项中,代码顺序正确的是(　　)
A.①③ B.②③
C.①④ D.②④
答案　C
解析　(1)当头节点为奇数时,需要更新头节点。则移动头节点。故h=d[h][1]。(2)当p节点为奇数时候,需要删除该节点,将p的后继节点接到p的前驱结点q的下一个节点指针上。故d[q][1]=d[p][1]。
7.实现在链表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
解析　本题考查链表遍历和最值查找。当前节点从头节点开始遍历,最小值的初值为头节点大小,因此需先移动到下一节点,再与最值进行比较,同时终止遍历的条件是遍历到尾节点马上结束。
8.使用列表d模拟链表结构,每个节点包含数据区域和指针区域,h为头指针。现要从链表中找出节点值相同的连续节点并删除,重复执行以上操作,直到链表中不存在节点值相同的连续节点。删除过程如图所示,实现该功能的Python程序段如下:
p=h
while d[p][1]!=-1 and d[h][1]!=-1:
　　pre=p=h
　　q=d[p][1]
　　while q!=-1 and d[q][0]!=d[p][0]:
　　　　pre=p;p=q;q=d[q][1]
　　while q!=-1 and d[q][0]==d[p][0]:
　　　　　　　　　　　　
　　if p==pre:
　　　　h=q
程序中加框处应填入的语句分别为(　　)
A.d[pre][1]=d[p][1]
q=d[p][1]
B.d[pre][1]=d[q][1]
q=d[q][1]
C.d[p][1]=d[q][1]
q=d[p][1]
D.d[p][1]=d[q][1]
q=d[q][1]
答案　B
解析　循环while q!=-1 and d[q][0]!=d[p][0]的功能是找到相同的2个节点,p指向第1个重复节点,q指向第2个,pre是p的前驱,删除节点p,更新q为d[q][1],继续检查后续节点是否还有重复值。
9.有如下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
答案　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。
10.用Python程序实现删除链表的倒数第n(n不大于链表长度)个节点,如n=2时,链表1→2→3→4→5→6更新为1→2→3→4→6。部分代码如下:
#读入链表存储在列表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]。
11.下列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
答案　D
解析　①处采用头插法新增一个节点,头指针为len(link)-1。②当前节点q从头节点开始,不断地向遍历找到插入data的位置,首先要保证前节点q不为-1,同时满足条件data>link[q][0],当前节点q才向后遍历。③前节点q从头节点开始显示各个节点的值,当q为-1时结束循环。
12.有如下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]
答案　B
解析　原链表a存储一个升序的数列,值依次为1,2,2,2,5,6,9,输入一个数key,先在链表中查找大于key的第一个位置,并将该数插入到链表中,求插入的节点。
13.使用列表d模拟链表结构(节点数大于0),每个节点包含数据区域和指针区域,h为头指针。链表中各节点已按数据区域中数值由小到大排列,如图a所示。现要修改该链表各节点的链接关系,使链表各节点按数据区域中的数值由大到小排列,结果如图b所示。实现该功能的程序段如下。
p=d[h][1];d[h][1]=-1
while p!=-1:
　　q=d[p][1]
　　　　　　　
划线处应填入的正确代码为(　　)
A.h=p
d[p][-1]=h
p=q
B.d[p][1]=h
h=p
p=q
C.p=q
h=p
d[p][-1]=h
D.d[p][1]=h
p=q
h=p
答案　B
解析　第1个节点将成为最后一个节点,当前节点p从第2个节点开始,将第1个节点的指针区域值修改为-1。q暂时保存p的后继,将p节点采用头插法插入新链表,对应的代码为d[p][1]=h,h=p,然后再将p指向q,切换到下一个需要头插的值,如此循环。
14.使用列表a模拟链表结构(节点数大于2),每个节点包含数据区域和指针区域,h为头指针,如图a所示。现修改该链表各节点的链接关系,移除链表中值重复的节点,保留最开始出现的节点,结果如图b所示。实现该功能的程序段如下,方框中应填入的正确代码为(　　)
p=-1;q=head
vis=[]
while q!=-1:
　　　　　　　　
A.if a[q][0] in vis:
　　a[p][1]=a[q][1]
else:
　　vis.append(a[q][0])
　　p=q
q=a[q][1]
B.if a[q][0] in vis:
　　a[p][1]=a[q][1]
　　p=q
　　q=a[q][1]
else:
　　vis.append(a[q][0])
C.if a[q][0] in vis:
　　p=q
else:
　　a[p][1]=a[q][1]
　　vis.append(a[q][0])
q=a[q][1]
D.if a[q][0] in vis:
　　a[p][1]=a[q][1]
else:
　　vis.append(a[q][0])
　　p=q
　　q=a[q][1]
答案　A
解析　题图a链表为:5→2→1→1→5→1,题图b链表为:5→2→1。若a[q][0] in vis成立,采用语句a[p][1]=a[q][1]删除q节点,否则将节点q增加到vis中。C选项操作与要求相反。B和D选项均无法继续正常遍历链表a。
15.接力比赛男女生人数相等,男女队员交替接力,实现该功能的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]]
答案　D
解析　程序借助队列结构完成接力比赛男女队员的交替接力。对队列队首队员的性别和最近进入接力序列队员的性别进行比较,若不同,则将队列队首元素出队,否则继续对a数组进行遍历,若取到符合性别要求的元素则设定为下一趟性别比较的前驱,若性别与前一棒相同时则将该元素的索引置入等待队列。
16.使用列表d模拟链表结构(节点数大于0),每个节点包含数据区域和指针区域,h为头指针(头节点数据为奇数),如图a所示。现需修改该链表各节点的链接关系,使链表各节点数据区域中的数值按奇数在前,偶数在后排列,结果如图b所示。实现该功能的程序段如下,方框中应填入的正确代码为(　　)
p=h;q=d[h][1]
r,tmp=-1,-1
while q!=-1:
　　if d[q][0]%2==0:
　　　　　　　　　　
　　else:
　　　　d[p][1]=q;p=q
　　q=d[q][1]
if d[p][1]==-1 and r!=-1:
　　d[r][1]=-1
d[p][1]=tmp
A.if r==-1:
　　tmp=q
else:
　　d[r][1]=q
r=q
B.if r==-1:
　　tmp=q
else:
　　d[r][1]=q
　　r=q
C.if r==-1:
　　tmp=q
　　r=q
　　d[r][1]=q
r=q
D.if r!=-1:
　　d[r][1]=q
else:
　　tmp=q
　　r=q
答案　A
解析　按奇数在前,偶数在后排列,因语句d[p][1]=tmp可知,tmp为偶数链表的头指针,p为奇数链表的尾指针。头节点数据为奇数,当前指针q从第2个节点开始遍历,若为奇数,采用尾插法插入到新奇数链表的尾部。若为奇数,插入到奇数链表的尾部,指针r和tmp分别为奇数链表的尾和头指针,若尾指针为-1,表示链表为空,更新头指针,否则将插入到尾部,同时更新尾指针。
17.链表a中各节点由数据域和指针构成,并按数据域数值升序排列(头节点数据为奇数),现要修改各节点顺序,按奇数在前升序,偶数在后升序的顺序排列,如图所示。实现该功能的程序段如下,方框中应填入的正确代码是(　　)
a=[[8,1],[9,-1],[6,0],[1,5],[5,2],[2,4]]
p=t=head=3
while a[t][1]!=-1:
　　k=a[t][1]
　　if a[k][0] % 2==1:
　　　　　　　　　　
　　else:
　　　　t=a[t][1]
A.a[t][1]=a[p][1]
a[p][1]=t
p=t
t=k
B.a[t][1]=a[k][1]
a[k][1]=a[p][1]
a[p][1]=k
p=a[p][1]
C.a[p][1]=t
a[t][1]=a[p][1]
p=[p][1]
t=k
D.t=a[t][1]
a[k][1]=a[p][1]
a[p][1]=k
p=k
答案　B
解析　指针t是奇数段的尾节点指针,也是遍历链表的当前指针;指针p是偶数段的尾节点指针,同时a[p][1]维护偶数段链表在奇数段链表后面的链接关系。指针k为t的后继,若a[k][0]为奇数,直接更新奇数段尾指针t。若a[k][0]为偶数,如链表1→2→5→6→8→9,当t遍历到1所在节点,k指向节点,值为2,需先将k节点从原链表中删除(a[t][1]=a[k][1]),为了维护偶数段链接在奇数段后面,将a[p][1]赋值给a[k][1],再将k节点链接到p节点后面(a[p][1]=k),同时更新偶数段尾节点(p=a[p][1])。
18.某无序链表如图a所示,对链表数据进行整理,将所有小于x的节点通过头插的方法逐个放置在链表前面。例如,当x等于3时,对数据进行整理的结果如图b所示:
实现程序代码如下:
a=[[1,1],[4,2],[2,3],[3,4],[5,5],[2,-1]]
x=int(input())
p=head=0;frt=-1
while p!=-1:
　　if a[p][0]　　　　pp=p　#提取出要移动的元素
　　　　　　　　　　
　　else:
　　　　frt=p
　　p=a[p][1]
方框处可填入的代码为(　　)
A.a[pp][1]=head
head=pp
a[frt][1]=a[p][1]
B.a[frt][1]=a[p][1]
a[pp][1]=head
head=pp
C.a[frt][1]=a[p][1]
a[p][1]=head
head=pp
D.a[pp][1]=head
head=pp
a[p][1]=a[frt][1]
答案　B
解析　当找到一个小于x的节点时,需要将其移动到链表的前面。需要更新其next指针指向当前的head,并更新head为新找到的节点的索引。同时更新frt(如果frt不是-1,即之前已经遍历过节点)的next指针,使其跳过当前节点。A选项在更新pp的next指针后,立即更新了head,但是接下来错误地更新了frt的next为p的next,而不是pp。B选项首先更新frt的next(如果frt不是-1),然后移动到了下一个节点,之后正确地将pp的next指向head,并更新了head。C选项现将head节点链接到p节点后,再移动p指针,会重复遍历链表。D选项语句a[p][1]=a[frt][1]在尝试将当前节点p的next指针设置为frt的next,但这并不是想要的操作。
19.使用列表d模拟链表结构(节点数n>0),如图a所示,每个节点包含数据、个数、指针三个数据项,h为头指针,链表节点按“数据”非降序排序。现要对链表节点进行合并,将“数据”相同的节点合并为一个节点,并在节点中记录该数据的个数,如图b所示。实现上述功能的Python程序段如下:
p=h=1
while p!=-1:
　　(1)　　　　　　
　　(2)　　　　　　
　　while q!=-1 and d[q][0]==d[p][0]:
　　　　q=d[q][2]
　　　　c+=1
　　d[p][1]=c
(3)　　　　　　
(4)　　　　　　
方框处可选代码有:
①q=p　②q=d[p][2]　③c=1　④c=0　⑤d[p][2]=q　⑥d[p][2]=d[q][2]　⑦p=d[p][2]　⑧p=q
则(1)(2)(3)(4)中填入代码顺序正确的是(　　)
A.①④⑥⑦ B.②③⑤⑧
C.②③⑥⑦ D.①③⑤⑧
答案　B
解析　本题考查的是链表遍历和节点的删除等操作。链表节点按“数据”非降序排序,节点p从头节点开始遍历链表,(1)指针q指向p的下一个节点,若d[q][0]等于d[p][0],变量c增加1,q不断地向后移动。变量c记录相同节点的数量(至少为1个),因此(2)需对c赋初值为1。将相同的节点合并为一个节点,因此(3)将p的指针直接指向q,跳过所有重复节点。接着语句(4)p=q处理下一个节点。4.6　链　表
学习目标　
1.掌握链表的概念和链表的遍历方法。
2.掌握链表头节点、尾节点的插入和删除操作。
3.掌握链表除头尾节点外的其他节点的插入和删除操作。
(2024年6月浙江选考)使用列表d模拟链表结构(节点数n>0),如图a所示,每个节点包含数据区域和指针区域,h为头指针。现要按链表顺序将这n个节点中的数据依次存放到d[0][0]、d[1][0]…d[n-1][0]中,最终保持节点链接关系不变,结果如图b所示。实现上述功能的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
　　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]
　　链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表每个节点的结构是相同的,由数据区域和指针区域组成,其中指针区域指向下一个节点的索引。链表的访问必须从头节点开始,因此头指针是链表必不可少的元素。在数组中删除某个节点,往往需把该节点后面的值往前移,时间复杂度为线性阶O(n)。链表节点的删除分为头节点的删除和其他节点的删除,头节点的删除只要移动头指针到下一节点,即head=a[head][1]即可,其他节点的删除,只要修改该节点的前驱节点的指针区域值为该节点的后继节点索引即可,时间复杂度为常量阶O(1)。
例1 有如下链表操作Python程序段:
a=[[2,2],[4,4],[8,3],[3,-1],[5,0],[1,1]]
head=5
q=random.randint(0,5)
while head!=q:
　　t=head
　　head=a[head][1]
　　a[t][1]=a[q][1]
　　a[q][1]=t
#按链表顺序输出元素,代码略
执行上述程序后,下列输出结果不可能的是(　　)
A.145283 B.382541
C.825413 D.254813
变式1 有如下Python程序段:
a=[4,5,3]
d=[[3,"A",2],[6,"B",0],[3,"C",1]]
head=1;p=2
n=3;ans=""
i=0
while n>0 and i　　q=d[p][2]
　　if d[q][0]>a[i]:
　　　　d[q][0]-=a[i]
　　　　i+=1
　　else:
　　　　ans+=d[q][1]
　　　　a[i]-=d[q][0]
　　　　d[p][2]=d[q][2]
　　　　n-=1
　　p=d[p][2]
执行该程序段后,ans的值是(　　)
A."ABC" B."ACB"
C."BAC" D."CBA"
例2 使用列表d模拟链表结构(节点数大于0),每个节点包含数据区域和指针区域,h为头指针。链表中各节点已按数据区域中数值的绝对值由小到大排列,如图a所示。现要修改该链表各节点的链接关系,使链表各节点按数据区域中的数值由小到大排列,结果如图b所示。实现该功能的程序段如下,方框中应填入的正确代码为(　　)
t=h
p=d[h][1]
while p!=-1:
　　q=d[p][1]
　　　　　　　　
　　p=q
d[t][1]=-1
A.if d[p][0]>0:
　　d[q][1]=p
　　d[t][1]=q
else:
　　d[h][1]=q
　　h=p
B.if d[p][0]>0:
　　d[t][1]=q
　　t=q
else:
　　h=p
　　d[p][1]=t
C.if d[p][0]>0:
　　d[t][1]=p
　　t=p
else:
　　d[p][1]=h
　　h=p
D.if d[p][0]>0:
　　d[t][1]=q
　　d[q][1]=p
else:
　　d[p][1]=h
　　h=q
变式2 使用列表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]
1.采用Python二维列表模拟链表,
a=[['A',1],['B',2],['C',3],['D',4],['E',5],['F',-1]]
head=0;p=a[head][1]
a[head][1]=-1
while p!=-1:
　　p=a[p][1]
　　if p==-1:
　　　　break
　　t=a[p][1];a[p][1]=head
　　head=p;p=t
执行以上程序后,以head为首的链表结构为(　　)
A.E→C→A B.A→C→E
C.B→D→F D.F→D→B
2.将链表中的奇数节点和偶数节点分别排在一起,奇数节点和偶数节点的相对顺序不变。如原始链表为,新链表为。部分程序如下:
#读入链表,存储在列表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.③①④②
3.某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
4.链表中有两个不同节点指向同一个节点,构成一个环,编写程序检验链表指针设置是否合理的代码如下,请将空白处补充完整
#将链表数据存储在列表d中,每个节点第1个元素为值,第2个元素为指针
slow,fast=head,head
while ①　　　　　　:
　　slow=d[slow][1]
　　fast=d[d[fast][1]][1]
　　if ②　　　　　　:
　　　　print("链表中有环,指针设置不合理!")
　　　　break
　　else:
　　　　print("链表指针设置合理!")(　　)
A.①fast=-1 and a[fast][1]=-1
②fast!=slow
B.①fast=-1 and a[fast][1]=-1
②fast==slow
C.①fast=-1 or a[fast][1]=-1
②fast!=slow
D.①fast=-1 or a[fast][1]=-1
②fast==slow
5.有如下程序段:
people=[[1,1],[2,2],[3,3],[4,4],[5,5],[6,0]]
k=2;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])
运行该程序段,输出的结果为(　　)
A.3 B.5
C.6 D.2
6.删除升序链表link中重复的数据,仅保留下不重复的数据的部分Python程序段如下:
link=[[2,1],[2,2],[2,3],[5,4],[6,-1]]
pre=head=0
cur=link[pre][1]
while cur!=-1:
　　if link[pre][0]!=link[cur][0]:
　　　　(1)　　　　　　
　　else:
　　　　(2)　　　　　　
　　(3)　　　　　　
上述程序中加框处可选语句为①cur=link[cur][1]
②pre=cur　③link[pre][1]=link[cur][1]则(1)、(2)、(3)处正确的语句顺序是(　　)
A.③②① B.③①②
C.②①③ D.②③①
7.使用列表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]
A.if lst[d[p][0]]>=2:
　　if p==h:
　　　　h=d[h][1]
　　else:
　　　　d[q][1]=d[p][1]
　　　　lst[d[p][0]]-=1
else:
　　q=p
B.if lst[d[p][0]]<2:
　　q=p
elif p==h:
　　lst[d[p][0]]-=1
　　h=d[h][1]
else:
　　lst[d[p][0]] -=1
　　d[q][1]=d[p][1]
C.if lst[d[p][0]]>=2:
　　if p==h:
　　　　h=d[h][1]
　　else:
　　　　d[d[p][1]][1]=q
　　　　lst[d[p][0]]-=1
else:
　　q=d[q][1]
D.if lst[d[p][0]]<2:
　　q=d[p][1]
else:
　　if p!=h:
　　　　d[q][1]=p
　　else:
　　　　h=d[h][1]
　　lst[d[p][0]] -=1
8.使用列表a模拟链表结构(节点数n>0且n为偶数),每个节点包含数据区域和指针区域,head为头指针。若要计算该链表中两个中点位置节点的数据区域的平均值。实现上述功能的Python程序段如下所示,方框中应填入的正确代码为(　　)
s=f=head
while f!=-1:
　　　　　　　　
num=(num+a[s][0])/2
print("平均值为",num)
A.if a[f][1]==-1:
　　num=a[s][0]
s=a[s][1]
f=a[a[f][1]][1]
B.s=a[s][1]
f=a[a[f][1]][1]
if a[f][1]==-1:
　　num=a[s][0]
C.if a[a[f][1]][1]==-1:
　　num=a[s][0]
s=a[s][1]
f=a[a[f][1]][1]
D.s=a[s][1]
f=a[a[f][1]][1]
if a[a[f][1]][1]==-1:
　　num=a[s][0]
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.②③①
10.使用链表结构模拟某校游览路线,链表a中每一个节点包含三个数据,第1个为地点名称,第2个为预计停留时间(单位:分钟),第3个为指向下一个地点指针。可以从多个地点开始浏览,但只能从“南大门”离开,输出显示从各景点进入路线及预计总时间的代码如下。
a=[["校训石",15,2],["教学楼",30,2],["风雨操场",25,5],["科技楼",40,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=s+a[p][1]　④p=a[p][2]
则(1)、(2)、(3)处代码依次为(　　)
A.①③④ B.①④③
C.②③④ D.②④③
1.通过以下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.①②③
2.使用列表d模拟链表结构,每个节点包含数据区域和指针区域。如图所示,ha和hb分别为两个链表的头指针,现要找出并返回两个链表相交的起始节点,并输出该节点的数据域值。实现该功能的程序段如下:
d=[]
qa,qb=ha,hb
while qa!=-1:
　　(1)　　　　　
　　qa=data[qa][1]
while qb!=-1:
　　(2)　　　　　
　　　　print(data[qb][0])
　　　　break
　　qb=data[qb][1]
else:
　　print("两个链表不相交")
上述程序段中可选语句为:
①d.append(data[qa][0])　②d.append(qa)
③if qb in d　④if data[qb][0] in d
则(1)(2)处语句依次可为(　　)
A.①③ B.②④
C.①④ D.②③
3.使用列表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
4.利用列表模拟链表,有如下Python程序:
a=[[0,3],[1,2],[-2,-1],[11,4],[2,2],[5,6],[8,1],[10,-1],[6,1],[3,3],[-4,9],[9,2],[4,10]]
maxn=0
for i in range(len(a)):
　　n=0;p=i
　　while p!=-1:
　　　　n+=1;p=a[p][1]
　　if maxn　　　　maxn=n;h=i
p=h;s=0
while p!=-1:
　　if a[p][0]>0:
　　　　s+=a[p][0]
　　p=a[p][1]
程序运行后,变量s的值为(　　)
A.10 B.15
C.20 D.25
5.有如下Python程序段:
link=[[1,3],[3,2],[7,-1],[5,1],[4,3]]
head=0;n=2
length=1;curr=head
while link[curr][1]!=-1:
　　length+=1
　　curr=link[curr][1]
index=head;count=0
target_index=length-n-1
if target_index < 0:
　　head=link[head][1]
else:
　　while count < target_index:
　　　　count+=1;index=link[index][1]
　　link[index][1]=link[link[index][1]][1]
执行该程序后,link的值是(　　)
A.[[1,3],[3,2],[7,-1],[5,1],[4,3]]
B.[[1,3],[3,2],[7,-1],[5,2],[4,3]]
C.[[1,1],[3,2],[7,-1],[5,1],[4,3]]
D.[[1,3],[3,-1],[7,-1],[5,1],[4,3]]
6.使用列表d模拟链表结构(节点数大于0),每个节点包含数据区域和指针区域,h为头指针。下列程序段实现了删除数据区域为奇数的节点。
q=p=h=2
while p!=-1:
　　if d[h][0]%2==1:
　　　　(1)　　　　　
　　　　q=p=h
　　elif d[p][0]%2==1:
　　　　(2)　　　　　
　　　　p=d[p][1]
　　else:
　　　　q=p
　　　　p=d[p][1]
划线处可选代码如下:
①h=d[h][1]　②p=d[p][1]
③d[p][1]=d[q][1]　④d[q][1]=d[p][1]
下列选项中,代码顺序正确的是(　　)
A.①③ B.②③
C.①④ D.②④
7.实现在链表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.②④
8.使用列表d模拟链表结构,每个节点包含数据区域和指针区域,h为头指针。现要从链表中找出节点值相同的连续节点并删除,重复执行以上操作,直到链表中不存在节点值相同的连续节点。删除过程如图所示,实现该功能的Python程序段如下:
p=h
while d[p][1]!=-1 and d[h][1]!=-1:
　　pre=p=h
　　q=d[p][1]
　　while q!=-1 and d[q][0]!=d[p][0]:
　　　　pre=p;p=q;q=d[q][1]
　　while q!=-1 and d[q][0]==d[p][0]:
　　　　　　　　　　　　
　　if p==pre:
　　　　h=q
程序中加框处应填入的语句分别为(　　)
A.d[pre][1]=d[p][1]
q=d[p][1]
B.d[pre][1]=d[q][1]
q=d[q][1]
C.d[p][1]=d[q][1]
q=d[p][1]
D.d[p][1]=d[q][1]
q=d[q][1]
9.有如下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
10.用Python程序实现删除链表的倒数第n(n不大于链表长度)个节点,如n=2时,链表1→2→3→4→5→6更新为1→2→3→4→6。部分代码如下:
#读入链表存储在列表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.②①③
11.下列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
12.有如下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]
13.使用列表d模拟链表结构(节点数大于0),每个节点包含数据区域和指针区域,h为头指针。链表中各节点已按数据区域中数值由小到大排列,如图a所示。现要修改该链表各节点的链接关系,使链表各节点按数据区域中的数值由大到小排列,结果如图b所示。实现该功能的程序段如下。
p=d[h][1];d[h][1]=-1
while p!=-1:
　　q=d[p][1]
　　　　　　　
划线处应填入的正确代码为(　　)
A.h=p
d[p][-1]=h
p=q
B.d[p][1]=h
h=p
p=q
C.p=q
h=p
d[p][-1]=h
D.d[p][1]=h
p=q
h=p
14.使用列表a模拟链表结构(节点数大于2),每个节点包含数据区域和指针区域,h为头指针,如图a所示。现修改该链表各节点的链接关系,移除链表中值重复的节点,保留最开始出现的节点,结果如图b所示。实现该功能的程序段如下,方框中应填入的正确代码为(　　)
p=-1;q=head
vis=[]
while q!=-1:
　　　　　　　　
A.if a[q][0] in vis:
　　a[p][1]=a[q][1]
else:
　　vis.append(a[q][0])
　　p=q
q=a[q][1]
B.if a[q][0] in vis:
　　a[p][1]=a[q][1]
　　p=q
　　q=a[q][1]
else:
　　vis.append(a[q][0])
C.if a[q][0] in vis:
　　p=q
else:
　　a[p][1]=a[q][1]
　　vis.append(a[q][0])
q=a[q][1]
D.if a[q][0] in vis:
　　a[p][1]=a[q][1]
else:
　　vis.append(a[q][0])
　　p=q
　　q=a[q][1]
15.接力比赛男女生人数相等,男女队员交替接力,实现该功能的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]]
16.使用列表d模拟链表结构(节点数大于0),每个节点包含数据区域和指针区域,h为头指针(头节点数据为奇数),如图a所示。现需修改该链表各节点的链接关系,使链表各节点数据区域中的数值按奇数在前,偶数在后排列,结果如图b所示。实现该功能的程序段如下,方框中应填入的正确代码为(　　)
p=h;q=d[h][1]
r,tmp=-1,-1
while q!=-1:
　　if d[q][0]%2==0:
　　　　　　　　　　
　　else:
　　　　d[p][1]=q;p=q
　　q=d[q][1]
if d[p][1]==-1 and r!=-1:
　　d[r][1]=-1
d[p][1]=tmp
A.if r==-1:
　　tmp=q
else:
　　d[r][1]=q
r=q
B.if r==-1:
　　tmp=q
else:
　　d[r][1]=q
　　r=q
C.if r==-1:
　　tmp=q
　　r=q
　　d[r][1]=q
r=q
D.if r!=-1:
　　d[r][1]=q
else:
　　tmp=q
　　r=q
17.链表a中各节点由数据域和指针构成,并按数据域数值升序排列(头节点数据为奇数),现要修改各节点顺序,按奇数在前升序,偶数在后升序的顺序排列,如图所示。实现该功能的程序段如下,方框中应填入的正确代码是(　　)
a=[[8,1],[9,-1],[6,0],[1,5],[5,2],[2,4]]
p=t=head=3
while a[t][1]!=-1:
　　k=a[t][1]
　　if a[k][0] % 2==1:
　　　　　　　　　　
　　else:
　　　　t=a[t][1]
A.a[t][1]=a[p][1]
a[p][1]=t
p=t
t=k
B.a[t][1]=a[k][1]
a[k][1]=a[p][1]
a[p][1]=k
p=a[p][1]
C.a[p][1]=t
a[t][1]=a[p][1]
p=[p][1]
t=k
D.t=a[t][1]
a[k][1]=a[p][1]
a[p][1]=k
p=k
18.某无序链表如图a所示,对链表数据进行整理,将所有小于x的节点通过头插的方法逐个放置在链表前面。例如,当x等于3时,对数据进行整理的结果如图b所示:
实现程序代码如下:
a=[[1,1],[4,2],[2,3],[3,4],[5,5],[2,-1]]
x=int(input())
p=head=0;frt=-1
while p!=-1:
　　if a[p][0]　　　　pp=p　#提取出要移动的元素
　　　　　　　　　　
　　else:
　　　　frt=p
　　p=a[p][1]
方框处可填入的代码为(　　)
A.a[pp][1]=head
head=pp
a[frt][1]=a[p][1]
B.a[frt][1]=a[p][1]
a[pp][1]=head
head=pp
C.a[frt][1]=a[p][1]
a[p][1]=head
head=pp
D.a[pp][1]=head
head=pp
a[p][1]=a[frt][1]
19.使用列表d模拟链表结构(节点数n>0),如图a所示,每个节点包含数据、个数、指针三个数据项,h为头指针,链表节点按“数据”非降序排序。现要对链表节点进行合并,将“数据”相同的节点合并为一个节点,并在节点中记录该数据的个数,如图b所示。实现上述功能的Python程序段如下:
p=h=1
while p!=-1:
　　(1)　　　　　　
　　(2)　　　　　　
　　while q!=-1 and d[q][0]==d[p][0]:
　　　　q=d[q][2]
　　　　c+=1
　　d[p][1]=c
(3)　　　　　　
(4)　　　　　　
方框处可选代码有:
①q=p　②q=d[p][2]　③c=1　④c=0　⑤d[p][2]=q　⑥d[p][2]=d[q][2]　⑦p=d[p][2]　⑧p=q
则(1)(2)(3)(4)中填入代码顺序正确的是(　　)
A.①④⑥⑦ B.②③⑤⑧
C.②③⑥⑦ D.①③⑤⑧

展开更多......

收起↑