2023-2024学年高二上学期浙教版(2019)选修一3.2队列

2023-2024学年高二上学期浙教版(2019)选修一3.2队列 一、选择题 1．队列que中队首至队尾元素依次为“A，B，C，D，E，F”，约定：Q为出队操作，R为出队再入队操作，经过QRQRRQ系列操作后，队列中队首到队尾的元素依次为（   ） A．F，B，D B．E，F，B C．B，D，E D．F，B，D，E 2．依次在初始为空的队列中插入元素 a，b，c，d 以后，紧接着做了两次删除操作，此时的队首元素是（   ） A．a B．b C．c D．d 3．有如下Python程序段： a="Python"；q=[0]*6 head,tail=0,0 i=len（a）-1 while i>=0: if i%3!=0: q[tail]=a[i] else: q[tail]=q[head] head+=1 tail+=1 i-=1 print（q[head:tail]） 当执行该程序段后，输出的结果是（   ） A．['n','t','y','o'] B．['n','t','y'] C．['n','o','n','t','y'] D．['n','o','n','t','y','o'] 4．某队列当前队首指针head=2，队尾指针tail=5，在不考虑队列溢出的情况下，进行如下操作：入队、入队、出队、出队、入队，队列中剩余的元素个数为（   ） A．7 B．5 C．4 D．3 5．下列对队列的描述，正确的是（   ） A．队列的特点是先进后出 B．在队列中，允许插入的一端称为队首，允许删除的一端称为队尾 C．刚建立的队列，队首指针和队尾指针均为0 D．出队操作时，先将队首指针加1，然后再将队首元素出队 6．栈和队列的共同点是（   ） A．只允许在端点处插入和删除数据 B．都是先进后出 C．都是先进先出 D．没有共同点 7．用列表模拟队列对数据进行操作，python程序如下 a=[3,4,5,6,7] head=0;tail=len(a) a+=[0]*100 while head+2<=tail:     if a[head]%2==0         a[tail]=a[head]//2         head+=1;tail+=1     elif a[head]<=5:         head+=1     else:         a[head]-=5 print(a[head]) 程序运行后输出的结果是（   ） A．0 B．1 C．2 D．3 8．下列场景中蕴含的数据结构思想与图一致的是（　　） 图一：排队做核酸 A．Excel执行撤销操作 B．编号不重复的名单 C．寻宝游戏路线 D．打印机任务面板 9．某单向队列存储空间足够，使用head记录队首元素所在的位置，tail记录队尾元素的下一个位置，经过“出队，入队，出队，出队，入队，出队”操作后，head=6，tail=8，则在操作前队列中元素的个数是（    ） A．0 B．2 C．4 D．6 10．在数据结构中，队列的特点是（   ） A．先进先出 B．先进后出 C．后进先出 D．后进后出 11．给一个队列如下约定：T操作是指队列中1个元素出队后再入队，P操作是指1个元素入队。原始队列经过TTPTP系列操作后，队列中队首到队尾的元素依次为ABCDE，则原始队列中队首到队尾的元素依次为（   ） A．ABC B．ABD C．BAE D．BADEC 12．在某餐厅点餐系统中， 利用队列来储存当前正在排队顾客的编号，head 指向队首元素，tail 指向队尾元素的下一个位置， 若 tail=head+3，则现在排队的顾客数量为（    ） A．2 B．3 C．4 D．5 13．某队列经过“出队”“入队”操作后，队首指针head=2，队尾指针tail=6，则该队列中剩余的元素个数是（   ） A．2 B．4 C．5 D．6 14．约定：T操作是指在队列中1个元素出队后再入队，E操作是指将1个元素入队，P操作是指队列中1个元素出队，队首指针head和队尾指针tail初始值均为0。则经过EETPETEP 系列操作后，队首指针head和队尾指针tail的值分别为（   ） A．3 4 B．3 5 C．4 5 D．4 6 15．队列q中队首至队尾元素依次为“A，B，C，D，E，F”，约定：S为出队操作，U为出队再入队操作，若要使队列q队首至队尾元素依次为“B，D，E”，下列操作可实现的是（    ） A．USUSSU B．SUSUUS C．SSSUUU D．SUUSUS 二、填空题 16．队列是一种有限制的 结构。特点是数据元素只能在 依次添加（称为进队），在另一端依次删除（称为 ）。 17．在计算机编程中， 是一种用于存储和管理数据的集合，它允许数据项以有序的方式添加和删除。 18．在数据结构中， 是一种特殊的线性表，只允许在表的两端进行插入和删除操作。 三、操作题 19．为鼓励绿色出行，某市推出了优惠方案：乘一次地铁后可以获得一张优惠券，在有效期45分钟内(含)可免费搭乘一次公交车。有效期指乘公交车与乘地铁的开始时刻之差。搭乘公交车时，可以使用优惠券则一定会使用，如果有多张优惠券满足条件，则优先消费获得最早的优惠券。有人用Python编写程序计算出行的费用。他的某次出行过程如图a所示，程序运行结果如图b所示。    请回答下列问题： （1）请在划线处填入合适的代码。 def Ctime(t): # 自定义函数Ctime功能为将时间转为分钟计存入变量s，代码略。 return s ''' 读取出行记录，存储在列表a中，a[i][0]、a[i][1]、a[i][2]依次存储交通工具类型、票价、乘坐开始时刻。交通工具类型a[i][0]值为0表示地铁，1表示公交车。代码略。 ''' n = len(a) for i in range(n): a[i][2] = Ctime(a[i][2]) for i in range(n - 1): for j in range(n - 1, i, -1): a[j], a[j - 1]= a[j - 1], a[j] # 输出出行记录，代码略。 total = 0 head = tail = 0 q = [-1] * n for i in range(n): if a[i][0] == 0: total += a[i][1] tail += 1 else: while head < tail and q[head] < a[i][2] - 45: head += 1 if : total += a[i][1] else: print(a[i][2],"时刻使用了优惠券") print("总共花费为:", total) （2）程序中加框处代码有错，请改正。 （3）该程序主要应用的数据结构类型是 (选填：队列 / 栈 / 链表 / 二叉树)。 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．C 2．C 3．A 4．B 5．C 6．A 7．C 8．D 9．C 10．A 11．B 12．B 13．B 14．D 15．B 16． 线性数据 队尾 出队 17．队列 18．队列 19． q[tail]=a[i][2] head==tail 或 q[head]==-1 head+=1 a[j][2] < a[j - 1][2] 队列 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$