2.2 链表的应用练习　2021-2022学年高中信息技术浙教版（2019）选修1（含答案）

2.2 链表的应用
姓名： 班级：
1. 下列关于链表的说法，正确的是（ ）
A.链表中的各元素在存储空间中的位置必须是连续的
B.链表中的表头元素一定存储在其他元素的前面
C.链表中的各元素在存储空间中的位置不一定连续，且各元素存储顺序也是任意的
D.链表一旦创建好后，它的占用空间就是固定的
2. 在一个包含n（n>1）个节点的单链表上，没有头和尾两个指针，下列操作需要遍历多个节点的是（ ）
A.删除该链表中的第一个节点 B.删除该链表中的最后一个节点
C.在该链表第一个节点前插入一个新节点 D.在该链表最后一个节点后插入一个新节点
3. 用python的二维列表来模拟单向链表，已知列表a=[[“红”,1], [“橙”,2], [“绿”,3],[“青”,-1]]，则在删除节点“橙”之后，列表a的值为（ ）
A. [[“红”,1],[“绿”,3],[“青”,-1]]
B. [[“红”,1],[“绿”,2],[“青”,-1]]
C. [[“红”,1], [“橙”,2], [“绿”,3],[“青”,-1]]
D. [[“红”,2], [“橙”,2], [“绿”,3],[“青”,-1]]
4. 使用python的二维列表来模拟单向链表，已知列表a=[[“红”,1]，[“绿”,2],[“青”,-1]]，则在节点“红”和节点“绿”之间插入节点“橙”之后，列表a的值为（ ）
A. [[“红”,3],[“绿”,2],[“青”,-1],[“橙”,1]]
B. [[“红”,1],[“绿”,2],[“青”,-1],[“橙”,3]]
C. [[“红”,1],[“橙”,3],[“绿”,2],[“青”,-1]]
D. [[“红”,1],[“橙”,2],[“绿”,3],[“青”,-1]]
5.下列代码创建了一个拥有4个节点的双链表a:
a=[[2,2,3],[8,3,-1],[0,-1,0],[4,0,1]]
head=2
则其头节点和尾节点数据域的值分别为（ ）
A.2和4 B.0和8 C.8和0 D.3和-1
5.有如下代码段：
a=[[2,2,5],[8,0,5],[0,- 1,0],[1,- 1,2],[5,5,- 1],[3,0,- 1]]
head=2
则该双向链表a的节点数量为( )
A.3 B.4 C.5 D.6
6.有如下python程序段：
a=[[7,1],[8,2],[9,-1],[6,0]]
head=3
head=a[head][1]
则程序执行后，链表a有几个节点（ ）
A.1 B.2 C.3 D.4
7.有如下python程序段，表示一个链表及操作：
a=[[5,-1],[9,4],[7,3],[2,1],[6,0]]
head=2
p=head
b=[ ]
While a[p][1]!=-1:
b.append(a[p][0])
p=a[p][1]
b.append(a[p][0])
print(b)
程序执行后，输出的结果为（ ）
A.[7,2,9,6,5,5] B.[5,9,7,2,6] C.[7,2,9,6,5] D.[2,9,6]
8.有如下python程序段：
a=[[1,1],[2,2],[3,3],[4,-1]]
head=0
cur=a[head][1]
a[head][1]=-1
while cur!=-1:
next_=a[cur][1]
a[cur][1]=head
head,cur=cur,next_
则程序执行后，a的值为（ ）
A.[[1,1],[2,2],[3,3],[4,-1]] B.[[1,-1],[2,0],[3,1],[4,2]]
C.[[4,1],[3,2],[2,3],[1,-1]] D.[[4,-1],[3,0],[2,1],[1,2]]
9.有如下python程序段：
a=[[4,2,-1],[0,-1,2],[2,1,0]]
head=1
a.append([8,-1,-1])
p=head
while a[p][2]!=-1:
p=a[p][2]
a[p][2]=len(a)-1
a[-1][1]=p
上述代码段中的二维列表a看作是一个双向链表，则执行上述语句后，双向链表的结构可以表示为（ ）
A.4->0->2->8 B. 8->4->0->2
C. 0->2->4->8 D. 8->0->2->4
10.有如下python程序段：
a=[[2,2,3],[8,3,-1],[0,-1,0],[4,0,1]]
head=2
if a[head][2]!=-1:
a[a[head][2]][1]=-1
head=a[head][2]
上述代码段中的二维列表a看作是一个双向链表，则执行上述语句后，双向链表的结构可以表示为（ ）
A. 0->2->4->8 B. 0->2->4 C. 0->2->8 D. 2->4->8
11、十二生肖，又称属相，是中国与十二地支相配、表示人出生年份的十二种动物，包括“鼠牛虎兔龙蛇马羊猴鸡狗猪”，小美创建了一个单向链表，每个节点存储一个生肖名称，可是他漏掉了生肖鼠、生肖马和生肖猪。下列代码能将漏掉的三个生肖添加到链表中，请在划线处填入合适的代码。
a=[[“牛”,1],[“虎”,2],[“兔”,3],[“龙”,4],[“蛇”,5],[“羊”,6],[“猴”,7],[“鸡”,8],[“猪”,9]]
head=0
#从链表头部插入存储生肖鼠的新节点
node=[“鼠”，head]
a.append(node)
head=
此时链表a=
#从链表中部插入存储生肖马的新节点
new="马"
p=head
while a[p][0]!= :
p=a[p][1]
a.append([new, ]])
a[p][1]=len(a)-1
print(a)此时链表a=
#从链表尾部插入存储生肖猪的新节点
node=
a.append(node)
p=head
while a[p][1]!=-1:
p=
a[p][1]=
此时链表a=
2.2 链表的应用
姓名： 班级：
1. 下列关于链表的说法，正确的是（ c ）
A.链表中的各元素在存储空间中的位置必须是连续的
B.链表中的表头元素一定存储在其他元素的前面
C.链表中的各元素在存储空间中的位置不一定连续，且各元素存储顺序也是任意的
D.链表一旦创建好后，它的占用空间就是固定的
2. 在一个包含n（n>1）个节点的单链表上，没有头和尾两个指针，下列操作需要遍历多个节点的是（ B ）
A.删除该链表中的第一个节点 B.删除该链表中的最后一个节点
C.在该链表第一个节点前插入一个新节点 D.在该链表最后一个节点后插入一个新节点
3. 用python的二维列表来模拟单向链表，已知列表a=[[“红”,1], [“橙”,2], [“绿”,3],[“青”,-1]]，则在删除节点“橙”之后，列表a的值为（D）
A. [[“红”,1],[“绿”,3],[“青”,-1]]
B. [[“红”,1],[“绿”,2],[“青”,-1]]
C. [[“红”,1], [“橙”,2], [“绿”,3],[“青”,-1]]
D. [[“红”,2], [“橙”,2], [“绿”,3],[“青”,-1]]
4. 使用python的二维列表来模拟单向链表，已知列表a=[[“红”,1]，[“绿”,2],[“青”,-1]]，则在节点“红”和节点“绿”之间插入节点“橙”之后，列表a的值为（A）
A. [[“红”,3],[“绿”,2],[“青”,-1],[“橙”,1]]
B. [[“红”,1],[“绿”,2],[“青”,-1],[“橙”,3]]
C. [[“红”,1],[“橙”,3],[“绿”,2],[“青”,-1]]
D. [[“红”,1],[“橙”,2],[“绿”,3],[“青”,-1]]
5.下列代码创建了一个拥有4个节点的双链表a:
a=[[2,2,3],[8,3,-1],[0,-1,0],[4,0,1]]
head=2
则其头节点和尾节点数据域的值分别为（ B ）
A.2和4 B.0和8 C.8和0 D.3和-1
5.有如下代码段：
a=[[2,2,5],[8,0,5],[0,- 1,0],[1,- 1,2],[5,5,- 1],[3,0,- 1]]
head=2
则该双向链表a的节点数量为( a)
A.3 B.4 C.5 D.6
6.有如下python程序段：
a=[[7,1],[8,2],[9,-1],[6,0]]
head=3
head=a[head][1]
则程序执行后，链表a有几个节点（C ）
A.1 B.2 C.3 D.4
7.有如下python程序段，表示一个链表及操作：
a=[[5,-1],[9,4],[7,3],[2,1],[6,0]]
head=2
p=head
b=[ ]
While a[p][1]!=-1:
b.append(a[p][0])
p=a[p][1]
b.append(a[p][0])
print(b)
程序执行后，输出的结果为（c）
A.[7,2,9,6,5,5] B.[5,9,7,2,6] C.[7,2,9,6,5] D.[2,9,6]
8.有如下python程序段：
a=[[1,1],[2,2],[3,3],[4,-1]]
head=0
cur=a[head][1]
a[head][1]=-1
while cur!=-1:
next_=a[cur][1]
a[cur][1]=head
head,cur=cur,next_
则程序执行后，a的值为（ B ）
A.[[1,1],[2,2],[3,3],[4,-1]] B.[[1,-1],[2,0],[3,1],[4,2]]
C.[[4,1],[3,2],[2,3],[1,-1]] D.[[4,-1],[3,0],[2,1],[1,2]]
9.有如下python程序段：
a=[[4,2,-1],[0,-1,2],[2,1,0]]
head=1
a.append([8,-1,-1])
p=head
while a[p][2]!=-1:
p=a[p][2]
a[p][2]=len(a)-1
a[-1][1]=p
上述代码段中的二维列表a看作是一个双向链表，则执行上述语句后，双向链表的结构可以表示为（ c ）
A.4->0->2->8 B. 8->4->0->2
C. 0->2->4->8 D. 8->0->2->4
10.有如下python程序段：
a=[[2,2,3],[8,3,-1],[0,-1,0],[4,0,1]]
head=2
if a[head][2]!=-1:
a[a[head][2]][1]=-1
head=a[head][2]
上述代码段中的二维列表a看作是一个双向链表，则执行上述语句后，双向链表的结构可以表示为（ d ）
A. 0->2->4->8 B. 0->2->4 C. 0->2->8 D. 2->4->8
11、十二生肖，又称属相，是中国与十二地支相配、表示人出生年份的十二种动物，包括“鼠牛虎兔龙蛇马羊猴鸡狗猪”，小美创建了一个单向链表，每个节点存储一个生肖名称，可是他漏掉了生肖鼠、生肖马和生肖猪。下列代码能将漏掉的三个生肖添加到链表中，请在划线处填入合适的代码。
a=[[“牛”,1],[“虎”,2],[“兔”,3],[“龙”,4],[“蛇”,5],[“羊”,6],[“猴”,7],[“鸡”,8],[“猪”,9]]
head=0
#从链表头部插入存储生肖鼠的新节点
node=[“鼠”，head]
a.append(node)
head= len(a)-1
此时链表a=
#从链表中部插入存储生肖马的新节点
new="马"
p=head
while a[p][0]!= “蛇” :
p=a[p][1]
a.append([new, a[p][1] ]])
a[p][1]=len(a)-1
print(a)此时链表a=
#从链表尾部插入存储生肖猪的新节点
node= [“猪”，-1]
a.append(node)
p=head
while a[p][1]!=-1:
p= a[p][1]
a[p][1]= len(a)-1
此时链表a=