资源简介

(共57张PPT)
课时24 队列
一、队列的概念
1. 概念：队列是一种　　　　的线性表，允许插入的一端称为　　　　 ，允许删除的一端称为　　 　。在队列中插入一个元素称为入队，从队列中删除一个元素称为出队。
2. 图示，以队列 a 为例。
先进先出
队首
队尾
1. 先进先出、后进后出。队列具备“先进先出，后进后出”的特点，队列元素根据入队的顺序出队。
2. 有限序列性。队列是一种　　　　结构，元素个数是有限的。队列中可以有零个或多个元素，队首元素只有一个　　　　，队尾元素只有一个　　　　，其他队列元素既有一个唯一的前驱点，又有一个唯一的后继点。
线性表
后继点
二、队列的特性
前驱点
1. 队列的实现。
（1）数组实现的队列。
①当队列中的数据进行出队和入队操作时，队列中的队首元素和队尾元素也在相应变化。例如，在上图中，若队首元素 a1 出队，则　　　　成为队首元素，此时可以设置一个头指针变量 head 和尾指针变量 tail 分别记录队首元素和队尾元素的变化。head 记录　　　　元素所在的位置，tail 记录　　　　元素的下一个位置。
三、队列的基本操作
a2
队首
队尾
②tail指向队尾元素的下一个位置而不是队尾元素所在位置是用以区分队列为空和队列中只有一个元素的情况。如图所示，当队列为空时，head=tail；当队列中只有一个元素时，tail=head+1。
（2）链表实现的队列。
①队列的链式存储称为　　　　。队首指针 head 记录链表的头节点，队尾指针 tail记录链表的队尾节点。
②注意链表的头节点是一个另外设置的空节点，不存储数据，方便处理队列为空的情况。
链队列
2. 建队（数组表示）。
（1）使用数组存储队列，可利用 Python 中的　　　　结构，初始化数组空间以及 head 和 tail指针。
（2）创建一个长度为 5 的队列 a 的 Python 代码。
a=[0]*5 #初始化的数值取决于队列中的数据类型
head=0
tail=0
列表
3. 入队、出队。
（1）使用数组实现队列，入队操作是使　　　　指针变量加 1，出队操作则是使
　　　　指针变量加 1，两个指针之间的区域表示队列中的数据，当 head 值与 tail 值相等时，表示队列为　　　　。
（2）元素入队、出队代码示例。
que=[0]*10
head=0
tail=0
que[tail]=23 #元素 23 入队
tail+=1 #队尾指针后移
que[tail]=78 #元素 78 入队
tail+=1
que[tail]=19 #元素 19 入队
tail+=1
head+=1 #队首元素出队
print(que[head:tail]) #输出队列中的所有元素
#输出：[78,19]
tail
head
空
4. Python 自带的队列模块可以实现队列的建队、入队、出队等操作。
import queue #引入队列模块
q=queue.Queue(10) #建一个长度为 10 的队列 q
q.put("A") #字母 A 入队
q.put("B") #字母 B 入队
print(q.qsize()) #输出队列中元素的个数，个数为 2
print(q.get()) #队首元素出队，出队元素为 A
print(q.qsize()) #输出队列中元素的个数，个数为 1
1. 对于队列，进行多次出队、入队操作后，会出现 tail 指针已经超出了队列的边界，head 指针指向了队列中某处位置，这样队尾无法继续进行入队操作，而 head 指针前面又存在空闲部分的情况，这种现象叫作队列“假溢出”，如图所示。
2. 循环队列是将队列的队首和队尾连接起来，形成逻辑上的环状结构。当对循环队列中的元素进行入队、出队操作时，队首指针变量和队尾指针变量可以循环指向所有位置，从而有效地解决队列中“假溢出”的问题。
四、循环队列
3. 将上图所示的队列改为循环队列，如图所示，则在元素“E”入队后，head 的值为 4，队尾指针重新指向队首（tail 的值为 0），当新元素“F”入队时，就加入到队首，然后 tail 的值变为 1。
4. 当队列满时，会留出一个空间，这样就便于和队列为空时做区分，如图所示。当循环队列为空时，满足 head==tail；当循环队列为满时，满足(tail+1)%n==head（n 为队列最大长度）。
5. 循环队列中，元素出队时，队首指针 head=(head+1)%n；入队时，队尾指针 tail=(tail+1)%n。队列中的元素个数为(tail-head+n)%n。
典例 1 已知某非循环队列的实现方式是数组或链表，其指针条件为 head=tail-3，则下列说法正确的是 （　　）
A.该队列中一定有 3 个元素
B.若该队列以数组实现，则该队列的长度为 3
C.若该队列以链表实现，则该队列的长度为 3
D.该队列中最先出队的元素一定是tail位置的元素
B
√
题型导向一　队列的特性
胜券点拨1
明考向 本题主要考查非循环队列的特性
审关键 非循环队列的队首元素及队尾元素的关系、队列中元素个数的计算
考场思维快闪 A 队列实现的方式不确定，则其中元素的个数也不一定
B 在数组实现的队列中，队列元素的个数是tail-head
C 在链表实现的队列中，由于存储位置的随机性，队列元素的个数不能通过队首指针和队尾指针确定
D 队列中最先出队的元素是队首元素，即head位置的元素
典例 2 若元素 2，5，6，7，9 依次入队一个空队列后全部出队，则元素的出队顺序是 （　　）
A.2，5，6，7，9
B.9，7，6，5，2
C.2，5，9，7，6
D.9，2，5，6，7
A
√
胜券点拨2
明考向 本题主要考查队列的特性
审关键 队列的入队与出队操作
考场思 维快闪 队列是先进先出的数据结构
典例 3 在某银行排队叫号系统中，利用队列来存储当前正在排队的顾客的编号，head 指向队首元素，tail 指向队尾元素的下一个位置，若现在队列中顾客的数量为 4，则 head和 tail的关系正确的是 （　　）
A.head==tail+3
B.head==tail+4
C.tail==head+3
D.tail==head+4
D
√
胜券点拨3
明考向 本题主要考查非循环队列的特性
审关键 非循环队列的队首元素及队尾元素的关系
考场思 维快闪 若现在队列中顾客的数量为4，则head的值为0，tail的值为4，故head和tail的关系正确的是tail==head+4
典例4　［2025.6浙江选考］某队列中队首到队尾的元素依次为A,B,C,D,E。元素出队后直接输出或重新入队，若输出次序为B,D,C,E,A，则元素A重新入队的最少次数为 （　　）
A.1 B.2 C.3 D.4
B
√
题型导向二　队列的基本操作
胜券点拨4
明考向 本题主要考查队列的基本操作
审关键 出队后直接输出或重新入队
考场思维快闪 出队入队过程如下：A出队后入队，B出队并输出；C出队后入队，D出队并输出；E、A出队后入队，C、E、A出队并输出
典例 5 ［2023.1 浙江选考］有 1 个队列，队首到队尾的元素依次为 8，3，2，9，5。约定：T 操作是指队列中 1 个元素出队后再入队，Q 操作是指队列中 1 个元素出队。则经过 TTTQTTQ 系列操作后，队列中队首到队尾的元素依次为 （　　）
A.2，9，5
B.2，5，8
C.5，8，2
D.8，3，2
B
√
胜券点拨5
明考向 本题主要考查队列的特性和队列的相关操作
审关键 队列中的数据遵循“先进先出”的原则
考场思 维快闪 根据题目的描述，逐步对队列中的元素进行操作。三次“T”操作后，队列中队首到队尾的元素依次为9，5，8，3，2；一次“Q”操作后，队列中的元素依次为5，8，3，2；两次“T”操作后，队列中的元素依次为3，2，5，8；最后进行一次“Q”操作后，队列中的元素依次为2，5，8
典例 6 ［2023.6 浙江选考］列表 q 长度为 20，q[0]至 q[4]的值依次为'p'，'r'，'i'，'n'，'t'，执行如下程序段后，输出的最后一个字符为 （　　）
head,tail=0,5
while headif head%3==0:
print(q[head])
else:
q[tail]=q[head]
tail+=1
head+=1
A.t B.n C.i D.r
D
√
题型导向三　队列的Python实现
胜券点拨6
明考向 本题主要考查队列
审关键 队列的程序实现
考场思 维快闪 根据队列基本操作可知该程序段的功能是：当队列q非空时，若队首指针head%3==0，执行“出队并输出”操作，否则执行“出队并入队”操作，故输出的最后一个字符即最后一个出队的元素
典例 7 ［2025 强基联盟］有如下 Python 程序段：
s="hAp#py"
que=[""]*10
head,tail=0,0
res=""
for i in range(len(s)):
if "a"<=s[i]<="z":
que[tail]=s[i]
tail+=1
else:
head+=1
print(que[head:tail])
执行该程序段后，输出的结果是 （　　）
A.["h","p","p","y"] B.["p","p","y"] C.["p","y"] D.["y"]
C
√
胜券点拨7
明考向 本题主要考查队列的Python实现
审关键 队列的入队与出队操作
考场思 维快闪 该程序段遍历字符串s，若为小写字母，则入队que，否则出队队首元素。最后输出队列que中的元素。首先"h"入队后出队，接着"p"入队后出队，接着"p""y"入队，故输出的结果是["p","y"]
典例8　［2026浙江名校协作体］有如下Python程序段：
import random
a=["信","-","息","+","技","术","+"]
que=[0]*len(a)
head=tail=0
for i in range(len(a)):
pos=random.choice(["m","n"])
if pos=="m" and a[i]!="-":
que[tail]=a[i]
a[i]="-"
tail+=1
elif pos=="n" and head!=tail and a[i]!="+":
a[i]=que[head]
head+=1
tail+=1
B
√
运行该程序段后，下列说法不正确的是 （　　）
A.列表que的值可能是
["信","息","技","术",0,0,0]
B.列表que的值不可能是
["信",0,"息","技","术","+",0]
C.列表a的值可能是
["信","-","息","+","-","技","+"]
D.列表a的值不可能是
["+","+","+","+","+","+","+"]
胜券点拨8
明考向 本题主要考查队列的Python实现
审关键 入队和出队操作
考场思维快闪 该程序遍历a的每个元素，每次随机取出"m"或"n"赋值给pos。当pos为"m"时：若当前元素a[i]不是"-"，则将a[i]入队que，然后将a[i]替换为"-"。当pos为"n"时：若队列非空且a[i]不是"+"，则将队首元素出队并赋值给a[i]，同时队尾指针tail后移1位。在i=0执行"m"操作，i=1执行"n"操作，i=2执行"m"操作，i=3执行"n"操作，i=4执行"m"操作，i=5执行"m"操作，i=6执行"m"操作，可以使que值为["信",0,"息","技","术","+",0]
典例 9 有如下 Python 程序段，通过自定义函数，封装队列的入队、出队方法，请在画线处填入合适的代码。
queue=[] #建立空列表表示一个空队列
#判断队列是否为空
def empty(queue):
if len(queue)==0:
flag=True
else:
flag=False
return flag
#元素入队
def enqueue(queue,elem):
　　　①　　　 #元素 elem 入队
#元素出队并输出出队元素
def outqueue(queue):
if empty(queue)==True:
return "队列为空"
else:
#队首元素出队，并存放在变量 x 中
x=　　　②　　　1
return x
queue.append(elem)
queue.pop(0)
胜券点拨9
明考向 本题主要考查队列的Python实现
审关键 使用Python列表的自带方法实现队列建队、入队和出队操作
考场思维快闪 ① ①处通过向列表末尾添加元素的方法来实现入队操作，使用queue.append(elem)方法
② ②处将队列中的队首元素出队，使用列表自带的pop()方法，因为pop()方法默认删除列表末位的数据，所以参数要指定删除的元素是队首元素，即下标位置为0的队列元素
典例 10 用一个包含 10 个元素的数组存储循环队列，当队首元素指针 head 和队尾指针 tail 满足条件(tail+1)%10==head时，表示队满。当 head=3，tail=8 时，先入队 4 个元素，再出队 2 个元素，则 head 和 tail 的值以及队列长度分别是 （　　）
A.2，5，7
B.2，5，3
C.5，2，3
D.5，2，7
D
√
题型导向四　循环队列
胜券点拨10
明考向 本题主要考查循环队列
审关键 循环队列的入队和出队
考场思 维快闪 当head=3，tail=8时，队列中有5个元素。入队4个元素，执行4次tail=(tail+1)%10，得到tail的值为2，此时队列中有9个元素。出队2个元素，执行2次head=(head+1)%10，得到head的值为5，此时队列中有7个元素
典例 11 ［2025 天域协作体］有如下 Python 程序段：
from random import randint
n=5;q=[0]*n
head=tail=randint(0,n-1)
while head!=(tail+1)%n:
num=randint(1,n)
if q[head]!=num:
q[tail]=num
tail=(tail+1)%n
else:
q[head]=0
head=(head+1)%n
执行该程序段后，列表 q 的值可能是 （　　）
A.[1,2,3,4,5] B.[3,0,1,4,1] C.[5,0,1,2,3] D.[1,0,0,4,3]
C
√
胜券点拨11
明考向 本题主要考查循环队列
审关键 随机函数、循环队列的入队与出队
考场思 维快闪 该程序段使用长度为n的列表q（初始值都为0，表示队列为空）模拟循环队列，head和tail随机初始化为[0,4]范围内的同一整数，变量num为[1,5]范围内的随机整数，若队列q的队首元素不是num，则将num入队，否则将队首元素置为0，然后队首元素出队，执行上述操作直到队满为止。满循环队列会留出一个空间，因此列表q中一定且只存在一个值为0的元素（选项A、D不可能），且元素0后面的位置表示队首，根据上述分析可知，队列q中不存在与队首元素相同的元素（选项B不可能）
典例 12 ［2025.1 浙江选考］列表 c 长度为 100，如图所示，其中 c[10]~c[89]各元素的值均为 10 以内的随机正整数。执行如下程序段，输出的最后一行是
（　　）
qa=[0,0,0,0,0]
qb=[0,0,0,0,0]
h,t=0,4
temp=0
for k in range(100):
qa[t]=c[k]
qb[t]=temp+qa[t]-qa[h]
print(qb[h],qb[t])
temp=qb[t]
t=(t+1)%5
h=(h+1)%5
A.5 4 B.8 4 C.9 5 D.9 9
B
√
胜券点拨12
明考向 本题主要考查循环队列
审关键 滑动窗口问题
考场思 维快闪 变量h和t通过求余操作，使其值在[0,4]范围内循环，代码“qb[t]=temp+qa[t]-qa[h]”表示加上后一项的值并减去第一项的值，而qa[t]=c[k]，所以列表qb存储的是列表c中连续4项元素值的和，这实现了一个滑动窗口的累加计算，每次循环更新窗口内的一个元素。最后一次循环时，窗口内的元素是c[96]~c[99]，qb[t]存储窗口内的元素和，即4，而h的值为(t-4)%5，对应窗口为最后一个窗口向左滑动4个元素的窗口，qb[h]的值即c[92]~c[94]的元素和，即8
若有一个普通队列和一个循环队列的最大容量都为 n，两个队列中 head 指向队首元素所在的位置，tail 指向队尾元素的下一位置，则关于这两种队列中数据元素的个数以及判断队列为空的条件如表所示。
项目 普通队列 循环队列
队列中数据元素个数 tail-head (tail-head+n)%n（同样适用于普通队列）
队列为空的条件 tail==head
通法一　普通队列与循环队列辨析
项目 普通的方法 列表自带的方法 queue模块（已导入模块）
建队 q=[0]*n head=0 tail=0 q=[] q=queue.Queue(n)
判断队列是否为空 head==tail len(q)==0 q.empty()
将“A”入队 q[tail]="A" tail+=1 q.append("A") q.put("A")
出队 head+=1 q.pop(0) q.get()
返回队列元素个数 tail-head len(q) q.qsize()
通法二　常见队列问题的Python实现
1.下列关于队列概念的说法，正确的是 （　　）
A.队列是先进后出的线性表
B.队列可以从队首和队尾删除元素
C.队列元素从队尾入队
D.队列中可以存放无限多个队列元素
队列是先进先出的线性表。队列只允许从队首删除元素，从队尾插入元素。队列中的元素个数是有限的。
一、队列的特性
C
√
2.［2026.1浙江选考］队列初始为空，字符“甲”“乙”“丙”“丁”“戊”“己”依次入队的规则为：若队列为空，字符入队；否则队首元素出队后再入队，然后字符入队，重复执行直到字符全部入队。字符全部入队后，队首元素为 （　　）
A.丁 B.己 C.甲 D.乙
模拟队列操作过程如表所示。故字符全部入队后，队首元素为“乙”。
D
√
二、队列的基本操作
操作过程 队列状态
“甲”入队 甲
“甲”出队后再入队，“乙”入队 甲乙
“甲”出队后再入队，“丙”入队 乙甲丙
“乙”出队后再入队，“丁”入队 甲丙乙丁
“甲”出队后再入队，“戊”入队 丙乙丁甲戊
“丙”出队后再入队，“己”入队 乙丁甲戊丙己
3.［2025强基联盟］在某一队列（非循环队列）中，使用head记录队首元素所在位置，tail记录队尾元素的下一位置，约定：T操作指队列中1个元素出队后再入队，Q操作指队列中1个元素出队。若经过TTQTTQ系列操作后，head=6，tail=9，则在操作前队列中的元素个数是 （　　）
A.1 B.3 C.5 D.7
C
√
每个T操作都有一个元素入队，一个元素出队，每个Q操作都有一个元素出队，每入队一个元素，tail+=1，每出队一个元素，head+=1，则经过TTQTTQ系列操作后，有4个元素入队，6个元素出队，即操作前head=6-6=0，tail=9-4=5，队列中元素个数=tail-head=5。
4.有如下Python程序段：
s="abcdefghij"
q=[""]*10
head,tail=0,0
for i in range(len(s)):
　if i%3==1:
　　head+=1
　else:
　　q[tail]=s[i]
　　tail+=1
while head!=tail:
　print(q[head],end=" ")
　head+=1
D
√
该程序段首先定义一个长度为10的空队列q。遍历字符串s中的元素，若i的值为1、4、7，则出队队首元素，否则将元素s[i]入队。最后依次输出队首元素并出队。当s="abcdefghij"时，操作过程依次为：a入队；a出队；c、d入队；c出队；f、g入队；d出队；i、j入队。最后输出队列q中的元素为f g i j。
三、队列的Python实现
执行该程序段后，输出的结果是 （　　）
A.a c d f g i j B.d e f g h i j
C.g h D.f g i j
5.有如下Python程序段：
a=[13,16,15,10,11]
b=[38,30,36,38,35]
q=[0]*10
head=0;tail=0
for i in range(5):
　if a[i]%2==0 and b[i]%2==0:
　　q[tail]=a[i]
　　tail+=1
　　q[tail]=b[i]
　　tail+=1
　elif head　　head+=1
　　print("出队")
执行该程序段后，队列q中的元素个数是 （　　）
A.3 B.8 C.4 D.1
当a与b同一位置的元素值都为偶数时，这两个元素依次入队；当队列非空且a和b同一位置的元素值都为奇数时，队列q中队首元素出队。根据该规律可知，当i为1时，16和30入队；当i为3时，10和38入队，此时tail的值为4；当i为4时，16出队，head的值为1，所以此时队列q中的元素为30，10，38。
A
√
6.有一个循环队列，长度为15，头指针为head，尾指针为tail，则下列选项中队列元素个数与其他三项不同的是 （　　）
A.head=3，tail=8
B.head=8，tail=13
C.head=10，tail=0
D.head=14，tail=9
循环队列中的元素个数为(tail-head+n)%n。选项A中队列元素个数=(8-3+15)%15=5。选项B中队列元素个数=(13-8+15)%15=5。选项C中队列元素个数=(0-10+15)%15=5。选项D中队列元素个数=(9-14+15)%15=10。
D
√
四、循环队列
7.［2025金色阳光联盟］有如下Python程序段：
que=["A","B","C","D","E","F","G"]
head=0;tail=6
k=0;n=len(que)
m=int(input())
while head!=tail:
　k=k+1
　t=que[head]
　head=(head+1)%n
　if k==m:
　　print(t,end="")
　　k=0
　else:
　　que[tail]=t
　　tail=(tail+1)%n
B
√
该程序段模拟循环队列的操作。每次循环k的值累加1，然后出队队首元素并存储在t中，当k等于m时，输出t的值，k置为0；当k不等于m时，入队t，直到队列为空时退出循环。程序中初始head=0，tail=6，则初始循环队列为ABCDEF。若输入m的值为2，则操作过程为：A出队后入队；B出队并输出；C出队后入队；D出队并输出；E出队后入队；F出队并输出；A出队后入队；C出队并输出；E出队后入队；A出队并输出；E出队后入队；E出队并输出。故输出的结果是BDFCAE。
执行该程序段后，若输入m的值为2，则输出的结果是
（　　）
A.BDFACE B.BDFCAE
C.BDFAECG D.BDFACGE
8.有“甲”“乙”“丙”“丁”“戊”5位游客已按序排队，定义下列操作：顺利买票进入景区，记为Q1；缺少证件需要重新排队，记为Q2；新游客进来排队，记为Q3。若游客“丁”买票时，发现游客“乙”在“丁”的后两位，则已进行的操作过程可能是 （　　）
A.Q3，Q1，Q2，Q1
B.Q1，Q2，Q2，Q3
C.Q1，Q2，Q3，Q3
D.Q2，Q2，Q1，Q3
B
√
根据题干描述可知，Q1为出队，Q2为出队后入队，Q3为入队。游客“丁”买票时，“丁”在队首，说明“甲”“乙”“丙”已出队，故前3次操作一定是Q1或Q2，第4次操作一定是Q3。游客“乙”在“丁”的后两位，说明“乙”重新入队到“戊”的后面，故第1次操作一定是Q1（“甲”出队），第2次操作一定是Q2（“乙”出队后入队）。
9.［2026江浙皖发展共同体］5位同学（学号为1~5）随机排成一队，从队首同学开始“1，2，3，1，2，3，…”报数，报到3的同学出列，队尾同学报数完由队首同学继续报数，直到队列中只剩下一位同学为止。若出列同学的学号依次为2，4，1，5，则5位同学的初始队列顺序为 (　　)
A.4，5，2，3，1
B.4，5，2，1，3
C.5，4，2，1，3
D.5，4，2，3，1
A
√
设排成一队的5个位置序号为1，2，3，4，5，则根据规则，出队的位置序号依次是3，1，5，2，最后剩下位置4。若出列同学的学号依次为2，4，1，5，对应到出队位置序号上，则学号2在位置3，学号4在位置1，学号1在位置5，学号5在位置2，最后剩下学号3在位置4，即5位同学的初始队列顺序为4，5，2，3，1。
10.［2025绍兴模拟］某设备按优先级1~4依次发送数据，利用队列S组织数据并模拟发送过程。初始队首至队尾的数据依次为S1，S4，S3，S2，各数据优先级如图所示。可利用M操作（出队后再入队）调整数据发送顺序，为将数据发送完毕，M操作的执行次数至少是
（　　）
A.4 B.5 C.6 D.7
B
√
数据 优先级
S1 3
S2 4
S3 1
S4 2
第1个发送的数据是S3（优先级为1），则先将S1和S4出队后入队，即执行2次M操作，然后S3出队，此时队列S为S2，S1，S4。第2个发送的数据是S4（优先级为2），则先将S2和S1出队后入队，即执行2次M操作，然后S4出队，此时队列S为S2，S1。第3个发送的数据是S1（优先级为3），则先将S2出队后入队，即执行1次M操作，然后S1出队，此时队列S为S2。最后发送数据S2（优先级为4）。故M操作的执行次数至少是2+2+1=5。
执行该程序段后，变量res的值是（　　）
A.["t","y","","",""]
B.["a","e","s","y",""]
C.["a","e","i","s","y"]
D.["a","s","y","",""]
11.有如下Python程序段：
res=[""]*5
head=0
tail=0
a="takeiteasy"
for i in range(len(a)):
　if tail-head==0 or a[i]>res[tail-1]:
　　res[tail]=a[i]
　　tail+=1
　elif tail-head==1:
　　res[head]=a[i]
　elif tail-head>1 and a[i]>res[tail-2]:
　　res[tail-1]=a[i]
C
√
for循环遍历字符串a，当队列为空或a[i]大于队尾元素时，将a[i]入队；否则当队列长度为1时，将a[i]赋值给队首元素；否则当队列长度大于1，且a[i]大于队列中倒数第二个元素时，将a[i]赋值给队尾元素。该程序段的执行过程如表所示。
i a[i] 执行操作 res
0 "t" "t"入队 ["t","","","",""]
1 "a" 队首元素更新为"a" ["a","","","",""]
2 "k" "k"入队 ["a","k","","",""]
3 "e" 队尾元素更新为"e" ["a","e","","",""]
4 "i" "i"入队 ["a","e","i","",""]
5 "t" "t"入队 ["a","e","i","t",""]
6 "e" — ["a","e","i","t",""]
7 "a" — ["a","e","i","t",""]
8 "s" 队尾元素更新为"s" ["a","e","i","s",""]
9 "y" "y"入队 ["a","e","i","s","y"]
当参数data为[1,1,3,2,2,3,0,1,2,0,1,3]，m为4时，该函数返回的结果是 (　　)
A.[1,1,3,2] B.[2,3,0,1]
C.[3,0,1,2] D.[2,0,1,3]
12.［2026天域名校协作体］有如下自定义函数：
def select(data,m):
　f=[0]*m
　ans=len(data)
　cnt=0
　head=tail=0
　newdata=[]
　while tail　　f[data[tail]]+=1
　　if f[data[tail]]==1:
　　　cnt+=1
　　tail+=1
　　while f[data[head]]>1:
　　　f[data[head]]-=1
　　　head+=1
　　if cnt==m and tail-head　　　ans=tail-head
　　　newdata=data[head:tail]
　return newdata
B
√
函数select(data,m)用于在data中寻找包含0到m-1所有数字的最短连续子数组。给定data=[1,1,
3,2,2,3,0,1,2,0,1,3]和m=4，函数通过移动head和tail指针维护窗口，并更新最短满足条件的子数组。初始f=[0,0,0,0]，ans=12，cnt=0，head=0，tail=0，newdata=[]。随着tail移动，当窗口包含0、1、2、3（即cnt为4时），且窗口长度小于当前ans时，更新ans和newdata。首先遇到的最短子数组为[2,3,0,1]（长度为4），之后遇到长度同为4的子数组[3,0,1,2]和[2,0,1,3]，因长度未更小而不更新。因此函数返回的结果是[2,3,0,1]。
13.［2025浙江联考］某医院为提高效率，引进了一个“挂号就诊排队系统”。该系统每天共放出100个号，编号为1~100，医生每天8:30开始出诊。患者预约挂号，按照挂号的时间顺序给患者由小到大发放对应编号；患者到医院就诊时需要到签到机上进行签到排队；患者当天初诊后可以进行回诊，回诊需要在签到机上再次签到排队。签到排队规则：①患者签到后开始排队，签到后患者按照挂号的编号由小到大排队；②回诊患者问诊优先于出诊患者。
（1）假定患者的挂号签到信息如图所示，0代表初诊，1代表回诊，假定编号为1，3，6，8，10的患者初诊问诊时长分别为8，5，8，6，10，编号为10的患者回诊问诊时长为9，根据题意可知，患者的叫号就诊顺序为（按挂号编号叫号）8，10，3，1，10，6。若编号为3的患者签到时间改为08:35，则患者的叫号就诊顺序　　　　　　　（选填：会 / 不会）发生变化。
会
√
（1）若编号为3的患者签到时间改为8:35，则患者的叫号就诊顺序为8，3，10，1，10，6。
（2）定义如下px(data)函数，参数data的每个元素由“挂号编号”“签到时间”“是否回诊”3个数据项组成。函数的功能是根据签到时间对元素升序排序。
def px(data):
　p_wait=[[] for i in range(len(data))]
　x=0
　for i in range(len(data)):
　　'''将时间转换成分钟，如8:30转换为510'''
　　t=int(data[i][1][:2])*60+int(data[i][1][3:])
　　 　　　　　　　
　　while j>=0 and t　　　p_wait[j+1]=p_wait[j]
　　　j-=1
　　p_wait[j+1]=[data[i][0],t,data[i][2]]
　　x+=1
　return p_wait
①请在画线处填入合适的代码。
①j=i-1　或　j=x-1
②若将加框处代码“j>=0 and t0 and tA.p_wait=[[1,510,0],[10,520,0],[""]]
　t=515
B.p_wait=[[1,510,0],[""]]
　t=515
C.p_wait=[[10,520,0],[""]]
　t=510
D.p_wait=[[10,520,0],[1,530,0],[""]]
　t=520
C
√
（2）①px(data)采用插入排序算法，p_wait[0]~p_wait[i-1]为有序区间，将p_wait[i]插入到该区间中，j从后往前，查找应插入的位置，故填入代码为j=i-1或j=x-1。②若误写成“j>0 and t（3）实现模拟排队叫号的部分Python程序如下，请在画线处填入合适的代码。
import random as rd
def proc(p_wait):
　n=len(p_wait)
　queinfo=[-1,-1]
　for i in range(n):
　　p_wait[i].append(-1)
　#模拟时间推进（医生08:30开始叫号）
　call_time=510
　waitpatient=0;i=0;jzxx=[]
　while 　　　①　　　:
　　if i　　　k=p_wait[i][2]
　　　if queinfo[k]==-1:
　　　　queinfo[k]=i
　　　else:
　　　　head=queinfo[k]
　　　　p=pre=head
①i0　或　len(jzxx)　　　　while p!=-1 and p_wait[i][0]>p_wait[p][0]:
　　　　　pre=p
　　　　　p=p_wait[p][3]
　　　　if p==head:
　　　　　p_wait[i][3]=head
　　　　　　　　② 　　　
　　　　else:
　　　　　p_wait[i][3]=p
　　　　　p_wait[pre][3]=i
　　　waitpatient+=1;i+=1
　　elif waitpatient>0:
　　　k=1
　　　while queinfo[k]==-1:
　　　　k-=1
　　　　　　③ 　　　
　　　if k==1:
　　　　jzxx.append(str(p_wait[p][0])+"（回诊）")
②queinfo[k]=i　
③p=queinfo[k]
　　　else:
　　　　jzxx.append(p_wait[p][0])
　　　queinfo[k]=p_wait[p][3]
　　　waitpatient-=1
　　　#随机模拟患者就诊花费时间
　　　call_time+=rd.randint(5,10)
　　else:
　　　call_time=p_wait[i][1]
　return jzxx
'''读取n个患者的数据，存储到列表data中，每个元素有3个数据项，分别为挂号编号、签到时间、是否回诊，如[[1,"08:50",0],[3,"08:40",0],…]，代码略'''
p_wait=px(data)
print("模拟就诊叫号顺序为（挂号编号）：")
for i in proc(p_wait):
　print(i)
（3）①queinfo[0]和queinfo[1]分别存储就诊队列和回诊队列的队首。waitpaient表示等待人数，jzxx存储就诊序号。当还有患者未被叫号或等待队列中还有病人时，继续进行处理，故填入代码为i0或len(jzxx)①i0　或　len(jzxx)14.[2023.1浙江选考]有2组器件共n个，要用一台检测设备检测。每个送检器件的信息包含送达时间、检测时长和优先级。优先级有m（1编写程序模拟检测过程，先合并2组器件的数据，然后计算所有器件的平均等待时长，其中每个器件等待时长为其开始检测的时间与送达时间的时间差。（时间单位均为秒）
请回答下列问题：
（1）由题意可知，图中器件A、B、C、D的检测顺序为A—C—D—B，A、C、D的等待时长分别为0、1、0，B的等待时长是　　　 。
6
（1）根据表格中的信息，优先级值越小，则优先级越高并先进行检测，可列出时间与事件的关系如表所示，所以可知B的等待时间为6。
时间表 事件
0 A到达，开始检测
1 A检测中；B送达，开始等待
2 A检测中；B等待中；C送达
3 A检测结束；C开始检测；B等待中
4 C检测结束；D到达，开始检测；B等待中
5 D检测中；B等待中
6 D检测中；B等待中
7 D检测结束；B开始检测
（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追加一个元素[0,0,0]
　　lst1.append([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]]
4
A
√
（2）①while循环中只对“到达时间”进行比较，即lst1[i][0]和lst2[j][0]。对两个列表中的数据进行从后往前的比较，第一次比较：满足if条件，此时i=1，j=2，k=4；第二次比较：不满足if条件，此时i=1，j=1，k=3；第三次比较：不满足if条件，此时i=0，j=0，k=2；第四次比较：不满足if条件，此时i=-1，j=-1，k=1。循环结束，故循环体执行了4次。②当while循环的条件由“j>=0”改为“k>=0”时，该循环体内就会缺少对变量j的判断，而k的值大于i且大于j，所以当循环执行时，可能会导致lst2中的下标j变成负数，产生错误的处理结果。所以若要测试这个错误，则需要使循环体内至少执行j+1次else语句，使j的值小于0，则执行程序之后符合该要求的列表为选项A。
（3）实现模拟检测过程并计算平均等待时长的部分Python程序如下，请在画线处填入合适的代码。
def proc(data,m):
　n=len(data)
　queinfo=[]
　for i in range(m):
　　#queinfo追加一个元素[-1,-1]
　　queinfo.append([-1,-1])　
　for i in range(n):
　　#data[i]追加一个元素-1
　　data[i].append(-1)　
　curtime=0
　waitnum=0
　i=0
　　　　①
①total=0
　while i0:
　　if i　　　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][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))
③queinfo[k][0]=data[p][3]
①处在代码的变量定义区，最可能是对某个变量的定义，故首先
对每个变量进行解读。自定义函数的作用是传入按送达时间升序
排列的二维数组data，以及data中包含的优先级种类数m，计算
每个器件的平均等待时间，则根据返回值语句可知，变量total
存储总等待时间，n存储器件总数；queinfo为一个长度为m的二
维数组，结合题干描述，则queinfo存储优先级队列的相关信息；data中每个元素都追加一个数据，curtime表示最开始的时间0，也就是第一个器件开始处理的时间，waitnum存储等待的器件数量，i在data中表示下标，则缺少变量total的初始化语句。total表示的是总等待时间，初始值应为0，故填入代码为total=0。②处在while循环的分支1中，首先判断循环体的作用，条件“i0”表示有器件正在等待，则可知循环体的作用是对每个器件的
①total=0　②p=queinfo[k][1] 　③queinfo[k][0]=data[p][3]
（3）可将代码框架整理如图所示。
状态进行判断，直至data中所有器件都已经被检测。器件的状态有未送达、送达、开始检测、等待中、检测完毕几个状态，程序只对零件的等待时间进行计算，即重点判断器件的送达时间和开始检测的时间；分支1的条件“data[i][0]<=curtime”，说明送达时间小于等于当前时间，也就是当前遍历到的器件data[i]是已经送达的状态。k存储该器件的优先级，该优先级在二维数组queinfo中对应的元素为queinfo[k]，则表示优先级队列k的队列信息，队列信息主要是队首指针和队尾指针，故可以判断queinfo[k][0]存储优先级队列k的队首指针，queinfo[k][1]存储优先级队列k的队尾指针。故根据if判断条件“queinfo[k][0]==-1”可知，判断的是当优先级队列k为空时，则将该器件在data中的位置存储为第一个节点，即入队操作；否则当该优先级队列不为空时，该器件应该从队尾入队，修改队尾节点的指针，该队列的队尾指针为queinfo[k][1]，后续语句是将data[p][3]的值赋值为i，说明data[p][3]是该优先级队列的队尾节点，故可知定义语句中“data[i].append(-1)”是为二维列表data添加了一个指针域，将该数组转为链表，故②处是从queinfo中获取到优先级队列k的尾指针p，故填入代码为
p=queinfo[k][1]。③处在分支2中，分支2的判断语句说明当前时间没有器件送达，或所有器件都已经送达，但是有器件在等待。那么表示当前有器件在检测，需要将当前器件检测完毕并出队，此时找到等级最高的非空优先级队列，在queinfo中查找，第一个非空的que[k][0]即是优先级最高的队列，将该队列中的队首元素出队。p存储该队列的队首指针，total（总等待时长）为当前时间（curtime）减去该器件的送达时间（data[p][0]），当前时间再加上该器件的检测时长（data[p][1]），得到的curtime的值就是下一个器件开始检测的时间；此时该器件处理完毕，从优先级队列k中出队，故queinfo中的队首元素queinfo[k][0]更改为链表节点data[p]的后继指针（data[p][3]），故填入代码为queinfo[k][0]=data[p][3]。
p=queinfo[k][1]。③处在分支2中，分支2的判断语句说明当前时间没有器件送达，或所有器件都已经送达，但是有器件在等待。那么表示当前有器件在检测，需要将当前器件检测完毕并出队，此时找到等级最高的非空优先级队列，在queinfo中查找，第一个非空的que[k][0]即是优先级最高的队列，将该队列中的队首元素出队。p存储该队列的队首指针，total（总等待时长）为当前时间（curtime）减去该器件的送达时间（data[p][0]），当前时间再加上该器件的检测时长（data[p][1]），得到的curtime的值就是下一个器件开始检测的时间；此时该器件处理完毕，从优先级队列k中出队，故queinfo中的队首元素queinfo[k][0]更改为链表节点data[p]的后继指针（data[p][3]），故填入代码为queinfo[k][0]=data[p][3]。

展开更多......

收起↑