2025届高中信息技术二轮复习 第三部分 数据的存储与逻辑结构 专题15 队 列(课件 学案)

资源下载
  1. 二一教育资源

2025届高中信息技术二轮复习 第三部分 数据的存储与逻辑结构 专题15 队 列(课件 学案)

资源简介

专题15 队 列
学习目标 1.通过生活实例,理解队列的性质和作用;
2.在理解队首和队尾指针的功能上,掌握队列和循环队列元素个数的计算方法;
3.在理解队首和队尾指针的功能上,掌握建队、入队和出队的操作过程.
栈和队列主要用于计算过程中保存的临时数据,为了更好地检索到需要的数据,需要复杂的存储机制,这样的存储机制称为缓存。栈和队列就是使用最多的缓存结构。队列是一种在数组两端分别进行存取的数据结构,最大特点是数据在存取时,无需查询,时间复杂度为O(1),先存取的数据先被取出。队列是一种先进先出、后进后出的线性表,允许插入的一端称为队尾,允许删除的一端称为队头。队列一般按顺序结构存储,可以用数组来实现。设置头指针head和尾指针tail记录队首元素位置和队尾元素的下一个位置。在Python中,用列表(数组)创建队列,元素入队时,先将元素存储到tail指针指向位置,然后tail指针加1,即向队尾方向移动。元素出队时,当队列非空时条件head!=tail,先读取队首head指针指向的元素,然后head指针加1,即向队尾方向移动,直到head==tail为止。
(2023年6月浙江省选考)列表q长度为20,q[0]至q[4]的值依次为'p','r','i','n','t',执行如下程序段后,输出的最后一个字符为(  )
head,tail= 0,5
while head < tail:
  if head % 3 == 0:
print(q[head])
  else:
q[tail] = q[head]
tail += 1
  head += 1
A.t B.n C.i D.r
重难点1 队列的特性
队列是一种先进先出的线性表,允许插入的一端称为队尾,允许删除的一端称为队首。先进先出是队列的特性,若元素出队后将入队,那么入队后的元素还是维持原来的顺序。建队时,指针head和tail均指向0,head加1表示出队,tail加1表示入队。判断队列是否空的条件是head!=tail,判断队列中元素的数量为tail-head。
例题 有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记录队首元素位置,队尾指针tail记录队尾元素的下一个位置,队列q的队尾元素值为q[tail-1]。入队时,需将x赋值给q[tail],让其成为新的队尾元素,再移动tail指针。出队时,需先将q[head]赋值给x,再移动head指针。
例1 执行下列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]
变式1 有如下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']
例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程序段:
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 队列的特性
1.有一个队列S,其中指针head指向队首元素的位置,指针tail指向队尾元素的下一个位置。关于该队列说法正确的是(  )
A.队列中元素个数为tail-head+1
B.新元素入队时,指针head向右移动
C.元素出队时,指针tail向右移动
D.当tail的值为len(S)时,无法再入队新元素
2.某队列经过“出队”“入队”操作后,队首指针head=2,队尾指针tail=6,则该队列中剩余的元素个数是(  )
A.2 B.4 C.5 D.6
3.有1个队列,现有元素依次为1,2,3,4。约定:P操作是指1个入队,T操作是指队列中1个元素出队后再入队,Q操作是指队列中1个元素出队。则经过PPTQTPQ系列操作后,队列中队首到队尾的元素依次为(  )
A.1 B.1,3 C.3,4 D.3
4.若用一个规模为20的数组来实现队列,已知当前队尾指针tail的值为8,队头指针head的值为3,进行如下操作:连续删除2个元素、连续插入5个元素、删除1个元素,连续插入2个元素。则操作后指针head和tail的值分别为(  )
A.5和14 B.6和14
C.6和15 D.7和15
5.队列q中队首至队尾元素依次为“A,B,C,D,E,F”,约定:S为出队操作,U为出队再入队操作,若要使队列q队首至队尾元素依次为“B,D,E”,下列操作可实现的是(  )
A.USUSSU B.SUSUUS
C.SSSUUU D.SUUSUS
6.某种特殊的队列 Q,支持以下3个操作:操作Q1,若队列非空,队首元素出队,并输出;操作Q2,若队列非空,队首元素出队;操作Q3,一个元素入队;以上任意一种操作后,若队列非空,新的队首元素仍为队列中所有元素的最小值。若队列 Q 初始状态为空,依次进行 Q3、Q2、Q1、Q2、Q3、Q1、Q3 七次操作后,下列说法正确的是(  )
A.当前队列中的元素个数为2
B.输出的元素个数为2
C.第一个输出的元素肯定比当前队首元素大
D.队列初始状态是否为空对输出结果有影响
重难点2 队列的算法实现
1.执行如下程序段后,变量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
2.有如下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
3.有如下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
4.列表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
5.有如下Python程序:
a=[4,2,5,1,9]
que=[0]*7
head,tail=0,0
que[tail]=a[0]
tail+=1
for i in range(1,len(a)):
  if a[i]>que[tail-1]:
  que[tail]=a[i]
  tail+=1;head+=1
  elif a[i]  que[tail]=a[i]
  tail+=1
