链表及其基本操作一轮复习课件-浙江省高三信息技术选修一

链表及其基本操作知识过关

1.链表的概念(1)链表指的是将需要处理的数据对象以节点的形式,通过指针串联在一起的一种数据结构。(2)每个节点一般包括两个区域:数据区域和指针区域。(3)每个链表有一个表头——head(也称头指针),是链表的入口,也便于循环链表在数据处理时的边界判断和处理。(4)链表的形式。链表的形式主要有单向链表、双向链表和循环链表。①单向链表:只有一个指针用来指向其后继节点。单向链表如图所示。②双向链表:有两个指针分别用于指向其前驱节点和后继节点。双向链表如图所示。③循环链表:第一个节点和最后一个节点使用指针链接。循环链表如图所示。2.链表的特性(1)同一链表中每个节点的结构均相同,由数据区域和指针区域组成。(2)每个链表必定有一个头指针,以实现对链表的引用和边界处理。(3)链表占用的空间不固定。可根据需求增删节点,提高存储空间的利用率。3.链表的基本操作(1)链表的创建。(2)链表节点的访问。链表只能通过头指针进行访问,其他节点通过节点间的指针依次访问。(3)链表节点的插入与删除。插入操作:插入datax节点删除data2节点(4)链表节点的访问与遍历。访问链表中的节点时,只能通过头指针进入链表并通过指针链接依次访问,直到找到目标位置上的节点。*4.链表的类实现在Python中,链表除了可以使用列表来实现,还可以使用“类”来实现。“类”是一种抽象的数据结构,它将数据及其操作封装在一起。构造单向链表类的具体实现过程如下:(1)自定义单向链表的节点类:class

Node:

#定义单链表节点类

def_init_(self,data,next_=None):#初始化节点包含两个域self.data、self.next

self.data=data

#self.data域保存数据

self.next=next

#self.next域保存指针,缺省值为None(2)构造单向链表类:class

Link:

#定义单向链表类Link

def_init_(self):

#初始化空链表

self._head=None

#空链表头指针指向为空

典例精选【例1】下列关于链表的说法,错.

误.

的是(

)A.插入、删除操作不需要移动数据元素B.增加或减少节点会改变链表占用的存储空间C.可随机快速访问任何一个数据元素D.同一链表中每个节点的结构均相同【解析】可随机快速访问数据元素的是数组结构,原因是数组结构不仅在逻辑上相邻,其物理存储位置也相邻。但链表的物理存储位置可能是随机的,C符合题意。C【例2】

(2024·浙江6月选考)使用列表d模拟链表结构(节点数n>0),如图1所示,每个节点包含数据区域和指针区域,h为头指针。现要按链表顺序将这n个节点中的数据依次存放到d[0][0]、d[1][0]、…、d[n－1][0]中,最终保持节点链接关系不变,结果如图2所示。实现上述功能的Python程序段如下,方框中应填入的代码是(

)

p,i

=

h,0

while

p!=－1:

tp

=

d[p][1]

if

p

==

i:

i+=

1

elif

p>i:

d[i][0],d[p][0]

=

d[p][0],d[i][0]

i+=

1

p

=

tp#

调整头指针h及指针区域,保持节点链接关系不变,代码略图2图1(

)A.d[i][1]

=

d[p][1]

d[p][1]

=

i

B.d[p][1]

=

d[i][1]

d[i][1]

=

pC.d[i][1]

=

p

d[p][1]

=

d[i][1]

D.d[p][1]

=

i

d[i][1]

=

d[p][1]B【解析】本题考查链表的节点操作。根据题意可知,当前节点为p节点,p从头结点开始进行遍历。而变量i是从0开始顺序增加的,当p和i相等时,意味着链表是按链表顺序依次存放到d[0][0]、d[1][0]…d[n－1][0]的,即已经符合题意,此时只需依次进行简单的迭代即可。若p和i不相等,即数据的存放不符合题意,由于i是从0开始的,因此若p和i不等则肯定是p>i,此时由代码可知将节点i和节点p的数据域进行交换,由于在链表中p的位置比节点i更加靠前,即p→i。而数据交换后两者的关系刚好逆转了,即i→p,因此可以先删除节点i,然后将节点i插入到p节点的前面,这样即可实现题意,故先执行代码d[p][1]=d[i][1],删除节点i,然后再将节点i指向节点p,故代码为d[i][1]=p。以此类推直到循环结束。至此，链表已实现按照顺序将这n个节点中的数据依次存放到d[0][0]、d[1][0]、…、d[n－1][0]中,但循环结束后,还需要修改头指针h的值,以及重新调整每个节点的指针域数据(即代码略部分)。B正确。【例3】

