高效作业5 第5课 链表1——单向链表-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参(浙教版2019)

| 9页
| 79人阅读
| 7人下载
浙江良品图书有限公司
进店逛逛

新版页眉

学科网 zxxk.com学科网 zxxk.com

高效作业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]=xpage number 0

独家授权

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司


新版页眉

学科网 zxxk.com学科网 zxxk.com

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 值赋值给“杭州”所在节点,使“成都”所在节点成为“杭州”page number 1

独家授权

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司


新版页眉

学科网 zxxk.com学科网 zxxk.com

所在节点的后继;再让“杭州”所在节点成为“上海”所在节点的后继,即“上海”所在节点的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 )page number 2

独家授权

学科网 zxxk.com学科网 zxxk.com学科网(北京)股份有限公司


由于学科网是一个信息分享及获取的平台,不确保部分用户上传资料的 来源及知识产权归属。如您发现相关资料侵犯您的合法权益,请联系学科网,我们核实后将及时进行处理。