print(que[head:tail])
执行以上程序段后,输出结果是(  )
A.4,7 B.5,1,9
C.2,5,1,9 D.4,7,2,5,1,9
6.有如下程序段:
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
重难点1 队列的特性
1.下列有关队列的说法正确的是(  )
A.队列是一种先进先出的线性表,插入一端为队首,删除一端称队尾
B.队列的存储结构,可用数组实现,也可用链表实现
C.一队列队头指针head,队尾指针tail, 则tail-1-head表示队列中元素个数
D.学生排队就餐与软件连续撤销操作都是数据结构“队列”的应用实例
2.在该系统中,可以利用队列来储存当前正在排队顾客的编号,head指向队首元素,tail指向队尾元素的下一个位置,若tail=head+3,则现在排队的顾客数量为(  )
A.2 B.3 C.4 D.5
3.假设队列的空间足够,队首指针head和队尾指针tail经过“出队、入队、出队、出队、入队、入队、出队”这一系列操作后,head=7,tail=9。则操作前的head和tail的值分别为(  )
A.11 12 B.2 5
C.3 6 D.3 5
4.有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
5.某队列的数据结构如图所示,head和tail分别是队列的头指针和尾指针。现对该队列进行下列操作:①队首元素出队后再入队;②队首元素出队并输出,重复①②操作直到队列为空。若队列的数据元素为“Python”,则输出的顺序是(  )
A.Python B.Ptoynh
C.yhntPo D.yhntoP
6.约定:T操作是指在队列中1个元素出队后再入队,E操作是指将1个元素入队,P操作是指队列中1个元素出队,队首指针head和队尾指针tail初始值均为0。则经过EETPETEP系列操作后,队首指针head和队尾指针tail的值分别为(  )
A.3 4 B.3 5 C.4 5 D.4 6
7.有1个队列,队首到队尾的元素依次为1,2,3,4,5。约定:T操作是指队列中1个元素出队后再入队,Q操作是指队列中1个元素出队。则经过TTQTTQTTQ系列操作后,队列中队首到队尾的元素依次为(  )
A.4,5 B.5,4 C.2,4 D.4,2
8.队列Q从队首到队尾的元素依次为3,1,2,栈S初始为空。约定以下操作:H操作是指元素出队后再入队,T操作是指元素出队后入栈,P操作是指元素出栈。经过一系列操作后,最终出栈顺序为1,2,3,以下操作不可能的是(  )
A.TTPTPP B.HTTTPPP
C.THTTPPP D.HTPTPTP
9.假设高铁站的售票窗口平均每分钟过来一个人购票,每人的购票时间平均约为2分钟,某车站在中午时段开了一个售票窗口,12:01:00的时候有1个人刚开始购票,3个人在等待,那么12:11:00时队伍中等待购票的人数为(  )
A.7 B.8 C.9 D.10
重难点2 队列的算法实现
1.有如下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):
    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]
2.执行如下程序段后,输出的结果是(  )
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
3.有如下Python程序段:
que = ['A', 'B', 'C', 'D', 'E']
for i in range(10):
  que.append(-1)
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
4.某 Python 程序如下:
que=[0]*7
a=[2,3,5,1,3,5,2]
head=0 ;tail=0
for i in a:
  if tail-head==3:
  head+=1
  elif i not in que[head:tail]:
  que[tail]=i
  tail+=1
print(que[head:tail])
执行上述程序后,输出的结果为(  )
A.[2, 3, 5, 1] B.[3, 5, 2]
C.[2, 3, 5] D.[5, 1, 2]
5.有如下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
  s+=i
  if ans  ans=s
  while ik:
  s-=q[head]
  head=head+1
执行该程序段后,输入k的值为2,变量ans的值是(  )
A.18 B.19 C.21 D.22
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.有如下程序段:
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]
8.有如下Python 程序段:
import random
q=[0]*5
head,tail=0,0
for i in range(5):
  if random.randint(0,i)%2==0:
  q[tail]=random.randint(1,9) #随机生成1到9之间的整数
  elif head  q[tail]=q[head]
  head +=1
  tail +=1
