高效作业9 第9课 队列1——初识队列-【精彩三年】2024-2025学年高中信息技术选择性必修1课程探究与巩固Word教参（浙教版2019）

高效作业9[第9课　队列1——初识队列](见学生用书P203) 【A级　新教材落实与巩固】 1．下列生活情境与队列相关的内容或操作的说法中，不正确的是(　D　) A．由于来餐厅用餐的人数较多，餐厅让客人排队用餐，对应队列的建队操作 B．小明点的外卖下单后，订单等待被处理，对应队列的入队操作 C．机场安检时，排在最前面的人员被告知前往相应位置进行安检，对应队列的出队操作 D．为控制游客的数量，管理人员告知后来的游客无法入园，不必再排队购票，正在排队的游客继续排队购买，对应队列空的状态 【解析】 选项D中“后来的游客无法入园”，对应的是队列满的状态，选项错误。 2． 小明在使用队列解决问题的过程中，初始时(空队列)，队列的队首指针head＝0，队尾指针tail＝0，经过一系列的入队、出队操作后，head＝4，tail＝7。在不考虑队列溢出的情况下，小明接下来进行的操作一系列为出队、入队、出队、出队、入队、出队，此时head和tail的值分别为(　B　) A．7和9　　　　　　　B．8和9 C．7和8 D．8和8 【解析】 队列元素在队首出队，队首指针加1，在队尾入队，队尾指针加1，根据操作系列“出队(head＋1)、入队(tail＋1)、出队(head＋1)、出队(head＋1)、入队(tail＋1)、出队(head＋1)”，进行一系列操作后head＝8，tail＝9，选项B正确。 3． 用一个大小为60的数组来做循环队列，循环队列需要牺牲队尾和队首之间的一个存储空间来区分队空和队满，队首指针是head，队尾指针tail指向最后一个元素的下一个位置，当(tail＋1)%60＝＝head时表示队满，则当head＝54，tail＝3时，先出队8个元素，再入队20个元素，则head和tail分别是(　B　) A．1和22 B．2和23 C．23和2 D．22和1 【解析】 从初始时head＝＝54，tail＝＝3时，可以计算出元素个数为(2－54＋1)%60＝＝9 个，所以先出队8个，还剩1个，即head＝(head＋8)%60，head指向(54＋8)%60＝＝2的位置，此时tail＝＝3，指向最后一个元素的下一个位置，真正元素的个数只有1个，在2这个位置，入队20个，tail＝(tail＋20)%60＝＝23，选项B正确。 4．从一个顺序队列删除元素时，首先需要(　C　) A．队首指针加1 B．队首指针减1 C．取出队首指针所指位置上的元素 D．取出队尾指针所指位置上的元素 【解析】 根据队列的先进先出的特性，需要删除元素只能从队首的位置开始进行，先取出队首指针所指位置上的元素，接下来队首指针加1，选项C正确。 5．2023·衢州一中检测已知队列元素的个数为 5，则队首指针 head和队尾指针 tail的值不可能是(　B　) A．head＝1，tail＝6 B．head＝2，tail＝6 C．head＝5，tail＝0 D．head＝3，tail＝2 【解析】 不管是否循环队列，head＝2，tail＝6 此时队列的元素一定是4，不可能是5，选项B符合题意。 6．下列关于队列的说法中，正确的是(　B　) A．队列是一种先进先出的线性表，插入一端为队首，删除一端称队尾 B．队列的存储结构，可用数组实现，也可用链表实现 C．一队列队头指针head，队尾指针tail, 则tail－1－head 表示队列中元素个数 D．学生排队就餐与软件连续撤销操作都是数据结构“队列”的应用实例 【解析】 选项A，队列插入一端(入队)为队尾，删除一端(出队)为队首，选项错误；选项C，队尾指针tail 指向队尾元素的下一个位置，所以tail－head 表示队列中元素个数，选项错误；选项D，软件连续撤销操作是撤销前一步操作，是“后进先出”的“栈”的应用实例，选项错误。 7．假设队列的空间足够，队首指针head和队尾指针tail经过“出队、入队、出队、出队、入队、入队、出队”这一系列操作后，head＝7，tail＝9。则操作前的head和tail的值分别为(　C　) A．11和12 B．2和5 C．3和6 D．3和5 【解析】 根据题意经过3次入队后，队尾指针tail＝9，因此在3次入队前tail应为6，在经过4次出队后队首指针head＝7，因此在4次出队前head应为3，选项C正确。 8．有一个队列，若进队的元素依次为“A，B，C，D，E，F”，则出队的序列为(　A　) A．A，B，C，D，E，F B．F，E，D，C，B，A C．A，B，C，D，F，E D．A，B，F，E，D，C 【解析】 队列是一种“先进先出，后进后出”的线性表，即队首元素优先出队，队尾元素最后出队，选项A正确。 9．有一个循环队列，它的最大容量为50，经过一系列的入队和出队操作后，发现队头指针head为30，队尾指针tail为15，则队列中元素的个数是(　C　) A．14 B．15 C．35 D．36 【解析】 因为是循环队列，head开始至tail元素个数为(15－30＋1＋50)%50＝35个，选项C正确。 10．创建一个容量为3的队列，元素2，3，5，1，3，5，2依次等待入队。入队规则为： ①若当前待入队元素已经在队列中，则跳过该元素，否则转②； ②若当前队列已满，将队首元素出队列，否则转③； ③将当前待入队元素入队列。 操作完成后，队列中的元素为(　D　) A． 2，3，5，1 B． 1，2，3，5 C． 2，3，5 D．5，1，2 【解析】 队列的容量为3，排除选项A、B；首先2，3，5入队，1入队时队列满，2出队，队列内为1，3，5；3，5队列中存在，跳过；2入队，队列满，队头3出队，队列内为1，2，5，head指向5，选项D正确。 11．某队列的数据结构如图所示，head和tail分别为队列的头、尾指针。现对该队列进行以下操作：①队首元素出队输出；②队首元素出队再入队；③重复①②操作直到队列为空。 若队列数据元素为“LUCKY”，则输出顺序是(　C　) A．LYUKC B．LCYUK C．LCYKU D．LUCKY 【解析】 首先输出L，U重新入队，接着输出C，K重新入队；Y出队输出，U重新入队；K出队输出，最后U输出，选项C正确。 12．下列关于Queue模块的说法中，正确的是(　D　) A． Queue对象是一种LIFO(后进先出)的队列 B． 当调用Queue.empty()方法时，如果队列为空，返回False，反之True C． Queue.get()方法的作用是返回队首元素的值 D．Queue.put(item)方法的作用是将新元素item添加到队列中 【解析】 选项A，一种LIFO(先进先出)的队列，选项错误；选项B，空返回True，选项错误；选项C，Queue.get()方法的作用是出队并返回队首元素的值，选项错误。 【B级　素养形成与评价】 13．2023·江山中学检测有如下Python程序段： d＝”零壹贰叁肆伍陆柒捌玖” a＝[””]*10 head，tail＝0，0 for i in range(len(d))： if i%3＝＝2： 　head＋＝1 else： a[tail]＝d[i] tail＋＝1 while head！＝tail： print(a[head]，end＝””) head＋＝1 执行该程序段后，输出的结果是(　D　) A．零壹贰叁肆伍陆柒 B．零壹叁肆陆柒玖 C．叁肆陆柒玖 D．肆陆柒玖 【解析】 程序中for循环遍历字符串d，当遍历的字符位置除以3余2时，队首指针加1(出队)，当遍历到其他位置的字符，把字符添加到队列a中(入队)，这个过程中字符串的“零壹叁肆陆柒玖”会依次进入队列a中，同时head值为3；while循环实现队列a的head至队尾tail范围元素出队过程，并输出出队元素，选项D正确。 14．有如下Python程序段： fib＝[] q＝[1]*3 head，tail＝0，2 for i in range(3，10)： q[tail]＝q[head]＋q[(head＋1)%len(q)] tail＝(tail＋1)%len(q) fib.append(q[head]) head＝(head＋1)%len(q) while head！＝tail： fib.append(q[head]) head＝(head＋1)%len(q) 执行该程序段后，fib[－1]的值为(　C　) A．1　　B．21　　C．34　　D．55 【解析】 执行程序后fib＝[1，1，2，3，5，8，13，21，34]，fib[－1]的值为34，选项C正确。 15．有如下Python程序段： q＝[3] a＝b＝0 while q[－1]<50： q．append(min(q[a]*3，q[b]*5)) if q[－1]＝＝q[a]*3： a＋＝1 if q[－1]＝＝q[b]*5： b＋＝1 执行该程序段后，len(q)和q[－1]的值分别为(　D　) A．5和45 B．5和50 C．6和50 D．6和75 【解析】 执行程序后q＝[3，9，15，27，45，75]，故len(q)的值为6，q[－1]的值为75，选项D正确。 16．下列Python程序段的功能是对队列que进行入队和出队操作，其代码如下： n＝10 que＝[””]*n tail＝head＝0 m＝int(input(”m＝”)) data＝input(”please input data：”) while data！＝”#”： #入队操作，输入“#”结束 if tail＝＝n－1： print(”队列已满！”) else： que[tail]＝data tail＝tail＋1 data＝input(”please input data：”) while head<tail and head<m：　#出队操作 print(que[head]，end＝””) head＋＝1 若输入m 的值为2，输入data的值分别为“A，B，C，D，E，F，#”，则执行该程序段后，队列que中的元素分别为(　A　) A．A，B B．C，D，E，F C．E，F D．A，B，C，D 【解析】 第1个while循环依次入队，q＝['A'，'B'，'C'，'D'，'E'，'F']，第2个while循环出队，由于“head<m”，存在一只出队并输出前2个元素，选项A正确。 17．有如下Python 程序段： a＝[2，4，5，10，8，13，11，7，2，6] que＝[0]*len(a) k＝int(input()) key＝int(input()) msq＝0；sq＝0 head，tail＝0，0 for i in a： que[tail]＝i sq＝sq＋i tail＝tail＋1 while sq>key or tail－head >＝k： sq＝sq－que[head] head＝head＋1 if sq>msq： msq＝sq 若输入k 的值为3，key 的值为20，则执行该程序段后，变量msq 的值为(　A　) A．18 B．19 C．20 D．32 【解析】 算法核心思想是求序列中连续长度为k－1，且元素和不超过key 值的最大值。利用队列结构中入队、出队的过程来实现这个最大值的查找。程序结果为列表a 中连续两个元素的和中，不超过20 的最大值，可得结果为18，选项A正确。 18．有如下Python 程序段： a＝[0，3，－3，0，－1，3，1，－5，5，2，－5，2] n＝len(a) q＝[0]*n head，tail，ans＝0，0，0 for i in range(n)： if head<tail： if q[tail－1]＋a[i]>＝0： q[tail]＝q[tail－1]＋a[i] tail＋＝1 else： if ans<tail－head： ans＝tail－head head＝tail else： if a[i]>0： q[tail]＝a[i] tail＋＝1 print(ans) 执行该程序段后，输出的结果是(　B　) A．2　 　B．3　 　C．4　 　D．5 【解析】 该代码求的是数组a 连续的累加和大于0 的最大长度，观察数组a 可知最长为3，选项B正确。 19． 2023·学军中学检测有如下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]) 执行该程序段后，输出的结果是(　B　) A． [2，3，5，1] B． [3，5，2] C． [2，3，5] D．[5，1，2] 【解析】 执行过程如下表： i 2 3 5 1 3 5 2 head 0 0 0 1 1 1 1 tail 1 2 3 3 3 3 4 que [2] [2，3] [2，3，5] [3，5] [3，5] [3，5] [3，5，2] 从队首位置开始输出，选项B正确。 20． 2023·东海中学检测 有如下Python 程序段： def f(lt，s，e，t，mx)： flag＝False while s！＝e： if t＝＝lt[s]： flag＝True；break s＝(s＋1)%mx return flag la＝[1，3，4，2，3，4，1，2，4，3，2，4] m＝3；n＝len(la) maxn＝m＋1；ans＝0 lb＝[－1]*maxn；head＝tail＝0 for i in range(n)： t＝la[i] if f(lb，head，tail，t，maxn)＝＝False： if (tail＋1)%maxn＝＝head： head＝(head＋1)%maxn lb[tail]＝t tail＝(tail＋1)%maxn ans＝ans＋1 print(ans) 执行该程序段后，输出的结果是(　C　) A．5 B．6 C．7 D．8 【解析】 本题考查自定义函数及循环队列知识。本题计算量较大，由代码可知，本题属于循环队列问题，maxn 是循环队列的长度，数组lb 的元素的初值都为－1，表示这是空队列。队列lb的实际元素个数只有(tail－head)%maxn＝＝3 个，进入队列lb 的元素都来自数组la 的特定元素，变量ans 记录lb 入队的次数。自定义函数f()的作用是当形式参数t 是数组lt 中的某个元素时，将flag 置为True，且强行退出。因此lb 中的元素不可能重复，且程序外循环将遍历整个队列la，其中只有部分情况符合入队条件(i 的值为0，1，2，3，6，9，11 时，此时if条件成立)，列表模拟程序运行界面如下： 因此，最终在lb 进队7 次后结束，选项C正确。 学科网（北京）股份有限公司 $$