4.1 队列结构及其实现 同步作业 教科版（2019）选择性必修1

4.1 队列结构及其实现 一、选择题 1．一个队列初始为空，若它的输入序列为a、b、c、d，则它的输出序列为（   ）。 A．d、c、b、a B．d、a、c、b C．a、b、c、d D．a、c、b、d 2．有一个非循环队列S如图所示，其中指针head指向队首元素的位置，指针tail指向队尾元素的下一个位置。 关于该队列说法正确的是（    ） A．队列中元素个数为tail-head+1 B．新元素入队时，指针head向右移动 C．元素出队时，指针tail向右移动 D．当tail==len（S）时，无法再入队新元素 3．下列对队列的描述，正确的是（   ） A．队列的特点是先进后出 B．在队列中，允许插入的一端称为队首，允许删除的一端称为队尾 C．刚建立的队列，队首指针和队尾指针均为0 D．出队操作时，先将队首指针加1，然后再将队首元素出队 4．“餐厅信息管理系统”由菜品管理、订单管理和客户管理三个模块组成。订单管理模块可以实现顾客点餐、订单结算和订单统计的功能。餐厅的碗碟都已植入了电子标签，在系统中可设定每个电子标签对应的菜品。顾客将选好菜品的托盘放入结算台，结算台读取电子标签信息，系统自动完成结算，顾客在刷卡区完成结算。在该系统中，可以利用队列来储存当前正在排队顾客的编号，head 指向队首元素，tail指向队尾元素的下一个位置，若 tail=head+3，则现在排队的顾客数量为 (　　) A．2 B．3 C．4 D．5 5．下列关于队列的描述中，正确的是（   ） A．在队列中只能删除数据 B．队列是先进后出的线性表 C．在队列中只能插入数据 D．队列是先进先出的线性表 6．有2个队列a和b，队首到队尾的元素依次分别为“5，7，9”和“6，4，8”。约定：T操作是指队列a中1个元素先出队，若大于队列b的队首元素则再入b队列，否则不入；Q操作是指队列b中1个元素先出队，若大于队列b的队尾元素则再入b队列，否则不入。则经过TTQQQQT系列操作后，队列b中的元素个数为（    ） A．1 B．2 C．3 D．4 7．某队列中存有12张扑克牌，如题图所示，游戏规则如下：①取队首扑克牌，然后加入到队尾，②打出队首扑克牌；重复①、②两个操作，直到队列为空。 若要根据上述规则用扑克牌打出“一条龙”游戏（注：总共13张牌，从队列中出牌的次序为“A2345678910JQK” ）。请你设计游戏，将扑克牌“10”放到初始队列中正确的位置（    ） A．放置在扑克牌6的后面 B．放置在扑克牌5与扑克牌K之间 C．放置在扑克牌2与扑克牌8之间 D．以上说法均错误 8．某种特殊的队列Q，支持以下三个操作： 操作Q1：若队列非空，队首元素出队，并输出； 操作Q2：若队列非空，队首元素出队； 操作Q3：一个元素入队； 以上任意一种操作后，若队列非空，新的队首元素仍为队列中所有元素的最小值。 若队列Q初始状态为空，依次进行Q3、Q2、Q1、Q2、Q3、Q1、Q3七次操作后，下列说法正确的是（    ） A．当前队列中的元素个数为2 B．输出的元素个数为2 C．第一个输出的元素肯定比当前队首元素大 D．队列初始状态是否为空对输出结果有影响 9．小王在使用队列解决问题的过程中，初始时，队列为空，队列的首指针和尾指针分别为head、tail，接着小王开始进行了一系列的操作，操作序列为：入队、入队、入队、出队、入队、入队、出队、出队、出队、入队、入队，则操作结束时head和tail的值分别为（   ） A．4 7 B．4 8 C．5 7 D．5 8 10．有如下Python程序段： st = [″h″,″a″,″p″,″*″,″p″,″Y″] que = [0]*20; key = 2 head,tail = 0, 0 for i in range (len(st)):    if ″a″ <= st[i] <= ″z″:      que[tail] = chr((ord(st[i]) - ord(″a″) + key)%26 + ord(″a″))      tail += 1    else:      head += 1 while head != tail:    print (que[head],end =″ ″)    head += 1 程序运行后，输出的结果是（   ） A．r r B．p p C．c r r a D．c r r A 11．假设队列的空间足够，队首指针head和队尾指针tail经过“出队、入队、出队、出队、入队、入队、出队”这一系列操作后，head=7，tail=9。则操作前的head和tail的值分别为（   ） A．11  12 B．2  5 C．3  6 D．3  5 12．队列的特点（   ） A．先进先出 B．先进后出 C．插入操作只能在队头进行 D．删除操作只能在队尾进行 13．有如下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 14．某单向队列存储空间足够，使用head记录队首元素所在的位置，tail记录队尾元素的下一个位置，经过“出队，入队，出队，出队，入队，出队”操作后，head=6，tail=8，则在操作前队列中元素的个数是（    ） A．0 B．2 C．4 D．6 15．已知字符″a″的ASCⅡ码值为97，有如下Python程序段： que=[" "]*20 head,tail=0,0 for i in range(3):     que[tail]=chr(97+i)     tail+=1 st=["b","c","d","a"] top=3 while head<tail and top>-1:     if st[top]==que[head]:         head+=1     else:         que[tail]=st[top]         tail+=1     top-=1 print(que[head:tail]) 执行该程序段，则输出的结果是（    ） A．[’c’，’d’，’c’] B．[’c’，’c’，’d’] C．[’c’，’’，’d’] D．[’c’，’d’] 16．列表q长度为20，q[0]至q[4]的值依次为'p'，'r'，'i'，'n'，'t'，执行如下程序段后，输出的最后一个字符为（    ）     head，tail=0，5     while head< tail：         if head%3=0：             print（q[head]）         else：             q[tail]=q[head]             tail+=1         head+=1 A．t B．n C．i D．r 17．某队列的数据结构如图所示，head 和tail 分别为队列的头、尾指针。现对该队列进行 以下操作：①队首元素出队输出②队首元素出队再入队，重复①②操作直到队列为空。 que     L      U      C      K      Y 0      1      2      3      4      5      … 若队列数据元素为“LUCKY”，则输出顺序是（    ） A．LYUKC B．LCYUK C．LCYKU D．LUCKY 18．某诊所叫号系统中，利用队列来储存当前正在排队病人的编号，head指向队首元素，tail指向队尾元素的下一个位置。若当前没有病人，则head与tail的关系是（   ） A．head!=tail B．head>tail C．head==tail D．head<tail 19．有1个队列，现有元素依次为1，2，3，4。约定：P操作是指1个入队，T操作是指队列中1个元素出队后再入队，Q操作是指队列中1个元素出队。则经过PPTQTPQ系列操作后，队列中队首到队尾的元素依次为（    ） A．1 B．1，3 C．3，4 D．3 20．在某餐厅点餐系统中， 利用队列来储存当前正在排队顾客的编号，head 指向队首元素，tail 指向队尾元素的下一个位置， 若 tail=head+3，则现在排队的顾客数量为（    ） A．2 B．3 C．4 D．5 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．C 【详解】本题主要考查队列数据结构。一个队列初始为空，若它的输入序列为a、b、c、d，则它的输出序列为a、b、c、d（先进先出、后进后出），故本题选C选项。 2．D 【详解】本题主要考查队列数据结构。由图可知，队列中元素个数为tail-head；新元素入队时，指针tail向右移动；元素出队时，指针tail向左移动； 当tail==len（S）时，无法再入队新元素，故本题选D选项。 3．C 【详解】本题考查队列。队列的特点是先进先出，因此A选项错误；允许插入的一端称为队尾，允许删除的一端称为队首，因此B选项错误；刚建立的队列，队首指针和队尾指针均指向下标为0的元素，即队首指针和队尾指针均为0，C选项正确；出队操作时，先将队首元素出队，然后将队首指针加1，因此D选项错误。故答案为：C。 4．B 【详解】本题主要考查队列数据结构。head 指向队首元素，tail指向队尾元素的下一个位置，若 tail=head+3，则现在排队的顾客数量为tail-tail=3，故本题选B选项。 5．D 【详解】本题主要考查队列的描述。队列是先进先出的线性表，在队尾插入数据，队首删除数据，故本题选D选项。 6．B 【详解】本题考查数据结构队列相关内容。结合队列先进先出特点，分析题目内容，可知： （1）执行“T”，队列a中1个元素先出队，即“5”出队，由于“5”不大于队列b中队首元素“6”，则不入队，a队元素为：“7，9”； （2）执行“T”，队列a中1个元素先出队，即“7”出队，由于“7”大于队列b中队首元素“6”，则将其入b队；b队元素为：“6，4，8，7”，a队元素为：“9”； （3）执行“Q”，队列b中1个元素先出队，即“6”出队，由于“6”不大于队列b中队尾元素“7”，则不入队，b队元素为：“4，8，7”； （4）执行“Q”，队列b中1个元素先出队，即“4”出队，由于“4”不大于队列b中队尾元素“7”，则不入队，b队元素为：“8，7”； （5）执行“Q”，队列b中1个元素先出队，即“8”出队，由于“8”大于队列b中队尾元素“7”，则再次入队，b队元素为：“7，8”； （6）执行“Q”，队列b中1个元素先出队，即“7”出队，由于“7”不大于队列b中队尾元素“8”，则不入队，b队元素为：“8”； （7）执行“T”，队列a中1个元素先出队，即“9”出队，由于“9”大于队列b中队首元素“8”，则将其入b队；b队元素为：“8，9”。 则经过TTQQQQT系列操作后，队列b中的元素个数为：2。故本题答案是B选项。 7．A 【详解】本题考查队列相关内容。按照游戏规则，以A选项为例，队列中扑克牌出队入队情况如图所示：。A选项可以得出“一条龙”，采用同样的方法，BC选项不能得到“一条龙”，故本题答案是A选项。 8．D 【详解】本题考查的是队列操作。队列是先进先出。当前队列中的元素个数为1；第一次Q1，由于队列为空，没有输出，第二次Q1，有输出，输出元素1个；无法判断第一个输出的元素比当前队首元素大。故本题应选D。 9．A 【详解】本题考查队列。初始时，队列为空，队首指针head和队尾指针tail的值均为0，队列不为空时，队首指针指向队首元素，队尾指针指向队尾元素的下一个位置，本题中共进行了7次入队操作和4次出队操作，因此最终head和tail的值分别为4、7。故答案为：A。 10．A 【详解】本题考查的是队列。阅读程序可知程序功能：遍历st列表，遇到小写字符则将其后移key位，再入队tail+1；遇到其他字符则出队head+1，最后输出队列里的元素。在列表st = ["h","a","p","**,"p","Y"]中，字符后移2位则变成 ["j","c","r","*","r","Y"]。遇到"*"出队一次，遇到"Y"出队一次，最后队列里的元素为rr，故答案选A。 11．C 【详解】本题考查队列的操作。队首指针head和队尾指针tail经过“出队、入队、出队、出队、入队、入队、出队”这一系列操作后，共出队4次，入队3次，所以head+4=7，tail+3=9，得到操作前的head和tail的值分别为3、6，所以选项C符合题意。故选：C。 12．A 【详解】本题主要考查队列数据结构。队列的特点是先进先出，插入操作只能在队尾进行，删除操作只能在队头进行，故本题选A选项。 13．D 【详解】本题主要考查Python程序的执行。分析程序可知，该程序模拟队列数据类型，如果i是偶数，则将s[i]入队列que[tail]，如果i是奇数，则将s[len(s)-i]入队列que[tail]，第一个for循环执行完，队列中的元素是“AFCDEB”，第二个for循环按照队列“先进先出”的规则依次出队，故以上程序运行后，打印出列表的情况是：AFCDEB，故本题选D选项。 14．C 【详解】本题主要考查队列的操作。经过“出队，入队，出队，出队，入队，出队”操作后， head =6, tail =8，可以得到操作前的 head =6-4(4次出队)=2, tail=8-2(2次入队）=6，所以原来队列中有6-2=4个元素，所以选项 C 符合题意。故选： C 。 15．A 【详解】本题考查数据结构栈、队列相关知识。Que为队列，st为栈。代码段功能是：当队首元素与栈顶元素相等时，队首元素出队，栈顶元素出栈；当队首元素与栈顶元素不相等时，将栈顶元素出栈并将其入队。循环结束时，队列中存在三个元素’c’、’d’、’c’，栈已空。最后输出队列元素，即[’c’，’d’，’c’]。故本题答案是A选项。 16．D 【详解】本题考查单向顺序队列的基本操作（数组实现）。根据队列基本操作可知程序段的功能是：当队列q非空时（空队列为head=tail），根据头指针的索引位置（head%3=0），分别执行“出队”操作或者“出队并入队”操作，再结合题意，本题求解的是最后一个出队元素。用表格法模拟该队列头、尾指针和“出队”操作的变化，如下表： head tail 队列q 出队字符 0 5 p，r，i，n，t P 3 7 n，t，r，i n 6 9 i，t，r i 9 11 t，r t 12 13 r r 综上所述，故选D。 17．C 【详解】本题主要考查队列数据结构。根据题意先执行①输出L，接着执行②，U为队首出队加入队尾，字符串为CKYU；再次执行①输出C，接着执行②，K为队首出队加入队尾，字符串为YUK；第三次执行①输出Y，接着执行②，U为队首出队加入队尾，字符串为KU；第四次执行①输出K，接着执行②，U为队首出队加入队尾，字符串为U；第五次执行①输出U。因此输出字符串为LCYKU，故本题选C选项。 18．C 【详解】本题考查队列。head、tail分别是队首和队尾指针，当队列为空时，指针head和tail指向同一个位置，即head==tail。故答案为：C。 19．D 【详解】本题考查数据结构队列相关内容。依据队列先进先出的特点，模拟其出队入队操作，如图所示：，经过PPTQTPQ系列操作后，队列中仅有元素3。故本题答案是D选项。 20．B 【详解】本题主要考查队列数据结构。head 指向队首元素，tail 指向队尾元素的下一个位置，则队尾元素的位置是tail-1，若 tail=head+3，则现在排队的顾客数量为tail-1-head+1=head+3-1-head+1=3，故本题选B选项。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$