(2024·浙江1月选考)使用列表d模拟链表结构(节点数大于0),每个节点包含数据区域和指针区域,h为头指针。链表中各节点已按数据区域中数值的绝对值由小到大排列,如图1所示。现要修改该链表各节点的链接关系,使链表各节点按数据区域中的数值由小到大排列,结果如图2所示。实现该功能的程序段如下,方框中应填入的代码是(

)t=h

p=d[h][1]

while

p

!=

－1

:

q=d[p][1]

p=q

d[t][－1]=－1

图1

图2A.if

d[p][0]>0:

d[q][1]=p

d[t][1]=q

else:

d[h][1]=q

h=pB.if

d[p][0]>0:

d[t][1]=q

t=q

else:

h=p

d[p][1]=tC.if

d[p][0]>0:

d[t][1]=p

t=p

else:

d[p][1]=h

h=pD.if

d[p][0]>0:

d[t][1]=q

d[q][1]=p

else:

d[p][1]=h

h=qC(

)【解析】本题考查单链表及分支语句和数据排序等知识。由于数据区域中数值的绝对值由小到大排列,由代码可知,原先的节点关系是:t→p→q,若数据区域d[p][0]的数值为正数,则原链表节点关系不变,只需将各节点关系往下迭代即可,即:t变为p,p变为q即可。若数据区域d[p][0]的数值为负数,则原先的链表各节点关系需要重新指向,由于原数据是按照绝对值大小排序的,因此越往后面绝对值数越大,因此其相反数(负数)就越小,这样每一个当前节点p的负数肯定是当前链表中最小的数,因此该数应该变为最小的头节点,采用头插法可以实现,即将当前节点p的指针域指向原先的头节点h,然后再将头节点h变为当前节点p,C正确。

自我检测1.关于单向链表的节点结构,下列说法中错.

误.

的是(

)A.节点的数据区域用于存放实际需要处理的数据元素B.节点的指针区域用于存放该节点相邻节点的存储地址C.单向链表必须带有数据区域为空的头节点和尾节点D.单向链表中的各个节点在内存中可以非顺序存储【解析】单向链表的头尾节点一般情况下数据区域都不为空,是有效节点,C符合题意。C2.有如下Python程序段:d=[[7,1],[8,2],[9,－1],[6,0]]head=3head=d[head][1]程序执行后,链表中共有几个节点(

)A.1 B.2C.3 D.4【解析】本题考查链表的知识。原链表有4个节点,经过代码“head=d[head][1]”操作后,头节点变为0,故节点数减少为3,C正确。C3.下列关于链表的说法,正确的是(

)A.链表中的各元素在存储空间中的位置必须是连续的B.链表中的表头元素一定存储在其他元素的前面C.链表中的各元素在存储空间中的位置不一定连续,且各元素的存储顺序也是任意的D.链表一旦创建好后,它的占用空间就是固定的【解析】本题考查链表的基础知识。链表中的各元素在存储空间中的位置不一定连续,A错误。链表中的表头元素也可以在其他元素后面,B错误。链表一旦创建好后,其占用空间是可变的,比较灵活,D错误。C4.有如下Python程序段:d=[[7,2],[5,4],[4,1],[9,－1],[1,3]]p=head=2while

d[p][1]!=－1:

print(d[p][0],end="－>")

p=d[p][1]执行该代码后,输出的结果是(

)A.4－>5－>1 B.7－>4－>5－>1－>C.4－>5－>1－> D.4－>5－>1－>9【解析】本题考查链表的遍历。由于循环的条件是d[p][1]!=－1,也就是当前头指针p的下一个指针域不是最后一个(指针域为－1),则输出该数据域。因此这样输出,最后的9不能输出,C正确。C5.有如下Python程序段:d=[[6,2],[4,3],[8,1],[2,－1]]p=head=0whilep!=－1:

print(d[p][0],end="－>")

