2.2链表作业浙教版选修一

2.2链表一、选择题1．有如下Python程序段：defpoem(1st,q,flag):

st=""

foriinrange(7):

st+=1st[q][0]

q=1st[q][flag]

print(st)hw=[["冬",1,1],["梅",0,2],["枝",1,3],["几",2,4],["点",3,5],["雪",4,6],["花",5,7],["开",6,8],["春",7,9],["信",8,10],["来",9,0]]p=head=0flag=1;step=3foriinrange(2):

p=hw[head][flag]

poem(hw,p,flag)#①

forjinrange(step):

p=hw[p][flag]

poem(hw,p,flag)#②关于上述程序段的说法，不正确的是(

)A．语句①第一次执行时，输出“梅枝几点雪花开” B．语句②第二次执行时，输出“开花雪点几枝梅”C．若加框处语句改为flag+=(1)**i，不会影响程序运行结果 D．若将hw中的["梅",0,2]修改为["梅",0,3]，输出结果将不含文字“枝”2．某个正整数的每位数依次存储在链表d中各节点的数据区域中。例如，正整数572存储情况如图a所示，h为d的头指针。将该正整数翻倍后的计算结果（如572翻倍后的结果为1144）仍以这个链表存储，最高位存储于头节点中，如图b所示。实现该功能的程序段如下：

图a

图bifd[h][0]>4:d.append([0,h])

#链表d新增一个节点h=len(d)1p=hwhilep!=1:d[p][0]=d[p][0]*2%10cur=d[p][1]p=d[p][1]方框中应填入的正确代码为（

）A．ifcur!=1andd[cur][0]>4:d[p][0]+=1B．ifcur!=1andd[p][0]>4:d[cur][0]=(d[p][0]*2+1)//10C．ifcur!=1andd[cur][0]>4:d[p][0]+=(d[cur][0]*2+1)%10D．ifcur!=Iandd[p][0]>4:d[cur][0]+=13．某Python程序如下：a=[[3,2],[2,3],[7,1],[1,0]]p=head=0whilea[p][1]!=head:

print(a[p][0],end='>')

p=a[p][1]print(a[p][0])程序运行后，输出的结果是（

）A．3>7>2>1 B．3>2>7>1 C．1>7>3>2 D．3>7>1>24．有如下Python程序段defbianli(head):pt=headwhilept!=1:print(data[pt][0],data[pt][1],">",end='')pt=data[pt][1]print()data=[['A',1],['B',2],['C',3],['D',1]]head=0bianli(head)

#遍历链表，显示初始状态为“A1>B2>C3>D1>”qt=headpt=data[qt][1]bianli(head)#遍历链表，显示最终状态为“A2>C1>B3>D1>”执行该程序段后，链表遍历结果由初始状态变为最终状态，上述程序段中方框处可选代码为：①data[data[qt][1]][1]=pt②data[qt][1]=data[pt][1]③data[pt][1]=data[data[pt][1]][1]则方框处代码的正确顺序是（

）A．①②③ B．①③② C．②①③ D．②③①5．使用列表d模拟链表结构（节点数大于0）每个节点包含数据区域和指针区域，h为头指针。链表中各节点已按数据区域中数值的绝对值由小到大排列，如图a所示。现要修改该链表各节点的链接关系，使链表各节点按数据区域中的数值由小到大排列，结果如图b所示。实现该功能的程序段如下，方框中应填入的正确代码为（

）图a

图bt=hp=d[h][1]whilep!=1:

q=d[p][1]

p=qd[t][1]=1A． B． C． D．6．小张准备去多个城市旅游，他设计的行程若采用链表结构表示，如图a所示。

图a图b若行程有变，需在“上海”与“成都”之间增加一站“杭州”，链表修改为如图b所示，有以下可选操作：①“上海”所在节点的next值赋为“杭州”所在节点的next值②“上海”所在节点的next值赋为5③“杭州”所在节点的next值赋为“上海”所在节点的next值④“杭州”所在节点的next值赋为1链表更新顺序正确的是（

）A．③② B．③① C．①④ D．②④7．用两个列表a、b分别保存单向链表中的数据区域和指针区域。如下图所示，在节点x与节点y之间插入一个新节点，操作步骤正确的是（

