资源简介

专题13　队　列
知识点一　队列的性质
1.在该系统中，可以利用队列来储存当前正在排队顾客的编号，head指向队首元素，tail指向队尾元素的下一个位置，若tail＝head＋3，则现在排队的顾客数量为(　　)
A.2 B.3
C.4 D.5
2.约定：T操作是指在队列中1个元素出队后再入队，E操作是指将1个元素入队，P操作是指队列中1个元素出队，队首指针head和队尾指针tail初始值均为0。则经过EETPETEP系列操作后，队首指针head和队尾指针tail的值分别为(　　)
A.3　4 B.3　5
C.4　5 D.4　6
3.有1个队列，队首到队尾的元素依次为8，10，12，9。若队首元素是偶数则先出队，再将偶数整除2后重新入队，若队首元素是奇数，直接出队。入队或出队各算一次操作，经过6次操作后，队列中队首到队尾的元素依次为(　　)
A.2，3 B.6，2，3
C.9，4，5 D.9，4，5，6
4.已知队列元素的个数为5，则队首指针head和队尾指针tail的值不可能是(　　)
A.head＝1，tail＝6 B.head＝2，tail＝6
C.head＝5，tail＝0 D.head＝3，tail＝2
5.假设队列的空间足够，队首指针head和队尾指针tail经过“出队、入队、出队、出队、入队、入队、出队”这一系列操作后，head＝7，tail＝9。则操作前的head和tail的值分别为(　　)
A.11　12 B.2　5
C.3　6 D.3　5
6.某队列的数据结构如图所示，head和tail分别是队列的头指针和尾指针。
现对该队列进行下列操作：①队首元素出队后再入队；②队首元素出队并输出，重复①②操作直到队列为空。若队列的数据元素为“Python”，则输出的顺序是(　　)
A.Python B.Ptoynh
C.yhntPo D.yhntoP
7.假设高铁站的售票窗口平均每分钟过来一个人购票，每人的购票时间平均约为2分钟，某车站在中午时段开了一个售票窗口，12：01：00的时候有1个人刚开始购票，3个人在等待，那么12：11：00时队伍中等待购票的人数为(　　)
A.7 B.8
C.9 D.10
知识点二　队列的算法实现
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.有如下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
3.执行如下程序段后，输出的结果是(　　)
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
4.使用Python自带的队列模块queue可以更便捷地实现队列的操作，代码如下：
import queue
q＝queue.Queue(5)
q.put(″A″)　#字符A入队
q.put(″B″)
q.put(″C″)
已知get函数可以按照队列特性出队，若要使字符“C”从队列q中出队正确的方法是(　　)
A.直接使用语句q.get(″C″)
B.直接使用语句q.get()
C.使用两次语句q.get()
D.使用三次语句q.get()
5.有如下Python程序段：
q＝[chr(i) for i in range(65，70)]
ans＝″″
head，tail＝0，len(q)
while headans＝ans＋q[head]
head＋＝1
if headq＋＝q[head]
tail＋＝1
head＋＝1
print(ans)
执行该程序段后，输出的ans值为(　　)
A.ABCDE B.ACEDB
C.ADCEB D.EDCAB
6.有如下Python程序段：
import random
q＝[1]*12；s＝0
head＝0；tail＝1
k＝random.randint(1，5)
while k>0：
q[tail]＝q[head]*2
tail＋＝1
q[tail]＝q[head]*2＋1
tail＋＝1；head＋＝1；k－＝1
while heads＋＝q[head]
head＋＝1
执行该程序段后，s的值不可能的是(　　)
A.7 B.22
C.35 D.51
7.有如下Python程序：
s＝input()
sq＝[″″]*100
head＝tail＝0
flag，res＝True，″″
for i in range(len(s))：
if s[i]＝＝″－″：
while head ！＝tail：
　　　 　res＋＝sq[head]
　　　 　head＝head＋1
　　 　　if flag：
　　　　 　　sq[tail]＝sq[head]
　　　　　 　tail，head＝tail＋1，head＋1
　　　　 flag＝not flag
else：
sq[tail]＝s[i]
tail＝tail＋1
如输入的s为″Python－2023－″，执行该程序，则变量res的值为(　　)
A.″Pthnyo2230″ B.″Ptoynh2203″
C.″tPyhno2302″ D.″yPntho2023″
8.有如下Python程序段：
lst＝[5，9，2，6，4，7，3，0]
que＝[0]*len(lst)
head＝tail＝0
i＝0
while iif lst[i] %2＝＝0：
que[tail]＝lst.pop(i)
#lst.pop(i)删除列表1st中索引为i的元素，返回删除的元素
tail＋＝1
else：
i＋＝1
while head ！＝tail：
lst.append(que[head])
head＋＝1
执行该程序段后，lst 的值为(　　)
A.[5，9，7，3，2，6，4，0] B.[5，9，7，3，0，4，6，2]
C.[2，6，4，0，5，9，7，3] D.[3，7，9，5，0，4，6，2]
9.有如下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]
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＝[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]
12.n位志愿者分别来自5所学校，用1－5对每所学校志愿者进行编号，按报名参加志愿服务的先后顺序依次存入数组s，对应的姓名分别存入数组xm中。组委会从中选择若干名志愿者，要求每个报名的学校至少包含1名志愿者，且满足条件的志愿者人数最少，输出区间内的志愿者名单。部分代码如下：
#读取全体志愿者编号到数组s中，并输出，代码略
head＝0；tail＝0
minn＝len(s)；ta＝0
while tailtail＋＝1
if tail！＝1 and s[tail－1]＝＝s[head]：　#①
head＋＝1
②________：
head＋＝1
p＝head
③________
while ptotn[p]＝＋1　#④
p＋＝1
if sum(totn)＝＝5：　# sum(totn)统计totn列表中所有元素之和
if tail－head　　 　　minn＝tail－head
　　 　　ta＝head
下列关于程序代码的完善和修改，说法正确的是(　　)
A.①处语句修改为if s[tail－1]＝＝s[head]：，功能不变
B.②处语句应为if s[head]＝＝s[head＋1]
C.③处语句应为totn＝[0]*5
D.④处语句修改为totn[s[p]]＝1
13.某城市规模较小，人口流动量不大，通常两个完全不认识的陌生人通过2－3个亲戚或朋友的牵线搭桥就可以建立联系。王老师建立了一种人际关系矩阵来模拟这种现象，如图所示有甲、乙、丙、丁、戊、己、庚、辛8人，分别用1－8进行编号，相互之间认识，在矩阵中用1表示；相互之间不认识，在矩阵中用0表示；对于自身，用0表示，即矩阵左上角到右下角的对角线全为0。当前甲和乙不认识，只需通过2人(辛和丁)牵线即可建立联系。程序运行的效果如图所示：
(1)实现上述功能的Python程序如下，请在划线处填入合适的代码。
(2)程序中加框处代码有错，请改正。
#列表a用于存储联系是否是朋友的关系
n＝8　#人员数量
p1＝int(input(″输入第1个联系人编号：″))－1
p2＝int(input(″输入第2个联系人编号：″))－1
b＝[0]*n；b[0]＝p1　#存储访问过的联系人列表
ren＝[0]*n　#从p1开始访问过的联系人人数
head＝0；tail＝1
find＝[False]*n
find[p1]＝True
lxr＝[0]*n　#上一个访问的联系人
while not find[p2]：
①________
for i in range(n)：
if a[cur][i]＝＝1 and find[i]＝＝False：
　　　 　b[tail]＝i
　　　　　　tail＋＝1
　　　　 find[i]＝True
　　　 　②________
　　　 　lxr[i]＝cur
head＋＝1
if head＝＝tail：
break
if ③__________：
print(″需要″＋str(ren[p2]－1)＋″个介绍人″)
else：
print(″无法建立联系″)
p＝p2；s＝″″
while ：
s＝str(lxr[p]＋1)＋″，″＋s
p＝lxr[p]
print(″依次访问的联系人为：″＋s＋str(p2＋1))
14.题目要求同题13，现找出所有的联系人路径，程序运行的结果如图所示：
输入第1个联系人编号：1 输入第2个联系人编号：2 路径：1，5，8，3，4，2 路径：1，5，8，3，4，6，7，2
实现上述功能的Python程序如下，请在划线处填入合适的代码。
#列表a用于存储联系是否是朋友的关系
n＝8　#人员数量
p1＝int(input(″输入第1个联系人编号：″))－1
p2＝int(input(″输入第2个联系人编号：″))－1
b＝[0]*n；ren＝[0]*n
b[0]＝p1
head＝0；tail＝1
find＝[False]*n
find[p1]＝True
lxr＝[″″]*n
lxr[p1]＝str(b[head]＋1)＋″，″
while ①________：
cur＝b[head]
for i in range(n)：
if a[cur][i]＝＝1 and not find[i]：
　 　　　if ②________：
　　　　　 　print(″路径：″＋lxr[cur]＋str(p2＋1))
　　　　 else：
　　　　　 　b[tail]＝i
　　　　 　　tail＋＝1
　　　　 　　find[i]＝True
　　 　　　　ren[i]＝ren[cur]＋1
③________
if head！＝tail：
lxr[b[head]]＝lxr[b[head－1]]＋str(b[head]＋1)＋″，″
专题13　队　列
知识点一
1.B　[队列的长度计算公式为tail－head，因此队列中有3人排队。]
2.D　[本题考查队列的基本操作。T操作既有入队，又有出队，因此共有6次入队，4次出队，每次出队和入队，指针分别加1。]
3.D　[本题考查队列性质和操作。根据队列的特点“先进先出，后进后出”，8出队后4入队(2 次)，10 出队后5入队(2 次)，12 出队后6入队(2 次)。共 6 次，其结果为 9，4，5，6。]
4.B　[本题队列的相关概念。队列的元素计算公式为(tail－head＋n)%n，其中n是队列存储空间。B选项head＝2，tail＝6，长度是4。]
5.C　[本题考查队列的性质。入队3次，出队4次，在3次入队前tail应为6，在4次出队前head应为3。]
6.C　[题目中队列的元素执行队首元素出队，再从队尾入队，接下来队首元素出队并输出，直至队列空，输出的顺序为C选项结果。]
7.C　[根据题目描述，10分钟过来了10个人购票，总共14人，期间4人结束购票，所以队伍还有10人，1人在购票，9人在等待。]
知识点二
1.B　[本题考查队列的入队与出队操作。字符串S中两个字符为一组，第1个元素t代表入队或出队，第2个元素代表n入队或出队的次数。A是入队，D是出队，若出队过程中队空，则中止出队。]
2.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出队。]
3.B　[本题考查队列的基本操作。程序的功能是查找队列中最小值，pre初值为10，每次出队一个元素，出队元素也pre比较，记录其最小值的过程。]
4.D　[本题考查队列类实现。题中所给代码实现了字符“A”“B”“C”依次入队，要让字符“C”出队，根据队列先进先出的特性，应执行三次出队操作。]
5.B　[本题主要考查队列的应用。程序实现的功能是：当队不为空时，先出队一个元素，再将队首放在队尾，并再次出队一个元素。]
6.A　[本题考查随机数和队列及其代码实现知识。变量k是1～5之间的整数，表示循环次数。每次将头首乘以2和乘以2加1的2个数入队，并将队首出队。变量s将队列中的数据进行求和。]
7.A　[本题考查队列的应用。遍历到'－'字符，队列中的元素按照一定的规则出队，否则字符入队。第1个出队的元素一定是P，此时flag值为True，字符'y'重新进入队尾。接下来't'出队，flag值为False，依此类推。]
8.A　[本题考查队列和列表的相关知识。根据题意可知，que当中追加的是lst中从前向后遍历偶数值，且把该偶数从lst中删除，最后将que中的偶数追加到lst后面，所以该程序段实现的是提取lst中的偶数放置末尾。]
9.D　[本题队列的基本操作。入队的条件是产生的随机数为0，出队的条件是队不空且队尾元素比较队首元素小。A选项产生随机数均为1，没有任何元素入队。B选项依次入队过程中，队尾元素大于队尾元素值。C选项队列中只有3个元素，先产生8，5，再进行出队和入队，最后再产生3，循环了4次，还有一次产生的随机数为1，不做任何操作。D选项只要有元素入队，第一个元素不可能为0。]
10.B　[本题考查队列的性质。语句q[tail]＝q[head]表示将队首出队，再入队，中间也可能有元素出队，最后输出队列中元素。队列的特性是先进先出，无论有多少元素全部出队后，部分数据再入队，在队列的位置还是按原来的次序排列，因此选项B不可能。]
11.B　[本题考查队列的基本操作。当i的值为2，3，5时，i均不在队列中，因此入列3次，tail＝3，当i的值为1时，条件tail－head＝＝3成立，因此进行出队(队首指向2)操作，队列中值依次为[3，5]，当i的值为3，5，不符合条件，当i的值为2时，入队。]
12.D　[本题考查队列的基本操作。A选项本语句块的功能是当队尾入队一个元素后，入队的值与队首相同，则队首出队一个元素，当tail＝1时，队列中只有一个元素，条件成立，形成死循环，因此必须判断tail不等于1。B选项出队后，新的队首后面可能存在多个与队首相同的元素，因此必须要采用循环结构。使其不断地出队。C选项totn用于存储1－5各个序号的数量，语句totn＝[0]*5预设最大的下标元素为totn[4]，应为totn＝[0]*6。D选项p是下标，要统计的是s[p]的值，sum(totn)统计totn列表中所有元素之和，不管某个编号出现多少次，该编号的统计值为1，表示出现过，0表示未出现过。]
13.(1)①cur＝b[head]　②ren[i]＝ren[cur]＋1 ③find[p2]　(2)p！＝p1
解析　本题考查队列和链表的基本操作。(1)b数组存储访问过的联系人列表，语句b[0]＝p1表示从队首开始遍历队列，下方用到a[cur][i]＝＝1，因此需对cur进行赋值。ren＝[0]*n#从p1开始访问过的联系人人数，从输出语句print(″需要″＋str(ren[p2]－1)＋″个介绍人″)，因此第i个人访问是在当前访问次数加1。③空比较简单，当找到find[p2]为真，可以输出。(2)此次考查链表操作，p的初值为p2，p作为数组lxr中的下标，访问lxr[p]的值，然后把lxr[p]作为新的下标，依次向前访问，当访问到p1时结束访问，如数组lxr的值依次为[0，3，4，7，0，7，7，0]，p＝1，lxr[1]＝3，p＝3，lxr[3]＝4，p＝4，lxr[4]＝0，而要访问的p1就是0号索引，因此须修改为p！＝p1。
14.①head！＝tail　②i＝＝p2　③head＋＝1
解析　本题考查队列的基本操作。①由于要查找所有路径，因此把b数组看成队列，当队列中没有数据时，结束遍历，因此条件是head！＝tail。②print(″路径：″＋lxr[cur]＋str(p2＋1))，输出一条路径，因此必须是找到了，即i＝＝p2。③遍历完一个数据，要对该数据进行出队操作。

展开更多......

收起↑