p=d[p][1]执行上述语句后,程序输出结果为(

)A.6－>8－>4－> B.6－>8－>4C.2－>8－>6－>4 D.6－>8－>4－>2－>【解析】列表d存储了一个单向链表,d[p][0]和d[p][1]分别是节点p的数据域和指针域,程序功能为从头节点开始遍历链表输出各节点的数据域的值,且这种遍历可以输出最后一项节点的数据2。D必备知识练1.使用链表结构模拟某校浏览路线,链表a中每一个节点包含三个数据,第1个为地点名称,第2个为预计停留时间(单位:分钟),第3个为指向下一个地点的指针。可以从多个地点开始浏览,但只能从“南大门”离开,输出显示从各景点进入路线及预计总时间的代码如下。a=[["校训石",15,2],["教学楼",30,2],["风雨操场",25,5],["科技楼",40,4],["新华书店",60,5],["南大门",20,－1]]

head=[0,1,3]

foriinrange(len(head)):

(1)

s=a[p][1]

whilea[p][2]!=－1:

print(a[p][0],end="→")

(2)

(3)

print(a[p][0])

print("预计时间:",s,"分钟")

上述程序画线处的可选代码有:①p=head

②p=head[i]

③s=s＋a[p][1]

④p=a[p][2]

则(1)、(2)、(3)处代码依次为(

)A.①③④ B.①④③

C.②③④ D.②④③【解析】本题考查链表节点遍历知识。由代码可知,p为当前节点,且起始节点可选,因此(1)处代码应该是p=head[i],从而排除选项A和B。代码(2)和(3)处,由于s的初值已经包含当前节点的访问时间(s=a[p][1])但却没有输出当前节点的地点名称,因此应该先指向下一个节点,然后再将该节点的访问时间累加到s中,即先④再③,故选D。D2.使用列表d模拟链表结构(节点数大于0),每个节点包含数据区域和指针区域,h为头指针。下列程序段实现了删除数据区域为奇数的节点。q=p=h=2whilep!=－1:

ifd[h][0]%2==1:

(1)

q=p=h

elifd[p][0]%2==1:

(2)

p=d[p][1]

else:

q=p

p=d[p][1]画线处可选代码如下:①h=d[h][1]

②p=d[p][1]

③d[p][1]=d[q][1]

④d[q][1]=d[p][1]下列选项中,代码顺序正确的是(

)A.①③ B.②③C.①④ D.②④【解析】本题考查链表节点删除知识。由代码可知,p为当前节点,q为p的前驱节点,删除当前节点p的代码应该是d[q][1]=d[p][1],因此可以排除③,即选项AB不可能。h为头节点,需要单独考虑,若头节点为奇数则删除头结点h,且修改头节点的值,因此(1)处代码为h=d[h][1],故本题选C。C3.用链表实现数组的升序排序,Python程序如下,方框中应填入的正确代码是(

)#生成无序数组,元素如[3,－1],分别表示数值和指针(指针初值均为－1),代码略head=0for

i

in

range(1,len(a)):

q=head

p=a[head][1]

if

a[head][0]>a[i][0]:

a[i][1]=head

head=i

else:

a[q][1]=i;a[i][1]=pA.while

p!=－1

and

a[p][0]<a[i][0]

:

q=p

p=a[p][1]B.while

p!=－1

and

a[p][0]<a[i][0]

:

p=a[p][1]

q=pC.while

p!=－1

and

a[q][0]<a[i][0]

:

p=q

q=a[q][1]D.while

q!=－1

or

a[p][0]<a[i][0]

:

q=p

p=a[p][1]A【解析】本题考查链表与排序的综合应用。该算法中head固定在位置0,每轮均需要在已完成排序的链表中遍历,并把a[i]插入到q和p之间。本轮查找时,若p节点数据小于a[i]并且未到链表尽头(p不等于－1),则继续搜索,然后更新前置节点q和后继节点p。A正确。4.使用列表d模拟链表结构(节点数大于0),每个节点包含数据区域和指针区域,head为头指针。现要删除链表中数据值在[begin,end]范围的节点,实现该功能的部分程序段如下,方框中应填入的代码是(

)d=[[4,

5],

[10,

2],

[12,

4],

[1,

0],

[16,

－1],

[7,

1]]head=3q=head;p=headwhile

p!=－1:

if

d[p][0]<begin

or

d[p][0]>end:

q=p

p=d[p][1]else:A.if

head!=p:

d[q][1]=d[p][1]

else:

head=d[p][1]

p=d[p][1]

B.if