）①b[i]=b[y]

②b[i]=b[x]

③b[y]=i

④b[x]=i

⑤b[i]=x

⑥b[i]=yA．③⑥ B．④② C．①③ D．②④8．双向链表中有两个指针域llink和rlink，llink指向当前节点的前一个节点，rlink指向当前节点的后一个节点。假定链表中节点数大于3个，p指向链表中的某一个节点（p不是头节点），现要求删除p所指的节点，则下列操作能实现的是（

）A．p.llink.rlink=p.rlinkB．p.llink.rlink=p.rlinkC．p.rlink.llink=p.llink；p.llink.rlink=p.rlinkD．p.llink.rlink=p.llink；p.llink.rlink=p.rlink9．在日常幻灯片的放映中，可以通过超级链接方式进行幻灯片之间的任意跳转。和这种跳转方式相似的数据结构是（）A．数 B．链表 C．队列 D．栈10．有如下图所示的单向链表：从头指针head指向的节点开始查找数据元素“5”，并删除该节点，下列说法正确的是（

）A．共需查找3次 B．删除数据元素“5”的节点，后续节点需要移动3次C．头指针head将指向数据元素“7”的节点 D．操作完成后，链表中数据元素的个数为6个11．在单向链表如下图所示，在data2与data3之间插入一个新节点data4（p指向data2，r指向data4。列表data来记录链表数据域，列表next来记录指针域），在以下选项中选择正确的执行步骤（

）①next[p]=next[r]

②next[p]=r

③next[r]=p④next[r]=1

⑤next[r]=next[p]

⑥next[p]=1A．③⑥ B．⑤② C．①④ D．⑤②④12．给定两个相交的单链表均存储在列表link中，头节点分别是headA和headB，用最少的循环次数找出两个链表相交的起始点。如图所示，两个链表在节点c1开始相交。p1,p2=headA,headBc=0while(1):

ifp1!=1:

p1=link[p1][1]

else:

(2)

ifp2!=1:

p2=link[p2][1]

else:

(3)

c+=1print(f'循环{c}次后找到交叉点{link[p1][0]}')上述程序段划线出可选的代码为：①p1!=p2

②p1!=1andp2!=1

③p1=headB

④p2=headA则(1)、(2)、(3)处可选的代码依次为（

）A．①③④ B．②③④ C．①④③ D．②④③13．寻宝游戏中通过一个线索找到下一个线索，最好用下列数据组织形式中的（