print(q)
执行该程序段后,列表q 的值不可能是(  )
A.[1,0,1,0,9] B.[5,4,3,2,1]
C.[5,8,3,0,0] D.[5,5,6,0,6]
9.有如下Python程序段:
import random
a=[8,10,2,7,11,9,16]
c=[0]*len(a)
head=0;tail=0
for i in range(len(a)):
  t=random.randint(0,1)
  if tail-head<2 or t==0:
  c[tail]=a[i]
   tail=tail+1
  elif a[i]>c[head]:
   head=head+1
print(c[head:tail])
执行该程序段后,输出的内容不可能是(  )
A.[10,9,16] B.[8,10,11,9,16]
C.[8,10,2,9] D.[10,7,16]
10.有如下Python程序段:
from random import randint
s=″14257″;q=[″″]*10; ans=″″
head=tail=0
for i in s:
  q[tail]=i
  tail+=1
for i in range(len(s)):
  t=randint(0, 1)
  if t==0:
  q[tail]=q[head]
  tail+=1
  head+=1
while tail>head:
  ans+=q[head]
  head+=1
print(ans)
运行该程序段,则输出的值不可能的是(  )
A.5 B.41 C.457 D.14257
11.有如下Python程序段:
que=[1,5,3,2,7]+[0]*100 #构建列表que, 形如[1,5,3,2,7,0,0,0,…]
head=0;tail=5
st=[0]*len(que) #构建栈st
top=-1
while head!=tail:
  while top!=- 1 and que[head]>st[top]:
  que[tail]=st[top]
   tail+=1
   top-=1
  top+=1
  st[top]=que[head]
  head+=1
执行该程序段后,栈st从栈顶到栈底的元素依次为(  )
A.7,5,3,2,1 B.1,2,3,5,7
C.0,1,2,3,5,7 D.7,5,3,2,1,0
专题15 队 列
学习目标 1.通过生活实例,理解队列的性质和作用;
2.在理解队首和队尾指针的功能上,掌握队列和循环队列元素个数的计算方法;
3.在理解队首和队尾指针的功能上,掌握建队、入队和出队的操作过程.
栈和队列主要用于计算过程中保存的临时数据,为了更好地检索到需要的数据,需要复杂的存储机制,这样的存储机制称为缓存。栈和队列就是使用最多的缓存结构。队列是一种在数组两端分别进行存取的数据结构,最大特点是数据在存取时,无需查询,时间复杂度为O(1),先存取的数据先被取出。队列是一种先进先出、后进后出的线性表,允许插入的一端称为队尾,允许删除的一端称为队头。队列一般按顺序结构存储,可以用数组来实现。设置头指针head和尾指针tail记录队首元素位置和队尾元素的下一个位置。在Python中,用列表(数组)创建队列,元素入队时,先将元素存储到tail指针指向位置,然后tail指针加1,即向队尾方向移动。元素出队时,当队列非空时条件head!=tail,先读取队首head指针指向的元素,然后head指针加1,即向队尾方向移动,直到head==tail为止。
(2023年6月浙江省选考)列表q长度为20,q[0]至q[4]的值依次为'p','r','i','n','t',执行如下程序段后,输出的最后一个字符为(  )
head,tail= 0,5
while head < tail:
  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出队。
