浙教版(2019) 高中信息技术 选修1 2.2 链表 同步练习

资源下载
  1. 二一教育资源

浙教版(2019) 高中信息技术 选修1 2.2 链表 同步练习

资源简介

第二章 2.2 链 表
一、选择题(每小题列出的四个备选项中只有一个是符合题目要求
的,不选、多选、错选均不得分)
1.下列有关链表的说法,正确的是 ( )
A.可快速访问任何一个数据元素
B.插入、删除操作无需移动数据元素
C.链表占用固定的存储空间
D.链表不一定含有头指针
2. 已知一个有7个节点的单向链表,设有头指针head 和尾指针tail, 如 图所示,下列操作需要遍历多个节点的是 ( )
列表索引数据域指针域
0 1 head → 2 tail → 3 4 5 6 i 5
n 0
m 4
g -1
0 6
n 3
r 1
A.删除该链表中的最后一个节点
B.删除该链表中的第一个节点
C.在该链表第一个节点前插入一个新节点
D.在该链表最后一个节点后插入一个新节点
3. 由 n个节点链接成的单向链表如图所示,其中head 为头指针,现要
删除链表中的尾节点(end所指节点),下列操作正确的是 ( )
end
head→ datal next data2 next data3 next datan -1
A.将end所指节点的数据值改为0
B.将end所指节点的next值改为head
C.将end所指节点的前驱节点的next值改为0
D.将end所指节点的前驱节点的next值改为-1
4.下列关于链表的叙述,正确的是 ( )
A.线性链表中的各元素在存储空间中的位置必须是连续的
B.线性链表中的表头元素一定存储在其他元素的前面
C.线性链表中的各元素在存储空间中的位置不一定是连续的,但
表尾元素一定存储在其他元素的后面
D.线性链表中的各元素在存储空间中的位置不一定是连续的,且
各元素在存储空间中的存储顺序也是任意的
5.Python中可以使用二维列表来模拟双向链表,用包含三个元素的 列表来表示一个节点,其中第一个元素存储数据,第二、三个元素 分别存储前驱节点的地址和后继节点的地址(-1表示无前驱节点 或后继节点)。下列代码创建了一个有4个节点的升序(从小到大)
双向链表a:
a=[[12,2,3],[18,3,- 1],[10,- 1.0].[14,0. 1]]
head=2
现使用append()方法插入新数据17,并使a依旧保持升序,则插入
后的列表a是 ( )
A.[[12,2,3],[18,3,- 1],[10,- 1.0].[14,0,1],[17,3,1]]
B.[[12,2,3],[18,3,- 1],[10,- 1,0].[14,0,4],[17,3,1]]
C.[[12,2,3],[18,4,- 1],[10,- 1.0].[14,0,4],[17,3,1]]
D.[[12,2,3],[18,4,- 1],[10,- 1.0].[14,0,1],[17,3,1]]
6. 有单向链表如图所示,在data2 与data3 之间插入一个新节点data4 (p指向data2,r指向data4。 列表data记录链表数据域,列表next记
录各节点的指针域),则下列执行步骤及顺序正确的是 ( )
(
datal
next
data2
next
data3
next
data4
next
P
)
①next[p]=next[r]②next[r]=p ③next[p]=r ④next{r}=-1
⑤ next[p]=-1 ⑥next[r]-next[p]
A.⑤②④ B.⑤② C.①④ D.⑥③
7. 某Python程序如下:
s=[[8,2],[5,-1],[6,1],[9,0]]
p=head=0
while s[p][1]!=head:
print(s[p][0],end="->")
p=s[p][1]
print(s[p][0])
程序运行后,输出的结果是 ( )
A.8->6->5->9 B.9->5->6->8
C.8->5->6->9 D.9->6->5->8
8. 某Python程序如下:
a=[[7,1],[8,2],[9,- 1]]
head=0
p=1
a.append([6,a[p][1]I)
a[p][1]=len(a)- 1
程序运行后,下列说法正确的是 ( )
A.a[2][0]的值为6,单向链表a的尾节点数据值为6
B.a[2][0]的值为9,单向链表a的尾节点数据值为6
C.a[3][1]的值为2,单向链表a的尾节点数据值为9
D.a[3][1]的值为-1,单向链表a的尾节点数据值为9
二、非选择题
9. 双向链表也叫双链表,它的每个数据都有两个指针,分别指向前驱 节点和后继节点。在Python中用二维列表来模拟双向链表,用包 含3个元素的列表来表示每一个节点,其中第一个元素存储数据, 后两个元素分别存储指向前驱节点和后继节点的指针。若没有前 驱或后继节点则对应的指针值为-1。下列程序产生了一些两位数 的随机正整数,并依次存储到双向链表a中。现要求删除其中值为
偶数的节点,请在划线处填入合适的代码。
import random
a= [ ]
head=- 1
for i in range(8):
node=[ ① ,head,- 1]
a.append(node)
if head!=- 1:
a[head][2]=i
head= ②
p=head=0
while p!=- 1:
if a[p][0]%2==0:
if ③ :
a[a[pl[1]][2]=a[p][2]
if a[p][2]!= -1:
a[a[pl[2]][1]=a[p][1]
if head==p:
head= ④
p=a[p][2]
10. 山顶上有10个圆形排列的洞, 一只狐狸和一只兔子各住一个洞 狐狸总想吃掉兔子。 一天兔子对狐狸说:“你想吃我有一个条件, 先把洞从1~10编上号,你先到1号洞找我;第二次隔1个洞(即3 号洞)找我,第三次隔2个洞(即6号洞)找我,之后以此类推,次数 不限。但狐狸从早到晚进进出出了1000次,仍没有找到兔子。请问兔子可能躲在哪个洞里
实现上述功能的Python程序如下,请在划线处填入合适的代码。
hone=[]
n=10
m=1000
#构造一个循环链表,并给n 个洞编号,设置洞的初始标志为0
#链表的节点样式为:[洞的标志,洞的编号]
fori in range(n- 1):
hone.append([0,i+1])

#狐狸开始找兔子,将进入过的洞标志改为1,寻找m 次结束
head=0 #第一个洞的位置
k=head
hone[0][0]=1
for i in range(1,m):
for j in range(1,i+2):

hone[k][0]=1
#输出标志仍为0的洞,即兔子可能藏身地点
for i in range(len(hone)):
if hone[i][0]==0:
print("兔子可能躲在第"+ ③ +"号洞")
11.传话游戏。 一个班级中的n 个同学(编号为1~n) 正在玩一个游 戏,每人在纸条上随机写一个1~n 之间的数字。接下来,每位同 学传一句话给纸条上编号对应的另一位同学,收到这句话的同学 又继续将这句话传给自己纸条上编号对应的同学。问在游戏的过程中,有多少人会收到自己传出去的话
(1)以五位同学为例,每人的信息和纸条信息如表所示,有 位同学能收到自己传出去的话。
同学本人编号 1 2 3 4 5
纸条上的编号 5 4 2 1 2
(2)根据抽象与建模,若编程解决该问题,则适合使用 (选填:数组/链表/队列)来存储和处理数据。
(3)实现上述功能的Python程序如下,请在划线处填入合适的 代码。
(4)若将程序加框处代码改为cntimport random
n=int(input(”输入班级人数:")
#随机生成纸条信息
zhitiao=[random.randint(1,n)fori in range(n+1)]
ans=0
fori in range(1.n+1):#对每个同学进行传话过程的模拟
cnt=1 #cnt存储传话经过的人数
p=i
while zhitiaolpl!=i and cnt<=n:

cnt+=1
if zhitiao[p] == i:

print(ans)
12. 下列Python程序的功能是使用类的方法创建一个链表,并在链表
中间插入一个新节点。
class Nodei
def init (self.data=None):
self.data=data
self.next=None
class Link list( )
def init (self):
self.head=None
def print list(self):
ptr=self.head
while ptr:
print(ptr.data)
ptr=ptr.next
def insert node(self,pre node,newdata):
if pre node==None:
print("插入位置不对")
else:
new node=Node(newdata)


link=Link list()
link.head=Node(1)
n2=Node(5)
n3=Node(9)
link.head.next=n2
n2.next=n3
link.print list()
print("新的链表")
link.insert node(n2,7)
③ #打印链表
请回答下列问题:
(1)操作后的新链表中的节点是
(2)请在划线处填入合适的代码。

展开更多......

收起↑

资源预览