3.2 队列 知识点复习 浙教版（2019）选修一

3.2 队列 一、选择题 1．假设队列的空间足够，队首指针head和队尾指针tail经过“出队、入队、出队、出队、入队、入队、出队”这一系列操作后，head=7，tail=9。则操作前的head和tail的值分别为（   ） A．11  12 B．2  5 C．3  6 D．3  5 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．有一个非循环队列S如图所示，其中指针head指向队首元素的位置，指针tail指向队尾元素的下一个位置。 关于该队列说法正确的是（    ） A．队列中元素个数为tail-head+1 B．新元素入队时，指针head向右移动 C．元素出队时，指针tail向右移动 D．当tail==len（S）时，无法再入队新元素 4．队列q中队首至队尾元素依次为“A，B，C，D，E，F”，约定：S为出队操作，U为出队再入队操作，若要使队列q队首至队尾元素依次为“B，D，E”，下列操作可实现的是（    ） A．USUSSU B．SUSUUS C．SSSUUU D．SUUSUS 5．某种特殊的队列Q，支持以下三个操作： 操作Q1：若队列非空，队首元素出队，并输出； 操作Q2：若队列非空，队首元素出队； 操作Q3：一个元素入队； 以上任意一种操作后，若队列非空，新的队首元素仍为队列中所有元素的最小值。 若队列Q初始状态为空，依次进行Q3、Q2、Q1、Q2、Q3、Q1、Q3七次操作后，下列说法正确的是（    ） A．当前队列中的元素个数为2 B．输出的元素个数为2 C．第一个输出的元素肯定比当前队首元素大 D．队列初始状态是否为空对输出结果有影响 6．下列场景中蕴含的数据结构思想与图一致的是（　　） 图一：排队做核酸 A．Excel执行撤销操作 B．编号不重复的名单 C．寻宝游戏路线 D．打印机任务面板 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．在日常幻灯片的放映中，可以通过超级链接方式进行幻灯片之间的任意跳转。和这种跳转方式相似的数据结构是（　　） A．数 B．链表 C．队列 D．栈 9．有如下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 10．某队列当前队首指针head=2，队尾指针tail=5，在不考虑队列溢出的情况下，进行如下操作：入队、入队、出队、出队、入队，队列中剩余的元素个数为（   ） A．7 B．5 C．4 D．3 11．某队列中存有12张扑克牌，如题图所示，游戏规则如下：①取队首扑克牌，然后加入到队尾，②打出队首扑克牌；重复①、②两个操作，直到队列为空。 若要根据上述规则用扑克牌打出“一条龙”游戏（注：总共13张牌，从队列中出牌的次序为“A2345678910JQK” ）。请你设计游戏，将扑克牌“10”放到初始队列中正确的位置（    ） A．放置在扑克牌6的后面 B．放置在扑克牌5与扑克牌K之间 C．放置在扑克牌2与扑克牌8之间 D．以上说法均错误 12．有1个队列，现有元素依次为1，2，3，4。约定：P操作是指1个入队，T操作是指队列中1个元素出队后再入队，Q操作是指队列中1个元素出队。则经过PPTQTPQ系列操作后，队列中队首到队尾的元素依次为（    ） A．1 B．1，3 C．3，4 D．3 13．有如下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 for i in range(len(s)): print(que[head],end="") head=head+1 以上程序运行后，打印出列表的情况是：（    ） A．ABCDEF B．FEDCBA C．ACEFDB D．AFCDEB 14．队列Q和栈S的初始值均为空，数字入栈先后顺序为1、2、3、4、5。P表示入栈，T表示元素出栈以后入队。在进行PPTTPPTPT操作后，队列中从队首到队尾的元素依次为（   ） A．2、1、3、4 B．2、1、4、5 C．1、2、4、5 D．2、1、4、3 15．操作Q为出队，R为入队，T为出队后入队，则序列1，2，3，4，5，按照操作顺序RRRTQRQR进行操作后，队列中的数字依次为（    ） A．1 4 5 B．2 3 5 C．1 3 5 D．2 4 5 16．某诊所叫号系统中，利用队列来储存当前正在排队病人的编号，head指向队首元素，tail指向队尾元素的下一个位置。若当前没有病人，则head与tail的关系是（   ） A．head!=tail B．head>tail C．head==tail D．head<tail 17．下列对队列的描述，正确的是（   ） A．队列的特点是先进后出 B．在队列中，允许插入的一端称为队首，允许删除的一端称为队尾 C．刚建立的队列，队首指针和队尾指针均为0 D．出队操作时，先将队首指针加1，然后再将队首元素出队 18．以下有关栈和队列的说法正确的是（    ） A．栈和队列都是先进后出 B．栈和队列都是先进先出 C．队列元素前面只有一个，后面有多个 D．栈和队列只允许在端点插入和删除数据 19．“餐厅信息管理系统”由菜品管理、订单管理和客户管理三个模块组成。订单管理模块可以实现顾客点餐、订单结算和订单统计的功能。餐厅的碗碟都已植入了电子标签，在系统中可设定每个电子标签对应的菜品。顾客将选好菜品的托盘放入结算台，结算台读取电子标签信息，系统自动完成结算，顾客在刷卡区完成结算。在该系统中，可以利用队列来储存当前正在排队顾客的编号，head 指向队首元素，tail指向队尾元素的下一个位置，若 tail=head+3，则现在排队的顾客数量为 (　　) A．2 B．3 C．4 D．5 20．约定：T操作是指在队列中1个元素出队后再入队，E操作是指将1个元素入队，P操作是指队列中1个元素出队，队首指针head和队尾指针tail初始值均为0。则经过EETPETEP 系列操作后，队首指针head和队尾指针tail的值分别为（   ） A．3 4 B．3 5 C．4 5 D．4 6 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．C 【详解】本题考查队列的操作。队首指针head和队尾指针tail经过“出队、入队、出队、出队、入队、入队、出队”这一系列操作后，共出队4次，入队3次，所以head+4=7，tail+3=9，得到操作前的head和tail的值分别为3、6，所以选项C符合题意。故选：C。 2．B 【详解】本题考查队列相关内容。队列的特点是：先进先出，其入队序列是1,2,3,4，则该队列的出队序列是1,2,3,4。故本题答案是B选项。 3．D 【详解】本题主要考查队列数据结构。由图可知，队列中元素个数为tail-head；新元素入队时，指针tail向右移动；元素出队时，指针tail向左移动； 当tail==len（S）时，无法再入队新元素，故本题选D选项。 4．B 【详解】本题考查队列的操作。S为出队操作，U为出队再入队操作，选项操作后依次为：“A，C，F”、“B，D，E”、“D，E，F”、“B、C、E”。故选B。 5．D 【详解】本题考查的是队列操作。队列是先进先出。当前队列中的元素个数为1；第一次Q1，由于队列为空，没有输出，第二次Q1，有输出，输出元素1个；无法判断第一个输出的元素比当前队首元素大。故本题应选D。 6．D 【详解】本题考查数据结构。排队做核酸与数据结构中的队列有关，队列是一种先进先出（FIFO）的数据结构，它适用于需要按照顺序处理和排队等待的场景。在排队做核酸测试时，人们需要按照先来后到的顺序进行核酸检测，这就是典型的队列操作。从给出的选项中，只有打印机任务面板与队列操作相关。在打印机任务面板中，打印任务通常会排队等待打印，先提交的任务会先被处理，这也是队列的典型应用。故答案为D选项。 7．C 【详解】本题考查的是队列操作。队列是先进先出，T操作是指队列中1个元素出队后再入队，Q操作是指队列中1个元素出队，队首到队尾的元素依次为1，2，3，4，5。经过TT后，队首到队尾的元素依次为4，5，1，2，3；经过Q后，队首到队尾的元素依次为4，5，1，2；经过TT后，队首到队尾的元素依次为1，2，4，5；经过Q后，队首到队尾的元素依次为1，2，4；经过TT后，队首到队尾的元素依次为2，4，1；经过Q后，队首到队尾的元素依次为2，4。选项C正确。 8．B 【详解】本题考查的是对数据结构的理解。链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。链表由一系列数据结点构成，每个数据结点包括数据域和指针域两部分。其中，指针域保存了数据结构中下一个元素存放的地址。链表结构中数据元素的逻辑顺序是通过链表中的指针链接次序来实现的。故选项B正确。 9．A 【详解】本题考查的是队列。阅读程序可知程序功能：遍历st列表，遇到小写字符则将其后移key位，再入队tail+1；遇到其他字符则出队head+1，最后输出队列里的元素。在列表st = ["h","a","p","**,"p","Y"]中，字符后移2位则变成 ["j","c","r","*","r","Y"]。遇到"*"出队一次，遇到"Y"出队一次，最后队列里的元素为rr，故答案选A。 10．B 【详解】本题考查数据结构队列操作相关内容。队首指针指向队首元素，队尾指针指向队尾元素的下一个位置，则队首元素位置是2，队尾元素位置是5，则目前队列中共有5-2+1=4个元素。先执行两次入队操作，则队列中元素有6个（4+2），接着执行两次出队操作，则队列中元素有4个（6-2），最后一次执行入队操作，则队列中元素有5个（4+1）。故本题答案是B选项。 11．A 【详解】本题考查队列相关内容。按照游戏规则，以A选项为例，队列中扑克牌出队入队情况如图所示：。A选项可以得出“一条龙”，采用同样的方法，BC选项不能得到“一条龙”，故本题答案是A选项。 12．D 【详解】本题考查数据结构队列相关内容。依据队列先进先出的特点，模拟其出队入队操作，如图所示：，经过PPTQTPQ系列操作后，队列中仅有元素3。故本题答案是D选项。 13．D 【详解】本题主要考查Python程序的执行。分析程序可知，该程序模拟队列数据类型，如果i是偶数，则将s[i]入队列que[tail]，如果i是奇数，则将s[len(s)-i]入队列que[tail]，第一个for循环执行完，队列中的元素是“AFCDEB”，第二个for循环按照队列“先进先出”的规则依次出队，故以上程序运行后，打印出列表的情况是：AFCDEB，故本题选D选项。 14．B 【详解】本题考查队列和栈。根据操作规则，数字先入栈，然后出栈后入队。按照给定的操作序列PPTTPPTPT，首先数字1入栈，接着2入栈，然后2出栈入队，接着1出栈入队，然后3入栈，接着4入栈，接着4出栈入队，接着5入栈，然后5出栈入队，依次类推。最终队列中从队首到队尾的元素依次为2、1、4、5。故答案为：B。 15．A 【详解】本题主要考查队列的操作。按照操作顺序RRRTQRQR进行操作，首先1、2、3入队，再1出队再入队，此时队列元素是2、3、1，接着2出队4入队，此时队列元素是3、1、4，最后3出队5入队，此时队列中的数字依次为1、4、5，故本题选A选项。 16．C 【详解】本题考查队列。head、tail分别是队首和队尾指针，当队列为空时，指针head和tail指向同一个位置，即head==tail。故答案为：C。 17．C 【详解】本题考查队列。队列的特点是先进先出，因此A选项错误；允许插入的一端称为队尾，允许删除的一端称为队首，因此B选项错误；刚建立的队列，队首指针和队尾指针均指向下标为0的元素，即队首指针和队尾指针均为0，C选项正确；出队操作时，先将队首元素出队，然后将队首指针加1，因此D选项错误。故答案为：C。 18．A 【详解】本题主要考查栈和队列数据结构。栈和队列都是先进后出，队头只允许删除元素，队尾只允许插入元素，而栈只允许在栈顶插入和删除元素，故本题选A选项。 19．B 【详解】本题主要考查队列数据结构。head 指向队首元素，tail指向队尾元素的下一个位置，若 tail=head+3，则现在排队的顾客数量为tail-tail=3，故本题选B选项。 20．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选项。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$