head==p:

d[q][1]=d[p][1]

else:

head=d[p][1]

p=d[p][1]C.if

head!=p:

p=d[p][1]

else:

head=d[p][1]

p=d[p][1]D.if

head==p:

p=d[p][1]

else:

head=d[p][1]

p=d[p][1]A【解析】本题考查链表节点删除的知识。根据代码可知,p为当前节点,q为p的前驱节点。其删除数据节点的逻辑为:若数值不在[begin,end]范围之内的节点p,依次往后进行迭代。若数值在[begin,end]范围之内的节点p,将当前节点删除。删除节点p时又可分为两种情况,若删除的是头节点,需要更新head值为当前节点p的下一个节点,代码为head=d[p][1]。若删除的节点不是头节点,则让p的前驱节点q直接指向p的后继节点,即可实现删除p节点,因此其代码是d[q][1]=d[p][1]。A正确。关键能力练

5.使用列表d模拟链表结构(节点数大于2,且不存在连续为0的节点),每个节点包含数据区域和指针区域,h为头指针。链表的开头和末尾的节点数据区域的值均为0,如图1所示。现要把相邻两个数值为0的节点之间所有节点合并为一个节点,该节点值为所有合并节点值之和,并将值为0的节点移除,结果如图2所示。实现该功能的部分程序段如下,方框中应填入的正确代码是(

)k=h;p=d[k][1]while

k!=－1

and

p!=－1:

p=d[k][1]

图1

图2A.if

d[p][0]!=0:

d[k][0]＋=d[p][0]

d[k][1]=d[p][1]

if

d[p][0]==0:

k=pB.if

d[p][0]!=0:

d[k][0]＋=d[p][0]

d[k][1]=d[p][1]

if

d[p][0]==0:

k=d[k][1]C.if

d[p][0]==0:

k=p

else:

d[k][0]＋=d[p][0]

d[k][1]=d[p][1]D.if

d[p][0]==0:

k=d[k][1]

else:

d[k][0]＋=d[p][0]

d[k][1]=d[p][1]B【解析】本题考查链表操作等相关知识。题干明确告知头节点和尾节点数据区域均为0,因此从第一个节点开始就需要将后继的值加入当前头节点的数据域当中,并删除值已经被加入的节点。而当下一次遇到数值为0的节点时,就需要思考,最后一个节点也是数据为0的节点,如果按照如上的方案进行后几个0节点的操作,那么最后一个0节点将无法被删除。因此,当跳过第一个0节点以后,当遇到下一个0数据域的节点时,直接跳过当前节点,以0数据域的下一个节点作为当前k的节点,既保证了数据域的不丢失,也保证了删除数据域为0

的节点。A选项,当碰到数据域的0节点时,k移动到当前0节点数据域,但是当前的节点在上一次的使用中已经被删除,A错误。当碰到数据域的0节点,k

移动到当前0节点数据域,最后一个0节点无法被删除,C、D错误。6.使用列表d模拟链表结构(节点数大于1),每个节点包含数据区域(数据均为整型,范围为0~9)和指针区域,h为头指针,如图1所示。现要对该链表节点进行去重操作,只保留最后一次出现的节点,结果如图2所示。lst

=

[0]*10

p

=

hwhile

p

!=

－1:

lst[d[p][0]]

＋=

1

p

=

d[p][1]q,

p

=

h,

hwhile

d[p][1]

!=

－1:

p

=

d[p][1]图1图2A.if

lst[d[p][0]]

>=

2:

if

p

==

h:

h

=

d[h][1]

else:

d[q][1]

=

d[p][1]

lst[d[p][0]]

－=

1

else:

q

=

pB.if

lst[d[p][0]]

<

2:

q

=

p

elif

p

==

h:

lst[d[p][0]]

－=

1

h

=

d[h][1]

else:

lst[d[p][0]]

－=

1

d[q][1]

=

d[p][1]C.if

lst[d[p][0]]

>=

2:

if

p

==

h:

h

=

d[h][1]

else:

d[d[p][1]][1]

=

q

lst[d[p][0]]

－=

1

else:

q

=

d[q][1]D.if

lst[d[p][0]]

<

2:

q

=

d[p][1]

else:

if

p

!=

h:

d[q][1]

=

p

else:

h

=

d[h][1]

lst[d[p][0]]

－=

