教科版（2019）选修一4.1队列结构及其实现同步训练

教科版（2019）选修一4.1队列结构及其实现同步训练 学校:___________姓名：___________班级：___________考号：___________ 一、选择题 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．“餐厅信息管理系统”由菜品管理、订单管理和客户管理三个模块组成。订单管理模块可以实现顾客点餐、订单结算和订单统计的功能。餐厅的碗碟都已植入了电子标签，在系统中可设定每个电子标签对应的菜品。顾客将选好菜品的托盘放入结算台，结算台读取电子标签信息，系统自动完成结算，顾客在刷卡区完成结算。在该系统中，可以利用队列来储存当前正在排队顾客的编号，head 指向队首元素，tail指向队尾元素的下一个位置，若 tail=head+3，则现在排队的顾客数量为 (　　) A．2 B．3 C．4 D．5 3．有1个队列，队首到队尾的元素依次为1，2，3，4，5。约定：T操作是指队列中1个元素出队后再入队，Q操作是指队列中1个元素出队。则经过TTQTTQTTQ系列操作后，队列中队首到队尾的元素依次为：（　　） A．4，5 B．5，4 C．2，4 D．4，2 4．假设队列空间足够，队列中的元素个数为5。约定：T为入队操作，Q为出队操作，则经过TTQQTQTQQ 一系列操作之后，队首指针head，队尾指针tail的值可能为（    ） A．head=11，tail=7 B．head=7，tail=11 C．head=9，tail=12 D．head=12，tail=9 5．有一个非循环队列S如图所示，其中指针head指向队首元素的位置，指针tail指向队尾元素的下一个位置。 关于该队列说法正确的是（    ） A．队列中元素个数为tail-head+1 B．新元素入队时，指针head向右移动 C．元素出队时，指针tail向右移动 D．当tail==len（S）时，无法再入队新元素 6．某单向队列存储空间足够，使用head记录队首元素所在的位置，tail记录队尾元素的下一个位置，经过“出队，入队，出队，出队，入队，出队”操作后，head=6，tail=8，则在操作前队列中元素的个数是（    ） A．0 B．2 C．4 D．6 7．操作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 8．小陈设置密码的步骤如下：①将[1,10)以内是2或3的倍数整数全部依次入队；②队首元素出队并输出；③队首元素出队再入队，重复②③操作直到队列为空，输出的结果为（   ） A．234689 B．248369 C．369428 D．248396 9．有1个队列，队首到队尾的元素依次为8，3，2，9，5。约定：T操作是指队列中1个元素出队后再入队，Q操作是指队列中l个元素出队。则经过TTTQTTQ系列操作后，队列中队首到队尾的元素依次为（   ） A．2，9，5 B．2，5，8 C．5，8，2 D．8，3，2 10．有如下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 11．下列关于数据结构的说法正确的是（   ） A．同一数据元素中各数据项的数据类型一定相同 B．跳跃表是立足链表、借鉴二分查找的思想而形成的数据结构 C．若入栈序列为 abcd，则出栈序列可能为 dbca D．在浏览器中执行“后退”、“前进”操作的原理与队列的特点相同 12．在某餐厅点餐系统中， 利用队列来储存当前正在排队顾客的编号，head 指向队首元素，tail 指向队尾元素的下一个位置， 若 tail=head+3，则现在排队的顾客数量为（    ） A．2 B．3 C．4 D．5 13．某队列的数据结构如图所示，head 和tail 分别为队列的头、尾指针。现对该队列进行 以下操作：①队首元素出队输出②队首元素出队再入队，重复①②操作直到队列为空。 que     L      U      C      K      Y 0      1      2      3      4      5      … 若队列数据元素为“LUCKY”，则输出顺序是（    ） A．LYUKC B．LCYUK C．LCYKU D．LUCKY 14．下列关于数据结构的说法正确的是（    ） A．“撤销”操作，是“队列”的应用 B．排队就餐， 是“栈”的应用 C．“链表”存储相邻节点不需要连续空间 D．“树”中每个节点的前后都只有一个相邻节点 15．队列的特点（   ） A．先进先出 B．先进后出 C．插入操作只能在队头进行 D．删除操作只能在队尾进行 试卷第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 【详解】本题主要考查队列数据结构。head 指向队首元素，tail指向队尾元素的下一个位置，若 tail=head+3，则现在排队的顾客数量为tail-tail=3，故本题选B选项。 3．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正确。 4．B 【详解】本题主要考查队列的操作。T为入队操作，Q为出队操作，队列队首出队，队尾入队，经过TTQQTQTQQ一系列操作之后，即出队了5个，入队了4个，此时队列中还有4个元素，如果tail指向最后一个元素的下一个位置，则tail-head=队列元素=4，结合选项，可知head=7，tail=11符合题意，故选B。 5．D 【详解】本题主要考查队列数据结构。由图可知，队列中元素个数为tail-head；新元素入队时，指针tail向右移动；元素出队时，指针tail向左移动； 当tail==len（S）时，无法再入队新元素，故本题选D选项。 6．C 【详解】本题主要考查队列的操作。经过“出队，入队，出队，出队，入队，出队”操作后， head =6, tail =8，可以得到操作前的 head =6-4(4次出队)=2, tail=8-2(2次入队）=6，所以原来队列中有6-2=4个元素，所以选项 C 符合题意。故选： C 。 7．A 【详解】本题主要考查队列的操作。按照操作顺序RRRTQRQR进行操作，首先1、2、3入队，再1出队再入队，此时队列元素是2、3、1，接着2出队4入队，此时队列元素是3、1、4，最后3出队5入队，此时队列中的数字依次为1、4、5，故本题选A选项。 8．D 【详解】本题主要考查队列的操作。①将[1,10)以内是2或3的倍数整数全部依次入队，即入队元素是234689，第一次2是队首元素出队并输出，之后3是队首元素，出队再入队，变为46893；第二次4出队并输出，之后6是队首元素，出队再入队，变为8936；第三次8出队并输出，之后9是队首元素，出队再入队，变为369；第四次3出队并输出，之后6是队首元素，出队再入队，变为96；接下来分别输出9和6，因此输出的结果是248396，故本题选D选项。 9．B 【详解】本题考查的是队列操作。队列操作原则是先进先出。经过TTT操作后队首到队尾的元素依次为9,5,8,3,2；再经过Q操作后队首到队尾的元素依次为5,8,3,2；再经过TT操作后队首到队尾的元素依次为3,2,5,8；再经过Q操作后队首到队尾的元素依次为2,5,8。故选项B正确。 10．D 【详解】本题主要考查Python程序的执行。分析程序可知，该程序模拟队列数据类型，如果i是偶数，则将s[i]入队列que[tail]，如果i是奇数，则将s[len(s)-i]入队列que[tail]，第一个for循环执行完，队列中的元素是“AFCDEB”，第二个for循环按照队列“先进先出”的规则依次出队，故以上程序运行后，打印出列表的情况是：AFCDEB，故本题选D选项。 11．B 【详解】本题主要考查数据结构的描述。同一数据元素中各数据项的数据类型不一定相同；跳跃表是立足链表、借鉴二分查找的思想而形成的数据结构；若入栈序列为 abcd，则出栈序列不可能为 dbca；在浏览器中执行“后退”、“前进”操作的原理与栈的特点相同，故本题选B选项。 12．B 【详解】本题主要考查队列数据结构。head 指向队首元素，tail 指向队尾元素的下一个位置，则队尾元素的位置是tail-1，若 tail=head+3，则现在排队的顾客数量为tail-1-head+1=head+3-1-head+1=3，故本题选B选项。 13．C 【详解】本题主要考查队列数据结构。根据题意先执行①输出L，接着执行②，U为队首出队加入队尾，字符串为CKYU；再次执行①输出C，接着执行②，K为队首出队加入队尾，字符串为YUK；第三次执行①输出Y，接着执行②，U为队首出队加入队尾，字符串为KU；第四次执行①输出K，接着执行②，U为队首出队加入队尾，字符串为U；第五次执行①输出U。因此输出字符串为LCYKU，故本题选C选项。 14．C 【详解】本题主要考查数据结构的描述。“撤销”操作，是“栈”的应用；排队就餐， 是“队列”的应用；“链表”存储相邻节点不需要连续空间；“树”结构不一定是二叉树，也不一定只有一个相邻节点，故本题选C选项。 15．A 【详解】本题主要考查队列数据结构。队列的特点是先进先出，插入操作只能在队尾进行，删除操作只能在队头进行，故本题选A选项。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$