高效作业5 第5课 链表1——单向链表-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参(浙教版2019)
高效作业5[第5课 链表1——单向链表](见学生用书P181)
【A级 新教材落实与巩固】
1.单向链表和数组都属于线性表,它们都用于存储具有相同属性的数据,下列说法不正确的是( C )
A.对于需要频繁插入和删除元素的情况,使用单向链表比使用数组更合适
B.数组适用于最大元素个数容易确定的情况
C.查找特定元素,使用单向链表比使用数组更方便
D.存储相同的元素,使用单向链表比使用数组更方便
【解析】 链表元素的访问只能通过头指针,其他节点通过节点间的指针依次访问,没有数组直接通过下标访问方便,选项C错误。
2. 下列关于链表的说法中,正确的是( D )
A.线性链表中的各元素在存储空间中的位置必须是连续的
B.线性链表中的表头元素一定存储在其他元素的前面
C.线性链表中的各元素在存储空间中的位置不一定是连续的,但表头元素一定存储在其他元素的前面
D.线性链表中的各元素在存储空间中的位置不一定是连续的,且各元素的存储顺序也是任意的
【解析】 链表中的各个节点在内存中可以非顺序存储,通过指针指向后继节点连接各节点数据,选项D正确。
3.如图,这是一个单向链表,在data2与data3之间插入一个新节点data4(p指向data2,r指向data4。列表data来记录链表数据域,列表next来记录指针域),在下列选项中选择正确的执行步骤( D )
①next[p]=next[r] ②next[r]=p
③next[p]=r ④next[r]=-1
⑤next[p]=-1 ⑥next[r]=next[p]
A.⑤②④ B.⑤②
C.①④ D.⑥③
【解析】 在p节点之后插入节点r, 先将r节点指向p的下一节点,语句为next[r]=next[p];再将p节点指向r节点,语句为next[p]=r,选项D正确。
4.在Python中可以使用列表模拟单向链表,如链表中的节点p,a[p][0]存储p节点的数据,a[p][1]存储p指向后继节点的指针。若要在p节点之后插入新的节点x(x作为p的新后继节点),需要执行的语句是( B )
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
【解析】 在p节点之后插入节点r, 先将r节点指向p的下一节点,语句为a[x][1]=a[p][1];再将p节点指向r节点,语句为a[p][1]=x,选项B正确。
5.在Python中可以使用二维列表来模拟单向链表,用包含两个元素的列表来表示每一个节点,其中第一个元素存储数据,第二个元素存储指针(即后继节点在二维列表中的索引)。下列代码创建了一个拥有3个节点的链表a:
a=[[7,2],[8,-1],[9,1]]
head=0
则其头节点和尾节点数据域的值分别为( A )
A.7和8 B.7和9
C.8和9 D.2和-1
【解析】 根据head=0,可知头节点是[7,2],下一个节点是[9,1],尾节点是[8,-1],故头节点和尾节点数据域的值分别为7和8,选项A正确。
6.在Python中可以使用二维列表来模拟单向链表,下列代码创建了一个拥有4个节点的链表a:
a=[[7,1],[8,2],[9,-1],[6,0]]
head=3
依次输出各节点数据域的值,则输出内容为( B )
A.7,8,9,6 B.6,7,8,9
C.9,8,7,6 D.9,6,7,8
【解析】 根据head=3可知,头节点是[6,0],依次访问的节点顺序是[7,1],[8,2],[9,-1],因此输出内容是6,7,8,9,选项B正确。
7.小张准备去多个城市旅游,他设计的行程若采用链表结构表示,如图1所示。
若行程有变,需在“上海”与“成都”之间增加一站“杭州”,链表修改为如图2所示,有以下可选操作:
①“上海”所在节点的next 值赋为“杭州”节点的next 值; ②“上海”所在节点的next 值赋为5;
③“杭州”所在节点的next 值赋为“上海”所在节点的next 值; ④“杭州”所在节点的next 值赋为-1
链表更新顺序正确的是( B )
A.③① B.③② C.①④ D.②④
【解析】 链表中插入新元素并不需要进行元素位置移动,只需要进行节点指针域的更改即可。在“上海”与“成都”之间增加一站“杭州”,需要先将新元素“杭州”的指针域设置为“成都”所在位置,再更改节点“上海”的指针域至节点“杭州”所在位置。即先将“上海”所在节点的next 值赋值给“杭州”所在节点,使“成都”所在节点成为“杭州”
学科网(北京)股份有限公司
所在节点的后继;再让“杭州”所在节点成为“上海”所在节点的后继,即“上海”所在节点的next 值为“杭州”所在节点的索引5。选项B正确。
8. 采用列表模拟单向链表,data[p][0]为数据区域,data[p][1]为指针区域。在单向链表指针为p的节点之后插入指针为s 的节点,正确的操作是( C )
A.data[s][1]=p
data[p][1]=data[s][1]
B.data[p][1]=s
data[s][1]=data[p][1]
C.data[s][1]=data[p][1]
data[p][1]=s
D.data[p][1]=data[s][1]
data[s][1]=p
【解析】 插入过程如下:节点s 的指针区域指向节点p 的后继节点,即data[s][1]=data[p][1],节点p 的指针区域指向节点s,即data[p][1]=s。选项C正确。
9.已知一个有7个节点的单向链表,设有头指针head和尾指针tail,如图所示,下列操作需要遍历多个节点的是( A )
A.删除该链表中的最后一个节点
B.删除该链表中的第一个节点
C.在该链表第一个节点前插入一个新节点
D.在该链表最后一个节点后插入一个新节点
【解析】 删除该链表中的最后一个节点,需要找到该节点的前一个节点,需要从头节点开始遍历,选项A正确。
10.2023·柯桥中学检测有如下Python程序段:
n=int(input())
a=[];head=-1
while n>0:
r=1-n%2
n=n//2
a.append ([r,head])
head=len(a)-1
p=head
while p!=-1:
print(a[p][0],end=””)
p=a[p][1]
执行上述程序段后, 如果输入11, 则输出的结果是( D )
学科网(北京)股份有限公司