重难点1 队列的特性
队列是一种先进先出的线性表,允许插入的一端称为队尾,允许删除的一端称为队首。先进先出是队列的特性,若元素出队后将入队,那么入队后的元素还是维持原来的顺序。建队时,指针head和tail均指向0,head加1表示出队,tail加1表示入队。判断队列是否空的条件是head!=tail,判断队列中元素的数量为tail-head。
例题 有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个队列,队首到队尾的元素依次为 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。
重难点2 队列的算法实现
头指针head记录队首元素位置,队尾指针tail记录队尾元素的下一个位置,队列q的队尾元素值为q[tail-1]。入队时,需将x赋值给q[tail],让其成为新的队尾元素,再移动tail指针。出队时,需先将q[head]赋值给x,再移动head指针。
例1 执行下列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]
思维点拨
明考向 本题考查队列的算法实现
精点拨 遍历data数组,如果data[i]是奇数,入队。data[i]是偶数且队列中至少有2个元素时,队首元素出队且累加到que[tail - 1]元素。遍历到1时,1入队;遍历到2时,队列只有1个元素。遍历到3时,3入队;遍历到1时,1入队;遍历到1时,1出队且累加到队尾,队列为[3,2] ;遍历到3时,3入队
答案 D
变式1 有如下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依次入队。
例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程序段:
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 队列的特性
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=2,队尾指针tail=6,则该队列中剩余的元素个数是(  )
A.2 B.4 C.5 D.6
答案 B
解析 本题考查队列的基本知识。队列中元素个数=tail-head=4。
3.有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。
4.若用一个规模为20的数组来实现队列,已知当前队尾指针tail的值为8,队头指针head的值为3,进行如下操作:连续删除2个元素、连续插入5个元素、删除1个元素,连续插入2个元素。则操作后指针head和tail的值分别为(  )
A.5和14 B.6和14
C.6和15 D.7和15
答案 C
解析 本题考查队列的入队出队操作。删除元素,即进行出队操作,出队时将队首元素删除,然后队首指针加1;插入元素,即进行入队操作,入队时先将元素插入,然后队尾指针加1。共删除3个元素,删除操作结束后,因此队头指针head的值为6,共插入7个元素,操作后队尾指针tail的值为15。
5.队列q中队首至队尾元素依次为“A,B,C,D,E,F”,约定:S为出队操作,U为出队再入队操作,若要使队列q队首至队尾元素依次为“B,D,E”,下列操作可实现的是(  )
A.USUSSU B.SUSUUS
C.SSSUUU D.SUUSUS
答案 B
解析 元素A出队,元素B出队后入队,元素C出队,元素D和E出队后入队,元素F出队。
6.某种特殊的队列 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输出的结果不一样。
重难点2 队列的算法实现
1.执行如下程序段后,变量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'。
2.有如下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
答案 D
解析 遍历字符串s,当i%2==0条件成立时,将s[i]入队,否则将s[len(s)-i]入队。
3.有如下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入队。
4.列表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。
5.有如下Python程序:
a=[4,2,5,1,9]
que=[0]*7
head,tail=0,0
que[tail]=a[0]
tail+=1
for i in range(1,len(a)):
  if a[i]>que[tail-1]:
  que[tail]=a[i]
  tail+=1;head+=1
  elif a[i]  que[tail]=a[i]
  tail+=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
解析 队列中初始1个元素,值为4。遍历列表a中位置1到len(a)-1的元素,若遍历的元素值比队尾元素大,则将队首出队后再将a[i]入队。若遍历的元素值小于队首,直接将a[i]入队。队列中元素变化情况为[4, 2]、[2, 5]、[2, 5, 1]、[5, 1, 9]。
6.有如下程序段:
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入队。
重难点1 队列的特性
1.下列有关队列的说法正确的是(  )
A.队列是一种先进先出的线性表,插入一端为队首,删除一端称队尾
B.队列的存储结构,可用数组实现,也可用链表实现
C.一队列队头指针head,队尾指针tail, 则tail-1-head表示队列中元素个数
D.学生排队就餐与软件连续撤销操作都是数据结构“队列”的应用实例
答案 B
解析 本题考查队列的性质。A选项队列在队尾插入,在队首删除;C选项队尾指针tail指向队尾元素的下一个位置,所以tail-head表示队列中元素个数;D选项软件连续撤销操作是撤销前一步操作,是栈的应用实例。
2.在该系统中,可以利用队列来储存当前正在排队顾客的编号,head指向队首元素,tail指向队尾元素的下一个位置,若tail=head+3,则现在排队的顾客数量为(  )
A.2 B.3 C.4 D.5
答案 B
解析 队列的长度计算公式为tail-head,因此队列有3人排队。
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.有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。
5.某队列的数据结构如图所示,head和tail分别是队列的头指针和尾指针。现对该队列进行下列操作:①队首元素出队后再入队;②队首元素出队并输出,重复①②操作直到队列为空。若队列的数据元素为“Python”,则输出的顺序是(  )
A.Python B.Ptoynh
C.yhntPo D.yhntoP
答案 C
解析 题目中队列的元素执行队首元素出队,再从队尾入队,接下来队首元素出队从队尾入队,直至队列空,输出的顺序为C选项结果。
6.约定: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。
7.有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。
8.队列Q从队首到队尾的元素依次为3,1,2,栈S初始为空。约定以下操作:H操作是指元素出队后再入队,T操作是指元素出队后入栈,P操作是指元素出栈。经过一系列操作后,最终出栈顺序为1,2,3,以下操作不可能的是(  )
A.TTPTPP B.HTTTPPP
C.THTTPPP D.HTPTPTP
答案 B
解析 B选项先出队后入队,队列中为1,2,3,再依次入栈,出栈的顺序为3,2,1。
9.假设高铁站的售票窗口平均每分钟过来一个人购票,每人的购票时间平均约为2分钟,某车站在中午时段开了一个售票窗口,12:01:00的时候有1个人刚开始购票,3个人在等待,那么12:11:00时队伍中等待购票的人数为(  )
A.7 B.8 C.9 D.10
答案 C
解析 根据题目描述,10分钟过来了10个人购票,总共14人,其间4人结束购票,所以队伍还有10人,1人在购票,9人在等待。
重难点2 队列的算法实现
1.有如下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):
    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]
