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

第三章 线性数据的组织和存储 一、选择题 1．使用键盘在word软件中输入“bliokocke”其中“”代表撤销操作（如oni表示撤销最近输入的“i”保留on），编程模拟其输入过程，合适的数据结构和最后输入的字母是（   ） A．栈  block B．队列  block C．队列  bicke D．栈  blook 2．有一个栈，栈顶到栈底的元素依次为4，1，3，2若栈顶元素是偶数则先出栈，再将偶数整除2后重新入栈，若栈顶元素是奇数，则直接出栈。若入栈和出栈各算一个操作，则经过6次操作后，栈中余下的元素个数为（ ） A．1 B．2 C．3 D．4 3．栈s的最大长度为4，初始已有两个元素在栈内，栈底为a，栈顶为b，经过一系列入栈、出栈操作，若元素入栈的顺序是c，d，e，f，则可能的出栈序列为（   ） A．c，a，b，e，f，d B．b，d，f，e，c，a C．a，b，d，c，e，f D．b，e，f，c，d，a 4．一个栈的初始状态为空，若它的输入序列为a、b、c、d，则它的输出序列为(    ) A．a、b、c、d B．d、c、b、a C．b、a、c、d D．d、b、a、c 5．有一个栈s，经过一系列入栈、出栈操作，从栈顶到栈底的元素依次为e、f、g、h，并且已知元素i已入栈并出栈，则这五个元素的入栈顺序可能为（   ） A．e,f,g,h,i B．f,i,g,h,e C．g,I,f,e,h D．h,i,g,f,e 6．栈和队列的共同点是（   ） A．只允许在端点处插入和删除数据 B．都是先进后出 C．都是先进先出 D．没有共同点 7．设栈S 的初始状态为空，元素a,b,c,d,e,f依次入栈，出栈顺序为b,d,c,f,e,a,则栈S的容量至少是（   ） A．2 B．3 C．4 D．5 8．下列关于队列的描述中，正确的是（   ） A．在队列中只能删除数据 B．队列是先进后出的线性表 C．在队列中只能插入数据 D．队列是先进先出的线性表 9．“餐厅信息管理系统”由菜品管理、订单管理和客户管理三个模块组成。订单管理模块可以实现顾客点餐、订单结算和订单统计的功能。餐厅的碗碟都已植入了电子标签，在系统中可设定每个电子标签对应的菜品。顾客将选好菜品的托盘放入结算台，结算台读取电子标签信息，系统自动完成结算，顾客在刷卡区完成结算。在该系统中，可以利用队列来储存当前正在排队顾客的编号，head 指向队首元素，tail指向队尾元素的下一个位置，若 tail=head+3，则现在排队的顾客数量为 (　　) A．2 B．3 C．4 D．5 10．队列Q从队首到队尾的元素依次为1，2，3，4，栈S初始为空。约定：H操作是指元素出队后入队，T操作是指元素出队后入栈。经过HTTHT操作后，栈S中从栈底到栈顶的元素依次为（    ） A．1，2，4 B．2，3，1 C．3，1，2 D．4，2，1 11．用一个底端封闭的圆柱形塑料筒来放取乒乓球，筒的直径只允许一个球进出，且该筒最多可容纳3 个乒乓球。若放入球的编号依次为1、2、 3、4、5，则取出球的顺序可能是（   ） A．4、 3、 5、 2、 1 B．2、 4、 3、 1、 5 C．5、 4、 3、 2、 1 D．1、 5、 4、 3、 2 12．某单向队列存储空间足够，使用head记录队首元素所在的位置，tail记录队尾元素的下一个位置，经过“出队，入队，出队，出队，入队，出队”操作后，head=6，tail=8，则在操作前队列中元素的个数是（    ） A．0 B．2 C．4 D．6 13．有如下程序段： bt=["A","B","C","D",None,"E","F"] result=[] stack=[] i=0 while stack or (i<len(bt) and bt[i] is not None):     if i < len(bt) and bt[i] is not None:         stack.append(i)         i=2*i+1     else:         i=stack.pop()         result.append(bt[i])         i=2*i+2 print("-".join(result)) 则程序运行后输出的结果为（   ） A．A-B-D-C-E-F B．D-B-E-F-C-A C．D-B-A-E-C-F D．A-B-C-D-E-F 14．有如下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 15．栈S初始状态为空栈，将序列3,2,5,7,1中元素逐一入栈，当栈空或入栈元素比桟顶元素大时则入栈，否则出栈至符合条件再入栈。序列所有元素入栈完毕后，栈内剩余元素出栈，直至栈空。则出栈的顺序是（    ） A．17523 B．37521 C．37512 D．32751 16．一个序列的入栈顺序为9,8,7,6,5,4。若7第一个出栈，则下列出栈序列中不可能的是（   ） A．7,8,9,6,5,4 B．7,8,9,5,6,4 C．7,9,8,4,5,6 D．7,8,9,6,4,5 17．若已知元素的入栈顺序是a,b,c,d,其出栈序列为Q1,Q2,Q3,Q4,则Q2,Q4不可能是（   ） A．a和c B．a和b C．b和d D．c和d 18．若队列Q1中保存整数，队列Q2中保存运算符，依次执行下述各步操作： ①从Q1中依次出队两个操作数a和b； ②从Q2中出队一个运算符op； ③执行相应的运算a op b； ④将运算结果入队Q1中。 假设Q1中的操作数依次是11，3，2，0，2，Q2中的运算符依次是//，*，-，+。最终Q1队首保存的值是（   ） A．-2 B．-1 C．0 D．1 19．下列哪一项不是队列的特性（     ） A．元素有序 B．允许在一端添加，在另一端移除 C．支持随机访问 D．以作为缓冲区使用 20．设栈S初始状态为空，元素A、B、C、D、E、F依次入栈，出栈的序列为D、F、E、C、B、A，则栈S的容量至少应该是（   ） A．5 B．4 C．3 D．2 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．A 【详解】本题考查数据结构。输入过程中，需要按照先进后出的原则，即最后输入的字符最先被撤销，因此可以使用栈来模拟。栈的特性正好符合这种撤销操作的需求。最后输入的字母为：block。故答案为：A。 2．B 【详解】本题考查的是栈的操作。栈是先进后出，后进先出。栈顶到栈底的元素依次为4，1，3，2。4是偶数，第1次操作出栈；整除2后为2，第2次操作重新入栈；2是偶数，第3次操作出栈；整除2后为1，第4次操作重新入栈；1是奇数，第5次操作直接出栈；1是奇数，第6次操作直接出栈。经过6次操作后，栈顶到栈底的元素依次为3，2。选项B正确。 3．B 【详解】本题考查栈的基本操作。在栈的操作中，元素的入栈和出栈是遵循"先进后出"的原则的。题目中给定了栈的最大长度为4，初始已有两个元素在栈内，栈底为a，栈顶为b。经过一系列入栈、出栈操作，需要判断给定的元素入栈顺序是否可能产生给定的出栈序列。元素b比元素a后入栈，因此元素a不可能比元素b先出栈，A、C选项错误；元素b出栈，元素c，d入栈，元素d出栈，元素e，f入栈，元素f出栈，元素e出栈，元素c出栈，元素a出栈，可以实现b，d，f，e，c，a的出栈序列，B选项正确；元素b出栈，元素c，d，e入栈，元素e出栈，元素f入栈，元素f出栈，但此时栈顶为元素d，而不是元素c，D选项错误。故答案为：B。 4．B 【详解】本题考查的栈的操作。堆栈是一个后进先出的数据结构，若它的输入序列为a、b、c、d，则它的输出序列为d、c、b、a。故本题应选B。 5．D 【详解】本题考查栈操作相关内容。在栈的操作中，元素的入栈和出栈原则是：先进后出。从栈顶到栈底的元素依次为e、f、g、h且元素i已入栈并出栈，则说明e、f、g、h尚未出栈，按照先进后出原则，其入栈顺序可能为：（1）h、i、g、f、e；（2）h、g、i、f、e；（3）h、g、f、i、e；（4）h、g、f、e、i；。故本题答案是D选项。 6．A 【详解】本题考查了栈和队列的基本特性。栈和队列的共同点是都只允许在端点处插入和删除数据。具体来说：栈（Stack）是先进后出（LIFO）的数据结构，只允许在一端（称为栈顶）插入和删除数据。队列（Queue）是先进先出（FIFO）的数据结构，只允许在一端（称为队尾）插入数据，在另一端（称为队头）删除数据。因此，A选项是正确的。B和C选项分别描述了栈和队列的不同特性，而D选项显然是不正确的。故答案为：A。 7．B 【详解】本题考查的是栈相关知识。栈是先入后出。栈S 的初始状态为空，元素a，b，c，d，e，f依次入栈，出栈顺序为b，d，c，f，e，a，则先入栈a、b，出栈b；再入栈c、d，出栈d、c；再入栈e、f，出栈f、e、a。整个过程栈中最多元素为3个，故栈S的容量至少是3，选项B正确 8．D 【详解】本题主要考查队列的描述。队列是先进先出的线性表，在队尾插入数据，队首删除数据，故本题选D选项。 9．B 【详解】本题主要考查队列数据结构。head 指向队首元素，tail指向队尾元素的下一个位置，若 tail=head+3，则现在排队的顾客数量为tail-tail=3，故本题选B选项。 10．B 【详解】本题考查的是栈和队列的操作。队列是先进先出，栈是后进先出。操作过程队列Q和栈S变化过程如下： 操作 队列Q 栈S 初始 1，2，3，4 H 2，3，4，1 T 3，4，1 2 T 4，1 2，3 H 1，4 2，3 T 4 2，3，1 故本题应选B。 11．B 【详解】本题考查的是栈的相关知识。栈是先进后出。依据题意可知，栈中存储最多3个元素。若放入球的编号依次为1、2、 3、4、5，则第一个出栈的球可能为：1、2、3，故选项A、C错误。因为筒最多可容纳3，故第2个出栈不可能为5，选项D错误。故本题应选B。 12．C 【详解】本题主要考查队列的操作。经过“出队，入队，出队，出队，入队，出队”操作后， head =6, tail =8，可以得到操作前的 head =6-4(4次出队)=2, tail=8-2(2次入队）=6，所以原来队列中有6-2=4个元素，所以选项 C 符合题意。故选： C 。 13．C 【详解】本题主要考查Python中stack()用法。分析程序可知，前3轮循环，即当i=0、1、3时均满足if判断条件，此时stack=[0,1,3]，接下来i=2*i+1=7不满足if判断条件，执行else部分， i=stack.pop()=3，result.append(bt[i])=["D"]，i=2*i+2=8，继续执行else，i=stack.pop()=1，result.append(bt[i])=["D","B"]，i=2*i+2=4，不满足if判断条件，继续执行else部分，i=stack.pop()=0，result.append(bt[i])=["D","B","A"]，此时结合选项可知程序运行后输出的结果为D-B-A-E-C-F，选C选项。 14．C 【详解】本题考查的是Python的栈操作。阅读程序可知，列表a是要入栈的数据，列表b是要出栈的数据。列表b可以看成队列，如果栈顶的数据与队列头数据相同，则出栈，队列出列。故先入栈1，2，3；出栈3，2；入栈4，5；出栈5。最后栈中数据[1, 4]。故本题应选C。 【点睛】 15．B 【详解】本题考查栈数据结构。2入栈时栈顶元素为3不满足条件，此时3出栈2入栈；5、7元素符合条件依次入栈；1入栈时不满足条件，7、5、2依次出栈，1入栈并出栈，因此出栈的顺序是37521，故选B。 16．C 【详解】本题主要考查栈数据结构。一个序列的入栈顺序为9,8,7,6,5,4。若7第一个出栈，第二个出栈的不可能是9，8出栈后才可以出9，故出栈序列中不可能的是7,9,8,4,5,6，故本题选C选项。 17．B 【详解】本题考查栈结构相关内容。入栈顺序是a、b、c、d，其出栈序列共14种，分别是：abcd、abdc、acbd、acdb、adcb、bacd、badc、bcad、bcda、bdca、cbad、cbda、cdba、dcba。对比四个选项，B选项不可能出现，故本题答案是B选项。 18．B 【详解】本题考查队列。从队列Q1中依次出队两个操作数a和b，分别为11和3。从队列Q2中出队一个运算符op，为//。执行相应的运算a//b，结果为3。将运算结果3入队队列Q1中。依次执行下一个操作，从Q1中出队2和0，从Q2中出队*，执行相应的运算，结果为2*0=0，将结果入队Q1中。依次执行下一个操作，从Q1中出队2和3，从Q2中出队-，执行相应的运算，结果为2-3=-1，将结果入队Q1中。依次执行下一个操作，从Q1中出队0和-1，从Q2中出队+，执行相应的运算，结果为0+(-1)=-1，将结果入队Q1中。因此，最终队列Q1队首保存的值是-1。故答案为：B。 19．C 【详解】本题考查队列。队列不支持随机访问，只能在一端添加元素，在另一端移除元素。故答案为：C。 20．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选项。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$