2024-2025学年高二上学期浙教版(2019)选修一 2.2 链表 同步练习（含答案）

2023-2024学年高二上学期浙教版(2019)选修一2.2 链表 一、选择题 1．如下图所示的链表： 假如要查找元素11，共需遍历的次数为（ ） A．5 B．6 C．7 D．8 2．寻宝游戏中通过一个线索找到下一个线索，最好用下列数据组织形式中的（ ）来表示。 A．数组 B．链表 C．栈 D．队列 3．小张准备去多个城市旅游，他设计的行程若采用链表结构表示，如图a所示。 图a 图b 若行程有变，需在“上海”与“成都”之间增加一站“杭州”，链表修改为如图b所示，有以下可选操作： ①“上海”所在节点的next值赋为“杭州”所在节点的next值 ②“上海”所在节点的next值赋为5 ③“杭州”所在节点的next值赋为“上海”所在节点的next值 ④“杭州”所在节点的next值赋为-1 链表更新顺序正确的是（ ） A．③② B．③① C．①④ D．②④ 4．把单向链表第1个节点的位置口叫奇数位置，第2个节点的位置叫偶数位置，以此类推。现将所有偶数位置的节点依次取出后，放在所有奇数位置节点的后面。实现该功能的 Python代码段如下，方框中应填入的正确代码为（ ） a=[['a',1],['b',2]. ['c',3],['d',4],[ 'e',-1]] head=odd=0 #链表 a头节点指针是 head evenhead=even=a[head][1] while even!=-1 and a[even][1]!=-1: a[odd][1]=evenhead #将链表连接在奇数链表之后 A． B． C． D． 5．链表中的节点通常包含哪两部分（ ） A．数据域和控制域 B．数据域和指针域 C．指令域和地址域 D．标志域和内容域 6．有如下 Python程序，用于判断链表是否为回文链表（回文链表是指正序遍历和逆序遍历得到的结点顺序一致的链表），则划线处代码是（ ） a=[[1,1],[2,2],[8,3],[2,4],[1,-1]] st=[];head=0;flag=True slow, fast=head, head while ① : st.append (a[slow][o]) slow=a[slow][1] fast=a[a[fast][1]][1] if ② : slow=a[slow][1] while slow!=-1: if st.pop () !=a[slow][0]: flag=False slow=a[slow][1] if flag: print("是回文链表!") else: print("不是回文链表!") A．①fast!=-1 or a[fast][1]!=-1 ②fast!=-1 B．①fast!=-1 or a[fast][1]!=-1 ②a[fast][1]!=-1 C．①fast!=-1 and a[fast][1]!=-1 ②fast!=-1 D．①fast!=-1 and a[fast][1]!=-1 ②a[fast][1]!=-1 7．有如下图所示的单向链表： 从头指针head指向的节点开始查找数据元素“5”，并删除该节点，下列说法正确的是（ ） A．共需查找3次 B．删除数据元素“5”的节点，后续节点需要移动3次 C．头指针head将指向数据元素“7”的节点 D．操作完成后，链表中数据元素的个数为6个 8．创建一个空链表时，通常会设置什么来表示链表的起始（ ） A．尾指针 B．头指针指向一个空节点 C．头指针指向NULL或-1 D．无需设置特殊标记 9．一头指针 head=2 的单向链表 L=[[30,4], [10,-1], [20,0], [15,1],[21,3]]通过以下 Python 程序段，转换为原链表的逆序链表，即头指针 head=1，L=[[30,2], [10,3], [20,-1], [15,4],[21,0]]。 q=-1 p=head #head 为原链表头指针 while p!=-1 : tmp=L[p][1] head=q 上述程序段中方框处可选的语句为：①p=tmp ②q=p ③L[p][1]=q 则方框处语句依次为( ) A．③②① B．③①② C．①③② D．①②③ 10．有如下 Python 程序段 def bianli(head): pt = head while pt != -1: print(data[pt][0],data[pt][1],"->",end='') pt = data[pt][1] print() data = [['A',1],['B',2],['C',3],['D',-1]] head = 0 bianli(head) #遍历链表，显示初始状态为“A 1 ->B 2 ->C 3 ->D -1 ->” qt = head pt = data[qt][1] bianli(head) #遍历链表，显示最终状态为“A 2 ->C 1 ->B 3 ->D -1 ->” 执行该程序段后，链表遍历结果由初始状态变为最终状态，上述程序段中方框处可选代码为： ①data[data[qt][1]] ... ...