资源简介

浙教版（2019）选修一2.2链表同步练习
学校:___________姓名：___________班级：___________考号：___________
一、选择题
1．某Python程序如下：
a=[[3,2],[2,3],[7,1],[1,0]]
p=head=0
while a[p][1]!=head:
print(a[p][0],end='->')
p=a[p][1]
print(a[p][0])
程序运行后，输出的结果是（ ）
A．3->7->2->1 B．3->2->7->1 C．1->7->3->2 D．3->7->1->2
2．有如下图所示的单向链表：
从头指针head指向的节点开始查找数据元素“5”，并删除该节点，下列说法正确的是（ ）
A．共需查找3次 B．删除数据元素“5”的节点，后续节点需要移动3次
C．头指针head将指向数据元素“7”的节点 D．操作完成后，链表中数据元素的个数为6个
3．使用链表结构模拟某校游玩路线，链表a中每一个节点包含三个数据，第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=s+a[p][1] ④p=a[p][2]
则（1)、(2)、(3）处代码依次为（ ）
A．①③④ B．①④③ C．②③④ D．②④③
4．使用链表结构模拟某景区游玩路线，链表a中每一个节点包含三个数据，第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=s+a[p][1] ④p=a[p][2]
则(1)，(2)，(3)处代码依次为（ ）
A．①③④ B．①④③ C．②③④ D．②④③
5．利用列表模拟某单向非循环链表a(其中可能存在已被删除的节点），下列程序运行完毕后，变量p肯定表示尾节点的节点位置的是（　　）
A． B． C． D．
6．下列Python程序段的功能是在链表link1中删除数据为key的所有节点，link1链表中的每个节点由一个数据域和一个指针域组成。
#建立链表 link1，代码略
key=int(input("输入要删除的数据："))
head=0
while link1[head][0]==key and head!=- 1:
head=link1[head][1]
p=q=head
if head==- 1:
print("全部数据删除")
else:
q=link1[q][1]
while ① :
if link1[q][0]==key:
②
else:
p=link1[p][1]
q=link1[q][1]
则划线①②处的代码分别为（　　）
A．①link1[q][1]!=- 1 ②link1[p][1]=link1[q][1]
B．①link1[q][1]!=- 1 ②link1[q][1]=link1[p][1]
C．①q!=- 1 ②link1[q][1]=link1[p][1]
D．①q!=- 1 ②link1[p][1]=link1[q][1]
7．有如下Python程序段，其功能是将一个单向链表转换成原链表的逆序链表：
lst=[[15,4],[30,-1],[8,0],[5,2],[19,1]]
head=3
p=head
q=-1
while p!=-1:
tmp=lst[p][1]
head=q
上述程序段执行后lst内容变为[[15,2],[30,4],[8,3],[5,-1],[19,0]]。方框处可选代码有：①q=p ②p=tmp ③lst[p][1]=q，则方框处的语句依次为（ ）
A．①②③ B．②③① C．③①② D．③②①
8．寻宝游戏中通过一个线索找到下一个线索，最好用下列数据组织形式中的（ ）来表示。
A．数组 B．链表 C．栈 D．队列
9．王老师用链表模拟某次比赛中运动员的出场次序，运动员号码存储如下：a=[[“056”，4]，[“134”，-1]，[“215”，5]，[“098”，0]，[“144”，2]，[“024”，1]]。假设head=3，小明同学的号码是“215”，则他的出场次序是（ ）
A．2 B．4 C．5 D．6
10．使用列表模拟单向链表，链表中p节点的a[p][0]存储数据，a[p][1]存储其后继节点的指针。编写Python程序删除链表中所有的偶数项（头节点为该链表的第1项），部分代码如下：
p=head #head指向该链表的头节点
while p!=-1:
q=a[p][1] if （1） :
（2）
p=a[p][1]
上述程序段划线处可选语句为
①q!=-1 ②a[q][1]!=-1 ③a[q][1]=a[p][1] ④a[p][1]=a[q][1]
则（1）（2）处填入的语句依次为（ ）
A．①③ B．①④ C．②③ D．②④
11．用Python程序实现删除链表的倒数第n（n不大于链表长度）个节点，如n=2时，链表
更新为。
部分代码如下：
# 读入链表存储在列表s中，head存储链表的头节点，代码略
n=int(input())
pl=p2=head
while p2!=-1:
if n>=0：
(1) n -= l
else:
(2) p2 = s[p2] [1]
if p1 == head :
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．②①③
12．现采用新的排队方案为小明、小红、小丽、小辉四人排队，
Python程序段如下：
linklist=[["小明",1],["小红",2],["小丽",3],["小辉",-1]]
def reset(head):
if linklist[head][1]==- 1 or head==- 1:
return head
else:
new_head=reset(linklist[head][1])
linklist[linklist[head][1]][1]=head
linklist[head][1]=- 1
return new head
p=h=reset(0)
while p!=- 1:
print(linklist[p][0],end="")
p=linklist[p][1]
执行该程序段后，输出的结果是（ ）
A．小明小红小丽小辉 B．小明小辉小丽小红
C．小辉小丽小红小明 D．小明小丽小红小辉
13．有如下 Python 程序段
def bianli(head):
pt = head
while pt != -1:
print(data[pt][0],data[pt][1],"->",end='')
pt = data[pt][1]
print()
data = [['A',1],['B',2],['C',3],['D',-1]]
head = 0
bianli(head) #遍历链表，显示初始状态为“A 1 ->B 2 ->C 3 ->D -1 ->”
qt = head
pt = data[qt][1]
bianli(head) #遍历链表，显示最终状态为“A 2 ->C 1 ->B 3 ->D -1 ->”
执行该程序段后，链表遍历结果由初始状态变为最终状态，上述程序段中方框处可选代码为：
①data[data[qt][1]][1] = pt
②data[qt][1] = data[pt][1]
③data[pt][1] = data[data[pt][1]][1]
则方框处代码的正确顺序是（ ）
A．①②③ B．①③② C．②①③ D．②③①
14．在Python中可以使用列表模拟单向链表，如链表中的节点p，a[p] [0]存储p节点的数据，a[p][1]存储p指向后继节点的指针。若要在p节点之后插入新的节点x（x作为p的新后继节点），需要执行的语句是（ ）
A．a[p][1]=x; a[x][1]=a[p][1] B．a[x][1]=a[p][1]; a[p][1]=x
C．a[p][0]=x; a[x][0]=a[p][0] D．a[x][0]=a[p][0]; a[p][0]=x
15．一头指针 head=2 的单向链表 L=[[30,4], [10,-1], [20,0], [15,1],[21,3]]通过以下 Python 程序段，转换为原链表的逆序链表，即头指针 head=1，L=[[30,2], [10,3], [20,-1], [15,4],[21,0]]。
q=-1
p=head #head 为原链表头指针
while p!=-1 :
tmp=L[p][1]
head=q
上述程序段中方框处可选的语句为：①p=tmp ②q=p ③L[p][1]=q
则方框处语句依次为( )
A．③②① B．③①② C．①③② D．①②③
试卷第1页，共3页
试卷第1页，共3页
参考答案：
1．A
【详解】本题考查的是链表相关知识。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。a[p][1]是链表的指针，a=[[3,2],[2,3],[7,1],[1,0]]，故输出：3->7->2->1。选项A正确。
2．D
【详解】本题考查的知识点是链表数据结构。从头指针head指向的节点开始查找数据元素“5”，“5”是第4个元素，共查找4次。删除节点时，找到要删除的节点后，修改其前一个节点的指针域，使其指向要删除节点的下一个节点，后续节点不存在移动。由于删除的是第三个节点，因此头指针head将指向第四个节点，即数据元素为“1”的节点。操作完成后，链表中数据元素的个数为6个。故答案为D选项。
3．D
【详解】本题考查的是链表。head列表里存放的是开始景点的指针。p表示头结点，故第一空应为：p=head[i] ；由于内循环开始前已经把头结点的时间存储到s中，故内循环要先指向下一个指针，再累加时间，故第二空应为：p=a[p][2]，第三空应为：s=s+a[p][1]。选项D正确。
4．D
【详解】本题考查链表结构。链表结构模拟景区游玩路线的程序中，需要注意如下的逻辑：(1)处：应该设置当前节点的指针p为head[i]，表示第i个大门的开始路线，即p=head[i]。（2）（3）处注意s的初值为a[p][1]，同时最后一个节点取不到，所以应先跳入下一节点再统计当前时间的和，所以答案为②④③，故答案为D选项。
5．B
【详解】本题主要考查链表数据结构的应用。选项A执行完，变量p表示尾节点的指针域，即-1；选项B执行完，变量p表示尾节点的节点位置；选项C执行完，变量p表示尾节点的前一个节点位置；选项D中，如果存在已被删除的节点，则变量p不一定表示尾节点的节点位置，故本题选B选项。
6．D
【详解】本题主要考查链表的操作。通过遍历链表来寻找key，故第一空while循环条件是q!=-1。如果link1[q][0]==key，则删除key所在的节点，p是q的上一个节点，则通过p的指针域指向q的指针域以实现删除q节点，故第二空填link1[p][1]=link1[q][1]，故本题选D选项。
7．C
【详解】本题主要考查Python程序的调试。 p=head=3，即指向的元素是[5,2]，也就是链表中最小的一个元素，则逆序后就是最后一个元素，因此其指针域应是-1，此时q=-1，因此第一个语句是lst[p][1]=q，原指针域已经保存在tmp中了，即tmp=lst[p][1]。接下来就是更新q的值为p=3，即下一个元素指向[5,-1]。更新p的值为tmp=2，即接下来处理倒数第二小元素[8,0]，其余元素依次类推，故方框处的语句依次为③①②，故本题选C选项。
8．B
【详解】本题考查的是链表相关知识。链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。寻宝游戏中通过一个线索找到下一个线索，最好用链表来表示，故选B选项。
9．B
【详解】本题主要考查链表数据结构的操作。假设head=3，则出场顺序依次是“098”→“056”→“144”→“215”→“024”→“134”，小明同学的号码是“215”，则他的出场次序是4，故本题选B选项。
10．B
【详解】本题主要考查链表数据结构及Python程序实现。头节点为该链表的第1项，p的初值指向head，q为p的下一个节点，因此每次删除q节点即可，删除之前需要判断q是否为-1，故if判断条件是q!=-1，删除q节点的方法是，p的后继节点指向q的后继节点，即a[p][1]=a[q][1]，选项B符合题意，故选B。
11．D
【详解】本题主要考查Python程序的综合应用。①第一空更新p2的位置，即指向下一个节点，p2=s[p2][1]，同时n递减1。②当n<0时，此时需要更新p1的位置为p1=s[p1][1]，同时p2也指向下一个节点，当p2=-1时，p1的位置为删除节点的前一个节点。③如果p1!=head，则p1需要跳过删除的节点，即s[p1][1]=s[s[p1][1]][1]，故本题选D选项。
12．C
【详解】本题主要考查链表数据结构及Python程序实现。分析程序可知，reset(head)函数实现将列表linklist逆着连接起来，linklist=[["小明",1],["小红",2],["小丽",3],["小辉",-1]]，因此执行该程序段后，输出的结果是小辉小丽小红小明，故本题选C选项。
13．D
【详解】本题主要考查链表及其Python程序实现。本程序考查的是链表的重新链接，程序实现的效果是 A 1 ->B 2 ->C 3 ->D -1 ->，变为 A 2->C 1 ->B 3 ->D -1 ->，qt 指前一指针，pt 指后一指针，故‘A’要指向‘C’,‘B’要指向‘D’,然后‘C’要指向‘B’，即正确的顺序是，故本题选D选项。
14．B
【详解】本题主要考查链表数据结构。若要在p节点之后插入新的节点x（x作为p的新后继节点），则x的指针域指向p的下一个节点，即a[x][1]=a[p][1]。其次将x与p连接起来，即p的指针域指向x，即a[p][1]=x，故本题选B选项。
15．A
【详解】本题主要考查链表及Python程序实现。因为是逆序链表，q的初值为-1，故L[p][1]即p的下一个节点指向q，③L[p][1]=q。由题干单项链表可知，接下来更新q的值为p即②q=p，p的值为tmp①p=tmp，故本题选A选项。
答案第1页，共2页
答案第1页，共2页

展开更多......

收起↑