2025新教材技术高考第一轮基础练习--通用技术专题七 数据的组织（含答案）

中小学教育资源及组卷应用平台
2025新教材技术高考第一轮
专题七　数据的组织
考点过关练
考点一　数组
1.(2022浙北G2联盟期中,15)有如下Python 程序段:
import random
a=[]
for i in range(10):
　　　 a.append(random.randint(1,100))
i=0
while i <10:
　　　 if i==0:
　　　　　　i=i+1
　　　 elif a[i-1]<=a[i]:
　　　　　　　　　①　　　
　　　 else:
　　　　　　a[i],a[i-1]=a[i-1],a[i]
　　　　　　　　　②　　　
print(a)
执行该程序段实现了随机生成一个数组,并将其元素递增输出的功能。划线处的代码应该是(　　)
A.① i+=1　② i=1
B.① i-=1　② i=1
C.① i+=1　② i+=1
D.① i-=1　② i-=1
2.(2022绍兴诸暨期中,3)使用列表生成的方式创建数组代码如下:
a=[i*i-1 for i in range(10) if i%2==0]
则数组元素a[3]的值为(　　)
A.2　　　B. 8　　　C. 15　　　D. 35
3.(2022绍兴诸暨期中,4)设有一个5×8的二维数组a,若按行优先的顺序存储数组元素,则元素a[3][5]前面元素的个数为(　　)
A.21　　　B. 22　　　C. 29　　　D. 37
4.(2022绍兴诸暨期中,13)有如下Python程序段:
a=[[0 for i in range(3)]for j in range(3)]
for i in range(3):
　for j in range(3):
　　a[i][j]=i*5+j+1
for i in range(1,3):
　for j in range(2):
　　print(a[j][i],end=" ")
程序段执行后,输出的结果是(　　)
A.2 3 7 8　　　　B.7 12 8 13
C.2 7 3 8　　　　D.6 7 11 12
5.(2022杭州期中,10)下述代码段用于实现在数组a中将新数据k插入下标为 j(0<=j<=8)的位置:
a=[8,6,12,3,5,7,11,2,10,0]
i=8
while i>=j:
　　　　(1)　　
　　　　(2)　　
　　(3)　　
横线处的代码由以下五部分中的三部分组成:
①a[i+1]=k　②a[i]=k　③a[i+1]=a[i]
④a[i]=a[i-1]　⑤i=i-1
下列选项中代码选择与顺序正确的是(　　)
A.③⑤②　　　B.⑤③①　　　C.③⑤①　　　D.④⑤②
6.(2022嘉兴期中,3)用 Python 程序段定义一个3行4列的二维数组(要求先将各元素的值初始化为0,再将第2行第 2 个元素重新赋值为1),以下程序段可行的是(　　)
A. arr=[[0]*3 for j in range(4)]
arr[2][2]=1
B.arr=[[0]*4]*3
arr[1][1]=1
C.arr=[[0 for i in range(4)]for j in range(3)]
arr[1][1]=1
D.arr=[[0,0,0,0]for j in range(3)]
arr[2][2]=1
考点二　链表
1.(2022浙南名校联盟期末,12)一个头指针 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.①②③
2.(2022浙北G2联盟期中,14)用两个列表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.②④
3.(2023浙江开学考,10)已知一个链表a,其a[i][0]存储索引i下节点的数据区域,a[i][1]存储索引i下节点的指针区域。对于当前链表中的一个节点p(索引为p),若要删除p的后一个节点q(q=a[p][1]),则应执行语句(　　)
A.a[p]=a[q]
B.a[p][1]=a[q][1]
C.a[p]=a[a[q][1]]
D.a[p]=a[q];a[p][1]=a[q][1]
4.(2022杭州期中,12)在Python中用列表模拟链表结构,某程序段如下:
a=[['H',1],['a',2],['n',3],['g',4],['2',5],['0',6],['2',7],['2',0]]
p, head=3,3;q,c=-1,0;m,n=3,0
while n<4:
　　c=c+1
　　if c==m:
　　　　n=n+1;c=0
　　　　if p==head:
head=a[p][1]
a[q][1]=head
p=a[p][1]
　　　　else:
　a[q][1]=a[p][1]
　p=a[p][1]
　　else:
q=p
p=a[p][1]
#从头节点开始遍历链表a逻辑顺序的所有节点,并依次输出节点的数据,代码略
该程序段执行后的输出结果为(　　)
A.ng02　　　B.g02n　　　C.2an2　　　D.22an
5.(2022诸暨期末,8)某单向链表如图所示,在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]=-1
A.③⑥　　　B.⑤②　　　C.①④　　　D.⑤②④
6.(2022杭嘉湖金月考,15)山顶上有10个圆形排列的洞,一只狐狸和一只兔子各住一个洞。狐狸总想吃掉兔子。一天兔子对狐狸说:“你想吃我有一个条件,先把洞从1~10编上号,你先到1号洞找我;第二次隔1个洞(即3号洞)找我,第三次隔2个洞(即6号洞)找我,依此类推,次数不限。但狐狸从早到晚进进出出了1000次,仍没有找到兔子。请问兔子可能躲在哪个洞里
实现上述功能的Python程序如下,请在划线处填入合适的代码。
hole=[]
n=10
m=1000
#构造一个循环链表,并给n个洞编号,设置洞的初始标志为0
#链表的节点样式为:[洞的标志,洞的编号]
for i in range(n-1):
　　hole.append([0,i+1])
　　　　　(1)　　　　　
#狐狸开始找兔子,将进入过的洞标志改为1,寻找m次结束
head=0
k=head
hole[0][0]=1
for i in range(1,m):
　　for j in range(1,i+2):
　　　　　　　　(2)　　　　　
　　hole[k][0]=1
#输出标志仍为0的洞,即兔子可能的藏身地点
for i in range (len(hole)):
　　if hole[i][0]==0:
　　　　print("兔子可能躲在第"+　(3)　+"号洞")
考点三　队列
1.(2024届七彩联盟联考,11)有如下程序段:
s=input()
head=0;tail=0;ans=0;tmp=' '
q=[' ']*100
flag=True
for i in range(len(s)):
　if s[i]==',':
　　while head!=tail:
　　　tmp+=q[head]
head+=1
if flag and head　head+=1
flag=not flag
　　ans+=int(tmp)
　　tmp=' ';flag=True
　elif '0'<=s[i]<='9':
　　q[tail]=s[i]
　　tail+=1
输入s为"1-500,2023900-,",执行该程序段,变量ans的值为(　　)
A.100　　　B.22300　　　C.22351　　　D.22400
2.(2022杭州“六县九校”期中,5)有A、B、C、D、E五个人依次进入电梯,结果警告超重了,需要出去一个人才能正常运行,按照数据结构中栈和队列的思维,应离开电梯的人分别是(　　)
A.栈:A　队列:E　　　　B.栈:A　队列:A
C.栈:E　队列:A　　　　D.栈:E　队列:E
3.(2024届强基联盟联考,9)执行下列Python程序段,输出结果为(　　)
data=[1,2,3,1,2,3]
que=[0]*10
head=tail=0
for i in range(len(data)):
if data[i]%2 !=0:
　　que[tail]=data[i]
　　tail+=1
elif tail-head>1:
　　que[tail-1]+=que[head]
　　head+=l
print(que[head:tail])
A.[3,2,1]　　　　B.[1,2,3]
C.[1,3,1]　　　　D.[3,2,3]
4.(2024届新阵地联盟第二次联考,11)有如下程序段:
m=3;n=7
head=tail=0;ans=0
vis=[0]*10;q=[0]*10
for i in range(n):
x=int(input())
if(vis[x]=0):
　ans+=1
　if(tail-head>=m):
　　vis[q[head]]=0
　　head+=1
　q[tail]=x
　tail+=1
　vis[x]=1
print(ans)
运行该程序段,依次输入x的值:1,2,1,5,4,4,1。则程序运行完成后ans 的值是(　　)
A.3　　　B.4　　　C.5　　　D.6
5. (2024届天域全国名校协作体联考,12)已知列表a的长度为6,a[0]至a[5]的值依次为18,12,24,15,21,0,某程序如下所示:
head, tail=0,5
x=a[head]
head+=1
while (head+1) % len(a) !=tail:
　　 t=y=a[head]
head=(head+1) % len(a)
if x　 x,y=y,x
if x % y !=0:
　 a[tail]=x % y
　 tail=(tail+1) % len(a)
x=t
print(a[head])
程序运行后,输出的结果是(　　)
A.24　　　　B.12　　　
C.3　　　　D.0
6.(2023“山水联盟”开学考,11)有如下Python程序代码:
s="ABCDEF"; head=0;tail=0
que=[" "]*100
for i in range(len(s)):
if i%2==0:
　que[tail]=s[i]
else:
　que[tail]=s[len(s)-i]
tail=tail+1
for i in range(len(s)):
print(que[head], end=" ")
head=head+1
以上程序运行后,输出列表的情况是(　　)
A.ABCDEF　　　　B.FEDCBA
C.ACEFDB　　　　D.AFCDEB
考点四　栈
1.(2022浙南名校联盟期末,10)一个栈的入栈序列为“6、9、5、7、8、3”,其出栈序列不可能是(　　)
A.3、8、7、5、9、6
B.7、5、9、8、6、3
C.6、5、7、9、3、8
D.5、9、6、3、7、8
2.(2024届百校起点调研测试,9)栈q初始有三个值,经过一系列入栈、出栈操作后,栈为空,若元素出栈的顺序是1,2,3,4,5,6,7,则栈q初始的情况可能是(　　)
A.[1,2,3]　　　　B.[7,5,6]
C.[6,3,1]　　　　D.[4,7,2]
3.(2024届Z20联盟联考,9)若元素入栈的顺序是1,2,3,4,5,6,不允许连续三次入栈,则可能的出栈序列为(　　)
A.2,3,5,1,6,4　　　　B.1,2,3,6,5,4
C.2,4,3,1,6,5　　　　D.2,5,4,6,3,1
4.(2024届七彩联盟联考,9)假设栈S的最大长度为3,其初始状态和终止状态均为空,经过一系列入栈和出栈的操作,若元素最后的出栈序列为F,E,D,C,B,A,则可能的入栈顺序为(　　)
A.ABCDEF　　　　B.ACDFEB
C.BEFACD　　　　D.BFDECA
5.(2024届嘉兴基测,12)待入栈的序列a有多种出栈序列,以下函数用于判断序列b是不是a的出栈序列,代码如下:
def judge(a,b):
n=len(a);st=[-1]*n
top=-1;i=j=0
while i　top+=1
　　　①　　
　i+=1
　while top>-1 and 　　②　　:
　　top-=1
　　j+=1
return top==-1
from random import shuffle
a=[1,2,3,4,5]
b=[1,2,3,4,5]
shuffle(b)　　#将序列b的元素随机排序
if judge(a,b):
　　print(b,'是', a,'的出栈序列')
else:
　　print(b,'不是',a,'的出栈序列')
程序运行结果如图所示。划线处应填写的语句是(　　)
python 12.py
[2,5,4,3,1]是[1,2,3,4,5]的出栈序列
python 12.py
[5,2,3,1,4]不是[1,2,3,4,5]的出栈序列
A.①st[top]=a[i]　②st[top]==b[j]
B.①st[top]=a[i]　②st[-1]==b[j]
C.①st[top]=b[i]　②st[top]==a[j]
D.①st[top]=b[i]　②st[-1]==a[j]
6.(2022 Z20名校联盟,10)某算法利用“栈”思想进行字符串处理,其步骤如下:①创建长度为n的空栈,字符依次入栈;②当达到栈满状态或数据全部入栈时,字符依次出栈,按照出栈顺序连接成新字符串:③若还有未处理的字符,则重复步骤①②,直到全部字符处理完毕。实现该功能的 Python程序如下:
s=input("请输入字符串:")
n=5;st=[" "]*n
top=-1;i=0;m=" "
while i　while 　(1)　 and i　　　(2)　
　　st[top]=s[i]
　　i+=1
　while top!=-1:
　　m+=st[top]
　　　(3)　
print("密文:" ,m)
加框处(1)(2)(3)的代码由以下代码组成:
①top-=1　②top+=1　③top+1④top下列选项中代码顺序正确的是(　　)
A.④②①　　　　B.③①②
C.③②①　　　　D.④①②
7.(2022诸暨海亮高中月考,10)有如下程序段:
bt=["A","B","C","D",None,"E","F"]
result=[]
stack=[]
i=0
while stack or (i　　if i < len(bt) and bt[i] is not None:
　　　　stack.append(i)
　　　　i=2*i+1
　　else:
　　　　i=stack.pop()
　　　　result.append(bt[i])
　　　　i=2*i+2
print("-".join(result))
则程序运行后输出的结果为(　　)
A.A-B-D-C-E-F　　　　
B.D-B-E-F-C-A
C.D-B-A-E-C-F　　　　
D.A-B-C-D-E-F
考点五　树
1.(2024届Z20联盟联考,8)某二叉树的树形结构如图所示,其后序遍历结果为“物技化数英语”,则中序遍历结果为(　　)
A.语数英物化技　　　　B.物数技化语英
C.语数物化技英　　　　D.化物技英数语
2.(2022名校协作体,10)已知二叉树T2的后序遍历序列为G-D-H-E-B-I-F-C-A,中序遍历序列为D-G-B-E-H-A-C-I-F,则二叉树T2的前序遍历序列为(　　)
A.A-B-D-G-E-H-C-I-F
B.A-B-D-G-E-H-C-F-I
C.A-B-D-G-E-H-F-C-I
D.该二叉树形态不唯一,无法确定
3.(2024届新阵地联盟第二次联考,8)某二叉树的树形结构如图所示,其后序遍历结果为FABGDEC,则中序遍历结果为(　　)
A.FDAGBCE　　　　B.FDABGEC
C.AGBDFCE　　　　D.FDAGBEC
4.(2024届天域全国名校协作体联考,8)下列二叉树中,后序遍历结果不为CBFEAD的是(　　)
　　
　　
5.(2024届七彩联盟联考,8)某二叉树用一维数组表示(见表)。该二叉树从根节点开始,按照从上到下,从左到右的顺序依次用A-H字母表示,该二叉树的中序遍历为(　　)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A B C D E F G H
A.DBGEACFH　　　　B.DBGEACHF
C.DBEGACHF　　　　D.ABCDEFGH
考点六　大数据时代的数据的组织
1.下列关于实时查询数据系统中的数据结构的说法,不正确的是(　　)
A.在实时查询系统中使用数组,时效性较差
B.在链表中查找数据时效性较高,插入数据时效性较低
C.跳跃表基于有序链表
D.跳跃表通过跨区间、跳跃性的比较,避免了依次比较,提高了效率
2.有如下跳跃表:
若要在原链表中插入元素7,则数据元素需要比较的次数为(　　)
A.1　　　B.3　　　C.4　　　D.5
3.下列关于Hadoop的说法,不正确的是(　　)
A.Hadoop是一种超大规模,高可靠性,高可扩展性的数据库
B.Hadoop是Google云计算技术的开源实现
C.使用Hadoop可以在POI数据的处理中获得更方便的体验和更低廉的成本
D.Hadoop可以对海量地理信息进行处理和计算
专题综合练
题组一
1.(2024届名校协作体联考,8)某二叉树的前序遍历结果为GFDECAB,中序遍历结果为DFGCAEB。关于该二叉树,以下说法正确的是(　　)
A.该二叉树的后序遍历为ADFCBEG
B.该二叉树的深度为4,节点C在第3层
C.该二叉树的叶子节点数比非叶子节点数多一个
D.该二叉树可以通过添加3个节点后变为完全二叉树
2.(2024届强基联盟联考,8)某二叉树的树形结构如图所示,其后序遍历结果为FBCEAD,则前序遍历结果为(　　)
A.ABCDEF　　　　B.FEDCBA
C.DFACBE　　　　D.FDBCAE
3.(2024届强基联盟统测,8)已知某二叉树的后序遍历为GDBEHFCA,中序遍历为DGBAECHF,下列说法正确的是(　　)
A.该二叉树中叶子节点有3个
B.该二叉树的前序遍历为ABDGCEHF
C.该二叉树是一棵完全二叉树,树的高度为4
D.该二叉树中度为1的节点有2个
4.(2024届新阵地联盟第二次联考,9)栈S初始状态为空栈,将序列3,2,5,7,1中元素逐一入栈,当栈空或入栈元素比栈顶元素大时则入栈,否则出栈至符合条件再入栈。序列所有元素入栈完毕后,栈内剩余元素出栈,直至栈空。则出栈的顺序是(　　)
A.17523　　　　B.37521
C.37512　　　　D.32751
5.(2024届天域全国名校协作体联考,9)利用栈求逆波兰表达式(表达式由操作数和运算符组成)的方法是:从左往右扫描该表达式,遇到操作数时入栈;遇到运算符时,把处于栈上方的两个元素依次出栈,用运算符计算,并把计算结果压入栈中。如此反复操作,直至表达式扫描结束。当用该算法求逆波兰表达式abcd-*e/+f-的值时(abcdef表示不同的操作数),所使用的栈的深度至少为(　　)
A.3　　　B.4　　　C.5　　　D.6
6.(2024届嘉兴基测,11)长度为5的循环队列que,que[0]至que[4]的值依次为'a','b','c','d','e',执行如下程序段后,输出的最后一个字符为　(　　)
n=5;head=0;tail=4
que=['a','b','c','d','e']
while head!=tail:
　　if head%4==0:
　　　print(que[head])
　　else:
　　　tail=(tai1+1)%n
　　　que[tail]=que[head]
　　head=(head+1)%n
print(que[head])
A.b　　　B.c　　　C.d　　　D.e
7.(2024届发展共同体联考,9)某种特殊的队列Q,支持以下三个操作:
操作Q1:若队列非空,队首元素出队,并输出;
操作Q2:若队列非空,队首元素出队;
操作Q3:一个元素入队。
以上任意一种操作后,若队列非空,新的队首元素仍为队列中所有元素的最小值。
若队列Q初始状态为空,依次进行Q3、Q2、Q1、Q2、Q3、Q1、Q3七次操作后,下列说法正确的是(　　)
A.当前队列中的元素个数为2
B.输出的元素个数为2
C.第一个输出的元素肯定比当前队首元素大
D.队列初始状态是不是空对输出结果有影响
8.(2024浙江1月选考,8,2分)栈S从栈底到栈顶的元素依次为1,2,3,队列Q 初始为空。约定:U 操作是指元素出栈后入队,H 操作是指元素出队后再入队。经过UUHU系列操作后,队列中队首到队尾的元素依次为(　　)
A.2,1,3　　　B.3,1,2　　　C.1,3,2　　　D.2,3,1
9.(2024浙江1月选考,9,2分)数组元素a[0]至a[n-1]依次存放着n个数据,现需要将元素a[n-1]插入在下标为x(0≤xtemp=a[n-1]
for i in range(n-2,x-1,-1):
　　　　　　　　
a[x]=temp
A.a[i+1]=a[i]　　　　B.a[i-1]=a[i]
C.a[i]=a[i+1]　　　　D.a[i]=a[i-1]
10.(2024届发展共同体联考,11)有如下程序段:
s=[' ']*len(a)
head=2;q=head;top=-1
while q!=-1:
　　top+=1
　　s[top]=a[q][0]
　　q=a[q][1]
print(s[top-2])
若a=[['a',3],['b',0],['c',1],['d',-1]],则输出的结果为(　　)
A.a　　　B.b　　　C.c　　　D.d
11.(2024届强基联盟联考,11)有如下Python程序段:
s=input()
stack=[0]* len(s);top=-1;presign='+';num=0
for i in range(len(s)):
if '0'<=s[i]<='9':
　　num=num*10+int(s[i])
if i==len(s)-1 or s[i] in '+-*/':
　　if presign=='+':
　　　　top+=1
　　　　stack[top]=num
　　elif presign=='-':
　　　　top+=1
　　　　stack[top]=-num
　　elif presign=='*':
　　　　top+=1
　　　　stack[top]=stack[top-1]*num
　　else:
　　　　top+=1
　　　　stack[top]=stack[top-1]
//num
　　presign=s[i]
　　num=0
print(sum(stack))　　#sum函数对stack中所有元素求和
若输入'5*4-6+10/3',程序运行后,输出的结果是(　　)
A.32　　　B.24　　　C.17　　　D.8
12.(2023浙江1月选考,15,9分)有2组器件共n个,要用一台检测设备检测。每个送检器件的信息包含送达时间、检测时长和优先级。优先级有m(1编写程序模拟检测过程,先合并2组器件的数据,然后计算所有器件的平均等待时长,其中每个器件等待时长为其开始检测时间与送达时间的时间差。(时间单位均为秒)
请回答下列问题:
(1)由题意可知,图中器件A、B、C、D的检测顺序为A—C—D—B,A、C、D的等待时长分别为0、1、0,B的等待时长是　　　　。
送达时间 检测时长 优先级
A 0 3 2
B 1 1 2
C 2 1 1
D 4 3 0
11 3 2
12 2 2
(2)定义如下merge(lst1, lst2)函数,参数 lst1和 lst2的每个元素由送达时间、检测时长和优先级3项构成,lst1和 lst2均已按送达时间升序排列。函数功能是将lst2中的元素合并到lst1中,并将 lst1按送达时间升序排列,函数返回lst1。
def merge(lst1,lst2):
　　i=len(lst1)-1
　　j=len(lst2)-1
　　for t in range(len(lst2)):
　　　lst1.append([0,0,0])　　#为lst1追加一个元素[0,0,0]
　　k=len(lst1) -1
while j >=0:
　　　if i >=0 and lst1[i][0]>lst2[j][0]:
　 lst1[k]=lst1[i]
i -=1
　　　else:
lst1[k]=lst2[j]
j -=1
　　　k -=1
　return lst1
①调用merge(lst1,lst2)函数,若lst1为[[0,3,2],[1,1,2],[12,2,2]],lst2为[[2,1,1],[4,3,0], [11,3,2]],则while语句中循环体的执行次数是　　　　。
②若函数中 while语句的条件“j>=0”误写为“k>=0”,会导致某些情况下无法得到符合函数功能的结果。调用merge(lst1, lst2)函数,下列4组数据中能测试出这一问题的是　　　　(单选,填字母)。
A.lst1=[[0,3,2],[4,3,0]]
lst2=[[1,1,2]]
B.lst1=[[1,1,2]]
lst2=[[0,3,2],[4,3,0]]
C.lst1=[[1,1,2],[4,3,0]]
lst2=[[0,3,2]]
D.lst1=[[4,3,0]]
lst2=[[0,3,2],[1,1,2]]
(3)实现模拟检测过程并计算平均等待时长的部分Python程序如下,请在划线处填入合适的代码。
def proc(data,m):
　　n=len(data)
　　queinfo=[]
　　for i in range(m):
　　　queinfo.append([-1, -1])
# queinfo追加一个元素[-1,-1]
　　for i in range(n):
data[i].append(-1)　　# data[i]追加一个元素-1
　　curtime=0
waitnum=0
i=0
　　①　　
while i < n or waitnum > 0:
　 if i < n and data[i][0] <=
curtime:
　　　k=data[i][2]
　　　if queinfo[k][0]==-1:
　　　　　queinfo[k][0]=i
　　　else:
　　　　　　　②　　
　　　　　data[p][3]=i
　　　queinfo[k][1]=i
　　　waitnum+=1
　　　i+=1
　　elif waitnum >0:
k=0
while queinfo[k][0]==-1:
　　k+=1
p=queinfo[k][0]
total+=curtime-data[p][0]
curtime+=data[p][1]
　　③　　
waitnum -=1
　　else:
　　　 curtime=data[i][0]
return total / n
'''
读取2组器件的数据,分别存入列表data1和 data2中。2个列表的每个元素包含3个数据项,分别对应器件的送达时间、检测时长和优先级。data1和 data2中的数据已分别按送达时间升序排列,代码略
读取优先级等级个数存入m,代码略
'''
data=merge(data1, data2)
print(proc(data, m))
13.(2023浙江6月选考,15,9分)某工程包含n个任务(编号为0~n-1),每天可以有多个任务同时进行。某些任务之间有依赖关系,如图a所示,任务4依赖于任务1,任务1依赖于任务2。即任务2完成后才可以开始任务1,任务1完成后才可以开始任务4。不存在一个任务依赖于多个任务,或多个任务依赖于同一个任务的情况。
现已对该工程的依赖关系进行了梳理,结果如图b所示,标记“T”表示依赖关系需保留,标记“F”表示依赖关系需删除。
根据每个任务完成所需的天数和梳理后的依赖关系,编写程序,首先删除标记为“F”的依赖关系,然后计算工程最快完成所需的天数,并以工程最快完成所需的天数为期限,计算每个任务最晚必须开始的时间。
任务A 任务B 标记
0 5 T
5 4 F
4 1 T
1 2 T
2 3 F
注:任务A依赖于任务B
图b
请回答下列问题:
(1)若某工程有6个任务,任务间依赖关系如图a所示,完成任务0~5所需天数分别为2,1,3,5,1,6,则工程最快完成需要　　天。
(2)定义如下erase(lst)函数,参数 lst列表的每个元素表示一个依赖关系。函数的功能是删除标记为“F”的依赖关系,返回保留的依赖关系的个数。
def erase(lst):
　　i=0
　　j=len(lst)-1
　　while i<=j:
　　　　if lst[i][2]=='T':
　　　　　　i+=1
　　　　else:
　　　　　　if lst[j][2]=='T':
lst[i]=lst[j]
i+=1
　　　　　　j-=1
　　return i
若lst列表依次存储图b所示的依赖关系,如 lst[0]为[0,5,'T'],调用erase(lst)函数,则语句“lst[i]=lst[j]”的执行次数为　　。
(3)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
def proc(n,lst,task):
pr=[0]*n
w=[0]* n　　# w[i]存放任务最晚必须开始的时间
m=erase(lst)
for i in 　　①　　:
task[lst[i][1]][1]=lst[i][0]
pr[lst[i][0]]=1
c=[]
days=0　　# days存放工程最快完成所需的天数
for i in range(n):
if pr[i]==0:
　　k=i
　　s=0
　　while k!=-1:
　　　　c.append(k)
　　　　s+=task[k][0]
　　　　　　②　　
　　if s > days:
　　　　days=s
for i in range(n-1,-1,-1):
k=c[i]
if task[k][1]==-1:
　　w[k]=days-task[k][0]+1
else:
　　　　③　　
#输出days,以及保存在w中的每个任务最晚必须开始的时间,代码略
"'
工程包含的任务数存入变量n
任务间的依赖关系存入lst列表
lst[0]包含3项,任务lst[i][0]依赖于任务lst[i][1],lst[i][2]存放保留/删除标记,任务数据存入task列表
task[i]包含2项,task[i][0]为完成任务所需天数,task[i][1]的初值为-1
代码略
"'
proc(n,lst,task)
14.(2024届Z20联盟联考,15)小明同学去看病,当他在一位医生的诊室门口等待就诊的时候,发现了叫号系统的页面上有两行病人名单。第一行名单为正常排队等待就诊的序号,第二行名单为过号或检后再诊而等待的序号。叫号的规则是先在第一行叫2个就诊序号,再到第二行叫1个就诊序号。小明同学回家后将刚才发现的叫号规则编写了Python程序。效果如图所示:
图①:当前到来的就诊序号是3号,为过号或检后再诊序号,进入第二行,先到达先就诊。
图②:当前到来的就诊序号是4号,为过号或检后再诊序号,进入第二行。
图③:当前到来的就诊序号是16号,为正常排队等待就诊的序号,进入第一行,按就诊序号顺序排列。
图④:开始叫号,按照正常排队等待就诊叫号2位,过号或检后再诊叫号1位,得到新的顺序。
(1)请在划线处填入合适的代码。
(2)加框处的代码有误,请改正。
def output(head, a, b):
p=head
head_b=0; tail_b=len(b)
while p!=-1:
　　print(a[p][0], end="->")
　　p=a[p][1]
print()
while head_b!=tail_b:
　　print(b[head_b], end="->")
　　head_b+=1
print()
def insert(data,a,b):　　#根据挂号的序号分别进入第一行名单或第二行名单
　 head_a=a[0][0]
　 if data>　　①　　:
　　　p=0
　　　a.append([data,-1])
　　　while p!=-1:
　　　　　if data<=a[p][0]:
　　　　　　　a[-1][1]=p
　　　　　　　a[q][1]=len(a)-1
　　　　　　　break
　　　　　else:
　　　　　　　q=p
　　　　　　　p=　　②　　
　　　if p==-1:
　　　　　a[q][1]=　　③　　
　　　output(0,a,b)
　 else:
　　　b.append(data)
　　　output(0,a,b)
#a、b赋初值,代码略
#如图①所示:a=[[13,1],[15,2],[17,-1]];b=[3]
while True:
　　data=int(input("请输入取号:"))
#输入0表示停止取号,开始叫号
　　if data==0:
　　　break
　　insert(data,a,b)
print("====开始叫号====")
p=head=0
head_b=0;tail_b=len(b)
while p!=-1 or head_b!=tail_b:
　　if p!=-1 and head_b!=tail_b:
　　　 i=0
　　　 while a[p][1]!=-1:
　　　　　print(a[p][0], end="->")
　　　　　p=a[p][1]
　　　　　i+=1
　　　 print(　　④　　, end="->")
　　　 head_b+=1
　　elif p!=-1 and head_b==tail_b:
　　　 print(a[p][0], end="->")
　　　 p=a[p][1]
　　else:
　　　 print(b[head_b], end="->")
　　　 head_b+=1
15.(2022山水联盟开学考,15)小赵同学在某游戏平台中获得虚拟的食物、装备、材料等物品,它们分别有不同的价值,现游戏平台有兑换机制,即可用多个不同物品换取一个等值的物品(每个物品只能取一样),下表为小赵同学已获得的物品。
序号 物品名称 数量 单价
0 灵丹 2 1
1 大力丸 1 2
2 止血草 3 5
3 忘魂花 1 7
4 雄黄 1 9
5 灵山仙芝 5 10
6 梅花镖 1 15
7 止血草 1 20
目标置换物品的价值:35。
已获得物品价值依次是:1,2,5,7,9,10,15,20。
依次拿取物品序号的方案有:
取序号为[0,1,2,3,7]的物品;
取序号为[0,1,3,5,6]的物品;
取序号为[0,2,4,7]的物品;
取序号为[0,4,5,6]的物品;
取序号为[2,5,7]的物品;
取序号为[6,7]的物品。
如要换取游戏中的物品“破天锤”,需要35个金币,有多种置换的方式,为方便计算以节省时间,小赵同学编写了如下程序,运行界面和代码如下,请在划线处填入合适的代码。
def exchange(t,pricelist):
　　n=len(pricelist)
　　stack=[]
　　i=0
　　num=0
　　while　　　①　　　:
　　　　while t>0 and i　　　　　　if t>=int(pricelist[i]):
stack.append(i)
　　②　　
　　　　　　i+=1
　　　　　　if t==0:
　　　　　　　print("取序号为",stack,"的物品")
num+=1
　　　　if 　　　③　　　:
　　　　　　i=stack.pop()
　　　　　　t+=int(pricelist[i])
　　　　　　④　　　
　　if num==0:
　　　　print("无方案")
m=int(input("目标置换物品的价值:"))
price=input("已获得物品价值依次是:")
p=price.split(",")　#将输入的内容以“,”作分隔,并转换为列表
print("依次拿取物品序号的方案有:")
exchange(m, p)
16.(2022名校协作体联考,15)某校军训,需要按照身高由低到高排成n行5列的方阵。某班学生按照身高(100≤身高<199)由低到高编写编号并将相关信息存在图1所示的“stu.txt”文件中。根据教官提出的排方阵要求,排成如图2所示的方阵,方阵各点显示学生编号。
　
现有延迟报到学生归队,归队学生编号延续该班现有编号依次往后,编写程序完成下列任务:输入学生身高,输出新的方阵布局图。例如:输入学生身高为168,新的方阵布局图如图3所示,学生在方阵的位置:3,4。
(1)若插入学生身高为160 cm,根据图1及范例,该学生应该在图2方阵中的　　　行　　　　列。
(2)为实现上述功能,请填写划线处代码。
f=open("stu.txt","r")
a=[]
line=f.readline().split()
i=1
while line!=[]:
　　a.append([line[0],line[1], i])
　　i+=1
　　line=f.readline().split()
n=len(a)-1
a[n][2]=-1
sg=input("请输入插入的学生身高(cm):")
xh=str(len(a))
head=1
p=head;q=head
while　　　①　　:
　　p=q
　　q=a[q][2]
if q==head:
　　　　②　　
　　head=len(a) -1
else:
　　a.append([xh,sg,a[p][2]])
　　a[p][2]=len(a)-1
p=head
m=1
while p!=-1:
　　if m!=5:
　　　　print(a[p][0],end=" ")
　　　　m+=1
　　else:
　　　　print(a[p][0])
　　　　m=1
　　　　　　③　　
17.(2022 A9协作体返校考,15)学校举办了“语文作文现场赛”,参赛同学成绩存储在文本文件“gra.txt”中,如图a所示(每一行记录一位同学的姓名和成绩,以“:”分隔)。陈老师利用Python程序对作文成绩进行处理,统计出各个分数等级的人数,并输出结果。程序运行界面如图b所示。
实现上述功能的Python程序如下,请在划线处填入合适的代码。
def cla(x):　#判断成绩等级
　　if x>=50:
　　　return "A"
　　elif x>=40:
　　　return "B"
　　elif x>=30:
　　　return "C"
　　else:
　　　return "D"
gra=[]　#存储各个整数型成绩
num=[0]*4
f=open("gra.txt")
lines=f.readlines()　#将f对象的数据按行存入列表lines中
f.close()　#关闭文件
for line in lines:　#循环读取列表lines 中的每个元素,并做相应处理
　　a=line.strip().split(":") #去除结尾的换行符并以冒号为分隔符进行分隔
　　gra.append(　　①　　)
for i in range(len(gra)):　#统计各等级人数
　　t=　　②　　
　　num[ord(t)-65]+=1
print("成绩分布如下: ")
for i in range(len(num)):　#输出统计结果
　　print(chr(i+65)+"等级有"+　③　+"人")
18.(2023七彩阳光开学考,15)食堂推出的三款特色菜,分别用A、B、C表示,想用投票方式统计出三款菜的受欢迎程度。每位投票者需要将三款菜按喜爱程度从高到低进行排列,并投出一票。如图a所示,小明负责将文件“投票.txt”中的选票进行统计。第1张选票信息为“A,C,B”,表示投票者认为A菜优于C菜,C菜优于B菜,即A菜也优于B菜。他得到如图b所示的投票情况。对选票进行统计,得到三款菜的偏好,如图c所示,数据第一行中的“6”说明有6张选票显示A菜优于B菜,“10”说明有10张选票显示A菜优于C菜,以此类推……将所有投票进行统计,再将三款菜的得票数进行求和,按得票数从高到低排列,分别为A菜16票,B菜11票,C菜12票,即可得到每款菜的受欢迎程度。
　　　　
　　　　
请回答下列问题:
(1)若有四款菜,投票情况如图d所示,则第2受欢迎的菜为　　　　(填字母)菜。
(2)加框处代码有错误,请改正。
(3)实现上述功能的 Python程序如下,请在划线①②③处填入合适的代码。
f=open('投票.txt')
a=[]
r=f.readline().strip()　#从文件中读取一行,并把末尾的'\n'删掉
while r:　#当r非空(从文件读取到了数据)
　　a=r.split(',')
　　r=f.readline().strip()
f.close()
n=len(a[0])
p=[0]*n**2
for i in a:
　　for j in range(n-1):
　　　　x1=ord(i[j])-65
　　　　for k in range(　　①　　):
　　　　　　x2=ord(i[k])-65
　　②　　
b=[[' ',0]for i in range(n)]
for i in range(n):
　　b[i][0]=chr(i+65)
　　for j in range(n):
　　　　b[i][1]+=p[i*n+j]
i=1
while i　　x=b[i]
　　j=i-1
　　while 　　③　　:
　　　　b[j+1]=b[j]
　　　　j-=1
　　b[j+1]=x
　　i+=1
for i in range(n):
　　print('第',i+1,'受欢迎的菜为',b[i][0],',得票为',b[i][1],'票')
题组二
1.(2024届百校起点调研测试,8)某二叉树的中序遍历为ABCDEF,则下列不可能是此二叉树的是(　　)
　　　
　　　
2.(2024届发展共同体联考,8)某二叉树的树形结构如图所示,其前序遍历结果为BADCFGE,则字符“G”所在的位置为(　　)
A.①　　　B.②　　　C.③　　　D.④
3.(2024届浙南名校联盟联考,8)有一棵二叉树如图所示,下列说法正确的是(　　)
A.此二叉树是完全二叉树
B.此二叉树的叶子节点有3个
C.此二叉树的后序遍历为FDBECA
D.此二叉树用一维数组表示为['A','B','C','D','E','F']
4.(2024届名校协作体联考,9)有一组数据4,2,6,3,1,5按序入栈,则出栈的顺序可能是(　　)
A.4,2,5,3,1,6　　　　B.1,3,5,2,6,4
C.6,4,2,3,5,1　　　　D.6,2,4,3,1,5
5.(2024届强基联盟联考,11)执行下列Python程序代码,若输入的数据为"ABCDE",则输出的结果不可能是(　　)
from random import randint
st=[' ']* 10;top=-1;out=' '
s=input('s=')
while s:
　　flag=randint(0,1)
　　if flag==1:
　　　　top+=1;st[top]=s[0]
　　　　s=s[1:]
　　elif top !=-1:
　　　　out+=st[top];top-=1
while top !=-1:
　　out+=st[top]; top-=1
print(out)
A.CEDAB　　　　B.BDECA
C.ABCED　　　　D.DCBEA
6.(2024届百校起点调研测试,11)有如下Python程序:
q=[0]* 6
q[0]=1
head=0;tail=1
while tail　　x=q[head]
　　if x%2==0:
　　　 q[tail]=x//2
　　　 tail+=1
　　else:
　　　 q[tail]=x*2
　　　 q[tail+1]=x*3
　　　 tail+=2
　　head+=1
程序运行后, tail-head的值为(　　)
A.3　　　B.4　　　C.5　　　D.6
7.(2024届浙南名校联盟联考,9)下列关于队列和栈的说法,不正确的是(　　)
A.队列是一种先进先出的线性表,可在队尾进行插入操作
B.栈的特性是“先进后出,后进先出”
C.某栈的入栈的顺序为abc,出栈顺序只有3种
D.队列和栈都是线性数据结构,都可以用数组来实现
8.(2024届浙南名校联盟联考,11)已知字符"a"的ASCII码值为97,有如下Python程序段:
que=[" "]*20
head,tail=0,0
for i in range(3):
que[tail]=chr(97+i)
tail+=1
st=["b" ,"c" ,"d" ,"a"]
top=3
while head < tail and top >-1:
　　if st[top]==que[head]:
　　　　head+=1
　　else:
　　　　que[tail]=st[top]
　　　　tail+=1
　　top-=1
print(que[head:tail])
执行该程序段,则输出的结果是(　　)
A.['c', 'd', 'c']　　　　B.['c', 'c', 'd']
C.['c', ' ', 'd']　　　　D.['c', 'd']
9.(2024届强基联盟统测,12)有如下Python程序段:
a=[i for i in range(1,7)]
b=[0]*6
head,tail=0,0
for i in range(1,7):
cnt=1
while cnta[tail]=a[head]
head=(head+1)%6
tail=(tail+1)%6
cnt+=1
b[a[head]-1]=i
head=(head+1)%6
执行该程序段后,b[5]的值为(　　)
A.2　　　B.3　　　C.4　　　D.5
10.(2024浙江1月选考,12,2分)使用列表d模拟链表结构(节点数大于0),每个节点包含数据区域和指针区域, h为头指针。链表中各节点已按数据区域中数值的绝对值由小到大排列,如图a所示。现要修改该链表各节点的链接关系,使链表各节点按数据区域中的数值由小到大排列,结果如图b所示。实现该功能的程序段如下,方框中应填入的正确代码为(　　)
　　
t=h
p=d[h][1]
while p !=-1:
q=d[p][1]
　　　　　
p=q
d[t][1]=-1
A.
if d[p][0]>0:
　　d[q][1]=p
　　d[t][1]=q
else:
　　d[h][1]=q
　　h=p
　B.
if d[p][0]>0:
　　d[t][1]=q
　　t=q
else:
　　h=p
　　d[p][1]=t
C.
if d[p][0]>0:
　　d[t][1]=p
　　t=p
else:
　　d[p][1]=h
　　h=p
　D.
if d[p][0]>0:
　　d[t][1]=q
　　d[q][1]=p
else:
　　d[p][1]=h
　　h=q
11.(2024届嘉兴基测,15)最短路径问题。以m*n个边长为1的正方形组成的矩形,各顶点按行优先从0开始编号,图a所示为3*2的矩形及顶点编号。从顶点x(起点)经由各正方形的边移动到顶点y(终点)有多种移动路径,编程求解所有的最短路径。
(1)分析问题,将矩形转换为计算机可处理的数据。可采用列表存储矩形中各顶点的相邻关系,如图b所示。
顶点 相邻顶点
0 [4,1]
1 [5,0,2]
2 [6,1,3]
3 [7,2]
4 [0,8,5]
...
图b
编写函数init,根据横向和纵向的正方形数量,返回所有顶点及其所有的相邻顶点数据。完善程序,在划线处填入合适的代码。
def init(m, n):
tot=(m+1)*(n+1)#顶点总数
lst=[[]for i in range(tot)]
for i in range(tot):
if i > m:
　lst[i].append(i-m-1)
if i < (m+1)*n:
　lst[i].append(i+m+1)
if i%(m+1) !=0:
　lst[i].append(i-1)
if i%(m+1)!=m:
　　　　　　　　　
return lst
(2)分析问题,查找所有从起点到终点的最短路径。例如:查找从起点1到终点10的所有最短路径,可先查找终点10的所有相邻顶点(6,9,11),然后再逐个查找顶点6、9、11的相邻顶点,直到查找到起点1,获得所有最短路径,如图c所示,共有3条长度为3的最短路径,分别为1→2→6→10,1→5→6→10,1→5→9→10。若从起点4到终点11,共有　　　　条最短路径。
(3)分析问题,存储查询到的路径。可采用链表结构保存路径数据,例如:查找从起点1到终点10的所有最短路径,首先将终点10的数据[10,0,-1]保存在path[0]中,然后将其相邻顶点6、9、11 的数据保存到path中,path[i][0]保存顶点的编号,path[i][1]保存当前顶点到终点的距离,path[i][2]保存下一顶点在path中的位置,其值为-1表示当前顶点为终点。
编写函数print_path,输出所有的最短路径。完善程序,在划线处填入合适的代码。
def print_path(x,path,length):#为起点编号,length为path中有效元素个数
　cnt=0
for i in range(length):
if path[i][0]==x:
　　　cnt+=1
　　　s="最短路径"+ str(cnt)+ " :"
　　　v=path[i]
　　　while 　　　　　　:
　　　　　s=s+ str(v[0])+ ","
　　　　　v=path[v[2]]
　　　s=s+ str(v[0])+ "。"
　　　print(s)
(4)实现上述功能的Python程序如下,运行结果如图d所示。请在划线处填入合适的代码。
请输入起点:0
请输入终点:10
最短路径1:0,1,2,6,10。
最短路径2:0,1,5,6,10。
最短路径3:0,4,5,6,10。
最短路径4:0,1,5,9,10。
最短路径5:0,4,5,9,10。
最短路径6:0,4,8,9,10。
图d
m=3#横向正方形数量
n=2#纵向正方形数量
mtx=init(m, n)
x=int(input("请输入起点:"))
y=int(input("请输入终点:"))
path=[[]for i in range(999)]
passed=[False]* len(mtx)　　#保存顶点是否已途经
　　①　　
dis=0;head=0;tail=0
path[tail]=[y,0,-1]
tail+=1
passed[y]=True
while not found:
　　dis+=1
　　pass_dis=[False]* len(mtx)
　　tmp=tail
　　for i in range(head,tail):
v=path[i]
for d in mtx[v[0]]:
if not passed[d]:
　　path[tail]=　　②　　
　　tail+=1
　　pass_dis[d]=True
if d==x:
　　found=True
　　head=tmp
　　for i in range(len(mtx)):　　#标记已途经的顶点
　　　 if 　　③　　:
　　　　　passed[i]=True
#输出结果
print_path(x, path,tail)
12.(2022 A9协作体返校考,16)字符串分段。输入一串仅由小写字母组成的字符串s,将这个字符串划分为尽可能多的小片段,要求同一个字母只出现在其中的一个片段中,并按照分段顺序逐行输出分段结果。程序运行界面如下:
请输入一串仅包含小写字母的字符串:asdasmhjhh
asdas
m
hjhh
(1)实现上述功能的Python程序如下,请在划线处填入合适的代码。
s=input("请输入一串仅包含小写字母的字符串:")
c=0
p=[-1]*52　#数组p用来记录各个小写字母出现的起始位置和结束位置
#a[0]记录a出现的起始位置,a[1]记录a出现的结束位置,依此类推
for i in range(0,len(s)):　#记录各字符第一次和最后一次出现的位置
　　a=　　①　　
　　if p[2*a]==-1:
　　　p[2*a]=i
　　else:
　　　p[2*a+1]=i
for i in range(0,26):
　　if p[2*i]>p[2*i+1]:
　　　p[2*i+1]=p[2*i]　#只出现一次的字符,起始位置就是结束位置
　　if p[2*i]!=-1:
　　　　c+=1
for i in range(0,c):　#将字符位置按照出现的起始位置升序排序
　　for j in range (25, i,-1):
　　　if p[2*j]> -1:
　　　　　if p[2*(j-1)]> p[2*j]or 　　②　　:
　　　　　p[2*(j-1)],p[2*j]=p[2*j],p[2*(j-1)]
　　　　　　p[2*(j-1)+1],p[2*j+1]=p[2*j+1],p[2*(j-1)+1]
t1,t2=p[0],p[1]　#字符串分段
for i in range(1, c):
　　if p[2*i]< t2 and p[2*i+1]> t2:
　　　　　　③　　
　　elif p[2*i]>t2:
　　　　print(s[t1:t2+1])
　　　　t1,t2=p[2*i], p[2*i+1]
print(s[t1:t2+1])
(2)运行程序后,若输入的字符串s为"hshjhqueeqabaa",输出的结果一共　　行,其中第二行显示结果为　　　　。
答案　(1)①ord(s[i])-97　或ord(s[i])-ord("a")
②p[2*(j-1)]==-1　③t2=p[2*i+1]　(2)3;queeq
13.(2022 Z20名校联盟联考,15)校学生会要从两个候选人A和B中选举一个会长,每个候选人都有自己的支持方。现在以轮为过程来进行选举,在每一轮选举中,当前成员可以禁止另一位成员的选举权,即让另一位成员在这一轮和随后的几轮中都丧失选举权。
在选举过程中,一旦有选举权的成员都来自同一个阵营,则该阵营胜利。
字母A和B分别代表两位候选人,输入一个字符串代表每个成员的阵营,例如输入“ABB”,则输出结果为B,即候选人B为会长。
说明:第一轮中,第一个成员(A)可以让第二个成员(B)失去选举权,第二个成员(B)会被跳过,因为他的选举权被禁止,第三个成员(B)可以让第一个成员(A)失去选举权,因此在第二轮只剩下第三个成员(B)拥有选举权,则输出结果为B,即候选人B为会长。
(1)若输入“ABABB”,则会长为　　　　。
(2)实现上述功能的Python程序如下,请在划线处填入合适的代码。
s=input("请输入投票字符串:")
queA=[" "]*100 ; queB=[" "]*100
headA=headB=0
tailA=tailB=0
n=len(s)
for i in range(n):
　　if　　①　　:
　　　　queA[tailA]=i
　　　　tailA+=1
　　else:
　　　　queB[tailB]=i
　　　　tailB+=1
while 　　②　　:
　　if queA[headA]　　　　queA[tailA]=queA[headA]+n
　　　　tailA+=1
　　else:
　　　　queB[tailB]=queB[headB]+n
　　　　tailB+=1
　　headA+=1; headB+=1
if　　③　　:
　　print("B")
else:
　　print("A")
14.(2022 Z20名校联盟联考,16)“最小波动值”是经济管理学上的一种衡量营业情况是否稳定的概念,当“最小波动值”越大时,就说明营业情况越不稳定。
经济管理学上对“最小波动值”的定义:
某一天的“最小波动值”=min{|该天以前某一天的营业额-该天营业额|},第一天的“最小波动值”为第一天的营业额。
若要分析某个店铺的营业情况是否稳定,只需要把一段时间内每一天的“最小波动值”加起来即可。现根据某个店铺一段时间内每一天的营业额(说明:支出为0表示该天不营业),设计程序计算该店铺的“最小波动值”之和。
(1)若营业额数据为“13,10,14,15,3,11”,则“最小波动值”之和是　　　　。
(2)实现上述功能的Python程序如下,请在划线处填入合适的代码。
import pandas as pd
num=[]　#数组num按经营时间顺序存储每天营业额
numy=[]　#数组numy按营业额降序存储每天营业额
item=[]　#根据数组numy构造链表item
df=pd.read_excel("yye.xlsx")
df=　　①　　　#筛选出营业的记录
df["营业额"]=df.sum(axis=1)　#在df对象最后一列插入“营业额”列
df1=df.sort_values("营业额",ascending=False)
for i in df.index:
　　num.append(df["营业额"][i])
for i in df1.index:
　　numy.append(df["营业额"][i])
n=1
for i in numy:
　　item.append([i,n])
　　n+=1
item[n-2][1]=-1
head=0
k=0
　　②　　
for i in num[-1 :-len(num):-1]:
　　p=head
while item[p][0]!=i:
　　k=p
　　p=item[p][1]
f=item[p][1]
if f==-1:
　　tot+=abs(item[k][0]-item[p][0])
elif p==head:
　　tot+=abs(item[f][0]-item[p][0])
else:
　　tot+=min(abs(item[k][0]-item[p][0]) , abs(item[f][0]-item[p][0]))
if p==head:
　　head=item[head][1]
else:
　　　　③　　
print("该店铺的最小波动值之和是",tot)
15.(2023“山水联盟”开学考,16)临近年关,学校为活跃新年气氛,举办迎新年联欢活动,最后一个节目为“我是大赢家”抽奖活动,为增强互动效果,最后中大奖的中奖者由教师们互动产生,游戏规则是:全校所有教工,每人获得一个随机编号,编号不得重复,然后按照编号大小顺时针手拉手围成一个圈,最后一个老师与第一个老师手拉手,接下来由第1个人指定m的值,从编号为1的人开始报数(1,2,3,…),报到m的人出圈,不再参加互动游戏,接着再由出圈人的上一位老师新指定m的值,并重新开始报数,逆时针报到m的人出列,游戏过程中出圈的人由老师们自己决定,如此继续,顺时针出圈一个人,逆时针出圈一个人,直到圈中只剩下一个人,他就是今天的最大赢家。小明编写了一个Python程序实现上述功能,程序运行时,输入参加游戏的人数,每次有人出圈后,再输入下一个指定值。
实现上述功能的Python程序如下,请在划线处输入合适的代码。
#删除索引为p的游戏者
def delete(a,head,p):
if a[p][1]!=-1:
　　a[a[p][1]][2]=a[p][2]
if a[p][2]!=-1:
　　　　①　　
if head==p:
　　head=a[head][2]
return head
n=int(input("请输入参加游戏的人数"))
a=[[i+1,i-1,i+1]for i in range(n)]
a[0][1]=n-1
a[n-1][2]=0
p=head=0
while 　　②　　:
　　m=int(input("请输入顺时针数第几位出局"))
　　for i in range(m-1):
　　　　　　③　　
　　head=delete(a,head,p)
　　p=a[p][1]　#退回到上一位游戏者
　　if a[head][1]!=head:
　　　　m=int(input("请输入逆时针数第几位出局"))
　　　　for i in range(m-1):
　　　　　　p=a[p][1]
　　　　head=delete(a,head,p)
　　　　　　④　　　#退回到上一位游戏者
print(a[head])
16.(2023强基联盟统测,16)某银行网点有5个窗口,银行最少要保持3个窗口营业,另2个窗口初始为备用状态。客户按批次进入大厅,每个客户的业务办理时间为1个单位,银行每过1个时间单位就允许下一批客户进入。对于进入银行的客户,如果某窗口正空闲,则可上前办理业务,反之,若所有窗口均有客户,他便会排在最短的队伍后面。当平均每个营业窗口前的队伍人数大于等于7人时(队伍包括正在办理业务的客户在内),银行可临时将备用窗口中一个或两个改为营业窗口,当所有窗口平均客户少于7人时,将立即停用一个营业窗口转为备用,窗口平均人数若继续减少至以上情况,可再停止一个营业窗口,但最多只能有两个窗口为备用状态。
现模拟该银行排队程序,效果如图所示,输出10个人各自的等待时间单位:
请输入共有多少批客户:2
输入每一批的人数4,6
(1:0)(2:0)(3:0)(4:1)(5:0)(6:0)
(7:1)(8:1)(9:1)(10:2)
输出格式描述:(客户编号:等待的时间)
(1)实现上述功能的Python程序如下,请在划线处填入合适的代码。
mins=3　#常用窗口3个
maxs=5　#最多可开设5个窗口
lims=7　#正常服务时每个窗口平均等待的最多人数
tm=int(input('请输入共有多少批客户:'))
ps=list(map(int,input('输入每一批的人数').split(',')))
sw=mins
if len(ps)!=tm:
print('输入有误!')
pid,cnt=0,0
head,tail=0,0
qe=[[0,0]]*1000 #创建等待队列
def updatetime(s):
for j in range(len(s)):
s[j][1]+=1
for i in range(tm):
for j in range(sw):　#将轮到的人进行出队
　　if　①　:
　print(f'({qe[head][0]} :{qe[head][1]})',end='')
head+=l
cnt-=1
#人数减少后,检查人数和窗口数是否符合要求并按照要求减少窗口,代码略
if head!=tail:
　②　#更新等待队列里每个人的等待时间
for j in range(ps[i]):
pid+=1
qe[tail]=[pid,0]
tail+=1
cnt+=1
while　③　:
sw+=1
while cnt>0 :
#最后一批人进入银行后,程序只需要处理等待队列剩余人员到出队和窗口的减少,直至人数为0,代码略
(2)共有3批客户,分别为22人,23人,21人,则输出结果中,第4个人等待的时间单位是　　　　。
17.(2022浙北G2联盟期中,16)小明来到探险岛寻宝,岛上共有N个宝藏(标号为0至N-1)。每个宝藏有一条路连接下一个宝藏,宝藏号和下一个宝藏号使用链表存储。小明想知道,从其中一个宝藏出发,最多可以找到多少个宝藏。
例如,共有5个宝藏,输入“1,3,4,4,1,”表示0~4各宝藏点连接的下一个宝藏依次是:1,3,4,4,1(如下表)。则最多可以找到4个宝藏,路径为:0号→1号→3号→4号。
宝藏号 0 1 2 3 4
下一个宝藏号 1 3 4 4 1
程序代码如下:
s=input("请输入宝藏连接的情况:")
t=0;c=" ";a=[]
for i in s:
　if i!=",":
　　c+=i
　else:
　　a.append([t,int(c)])
　　c=" "
　　　　　①　　　
max=0
for head in range(0,t):　 #枚举寻找宝藏起点
　g=[]
　p=head
　while p not in g:
　　g.append(p)
　　　　　②　　　
　if len(g)>max:
　　　　　③　　　
print(max)
(1)若有4个宝藏,且每个宝藏的连接情况为:2,0,0,1,那么小明最多可以挖到的宝藏数是　　　　。
(2)请将代码补充完整。
专题七　数据的组织
考点过关练
考点一　数组
1.(2022浙北G2联盟期中,15)有如下Python 程序段:
import random
a=[]
for i in range(10):
　　　 a.append(random.randint(1,100))
i=0
while i <10:
　　　 if i==0:
　　　　　　i=i+1
　　　 elif a[i-1]<=a[i]:
　　　　　　　　　①　　　
　　　 else:
　　　　　　a[i],a[i-1]=a[i-1],a[i]
　　　　　　　　　②　　　
print(a)
执行该程序段实现了随机生成一个数组,并将其元素递增输出的功能。划线处的代码应该是(　　)
A.① i+=1　② i=1
B.① i-=1　② i=1
C.① i+=1　② i+=1
D.① i-=1　② i-=1
答案　A　
2.(2022绍兴诸暨期中,3)使用列表生成的方式创建数组代码如下:
a=[i*i-1 for i in range(10) if i%2==0]
则数组元素a[3]的值为(　　)
A.2　　　B. 8　　　C. 15　　　D. 35
答案　D　
3.(2022绍兴诸暨期中,4)设有一个5×8的二维数组a,若按行优先的顺序存储数组元素,则元素a[3][5]前面元素的个数为(　　)
A.21　　　B. 22　　　C. 29　　　D. 37
答案　C　
4.(2022绍兴诸暨期中,13)有如下Python程序段:
a=[[0 for i in range(3)]for j in range(3)]
for i in range(3):
　for j in range(3):
　　a[i][j]=i*5+j+1
for i in range(1,3):
　for j in range(2):
　　print(a[j][i],end=" ")
程序段执行后,输出的结果是(　　)
A.2 3 7 8　　　　B.7 12 8 13
C.2 7 3 8　　　　D.6 7 11 12
答案　C　
5.(2022杭州期中,10)下述代码段用于实现在数组a中将新数据k插入下标为 j(0<=j<=8)的位置:
a=[8,6,12,3,5,7,11,2,10,0]
i=8
while i>=j:
　　　　(1)　　
　　　　(2)　　
　　(3)　　
横线处的代码由以下五部分中的三部分组成:
①a[i+1]=k　②a[i]=k　③a[i+1]=a[i]
④a[i]=a[i-1]　⑤i=i-1
下列选项中代码选择与顺序正确的是(　　)
A.③⑤②　　　B.⑤③①　　　C.③⑤①　　　D.④⑤②
答案　C　
6.(2022嘉兴期中,3)用 Python 程序段定义一个3行4列的二维数组(要求先将各元素的值初始化为0,再将第2行第 2 个元素重新赋值为1),以下程序段可行的是(　　)
A. arr=[[0]*3 for j in range(4)]
arr[2][2]=1
B.arr=[[0]*4]*3
arr[1][1]=1
C.arr=[[0 for i in range(4)]for j in range(3)]
arr[1][1]=1
D.arr=[[0,0,0,0]for j in range(3)]
arr[2][2]=1
答案　C　
考点二　链表
1.(2022浙南名校联盟期末,12)一个头指针 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.①②③
答案　A
2.(2022浙北G2联盟期中,14)用两个列表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.②④
答案　D　
3.(2023浙江开学考,10)已知一个链表a,其a[i][0]存储索引i下节点的数据区域,a[i][1]存储索引i下节点的指针区域。对于当前链表中的一个节点p(索引为p),若要删除p的后一个节点q(q=a[p][1]),则应执行语句(　　)
A.a[p]=a[q]
B.a[p][1]=a[q][1]
C.a[p]=a[a[q][1]]
D.a[p]=a[q];a[p][1]=a[q][1]
答案　B　
4.(2022杭州期中,12)在Python中用列表模拟链表结构,某程序段如下:
a=[['H',1],['a',2],['n',3],['g',4],['2',5],['0',6],['2',7],['2',0]]
p, head=3,3;q,c=-1,0;m,n=3,0
while n<4:
　　c=c+1
　　if c==m:
　　　　n=n+1;c=0
　　　　if p==head:
head=a[p][1]
a[q][1]=head
p=a[p][1]
　　　　else:
　a[q][1]=a[p][1]
　p=a[p][1]
　　else:
q=p
p=a[p][1]
#从头节点开始遍历链表a逻辑顺序的所有节点,并依次输出节点的数据,代码略
该程序段执行后的输出结果为(　　)
A.ng02　　　B.g02n　　　C.2an2　　　D.22an
答案　D　
5.(2022诸暨期末,8)某单向链表如图所示,在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]=-1
A.③⑥　　　B.⑤②　　　C.①④　　　D.⑤②④
答案　B　
6.(2022杭嘉湖金月考,15)山顶上有10个圆形排列的洞,一只狐狸和一只兔子各住一个洞。狐狸总想吃掉兔子。一天兔子对狐狸说:“你想吃我有一个条件,先把洞从1~10编上号,你先到1号洞找我;第二次隔1个洞(即3号洞)找我,第三次隔2个洞(即6号洞)找我,依此类推,次数不限。但狐狸从早到晚进进出出了1000次,仍没有找到兔子。请问兔子可能躲在哪个洞里
实现上述功能的Python程序如下,请在划线处填入合适的代码。
hole=[]
n=10
m=1000
#构造一个循环链表,并给n个洞编号,设置洞的初始标志为0
#链表的节点样式为:[洞的标志,洞的编号]
for i in range(n-1):
　　hole.append([0,i+1])
　　　　　(1)　　　　　
#狐狸开始找兔子,将进入过的洞标志改为1,寻找m次结束
head=0
k=head
hole[0][0]=1
for i in range(1,m):
　　for j in range(1,i+2):
　　　　　　　　(2)　　　　　
　　hole[k][0]=1
#输出标志仍为0的洞,即兔子可能的藏身地点
for i in range (len(hole)):
　　if hole[i][0]==0:
　　　　print("兔子可能躲在第"+　(3)　+"号洞")
答案　(1)hole.append([0,0])　(2)k=hole[k][1]　
(3)str(i+1)
考点三　队列
1.(2024届七彩联盟联考,11)有如下程序段:
s=input()
head=0;tail=0;ans=0;tmp=' '
q=[' ']*100
flag=True
for i in range(len(s)):
　if s[i]==',':
　　while head!=tail:
　　　tmp+=q[head]
head+=1
if flag and head　head+=1
flag=not flag
　　ans+=int(tmp)
　　tmp=' ';flag=True
　elif '0'<=s[i]<='9':
　　q[tail]=s[i]
　　tail+=1
输入s为"1-500,2023900-,",执行该程序段,变量ans的值为(　　)
A.100　　　B.22300　　　C.22351　　　D.22400
答案　D　
2.(2022杭州“六县九校”期中,5)有A、B、C、D、E五个人依次进入电梯,结果警告超重了,需要出去一个人才能正常运行,按照数据结构中栈和队列的思维,应离开电梯的人分别是(　　)
A.栈:A　队列:E　　　　B.栈:A　队列:A
C.栈:E　队列:A　　　　D.栈:E　队列:E
答案　C　
3.(2024届强基联盟联考,9)执行下列Python程序段,输出结果为(　　)
data=[1,2,3,1,2,3]
que=[0]*10
head=tail=0
for i in range(len(data)):
if data[i]%2 !=0:
　　que[tail]=data[i]
　　tail+=1
elif tail-head>1:
　　que[tail-1]+=que[head]
　　head+=l
print(que[head:tail])
A.[3,2,1]　　　　B.[1,2,3]
C.[1,3,1]　　　　D.[3,2,3]
答案　D　
4.(2024届新阵地联盟第二次联考,11)有如下程序段:
m=3;n=7
head=tail=0;ans=0
vis=[0]*10;q=[0]*10
for i in range(n):
x=int(input())
if(vis[x]=0):
　ans+=1
　if(tail-head>=m):
　　vis[q[head]]=0
　　head+=1
　q[tail]=x
　tail+=1
　vis[x]=1
print(ans)
运行该程序段,依次输入x的值:1,2,1,5,4,4,1。则程序运行完成后ans 的值是(　　)
A.3　　　B.4　　　C.5　　　D.6
答案　C　
5. (2024届天域全国名校协作体联考,12)已知列表a的长度为6,a[0]至a[5]的值依次为18,12,24,15,21,0,某程序如下所示:
head, tail=0,5
x=a[head]
head+=1
while (head+1) % len(a) !=tail:
　　 t=y=a[head]
head=(head+1) % len(a)
if x　 x,y=y,x
if x % y !=0:
　 a[tail]=x % y
　 tail=(tail+1) % len(a)
x=t
print(a[head])
程序运行后,输出的结果是(　　)
A.24　　　　B.12　　　
C.3　　　　D.0
答案　C　
6.(2023“山水联盟”开学考,11)有如下Python程序代码:
s="ABCDEF"; head=0;tail=0
que=[" "]*100
for i in range(len(s)):
if i%2==0:
　que[tail]=s[i]
else:
　que[tail]=s[len(s)-i]
tail=tail+1
for i in range(len(s)):
print(que[head], end=" ")
head=head+1
以上程序运行后,输出列表的情况是(　　)
A.ABCDEF　　　　B.FEDCBA
C.ACEFDB　　　　D.AFCDEB
答案　D　
考点四　栈
1.(2022浙南名校联盟期末,10)一个栈的入栈序列为“6、9、5、7、8、3”,其出栈序列不可能是(　　)
A.3、8、7、5、9、6
B.7、5、9、8、6、3
C.6、5、7、9、3、8
D.5、9、6、3、7、8
答案　D　
2.(2024届百校起点调研测试,9)栈q初始有三个值,经过一系列入栈、出栈操作后,栈为空,若元素出栈的顺序是1,2,3,4,5,6,7,则栈q初始的情况可能是(　　)
A.[1,2,3]　　　　B.[7,5,6]
C.[6,3,1]　　　　D.[4,7,2]
答案　C　
3.(2024届Z20联盟联考,9)若元素入栈的顺序是1,2,3,4,5,6,不允许连续三次入栈,则可能的出栈序列为(　　)
A.2,3,5,1,6,4　　　　B.1,2,3,6,5,4
C.2,4,3,1,6,5　　　　D.2,5,4,6,3,1
答案　C　
4.(2024届七彩联盟联考,9)假设栈S的最大长度为3,其初始状态和终止状态均为空,经过一系列入栈和出栈的操作,若元素最后的出栈序列为F,E,D,C,B,A,则可能的入栈顺序为(　　)
A.ABCDEF　　　　B.ACDFEB
C.BEFACD　　　　D.BFDECA
答案　D　
5.(2024届嘉兴基测,12)待入栈的序列a有多种出栈序列,以下函数用于判断序列b是不是a的出栈序列,代码如下:
def judge(a,b):
n=len(a);st=[-1]*n
top=-1;i=j=0
while i　top+=1
　　　①　　
　i+=1
　while top>-1 and 　　②　　:
　　top-=1
　　j+=1
return top==-1
from random import shuffle
a=[1,2,3,4,5]
b=[1,2,3,4,5]
shuffle(b)　　#将序列b的元素随机排序
if judge(a,b):
　　print(b,'是', a,'的出栈序列')
else:
　　print(b,'不是',a,'的出栈序列')
程序运行结果如图所示。划线处应填写的语句是(　　)
python 12.py
[2,5,4,3,1]是[1,2,3,4,5]的出栈序列
python 12.py
[5,2,3,1,4]不是[1,2,3,4,5]的出栈序列
A.①st[top]=a[i]　②st[top]==b[j]
B.①st[top]=a[i]　②st[-1]==b[j]
C.①st[top]=b[i]　②st[top]==a[j]
D.①st[top]=b[i]　②st[-1]==a[j]
答案　A　
6.(2022 Z20名校联盟,10)某算法利用“栈”思想进行字符串处理,其步骤如下:①创建长度为n的空栈,字符依次入栈;②当达到栈满状态或数据全部入栈时,字符依次出栈,按照出栈顺序连接成新字符串:③若还有未处理的字符,则重复步骤①②,直到全部字符处理完毕。实现该功能的 Python程序如下:
s=input("请输入字符串:")
n=5;st=[" "]*n
top=-1;i=0;m=" "
while i　while 　(1)　 and i　　　(2)　
　　st[top]=s[i]
　　i+=1
　while top!=-1:
　　m+=st[top]
　　　(3)　
print("密文:" ,m)
加框处(1)(2)(3)的代码由以下代码组成:
①top-=1　②top+=1　③top+1④top下列选项中代码顺序正确的是(　　)
A.④②①　　　　B.③①②
C.③②①　　　　D.④①②
答案　C　
7.(2022诸暨海亮高中月考,10)有如下程序段:
bt=["A","B","C","D",None,"E","F"]
result=[]
stack=[]
i=0
while stack or (i　　if i < len(bt) and bt[i] is not None:
　　　　stack.append(i)
　　　　i=2*i+1
　　else:
　　　　i=stack.pop()
　　　　result.append(bt[i])
　　　　i=2*i+2
print("-".join(result))
则程序运行后输出的结果为(　　)
A.A-B-D-C-E-F　　　　
B.D-B-E-F-C-A
C.D-B-A-E-C-F　　　　
D.A-B-C-D-E-F
答案　C　
考点五　树
1.(2024届Z20联盟联考,8)某二叉树的树形结构如图所示,其后序遍历结果为“物技化数英语”,则中序遍历结果为(　　)
A.语数英物化技　　　　B.物数技化语英
C.语数物化技英　　　　D.化物技英数语
答案　B　
2.(2022名校协作体,10)已知二叉树T2的后序遍历序列为G-D-H-E-B-I-F-C-A,中序遍历序列为D-G-B-E-H-A-C-I-F,则二叉树T2的前序遍历序列为(　　)
A.A-B-D-G-E-H-C-I-F
B.A-B-D-G-E-H-C-F-I
C.A-B-D-G-E-H-F-C-I
D.该二叉树形态不唯一,无法确定
答案　B　
3.(2024届新阵地联盟第二次联考,8)某二叉树的树形结构如图所示,其后序遍历结果为FABGDEC,则中序遍历结果为(　　)
A.FDAGBCE　　　　B.FDABGEC
C.AGBDFCE　　　　D.FDAGBEC
答案　A　
4.(2024届天域全国名校协作体联考,8)下列二叉树中,后序遍历结果不为CBFEAD的是(　　)
　　
　　
答案　D　
5.(2024届七彩联盟联考,8)某二叉树用一维数组表示(见表)。该二叉树从根节点开始,按照从上到下,从左到右的顺序依次用A-H字母表示,该二叉树的中序遍历为(　　)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A B C D E F G H
A.DBGEACFH　　　　B.DBGEACHF
C.DBEGACHF　　　　D.ABCDEFGH
答案　A　
考点六　大数据时代的数据的组织
1.下列关于实时查询数据系统中的数据结构的说法,不正确的是(　　)
A.在实时查询系统中使用数组,时效性较差
B.在链表中查找数据时效性较高,插入数据时效性较低
C.跳跃表基于有序链表
D.跳跃表通过跨区间、跳跃性的比较,避免了依次比较,提高了效率
答案　B　
2.有如下跳跃表:
若要在原链表中插入元素7,则数据元素需要比较的次数为(　　)
A.1　　　B.3　　　C.4　　　D.5
答案　B　
3.下列关于Hadoop的说法,不正确的是(　　)
A.Hadoop是一种超大规模,高可靠性,高可扩展性的数据库
B.Hadoop是Google云计算技术的开源实现
C.使用Hadoop可以在POI数据的处理中获得更方便的体验和更低廉的成本
D.Hadoop可以对海量地理信息进行处理和计算
答案　A　
专题综合练
题组一
1.(2024届名校协作体联考,8)某二叉树的前序遍历结果为GFDECAB,中序遍历结果为DFGCAEB。关于该二叉树,以下说法正确的是(　　)
A.该二叉树的后序遍历为ADFCBEG
B.该二叉树的深度为4,节点C在第3层
C.该二叉树的叶子节点数比非叶子节点数多一个
D.该二叉树可以通过添加3个节点后变为完全二叉树
答案　B　
2.(2024届强基联盟联考,8)某二叉树的树形结构如图所示,其后序遍历结果为FBCEAD,则前序遍历结果为(　　)
A.ABCDEF　　　　B.FEDCBA
C.DFACBE　　　　D.FDBCAE
答案　C　
3.(2024届强基联盟统测,8)已知某二叉树的后序遍历为GDBEHFCA,中序遍历为DGBAECHF,下列说法正确的是(　　)
A.该二叉树中叶子节点有3个
B.该二叉树的前序遍历为ABDGCEHF
C.该二叉树是一棵完全二叉树,树的高度为4
D.该二叉树中度为1的节点有2个
答案　A　
4.(2024届新阵地联盟第二次联考,9)栈S初始状态为空栈,将序列3,2,5,7,1中元素逐一入栈,当栈空或入栈元素比栈顶元素大时则入栈,否则出栈至符合条件再入栈。序列所有元素入栈完毕后,栈内剩余元素出栈,直至栈空。则出栈的顺序是(　　)
A.17523　　　　B.37521
C.37512　　　　D.32751
答案　B　
5.(2024届天域全国名校协作体联考,9)利用栈求逆波兰表达式(表达式由操作数和运算符组成)的方法是:从左往右扫描该表达式,遇到操作数时入栈;遇到运算符时,把处于栈上方的两个元素依次出栈,用运算符计算,并把计算结果压入栈中。如此反复操作,直至表达式扫描结束。当用该算法求逆波兰表达式abcd-*e/+f-的值时(abcdef表示不同的操作数),所使用的栈的深度至少为(　　)
A.3　　　B.4　　　C.5　　　D.6
答案　B　
6.(2024届嘉兴基测,11)长度为5的循环队列que,que[0]至que[4]的值依次为'a','b','c','d','e',执行如下程序段后,输出的最后一个字符为　(　　)
n=5;head=0;tail=4
que=['a','b','c','d','e']
while head!=tail:
　　if head%4==0:
　　　print(que[head])
　　else:
　　　tail=(tai1+1)%n
　　　que[tail]=que[head]
　　head=(head+1)%n
print(que[head])
A.b　　　B.c　　　C.d　　　D.e
答案　B　
7.(2024届发展共同体联考,9)某种特殊的队列Q,支持以下三个操作:
操作Q1:若队列非空,队首元素出队,并输出;
操作Q2:若队列非空,队首元素出队;
操作Q3:一个元素入队。
以上任意一种操作后,若队列非空,新的队首元素仍为队列中所有元素的最小值。
若队列Q初始状态为空,依次进行Q3、Q2、Q1、Q2、Q3、Q1、Q3七次操作后,下列说法正确的是(　　)
A.当前队列中的元素个数为2
B.输出的元素个数为2
C.第一个输出的元素肯定比当前队首元素大
D.队列初始状态是不是空对输出结果有影响
答案　D　
8.(2024浙江1月选考,8,2分)栈S从栈底到栈顶的元素依次为1,2,3,队列Q 初始为空。约定:U 操作是指元素出栈后入队,H 操作是指元素出队后再入队。经过UUHU系列操作后,队列中队首到队尾的元素依次为(　　)
A.2,1,3　　　B.3,1,2　　　C.1,3,2　　　D.2,3,1
答案　D　
9.(2024浙江1月选考,9,2分)数组元素a[0]至a[n-1]依次存放着n个数据,现需要将元素a[n-1]插入在下标为x(0≤xtemp=a[n-1]
for i in range(n-2,x-1,-1):
　　　　　　　　
a[x]=temp
A.a[i+1]=a[i]　　　　B.a[i-1]=a[i]
C.a[i]=a[i+1]　　　　D.a[i]=a[i-1]
答案　A　
10.(2024届发展共同体联考,11)有如下程序段:
s=[' ']*len(a)
head=2;q=head;top=-1
while q!=-1:
　　top+=1
　　s[top]=a[q][0]
　　q=a[q][1]
print(s[top-2])
若a=[['a',3],['b',0],['c',1],['d',-1]],则输出的结果为(　　)
A.a　　　B.b　　　C.c　　　D.d
答案　B　
11.(2024届强基联盟联考,11)有如下Python程序段:
s=input()
stack=[0]* len(s);top=-1;presign='+';num=0
for i in range(len(s)):
if '0'<=s[i]<='9':
　　num=num*10+int(s[i])
if i==len(s)-1 or s[i] in '+-*/':
　　if presign=='+':
　　　　top+=1
　　　　stack[top]=num
　　elif presign=='-':
　　　　top+=1
　　　　stack[top]=-num
　　elif presign=='*':
　　　　top+=1
　　　　stack[top]=stack[top-1]*num
　　else:
　　　　top+=1
　　　　stack[top]=stack[top-1]
//num
　　presign=s[i]
　　num=0
print(sum(stack))　　#sum函数对stack中所有元素求和
若输入'5*4-6+10/3',程序运行后,输出的结果是(　　)
A.32　　　B.24　　　C.17　　　D.8
答案　A　
12.(2023浙江1月选考,15,9分)有2组器件共n个,要用一台检测设备检测。每个送检器件的信息包含送达时间、检测时长和优先级。优先级有m(1编写程序模拟检测过程,先合并2组器件的数据,然后计算所有器件的平均等待时长,其中每个器件等待时长为其开始检测时间与送达时间的时间差。(时间单位均为秒)
请回答下列问题:
(1)由题意可知,图中器件A、B、C、D的检测顺序为A—C—D—B,A、C、D的等待时长分别为0、1、0,B的等待时长是　　　　。
送达时间 检测时长 优先级
A 0 3 2
B 1 1 2
C 2 1 1
D 4 3 0
11 3 2
12 2 2
(2)定义如下merge(lst1, lst2)函数,参数 lst1和 lst2的每个元素由送达时间、检测时长和优先级3项构成,lst1和 lst2均已按送达时间升序排列。函数功能是将lst2中的元素合并到lst1中,并将 lst1按送达时间升序排列,函数返回lst1。
def merge(lst1,lst2):
　　i=len(lst1)-1
　　j=len(lst2)-1
　　for t in range(len(lst2)):
　　　lst1.append([0,0,0])　　#为lst1追加一个元素[0,0,0]
　　k=len(lst1) -1
while j >=0:
　　　if i >=0 and lst1[i][0]>lst2[j][0]:
　 lst1[k]=lst1[i]
i -=1
　　　else:
lst1[k]=lst2[j]
j -=1
　　　k -=1
　return lst1
①调用merge(lst1,lst2)函数,若lst1为[[0,3,2],[1,1,2],[12,2,2]],lst2为[[2,1,1],[4,3,0], [11,3,2]],则while语句中循环体的执行次数是　　　　。
②若函数中 while语句的条件“j>=0”误写为“k>=0”,会导致某些情况下无法得到符合函数功能的结果。调用merge(lst1, lst2)函数,下列4组数据中能测试出这一问题的是　　　　(单选,填字母)。
A.lst1=[[0,3,2],[4,3,0]]
lst2=[[1,1,2]]
B.lst1=[[1,1,2]]
lst2=[[0,3,2],[4,3,0]]
C.lst1=[[1,1,2],[4,3,0]]
lst2=[[0,3,2]]
D.lst1=[[4,3,0]]
lst2=[[0,3,2],[1,1,2]]
(3)实现模拟检测过程并计算平均等待时长的部分Python程序如下,请在划线处填入合适的代码。
def proc(data,m):
　　n=len(data)
　　queinfo=[]
　　for i in range(m):
　　　queinfo.append([-1, -1])
# queinfo追加一个元素[-1,-1]
　　for i in range(n):
data[i].append(-1)　　# data[i]追加一个元素-1
　　curtime=0
waitnum=0
i=0
　　①　　
while i < n or waitnum > 0:
　 if i < n and data[i][0] <=
curtime:
　　　k=data[i][2]
　　　if queinfo[k][0]==-1:
　　　　　queinfo[k][0]=i
　　　else:
　　　　　　　②　　
　　　　　data[p][3]=i
　　　queinfo[k][1]=i
　　　waitnum+=1
　　　i+=1
　　elif waitnum >0:
k=0
while queinfo[k][0]==-1:
　　k+=1
p=queinfo[k][0]
total+=curtime-data[p][0]
curtime+=data[p][1]
　　③　　
waitnum -=1
　　else:
　　　 curtime=data[i][0]
return total / n
'''
读取2组器件的数据,分别存入列表data1和 data2中。2个列表的每个元素包含3个数据项,分别对应器件的送达时间、检测时长和优先级。data1和 data2中的数据已分别按送达时间升序排列,代码略
读取优先级等级个数存入m,代码略
'''
data=merge(data1, data2)
print(proc(data, m))
答案　(1)6或6秒　(2)①4　②A　(3)① total=0或其他等价表达式　②p=queinfo[k][1]或其他等价语句　
③queinfo[k][0]=data[p][3]或其他等价语句
13.(2023浙江6月选考,15,9分)某工程包含n个任务(编号为0~n-1),每天可以有多个任务同时进行。某些任务之间有依赖关系,如图a所示,任务4依赖于任务1,任务1依赖于任务2。即任务2完成后才可以开始任务1,任务1完成后才可以开始任务4。不存在一个任务依赖于多个任务,或多个任务依赖于同一个任务的情况。
现已对该工程的依赖关系进行了梳理,结果如图b所示,标记“T”表示依赖关系需保留,标记“F”表示依赖关系需删除。
根据每个任务完成所需的天数和梳理后的依赖关系,编写程序,首先删除标记为“F”的依赖关系,然后计算工程最快完成所需的天数,并以工程最快完成所需的天数为期限,计算每个任务最晚必须开始的时间。
任务A 任务B 标记
0 5 T
5 4 F
4 1 T
1 2 T
2 3 F
注:任务A依赖于任务B
图b
请回答下列问题:
(1)若某工程有6个任务,任务间依赖关系如图a所示,完成任务0~5所需天数分别为2,1,3,5,1,6,则工程最快完成需要　　天。
(2)定义如下erase(lst)函数,参数 lst列表的每个元素表示一个依赖关系。函数的功能是删除标记为“F”的依赖关系,返回保留的依赖关系的个数。
def erase(lst):
　　i=0
　　j=len(lst)-1
　　while i<=j:
　　　　if lst[i][2]=='T':
　　　　　　i+=1
　　　　else:
　　　　　　if lst[j][2]=='T':
lst[i]=lst[j]
i+=1
　　　　　　j-=1
　　return i
若lst列表依次存储图b所示的依赖关系,如 lst[0]为[0,5,'T'],调用erase(lst)函数,则语句“lst[i]=lst[j]”的执行次数为　　。
(3)实现上述功能的部分Python程序如下,请在划线处填入合适的代码。
def proc(n,lst,task):
pr=[0]*n
w=[0]* n　　# w[i]存放任务最晚必须开始的时间
m=erase(lst)
for i in 　　①　　:
task[lst[i][1]][1]=lst[i][0]
pr[lst[i][0]]=1
c=[]
days=0　　# days存放工程最快完成所需的天数
for i in range(n):
if pr[i]==0:
　　k=i
　　s=0
　　while k!=-1:
　　　　c.append(k)
　　　　s+=task[k][0]
　　　　　　②　　
　　if s > days:
　　　　days=s
for i in range(n-1,-1,-1):
k=c[i]
if task[k][1]==-1:
　　w[k]=days-task[k][0]+1
else:
　　　　③　　
#输出days,以及保存在w中的每个任务最晚必须开始的时间,代码略
"'
工程包含的任务数存入变量n
任务间的依赖关系存入lst列表
lst[0]包含3项,任务lst[i][0]依赖于任务lst[i][1],lst[i][2]存放保留/删除标记,任务数据存入task列表
task[i]包含2项,task[i][0]为完成任务所需天数,task[i][1]的初值为-1
代码略
"'
proc(n,lst,task)
答案　(1)8　(2)1　(3)① range(m)或 range(0, m)或 range(0, m ,1) 或 range (m -1,-1,-1)或 range(erase (lst))或 range(0, erase (lst))或 range(0, erase (lst),1)或 range(erase (lst)-1,-1,-1)　② k=task [k][1]　
③ w [k]=w [task [k][1]]- task [k][0]或 w [k]=w [c [i+1]]- task [k][0]或其他等价答案(这里面可以把 k 换成 c[i])
14.(2024届Z20联盟联考,15)小明同学去看病,当他在一位医生的诊室门口等待就诊的时候,发现了叫号系统的页面上有两行病人名单。第一行名单为正常排队等待就诊的序号,第二行名单为过号或检后再诊而等待的序号。叫号的规则是先在第一行叫2个就诊序号,再到第二行叫1个就诊序号。小明同学回家后将刚才发现的叫号规则编写了Python程序。效果如图所示:
图①:当前到来的就诊序号是3号,为过号或检后再诊序号,进入第二行,先到达先就诊。
图②:当前到来的就诊序号是4号,为过号或检后再诊序号,进入第二行。
图③:当前到来的就诊序号是16号,为正常排队等待就诊的序号,进入第一行,按就诊序号顺序排列。
图④:开始叫号,按照正常排队等待就诊叫号2位,过号或检后再诊叫号1位,得到新的顺序。
(1)请在划线处填入合适的代码。
(2)加框处的代码有误,请改正。
def output(head, a, b):
p=head
head_b=0; tail_b=len(b)
while p!=-1:
　　print(a[p][0], end="->")
　　p=a[p][1]
print()
while head_b!=tail_b:
　　print(b[head_b], end="->")
　　head_b+=1
print()
def insert(data,a,b):　　#根据挂号的序号分别进入第一行名单或第二行名单
　 head_a=a[0][0]
　 if data>　　①　　:
　　　p=0
　　　a.append([data,-1])
　　　while p!=-1:
　　　　　if data<=a[p][0]:
　　　　　　　a[-1][1]=p
　　　　　　　a[q][1]=len(a)-1
　　　　　　　break
　　　　　else:
　　　　　　　q=p
　　　　　　　p=　　②　　
　　　if p==-1:
　　　　　a[q][1]=　　③　　
　　　output(0,a,b)
　 else:
　　　b.append(data)
　　　output(0,a,b)
#a、b赋初值,代码略
#如图①所示:a=[[13,1],[15,2],[17,-1]];b=[3]
while True:
　　data=int(input("请输入取号:"))
#输入0表示停止取号,开始叫号
　　if data==0:
　　　break
　　insert(data,a,b)
print("====开始叫号====")
p=head=0
head_b=0;tail_b=len(b)
while p!=-1 or head_b!=tail_b:
　　if p!=-1 and head_b!=tail_b:
　　　 i=0
　　　 while a[p][1]!=-1:
　　　　　print(a[p][0], end="->")
　　　　　p=a[p][1]
　　　　　i+=1
　　　 print(　　④　　, end="->")
　　　 head_b+=1
　　elif p!=-1 and head_b==tail_b:
　　　 print(a[p][0], end="->")
　　　 p=a[p][1]
　　else:
　　　 print(b[head_b], end="->")
　　　 head_b+=1
答案　(1)①a[0][0]或head_a　②a[p][1]　③len(a)-1
④b[head_b]　(2)i<2 and p!=-1或i<=1 and p!=-1
15.(2022山水联盟开学考,15)小赵同学在某游戏平台中获得虚拟的食物、装备、材料等物品,它们分别有不同的价值,现游戏平台有兑换机制,即可用多个不同物品换取一个等值的物品(每个物品只能取一样),下表为小赵同学已获得的物品。
序号 物品名称 数量 单价
0 灵丹 2 1
1 大力丸 1 2
2 止血草 3 5
3 忘魂花 1 7
4 雄黄 1 9
5 灵山仙芝 5 10
6 梅花镖 1 15
7 止血草 1 20
目标置换物品的价值:35。
已获得物品价值依次是:1,2,5,7,9,10,15,20。
依次拿取物品序号的方案有:
取序号为[0,1,2,3,7]的物品;
取序号为[0,1,3,5,6]的物品;
取序号为[0,2,4,7]的物品;
取序号为[0,4,5,6]的物品;
取序号为[2,5,7]的物品;
取序号为[6,7]的物品。
如要换取游戏中的物品“破天锤”,需要35个金币,有多种置换的方式,为方便计算以节省时间,小赵同学编写了如下程序,运行界面和代码如下,请在划线处填入合适的代码。
def exchange(t,pricelist):
　　n=len(pricelist)
　　stack=[]
　　i=0
　　num=0
　　while　　　①　　　:
　　　　while t>0 and i　　　　　　if t>=int(pricelist[i]):
stack.append(i)
　　②　　
　　　　　　i+=1
　　　　　　if t==0:
　　　　　　　print("取序号为",stack,"的物品")
num+=1
　　　　if 　　　③　　　:
　　　　　　i=stack.pop()
　　　　　　t+=int(pricelist[i])
　　　　　　④　　　
　　if num==0:
　　　　print("无方案")
m=int(input("目标置换物品的价值:"))
price=input("已获得物品价值依次是:")
p=price.split(",")　#将输入的内容以“,”作分隔,并转换为列表
print("依次拿取物品序号的方案有:")
exchange(m, p)
答案　①stack or i16.(2022名校协作体联考,15)某校军训,需要按照身高由低到高排成n行5列的方阵。某班学生按照身高(100≤身高<199)由低到高编写编号并将相关信息存在图1所示的“stu.txt”文件中。根据教官提出的排方阵要求,排成如图2所示的方阵,方阵各点显示学生编号。
　
现有延迟报到学生归队,归队学生编号延续该班现有编号依次往后,编写程序完成下列任务:输入学生身高,输出新的方阵布局图。例如:输入学生身高为168,新的方阵布局图如图3所示,学生在方阵的位置:3,4。
(1)若插入学生身高为160 cm,根据图1及范例,该学生应该在图2方阵中的　　　行　　　　列。
(2)为实现上述功能,请填写划线处代码。
f=open("stu.txt","r")
a=[]
line=f.readline().split()
i=1
while line!=[]:
　　a.append([line[0],line[1], i])
　　i+=1
　　line=f.readline().split()
n=len(a)-1
a[n][2]=-1
sg=input("请输入插入的学生身高(cm):")
xh=str(len(a))
head=1
p=head;q=head
while　　　①　　:
　　p=q
　　q=a[q][2]
if q==head:
　　　　②　　
　　head=len(a) -1
else:
　　a.append([xh,sg,a[p][2]])
　　a[p][2]=len(a)-1
p=head
m=1
while p!=-1:
　　if m!=5:
　　　　print(a[p][0],end=" ")
　　　　m+=1
　　else:
　　　　print(a[p][0])
　　　　m=1
　　　　　　③　　
答案　(1)1,5　(2)①a[q][1]17.(2022 A9协作体返校考,15)学校举办了“语文作文现场赛”,参赛同学成绩存储在文本文件“gra.txt”中,如图a所示(每一行记录一位同学的姓名和成绩,以“:”分隔)。陈老师利用Python程序对作文成绩进行处理,统计出各个分数等级的人数,并输出结果。程序运行界面如图b所示。
实现上述功能的Python程序如下,请在划线处填入合适的代码。
def cla(x):　#判断成绩等级
　　if x>=50:
　　　return "A"
　　elif x>=40:
　　　return "B"
　　elif x>=30:
　　　return "C"
　　else:
　　　return "D"
gra=[]　#存储各个整数型成绩
num=[0]*4
f=open("gra.txt")
lines=f.readlines()　#将f对象的数据按行存入列表lines中
f.close()　#关闭文件
for line in lines:　#循环读取列表lines 中的每个元素,并做相应处理
　　a=line.strip().split(":") #去除结尾的换行符并以冒号为分隔符进行分隔
　　gra.append(　　①　　)
for i in range(len(gra)):　#统计各等级人数
　　t=　　②　　
　　num[ord(t)-65]+=1
print("成绩分布如下: ")
for i in range(len(num)):　#输出统计结果
　　print(chr(i+65)+"等级有"+　③　+"人")
答案　①int(a[1])或int(a[-1])　②cla(gra[i])
③str(num[i])
18.(2023七彩阳光开学考,15)食堂推出的三款特色菜,分别用A、B、C表示,想用投票方式统计出三款菜的受欢迎程度。每位投票者需要将三款菜按喜爱程度从高到低进行排列,并投出一票。如图a所示,小明负责将文件“投票.txt”中的选票进行统计。第1张选票信息为“A,C,B”,表示投票者认为A菜优于C菜,C菜优于B菜,即A菜也优于B菜。他得到如图b所示的投票情况。对选票进行统计,得到三款菜的偏好,如图c所示,数据第一行中的“6”说明有6张选票显示A菜优于B菜,“10”说明有10张选票显示A菜优于C菜,以此类推……将所有投票进行统计,再将三款菜的得票数进行求和,按得票数从高到低排列,分别为A菜16票,B菜11票,C菜12票,即可得到每款菜的受欢迎程度。
　　　　
　　　　
请回答下列问题:
(1)若有四款菜,投票情况如图d所示,则第2受欢迎的菜为　　　　(填字母)菜。
(2)加框处代码有错误,请改正。
(3)实现上述功能的 Python程序如下,请在划线①②③处填入合适的代码