第三章 线性数据的组织和存储 2023-2024学年高中信息技术粤教版(2019) 选修1

第三章 线性数据的组织和存储 学校:___________姓名：___________班级：___________考号：___________ 一、选择题 1．栈S初始状态为空栈，将序列3,2,5,7,1中元素逐一入栈，当栈空或入栈元素比桟顶元素大时则入栈，否则出栈至符合条件再入栈。序列所有元素入栈完毕后，栈内剩余元素出栈，直至栈空。则出栈的顺序是（    ） A．17523 B．37521 C．37512 D．32751 2．字符串“Hello,world!”的长度是（     ） A．11 B．12 C．13 D．14 3．约定:P操作是指1个元素入，O操作是指1个元素出栈，若有一组元素的入栈顺序为a、b、c、d，为了得到b、c、a、d的出栈顺序相应的P和O操作序列为（   ） A．PPOPOOPO B．PPOPOPOO C．PPOOPOPO D．PPPPOOOO 4．下列对栈的描述，正确的是（   ） A．栈的特点是后进后出 B．栈仅允许在表的一端进行插入或删除操作 C．入栈操作时，将把数据元素压入栈底 D．出栈操作时，先将栈顶指针加1，然后将栈顶元素取出 5．若用1表示进栈操作，用0表示出栈操作，若元素的进栈顺序是“q，w，e，r，t”，为了得到出栈序列“ewrtq”，则应进行的操作序列为(　　) A．1101010100 B．1110010100 C．1110011000 D．1110100100 6．某序列为a,b,c,d,经过入栈、出栈、入栈、入栈、出栈、出栈操作后，则出栈的序列是（   ） A．a,b,c B．a,c,b C．b,c,d D．b,a,c 7．字符串类型在Python中经常用到，以下关于字符串的表述不正确的是（   ） A．Python中只有“字符串”而无“字符”类型 B．Python中""和"  "是同一个字符串 C．Python中内置了许多字符串处理方法 D．字符串可以用“+”运算符进行连接运算 8．长度为5的循环队列que，que[0] 至que[4]的值依次为'a'，'b'，'c'，'d'，'e'，执行如下程序段后，输出的最后一个字符为 n=5 head = 0 tail= 4 que=['a','b','c','d','e'] while head!=tail： if head%4==0： print(que[head] ) else： tail=(tail+1) %n que[tail] =que[head] head=(head+1)%n print(que[head]) A．b B．c C．d D．e 9．操作Q为出队，R为入队，T为出队后入队，则序列1，2，3，4，5，按照操作顺序RRRTQRQR进行操作后，队列中的数字依次为（    ） A．1 4 5 B．2 3 5 C．1 3 5 D．2 4 5 10．一个底端封闭的圆柱形乒乓球收纳筒，最多可容纳4个乒乓球，筒的直径只允许一个球进出。初始时筒内自底向上已存有1，2号球，然后依次放入4个球，顺序为3，4，5，6号，则取出所有乒乓球的顺序可能是（   ） A．2,6,5,4,3,1 B．3,2,1,6,4,5 C．3,2,1,6,5,4 D．5,4,3,2,1,6 11．有1个队列，现有元素依次为1，2，3，4。约定：P操作是指1个入队，T操作是指队列中1个元素出队后再入队，Q操作是指队列中1个元素出队。则经过PPTQTPQ系列操作后，队列中队首到队尾的元素依次为（    ） A．1 B．1，3 C．3，4 D．3 12．有如下Python程序段： import random lst=['A'，'B'，'C'，'D'] st=[0]*len（lst） i，top=0，-1 while i<len（lst）：   k=random.randint（0，1）   if k==0：     top+=1     st[top]=lst[i]     i+=1   elif top!=-1：     lst[i]=st[top]     top-=1 执行该程序段后，lst的值不可能是（   ） A．['A'，'B'，'C'，'D'] B．['A'，'B'，'A'，'C'] C．['A'，'A'，'C'，'D'] D．['A'，'A'，'C'，'A'] 13．栈的出栈操作相当于（     ） A．在栈顶移除元素 B．在栈底移除元素 C．在栈中随机位置移除元素 D．在栈中指定位置移除元素 14．执行下列Python程序代码，当输入的数据为“ABCDE”，则输出的结果不可能的是（    ） from random import randint st = ["]*10; top=- 1; out=" s=input('s=') while s:     flag = randint(0,1)     if flag ==1：         top+=1；st[top]=s[0]         s=s[1:]     elif top!=- 1:         out+=st[top]；top-=1 while top!=- 1:     out +=st[top]；top -=1 print(out) A．CEDAB B．BDECA C．ABCED D．DCBEA 15．利用栈求逆波兰表达式（表达式由操作数和运算符组成）的方法是:从左往右扫描该表达式，遇到操作数时入栈；遇到运算符时，把处于栈上方的两个元素依次出栈，用运算符计算，并把计算结果压入栈中。如此反复操作，直至表达式扫描结束。当用该算法求逆波兰表达式abcd-*e/+f-的值时（abcdef表示不同的操作数），所使用的栈的深度至少为（   ） A．3 B．4 C．5 D．6 16．对于入栈顺序为1，2，3，4，5，6，7，8的序列，下列选项中不可能是出栈序列的是（   ） A．1，2，3，4，5，6，7，8 B．8，7，6，5，4，3，2，1 C．1，2，3，6，5，4，8，7 D．3，2，1，6，7，8，4，5 17．有如下Python程序段： a = [1,2,3,4,5];b = [3,2,5,1,4] stack =[];i = j = 0 while i < len(a):     stack.append(a[i])#将a[i]添加到stack末尾     i += 1     while len(stack)>0 and stack[-1] == b[j]:         stack.pop()#移除stack末尾元素         j +=1 执行该程序段后，stack中的元素个数为（   ） A．0 B．1 C．2 D．3 18．数字1,2,3依次进栈，则不可能的出栈顺序是 (　　) A．3,2,1 B．3,1,2 C．1,2,3 D．2,1,3 19．设栈S初始状态为空，元素A、B、C、D、E、F依次入栈，出栈的序列为D、F、E、C、B、A，则栈S的容量至少应该是（   ） A．5 B．4 C．3 D．2 20．下列数据中，不属于字符串类型的是（    ） A．"65" B．"python" C．True D．"nnez" 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．B 【详解】本题考查栈数据结构。2入栈时栈顶元素为3不满足条件，此时3出栈2入栈；5、7元素符合条件依次入栈；1入栈时不满足条件，7、5、2依次出栈，1入栈并出栈，因此出栈的顺序是37521，故选B。 2．B 【详解】本题考查字符串。字符串“Hello,world!”包括12个字符，包括逗号和感叹号。故答案为：B。 3．A 【详解】本题考查栈。首先a入栈，b入栈，b出栈，c入栈，c出栈，a出栈，d入栈，d出栈，此时即可符合入栈以及出栈顺序。因此相应的P和O操作序列PPOPOOPO。故答案为：A。 4．B 【详解】本题考查数据结构栈。栈的特点是先进后出，或后进先出，因此A选项错误；入栈操作时，将把数据元素压入栈顶，因此C选项错误；出栈操作时，先将栈顶元素取出，然后将栈顶指针减1，因此D选项错误；栈仅允许在表的一端进行插入或删除操作，栈的另一端是封闭的，B选项正确。故答案为：B。 5．B 【详解】本题主要考查栈的操作。为了得到出栈序列“ewrtq”，即e先出栈，按照进栈顺序，则qwe先进栈，对应111，接着是ew出栈，对应00，后面依次类推可得到应进行的操作序列为1110010100，故本题选B选项。 6．B 【详解】本题考查栈操作相关内容。栈的特点是：先进后出。第一步操作是入栈，即a入栈，栈中只有一个元素a；第二步操作是出栈，栈中元素a出栈，出栈序列为：a，此时栈空；第三步操作是入栈，即b入栈，栈中只有一个元素b；第四步操作是入栈，即c入栈，栈中有两个元素b、c；第五步操作是出栈，栈中元素c出栈，出栈序列为：a，c，此时栈中还有一个元素b；第六步操作是出栈，栈中元素b出栈，出栈序列为：a，c，b，此时栈空。故本题答案是B选项。 7．B 【详解】本题考查字符串。“”：是空字符串；“  ”：是空格；二者是不一样的。故答案为：B。 8．B 【详解】本题考查循环队列的基本操作。分析代码段得知：head在0、4时输出que[head]，head在1、2、3时，tail会发生移动，que会循环左移。经过多轮操作后，其输出序列是'a'、'e'、'b'、'd、'c'。输出的最后一个字符是'c'。本题正确答案为B。 9．A 【详解】本题主要考查队列的操作。按照操作顺序RRRTQRQR进行操作，首先1、2、3入队，再1出队再入队，此时队列元素是2、3、1，接着2出队4入队，此时队列元素是3、1、4，最后3出队5入队，此时队列中的数字依次为1、4、5，故本题选A选项。 10．C 【详解】本题考查栈操作相关内容。该题的栈大小只有四个位置，初始已经有1、2在内，进入为3、4、5、6。A选项，2出后，栈内只有1，接下来要出6，代表要将3、4、5、6依次全部先入栈。此时栈大小不足够，选项错误。B选项，3进，3、2、1依次出栈，接下来出栈的是6，说明4、5、6依次进栈，出栈顺序必须是6、5、4，选项错误。C选项，3进，3、2、1依次出栈，接下来出栈的是6，说明4、5、6依次进栈，出栈顺序必须是6、5、4，选项正确。D选项，先出5，说明要进栈3、4、5，此时栈大小不足够，选项错误。故本题答案是C选项。 11．D 【详解】本题考查数据结构队列相关内容。依据队列先进先出的特点，模拟其出队入队操作，如图所示：，经过PPTQTPQ系列操作后，队列中仅有元素3。故本题答案是D选项。 12．B 【详解】本题考查数据结构栈的相关操作。以下仅取部分随机数序列进行解析： A选项，若每次使用random．randint（0，1）时，都产生随机数0，即0、0、0、0，则只执行入栈操作（if部分），lst并未发生变化（elif部分未执行），其值仍然为['A'，'B'，'C'，'D'] ，选项A正确； C选项，当产生随机数依次为：0、1、0、0、0时，第一次值为0，将lst第一个元素'A'入栈，i+1变为1，第二次值为1时，将栈st中元素出栈且赋值给lst[1]，则lst[1]='A'，第三、四、五次值为0时，进行入栈操作，i值由1变为4，结束循环，lst中对应位置元素并未发生变化，lst中元素最终为：['A'，'A'，'C'，'D'] ，选项C正确； D选项，当产生随机数依次为：0、1、0、0、1、1、0时，第一次值为0，将lst第一个元素'A'入栈，i+1变为1，第二次值为1时，将栈st中元素出栈且赋值给lst[1]，则lst[1]='A'，第三、四次值为0时，进行入栈操作，st=['A'，'C']，第五、六次执行出栈，lst中元素为：['A'，'A'，'C'，'A]，第七次执行出栈，lst不变还是['A'，'A'，'C'，'A]，i值由1变为4，结束循环。选项D正确。 排除ACD，故本题答案是B选项。 13．A 【详解】本题考查栈。栈的出栈操作是移除最近添加的元素，即位于栈顶的元素。故选择A。 14．A 【详解】本题考查的是Python程序应用。分析程序可知，程序实现的是对字符串s进行入栈和出栈的操作，最后输出出栈的字符。选项B，入栈AB，出栈B，入栈CD，出栈D，入栈E，出栈ECA，符合栈的操作原则；选项C，入栈A，出栈A，入栈B，出栈B，入栈C，出栈C，入栈DE，出栈ED，符合栈的操作原则；选项D，入栈ABCD，出栈DCB，入栈E，出栈EA，符合栈的操作原则。排除BCD选项，故本题应选A。 15．B 【详解】本题考查栈结构及其实现。在求逆波兰表达式的值时， 当扫描到 a 时，将其入栈，深度为1。当扫描到 b 时，将其入栈，深度为2。当扫描到 c 时，入栈，深度为3。扫描到 d 时，入栈，深度为4。 当扫描到 - 运算符时，弹出栈顶的两个元素 d 和 c，将计算结果入栈，此时栈深度减少为3。 当扫描 * 运算符，出栈两个元素，计算结果入栈，栈深度为2。 扫描到 e，入栈，栈深度增加为3。 扫描到 / 运算符，出栈两个元素，计算结果入栈，栈深度为2。 扫描到 + 运算符，出栈两个元素，计算结果入栈，栈深度为1。 f 入栈，栈深度增加为2。 最后 - 运算符，再出栈两个元素，入栈，栈深度减少为1。 在整个过程中，栈的深度最大为4。因此，为了求逆波兰表达式 abcd-*e/+f- 的值，所使用的栈的深度至少为4。故答案为B选项。 16．D 【详解】本题考查栈的基本操作。栈的特点是先进后出，入栈顺序为1、2、3、4、5、6、7、8，当出栈序列为3、2、1、6、7、8时，说明栈中从栈顶到栈底的元素分别为5和4，因此出栈时5必在4之前，即3，2，1，6，7，8，4，5不可能是出栈序列。故答案为：D。 17．C 【详解】本题考查的是Python的栈操作。阅读程序可知，列表a是要入栈的数据，列表b是要出栈的数据。列表b可以看成队列，如果栈顶的数据与队列头数据相同，则出栈，队列出列。故先入栈1，2，3；出栈3，2；入栈4，5；出栈5。最后栈中数据[1, 4]。故本题应选C。 【点睛】 18．B 【详解】本题主要考查栈的操作。数字1,2,3依次进栈，若3先出栈，接着只能是2出栈，不可能是3、1、2，故本题选B选项。 19．A 【详解】本题考查栈相关内容。栈的特点是先入后出。栈S 的初始状态为空，元素A、B、C、D、E、F依次入栈，出栈顺序为D、F、E、C、B、A。D出栈，说明D要先进栈，此时C、B、A已在栈内，栈的容量至少为4；D出栈后，F出栈，说明F需要先进栈，此时E、C、B、A在栈内，栈的容量至少为5；后续出栈序列为E、C、B、A，期间没有元素再入栈，栈的容量不会再增加，故栈的容量至少为5。本题答案是A选项。 20．C 【详解】本题考查字符串。True：这是一个布尔类型的值，表示逻辑上的真。故答案为：C。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$