队列二轮复习专项训练-2025-2026学年浙教版高三信息技术选修一第三章

队列专题练 1. 在某银行排队叫号系统中，利用队列来储存当前正在排队顾客的编号，head 指向队首元素，tail 指向队 尾元素的下一个位置，若现在队列的顾客数量为4时，则head 和 tail 的关系正确的是 A. head-tail+3 B. head=tail+4 C.tail=head+3 D.tail=head+4 2. 有一个循环队列，长度为 15，头指针为 head，尾指针为 tail，则下列选项中队列元素个数与其他三项 不同的是 A.head=3, tail=8 B.head=8,tail=13 C.head=10,tail=0 D.head=14,tail=9 3. 有“甲乙丙丁戊”5 位游客已按序排队，定义下列操作:顺利买票进入景区，记为 Q1;缺少证件需要重新 排队，记为 Q2;新游客进来排队，记为 Q3。若游客“丁”买票时，发现游客“乙”在“丁”的后两位，则已进行的操作过程可能是 A. Q3,Q1,Q2,Q1 B.Q1,Q2,Q2,Q3 C. Q1,Q2,Q3,Q3 D.Q2,Q2,Q1,Q3 4. 队列Q从队首到队尾元素依次为"d","e","s","k"栈S初始为空。约定:O操作是元素出队后入栈,I操作是元 素出栈后入队。经过 OOIOOIO 系列操作后，栈S的顶元素为 A."d" B."e" C."s" D."k" 5. 有1个队列，队首到队尾的元素依次为 1,2,3,4,5,6,7。现进行如下操作:①出队2个元素:②再出队1个元 素并将该元素入队。重复以上操作，直至队列中仅剩1个元素。则该元素是 A.3 B.5 C.6 D.7 6. 有如下 Python 程序段: from random import randint q=[1,2,14,5,6,79,10] head =0, tail = len(q)-1 ans=0 m = randint(1.3) q+= [0]* m for i in range(m): for j in range(2 **i- 1): head += 1 ans += q[head] q[tail]= q[head] head +=1;tail += 1 执行该程序段后，变量 ans 的值不可能是 A. 1 B.15 C.24 D.34 7. 有如下 Python 程序段 from random import randint n=5 q=[0]*n head = tail =randint(0.n-1) while head !=(tail + 1)% n: num =randint(1,n) if q[head] != num: q[tail]= num tail = (tail + 1)% n else: q[head]=0 head =(head + 1)% n 执行该程序段后，列表q可能为 A. [1, 2, 3, 4, 5] B. [3, 0, 1,4,1] C. [5, 0, 1,2.3] D. [1, 0,0, 4,3] 8. 有如下 Python 程序段: s=input() d=[-1]*10 head = tail =0 n= len(s) for i in range(n): if d[int(s[i])] < head: if tail - head == 3: head += 1 d[int(s[i])]= tail tail +=1 若执行程序后，d的值为[-1,4,6,5,3,-1,-1,-1,-1,-1]，则输入的s 值可能是 A."6954132" B. "11114132" C."1324132" D."41341322 9. 若字符串 a的值为"takeiteasy”，执行如下程序段后，变量 res 的值是 res=["]* 5 head=0 tail=0 a='takeiteasy' for i in range(len(a)): if tail - head == 0 or a[i]>res[tai1 - 1]: res [tail]= a[i] tail+=1 elif tail - head ==1: res [head]= a[i] elif tail - head > 1 and a[i] > res[tail - 2]: res [tail-1]= a[i] A.['t','y','','',''] B.['a','e','s','y,''] C.['a','e','i','s','y'] D.['a','s','y',",''] 10. 某 python 程序段如下: s="hAp#py" que=[""]*10 head, tail=0，0 res="" for i in range(len(s)): if 'a'<=s[i]<='z': que[tail]-s[i] tail+=1 else: head+=1 print(que[head:tail]) 执行该程序段，输出的结果是 A.['h','p','p','y'] B.['p','p','y'] C.['p',' y'] D.['y'] 11.小阳的创意工坊，每天都会接到很多订单，且每个订单花费一个单位时间。其中order列表中存储每个订单的截止时间和利润。假设他的工作是从0时刻开始算，订单能在截止时间内（包括截止时间）完成，就会获得利润。他可以选择完成当前时间之后的任意一个订单，过了截止时间的订单就会自动取消。 （1）为了获得较高利润，小阳想到按时间优先的方式来完成订单。为此定义tsort(1st)函数，其中参数1st的每个元素包括截止时间和利润。函数的功能是根据订单截止时间升序排列。 def tsort(1st):     n=len(lst)     for i in range(n-1):         for j in range(n-i-1):             if lst[j][0]>lst[j+1][0]:                     return lst 调用该函数，若lst=[[2,4],[1,4],[1,2],[3,5],[2,3],[3,6]]，虚线框中的程序段执行次数为 。 （2）小阳发现按时间优先设计的算法，获得的利润并不是最大的。在截止时间进行排序后的订单基础上对算法重新设计：依次对每个订单进行处理，确保每个截止时间要完成的订单利润为当前订单队列和所有未超时订单中利润最高。部分python程序段如下，请在划线处填入合适的代码。 order=[[2,5],[1,4],[1,3],[3,1],[3,2],[2,6]];n=len(order) ans=0  #ans存放最大利润之和 que=[[] for i in range(n)]   #利润优先订单队列 head=tail=0 order=tsort(order) def enque(tmp, tail, head):#数组模拟优先队列入队     p=tail     que[tail]=tmp     tail+=1     for i in range(tail-1, head,-1):         if que[i-1][1]>tmp[1]:             que[i]=que[i-1]             ①             que[p]=tmp     return tail for i in range(n):     if order[i][0]> ② :         tail=enque(order[i], tail, head)         ans+=order[i][1]     else:         if order[i][1]>que[head][1]:             ans-= ③             head+=1             tail=enque(order[i], tail, head)             ans+=order[i][1] print("利润最大为"+str(ans)) （3）小阳接到订单order=[[2,5],[1,4],[1,3],[3,1],[3,2],[2,6]]，输出结果为 。 12．某餐厅餐桌设置如下表： 餐桌型号 2人小桌 4人方桌 6人大方桌 12人大圆桌 餐桌数量 8 15 10 4 平均就餐时间（分钟） 25 45 60 80 有客人来就餐时其叫号系统会自动生成一个号码，并根据人数安排餐桌型号；当对应餐桌型号有空桌时，按餐桌编号（由小到大）即时分配餐桌安排客人就餐；当对应餐桌型号没有空桌时，客人按先后顺序排队。程序部分运行界面如下： （1）定义如下gettype()函数，功能为输入客人人数，返回对应桌型，请在程序划线处填入合适代码。 def gettype(num):     type=-1     for i in range(len(size)):         if num<=size[i]:             type=i                  return type （2）定义如下checktable()函数，功能为输入桌型，返回对应桌型空桌的编号，返回值类型为列表，请在程序划线处填入合适代码。 def checktable(n):     ans=[]     for i in range(nums[n]):         if :             ans.append(i) return ans （3）解决上述问题的主程序部分代码如下，请在划线处填入合适代码。 size=[2，4，6，12] #每种桌型最大就餐人数 nums=[8，15，10，4] #每种桌型的餐桌数量 times=[25，45，60，80] #每种桌型平均就餐时间 flags=[[True]*nums[i] for i in range(4)] #标记每张桌子的初始状态 s_time=10*60*60  #开始营业时间——10 点整，转化为秒 e_time=14*60*60  #结束营业时间——14 点整，转化为秒 maxn=50  #假设队列已经足够深 qc=[[0]*maxn for i in range(4)] #循环队列 now_time=s_time id=0 head，tail=[0]*4，[0]*4 while now_time<e_time:     number=getinfo()#调用函数 getinfo()，获取客人人数     if number>0:         id+=1         type=gettype(number) #根据就餐人数确定餐桌类型         if type!=-1:             qc[type][tail[type]]=id             tail[type]=(tail[type]+1)%maxn             qc_len=①             print(id，"号客人，给您安排的是"，size[type]，"人桌，前面还有"，qc_len-1，"人在等位")         else:             print(id，"号客人，非常抱歉，没有适合您的桌型！")     for i in range(4):         tables=checktable(i)         if ② :             flags[i][tables[0]]=False#入座第一个空桌             print(qc[i][head[i]]，"号客人请用餐-->"，size[i]，"人桌"，tables[0]，"号")             head[i]=(head[i]+1)%maxn     now_time+=1     #更新每张餐桌的就餐情况，代码略 学科网（北京）股份有限公司 $ 队列专题练 答案 1.D 【解析】本题考查的是队列相关知识。在队列中，head指向队首元素，tail指向队尾元素的下一个位置。如果队列中有4个顾客，那么tail指向的位置比head指向的位置多4个位置。因此，tail=head+4。故本题应选D。 2.D 【解析】本题考查队列。循环队列元素个数计算:当 tailzhead，个数 = tail-head;当 tail<head，个数=队列长度+tail -head。A选项:head=3,tail=8,个数=8-3=5个。B选项:head=8,tail=13,个数=13-8=5个。C选项: head=10,tai=0，个数=15+0-10=5个。D选项:head=14,tail=9，个数=15+9-14=10个。因此，本题选择D。 3.B 【解析】本题考查队列。B选项正确，若按 Q1，Q2，Q2，Q3的顺序操作，初始顺序“甲乙丙丁戊”，甲顺利买票后变为“乙丙丁戊”，重新排队后为“丙丁戊乙”，丙重新排队后为“丁戊乙丙”，新游客X进来排队后为“丁戊乙丙X”，此时丁买票时乙在丁的后两位,符合条件;A选项错误，游客“乙”在“丁”的后三位，C选项错误，该选项操作结束后，还未轮到丁买票;D选项错误，游客“乙”在“丁”的后三位。因此本题选择B。 4.B 本题考查栈和队列相关内容。初始状态，队列Q从队首到队尾元素依次为栈S初始为空。元素操作情如下: (1)执行“O”操作，“d”元素出队后入栈，队列Q从队首到队尾元素依次为“e”，栈S从栈顶到栈底元素依次为“d” (2)执行“0”操作，“e”元素出队后入栈，队列Q从队首到队尾元素依次为“s”、，栈S从栈顶到栈底元素依次为“e”"d" (3)执行“”操作，“e”元素出栈后入队，队列Q从队首到队尾元素依次为“s”栈S从栈顶到栈底元素依次 为“d"(4)执行“0”操作，“s”元素出队后入栈，队列Q从队首到队尾元素依次为“k”."e"栈S从栈顶到栈底元素依次为“s”"d" (5)执行“0”操作，“k”元素出队后入栈，队列Q从队首到队尾元素依次为“e””，栈S从栈顶到栈底元素依次为“k”、"ầ紧c“d" (6)执行“”操作，“k”元素出栈后入队，队列Q从队首到队尾元素依次为“e”、“k”，栈S从栈顶到栈底元素依次为“s”“d” (7)执行“0”操作，“e”元素出队后入栈，队列Q从队首到队尾元素依次为“k”，栈S从栈顶到栈底元素依次为“e”、"d" 则经过OOIOOI0系列操作后，栈S的栈顶元素为“e”。故本题答案是B选项。 5.C 【解析】本题考查队列。C选项正确，队列是先进先出的，根据题意，队首到队尾的元素依次为1，2，3，4，5，6，7，执行操作出队2个元素，队列变为:3，4，5，6，7;执行操作②出队1个元素并将该元素入队，队列变为:4，5，6，7，3;第二次执行操作①后队列变为:6，7，3;第二次执行操作②后队列变为:7，3，6;第三次执行完操作后，队列中只剩一个元素6，故本题选择C。 6.D 【解析】本题考查Python程序设计相关内容。分析程序段，推知:程序段通过调用randint(1,3)函数产生随机数，赋值给m，其可能值为:1，2，3。若m为1，执行内循环后，head值为0，则ans +=q[head]-->ans =1，A选项为可能值。若m为2，执行内循环后，head值分别为0、2，则ans 值为q[0](1)与q[2](14)的和，即ans =15，B选项为可能值。若m为3，执行内循环后，head值分别为0、2、6，则ans 值为q[0](1)、与q[2](14)与q[6](9)的和，即ans =24，C选项为可能值。变量 ans的值不可能是34。故本题答案是D选项。 7.C 【解析】本题考査Python程序综合应用。该程序段意图是维护一个循环队列，通过随机数生成和替换变换列表内的元素。需要注意的是，head和tail以随机位置开始，且q[head]要不等于生成的随机数num才进行插入，不然head会向前移一个位置，并清零当前位置的 q值。 A项 [1,2,3,4,5]:前四个元素说明均满足if判断条件，最后一次循环不满足循环条件，因此q[4]仍为0。不可能是[1,2,3,4,5]。 B项 [3,0,1,4,1]:说明head=2，q[head]=1，若q[4]=1，则会执行else，因此不可能是[3,0,1,4,1]。 C项 [5,0,1,2,3]:这是可能的结果。 D项 [1,0,0,4.3]:此结果项包含了小数点， 符号，列表中本应是整数，所以此项是不可能的 故选C。 8.C 本题考查Python程序执行与调试。假设选项C为输入的s值，运行程序过程如下: head=0,tail=0，程序运行后，d[1]=0,head=0,tail=1 head=0,tail=1，程序运行后，d[3]=1,head=0,tail=2 head=0,tail=2，程序运行后，d[2]=2,head=0,tail=3 head=0,tail=3，程序运行后，d[4]=3,head=1,tail=4 head=1,tail=4，程序运行后，d[1]=4,head=2,tail=5 head=2,tail=5，程序运行后，d[3]=5,head=3,tail=6 head=3,tail=6，程序运行后，d[2]=6,head=4,tail=7 运行后列表d的输出结果符合题意，其它选项均不能输出题目结果。故正确答案为:选项C 9.C 本题考查队列。C选项正确，分析程序功能，for语句为从左到右依次遍历字符串a中所有字符，if语句为如果当前队列为空或者当前值a[]大于队尾时，将 a存入队尾;第一个eif 语句为如果队列长度为1时，修改队首;第二个 elif 语句功能为如果队列长度大于1时并且a[大于队列中倒数第二个值时，将队尾更新为当前值。将字符a="takeiteasy”代入程序依次执行循环体语句，可得到最后res结果为[“a”，“e”nn"S”“y”1，因此本题选择C。 10.C 11. 3 p=i-1或p=p-1 tail-head que[head][1] 利润最大为13 【解析】本题考查程序分析。1、冒泡算法排序执行：第一次交换，lst[0][0]>lst[1][0]，第二次交换，lst[1][0]>lst[2][0]，第三次交换，lst[3][0]>lst[4][0]。故执行3次。 2、队列函数保证低利润订单前置，高利润后置，故需要移动指针，指向前一个订单，填写p=p-1或p=i-1。 3、当前程序if语句判断条件不完整，根据订单order[i][0]指向时间，可知该条件控制时间，可以使用队列长度控制时间，当订单时间大于队列长度，可知该订单时间较长，加入队列中并加上该时间的利润故填写tail-head。 4、当前订单利润大于队列中头订单利润，则减去低利润订单，加上高利润订单。故填写que[head][1]。 5、排序后结果为：[[1, 4], [1, 3], [2, 5], [2, 6], [3, 1], [3, 2]]。利润比较：[1, 4]>[1, 3]，ans+=4。[2, 5]进入队列，ans+=5。利润比较：[1, 4]<[2, 6]，ans-=4,ans+=6。[3, 1]进队列，ans+=1。[3, 1]<[3, 2],ans-=1,ans+=2。故ans=13，利润为13。 12.break flags[n][i]==True (tail[type]-head[type]+maxn)%maxn len(tables)>0 and head[i]!=tail[i] 或 tables and head[i]!=tail[i] 【解析】本题考查Python程序设计相关内容。本题涉及到循环队列的常见操作、桶排序、自定义函数等知识点。 第（1）小题，自定义函数gettype()的作用是输入人数返回对应的桌型，阅读主程序可知，数组size存储了四种桌型能够容纳的最大人数，因此此处要遍历各种桌型，比较当前输入的客人人数num与对应桌型可容纳人数size[i]的大小关系，如果能够容纳，则返回桌型对应的索引i并提前结束遍历以提高算法效率。故①处答案为：break。 第（2）小题，自定义函数checktable()的作用是得到对应桌型的编号列表。参数n表示桌型，结合主程序可知，数组nums存储了四种桌型的总量，数组flags存储了不同桌型中每一张桌子的使用情况，状态为True表示空桌，故此处需要遍历数组flags中对应桌型为n子列表中的元素，并将空桌对应的索引存储至数组ans中作为返回值。故②处答案为：flags[n][i]==True。 第（3）小题，考查循环队列的常见操作与状态判断。填空①处需要统计当前桌型type队列的元素个数，根据题意可知，该队列的队首指针为head[type]，队尾指针为tail[type]，程序变量说明循环队列的最大容量为maxn，可得出当前桌型type队列的元素个数为：(tail[type]-head[type]+maxn)%maxn，故③处答案为：(tail[type]-head[type]+maxn)%maxn。填空②处处理出队情况，经过自定义函数checktable判定后，若对应桌型有空余桌号且桌型队列中有等候元素，则进行出队操作，故④处答案为：len(tables)>0 and head[i]!=tail[i]。 学科网（北京）股份有限公司 $