链表+算法综合四
班级 姓名
1.【202303平湖模拟】
① a[slow][1] （1 分）
② pre = cur （2 分）
③ a[h1][1] = h2 （2 分）
④ i//2+1 （2 分）
⑤ a[mid][1] = -1 （2 分）
2.【202304杭州地区四校联考】
(1)2 (1分)
(2) ①ch=dic[i][0][0] (2分）
②data[tmp[ord(ch)-97]]=i (2分）
③p!=-1 (2分）
④data[p][1] (2分）
(3)B (1分）
3.D
4.C链表+算法综合四
班级 姓名
1.【202303平湖模拟】小胡公司组织四人制篮球赛(2人对2人)，现已报名 n(n为偶数)人，根据这n人的个人篮球赛成绩降序排序后存于单向链表a中，为使每队实力尽量均衡，将a中第1人和最后一人组队，第 2人和倒数第2人组队，以此类推。例如有6名编号为 T01、T02、T03、T04、T05、T06 的队员报名参赛，按个人篮球赛成绩降序排序后的次序为：T05、T06、T02、T03、T04、T01，经过分组后分组情况如下图所示:
具体算法为：
(1)找到链表的中点
(2)将链表的右半段反转
(3)将链表左半段和反转后的右半段合并
(4)按顺序输出每组队员编号
小胡编写程序实现将这n人进行分组并输出每组队员编号，请在划线处填入合适的代码。
#找到原链表的中点
def middleNode(head):
slow=fast=head
while a[fast][1] != -1 and a[a[fast][1]][1] != -1:
slow=①________ ___
fast=a[a[fast][1]][1]
return slow
#将原链表的右半段反转
def reverseList(head):
pre=-1 ; cur=head
while cur!=-1:
nextTemp=a[cur][1] ; a[cur][1]=pre
②____________ _
cur=nextTemp
return pre
#将原链表的两段合并
def mergeList(h1, h2):
while h1!=-1 and h2 !=-1:
h1_tmp=a[h1][1] ; h2_tmp=a[h2][1]
③_____________ __
h1=h1_tmp ; a[h2][1]=h1 ; h2=h2_tmp
#输出分组情况
def show():
head=0 ; i=0 ; print('分组情况：')
while head!=-1:
if i % 2==0:
print('第', ④__________ __, '组：', a[head][0], '和 ', end='')
else:
print(a[head][0])
i+=1
head=a[head][1]
#读入n人编号，并按个人篮球赛成绩降序排序后依次将编号存入a中并输出a（代码略）
mid=middleNode(0)
head1=0
head2=a[mid][1]
⑤____________ __
head2=reverseList(head2)
mergeList(head1, head2)
show()
2.【202304杭州地区四校联考】张老师制作了一个python英汉词典用来帮助大家更好的学习，该词典dic收集了python的关键字、常用函数、专业名词及其中文含义。词典中的英文单词无序，且皆为小写。为了方便查询、扩展等，张老师在不改变元素位置情况下，对全部单词按首字母进行了分组，分组信息存储在data中。查询时只要先确定待查找单词的首字母，找到所在分组，然后在该组中依次比对即可。若找到则输出其中文含义，否则输出“找不到”。
(1)若dic=[['and', '与'], ['end', '结束'], ['or', '或'], ['else', '否则'], ['not', '非'], ['even', '偶数']]，按下列程序代码运行，查找单词else的查找次数为 次。
(2)Python程序如下，请在划线处填入合适的代码。
from readtxt import dic #dic是一个列表，从另一个文件readtxt.py中生成
#它每个元素都有两个数据项，第一项是英文单词，第二项是中文含义
#如dic=[['print','打印/输出'],……]，所有单词都是小写，且无序
data=[] ; ln=len(dic)
for i in range(ln):
data.append([i,-1])
headindex={}
for i in range(26):
headindex[chr(97+i)]=-1
tmp=[-1]*26
for i in range(ln):
①
if headindex[ch]==-1:
headindex[ch]=i
else:
②
tmp[ord(ch)-97]=i
# search函数只提供英文单词查询
def search(key):
key=key.lower() #转换成小写
p=headindex[key[0]]
while ③ :
if dic[p][0]==key:
print(key+' 中文含义是：'+dic[p][1])
break
else:
p=④
else:
print('sorry,'+key+' 找不到！')
word=input('请输入要查找英文单词：')
search(word)
(3)使用以下代码替换加框处代码，其功能保持不变的是 （单选，填字母）。
A.if p>0: B.if p<0: C.if not p:
3.有下列 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]的值为( )d
A.-1 B.0 C.1 D.3
4.使用 Python 程序在链表a中删除一个数据data，代码如下：
import random
a=[[87,1],[93,3],[97,5],[95,2],[80,0],[98,-1]]
head=4
x=random.randint(0,len(a)-1) #randint(a,b)返回[a,b]区间内的一个随机整数
data=①
p=q=head
while q!=-1:
if ②
if q==head:
head=a[q][1]
else:
a[p][1]=a[q][1]
break
else:
③
q=a[q][1]
则划线处的代码为( )c
A.①a[0][x] ②data==a[q][0] ③p=q
B.①a[0][x] ②data!=a[q][0] ③p=head
C.①a[x][0] ②data==a[q][0] ③p=q
D.①a[x][0] ②data!=a[q][0] ③q=head
