浙教版（2019）選修1《2.2 鏈表》2022年同步練習(xí)卷

• 1．下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的說法正確的是（　　）

  A．“撤銷”操作，是“隊列”的應(yīng)用

  B．排隊就餐，是“?！钡膽?yīng)用

  C．“鏈表”存儲相鄰節(jié)點不需要連續(xù)空間

  D．“樹”中每個節(jié)點的前后都只有一個相鄰節(jié)點
  組卷：31引用：7難度：0.3

  解析

• 2．有一個含7個節(jié)點的單向鏈表，設(shè)有頭指針head和尾指針tail,下列操作需遍歷多個節(jié)點的是（　　）

  A．刪除該鏈表中的最后一個節(jié)點

  B．刪除該鏈表中的第一個節(jié)點

  C．在該鏈表第一個節(jié)點前插入一個新節(jié)點

  D．在該鏈表最后一個節(jié)點后插入一個新節(jié)點
  組卷：5引用：2難度：0.5

  解析

• 3．在Python中可以使用列表模擬單向鏈表，如鏈表中的節(jié)點p,a[p][0]存儲p節(jié)點的數(shù)據(jù)，a[p][1]存儲p指向后繼節(jié)點的指針。若要在p節(jié)點之后插入新的節(jié)點x（x作為p的新后繼節(jié)點），需要執(zhí)行的語句是（　?。?/h2>

  A．a(chǎn)[p][1]=x；a[x][1]=a[p][1]	B．a(chǎn)[x][1]=a[p][1]；a[p][1]=x
  C．a(chǎn)[p][0]=x；a[x][0]=a[p][0]	D．a(chǎn)[x][0]=a[p][0]；a[p][0]=x
  組卷：11引用：4難度：0.5

  解析

• 9．有如下Python程序段：
  
  執(zhí)行該程序段后，鏈表遍歷結(jié)果由初始狀態(tài)變?yōu)樽罱K狀態(tài)，上述程序段中方框處可選代碼為：
  ①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èi)共有n個景點，每個景點序號為0，1，2，3……n-1?，F(xiàn)在只知道每個景點有一條路連接下一個景點。小明想尋找能游玩景點個數(shù)最多的一種方案并且從其中一個景點出發(fā)，最后能夠回到出發(fā)景點。如果游玩的景點個數(shù)一樣，則優(yōu)先考慮景點序號小的。例如，共有 n=5 個景點，每個景點連接的下個景點分別是1，3，4，4，1
  

  景點號	0	1	2	3	4
  下一個景點號	1	3	4	4	1

  方案一：從 0 號景點出發(fā)，則游玩線路為：0 號→1 號→3 號→4 號→1 號，由于此方案無法回到出發(fā)點，則不考慮；
  方案二：從 1 號景點出發(fā)，則游玩線路為：1 號→3 號→4 號→1 號，然后回到1號景點。最多可以玩3個景點。
  現(xiàn)用Python程序模擬這個問題：
  先輸入景點總數(shù)：n；則對應(yīng)的景點為[0，1，2，3，4]
  然后隨機產(chǎn)生各景點所連接的下一個景點的序號，如：[1，3，4，4，1]；
  接著產(chǎn)生一個列表，如上表的信息則產(chǎn)生的列表 s 為：[[0，1]，[1，3]，[2，4]，[3，4]，[4，1]]，
  最后利用鏈表的方式來分析解決問題。程序如下，請將橫線處補充完整并修改加框處。
  
  import random
  #產(chǎn)生信息列表 s
  n=int（input（“景點總數(shù)“））
  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 ②：②處應(yīng)修改為

   

  
  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

  解析