资源简介

(共77张PPT)
课时2　队　列
第三章　字符串、队列和栈
1.通过问题解决，理解队列的概念和特性。2.掌握队列的基本操作，并能编程实现。
目 录
CONTENTS
知识梳理
01
例题精析
02
随堂检测
03
巩固与提升
04
知识梳理
1
1.队列的概念
先进先出
(1)队列是一种____________的线性表，允许______的一端称为队尾，允许______的一端称为队首。
(2)队列中的数据元素称为____________。
插入
删除
队列元素
2.队列的特性
(1)___________________________。
(2)_______________。
队头指针指向实际队头元素的位置，而队尾指针指向实际队尾元素所在的后一个位置。
先进先出、后进后出
有限序列性
3.队列的基本操作
(1)队列的存储
①顺序存储
队列的顺序存储指用一段地址连续的内存单元依次存储在队列中的数据元素。
顺序存储的队列称为顺序队列，可用数组来实现。
②队列的链式存储
队列的链式存储指用一组任意(不要求连续)的内存单元存储队列中的数据元素及数据元素间的关系。
链式存储的队列称为链队列，用链表来实现，一个链式队列由一个头指针和一个尾指针共同确定。
(2)队列的操作(建队、入队、出队)的实现
①顺序队列
m＝100　#队列规模
head＝tail＝0
que＝[″″]*m　#建队
data＝input(″please input data：″)
i＝0
while data ！＝″#″：　#入队操作，输入#结束
if tail＝＝m：
print(″队列已满！″)
else：
que[tail]＝data
tail＋＝1
data＝input(″please input data：″)
while headprint(que[head]，end＝″″)
head＋＝1
②循环队列
m＝100　#队列规模
head＝tail＝0
que＝[″″]*m　　　　 #建队
data＝input(″please input data：″)
i＝0
while data ！＝″#″：　#入队操作，输入#结束
if (tail＋1)%m＝＝head：
print(″队列已满！″)
else：
que[tail]＝data
tail＝(tail＋1)%m
data＝input(″please input data：″)
while headprint(que[head]，end＝″″)
head＋＝1
③链队列
class Queue()：
def _ _init _ _(self)：
self.queue＝[]
def queue_in(self，data)：
#data插入队列
self.queue.insert(0，data)
def queue_out(self)：
#取出队首元素
if len(self.queue)：
　　　　return self.queue.pop()
return ″队列已空″
4.与队列有关的Python模块
Python内建有queue模块，在这个模块内可以使用Queue()建立对象，然后可以使用下列方法执行queue的操作。
from queue import Queue
q＝queue()
for i in range(3)：
q.put(i)
while not q.empty()：
print(q.get())
Queue类中定义的方法
方法 功能描述
put() 在队尾插入数据
get() 在队首取出数据
qsize() 返回队列的长度，即队列中的元素个数
empty() 判断队列是否为空，返回值为True或False
full() 判断队列是否为满，返回值为True或False
例题精析
2
例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
解析　本题考查队列的基本操作。数组前面入队，后面出队。TTT操作结果：9，5，8，3，2。Q后队列为：5，8，3，2。再TT之后结果为：3，2，5，8。Q后，队列为：2，5，8。
变式训练　有 1 个队列，队首到队尾的元素依次为 8，10，12，9。若队首元素是偶数则先出队，再将偶数整除 2 后重新入队，若队首元素是奇数，直接出队。入队或出队各算一次操作，经过 6 次操作后，队列中队首到队尾的元素依次为(　　)
A.2，3 B.6，2，3
C.9，4，5 D.9，4，5，6
解析　本题考查队列性质和操作。根据队列的特点“先进先出，后进后出”，8 出队后4入队(2 次), 10 出队后5入队(2 次)，12 出队后6入队(2 次)。共 6 次，其结果为 9，4，5，6。
D
例2 小明在使用队列解决问题的过程中，初始时(空队列)，队列的队首指针head＝0，队尾指针tail＝0，经过一系列入队、出队操作后， head＝4，tail＝7。在不考虑队列溢出的情况下，小明接下来进行的操作序列为出队、入队、出队、出队、入队、出队，此时head和tail的值分别为(　　)
A.7和8 B.7和9 C.8和9 D.9和10
解析　在这个操作过程中，每次出队都是成功的，总共出队4次，入队2次，所以head和tail的值分别变为8和9。
C
变式训练　若用一个规模为20的数组来实现队列，已知当前队尾指针tail的值为8，队头指针head的值为3，进行如下操作：连续删除2个元素、连续插入5个元素、删除1个元素，连续插入2个元素。则操作后指针head和tail的值分别为(　　)
A.5和14 B.6和14 C.6和15 D.7和15
解析　本题考查队列的入队出队操作。删除元素，即进行出队操作，出队时将队首元素删除，然后队首指针加1；插入元素，即进行入队操作，入队时先将元素插入，然后队尾指针加1。共删除3个元素，删除操作结束后，因此队头指针head的值为6，共插好入7个元素，操作后队尾指针tail的值为15。
C
例3 列表q长度为20，q[0]至q[4]的值依次为'p'，'r'，'i'，'n'，'t'，执行如下程序段后，输出的最后一个字符为(　　)
D
head，tail＝0，5
while head　if head % 3＝＝0：
print(q[head])
else：
q[tail]＝q[head]
tail＋＝1
head＋＝1
A.t B.n C.i D.r
解析　本题考查队列的基本操作。队列每次出队一个元素，若head是3的倍数时，输出队首元素，否则将队首元素入队，p出队并输出，r和i出队后入队，队列中元素依次为ntri，head值为3；n出队并输出，t和r出队后入队，队列中元素依次为itr，head值为6；i出队并输出，t和r出队后入队，队列中元素依次为tr，head值为9；t出队，队列中只剩下元素r，r连续两次出队后再入队，当head为12时，r出队。
变式训练　执行如下程序段后，变量length的值为(　　)
C
s＝″engineer″　
q＝[″″]*len(s)
head，tail＝0，0
length＝0
for x in s：
　while x in q[head：tail]：
　 head＋＝1
　q[tail]＝x
　tail＋＝1
　if tail－head>length：
　length＝tail－head
A.2 B.3 C.4 D.5
解析　程序功能实现查找最长不重复的子串，该子串为'engi '。
例4 有如下Python程序段：
import random
q＝[0]*8
head，tail＝0，4
for i in range(4)：
　 k＝random.randint(0，10)
　if k%2＝＝0：
q[tail]＝k%5
tail＋＝1
　else：
head＋＝1
while head　　print(q[head]，end＝″ ″)
　　head＋＝1
程序运行后，输出结果可能为(　　)
A.0 0 0 0 2 3 0 6 B.0 1 2 3 4 C.0 0 0 0 D.2 4
解析　队列中初始化4个元素，值均为0。程序一共循环4次，当产生的随机数k为偶数时，将k%5入队，否则出队一个元素。A选项队列中共有8个元素，因此共入队4个元素，但入队的元素值k%5必须小于5。B选项队列中共有5个元素，说明入队比出队多一次，设入队x次，出队y次，有表达式x＋y＝4和x－y＝1成立，两者相加得到x不为整数。C选项说明入队和出队各2次，两面2个0为后面入队的元素。D选项表达式x＋y＝4和x－y＝－2成立，入队1个元素4，出队2个0，但2不可能存在于原队列中。
C
变式训练　有如下Python程序段：
import random
que＝[0]*10
head＝0；tail＝5 #定义队列的首尾指针
for i in range(5)：
　k＝random.randint(0，10)
　 if k%2＝＝0：
head＋＝1
else：
que[tail]＝i%3
tail＋＝1
while head　print(que[head]，end＝″ ″)
　 head＋＝1
解析　i%3的值依次为0，1，2，0，1，队列的特性是先进先出，前5个零以后面入队的数字之前出队。5次操作后，前三项队列中有4个元素，说明出队比入队多1次。A选项0和2入队。B选项1和2入队。C选项1和2入队，但原始队列中没有1。D选项队列中剩余2个元素，出队加入队次数为5，出队比入队多3次，因此出队4次，入队1次，最后一个0入队。
C
随堂检测
3
1.有一个队列 S，其中指针 head 指向队首元素的位置，指针 tail 指向队尾元素的下一个位置。关于该队列说法正确的是(　　)
D
解析　本题考查队列性质和基本操作。tail是指向队尾元素后面的位置，因此队列长度为tail－head。 当tail值为len(S)，队尾元素存储在len(S)－1，因此队列已满。
A.队列中元素个数为 tail－head＋1
B.新元素入队时，指针 head 向右移动
C.元素出队时，指针 tail 向右移动
D.当 tail＝＝len(S)时，无法再入队新元素
2.有1个队列，队首到队尾的元素依次为1，2，3，4，5。约定：T操作是指队列中1个元素出队后再入队，Q操作是指队列中1个元素出队。则经过TTQTTQTTQ系列操作后，队列中队首到队尾的元素依次为(　　)
A.4，5 B.5，4 C.2，4 D.4，2
C
解析　队列的变化情况为12345→34512→4512→1245→245→524→24。
3.假设队列的空间足够，队首指针head和队尾指针tail经过“出队、入队、出队、出队、入队、入队、出队”这一系列操作后，head＝7，tail＝9。则操作前的head和tail的值分别为(　　)
A.11　12 B.2　5 C.3　6 D.3　5
C
解析　本题考查队列的性质。入队3次，出队4次，在3次入队前tail应为6，在4次出队前head应为3。
4.某队列的数据结构如图所示，head 和 tail 分别是队列的头指针和尾指针。
C
解析　题目中队列的元素执行队首元素出队，再从队尾入队，接下来队首元素出队从队尾入队，直至队列空，输出的顺序为C选项结果。
现对该队列进行下列操作：①队首元素出队后再入队；②队首元素出队并输出，重复①②操作直到队列为空。若队列的数据元素为“Python”，则输出的顺序是(　　)
A.Python B.Ptoynh C.yhntPo D.yhntoP
5.有如下Python程序段：
s＝″abcdddbha″
que＝[″″]*10
head＝tail＝0
for i in range(len(s))：
　if s[i] not in que[head：tail]:
que[tail]＝s[i]
　tail＋＝1
　else：
　head＋＝1
print(que[head：tail])
C
程序运行后，输出的结果是(　　)
A.['a'，'b'，'c'，'d'，'h'] 　B.['a'，'b'，'c'，'d'，'d']
C.['c'，'d'，'b'，'h'，'a'] 　D.['a'，'d'，'d'，'d'，'a']
解析　本题考查队列基本操作。遍历列表s，当元素不在队列中，将该元素入队，否则将队首元素出队(该元素不入队)。遍历第2个第3个d时，ab出队，队列中有[c，d]，接着bha依次入队。
6.有如下 Python 程序段：
s＝″abcxyz″
q＝[1，2，3]＋[0]*10
head，tail＝0，3
res＝″″
for i in s：
　c＝chr((ord(i)－ord(″a″)＋q[head]) % 26＋ord(″a″))
　 res＋＝c
　　q[tail]＝q[head]
　　head＝head＋1
　　tail＝tail＋1
print(res)
A
执行该程序段后，输出的结果是(　　)
A.bdfyac B.bdfxyz C.abcyac D.yacbdf
解析　本题考查队列的相关操作。表达式(ord(i)－ord(″a″)＋q[head]) % 26 的功能是将i转换为在字母表中索引位置，并循环后移q[head]个位置。计算出移动位置后，再转换为小写字母。q中元素实现出队后再入队，因此分别将a、b、c和x、y、z对应位置字母后称1、2、3位置。
7.有如下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]
D
tail＝tail＋1
while head　print(que[head]，end＝″″)
　head＝head＋1
解析　遍历字符串s，当i%2＝＝0条件成立时，将s[i]入队，否则将s[len(s)－i]入队。
执行该程序段后，输出的结果是(　　)
A.ABCDEF B.FEDCBA C.ACEFDB D.AFCDEB
8.有如下程序段：
import random
q＝[0]*6
head＝tail＝0
for i in range(6):
　x＝random.randint(0，1)
　 if x＝＝1：
　 q[tail]＝random.randint(1，10)
　elif head！＝tail and q[tail－1]>q[head]:
　q[tail]＝q[head]
　head＋＝1
　　tail＋＝1
B
运行该程序段后，q 的值可能是(　　)
A.[5，3，8，6，0，1] B.[5，3，0，1，0，2]
C.[2，0，3，0，4，0] D.[0，9，0，10，0，5]
解析　本题考查队列的算法实现。循环6次，当随机数x的值为1时，在队尾生成一个1到10之间的随机数；当x为0时，若队列不为空且队尾大于队首，则将队首出入后再入队尾。因此入队的数据有3种可能性，还有一种可能性是没有新数据入队，tail直接往后移动。A选项若x为1，0不可能产生。若x为0，此时队列不为空，队首值为5，队尾值为6，满足队尾大于队首，5出队后入队。B选项5大于3，5大于1，因此可以不出队。C选项2大于3，因此2要出队后再入队。D选项由于0小于9，0也队后入队，队首为9，由于9小于10，因此最后一个0不可能产生。
4
巩固与提升
基础巩固
能力提升
一、基础巩固
1.下列有关队列的说法正确的是(　　)
B
解析　本题考查队列的性质。A选项队列在队尾插入，在队首删除；C选项队尾指针tail指向队尾元素的下一个位置，所以tail－head表示队列中元素个数；D选项软件连续撤销操作是撤销前一步操作，是栈的应用实例。
A.队列是一种先进先出的线性表，插入一端为队首，删除一端称队尾
B.队列的存储结构，可用数组实现，也可用链表实现
C.一队列队头指针head，队尾指针tail，则tail－1－head表示队列中元素个数
D.学生排队就餐与软件连续撤消操作都是数据结构“队列”的应用实例
2.有1个队列，现有元素依次为1，2，3，4。约定：P操作是指1个入队，T操作是指队列中1个元素出队后再入队，Q操作是指队列中1个元素出队。则经过PPTQTPQ系列操作后，队列中队首到队尾的元素依次为(　　)
A.1 B.1，3 C.3，4 D.3
D
解析　元素1，2入队，1出队后入队，队列为2，1。2出队，1出队后入队，3入队，1出队，因此队列中只有元素3。
3.创建一个容量为 3 的队列，元素 2，3，5，1，3，5，2 依次等待入队。入队规则为：
①若当前待入队元素已经在队列中，则跳过该元素，否则转②
②若当前队列已满，将队首元素出队列，否则转③
③将当前待入队元素入队列
操作完成后，队列中的元素为(　　)
A.2，3，5，1 B.1，2，3，5
C.2，3，5 D.5，1，2
D
解析　本题考查队列性质。2，3，5入队，队满。2出队，1入队，队列为3，5，1；3和5在队列中，跳过该元素。3出队，才能让2入队，队列中元素为5，1，2。
4.某种特殊的队列 Q，支持以下3个操作：操作Q1，若队列非空，队首元素出队，并输出；操作Q2，若队列非空，队首元素出队；操作Q3，一个元素入队；以上任意一种操作后，若队列非空，新的队首元素仍为队列中所有元素的最小值。若队列 Q 初始状态为空，依次进行 Q3、Q2、Q1、Q2、Q3、Q1、Q3 七次操作后，下列说法正确的是(　　)
A.当前队列中的元素个数为 2
B.输出的元素个数为 2
C.第一个输出的元素肯定比当前队首元素大
D.队列初始状态是否为空对输出结果有影响
D
解析　操作Q3、Q2之后，队列为空。Q3、Q1，队列为空。因此队列中元素个数为1，Q1操作出队并输出元素，输出的元素个数为1。C选项没有可比性。D选项若队列不为空，则Q3、Q2、Q1、Q2输出的结果不一样。
5.假设队列空间足够，队列中的元素个数为 5。约定：T 为入队操作，Q 为出队操作，则经过 TTQQTQTQQ一系列操作之后，队首指针 head，队尾指针 tail 的值可能为(　　)
A.head＝11，tail＝7 B.head＝7，tail＝11
C.head＝9，tail＝12 D.head＝12，tail＝9
B
解析　本题考查队列基本操作。经过4次入队，5次出队，因此队列中共有4个元素。由于队列空间足够，因此队尾指针大于队首指针。A选项队尾应大于队首。B选项队列中元素个数为11－7＝4，符合题目要求。C选项队尾应大于队首。D选项队列中元素个数为12－9＝3，不符合题目要求。
6.列表q长度为20，q[0]到q[7]的值依次为'a'，'b'，'c'，'a'，'c'，'d'，'d'，'e'，执行如下程序段后，输出的结果为(　　)
A
head＝tail＝0
for i in range(8)：
if q[i]＝＝q[head] and head！＝tail:
　 tail＋＝1
　 head＝tail
else：
　　tail＋＝1
print(q[head：tail])
A.cdde B.acdde C.eddc D.e
解析　分析程序段可知，该程序段实现的是一种消消乐游戏，即若新遍历到的元素和队首的元素不同或者队列为空，则将新元素入队。若新遍历到的元素和队首的元素相同，则将所有队列中的元素清空。因此队列中最后剩余的元素为 c，d，d，e。
7.有如下程序段：
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
C
　 　　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
解析　本题考查队列的算法实现。vis是一个标志数组，当其元素值为0时，可以入队，保证队列中数据是唯一的。当队列中元素个数大于等于3时，将进行出队操作。ans统计入队次数。输入x的值1，2入队，接着1不能入队，5入队，当输入4时，让1出队，4入队。第2个4不能入队，最后一个1入队。
8.执行如下程序段后，输出的结果是(　　)
B
q＝[6，8，9，7，4，5，2，3]
pre＝10
head，tail＝0，len(q)
while head！＝tail：
　if pre>q[head]:
pre＝q[head]
print(q[head]，end＝' ')
head＋＝1
A.6 8 9 B.6 4 2 C.6 5 3 D.6
解析　本题考查队列的基本操作。程序的功能是查找队列中最小值，pre初值为10，每次出队一个元素，出队元素与pre比较，记录其最小值的过程。
9.有如下Python程序段：
a＝[3，6，10，5，9，4]
q＝[0]*len(a)
k＝int(input(″输入k的值：″))
head＝tail＝0
s＝ans＝0
for i in a：
　 q[tail]＝i
　 tail＝tail＋1
A.18 B.19 C.21 D.22
C
　s＋＝i
　if ansans＝s
　while ik：
s－＝q[head]
head＝head＋1
执行该程序段后，输入k的值为2，变量ans的值是(　　)
解析　遍历数组a并累加数组元素值，求队列的最大值；当遍历到的当前值小于队首或是长度大于k，将队首元素出队。s的值依次为[3，6，10]＝19，[6，10，5]＝21，[5，9]＝14，[5，9，4]＝18。
10.有如下Python程序段：
Q＝[0]*10
cnt，head，tail＝0，0，0
S＝input()
for i in range(0，9，2)：
　 t＝S[i]
　n＝int(S[i＋1])
　if t＝＝'A'：
　 for j in range(n)：
B
　　 Q[tail]＝cnt
　 　　tail＋＝1
　　 　cnt＋＝1
elif t＝＝″D″：
　while head！＝tail and n>0：
　　 head＋＝1
　　 n－＝1
print(Q[head : tail])
若输入S的值为″A2D1A1D3A2″，则程序的输出结果是 (　　)
A.[3，4，5] B.[3，4] C.[4，5] D.[4]
解析　本题考查队列的入队与出队操作。字符串S中两个字符为一组，第1个元素t代表入队或出队，第2个元素代表n入队或出队的次数。A是入队，D是出队，若出队过程中队空，则中止出队。
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
D
　　　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
解析　本题考查队列的程序实现。在for循环中，当s[i]的值为数字字符时，将s[i]放入队列中；当s[i]为’，’时，将队列中的字符出队并连接。当flag为True时，字符出队但不连接到tmp中；其余字符忽略不处理。因此当输入的字符串为“1－500，2023900－，”时，遇到第一个’，’字符，则ans加上100，然后再对于进入队列中的字符串“2023900”进行计算，故最后的结果为22400。
12.某市举办科技嘉年华活动，为了激发学生的参与积极性，举办方推出了玩游戏得积分，积分兑换礼物的活动。活动中游戏分为简单和困难两种，参与游戏就可以获得相应的积分，当完成困难游戏时，除了获得相应积分外，还可获得一张“积分翻倍卡”，一张“积分翻倍卡”可用于一个简单游戏，使简单游戏的积分翻倍。
“积分翻倍卡”使用规则如下：
1)当简单游戏开始时，如果有“积分翻倍卡”可用，则一定会使用。
2)“积分翻倍卡”需在15分钟内使用。比如困难游戏完成时间是9：15分，则获得的“积分翻倍卡”将在9：15分激活，且超过9：30分将失效。
3)如果有多张“积分翻倍卡”，则优先使用最早的“积分翻倍卡”。
某同学的游戏记录如图a所示(类型0表示困难游戏，类型1表示简单游戏)，小明读取游戏记录，编写Python程序计算出该同学游戏的最终得分。程序运行结果如图b 所示，请回答下列问题：
序号 类型 积分 开始时间 完成时间
1 0 10 9：10 9：15
2 1 3 9：15 9：28
3 1 5 9：38 9：42
4 0 12 9：58 10：05
5 1 3 10：20 10：36
6 0 15 10：48 10：55
7 1 3 11：25 11：29
图a
(1)若某同学参加游戏的记录如图c所示，则他获得的积分是________分。
(2)定义如下函数 change(t)，参数t为游戏时间，函数功能是将时间t转换为分钟并返回。如：t＝″9：20″时，转换为整数(分钟)值是560，函数返回值为560。
函数代码如下，请在划线处填入合适的语句。
def change(t): #参数t的时间格式为：″小时：分钟″
m＝t.split(″：″)　　
s＝____________
return s
(3)计算游戏积分的部分Python程序如下，请在划线处填入合适的代码。
从Excel文件中读取游戏过程记录，存储在列表s 中，如s＝[[1，0，10，550，565]，[2，1，3，565，568]，...]，s[i]表示第i个游戏记录，s[i][0]，s[i][1]，s[i][2]，s[i][3]，s[i][4]依次存储游戏的序号、类型、积分、开始时间，完成时间；当游戏类型s[i][1]值为日时表示困难游戏，为1则表示简单游戏；
将困难游戏取出存入列表a中，列表 a按游戏完成时间升序排序；
将简单游戏取出存入列表b中，列表b按游戏开始时间升序排序，代码略
que＝[－1]*(len(a)＋len(b)＋1)
head＝tail＝0
total＝0
for i in range(len(a)): #累加游戏积分，将“积分翻倍卡”激活时间加入队列
total＋＝a[i][2]
①____________
tail＋＝1
for i in range(len(b)) ：
　 while head　 print(que[head]∥60，″： ″，que[head] % 60，″时刻生效的″＋″积分翻倍卡过期；″)
　 head＋＝1
　　if head　 print(b[i][3]∥60，″：″，b[i][3]%60，″时刻使用了积分翻倍卡；″)
　③____________
　head＋＝1
　　else：
　total＋＝b[i][2]
print(″总共获得积分为： ″，total，″分，″，″剩余积分卡有： ″，tail－head，″张。″)
答案　(1)40　(2)int(m[0])*60＋int(m[1])
(3)①que[tail]＝a[i][4]
②que[head]＋15③total＋＝b[i][2]*2或total＝total＋b[i][2]*2
解析　本题考查队列的基本操作。(1)完成困难游戏获得积分翻倍卡，一张积分翻倍卡使简单游戏的积分翻倍，但积分卡在15分钟内有效，14：47激活卡，15：10已经过期。积分为10＋5*2＋15＋5。(2)将时间按冒号分隔，得到一个列表，列表中有两个值，分别为m[0]和m[1]。(3)①将积分卡激活时间加入队列，困难游戏完成时间就是卡激活时间。②遍历列表b，简单游戏一开始就可以使用翻倍卡，因此计算翻倍卡的激活时间与当前简单游戏开始时间的时间差，该时间差大于15分钟时，卡失效。③使用翻倍卡，积分将翻倍。
13.某文本编辑软件可以把所做的文本编辑操作记录下来，并通过撤销和恢复命令来撤销一步操作或恢复一步撤销的操作，也可以通过数字命令一次性撤销最近的多步文本编辑操作，如图所示。
设计算法模拟该功能。约定：①操作记录只存储文本编辑指令；②存储步数最多为 5步，存满后早期的操作记录将被覆盖；③程序只显示操作记录的可“撤销”记录，可 “恢复”记录不显示；④一旦有新的文本编辑操作，则清空所有可“恢复”记录。
人机交互的指令如下(所有操作示例都基于上一个示例结果继续操作)：
类型 指令 示例 程序输出结果
文本 编辑 “T1”、“T2”、“T3”、“T4”表示四种文本编辑操作 对文本依次做“ T1 ” 、 “T2”、“T3”、“T4” 操作后，再输入指令“T2” 请输入操作指令：T2
指令B可用：指令F不可用
可撤销记录：T1/T2/T3/T4/T2/
撤销 “B”表示撤销 1 步操作 输入“B” 结果：撤销最近一步操作 “T2” 请输入操作指令：B
指令B可用：指令F可用
可撤销记录：T1/T2/T3/T4/
数字“1”～“5”表示撤销多步操作 输入“3” 结果：撤销最近 3 步操作 “T4”、“T3”和“T2” 请输入操作指令：3
指令B可用：指令F可用
可撤销记录：T1/
恢复 “F”表示恢复 1 步撤销的文本编辑操作 输入“F” 结果：恢复最近的 1 步文本编辑操作“T2” 请输入操作指令：F
指令B可用；指令F可用
可撤销记录：T1/T2/
文本 编辑 在撤销或恢复操作之后继续新的文本编辑操作 输入“T1” 结果： 可“ 恢复” 记录 “T3”、“T4”、“T2” 被清空 请输入操作指令：T1
指令B可用；指令F不可用
可撤销记录：T1/T2/T1/
所有指令均可使用多次。每次输入一个指令后都输出“F”指令和“B”指令是否可用以及当前可撤销记录。所有无效操作指令输入后均提示“Input Error！”。输入“#”则结束程序。请回答下列问题：
(1)由题意可知，当依次执行指令“T2”、“T2”、“T1”、“T3”、“T1”、“T4”，则最终可撤销记录共有__________个。
(2)模拟实现该功能的 Python 代码如下，请在划线处填入合适的代码。
def printh(head，cur)：
　print(f[flag[0]*2＋flag[1]])
　 s＝″可撤销记录：″
　 while head！＝cur＋1:
　s＝s＋hist[head]＋″/″
　①____________
　print(s)
opera＝[″T1″，″T2″，″T3″，″T4″]
f＝{0：″指令 B 不可用；指令 F 不可用″，1：″指令 B 不可用；指令 F 可用″，2：″指令 B 可用；指令 F 不可用″，3：″指令 B 可用；指令 F 可用″}
maxn＝5 #历史记录最多存储的步数
maxsize＝100 #设定最多输入文本编辑指令 100 次
hist＝[″″]*maxsize
cur＝－1；tail＝0；head＝0
flag＝[0，0] #记录指令 B 与指令 F 的状态
while True：
　d＝input(″请输入操作指令：″)
　if d＝＝″#″： break
　if d in opera：
　if ②____________：
　　　head＝head＋1
　cur＝cur＋1；hist[cur]＝d
　tail＝cur＋1
　flag＝[1，0]
　printh(head，cur)
　　elif ″1″<＝d<＝str((cur－head＋1)):
　 cur＝③____________
　if cur＝＝head－1:
　　　flag[0]＝0
　flag[1]＝1
printh(head，cur)
　　elif d＝＝″F ″and tail！＝cur＋1:
　#恢复功能代码略
(3)若加框处代码误写为“d＝＝″B″”，会导致某些情况下无法得到符合判断功能的结果。下列 4 组数据中能测试出这一问题的是__________(多选，填字母)
选项 依次输入下列操作指令
A “B”
B “T1”、“B”、“B”
C “T1”、“1”、“B”
D “T1”、“T2”、“B”
答案　(1)5　(2)① head＋＝1　②cur－head＋1＝＝maxn或tail＝＝cur＋l and tail－head＝＝maxn　③cur－int(d)　(3)ABC
解析　本题考查队列的基本操作。(1)存储步数最多为 5步，存满后早期的操作记录将被覆盖。(2)①head表示队首，cur表示最后一个元素指针，每输出一个元素，就要出队。②当d是文本编辑指令时，存储步数最多为 5步，超出队首元素将不能撤消。cur初值为－1，一个元素入队后，值为0，因此cur表示列队中最后一个元素，因此队列总共元素个数为cur＋1－head。③当d为撤消步数时，cur表示撤消后的元素位置，因此cur将减去int(d)的值。(3)A选项cur小于head无法输出。B选项撤消一步后，效果同A。C选项1表示撤消一步，效果同B。D选项有两个元素，可以输出。课时2　队　列
课时目标
1.通过问题解决，理解队列的概念和特性。2.掌握队列的基本操作，并能编程实现。
1.队列的概念
(1)队列是一种____________的线性表，允许________的一端称为队尾，允许________的一端称为队首。
(2)队列中的数据元素称为____________。
2.队列的特性
(1)________________。
(2)______________。
队头指针指向实际队头元素的位置，而队尾指针指向实际队尾元素所在的后一个位置。
3.队列的基本操作
(1)队列的存储
①顺序存储
队列的顺序存储指用一段地址连续的内存单元依次存储在队列中的数据元素。
顺序存储的队列称为顺序队列，可用数组来实现。
②队列的链式存储
队列的链式存储指用一组任意(不要求连续)的内存单元存储队列中的数据元素及数据元素间的关系。
链式存储的队列称为链队列，用链表来实现，一个链式队列由一个头指针和一个尾指针共同确定。
(2)队列的操作(建队、入队、出队)的实现
①顺序队列
m＝100　#队列规模
head＝tail＝0
que＝[″″]*m　#建队
data＝input(″please input data：″)
i＝0
while data ！＝″#″：　#入队操作，输入#结束
if tail＝＝m：
print(″队列已满！″)
else：
que[tail]＝data
tail＋＝1
data＝input(″please input data：″)
while headprint(que[head]，end＝″″)
head＋＝1
②循环队列
m＝100　#队列规模
head＝tail＝0
que＝[″″]*m　　　　 #建队
data＝input(″please input data：″)
i＝0
while data ！＝″#″：　#入队操作，输入#结束
if (tail＋1)%m＝＝head：
print(″队列已满！″)
else：
que[tail]＝data
tail＝(tail＋1)%m
data＝input(″please input data：″)
while headprint(que[head]，end＝″″)
head＋＝1
③链队列
class Queue()：
def _ _init _ _(self)：
self.queue＝[]
def queue_in(self，data)：
#data插入队列
self.queue.insert(0，data)
def queue_out(self)：
#取出队首元素
if len(self.queue)：
　　　　return self.queue.pop()
return ″队列已空″
4.与队列有关的Python模块
Python内建有queue模块，在这个模块内可以使用Queue()建立对象，然后可以使用下列方法执行queue的操作。
from queue import Queue
q＝queue()
for i in range(3)：
q.put(i)
while not q.empty()：
print(q.get())
Queue类中定义的方法
方法 功能描述
put() 在队尾插入数据
get() 在队首取出数据
qsize() 返回队列的长度，即队列中的元素个数
empty() 判断队列是否为空，返回值为True或False
full() 判断队列是否为满，返回值为True或False
例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
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　有 1 个队列，队首到队尾的元素依次为 8，10，12，9。若队首元素是偶数则先出队，再将偶数整除 2 后重新入队，若队首元素是奇数，直接出队。入队或出队各算一次操作，经过 6 次操作后，队列中队首到队尾的元素依次为(　　)
A.2，3 B.6，2，3 C.9，4，5 D.9，4，5，6
例2 小明在使用队列解决问题的过程中，初始时(空队列)，队列的队首指针head＝0，队尾指针tail＝0，经过一系列入队、出队操作后， head＝4，tail＝7。在不考虑队列溢出的情况下，小明接下来进行的操作序列为出队、入队、出队、出队、入队、出队，此时head和tail的值分别为(　　)
A.7和8 B.7和9 C.8和9 D.9和10
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　若用一个规模为20的数组来实现队列，已知当前队尾指针tail的值为8，队头指针head的值为3，进行如下操作：连续删除2个元素、连续插入5个元素、删除1个元素，连续插入2个元素。则操作后指针head和tail的值分别为(　　)
A.5和14 B.6和14 C.6和15 D.7和15
例3 列表q长度为20，q[0]至q[4]的值依次为'p'，'r'，'i'，'n'，'t'，执行如下程序段后，输出的最后一个字符为(　　)
head，tail＝0，5
while head　if head % 3＝＝0：
print(q[head])
else：
q[tail]＝q[head]
tail＋＝1
head＋＝1
A.t B.n C.i D.r
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　执行如下程序段后，变量length的值为(　　)
s＝″engineer″　
q＝[″″]*len(s)
head，tail＝0，0
length＝0
for x in s：
　while x in q[head：tail]：
　 head＋＝1
　q[tail]＝x
　tail＋＝1
　if tail－head>length：
　length＝tail－head
A.2 B.3 C.4 D.5
例4 有如下Python程序段：
import random
q＝[0]*8
head，tail＝0，4
for i in range(4)：
　 k＝random.randint(0，10)
　if k%2＝＝0：
q[tail]＝k%5
tail＋＝1
　else：
head＋＝1
while head　　print(q[head]，end＝″ ″)
　　head＋＝1
程序运行后，输出结果可能为(　　)
A.0 0 0 0 2 3 0 6 B.0 1 2 3 4
C.0 0 0 0 D.2 4
听课笔记：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
变式训练　有如下Python程序段：
import random
que＝[0]*10
head＝0；tail＝5 #定义队列的首尾指针
for i in range(5)：
　k＝random.randint(0，10)
　 if k%2＝＝0：
head＋＝1
else：
que[tail]＝i%3
tail＋＝1
while head　print(que[head]，end＝″ ″)
　 head＋＝1
运行如下程序段后，输出结果不可能是(　　)
A.0 0 0 2 B.0 0 1 2 C.0 1 0 2 D.0 0
1.有一个队列 S，其中指针 head 指向队首元素的位置，指针 tail 指向队尾元素的下一个位置。关于该队列说法正确的是(　　)
A.队列中元素个数为 tail－head＋1
B.新元素入队时，指针 head 向右移动
C.元素出队时，指针 tail 向右移动
D.当 tail＝＝len(S)时，无法再入队新元素
2.有1个队列，队首到队尾的元素依次为1，2，3，4，5。约定：T操作是指队列中1个元素出队后再入队，Q操作是指队列中1个元素出队。则经过TTQTTQTTQ系列操作后，队列中队首到队尾的元素依次为(　　)
A.4，5 B.5，4 C.2，4 D.4，2
3.假设队列的空间足够，队首指针head和队尾指针tail经过“出队、入队、出队、出队、入队、入队、出队”这一系列操作后，head＝7，tail＝9。则操作前的head和tail的值分别为(　　)
A.11　12 B.2　5 C.3　6 D.3　5
4.某队列的数据结构如图所示，head 和 tail 分别是队列的头指针和尾指针。
现对该队列进行下列操作：①队首元素出队后再入队；②队首元素出队并输出，重复①②操作直到队列为空。若队列的数据元素为“Python”，则输出的顺序是(　　)
A.Python B.Ptoynh C.yhntPo D.yhntoP
5.有如下Python程序段：
s＝″abcdddbha″
que＝[″″]*10
head＝tail＝0
for i in range(len(s))：
　if s[i] not in que[head：tail]:
que[tail]＝s[i]
　tail＋＝1
　else：
　head＋＝1
print(que[head：tail])
程序运行后，输出的结果是(　　)
A.['a'，'b'，'c'，'d'，'h'] 　 B.['a'，'b'，'c'，'d'，'d']
C.['c'，'d'，'b'，'h'，'a'] 　 D.['a'，'d'，'d'，'d'，'a']
6.有如下 Python 程序段：
s＝″abcxyz″
q＝[1，2，3]＋[0]*10
head，tail＝0，3
res＝″″
for i in s：
　c＝chr((ord(i)－ord(″a″)＋q[head]) % 26＋ord(″a″))
　 res＋＝c
　　q[tail]＝q[head]
　　head＝head＋1
　　tail＝tail＋1
print(res)
执行该程序段后，输出的结果是(　　)
A.bdfyac B.bdfxyz C.abcyac D.yacbdf
7.有如下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
while head　print(que[head]，end＝″″)
　head＝head＋1
执行该程序段后，输出的结果是(　　)
A.ABCDEF B.FEDCBA C.ACEFDB D.AFCDEB
8.有如下程序段：
import random
q＝[0]*6
head＝tail＝0
for i in range(6):
　x＝random.randint(0，1)
　 if x＝＝1：
　 q[tail]＝random.randint(1，10)
　elif head！＝tail and q[tail－1]>q[head]:
　q[tail]＝q[head]
　head＋＝1
　　tail＋＝1
运行该程序段后，q 的值可能是(　　)
A.[5，3，8，6，0，1] B.[5，3，0，1，0，2]
C.[2，0，3，0，4，0] D.[0，9，0，10，0，5]
课时2　队　列
知识梳理
1.(1)先进先出　插入　删除　(2)队列元素
2.(1)先进先出、后进后出　(2)有限序列性
例题精析
例1　B　[本题考查队列的基本操作。数组前面入队，后面出队。TTT操作结果：9，5，8，3，2。Q后队列为：5，8，3，2。再TT之后结果为：3，2，5，8。Q后，队列为：2，5，8。]
变式训练　D　[本题考查队列性质和操作。根据队列的特点“先进先出，后进后出”，8 出队后4入队(2 次), 10 出队后5入队(2 次)，12 出队后6入队(2 次)。共 6 次，其结果为 9，4，5，6。]
例2　C　[在这个操作过程中，每次出队都是成功的，总共出队4次，入队2次，所以head和tail的值分别变为8和9。]
变式训练　C　[本题考查队列的入队出队操作。删除元素，即进行出队操作，出队时将队首元素删除，然后队首指针加1；插入元素，即进行入队操作，入队时先将元素插入，然后队尾指针加1。共删除3个元素，删除操作结束后，因此队头指针head的值为6，共插好入7个元素，操作后队尾指针tail的值为15。]
例3　D　[本题考查队列的基本操作。队列每次出队一个元素，若head是3的倍数时，输出队首元素，否则将队首元素入队，p出队并输出，r和i出队后入队，队列中元素依次为ntri，head值为3；n出队并输出，t和r出队后入队，队列中元素依次为itr，head值为6；i出队并输出，t和r出队后入队，队列中元素依次为tr，head值为9；t出队，队列中只剩下元素r，r连续两次出队后再入队，当head为12时，r出队。]
变式训练　C　[程序功能实现查找最长不重复的子串，该子串为'engi '。]
例4　C　[队列中初始化4个元素，值均为0。程序一共循环4次，当产生的随机数k为偶数时，将k%5入队，否则出队一个元素。A选项队列中共有8个元素，因此共入队4个元素，但入队的元素值k%5必须小于5。B选项队列中共有5个元素，说明入队比出队多一次，设入队x次，出队y次，有表达式x＋y＝4和x－y＝1成立，两者相加得到x不为整数。C选项说明入队和出队各2次，两面2个0为后面入队的元素。D选项表达式x＋y＝4和x－y＝－2成立，入队1个元素4，出队2个0，但2不可能存在于原队列中。]
变式训练　C　[i%3的值依次为0，1，2，0，1，队列的特性是先进先出，前5个零以后面入队的数字之前出队。5次操作后，前三项队列中有4个元素，说明出队比入队多1次。A选项0和2入队。B选项1和2入队。C选项1和2入队，但原始队列中没有1。D选项队列中剩余2个元素，出队加入队次数为5，出队比入队多3次，因此出队4次，入队1次，最后一个0入队。]
随堂检测
1.D　[本题考查队列性质和基本操作。tail是指向队尾元素后面的位置，因此队列长度为tail－head。 当tail值为len(S)，队尾元素存储在len(S)－1，因此队列已满。]
2.C　[队列的变化情况为12345→34512→4512→1245→245→524→24。]
3.C　[本题考查队列的性质。入队3次，出队4次，在3次入队前tail应为6，在4次出队前head应为3。]
4.C　[题目中队列的元素执行队首元素出队，再从队尾入队，接下来队首元素出队从队尾入队，直至队列空，输出的顺序为C选项结果。]
5.C　[本题考查队列基本操作。遍历列表s，当元素不在队列中，将该元素入队，否则将队首元素出队(该元素不入队)。遍历第2个第3个d时，ab出队，队列中有[c，d]，接着bha依次入队。]
6.A　[本题考查队列的相关操作。表达式(ord(i)－ord(″a″)＋q[head]) % 26 的功能是将i转换为在字母表中索引位置，并循环后移q[head]个位置。计算出移动位置后，再转换为小写字母。q中元素实现出队后再入队，因此分别将a、b、c和x、y、z对应位置字母后称1、2、3位置。]
7.D　[遍历字符串s，当i%2＝＝0条件成立时，将s[i]入队，否则将s[len(s)－i]入队。]
8.B　[本题考查队列的算法实现。循环6次，当随机数x的值为1时，在队尾生成一个1到10之间的随机数；当x为0时，若队列不为空且队尾大于队首，则将队首出入后再入队尾。因此入队的数据有3种可能性，还有一种可能性是没有新数据入队，tail直接往后移动。A选项若x为1，0不可能产生。若x为0，此时队列不为空，队首值为5，队尾值为6，满足队尾大于队首，5出队后入队。B选项5大于3，5大于1，因此可以不出队。C选项2大于3，因此2要出队后再入队。D选项由于0小于9，0也队后入队，队首为9，由于9小于10，因此最后一个0不可能产生。]

展开更多......

收起↑