1实现该功能的程序段如下,方框中应填入的代码是(

)B【解析】本题考查链表的综合应用。删除链表的重复元素,先通过遍历将链表元素按数值放入lst

数组中,lst

数组实现统计每个元素出现的次数。若次数小于2

,则保留,若大于或等于2,则通过链表元素删除,保留最后一次出现的节点。删除链表节点分为两种情况:①删除头节点,通过修改头指针为h=d[h][1]实现;②删除非头指针,q

为前驱节点,p

为当前节点,通过修改前驱节点指针域d[q][1]=d[p][1],删除当前p

指向的节点。

B正确。7.有如下Python程序段:a=[[1,1],[2,2],[3,3],[4,－1]]head=0cur=a[head][1]a[head][1]=－1whilecur!=－1:

next=a[cur][1]

a[cur][1]=head

head,cur=cur,next则程序执行后,a的值为(

)A.[[1,1],[2,2],[3,3],[4,－1]] B.[[1,－1],[2,0],[3,1],[4,2]]C.[[4,1],[3,2],[2,3],[1,－1]] D.[[4,－1],[3,0],[2,1],[1,2]]【解析】本题考查链表操作知识。该程序通过修改各个节点的指针值,来实现链表全部节点逆转的功能。程序运行结束后head的值为3,结果如选项B。B8.使用列表L模拟链表结构,每个节点包含数据区域和指针区域,现要删除该链表中的某一元素,示例输出结果如图所示,实现该功能的程序段如下。

请输入要删除的数据:9找到删除数据7－>4－>8－>6－>5>>>

==============RESTA==请输入要删除的数据:18未找到删除数据9－>7－>4－>8－>6－>5>>>

def

delete(data,p):

head=0

if

p==data[head][0]:

head=data[head][1]

print("找到删除数据")

else:

cur=pre=head

while

(1)

:

pre=cur

cur=data[cur][1]

if

cur!=－1:

(2)

print("找到删除数据")

else:

print("未找到删除数据")

return

head

L=[[9,3],[4,2],[8,4],[7,1],[6,5],[5,－1]]key=int(input("请输入要删除的数据:"))head=delete(L,key)#输出删除后的结果程序省略画线处应填入的代码依次是(

)①data[cur][0]!=panddata[cur][1]!=－1②data[cur][0]!=pandcur!=－1③data[pre][1]=data[cur][1] ④data[cur][1]=data[pre][1]A.①③ B.①④C.②③ D.②④C【解析】本题考查链表的基础操作知识。(1)处要完成的功能是,若当前节点cur的值不等于要删除的数p,且当前节点不是尾节点时,依次往下遍历,实现过程是迭代,即先将当前节点cur赋值给前驱节点pre,然后cur继续往下走一步,因此在①②代码中,②的表达式正确。(2)处实现的功能是,若找到需要删除的数据,且该节点不是尾节点时删除当前节点。分析代码可知,cur是当前节点,而pre是cur的前驱节点,因此删除的数据的正确代码是前驱节点pre直接指向当前节点cur的后继节点data[cur][1],即data[pre][1]=data[cur][1],因此在③④中选择③。C正确。9.给定一个链表a,以表头元素为基准数,将小于基准的节点移动到它的左侧,且保持节点相对顺序不变;大于基准的节点保持不动。如图1所示的链表处理后的结果如图2所示。实现该功能的程序段如下,head为头指针。pivot

=

a[head][0]p,

r

=

head,

－1while

a[p][1]

!=

－1:

q

=

a[p][1]

if

a[q][0]

<

pivot:

a[p][1]

=

a[q][1]

r

=

q

else:

p

=

a[p][1]图1

图2

A.if

r

==

－1:

a[q][1]=p

head=q

else:

a[r][1]=a[q][1]

a[q][1]=rB.if

r

==

－1:

a[p][1]=q

head=q

else:

a[r][1]=a[p][1]

a[q][1]=rC.if

r

==

－1:

a[p][1]=q

head=q

else:

a[q][1]=a[r][1]

a[r][1]=qD.if

r

==

－1:

a[q][1]=head

head=q

else:

a[q][1]=a[r][1]