答案 B
解析 本题考查队列的入队与出队操作。字符串S中两个字符为一组,第1个元素t代表入队或出队,第2个元素代表n入队或出队的次数。A是入队,D是出队,若出队过程中队空,则中止出队。
2.执行如下程序段后,输出的结果是(  )
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比较,记录其最小值的过程。
3.有如下Python程序段:
que = ['A', 'B', 'C', 'D', 'E']
for i in range(10):
  que.append(-1)
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出队。
4.某 Python 程序如下:
que=[0]*7
a=[2,3,5,1,3,5,2]
head=0 ;tail=0
for i in a:
  if tail-head==3:
  head+=1
  elif i not in que[head:tail]:
  que[tail]=i
  tail+=1
print(que[head:tail])
执行上述程序后,输出的结果为(  )
A.[2, 3, 5, 1] B.[3, 5, 2]
C.[2, 3, 5] D.[5, 1, 2]
答案 B
解析 本题考查队列的基本操作。当i的值为2,3,5时,i均不在队列中,因此入列3次,tail=3,当i的值为1时,条件tail-head==3成立,因此进行出队(队首指向2)操作,队列中值依次为[3, 5],当i的值为3,5,不符合条件,当i的值为2时,入队。
5.有如下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
  s+=i
  if ans  ans=s
  while ik:
  s-=q[head]
  head=head+1
执行该程序段后,输入k的值为2,变量ans的值是(  )
A.18 B.19 C.21 D.22
答案 C
解析 遍历数组a并累加数组元素值,求队列的最大值;当遍历到的当前值小于队首或是长度大于k,将队首元素出队。s的值依次为[3,6,10]=19,[6,10,5]=21,[5,9]=14,[5,9,4]=18。
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
答案 A
解析 本题考查队列的相关操作。表达式(ord(i) - ord(″a″) + q[head]) % 26 的功能是将i转换为在字母表中索引位置,并循环后移q[head]个位置。计算出移动位置后,再转换为小写字母。q中元素实现出队后再入队,因此分别将a、b、c和x、y、z对应位置字母后称1、2、3位置。
7.有如下程序段:
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]
答案 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不可能产生。
8.有如下Python 程序段:
import random
q=[0]*5
head,tail=0,0
for i in range(5):
  if random.randint(0,i)%2==0:
  q[tail]=random.randint(1,9) #随机生成1到9之间的整数
  elif head  q[tail]=q[head]
  head +=1
  tail +=1
print(q)
执行该程序段后,列表q 的值不可能是(  )
A.[1,0,1,0,9] B.[5,4,3,2,1]
C.[5,8,3,0,0] D.[5,5,6,0,6]
答案 C
解析 循环5次,每次循环有3种可能,一是当i为偶数时,入队一个[1,9] 之间的整数要么,二是当i为奇数时,且q[tail-1]9.有如下Python程序段:
import random
a=[8,10,2,7,11,9,16]
c=[0]*len(a)
head=0;tail=0
for i in range(len(a)):
  t=random.randint(0,1)
  if tail-head<2 or t==0:
  c[tail]=a[i]
   tail=tail+1
  elif a[i]>c[head]:
   head=head+1
print(c[head:tail])
执行该程序段后,输出的内容不可能是(  )
A.[10,9,16] B.[8,10,11,9,16]
C.[8,10,2,9] D.[10,7,16]
答案 C
解析 若队列中数据元素小于2或者t的值为0,则将a[i]入队,否则当a[i]大于c[head]时出队,a中元素既可以不入队,也可以不出队(t为1,且a[i]小于等于c[head])。A选项8,10入队,2和7可以不入队,11让8出队,队列中只剩下1个元素,9入队,接着t的值为0,16入队。B选项8,10入队后,接着t的值依次为1,1,0,0,0。C选项队首为8,当遍历到11时,要么让8出队,要么产生的t为0,11入队,因此C不可能。D选项11让队首8出队,当遍历到16时,产生的t为0,16入队。
10.有如下Python程序段:
from random import randint
s=″14257″;q=[″″]*10; ans=″″
head=tail=0
for i in s:
  q[tail]=i
  tail+=1
