资源简介 第二章 2.2 链 表一、选择题(每小题列出的四个备选项中只有一个是符合题目要求的,不选、多选、错选均不得分)1.下列有关链表的说法,正确的是 ( )A.可快速访问任何一个数据元素B.插入、删除操作无需移动数据元素C.链表占用固定的存储空间D.链表不一定含有头指针2. 已知一个有7个节点的单向链表,设有头指针head 和尾指针tail, 如 图所示,下列操作需要遍历多个节点的是 ( )列表索引数据域指针域0 1 head → 2 tail → 3 4 5 6 i 5n 0m 4g -10 6n 3r 1A.删除该链表中的最后一个节点B.删除该链表中的第一个节点C.在该链表第一个节点前插入一个新节点D.在该链表最后一个节点后插入一个新节点3. 由 n个节点链接成的单向链表如图所示,其中head 为头指针,现要删除链表中的尾节点(end所指节点),下列操作正确的是 ( )endhead→ datal next data2 next data3 next datan -1A.将end所指节点的数据值改为0B.将end所指节点的next值改为headC.将end所指节点的前驱节点的next值改为0D.将end所指节点的前驱节点的next值改为-14.下列关于链表的叙述,正确的是 ( )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记录各节点的指针域),则下列执行步骤及顺序正确的是 ( )(datalnextdata2nextdata3nextdata4nextP)①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=0while 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->8C.8->5->6->9 D.9->6->5->88. 某Python程序如下:a=[[7,1],[8,2],[9,- 1]]head=0p=1a.append([6,a[p][1]I)a[p][1]=len(a)- 1程序运行后,下列说法正确的是 ( )A.a[2][0]的值为6,单向链表a的尾节点数据值为6B.a[2][0]的值为9,单向链表a的尾节点数据值为6C.a[3][1]的值为2,单向链表a的尾节点数据值为9D.a[3][1]的值为-1,单向链表a的尾节点数据值为9二、非选择题9. 双向链表也叫双链表,它的每个数据都有两个指针,分别指向前驱 节点和后继节点。在Python中用二维列表来模拟双向链表,用包 含3个元素的列表来表示每一个节点,其中第一个元素存储数据, 后两个元素分别存储指向前驱节点和后继节点的指针。若没有前 驱或后继节点则对应的指针值为-1。下列程序产生了一些两位数 的随机正整数,并依次存储到双向链表a中。现要求删除其中值为偶数的节点,请在划线处填入合适的代码。import randoma= [ ]head=- 1for i in range(8):node=[ ① ,head,- 1]a.append(node)if head!=- 1:a[head][2]=ihead= ②p=head=0while 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=10m=1000#构造一个循环链表,并给n 个洞编号,设置洞的初始标志为0#链表的节点样式为:[洞的标志,洞的编号]fori in range(n- 1):hone.append([0,i+1])①#狐狸开始找兔子,将进入过的洞标志改为1,寻找m 次结束head=0 #第一个洞的位置k=headhone[0][0]=1for 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 randomn=int(input(”输入班级人数:")#随机生成纸条信息zhitiao=[random.randint(1,n)fori in range(n+1)]ans=0fori in range(1.n+1):#对每个同学进行传话过程的模拟cnt=1 #cnt存储传话经过的人数p=iwhile zhitiaolpl!=i and cnt<=n:①cnt+=1if zhitiao[p] == i:②print(ans)12. 下列Python程序的功能是使用类的方法创建一个链表,并在链表中间插入一个新节点。class Nodeidef init (self.data=None):self.data=dataself.next=Noneclass Link list( )def init (self):self.head=Nonedef print list(self):ptr=self.headwhile ptr:print(ptr.data)ptr=ptr.nextdef 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=n2n2.next=n3link.print list()print("新的链表")link.insert node(n2,7)③ #打印链表请回答下列问题:(1)操作后的新链表中的节点是(2)请在划线处填入合适的代码。 展开更多...... 收起↑ 资源预览