a[r][1]=q则方框中应填入的代码是(

)D【解析】本题考查链表知识。第5行元素值的比较可以看出,q节点表示当前待移动的节点,p节点是它的前一个节点。第6行相当于让q的前一个节点指向q的后一个节点,即跳过了q节点。第8行程序让r指向q节点,而q是最后一次移动的节点,因此r可以看成左侧链表的尾节点。第10行是q节点的值大于等于基准的情况,这时p直接往后移一位,那么p就是基准右侧链表的最后一个节点。对于四个选项的条件都是r为－1的情况,即r还未指向任何一个节点,也相当于左侧链表为空的情况。这时可以让q节点的下一个节点指向右侧节点的第一个节点,即p或者head节点(如选项A和D所示)。当r指向一个实际元素时,新元素应该如何插入?放在r的前面还是r的后面?这也是选项A和选项D中“else”分支语句的差别。考虑到题目中要求元素移动后保持相对顺序不变,后插入的元素应该在前插入的元素后面,因此元素应该插在r的后面。选项A将q节点插在了r的前面。选项D将q节点插在了r的后面,D正确。选项B和C,在if分支中的逻辑与第6行程序有冲突。10.有如下Python程序段:

a=[[1,3],[1,0],[7,1],[4,5],[1,－1],[6,4]]

x=1

p=head=2

if

x==a[p][0]:

head=a[p][1]

else:

while

p!=－1:

if

x==a[p][0]:

a[pre][1]=a[p][1]

else:

pre=p

p=a[p][1]

运行该段程序后,a[2][1]的值为(

)A.－1 B.0C.1 D.3【解析】本题考查链表的遍历及删除节点操作。阅读代码可知,选择结构部分的操作为:当x为当前链表头指针所指的节点的数据,那就删除头节点,如果不是就遍历后续节点并删除数据域为1的节点。因为删除需要记录当前节点的前驱节点,使用pre来存储。原链表为7→1→1→4→6→1。故删除了数据域为1的节点之后,数据7直接指向了数据4,故a[2][1]为3,D正确。D11.使用列表d模拟链表结构(节点数大于1),每个节点包含起始数值、连续长度、指针区域,h为头指针。链表中各节点已按起始数值由小到大排列,各个节点表示的数值区间不重叠,例如链表d为[[20,100,3],

[150,50,2],

[250,60,

－1],

[120,30,1]],h=0,其中节点[20,100,3]表示从数值20开始有长度为100的连续值(20到119),3代表后继节点索引为3,现要合并链表各节点连续的数值区间,合并后链表d的数据修改为[[20,

180,2],

[150,

50,

2],

[250,

60,

－1],

[120,

30,

1]],h=0。实现该功能的Python程序段如下。q=h=0p=d[q][2]while

p!=－1:

if

d[p][0]==d[q][0]＋d[q][1]:

d[q][1]=d[q][1]＋d[p][1]

else:

(1)

(2)

(3)

上述程序中方框处可选语句如下:①q=p

②d[q][2]=p

③p=d[p][2]加框处的代码依次是()A.①、②、③ B.①、③、②C.②、①、③ D.②、③、①【解析】本题考查链表的基础知识。分析代码可得,p是当前节点,q是p的前驱节点。如果q、p指向链表相邻两个节点的数值区间连续,则将两个节点进行合并,更新q节点的连续长度(即q节点的连续数值长度加上p节点的连续数值长度)。同时q节点的指针域需要指向当前p节点的后继节点。否则,将指针q的值更新为p,指针p后移指向下一节点。B正确。B12.链表a中各节点由数据域和指针构成,并按数据域数值升序排列(头节点数据为奇数),现要修改各节点顺序,按奇数在前升序、偶数在后升序的顺序排列,如图所示。实现该功能的程序段如下。a

=

[[8,1],[9,－1],[6,0],[1,5],[5,2],[2,4]]p

=

t

=

head

=

3while

a[t][1]

!=

－1:

k

=

a[t][1]

if

a[k][0]

%

2

==

1:

else:

t

=

a[t][1]A.a[t][1]

=

a[p][1]

a[p][1]

=

t

p

=

t

t

=

kB.a[t][1]

=

a[k][1]

a[k][1]

=

a[p][1]

a[p][1]

=

k

p

=

a[p][1]C.a[p][1]

=

t

a[t][1]

=

a[p][1]

p

=

a[p][1]

t

=

kD.t

=

a[t][1]

a[k][1]

=

a[p][1]

a[p][1]

=

k

p

=

