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

教科版（2019）选修一4.1队列结构及其实现同步作业 学校:___________姓名：___________班级：___________考号：___________ 一、选择题 1．队列Q和栈S的初始值均为空，数字入栈先后顺序为1、2、3、4、5。P表示入栈，T表示元素出栈以后入队。在进行PPTTPPTPT操作后，队列中从队首到队尾的元素依次为（   ） A．2、1、3、4 B．2、1、4、5 C．1、2、4、5 D．2、1、4、3 2．队列属于（   ） A．线性结构 B．树结构 C．图结构 D．以上均不是 3．有“甲乙丙丁戊”5位小朋友按序沿着一条仅容一人通过的小道行走，途中有一个单向出口的山洞，可容纳2人前后站位休息，如图所示，则5人走出小道的顺序不可能的是（   ） A．甲乙丁戊丙 B．丁戊甲丙乙 C．乙甲丁戊丙 D．丙乙甲戊丁 4．有如下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 5．有1个队列，现有元素依次为1，2，3，4。约定：P操作是指1个入队，T操作是指队列中1个元素出队后再入队，Q操作是指队列中1个元素出队。则经过PPTQTPQ系列操作后，队列中队首到队尾的元素依次为（    ） A．1 B．1，3 C．3，4 D．3 6．列表a长度为6，a[0]至a[5]值依次为4，2，5，1，9。 que=[0]*7 head,tail=0,0 que[tail]=a[0] tail+=1 for i in range(1,len(a)):     if a[i]>que[tail-1]:         que[tail]=a[i]         tail+=1; head+=1     elif a[i] < que[head]:         que[tail]=a[i]         tail+=1 print(que[head:tail]) 执行以上程序段后，输出结果是（   ） A．4,7 B．5,1,9 C．2,5,1,9 D．4,7,2,5,1,9 7．某队列经过“出队”“入队”操作后，队首指针head=2，队尾指针tail=6，则该队列中剩余的元素个数是（   ） A．2 B．4 C．5 D．6 8．有以下Python程序段： import random k=10;que=[0]*2*k que[0]=random.randint(1,20) head=0;tail=1;i=1 while i<k:     a=random.randint(1,20)     if a%2!=que[tail-1]%2:         que[tail]=a         tail=tail+1     elif a%2!=que[head]%2:         que[tail]=que[head]         que[tail+1]=a         tail=tail+2         head=head+1     i=i+1 print(que[head:tail]) 运行该程序段后，输出结果不可能的是（   ） A．[20,1,10,5,4] B．[14,17,10,3,12] C．[5,16,5,4,13,20,11] D．[13,10,5,16,19,10,20] 9．有如下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'] 10．假设队列的空间足够，队首指针head和队尾指针tail经过“出队、入队、出队、出队、入队、入队、出队”这一系列操作后，head=7，tail=9。则操作前的head和tail的值分别为（   ） A．11  12 B．2  5 C．3  6 D．3  5 11．已知字符″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’] 12．某种特殊的队列Q，支持以下三个操作： 操作Q1：若队列非空，队首元素出队，并输出； 操作Q2：若队列非空，队首元素出队； 操作Q3：一个元素入队； 以上任意一种操作后，若队列非空，新的队首元素仍为队列中所有元素的最小值。 若队列Q初始状态为空，依次进行Q3、Q2、Q1、Q2、Q3、Q1、Q3七次操作后，下列说法正确的是（    ） A．当前队列中的元素个数为2 B．输出的元素个数为2 C．第一个输出的元素肯定比当前队首元素大 D．队列初始状态是否为空对输出结果有影响 13．下列关于队列的描述中，正确的是（   ） A．在队列中只能删除数据 B．队列是先进后出的线性表 C．在队列中只能插入数据 D．队列是先进先出的线性表 14．已知队列元素的的个数为5，则队首指针head和队尾指针tail的值不可能是（　　） A．head=1,tail=6 B．head=2,tail=6 C．head=5,tail=0 D．head=3,tail=2 15．列表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 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．B 【详解】本题考查队列和栈。根据操作规则，数字先入栈，然后出栈后入队。按照给定的操作序列PPTTPPTPT，首先数字1入栈，接着2入栈，然后2出栈入队，接着1出栈入队，然后3入栈，接着4入栈，接着4出栈入队，接着5入栈，然后5出栈入队，依次类推。最终队列中从队首到队尾的元素依次为2、1、4、5。故答案为：B。 2．A 【详解】本题考查数据结构相关内容。数据结构分为集合、线性结构、树结构、图结构。队列属于线性结构，其操作特点是：先进先出。故本题答案是A选项。 3．B 【详解】本题考查的是队列相关知识。选项B中，丁最先走出小道，则甲乙丙需要再洞内，不满足容纳2人前后站位休息，故选项B不可能。选B。 4．A 【详解】本题考查的是队列。阅读程序可知程序功能：遍历st列表，遇到小写字符则将其后移key位，再入队tail+1；遇到其他字符则出队head+1，最后输出队列里的元素。在列表st = ["h","a","p","**,"p","Y"]中，字符后移2位则变成 ["j","c","r","*","r","Y"]。遇到"*"出队一次，遇到"Y"出队一次，最后队列里的元素为rr，故答案选A。 5．D 【详解】本题考查数据结构队列相关内容。依据队列先进先出的特点，模拟其出队入队操作，如图所示：，经过PPTQTPQ系列操作后，队列中仅有元素3。故本题答案是D选项。 6．B 【详解】本题考查的是队列操作。阅读程序可知，程序依次将列表a插入队列que中，如果列表a的值大于队尾，则查入队列，队头出列；如果比队头小，则查入队列。a[0]至a[5]值依次为4，2，5，1，9。 a[0]=4，将4插入队列，队列依次为：4； a[1]=2，满足比队头小，2插入队列，队列依次为：4，2； a[2]=5，满足大于队尾，5入队，4出队，队列依次为：2，5； a[3]=1，满足比队头小，1插入队列，队列依次为：2，5，1； a[4]=9，满足大于队尾，9入队，2出队，队列依次为：5，1，9； 故本题应选B。 7．B 【详解】本题考查队列相关内容。队首指针指向队首元素，队尾指针指向队尾元素的下一个位置，则队首元素位置是2，队尾元素位置是5，共有5-2+1=4个元素。故本题答案是B选项。 8．D 【详解】队列本题考查的知识点是本题考查的知识点是队列的相关知识。该程序段是一个简单的模拟程序，它使用一个循环来生成一系列随机整数，并将这些整数存储在一个队列中，同时保证队列中相邻的数字的奇偶性不同。程序首先生成一个长度为2k的队列，并将第一个元素设置为一个随机整数。然后，程序进入一个循环，该循环将生成k个随机整数，并将它们插入到队列中。在每次迭代中，程序会生成一个新的随机整数a，并检查它与队列中最后一个元素以及第一个元素是否具有相同的奇偶性。如果a与最后一个元素的奇偶性不同，则将a插入到队列的末尾。如果a与第一个元素的奇偶性不同，则将a插入到第一个元素之前，并将第一个元素移动到队列的末尾。通过这种方式，程序确保队列中相邻元素的奇偶性不同，A、B、C选项有可能。故答案为D选项。 9．A 【详解】本题考查的是队列应用。阅读程序可知，可以将q看成一个队列，将字符串a从后往前依次进入队列q。字符串索引是3的倍数时，则将队列q的队头排到队尾。a="Python"，i值为5、4时，依次入队['n','0']；i值为3时，队头排到队尾['0','n']；i值为2、1时，依次入队['0','n'，'t','y']；i值为0时，队头排到队尾['n','t','y','0']。故本题应选A。 10．C 【详解】本题考查队列的操作。队首指针head和队尾指针tail经过“出队、入队、出队、出队、入队、入队、出队”这一系列操作后，共出队4次，入队3次，所以head+4=7，tail+3=9，得到操作前的head和tail的值分别为3、6，所以选项C符合题意。故选：C。 11．A 【详解】本题考查数据结构栈、队列相关知识。Que为队列，st为栈。代码段功能是：当队首元素与栈顶元素相等时，队首元素出队，栈顶元素出栈；当队首元素与栈顶元素不相等时，将栈顶元素出栈并将其入队。循环结束时，队列中存在三个元素’c’、’d’、’c’，栈已空。最后输出队列元素，即[’c’，’d’，’c’]。故本题答案是A选项。 12．D 【详解】本题考查的是队列操作。队列是先进先出。当前队列中的元素个数为1；第一次Q1，由于队列为空，没有输出，第二次Q1，有输出，输出元素1个；无法判断第一个输出的元素比当前队首元素大。故本题应选D。 13．D 【详解】本题主要考查队列的描述。队列是先进先出的线性表，在队尾插入数据，队首删除数据，故本题选D选项。 14．B 【详解】本题主要考查队列数据结构。head=2，tail=6，则队列元素的个数为6-2=4，故本题选B选项。 15．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。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$