）来表示。A．数组 B．链表 C．栈 D．队列14．在一个单向链表（如图)中，若在尾指针tail所指节点之后插入新节点(r所指节点），则执行的操作是()A．tail所指节点的data3值赋为r所指节点的data4值B．r所指节点的next值赋为tailC．r所指节点的next值赋为－lD．tail所指节点的next赋为r,r所指节点的next值赋为－l15．使用链表结构模拟某景区游玩路线，链表a中每一个节点包含三个数据，第1个为景点名称，第2个为预计游玩时间（单位：分钟），第3个为下一个景点指针。景区可以从多个景点的大门进入，但只能从"天梯"离开，输出显示各大门进入路线及预计总时间的代码如下。a=[["迎客松",21,2]，["激流勇进",40,2]，["天空栈道",50,5]，["一线天",30,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．②④③16．现采用新的排队方案为小明、小红、小丽、小辉四人排队，Python程序段如下：linklist=[["小明",1],["小红",2],["小丽",3],["小辉",1]]defreset(head):

iflinklist[head][1]==1orhead==1:

returnhead

else:

new_head=reset(linklist[head][1])

linklist[linklist[head][1]][1]=head

linklist[head][1]=1

returnnewheadp=h=reset(0)whilep!=1:

print(linklist[p][0],end="")

p=linklist[p][1]执行该程序段后，输出的结果是（

）A．小明小红小丽小辉 B．小明小辉小丽小红C．小辉小丽小红小明 D．小明小丽小红小辉17．使用列表da和db模拟2个链表结构（节点数均大于0），每个节点包含数据区域和指针区域，ha和hb分别为链表da和db的头指针。链表中各节点已按数据区域中数值由小到大排列，且链表da头节点值小于链表db头节点值。现要将链表db中数据合并到链表da中，且保持升序排列。实现该功能的程序段如下，方框中应填入的正确代码为（

）q=hawhilehb!=1：p=da[q][1]A．ifp==1orda[p][0]>db[hb][0]：da．append（[db[hb][0]，p]）da[q][1]=len（da）1hb=db[hb][1]q=da[q][1]B．ifp==1orda[p][0]>db[hb][0]：da．append（[db[hb][0]，p]）da[q][1]=len（da）1hb=db[hb][1]q=da[q][1]C．ifp==1orda[p][0]>db[hb][0]：da．append（[db[hb][0]，p]）da[q][1]=len（da）1hb=db[hb][1]q=pD．ifp==1orda[p][0]>db[hb][0]：da．append（[db[hb][0]，p]）da[q][1]=len（da）1hb=db[hb][1]q=da[q][1]A．A B．B C．C D．D18．已知一个有7个节点的单向链表，设有头指针head和尾指针tail，如右图所示，下列操作需要遍历多个节点的是（

）A．删除该链表中的最后一个节点B．删除该链表中的第一个节点C．在该链表第一个节点前插入一个新节点D．在该链表最后一个节点后插入一个新节点19．王老师用链表模拟某次比赛中运动员的出场次序，运动员号码存储如下：a=[[“056”，4]，[“134”，1]，[“215”，5]，[“098”，0]，[“144”，2]，[“024”，1]]。假设head=3，小明同学的号码是“215”，则他的出场次序是（

）A．2 B．4 C．5 D．620．在Python中可以使用列表模拟单向链表，如链表中的节点p，a[p][0]存储p节点的数据，a[p][1]存储p指向后继节点的指针。若要在p节点之后插入新的节点x（x作为p的新后继节点），需要执行的语句是（

）A．a[p][1]=x;a[x][1]=a[p][1] B．a[x][1]=a[p][1];a[p][1]=xC．a[p][0]=x;a[x][0]=a[p][0] D．a[x][0]=a[p][0];a[p][0]=x参考答案：1．D【详解】本题考查链表的综合应用。原循环双向链表是：冬→梅→枝→几一点→雪→花一开→春→信一来→冬，第1次从p节点开始输出七言，再跳3个节点，继续输出七言。第2次反向从p节点开始输出七言，再跳3个节点，继续输出七言。因此依次输出4句话是梅枝几点雪花开，点雪花开春信来，来信春开花雪点，开花雪点几枝梅。因此AB选项正确。C选项，i=0时，flag+=(1)**i=2，切片效果等效flag=1。i=1时，flag+=(1)**i=1。因此C也正确。D选项，修改后，第4次输出还是含有枝。故本题应选D。2．A【详解】本题考查链表节点插入知识。根据代码可知，当最高位数d[p][0]大于4(即5以上)时，其翻倍后的数将产生进位，因此需要新增加一个节点(默认在数据域插入0)，并将其作为新的头节点h。p为高位节点，cur为p的后继节点(节点cur是节点p的低位)。该利用链表实现的乘法算法的顺序和常规乘法是相反的：先计算高位p然后再计算低位cur，p节点的数据域是本位d[p][0]的2倍然后%10后的值，但这还不是d[p][0]的终值，还要看p的低位cur有没有产生进，若cur的数据域d[cur][0]大于4，则还会向p节点的数据域产生进位，由于最大的单位数9的2倍，其进位也只是1，因此每次在p节点原先的数据域d[p][0]基础上加1即可实现进位操作。若没有产生进位则依次从高位向低位进行迭代，直到链表遍历结束为止，综上述，本题应该选A。3．A【详解】本题考查的是链表相关知识。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。a[p][1]是链表的指针，a=[[3,2],[2,3],[7,1],[1,0]]，故输出：3>7>2>1。选项A正确。4．D【详解】本题主要考查链表及其Python程序实现。本程序考查的是链表的重新链接，程序实现的效果是A1>B2>C3>D1>，变为A2>C1>B3>D1>，qt指前一指针，pt指后一指针，故‘A’要指向‘C’,‘B’要指向‘D’,然后‘C’要指向‘B’，即正确的顺序是，故本题选D选项。5．C【详解】本题考查单链表及分支语句和数据排序等知识。由于数据区域中数值的绝对值由小到大排列，由代码可知，原先的节点关系是：t→p→q，若数据区域d[p][0]的数值为正数，则原链表节点关系不变，只需将各节点关系往下迭代即可，即：t变为p，p变为g即可。若数据区域d[p][0]的数值为负数，则原先的链表各节点关系需要重新指向，由于原数据是按照绝对值大小排序的，因此越往后面绝对值数越大，因此其相反数(负数)就越小，这样每一个当前节点p的负数肯定是当前链表中最小的数，因此该数应该变为最小的头节点，采用头插法可以实现，即将当前节点p的指针域指向原先的头节点h，然后再将头节点h变为当前节点p。故本题选C。6．A【详解】本题考查链表的操作。若行程有变，需在“上海”与“成都”之间增加一站“杭州”，链表修改为如图b所示，则首先杭州所在的节点指向成都，即③“杭州”所在节点的next值赋为“上海”所在节点的next值。其次上海指向杭州，即②“上海”所在节点的next值赋为5。故选A。7．D【详解】本题主要考查链表数据结构。在节点x与节点y之间插入一个新节点i前x与y相连，b[x]=y，插入i后需要将i连接进来，首先将i节点与y相连接，即②b[i]=b[x]=y，再将x与i连接起来，即④b[x]=i，故本题选D选项。8．C【详解】本题考查双向链表。双向链表中，每个节点有两个指针域，分别指向前一个节点和后一个节点。当要删除某个节点时，需要将该节点前后两个节点的指针重新连接起来，以维持链表的连续性。而操作p.rlink.llink=p.llink是将p节点后一个节点的llink指针指向p节点前一个节点，而p.llink.rlink=p.rlink是将p节点前一个节点的rlink指针指向p节点后一个节点，两者均能实现删除p节点的目的。故答案为：C。9．B【详解】本题考查的是对数据结构的理解。链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。链表由一系列数据结点构成，每个数据结点包括数据域和指针域两部分。其中，指针域保存了数据结构中下一个元素存放的地址。链表结构中数据元素的逻辑顺序是通过链表中的指针链接次序来实现的。故选项B正确。10．D【详解】本题考查的知识点是链表数据结构。从头指针head指向的节点开始查找数据元素“5”，“5”是第4个元素，共查找4次。删除节点时，找到要删除的节点后，修改其前一个节点的指针域，使其指向要删除节点的下一个节点，后续节点不存在移动。由于删除的是第三个节点，因此头指针head将指向第四个节点，即数据元素为“1”的节点。操作完成后，链表中数据元素的个数为6个。故答案为D选项。11．B【详解】本题主要考查链表的操作。在data2与data3之间插入一个新节点data4，p指向data2，r指向data4，则正确的步骤是，先将r的next指针域指向p的next节点，其次更新p的next为r，故分别是：next[r]=next[p]和next[p]=r，故本题选B选项。12．C【详解】本题考查数据结构。首先，需要判断两个指针p1和p2是否相等，即链表是否相交。这可以通过比较节点的地址来实现，因此划线处应选择代码①p1!=p2。当p1指针达到链表末尾时，应该将其重新指向另一个链表的头节点，以继续遍历。因此，划线处应选择代码③p1=headB。同样，当p2指针达到链表末尾时，应该将其重新指向另一个链表的头节点。因此，划线处应选择代码④p2=headA。故答案为：C。13．B【详解】本题考查的是链表相关知识。链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。寻宝游戏中通过一个线索找到下一个线索，最好用链表来表示，故选B选项。14．D【详解】本题主要考查链表的操作。链表中尾结点的next指针为1，若在尾指针tail所指节点之后插入新节点(r所指节点），则执行的操作是：tail所指节点的next赋为r，r所指节点的next值赋为－l，故本题选D选项。15．D【详解】本题考查链表结构。链表结构模拟景区游玩路线的程序中，需要注意如下的逻辑：(1)处：应该设置当前节点的指针p为head[i]，表示第i个大门的开始路线，即p=head[i]。（2）（3）处注意s的初值为a[p][