k【解析】本题考查链表操作。本题的重点是理解几个指针的作用:p,t从头节点(奇数)出发,k为t的后继,若a[k][0]为偶数,则t指针后移……直到a[k][0]为奇数时才停止,此时t为连续偶数的最后一个,接下来从原位置删除k点(a[t][1]=a[k][1])。将k点连接到p之后:a[k][1]=a[p][1];a[p][1]=k。p指针后移,保留奇数段的链尾:p=a[p][1]。B正确。则方框中应填入的代码是(

)B13.利用链表实现升序排序:二维列表a同时保存数据域和指针域,排序的过程就是将每个数据的指针域不断链接到已有的有序链表的合适位置,直到所有的数据均链接到链表中。例如,将某节点插入到已有链表中,根据大小比较有三种情况:插入到最前面、插入到最后、插入到中间。具体程序设计方法如下:①将待排序的n个数保存在列表a中,且指针域的值均为－1,形成n个没有链接的节点。②将每个节点看成只含有一个节点的链表head,且head=0。③将第i个节点插入到链表head的适当位置,使head仍有序,此时head成为含有两个节点的有序链表;以此方法依次将a列表中的其他节点插入到链表head中,最后链表head上包含所有节点,且节点有序。依次输出head链表的数据域即可完成排序。程序运行界面如图所示,采用此思想进行升序排序的Python代码如下,请回答下列问题:原始链表为:[[43,－1],[68,－1],[25,－1],[17,－1],[52,－1]]排序后链表:[[43,4],[68,ˈ－1],[25,0],[17,2],[52,1]]排序后数据:17

25

43

52

68#随机生成列表a的数据域的值,且指针域全部为－1,代码略n

=

len(a)print("原始链表为:",a)head=0for

i

in

range(1,n):

①_____________

ifa[k][0]>=a[i][0]:

a[i][1]=k

head=i

else:

whilea[i][0]>a[a[k][1]][0]:

#改错

k=a[k][1]

a[i][1]=a[k][1]

②____________

print("排序后链表:",a)print("排序后数据:",end="")k=headwhilek!=－1:

print(a[k][0],end="")

③______________

k=heada[k][1]=ik=a[k][1](1)若用该算法进行升序排序,a=[[46,

－1],

[19,

－1],

[10,

－1],

[37,

－1]],排序完成后,head变量的值为__________。

(2)为实现上述功能,请在画线处填入合适的代码。(3)加框处代码有错误,请改正。【答案】a[i][0]>

a[a[k][1]][0]and

a[k][1]!=－1【解析】本题考查链式存储的插入排序算法。(1)链表是通过head进行遍历数据,升序排序时,最小值下标为2,故head值为2。(2)①此处表示插入的节点位于最前面的情况,故答案是k=head,为了避免head的值发生改变,因此使用k模拟head指针。②此处寻找插入位置,若插入数据a[i][0]大于当前值,则找下一个节点,直到到达链表的最后一个节点,若找到位置,则先更新i的下一个为k的下一个,再更新k的下一个为i节点(顺序不可更改)。③此处通过k(相当于head)遍历整个链表,并输出数据域,下一个节点的位置是k=a[k][1]。(3)否则继续循环每个节点,将节点i和当前遍历节点k的下一个节点进行比较,所以找到的k为第一个大于i的节点的前一个节点。除了考虑比较大小外,还必须考虑a[k][1]的值不能为－1(－1表示尾部)。214.某花瓶厂有三台不同型号的机器,可生产ABC三种不同型号的花瓶。厂家每天会收到很多网上订单,每个客户的订单信息包含订单号、型号、数量和状态,其中状态值为1表示确认订单,－1表示取消订单。工作人员首先挑选出确认的订单,然后对着订单按花瓶型号进行分类统计,最后交给生产部门生产。订单信息存储在“orders.csv”文件中,文件的数据格式如图1所示。请回答下列问题:(1)若某天的订单如图2所示,则当天应生产的B型号花瓶数量为__________个。

订单号型号数量状态S001A10001S002B20001S003B1500－1S004C9001S005B8001S006C7001S007A500－1S008B6001图1

图2

3400(2)定义如下readdata()函数,函数功能是从订单文件中挑选出确认的订单,并将订单的订单号、型号和数量存储在列表orders中,程序画线处应填入的代码为__________。

def

readdata():

import

csv

f=open("orders.csv","r",encoding="utf－8")

f_csv=csv.reader(f)

title=next(f_csv)

#读取标题行

for

l