3.2 队列（分层作业）信息技术浙教版2019选择性必修1

3.2队列 1课时（分层作业） 【基础达标】 1.队列是一种先进先出的 ，允许插入的一端称为队尾，允许删除的一端称为 。 2.队列中的数据元素称为 。在队列中插入一个元素称为 ，从队列中删除一个元素称为 。 3.队列的特性: 、 。 4.队列的元素个数是 。 5.队列中所有元素呈 ，队首元素只有一个 ，队尾元素只有一个 。 6.队列一般按 ，可以用 来实现。 7.队列的常用操作有 、 、 等。 8.循环队列是将队列的 ，形成逻辑上的环状结构。 9.幼儿园小朋友们排队玩滑滑梯，轮流爬上去，再轮流滑下来，此过程用哪种数据结构描述最合适( ) A.链表 B.字典 C.字符串 D.队列 10.下列事件执行过程与队列特征不相符的是( ) A.在汽车加油站排队加油时不允许插队 B.当主机运行速度与打印机的打印速度不匹配时，为打印机设置一个打印数据缓冲区 C.把书叠放成一摞，最底下的书要最后才能拿出来 D.CPU分时系统可以根据用户请求，按顺序快速运行各程序段，实现多用户“同时”工作的假象 【巩固提升】 1.已知队列元素的个数为6，则队首指针 head 和队尾指针 tail 的值不可能的是( ) A.head=0, tail=6 B. head=6,tail=0 C. head=3,tail=2 D. head=3,tail=8 2.用 python 列表模拟循环队列，并设置队首指针head指向队首元素，队尾指针指向队尾元素的下一个位置,则当列表长度 n=10，head=6，tail=3 时，队列中元素的个数为( ) A.5 B.6 C.7 D.8 3.已知队列(4，21，55，66，48，24，35，12，78，5)第一个进入队列的元素是4，请问第3个出队列的元素是( ) A.35 B.12 C.55 D.5 4.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( ) A.栈 B.队列 C.树 D.图 5.依次在初始为空的队列中将元素“h”，“e”，“l”，“l”，“o”入队以后，紧接着做了两次删除操作，此时的队首元素是（ ） A.“h” B.“e” C.“l” D.“o” 6.下列对队列的描述，正确的是（ ） A.队列的特点是先进后出 B.在队列中，允许插入的一端称为队首，允许删除的一端称为队尾 C.刚建立的队列，队首指针和队尾指针均为0 D.出队操作时，先将队首指针加1，然后再将队首元素出队 7小王在使用队列解决问题的过程中，初始时，队列为空，队列的首指针和尾指针分为为head、tail，接着小王开始进行了一系列的操作，操作序列为：入队、入队、入队、出队、入队、入队、出队、出队、出队、入队、入队，则操作结束时head和tail的值分别为（ ） A.4 7 B.4 8 C.5 7 D.5 8 8.有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 9.创建一个容量为3的队列，元素2，3，5，1，3，5，2依次等待入队。入队规则为： ①若当前待入队元素已经在队列中，则跳过该元素，否则转② ②若当前队列已满，将队首元素出队列，否则转③ ③将当前待入队元素入队列 操作完成后，队列中的元素为（　　） A．2，3，5，1 B.1，2，3，5 C.2，3，5 D.5，1，2 10.有如下python 程序段，使用长度为3的列表q模拟队列的出队、入队活动： q=[1,2,3] ys=[] for i in range(4,10): ys.append(q[0]) q[0]=q[1] q[1]=q[2] q[2]=i print(ys,q) 程序运行结束后，列表ys中元素的数量为_____________。 11..20个人围成一圈，他们的学号分别1，2，……，10，从第一个人开始数起，每数到4，这个人从圈里出来，再继续数。凡从圈里出来的位置，下次数时，就跳过不再计数，直到所有人出圈。请打印从圈里出来的人的顺序：_________________________________。 【链接高考】 1.卫星系统： 有一套环球卫星通讯系统，由n颗通讯卫星组成，编号为1到n，呈环状。为了保证信息通信的安全，在信息传递时将一条信息分割到各个卫星中传递。按以下规则接收信号：先接收第1号卫星上的信号，再间隔1颗卫星接收信号，这时恰好是第2号卫星上的信号；接下来间隔2颗卫星，接收到是第3号卫星上的信号。依此类推，每次间隔的卫星数量为上一次接收到的卫星编号。一颗卫星只接收一次信号，接收过的卫星不再接收第二次信号，即此卫星不计算在间隔的卫星数量中。按此规则，正好可以接收到所有n颗卫星的信号，并组成最终信息。 按上述规则，当有5颗卫星时，它们在环上的卫星编排顺序为：1 3 2 5 4，4号卫星的下一颗卫星是1号卫星。输入卫星数量n，从位置1开始输出环上每个位置上的卫星编号。程序如下，请完善代码。 n=int(input()) a=[0]*(n+1) a[1]=1 t=1 times=0 for i in range(2,n+1): c=0 while ① : t=t+1 ② if t>n: t=1 if a[t]==0: c+=1 a[t]= ③ # 表示位置t上放置卫星i for i in range(1,n+1):#检举环上位置，输出每个位置上的卫星编号 print(a[i],end=" ") print() print(times) 2.有11人，6男5女，在玩排队游戏。初始时，11人排成一个纵队A，并给他们标号为1，2，3，……，11号。排队游戏规则为：每次纵队A的前2人出队，按序插入到纵队B中，纵队A中第3人出队后，并排到纵队A的队尾；循环操作直至纵队A为空，且全部排到纵队B中。现要求纵队B，男女交替，则纵队A中，男女如何安排？ 3.有如下python程序段： from queue import Queue q=Queue(5) print(“能存放的最多元素个数=”,q.maxsize) #q.maxsize 返回最大元素个数 for i in range(q.maxsize): q.put(3*i) print(“是否满：”,q.full()) #q.full 返回True或False for i in range(q.qsize()): print(“当前实际长度=”,q.qsize()) print(“取出元素：”,q.get()) 从队列中取出的元素依次是____________。 4.银行叫号排队系统：客户去银行办理业务时，需先从取号机上取一张排队号，然后等待叫号系统叫号去柜台办理业务。请设计算法，实现该叫号系统的功能。 （1）思考：取号、叫号的顺序符合__________数据结构的特征？ （2）算法设计： ①建立队列que，队列的初始长度设置为1000，初始值均为-1。设置队首指针变量head，队尾指针变量tail的值均为0。 ②设计输入提示界面，实现多次取号和叫号功能。用x存储输入的数字，如果x=1，实现取号功能；x=2，实现叫号功能；x=3，程序退出。 ③当x=1时，分配一个号码，入队指针tail加1，并显示需要等待的人数。 ④当x=2时，先判断que队列是否为空。若为空，则显示无等待的人员；否则，que队首元素出队，head指针加1，并显示可以办理业务的客户号码。 （3）算法实现，并在划线处填入正确的语句。 que=[-1]*100;head=tail=0 print("1.新到顾客（取号)") print("2.下一个顾客（叫号）") print("3.程序结束") x=int(input("请输入操作编号：")) while x!=3: if x==1: que[tail]=tail print("您当前的号码为：A%d,需要等待的人数为:%d"%( ___①_ ,___②__)) __③_______ if x==2: if ____④_________: print("对不起，没有等待的客户！") else: print("请A%d的客户准备，马上为您办理业务！"% _____⑤___ ) ____⑥_______ x=int(input("请输入操作编号：")) 参考答案 【基础达标】 1.线性表、队首 2.队列元素、入队、出队 3.先进先出、后进后出、有限序列性 4.有限的 5.现线性特征、后继点、前驱点 6.顺序结构存储、数组 7.建队、入队、出队 8.队列的队首和队尾连接起来 9.[解析]链表是存储结构，字段是数据类型，栈和队列是数据结构。排队玩滑滑梯是一头进一头出的队列结构。 答案：D 10. [解析]队列数据是一头进一头出，先进先出。C选项是栈的特点，进出只有一头，先进的后出。ABD选项符合队列特点。故选C。 答案：C 【巩固提升】 1. [解析]本题考查的是队列的相关知识。初始时，队列为空，队首指针head和队尾指针tail的值均为0，队列不为空时，队首指针指向队首元素，队尾指针指向队尾元素的下一个位置。选项A中入队6次，出队0次，那么head和tail的值为0，6该项正确;同理分析选项B，选项B，不可能入队0次，出队6次，该项错误。 答案：B 2. [解析]head表示队首，tail表示队尾。当head等于tail时表示队列结束。本题意中的队列元素分别是a列表中下标为6，7，8，9，0，1，2，3的元素，共8个元素。故选D。 答案：D 3. [解析]队列进出的原则是先进先出，第3个出队列的实在第3个进队列，第一个为4，第3个为55，第3个出队列的就是55。 答案：C 4.[解析]为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，该缓冲区的逻辑结构应该是(队列)栈的定义:栈是只准在表尾进行插入和删除的线性表，称为LIOFO(即后进先出表)。允许插入和删除的一端叫栈顶，另一端叫栈底。队列的定义:队列是允许在一端进行插入而在另一端进行删除的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。队列也称为先进先出表(FIFO)树的定义:树是包含n个结点的有限集合(n>0)图的定义:图(Graph)是由非空的顶点集合和一个描述顶点之间关系一-边(或者弧)的集合组成。其形式化定义为:G=(V,E)其中G表一个图，V是图G中顶点的集合，E是图G中边的集合。 答案：B 5.[解析]队列数据结构的特点是先进先出。进入的顺序是hello，删除就是出数据，删除两次分别出数 据h和e。剩下llo，并且开头是l。 答案：C 6.[解析]队列的特点是先进先出，因此A选项错误;允许插入的一端称为队尾,允许删除的一端称为队首,因此B选项错误;出队操作时,先将队首元素出队，然后将队首指针加1,因此D选项错误;刚建立的队列,队首指针和队尾指针均指向下标为0的元素,即队首指针和队尾指针均为0,因此答案为C。 答案：C 7.[解析]初始时,队列为空,队首指针head和队尾指针tail的值均为0,队列不为空时,队首指针指向队首元素,队尾指针指向队尾元素的下一个位置,本题中共进行了7次入队操作和4次出队操作，因此最终 head 和 tail 的值分别为4、7,因此答案为 A。 答案：A 8.[解析]阅读题干信息可知，T的操作是出队并入队，Q的操作为出队，TTTQTTQ之后队列内元 素依次是2，5，8，出队的元素依次是9，3。故选:B。 答案：B 9.[解析]由于容量为3的队列，所以最初栈里的元素为2，3，5，当1进入栈时，若当前队列已满，将 队首元素出队列，变为3，5，1，当入栈为3和5时，由于栈中有该元素，跳过。当入栈为2时，当前队列已满，将队首元素出队列，变为5，1，2.故选:D。 答案：D 10.[解析]题目中列表q模拟队列的“先进先出，后进后出”的出队和入队过程,列表ys获得出队的序列，循环中实现了6个元素的出队和入队。 答案：6 11.答案：4 8 2 7 3 10 9 1 6 5 【链接高考】 1.答案：①c<i、②times+=1、③i 2.答案： 先按游戏规则，11个人排的纵队A，如下表： 1 2 3 4 5 6 7 8 9 10 11 按照游戏规则，纵队A和纵队B变化如下： A 4 5 6 7 8 9 10 11 3 B 1 2 A 7 8 9 10 11 3 6 B 1 2 4 5 A 10 11 3 6 9 B 1 2 4 5 7 8 A 6 9 3 B 1 2 4 5 7 8 10 11 A 3 B 1 2 4 5 7 8 10 11 6 9 A B 1 2 4 5 7 8 10 11 6 9 3 按照原始排队，得到的纵队B(男女交替)的编号为： B 1 2 4 5 7 8 10 11 6 9 3 由于纵队B为一男一女，则初始时，纵队A对应的性别为： A 1 2 3 4 5 6 7 8 9 10 11 男 女 男 男 女 男 男 女 女 男 女 3.答案：0,3,6,9,12 4.答案：（1）①que[tail], ②tail-head ③tail=tail+1 ④head==tail ⑤que[head] ⑥head=head+1 原创精品资源学科网独家享有版权，侵权必究！ 学科网（北京）股份有限公司 学科网（北京）股份有限公司 $$