浙教版（2019）选修一3.2队列同步练习（含答案）

浙教版（2019）选修一3.2队列同步练习
学校:___________姓名：___________班级：___________考号：___________
一、选择题
1．有1个队列，队首到队尾的元素依次为a，b，c，d，e。约定：T操作是指队列中1个元素出队后再入队，Q操作是指队列中1个元素出队。则经过TTTQTTQ系列操作后，队列中队首到队尾的元素依次为（ ）
A．b，d，e B．b，e，c C．c，e，a D．a，c，b
2．一个队列的数据入队序列是1,2,3,4，则该队列的出队序列是（ ）
A．4,3,2,1 B．1,2,3,4 C．1,4,3,2 D．3,2,4,1
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个队列，队首到队尾的元素依次为8,10,12,9。若队首元素是偶数则先出队，再将偶数整除2后重新入队，若队首元素是奇数，直接出队。入队或出队各算一次操作，经过6次操作后，队列中队首到队尾的元素依次为（ ）
A．2,3 B．6,2,3 C．9,4,5 D．9,4,5,6
5．下列有关队列的说法正确的是（ ）
A．队列是一种先进先出的线性表，插入一端为队首，删除一端称队尾
B．队列的存储结构，可用数组实现，也可用链表实现
C．一队列队头指针head，队尾指针tail，则tail-1-head表示队列中元素个数
D．学生排队就餐与软件连续撤消操作都是数据结构“队列”的应用实例
6．有如下Python程序段：
st = [″h″,″a″,″p″,″*″,″p″,″Y″]
que = [0]*20; key = 2
head,tail = 0, 0
for i in range (len(st)):
if ″a″ <= st[i] <= ″z″:
que[tail] = chr((ord(st[i]) - ord(″a″) + key)%26 + ord(″a″))
tail += 1
else:
head += 1
while head != tail:
print (que[head],end =″ ″)
head += 1
程序运行后，输出的结果是（ ）
A．r r B．p p C．c r r a D．c r r A
7．有1个队列，现有元素依次为1，2，3，4。约定：P操作是指1个入队，T操作是指队列中1个元素出队后再入队，Q操作是指队列中1个元素出队。则经过PPTQTPQ系列操作后，队列中队首到队尾的元素依次为（ ）
A．1 B．1，3 C．3，4 D．3
8．列表a长度为6，a[0]至a[5]值依次为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[head]:
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
9．某队列经过“出队”“入队”操作后，队首指针head=2，队尾指针tail=6，则该队列中剩余的元素个数是（ ）
A．2 B．4 C．5 D．6
10．有以下Python程序段：
import random
k=10;que=[0]*2*k
que[0]=random.randint(1,20)
head=0;tail=1;i=1
while i a=random.randint(1,20)
if a%2!=que[tail-1]%2:
que[tail]=a
tail=tail+1
elif a%2!=que[head]%2:
que[tail]=que[head]
que[tail+1]=a
tail=tail+2
head=head+1
i=i+1
print(que[head:tail])
运行该程序段后，输出结果不可能的是（ ）
A．[20,1,10,5,4] B．[14,17,10,3,12] C．[5,16,5,4,13,20,11] D．[13,10,5,16,19,10,20]
11．有如下Python程序段：
a="Python"；q=[0]*6
head,tail=0,0
i=len（a）-1
while i>=0:
if i%3!=0:
q[tail]=a[i]
else:
q[tail]=q[head]
head+=1
tail+=1
i-=1
print（q[head:tail]）
当执行该程序段后，输出的结果是（ ）
A．['n','t','y','o'] B．['n','t','y'] C．['n','o','n','t','y'] D．['n','o','n','t','y','o']
12．假设队列的空间足够，队首指针head和队尾指针tail经过“出队、入队、出队、出队、入队、入队、出队”这一系列操作后，head=7，tail=9。则操作前的head和tail的值分别为（ ）
A．11 12 B．2 5 C．3 6 D．3 5
13．某种特殊的队列Q，支持以下三个操作：
操作Q1：若队列非空，队首元素出队，并输出；
操作Q2：若队列非空，队首元素出队；
操作Q3：一个元素入队；
以上任意一种操作后，若队列非空，新的队首元素仍为队列中所有元素的最小值。
若队列Q初始状态为空，依次进行Q3、Q2、Q1、Q2、Q3、Q1、Q3七次操作后，下列说法正确的是（ ）
A．当前队列中的元素个数为2
B．输出的元素个数为2
C．第一个输出的元素肯定比当前队首元素大
D．队列初始状态是否为空对输出结果有影响
14．下列关于队列的描述中，正确的是（ ）
A．在队列中只能删除数据 B．队列是先进后出的线性表 C．在队列中只能插入数据 D．队列是先进先出的线性表
15．已知队列元素的的个数为5，则队首指针head和队尾指针tail的值不可能是（　　）
A．head=1,tail=6 B．head=2,tail=6 C．head=5,tail=0 D．head=3,tail=2
试卷第1页，共3页
试卷第1页，共3页
参考答案：
1．C
【详解】本题考查的是队列操作。根据题意得知队首到队尾经过TTT操作后，原队列变为d，e，a，b，c，经过Q操作队列变为e，a，b，c，再经过TT操作变为b，c，e，a，最后经过Q操作变为c，e，a，故选项C为正确答案。
2．B
【详解】本题考查队列相关内容。队列的特点是：先进先出，其入队序列是1,2,3,4，则该队列的出队序列是1,2,3,4。故本题答案是B选项。
3．D
【详解】本题考查队列操作相关内容。根据题目规定，T表示出队后入队，E表示入队，P表示出队，操作过程中指针变化情况如下所示：
操作序列EETPETEP 队列中指针初值head=tail=0
EETPETEP head=0;tail=1
EETPETEP head=0;tail=2
EETPETEP head=1;tail=3
EETPETEP head=2;tail=3
EETPETEP head=2;tail=4
EETPETEP head=3;tail=5
EETPETEP head=3;tail=6
EETPETEP head=4;tail=6
此队列共进行入队6次，出队4次，入队移动队尾指针及tail+6，出队移动head指针，即head+4，执行EETPETEP后（E入队，T（出队+入队），P出队）head=4，tail=6，故本题答案为D选项。
4．D
【详解】本题考查队列相关内容。队列的特点是先进先出。队首到队尾的元素依次为8、10、12、9。第一次操作8出队，第二次操作8//2的结果4入队，第三次操作10出队，第四次操作10//2的结果5入队，第五次操作12出队，第六次操作12//2的结果6入队，故此时队列中的元素依次为9、4、5、6，D选项正确。故本题答案是D选项。
5．B
【详解】本题考查队列。A选项错误，插入端是队尾，删除端是队首。B选项正确，存储队列可以用顺序存储（数组）也可以链式（链表）存储。C选项错误，队列中元素个数表达式为tail-head。D选项错误，软件中的撤销操作和栈的操作相关。故答案为：B。
6．A
【详解】本题考查的是队列。阅读程序可知程序功能：遍历st列表，遇到小写字符则将其后移key位，再入队tail+1；遇到其他字符则出队head+1，最后输出队列里的元素。在列表st = ["h","a","p","**,"p","Y"]中，字符后移2位则变成 ["j","c","r","*","r","Y"]。遇到"*"出队一次，遇到"Y"出队一次，最后队列里的元素为rr，故答案选A。
7．D
【详解】本题考查数据结构队列相关内容。依据队列先进先出的特点，模拟其出队入队操作，如图所示：，经过PPTQTPQ系列操作后，队列中仅有元素3。故本题答案是D选项。
8．B
【详解】本题考查的是队列操作。阅读程序可知，程序依次将列表a插入队列que中，如果列表a的值大于队尾，则查入队列，队头出列；如果比队头小，则查入队列。a[0]至a[5]值依次为4，2，5，1，9。
a[0]=4，将4插入队列，队列依次为：4；
a[1]=2，满足比队头小，2插入队列，队列依次为：4，2；
a[2]=5，满足大于队尾，5入队，4出队，队列依次为：2，5；
a[3]=1，满足比队头小，1插入队列，队列依次为：2，5，1；
a[4]=9，满足大于队尾，9入队，2出队，队列依次为：5，1，9；
故本题应选B。
9．B
【详解】本题考查队列相关内容。队首指针指向队首元素，队尾指针指向队尾元素的下一个位置，则队首元素位置是2，队尾元素位置是5，共有5-2+1=4个元素。故本题答案是B选项。
10．D
【详解】队列本题考查的知识点是本题考查的知识点是队列的相关知识。该程序段是一个简单的模拟程序，它使用一个循环来生成一系列随机整数，并将这些整数存储在一个队列中，同时保证队列中相邻的数字的奇偶性不同。程序首先生成一个长度为2k的队列，并将第一个元素设置为一个随机整数。然后，程序进入一个循环，该循环将生成k个随机整数，并将它们插入到队列中。在每次迭代中，程序会生成一个新的随机整数a，并检查它与队列中最后一个元素以及第一个元素是否具有相同的奇偶性。如果a与最后一个元素的奇偶性不同，则将a插入到队列的末尾。如果a与第一个元素的奇偶性不同，则将a插入到第一个元素之前，并将第一个元素移动到队列的末尾。通过这种方式，程序确保队列中相邻元素的奇偶性不同，A、B、C选项有可能。故答案为D选项。
11．A
【详解】本题考查的是队列应用。阅读程序可知，可以将q看成一个队列，将字符串a从后往前依次进入队列q。字符串索引是3的倍数时，则将队列q的队头排到队尾。a="Python"，i值为5、4时，依次入队['n','0']；i值为3时，队头排到队尾['0','n']；i值为2、1时，依次入队['0','n'，'t','y']；i值为0时，队头排到队尾['n','t','y','0']。故本题应选A。
12．C
【详解】本题考查队列的操作。队首指针head和队尾指针tail经过“出队、入队、出队、出队、入队、入队、出队”这一系列操作后，共出队4次，入队3次，所以head+4=7，tail+3=9，得到操作前的head和tail的值分别为3、6，所以选项C符合题意。故选：C。
13．D
【详解】本题考查的是队列操作。队列是先进先出。当前队列中的元素个数为1；第一次Q1，由于队列为空，没有输出，第二次Q1，有输出，输出元素1个；无法判断第一个输出的元素比当前队首元素大。故本题应选D。
14．D
【详解】本题主要考查队列的描述。队列是先进先出的线性表，在队尾插入数据，队首删除数据，故本题选D选项。
15．B
【详解】本题主要考查队列数据结构。head=2，tail=6，则队列元素的个数为6-2=4，故本题选B选项。
答案第1页，共2页
答案第1页，共2页