资源简介

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]][1] = pt
②data[qt][1] = data[pt][1]
③data[pt][1] = data[data[pt][1]][1]
则方框处代码的正确顺序是（ ）
A．①②③ B．①③② C．②①③ D．②③①
11．用两个列表a、b分别保存单向链表中的数据区域和指针区域。如下图所示，在节点x与节点y之间插入一个新节点，操作步骤正确的是（ ）
①b[i]= b[y] ②b[i]= b[x] ③b[y]= i
④b[x]=i ⑤b[i]= x ⑥b[i]= y
A．③⑥ B．④② C．①③ D．②④
12．使用列表d模拟链表结构（节点数大于0），每个节点包含数据区域和指针区域，h为头指针。下列程序段实现了删除数据区域为奇数的节点。
q=p=h=2
while p！=-1：
if d[h][0]%2==1：
（1）
q=p=h
elif d[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．②④
13．利用列表模拟某单向非循环链表a(其中可能存在已被删除的节点），下列程序运行完毕后，变量p肯定表示尾节点的节点位置的是（　　）
A． B． C． D．
14．如果一个链表的头指针为head，要访问链表中第i个节点，需要进行几次指针移动（ ）
A．i次 B．i-1次 C．i+1次 D．无法确定，取决于链表长度
15．使用列表a模拟链表结构（节点数大于0），每个节点包含数据区域和指针区域，head为头指针，如a=[["Z"，2]，["J"，0]，["H"，-1]，["S"，1]]，head=3，现要修改该链表各节点的链接关系，修改结果为a=[["Z"，1]，["J"，3]，["H"，0]，["S"，-1]]，head=2。实现该功能的程序段如下，方框中应填入的正确代码为（ ）
q=head;p=-1
while q!=-1：

head=p
A． a[q][1]=p nxt=a[q][1] p=q q=nxt B． a[q][1]=p nxt=a[q][1] q=nxt p=q C． nxt=a[q][1] a[q][1]=p q=nxt p=q D．nxt=a[q][1] a[q][1]=p p=q q=nxt
A．A B．B C．C D．D
二、填空题
16．在数据结构中， 是一种允许在任何位置插入和删除元素的数据结构。
三、操作题
17．现有n条编码（每条编码占1行，编号1到n）存储于某文本文件中，使用字符“：”对每条编码进行分隔，形成若干段，如图a所示。任一条编码的每一段均以十六进制形式表示（字母大写），最左段编码对应的十六进制数大于0。编写一个Python程序，实现对文件中所有编码的升序排序。
实现对编码排序的方法如下：排序处理前，需对每一条编码按从右到左进行段编号，如图b所示。首先从编号为1的段开始，根据每条编码在第1段的内容，对编码编号进行排序，再按编号为2的段进行排序，……，直至完成各段编码的处理。
图a 图b
请回答下列问题：
（1）各段排序的加工遍数为该段所对应编码的最长位数。现若仅对图b中所示的前4条编码进行排序，第1段编码的部分加工过程如下表所示，则第4遍加工完成后的编码编号次序为 （单选，填字母。A．3->1->2->4 /B．1->3->4->2）。
编码比较（从右向左第i位） 加工结果（编码编号次序）
原始内容 AE F3B AD 7AA6 1->2->3->4
第1遍加工 7AA6 F3B AD AE 4->2->3->1
第2遍加工 F3B 7AA6 AD AE 2->4->3->1
第3遍加工 AD AE 7AA6 F3B 3->1->4->2
（2）定义如下pick（hex，i）函数，函数功能是返回十六进制数hex从右向左第i位（1≤i）的值。
def pick（hex，i）：
dic= {'0'：0，'1'：1，'2'：2，'3'：3，'4'：4，'5'：5，'6'：6，'7'：7，'8'：8，'9'：9，'A'：10，'B'：11，'C'：12，'D'：13，'E'：14，'F'：15}
if i>len（hex）：
return 0
t= return dic[t]
为实现该函数功能，方框内的语句应修改为：
（3）实现第k段编码处理功能的Python程序如下，程序中用到的列表函数与方法如图c所示，请在程序中划线处填入合适的代码。
函数与方法 功能
w.append（x） 在列表w末尾添加元素x
w.pop（x） 将列表w中索引为x的元素从w中删除
图c
def process（k，lenk）： #根据第k段编码从右向左第i位的值，进行升序排序
for i in range（1，lenk+1）：
bucket=[]
for j in range（16）： # bucket[i]（0≤j≤15）列表存放值为j的编码编号
bucket.append（[]）
p=nex[Head]
while p！=-1：
①
bucket[t].append（p）
p=nex[p]
p=Head
for j in range（16）：
while ② :
t=bucket[i][0]
nex[p]=t；p=t；nex[p]=-1
bucket[j].pop（0）
``` 读取1至n条编码数据，各编码分段处理后依次存入列表data的data[1]至data[n]中，
图b中第1、2条编码分别存放在data[1]，data[2]中，data-[[]，[76A'，'0'，'9B'，'AE']，['9F'，'7A7'，'F3B']，……]，代码略 ```
nex = [-1]*（n+1）
Head=0；nex[Head]=1；maxk= 0
for i in range（1，n+1）：
nex[i] = i+1
maxk = max（maxk，len（data[i]））
nex[n]=-1
res =[] #res 列表中存放已排序的编码编号
for k in range（1，maxk+1）：
pre= Head；cur=nex[Head]；lenk=0
while cur！=-1：
if k <= len（data[cur]）：
lenk = max（lenk，len（data[cur][-k]））
pre=cur
else：
res.append（cur）
③
cur=nex[cur]
process（k，lenk）
# 按升序输出处理后的所有编码，代码略
18．某音乐平台的曲库中共有n首（编号为0~n-1）歌曲，每首歌曲初始的热度值均为0。歌曲列表分为热榜区和非热榜区，热榜区按热度值降序排列，若热度值相同则按歌曲编号升序排列；非热榜区按歌曲编号升序排列，某时刻的榜单如图a所示。用户对歌曲的操作会改变其热度值，规则如图b所示。
初始状态时，n首歌曲都在非热榜区，若某歌曲的热度值大于等于预设的阈值时，则将其移至热榜区；相反，若热榜区中某歌曲的热度值小于预设的阈值时，则将其移至非热榜区。
现有一段时间内的操作记录存储在"operation.csv"文件中，部分数据如图c所示，编写Python程序模拟两个榜区歌曲的实时更新功能。

图a 图b 图c
（1）若该曲库中有三首歌曲，编号分别为0、1、2，初始热度值均为0，热榜阈值为3。经过图c所示的若干个操作后，最终热榜区显示的歌曲编号依次为 。
（2）定义函数printsongs（headA,headB），其功能是输出某次操作后songs中的歌曲榜单信息。如图a所示的歌曲榜单，该曲库中共有10首歌。此时headA和headB的值分别为6和0；编号8、9的歌曲数据在列表中分别表示为songs[8]、songs[9]，其值分别为[8,-2,"悬溺",-1]、[9,8,"如果这就是爱",0]。
函数printsongs代码如下，请在划线处填入合适的代码。
def printsongs（headA,headB）:
print（"###热榜歌曲###"）
p=headA
while p!=headB:
print（"歌曲编号:",songs[p][0],"歌曲名:",songs[p][2],"热度值:",songs[p][1]）
print（"###非热榜歌曲###"）
while p!=-1:
#其他代码略
（3）实现曲库从非热榜区移至热榜区或更新热榜区的部分Python程序如下，请在划线处填入合适的代码。
'''
读取曲库和操作数据，分别存入列表songs和op中。songs中的每个元素包含三个数据项，分别对应歌曲的编号、热度值、名称。op中每个元素包含两个数据项，分别对应歌曲编号和操作编号。代码略
'''
inc=[0,1,3,-5] #操作编号对应的数值变化
val=int（input（'请输入热榜阈值'））#阈值设置
for i in range（0,len（songs）-1）:
songs[i].append（i + 1）
songs[len（songs）-1].append（-1）
headA,headB=0,0
for x in op:
p,q=headA,headA
while q!=-1 and songs[q][0]!=x[0]:
p=q
q=songs[q][3]
if q==-1:
print（"未找到该歌曲"）
else:
tmp=songs[q][1]#修改前的热度值
songs[q][1]+=① #修改后的热度值
if（tmp=val） or（songs[q][1]>=tmp>=val）:#上热榜或升榜
px, py=headA,headA
while py!= 1 and（songs[py][1]>songs[q][1]or ② ）:
px=py
py=songs[py][3]
if q==headB:
headB=songs[headB][3]
if py != q:
songs[p][3]= songs[q][3]
③
if py == headA or headA == headB:
headA=q
else:
songs[px][3]=q
printsongs（headA,headB）#输出当前操作后的榜单
#其他情况代码略
参考答案：
1．B
2．B
3．A
4．A
5．B
6．C
7．D
8．C
9．A
10．D
11．D
12．C
13．B
14．B
15．D
16．链表（或LinkedList）
17． A hex[-i]或hex[len（hex）-i] t=pick（data[p][-k], i） len（bucket[i]）>0或len（bucket[i]）>=1或bucket[i]！=[] nex[pre]=nex[cur]
18． 0，2 p= songs[p][3] inc[x[1]] songs[py][1]==songs[q][1] and songs[py][0]

展开更多......

收起↑