for i in range(len(s)):
  t=randint(0, 1)
  if t==0:
  q[tail]=q[head]
  tail+=1
  head+=1
while tail>head:
  ans+=q[head]
  head+=1
print(ans)
运行该程序段,则输出的值不可能的是(  )
A.5 B.41 C.457 D.14257
答案 B
解析 本题考查队列的性质。语句q[tail]=q[head]表示将队首出队,再入队,中间也可能有元素出队,最后输出队列中元素。队列的特性是先进先出,无论有多少元素全部出队后,部分数据再入队,在队列的位置还是按原来的次序排列,因此选项B不可能。
11.有如下Python程序段:
que=[1,5,3,2,7]+[0]*100 #构建列表que, 形如[1,5,3,2,7,0,0,0,…]
head=0;tail=5
st=[0]*len(que) #构建栈st
top=-1
while head!=tail:
  while top!=- 1 and que[head]>st[top]:
  que[tail]=st[top]
   tail+=1
   top-=1
  top+=1
  st[top]=que[head]
  head+=1
执行该程序段后,栈st从栈顶到栈底的元素依次为(  )
A.7,5,3,2,1 B.1,2,3,5,7
C.0,1,2,3,5,7 D.7,5,3,2,1,0
答案 B
解析 程序功能是利用队列将栈中的元素进行升序排列。若栈不为空,当队首元素大于栈顶元素的值时,将栈中元素入队并出栈,否则将队首元素入栈并将队首进行出队操作。(共71张PPT)
专题15 队列
第三部分 数据的存储与逻辑结构
1.通过生活实例,理解队列的性质和作用;
2.在理解队首和队尾指针的功能上,掌握队列和循环队列元素个数的计算方法;
3.在理解队首和队尾指针的功能上,掌握建队、入队和出队的操作过程.
目 录
CONTENTS
体系构建
01
真题再现
02
考点精练
03
当堂检测
04
课后练习
05
体系构建
1
栈和队列主要用于计算过程中保存的临时数据,为了更好地检索到需要的数据,需要复杂的存储机制,这样的存储机制称为缓存。栈和队列就是使用最多的缓存结构。队列是一种在数组两端分别进行存取的数据结构,最大特点是数据在存取时,无需查询,时间复杂度为O(1),先存取的数据先被取出。队列是一种先进先出、后进后出的线性表,允许插入的一端称为队尾,允许删除的一端称为队头。队列一般按顺序结构存储,可以用数组来实现。设置头指针head和尾指针tail记录队首元素位置和队尾元素的下一个位置。在Python中,用列表(数组)创建队列,元素入队时,先将元素存储到tail指针指向位置,然后tail指针加1,即向队尾方向移动。元素出队时,当队列非空时条件head!=tail,先读取队首head指针指向的元素,然后head指针加1,即向队尾方向移动,直到head==tail为止。
真题再现
2
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出队。
考点精练
3
重难点1 队列的特性
队列是一种先进先出的线性表,允许插入的一端称为队尾,允许删除的一端称为队首。先进先出是队列的特性,若元素出队后将入队,那么入队后的元素还是维持原来的顺序。建队时,指针head和tail均指向0,head加1表示出队,tail加1表示入队。判断队列是否空的条件是head!=tail,判断队列中元素的数量为tail-head。
例题 有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
D
解析 本题考查队列性质和操作。根据队列的特点“先进先出,后进后出”,8出队后4入队(2次),10出队后5入队(2次),12出队后6入队(2次)。共6次,其结果为9,4,5,6。
重难点2 队列的算法实现
头指针head记录队首元素位置,队尾指针tail记录队尾元素的下一个位置,队列q的队尾元素值为q[tail-1]。入队时,需将x赋值给q[tail],让其成为新的队尾元素,再移动tail指针。出队时,需先将q[head]赋值给x,再移动head指针。
D
思维点拨
明考向 本题考查队列的算法实现
精点拨 遍历data数组,如果data[i]是奇数,入队。data[i]是偶数且队列中至少有2个元素时,队首元素出队且累加到que[tail - 1]元素。遍历到1时,1入队;遍历到2时,队列只有1个元素。遍历到3时,3入队;遍历到1时,1入队;遍历到1时,1出队且累加到队尾,队列为[3,2] ;遍历到3时,3入队
程序运行后,输出的结果是(  )
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依次入队。
程序运行后,输出结果可能为(  )
A.0 0 0 0 2 3 0 6 B.0 1 2 3 4
C.0 0 0 0 D.2 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入队。
当堂检测
4
重难点1 队列的特性
重难点2 队列的算法实现
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,因此队列已满。
B
解析 本题考查队列的基本知识。队列中元素个数=tail-head=4。
2.某队列经过“出队”“入队”操作后,队首指针head=2,队尾指针tail=6,则该队列中剩余的元素个数是(  )
A.2 B.4 C.5 D.6
D
解析 元素1,2入队,1出队后入队,队列为2,1。2出队,1出队后入队,3入队,1出队,因此队列中只有元素3。
3.有1个队列,现有元素依次为1,2,3,4。约定:P操作是指1个入队,T操作是指队列中1个元素出队后再入队,Q操作是指队列中1个元素出队。则经过PPTQTPQ系列操作后,队列中队首到队尾的元素依次为(  )
A.1 B.1,3 C.3,4 D.3
C
解析 本题考查队列的入队出队操作。删除元素,即进行出队操作,出队时将队首元素删除,然后队首指针加1;插入元素,即进行入队操作,入队时先将元素插入,然后队尾指针加1。共删除3个元素,删除操作结束后,因此队头指针head的值为6,共插入7个元素,操作后队尾指针tail的值为15。
4.若用一个规模为20的数组来实现队列,已知当前队尾指针tail的值为8,队头指针head的值为3,进行如下操作:连续删除2个元素、连续插入5个元素、删除1个元素,连续插入2个元素。则操作后指针head和tail的值分别为(  )
A.5和14 B.6和14
C.6和15 D.7和15
B
解析 元素A出队,元素B出队后入队,元素C出队,元素D和E出队后入队,元素F出队。
5.队列q中队首至队尾元素依次为“A,B,C,D,E,F”,约定:S为出队操作,U为出队再入队操作,若要使队列q队首至队尾元素依次为“B,D,E”,下列操作可实现的是(  )
A.USUSSU B.SUSUUS
C.SSSUUU D.SUUSUS
D
解析 操作Q3、Q2之后,队列为空。Q3、Q1,队列为空。因此队列中元素个数为1,Q1操作出队并输出元素,输出的元素个数为1。C选项没有可比性。D选项若队列不为空,则Q3、Q2、Q1、Q2输出的结果不一样。
6.某种特殊的队列 Q,支持以下3个操作:操作Q1,若队列非空,队首元素出队,并输出;操作Q2,若队列非空,队首元素出队;操作Q3,一个元素入队;以上任意一种操作后,若队列非空,新的队首元素仍为队列中所有元素的最小值。若队列 Q 初始状态为空,依次进行 Q3、Q2、Q1、Q2、Q3、Q1、Q3 七次操作后,下列说法正确的是(  )
A.当前队列中的元素个数为2
B.输出的元素个数为2
C.第一个输出的元素肯定比当前队首元素大
D.队列初始状态是否为空对输出结果有影响
C
解析 程序功能实现查找最长不重复的子串,该子串为'engi'。
执行该程序段后,输出的结果是(  )
A.ABCDEF B.FEDCBA
C.ACEFDB D.AFCDEB
解析 遍历字符串s,当i%2==0条件成立时,将s[i]入队,否则将s[len(s)-i]入队。
D
执行后,程序输出结果为(  )
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入队。
A
解析 分析程序段可知,该程序段实现的是一种消消乐游戏,即若新遍历到的元素和队首的元素不同或者队列为空,则将新元素入队。若新遍历到的元素和队首的元素相同,则将所有队列中的元素清空。因此队列中最后剩余的元素为 c,d,d,e。
B
解析 队列中初始1个元素,值为4。遍历列表a中位置1到len(a)-1的元素,若遍历的元素值比队尾元素大,则将队首出队后再将a[i]入队。若遍历的元素值小于队首,直接将a[i]入队。队列中元素变化情况为[4, 2]、[2, 5]、[2, 5, 1]、[5, 1, 9]。
C
解析 本题考查队列的算法实现。vis是一个标志数组,当其元素值为0时,可以入队,保证队列中数据是唯一的。当队列中元素个数大于等于3时,将进行出队操作。ans统计入队次数。输入x的值1,2入队,接着1不能入队,5入队,当输入4时,让1出队,4入队。第2个4不能入队,最后一个1入队。
课后练习
5
重难点1 队列的特性
重难点2 队列的算法实现
1.下列有关队列的说法正确的是(  )
A.队列是一种先进先出的线性表,插入一端为队首,删除一端称队尾
B.队列的存储结构,可用数组实现,也可用链表实现
C.一队列队头指针head,队尾指针tail, 则tail-1-head表示队列中元素个数
D.学生排队就餐与软件连续撤销操作都是数据结构“队列”的应用实例
B
解析 本题考查队列的性质。A选项队列在队尾插入,在队首删除;C选项队尾指针tail指向队尾元素的下一个位置,所以tail-head表示队列中元素个数;D选项软件连续撤销操作是撤销前一步操作,是栈的应用实例。
2.在该系统中,可以利用队列来储存当前正在排队顾客的编号,head指向队首元素,tail指向队尾元素的下一个位置,若tail=head+3,则现在排队的顾客数量为(  )
A.2 B.3 C.4 D.5
B
解析 队列的长度计算公式为tail-head,因此队列有3人排队。
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.有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。
C
解析 题目中队列的元素执行队首元素出队,再从队尾入队,接下来队首元素出队从队尾入队,直至队列空,输出的顺序为C选项结果。
5.某队列的数据结构如图所示,head和tail分别是队列的头指针和尾指针。现对该队列进行下列操作:①队首元素出队后再入队;②队首元素出队并输出,重复①②操作直到队列为空。若队列的数据元素为“Python”,则输出的顺序是(  )
A.Python B.Ptoynh
C.yhntPo D.yhntoP
6.约定: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。
7.有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。
B
解析 B选项先出队后入队,队列中为1,2,3,再依次入栈,出栈的顺序为3,2,1。
9.假设高铁站的售票窗口平均每分钟过来一个人购票,每人的购票时间平均约为2分钟,某车站在中午时段开了一个售票窗口,12:01:00的时候有1个人刚开始购票,3个人在等待,那么12:11:00时队伍中等待购票的人数为(  )
A.7 B.8 C.9 D.10
C
解析 根据题目描述,10分钟过来了10个人购票,总共14人,其间4人结束购票,所以队伍还有10人,1人在购票,9人在等待。
B
解析 本题考查队列的入队与出队操作。字符串S中两个字符为一组,第1个元素t代表入队或出队,第2个元素代表n入队或出队的次数。A是入队,D是出队,若出队过程中队空,则中止出队。
B
解析 本题考查队列的基本操作。程序的功能是查找队列中最小值,pre初值为10,每次出队一个元素,出队元素也pre比较,记录其最小值的过程。
执行该程序段后,显示的结果是(  )
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出队。
B
解析 本题考查队列的基本操作。当i的值为2,3,5时,i均不在队列中,因此入列3次,tail=3,当i的值为1时,条件tail-head==3成立,因此进行出队(队首指向2)操作,队列中值依次为[3, 5],当i的值为3,5,不符合条件,当i的值为2时,入队。
解析 遍历数组a并累加数组元素值,求队列的最大值;当遍历到的当前值小于队首或是长度大于k,将队首元素出队。s的值依次为[3,6,10]=19,[6,10,5]=21,[5,9]=14,[5,9,4]=18。
C
执行该程序段后,输出的结果是(  )
A.bdfyac B.bdfxyz
C.abcyac D.yacbdf
A
解析 本题考查队列的相关操作。表达式(ord(i) - ord(″a″) + q[head]) % 26 的功能是将i转换为在字母表中索引位置,并循环后移q[head]个位置。计算出移动位置后,再转换为小写字母。q中元素实现出队后再入队,因此分别将a、b、c和x、y、z对应位置字母后称1、2、3位置。
运行该程序段后,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不可能产生。
B
解析 循环5次,每次循环有3种可能,一是当i为偶数时,入队一个[1,9] 之间的整数要么,二是当i为奇数时,且q[tail-1]C
解析 若队列中数据元素小于2或者t的值为0,则将a[i]入队,否则当a[i]大于c[head]时出队,a中元素既可以不入队,也可以不出队(t为1,且a[i]小于等于c[head])。A选项8,10入队,2和7可以不入队,11让8出队,队列中只剩下1个元素,9入队,接着t的值为0,16入队。B选项8,10入队后,接着t的值依次为1,1,0,0,0。C选项队首为8,当遍历到11时,要么让8出队,要么产生的t为0,11入队,因此C不可能。D选项11让队首8出队,当遍历到16时,产生的t为0,16入队。
C
B
解析 本题考查队列的性质。语句q[tail]=q[head]表示将队首出队,再入队,中间也可能有元素出队,最后输出队列中元素。队列的特性是先进先出,无论有多少元素全部出队后,部分数据再入队,在队列的位置还是按原来的次序排列,因此选项B不可能。
B
解析 程序功能是利用队列将栈中的元素进行升序排列。若栈不为空,当队首元素大于栈顶元素的值时,将栈中元素入队并出栈,否则将队首元素入栈并将队首进行出队操作。

展开更多......

收起↑

资源列表