浙教版（2019）选修1《2.2 链表》2022年同步练习卷

• 1．下列关于数据结构的说法正确的是（　　）

  A．“撤销”操作，是“队列”的应用

  B．排队就餐，是“栈”的应用

  C．“链表”存储相邻节点不需要连续空间

  D．“树”中每个节点的前后都只有一个相邻节点
  组卷：35引用：7难度：0.3

  解析

• 2．有一个含7个节点的单向链表，设有头指针head和尾指针tail,下列操作需遍历多个节点的是（　　）

  A．删除该链表中的最后一个节点

  B．删除该链表中的第一个节点

  C．在该链表第一个节点前插入一个新节点

  D．在该链表最后一个节点后插入一个新节点
  组卷：5引用：2难度：0.5

  解析

• 3．在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
  组卷：11引用：4难度：0.5

  解析

• 9．有如下Python程序段：
  
  执行该程序段后，链表遍历结果由初始状态变为最终状态，上述程序段中方框处可选代码为：
  ①data[data[qt][1]][1]=pt
  ②data[qt][1]=data[pt][1]
  ③data[pt][1]=data[data[pt][1]][1]
  则方框处代码的正确顺序是（　　）

  A．①②③

  B．①③②

  C．②①③

  D．②③①
  组卷：7引用：3难度：0.5

  解析

• 10．星期天小明来到动物园游玩，园内共有n个景点，每个景点序号为0，1，2，3……n-1。现在只知道每个景点有一条路连接下一个景点。小明想寻找能游玩景点个数最多的一种方案并且从其中一个景点出发，最后能够回到出发景点。如果游玩的景点个数一样，则优先考虑景点序号小的。例如，共有 n=5 个景点，每个景点连接的下个景点分别是1，3，4，4，1
  

  景点号	0	1	2	3	4
  下一个景点号	1	3	4	4	1

  方案一：从 0 号景点出发，则游玩线路为：0 号→1 号→3 号→4 号→1 号，由于此方案无法回到出发点，则不考虑；
  方案二：从 1 号景点出发，则游玩线路为：1 号→3 号→4 号→1 号，然后回到1号景点。最多可以玩3个景点。
  现用Python程序模拟这个问题：
  先输入景点总数：n；则对应的景点为[0，1，2，3，4]
  然后随机产生各景点所连接的下一个景点的序号，如：[1，3，4，4，1]；
  接着产生一个列表，如上表的信息则产生的列表 s 为：[[0，1]，[1，3]，[2，4]，[3，4]，[4，1]]，
  最后利用链表的方式来分析解决问题。程序如下，请将横线处补充完整并修改加框处。
  
  import random
  #产生信息列表 s
  n=int（input（“景点总数“））
  tt=（　　）；s=（　　）；c=0
  while c＜n：
  t=random.randint（0，n-1）
  if t!=c：
  s.jye.ai（[①

   

  ]）
  c+=1
  print（s）
  #枚举所有方案，寻找正确方案。
  max=0
  for head in range（n）：
  p=head
  k=1
  while k＜=n and s[p][1]!=head：
  k+=1
  p=s[p][1]
  if k＞max ②：②处应修改为

   

  
  max=k
  maxp=head
  print（“小明最多能访问%d 个景点“%（max））
  #输出正确线路
  p=maxp
  while s[p][1]!=maxp：
  print（s[p][0]，end=“→“）
  p=s[p][1]
  print（③

   

  ）
  组卷：5引用：1难度：0.3

  解析