资源简介

4.2　队　列
学习目标　
1.通过生活实例,理解队列的性质和作用。
2.在理解队首和队尾指针的功能上,掌握队列和循环队列元素个数的计算方法。
3.在理解队首和队尾指针的功能上,掌握建队、入队和出队的操作过程。
(2023年6月浙江省选考)列表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
　　队列是一种先进先出的线性表,允许插入的一端称为队尾,允许删除的一端称为队首。先进先出是队列的特性,若元素出队后将入队,那么入队后的元素还是维持原来的顺序。建队时,指针head和tail均指向0,head加1表示出队,tail加1表示入队。判断队列是否空的条件是head!=tail,判断队列中元素的数量为tail-head。
例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 利用队列实现字符串换位加密,列表k中各元素依次为加密过程中的操作,p表示出队,q表示出队后入队。若队列中元素从队首至队尾依次为“t”“r”“a”“i”“n”,k为[q,p,q,q,p,p,q,p,p],则加密后的出队结果为(　　)
A.“tanri” B.“niart”
C.“ritan” D.“rntia”
例2 有如下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
变式2 有如下Python程序:
a=[4,2,5,1,9]
que=[0]*(2*len(a))
head,tail=0,0
for i in range(0,len(a)):
　　if head==tail or a[i]　　　　que[tail]=a[i]
　　　　tail+=1
　　elif a[i]>que[tail-1]:
　　　　que[tail]=a[i]
　　　　tail+=1;head+=1
print(que[head:tail])
执行以上程序段后,输出结果是(　　)
A.4,7 B.5,1,9
C.2,5,1,9 D.4,7,2,5,1,9
1.有一个队列S,其中指针head指向队首元素的位置,指针tail指向队尾元素的下一个位置。关于该队列说法正确的是(　　)
A.队列中元素个数为tail-head+1
B.新元素入队时,指针head向右移动
C.元素出队时,指针tail向右移动
D.当tail==len(S)时,无法再入队新元素
2.某队列的数据结构如图所示,head和tail分别为队列的头、尾指针。现对该队列进行以下操作:①队首元素出队输出②队首元素出队再入队,重复①②操作直到队列为空。
若队列数据元素为“CHINA”,则输出顺序是(　　)
A.CIANH B.CIAHN
C.CAHNI D.CHINA
3.给一个队列如下约定:T操作是指队列中1个元素出队后再入队,P操作是指1个元素入队。原始队列经过TTPTP系列操作后,队列中队首到队尾的元素依次为ABCDE,则原始队列中队首到队尾的元素依次为(　　)
A.ABC B.ABD
C.BAE D.BADEC
4.有1个队列,队首到队尾的元素依次为8,10,12,9。若队首元素是偶数则先出队,再将偶数整除2后重新入队,若队首元素是奇数,直接出队。入队或出队各算一次操作,经过6次操作后,队列中队首到队尾的元素依次为(　　)
A.2,3 B.6,2,3
C.9,4,5 D.9,4,5,6
5.有2个队列a和b,队首到队尾的元素依次分别为“5,7,9”和“6,4,8”。约定:T操作是指队列a中1个元素先出队,若大于队列b的队首元素则再入b队列,否则不入;Q操作是指队列b中1个元素先出队,若大于队列b的队尾元素则再入b队列,否则不入。则经过TTQQQQT系列操作后,队列b中的元素个数为(　　)
A.1 B.2
C.3 D.4
6.元素1,2,3,4依次按先后顺序准备入队。约定:P操作是指1个入队,T操作是指队列中1个元素出队后再入队,Q操作是指队列中1个元素出队。则经过PPTQTPQ系列操作后,队列中队首到队尾的元素依次为(　　)
A.1 B.1,3
C.3,4 D.3
7.队列Q从队首到队尾的元素依次为5、2、7、3、6,栈S初始为空。约定:若栈为空或者队首元素小于栈顶元素,那么队首元素出队并入栈;否则,将栈内所有小于队首元素的元素依次出栈并入队,然后将队首元素出队并入栈。反复执行上述操作,直到队列为空。最终,栈S中从栈顶到栈底的元素依次为(　　)
A.2、3、5、6、7 B.7、6、5、3、2
C.7、6、5、2、3 D.5、2、7、3、6
8.队列Q中的元素依次为1,2,3,4,栈S为空。约定:P操作是队首元素出队后入栈,B操作是队首元素出队后入队,T操作是指栈顶元素出栈后入队。执行操作PPBT后,队列Q中的元素依次为(　　)
A.4,3,2 B.4,2,3
C.4,3,1 D.4,2,1
9.执行如下程序段后,变量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
10.某Python程序如下:
q=[""]*50;head=tail=0
s="ningbo"
for i in s:
　　q[tail]=i;tail+=1
while head　　print(q[head],end="")
　　head+=1
　　for i in range(3):
　　　　q[tail]=q[head]
　　　　head+=1;tail+=1
执行该程序段后,输出结果为(　　)
A.nbgoni B.nbogni
C.goninb D.ningbo
11.某Python程序段如下:
s="h#Ap#py"
que=[""]*10;res=""
head,tail=0,0
for i in range(len(s)):
　　if 'a'<=s[i]<='z':
　　　　que[tail]=s[i]
　　　　tail+=1
　　elif head　　　　head+=1
print(que[head:tail])
执行该程序段,输出的结果是(　　)
A.['h','p','p','y']
B.['p','p','y']
C.['p','y']
D.['y']
12.有如下程序段:
head=0;tail=5
que=['a','b','c','d','e']
while head+1　　if head%4!=0:
　　　　que.append(que[head])
　　　　tail+=1
　　head+=1
print(que[head])
执行如下程序段后,最后输出的内容为(　　)
A.a B.b
C.c D.d
13.有如下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']
14.列表q长度为20,q[0]到q[7]的值依次为'a','b','c','a','c','d','d','e',执行如下程序段后,输出的结果为(　　)
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
15.有如Python程序段:
a=[3,1,-6,0,-1,5,2,-5,1,3]
n=len(a);q=[0]*n
head,tail=0,0
for i in range(0,n):
　　if head　　　　if q[head]+a[i]>0:
　　　　　　q[tail]=q[tail-1]+a[i]
　　　　　　tail+=1
　　　　else:
　　　　　　head=tail
　　else:
　　　　if a[i]>0:
　　　　　　q[tail]=a[i]
　　　　　　tail+=1
print(tail-head)
执行以上程序段后,输出的结果为(　　)
A.2 B.3
C.5 D.6
16.有如下Python程序段:
import random
que=["a","b","c","d","","","","","",""]
head=0;tail=4;ans=""
for i in range(5):
　　if random.randint(0,1)==0:
　　　　ans+=que[head]
　　　　que[tail]=que[head]
　　　　head+=1
　　　　tail+=1
　　else:
　　　　head+=1
执行该程序段后,ans的值不可能是(　　)
A."bcc" B."aa"
C."bcdb" D."abcd"
17.有如下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.某队列中的元素依次为"R","o","u","t","e","r",将反复对队内元素做如下操作,直到队列元素为空:①队首元素出队并在队尾入队;②队首元素出队并输出。则输出顺序为(　　)
A.Rueort B.Reorut
C.otruRe D.otrueR
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.约定:T操作是指在队列中1个元素出队后再入队,E操作是指将1个元素入队,P操作是指队列中1个元素出队,队首指针head和队尾指针tail初始值均为0。则经过EETPETEP系列操作后,队首指针head和队尾指针tail的值分别为(　　)
A.3　4 B.3　5
C.4　5 D.4　6
4.有1个队列,队首到队尾的元素依次为1,2,3,4,5,6,7。现进行如下操作:①出队2个元素;②再出队1个元素并将该元素入队。重复以上操作,直至队列中仅剩1个元素。则该元素是(　　)
A.3 B.5
C.6 D.7
5.队列S有若干元素。约定:U操作是指出队,H操作是指元素出队后再入队。经过UHUHHU操作后,队列中队首到队尾的元素依次为4,1,3,则队列S初始状态中队首到队尾的元素可能为(　　)
A.1,1,4,4,3,3 B.4,4,1,1,3,3
C.1,4,3,1,4,3 D.3,1,4,3,1,4
6.有“甲乙丙丁戊”5位游客已按序排队,定义下列操作:顺利买票进入景区,记为Q1;缺少证件需要重新排队,记为Q2;新游客进来排队,记为Q3。若游客“丁”买票时,发现游客“乙”在“丁”的后两位(乙和丁之间还有一位游客),则已进行的操作过程可能是(　　)
A.Q3,Q1,Q2,Q1 B.Q1,Q2,Q2,Q3
C.Q1,Q2,Q3,Q3 D.Q2,Q2,Q1,Q3
7.现有一队列"ECBAD"可以进行如下两种操作:①队首出队后入队②队首出队进入结果区。要求结果区为"ABCDE",则元素"D"被执行①操作的次数至少为(　　)
A.1 B.2
C.3 D.4
8.有两个队列Q1与Q2,初始都为空,经过一系列入队、出队操作(数据全部入队后,才能进行出队操作),若元素入队的顺序是a,b,c,d,e,则不可能的出队序列是(　　)
A.acbde B.ebcda
C.abcde D.daebc
9.数据S1至S4的优先级依次为3,4,1,2,某设备按优先级1至4依次发送数据,利用队列S组织数据并模拟发送过程,初始队首至队尾数据依次为:S1、S4、S3、S2。可利用操作M(出队后再入队)调整数据发送顺序,为将数据发送完毕,则M的执行次数至少为(　　)
A.4 B.5
C.6 D.7
10.有如下Python程序:
a=[13,12,12,15,26,23,36]
que=[0]*len(a)
head=tail=0
for x in a:
　　while head　　　　if x　　　　　　tail-=1
　　　　else:
　　　　　　break
　　que[tail]=x
　　tail+=1
print(que[head:tail])
执行后,程序输出结果为(　　)
A.12 15 26 36 B.12 15 23 26
C.12 12 15 23 36 D.12 13 15 23 36
11.某Python程序段如下:
s="21027,53523,042,";ans=""
q=[0]*100;head=tail=0
for i in range(len(s)):
　　if "0"<=s[i]<="9":
　　　　q[tail]=s[i];tail+=1
　　elif s[i]==",":
　　　　flag=True
　　　　while head　　　　　　ans+=q[head];head+=1
　　　　　　if head!=tail and flag:
　　　　　　　　head+=1
　　　　　　flag=not flag
执行该程序段后,变量ans的值为(　　)
A."20735204" B."20255202"
C."20755302" D."20235304"
12.有如下Python程序段:
s="ABCDEF";que=[""]*10
head=0;tail=0
for i in range(len(s)):
　　if i % 2==0:
　　　　que[tail]=s[len(s)-1-i]
　　else:
　　　　que[tail]=s[i-1]
　　tail=tail+1
while head　　print(que[head],end="")
　　head+=1
该程序运行后输出的结果为(　　)
A.FAEBDC B.FADCBE
C.FBDDBF D.FDBACE
13.有如下Python程序段:
s=input()
d=[-1]*10;head=tail=0
for i in range(len(s)):
　　if d[int(s[i])]　　　　if tail-head==3:
　　　　　　head+=1
　　　　d[int(s[i])]=tail
　　　　tail+=1
若执行程序后,d的值为[-1,4,6,5,3,-1,-1,-1,-1,-1],则输入的s值可能是(　　)
A."6954132" B."11114132"
C."1324132" D."41341322"
14.有如下程序段:
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
15.有如下Python程序段:
from random import randint
n=5;q=[0]*n
head=tail=randint(0,n-1)
while head!=tail+1:
　　num=randint(1,n)
　　if q[head]!=num:
　　　　q[tail]=num
　　　　tail+=1
　　　　if tail==n:tail=0
　　else:
　　　　q[head]=0;head+=1
　　　　if head==n:head=0
执行该程序段后,列表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]
16.有如下Python程序段:
from random import randint
q=[1,2,14,5,6,7,9,10]
head=0;tail=len(q)-1;ans=0
m=randint(1,3)
q+=[0]*m
for i in range(m):
　　for j in range(2**i-1):
　　　　head+=1
　　ans+=q[head]
　　q[tail]=q[head]
　　head+=1;tail+=1
执行该程序段后,变量ans的值不可能是(　　)
A.1 B.15
C.24 D.34
17.执行下列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+=1
print(que[head: tail])
A.[3,2,1] B.[1,2,3]
C.[1,3,1] D.[3,2,3]
18.有如下Python程序段:
que=["A","B","C","D","E"]+[""]*10
n=5;head=0;tail=5
for i in range(n):
　　print(que[head],end="")
　　head+=1
　　for j in range(i):
　　　　que[tail]=que[head]
　　　　tail+=1
　　　　head+=1
执行该程序段后,显示的结果是(　　)
A.ACBED B.ABDCE
C.ABDEC D.ACBDE
19.执行如下程序段后,输出的结果是(　　)
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
20.有如下Python程序段:
import random
q=[0]*5
head=tail=0
for i in range(5):
　　if random.randint(0,1)==0:
　　　　q[tail]=random.randint(1,9)
　　　　tail+=1
　　elif head!=tail and q[tail-1]　　　　q[tail]=q[head]
　　　　head+=1
　　　　tail+=1
执行该程序段后,q的值不可能是(　　)
A.[0,0,0,0,0] B.[5,4,3,2,1]
C.[5,8,3,0,0] D.[0,5,6,0,0]
21.有如下Python程序段:
q=[i for i in range(7)]
head,tail=1,0;cnt=0
while (head+1)%7!=tail:
　　cnt+=1
　　if cnt==3:
　　　　cnt=0
　　else:
　　　　q[tail]=q[head]
　　　　tail=(tail+1)%7
　　head=(head+1)%7
print(q[head])
运行该程序段后,输出结果是(　　)
A.5 B.4
C.2 D.14.2　队　列
学习目标　
1.通过生活实例,理解队列的性质和作用。
2.在理解队首和队尾指针的功能上,掌握队列和循环队列元素个数的计算方法。
3.在理解队首和队尾指针的功能上,掌握建队、入队和出队的操作过程。
(2023年6月浙江省选考)列表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
答案　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出队。
　　队列是一种先进先出的线性表,允许插入的一端称为队尾,允许删除的一端称为队首。先进先出是队列的特性,若元素出队后将入队,那么入队后的元素还是维持原来的顺序。建队时,指针head和tail均指向0,head加1表示出队,tail加1表示入队。判断队列是否空的条件是head!=tail,判断队列中元素的数量为tail-head。
例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
思维点拨
明考向 本题考查队列的基本操作
精点拨 数组前面入队,后面出队。TTT操作结果:9,5,8,3,2。Q后队列为:5,8,3,2。再TT之后结果为:3,2,5,8。Q后,队列为:2,5,8
答案　B
变式1 利用队列实现字符串换位加密,列表k中各元素依次为加密过程中的操作,p表示出队,q表示出队后入队。若队列中元素从队首至队尾依次为“t”“r”“a”“i”“n”,k为[q,p,q,q,p,p,q,p,p],则加密后的出队结果为(　　)
A.“tanri” B.“niart”
C.“ritan” D.“rntia”
答案　D
解析　本题考查队列的基本操作。第1个出队元素为r,2次q操作后,q队列中为n,t,a,i,接着n和t出队。1次q操作后,q队列中为i,a,队列中最后2个元素出队。
例2 有如下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
变式2 有如下Python程序:
a=[4,2,5,1,9]
que=[0]*(2*len(a))
head,tail=0,0
for i in range(0,len(a)):
　　if head==tail or a[i]　　　　que[tail]=a[i]
　　　　tail+=1
　　elif a[i]>que[tail-1]:
　　　　que[tail]=a[i]
　　　　tail+=1;head+=1
print(que[head:tail])
执行以上程序段后,输出结果是(　　)
A.4,7 B.5,1,9
C.2,5,1,9 D.4,7,2,5,1,9
答案　B
解析　本题考查队列的算法实现。遍历列表a中元素,若队列为空或遍历的元素值a[i]小于队首que[head],直接将a[i]入队。若遍历的元素值比队尾元素大,则将队首出队后再将a[i]入队。队列中元素变化情况为[4,2]、[2,5]、[2,5,1]、[5,1,9]。
1.有一个队列S,其中指针head指向队首元素的位置,指针tail指向队尾元素的下一个位置。关于该队列说法正确的是(　　)
A.队列中元素个数为tail-head+1
B.新元素入队时,指针head向右移动
C.元素出队时,指针tail向右移动
D.当tail==len(S)时,无法再入队新元素
答案　D
解析　本题考查队列性质和基本操作。tail是指向队尾元素后面的位置,因此队列长度为tail-head。当tail值为len(S),队尾元素存储在len(S)-1,因此队列已满。
2.某队列的数据结构如图所示,head和tail分别为队列的头、尾指针。现对该队列进行以下操作:①队首元素出队输出②队首元素出队再入队,重复①②操作直到队列为空。
若队列数据元素为“CHINA”,则输出顺序是(　　)
A.CIANH B.CIAHN
C.CAHNI D.CHINA
答案　A
解析　队列的变化情况为CHINA→INAH→AHN→NH→H。
3.给一个队列如下约定:T操作是指队列中1个元素出队后再入队,P操作是指1个元素入队。原始队列经过TTPTP系列操作后,队列中队首到队尾的元素依次为ABCDE,则原始队列中队首到队尾的元素依次为(　　)
A.ABC B.ABD
C.BAE D.BADEC
答案　B
解析　A选项经过TTPTP系列操作,第3个元素必须是新入队的,而元素C已经存在于队列中。B选项元素AB出队后入队,C入队,队列为DABC,D出队后再入队,队列为ABCD,最后E入队。C选项第3个元素E已经在队列中。D选项原始队列有5个元素,再入队2个,将有7个元素。
4.有1个队列,队首到队尾的元素依次为8,10,12,9。若队首元素是偶数则先出队,再将偶数整除2后重新入队,若队首元素是奇数,直接出队。入队或出队各算一次操作,经过6次操作后,队列中队首到队尾的元素依次为(　　)
A.2,3 B.6,2,3
C.9,4,5 D.9,4,5,6
答案　D
解析　本题考查队列性质和操作。根据队列的特点“先进先出,后进后出”,8出队后4入队(2次),10出队后5入队(2次),12出队后6入队(2次)。共6次,其结果为9,4,5,6。
5.有2个队列a和b,队首到队尾的元素依次分别为“5,7,9”和“6,4,8”。约定:T操作是指队列a中1个元素先出队,若大于队列b的队首元素则再入b队列,否则不入;Q操作是指队列b中1个元素先出队,若大于队列b的队尾元素则再入b队列,否则不入。则经过TTQQQQT系列操作后,队列b中的元素个数为(　　)
A.1 B.2
C.3 D.4
答案　B
解析　5和7出队,由于7大于6,则7入队列b。6,4,8依次出队,8大于7,队列b中有7,8。第4个Q表示7出队后不入队。最后队列a中9出队入,入队列b,队列b有元素8和9。
6.元素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。
7.队列Q从队首到队尾的元素依次为5、2、7、3、6,栈S初始为空。约定:若栈为空或者队首元素小于栈顶元素,那么队首元素出队并入栈;否则,将栈内所有小于队首元素的元素依次出栈并入队,然后将队首元素出队并入栈。反复执行上述操作,直到队列为空。最终,栈S中从栈顶到栈底的元素依次为(　　)
A.2、3、5、6、7 B.7、6、5、3、2
C.7、6、5、2、3 D.5、2、7、3、6
答案　A
解析　程序的功能是实现从栈底到栈顶的降序排列。
8.队列Q中的元素依次为1,2,3,4,栈S为空。约定:P操作是队首元素出队后入栈,B操作是队首元素出队后入队,T操作是指栈顶元素出栈后入队。执行操作PPBT后,队列Q中的元素依次为(　　)
A.4,3,2 B.4,2,3
C.4,3,1 D.4,2,1
答案　A
解析　元素1,2出队后入栈,栈顶元素为2。B操作是队首元素出队后入队,队列中为4,3,因此最后队列中为4,3,2。
9.执行如下程序段后,变量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
答案　C
解析　程序功能实现查找最长不重复的子串,该子串为'engi '。
10.某Python程序如下:
q=[""]*50;head=tail=0
s="ningbo"
for i in s:
　　q[tail]=i;tail+=1
while head　　print(q[head],end="")
　　head+=1
　　for i in range(3):
　　　　q[tail]=q[head]
　　　　head+=1;tail+=1
执行该程序段后,输出结果为(　　)
A.nbgoni B.nbogni
C.goninb D.ningbo
答案　A
解析　操作过程:队首出队,紧接着3个入队尾后出队,直至队列为空。ningbo→boing→goin→oin→ni→i。
11.某Python程序段如下:
s="h#Ap#py"
que=[""]*10;res=""
head,tail=0,0
for i in range(len(s)):
　　if 'a'<=s[i]<='z':
　　　　que[tail]=s[i]
　　　　tail+=1
　　elif head　　　　head+=1
print(que[head:tail])
执行该程序段,输出的结果是(　　)
A.['h','p','p','y']
B.['p','p','y']
C.['p','y']
D.['y']
答案　C
解析　如果是小写字母直接入队,否则当队列不空时,就让队中元素出队。元素h先入队,元素#让h出队,队空,遍历到A时,无任何操作。元素p入队后,元素#让其出队,接着元素p和y入队。
12.有如下程序段:
head=0;tail=5
que=['a','b','c','d','e']
while head+1　　if head%4!=0:
　　　　que.append(que[head])
　　　　tail+=1
　　head+=1
print(que[head])
执行如下程序段后,最后输出的内容为(　　)
A.a B.b
C.c D.d
答案　C
解析　当head不是0或不是4的倍数时,队首元素出队后再入队,否则就直接出队,直到队列中只剩下一个元素。元素a和e先出队。元素bcd出队后再入队,head值为8,接着元素b出队。head为9,元素cd出队后入队,head为11,元素c出队入队,head为12,元素d出队,最后剩下元素c。
13.有如下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']
答案　C
解析　本题考查队列基本操作。遍历列表s,当元素不在队列中,将该元素入队,否则将队首元素出队(该元素不入队)。遍历第2个第3个d时,ab出队,队列中有[c,d],接着bha依次入队。
14.列表q长度为20,q[0]到q[7]的值依次为'a','b','c','a','c','d','d','e',执行如下程序段后,输出的结果为(　　)
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
答案　A
解析　分析程序段可知,该程序段实现的是一种消消乐游戏,即若新遍历到的元素和队首的元素不同或者队列为空,则将新元素入队。若新遍历到的元素和队首的元素相同,则将所有队列中的元素清空。因此队列中最后剩余的元素为c,d,d,e。
15.有如Python程序段:
a=[3,1,-6,0,-1,5,2,-5,1,3]
n=len(a);q=[0]*n
head,tail=0,0
for i in range(0,n):
　　if head　　　　if q[head]+a[i]>0:
　　　　　　q[tail]=q[tail-1]+a[i]
　　　　　　tail+=1
　　　　else:
　　　　　　head=tail
　　else:
　　　　if a[i]>0:
　　　　　　q[tail]=a[i]
　　　　　　tail+=1
print(tail-head)
执行以上程序段后,输出的结果为(　　)
A.2 B.3
C.5 D.6
答案　A
解析　若队列为空且a[i]大于0,将a[i]入队。若队列不空,当头首与a[i]大于0,将q[tail-1]+a[i]的值入队,当头首与a[i]小于等于0,清空队列。元素3和元素3+1入队,由于3和-6的值小于0,清空队列,0和-1不入队。元素5和元素5+2入队,由于5和-5的值等于0,清空队列。元素1和元素1+3入队,队列中有两个元素。
16.有如下Python程序段:
import random
que=["a","b","c","d","","","","","",""]
head=0;tail=4;ans=""
for i in range(5):
　　if random.randint(0,1)==0:
　　　　ans+=que[head]
　　　　que[tail]=que[head]
　　　　head+=1
　　　　tail+=1
　　else:
　　　　head+=1
执行该程序段后,ans的值不可能是(　　)
A."bcc" B."aa"
C."bcdb" D."abcd"
答案　A
解析　循环次数为5次,每次循环在将队首移至队尾与直接出队之间选择其一,在队首移至队尾前将队首存储在ans中。A选项a直接出队,b出队后入队,队列为cdb,c出队后入队,队列为dbc,d和b出队,c再次出队后入队,共需6次循环。B选项a出队后入队,bcd依次出队,a出队后入队。C选项a出队,bcd出队再入队,b再次出队再入队。D选项abcd出队再入队,a出队。
17.有如下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
答案　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.某队列中的元素依次为"R","o","u","t","e","r",将反复对队内元素做如下操作,直到队列元素为空:①队首元素出队并在队尾入队;②队首元素出队并输出。则输出顺序为(　　)
A.Rueort B.Reorut
C.otruRe D.otrueR
答案　C
解析　队列具有先进先出的特性,出队后入队的元素还是保持在原队列的顺序。每间隔一个元素出队,otr先出队,队列中有元素Rue,接着是uRe的顺序。
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.约定:T操作是指在队列中1个元素出队后再入队,E操作是指将1个元素入队,P操作是指队列中1个元素出队,队首指针head和队尾指针tail初始值均为0。则经过EETPETEP系列操作后,队首指针head和队尾指针tail的值分别为(　　)
A.3　4 B.3　5
C.4　5 D.4　6
答案　D
解析　本题考查队列的基本操作。T操作既有入队,又有出队,因此共有6次入队,4次出队,每次出队和入队,指针分别加1。
4.有1个队列,队首到队尾的元素依次为1,2,3,4,5,6,7。现进行如下操作:①出队2个元素;②再出队1个元素并将该元素入队。重复以上操作,直至队列中仅剩1个元素。则该元素是(　　)
A.3 B.5
C.6 D.7
答案　C
解析　元素1,2和4,5出队,3和6出队后入队,队中有7,3,6,元素7,3后,队中只有元素6。
5.队列S有若干元素。约定:U操作是指出队,H操作是指元素出队后再入队。经过UHUHHU操作后,队列中队首到队尾的元素依次为4,1,3,则队列S初始状态中队首到队尾的元素可能为(　　)
A.1,1,4,4,3,3 B.4,4,1,1,3,3
C.1,4,3,1,4,3 D.3,1,4,3,1,4
答案　B
解析　A选项经过该操作后的结果为1,4,3。C选项经过该操作后的结果为4,1,4。D选项经过该操作后的结果为1,3,1。
6.有“甲乙丙丁戊”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
解析　甲先出队,乙和丙出队后入队,丁出队买票,乙和丁之间有游客戊。
7.现有一队列"ECBAD"可以进行如下两种操作:①队首出队后入队②队首出队进入结果区。要求结果区为"ABCDE",则元素"D"被执行①操作的次数至少为(　　)
A.1 B.2
C.3 D.4
答案　B
解析　元素"ECB"出队后入队,元素A出队,元素D出队并入队1次。元素E和C出队并和队,B出队,元素D出队并入队第2次,队列中为ECD。元素E出队后入队,各个元素再依次出队。
8.有两个队列Q1与Q2,初始都为空,经过一系列入队、出队操作(数据全部入队后,才能进行出队操作),若元素入队的顺序是a,b,c,d,e,则不可能的出队序列是(　　)
A.acbde B.ebcda
C.abcde D.daebc
答案　B
解析　A选项abde入Q1队列,c入Q2队列。B选项由于e最后入队,若要第1个出队,则e必须占用一个队列,剩余的数据不符合先进先出的规则。C选项只用一个队列就可以实现。D选项元素d和e入Q1队列,a,b,c入Q2队列。
9.数据S1至S4的优先级依次为3,4,1,2,某设备按优先级1至4依次发送数据,利用队列S组织数据并模拟发送过程,初始队首至队尾数据依次为:S1、S4、S3、S2。可利用操作M(出队后再入队)调整数据发送顺序,为将数据发送完毕,则M的执行次数至少为(　　)
A.4 B.5
C.6 D.7
答案　B
解析　队列中各数据的优化级为3,2,1,4,S1和S4先进行M操作各一次,S3出队,S2和S1进行M操作各一次,S4出队,S2进行M操作一次,S1、S2出队。
10.有如下Python程序:
a=[13,12,12,15,26,23,36]
que=[0]*len(a)
head=tail=0
for x in a:
　　while head　　　　if x　　　　　　tail-=1
　　　　else:
　　　　　　break
　　que[tail]=x
　　tail+=1
print(que[head:tail])
执行后,程序输出结果为(　　)
A.12 15 26 36 B.12 15 23 26
C.12 12 15 23 36 D.12 13 15 23 36
答案　C
解析　遍历数组a,若队列不空,且x比队尾元素小,队尾元素不断地出队,再让x入队。整个过程描述为13入队后出队,12,12,15,26依次入队,26出队,23,36入队。
11.某Python程序段如下:
s="21027,53523,042,";ans=""
q=[0]*100;head=tail=0
for i in range(len(s)):
　　if "0"<=s[i]<="9":
　　　　q[tail]=s[i];tail+=1
　　elif s[i]==",":
　　　　flag=True
　　　　while head　　　　　　ans+=q[head];head+=1
　　　　　　if head!=tail and flag:
　　　　　　　　head+=1
　　　　　　flag=not flag
执行该程序段后,变量ans的值为(　　)
A."20735204" B."20255202"
C."20755302" D."20235304"
答案　B
解析　程序的功能遇到数字字符进行入队操作,遇到逗号进行出队操作,tmp 将出队的数字字符进行拼接,当flag为True时,跳过flag为True时第2个出队的数字字符,所以拼接的依次是"2"→"0"→"2"→"5"→"5"→"2"→"0"→"2"。
12.有如下Python程序段:
s="ABCDEF";que=[""]*10
head=0;tail=0
for i in range(len(s)):
　　if i % 2==0:
　　　　que[tail]=s[len(s)-1-i]
　　else:
　　　　que[tail]=s[i-1]
　　tail=tail+1
while head　　print(que[head],end="")
　　head+=1
该程序运行后输出的结果为(　　)
A.FAEBDC B.FADCBE
C.FBDDBF D.FDBACE
答案　B
解析　奇数位把字符s中索引i的对称位置中字符入队,偶数位把字符s中前一位置中字符入队。
13.有如下Python程序段:
s=input()
d=[-1]*10;head=tail=0
for i in range(len(s)):
　　if d[int(s[i])]　　　　if tail-head==3:
　　　　　　head+=1
　　　　d[int(s[i])]=tail
　　　　tail+=1
若执行程序后,d的值为[-1,4,6,5,3,-1,-1,-1,-1,-1],则输入的s值可能是(　　)
A."6954132" B."11114132"
C."1324132" D."41341322"
答案　C
解析　遍历字符串s,当前元素未出现过或比队首元素下标小,若队列元素个数等于3,出队一个元素,当前元素下标入队。
14.有如下程序段:
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
解析　本题考查队列的算法实现。vis是一个标志数组,当其元素值为0时,可以入队,保证队列中数据是唯一的。当队列中元素个数大于等于3时,将进行出队操作。ans统计入队次数。输入x的值1,2入队,接着1不能入队,5入队,当输入4时,让1出队,4入队。第2个4不能入队,最后一个1入队。
15.有如下Python程序段:
from random import randint
n=5;q=[0]*n
head=tail=randint(0,n-1)
while head!=tail+1:
　　num=randint(1,n)
　　if q[head]!=num:
　　　　q[tail]=num
　　　　tail+=1
　　　　if tail==n:tail=0
　　else:
　　　　q[head]=0;head+=1
　　　　if head==n:head=0
执行该程序段后,列表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
解析　初始队列q为空,随机选择一个位置作为head和tail,将产生的数存入队尾,队尾向后移动,若队尾到达n,则tail的为0,此时队尾在队首的前面,继续产生新的数入队。当队尾指针和队首指针相差1时,结束循环,因此队列中必须只包含一个0,排除选项A和D。随机生成1到n之间的值num,当队首和num值不相同时,将num存入队列,否则将队首设置为0,执行一次出队操作,队列中的数据不允许出现与当前队首元素重复值,若出现重复,则会将队首元素进行出队。tail指向0的位置,head在其后,队列中不可能存在与队首相同的元素。
16.有如下Python程序段:
from random import randint
q=[1,2,14,5,6,7,9,10]
head=0;tail=len(q)-1;ans=0
m=randint(1,3)
q+=[0]*m
for i in range(m):
　　for j in range(2**i-1):
　　　　head+=1
　　ans+=q[head]
　　q[tail]=q[head]
　　head+=1;tail+=1
执行该程序段后,变量ans的值不可能是(　　)
A.1 B.15
C.24 D.34
答案　D
解析　变量m为1,2,3的随机数,若m为1,i只能取到0,2**0-1结果是0,没有进入内循环。ans累加q[0],值为1。若m为2,q列表末尾插入2个0,当i为0时,没有出队,ans为1,队首出队重新入队。当i为1时,内循环执行一次,2出队,指针head值为2。ans累加q[2],结果是15。若m为3,外循环执行2次后,ans的值为3,head值为2,第3次执行外循环时,内循环执行3次,head的值为6,ans累加9,值为24。
17.执行下列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+=1
print(que[head: tail])
A.[3,2,1] B.[1,2,3]
C.[1,3,1] D.[3,2,3]
答案　D
解析　遍历data数组,如果data[i]是奇数,入队。data[i]是偶数且队列中至少有2个元素时,队首元素出队且累加到que[tail-1]元素。遍历到1时,1入队;遍历到2时,队列只有1个元素。遍历到3时,3入队;遍历到1时,1入队;遍历到1时,1出队且累加到队尾,队列为[3,2];遍历到3时,3入队。
18.有如下Python程序段:
que=["A","B","C","D","E"]+[""]*10
n=5;head=0;tail=5
for i in range(n):
　　print(que[head],end="")
　　head+=1
　　for j in range(i):
　　　　que[tail]=que[head]
　　　　tail+=1
　　　　head+=1
执行该程序段后,显示的结果是(　　)
A.ACBED B.ABDCE
C.ABDEC D.ACBDE
答案　C
解析　本题考查队列的基本操作。外循环5次,每次先出队一个元素,内循环分别循环0,1,2,3,4次,每次循环将队列元素出队并入队到最后。当i为0时,A出队,不循环移动。i为1时,B出队,C后移,队列中为DEC。i为2时,D出队,EC后移,队列中为EC。i为3时,E出队,C后移3次,队列中为C。最后C出队。
19.执行如下程序段后,输出的结果是(　　)
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
答案　B
解析　本题考查队列的基本操作。程序的功能是查找队列中最小值,pre初值为10,每次出队一个元素,出队元素也pre比较,记录其最小值的过程。
20.有如下Python程序段:
import random
q=[0]*5
head=tail=0
for i in range(5):
　　if random.randint(0,1)==0:
　　　　q[tail]=random.randint(1,9)
　　　　tail+=1
　　elif head!=tail and q[tail-1]　　　　q[tail]=q[head]
　　　　head+=1
　　　　tail+=1
执行该程序段后,q的值不可能是(　　)
A.[0,0,0,0,0] B.[5,4,3,2,1]
C.[5,8,3,0,0] D.[0,5,6,0,0]
答案　D
解析　本题队列的基本操作。入队的条件是产生的随机数为0,出队的条件是队不空且队尾元素比较队首元素小。A选项产生随机数均为1,没有任何元素入队。B选项依次入队过程中,队尾元素大于队尾元素值。C选项队列中只有3个元素,先产生8,5,再进行出队和入队,最后再产生3,循环了4次,还有一次产生的随机数为1,不做任何操作。D选项只要有元素入队,第一个元素不可能为0。
21.有如下Python程序段:
q=[i for i in range(7)]
head,tail=1,0;cnt=0
while (head+1)%7!=tail:
　　cnt+=1
　　if cnt==3:
　　　　cnt=0
　　else:
　　　　q[tail]=q[head]
　　　　tail=(tail+1)%7
　　head=(head+1)%7
print(q[head])
运行该程序段后,输出结果是(　　)
A.5 B.4
C.2 D.1
答案　D
解析　head=1,tail=0表示此队列中的元素为1到6,在此循环队列中数到第3个时出队,直到队列中只剩一个元素,出队的元素依次为3、6、4、2、5,最后队列中剩下的元素为1。

展开更多......

收起↑