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

第三章 线性数据的组织和存储 学校:___________姓名：___________班级：___________考号：___________ 一、选择题 1．若元素入栈的顺序为1，2，3，4，5，6，且不允许连续三次入栈，则可能的出栈序列为（   ） A．2，4，3，1，6，5 B．2，5，4，6，3，1 C．2，3，5，1，6，4 D．1，2，3，6，5，4 2．有1个队列，队首到队尾的元素依次为a，b，c，d，e。约定：T操作是指队列中1个元素出队后再入队，Q操作是指队列中1个元素出队。则经过TTTQTTQ系列操作后，队列中队首到队尾的元素依次为（    ） A．b，d，e B．b，e，c C．c，e，a D．a，c，b 3．有如下 Python 程序段： s='HAPPY2023' s=s[3：]+s[1：3] print(s) 则输出 s 的结果是（　　） A．PY2023AP B．HAPY2023 C．PY2023HA D．HAPP2023 4．栈和队列的共同点是（   ） A．只允许在端点处插入和删除数据 B．都是先进后出 C．都是先进先出 D．没有共同点 5．栈s的最大长度是3，初始为空。经过一系列入栈、出栈操作，若元素出栈的顺序是“好”“运”“留”“下”“来”，则元素入栈序列可能的是（    ） A．“来”“下”“运”“好”“留” B．“来”“留”“好”“运”“下” C．“好”“留”“下”“运”“来” D．“留”“好”“来”“运”“下” 6．有1个栈初始为空，其元素入栈顺序依次为a，b，c，d，e，f，g，经若干次入栈和出栈操作后，栈底至栈顶元素分别为b，d，f，则第3个出栈元素为（    ） A．g B．c C．e D．a 7．栈S1从栈底到栈顶的元素顺序由1，2，3改为3，2，1，可借助初始均为空、长度均为3的栈S2、栈S3出入栈操作来实现，则需要出栈操作的总次数至少是（    ） A．6 B．7 C．8 D．9 8．栈S从栈底到栈顶的元素依次为1，2，3，队列Q初始为空。约定：U操作是指元素出栈后入队，H操作是指元素出队后再入队。经过UUH系列操作后，队列中队首到队尾的元素依次为（    ） A．2，1，3 B．3，1，2 C．1，3，2 D．2，3，1 9．有队列：20.67.89.2.4.3.16.27.1。队列中第一个入队的元素是20。则出队时，第三个出队的元素是（    ） A．89 B．2 C．6 D．1 10．下列关于队列的描述中，正确的是（   ） A．在队列中只能删除数据 B．队列是先进后出的线性表 C．在队列中只能插入数据 D．队列是先进先出的线性表 11．有如下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'] 12．若元素入栈的顺序是 1，2，3，4，5，6，不允许连续三次入栈，则可能的出栈序列为（   ） A．2，3，5，1，6，4 B．1，2，3，6，5，4 C．2，4，3，1，6，5 D．2，5，4，6，3，1 13．5个小朋友坐观光车，每次只允许一人从车后方进出（如图所示），可容纳1-3人乘坐，按12345的顺序上车，下车的顺序不可能是（    ） A．12345 B．21435 C．43215 D．21354 14．有如下Python程序段： import random a=['A'，'B'，'#'，'#'，'C'，'D'，'#'] stk=[0]*len（a）；top=-l for i in range（len（a））：       op=random. randint（0，1）        # 随机生成0或1       if op= =l and a[i]!='#"：               top+=l；stk[top]=a[i]               a[i]='#'       elif op= =0 and top!=-1 and a[i]= ='#'：              a[i]=stk[top]；top-=l 执行该程序段后，a的值不可能的是（   ） A．['A'，'B'，'#'，'#'，'C'，'D'，'#'] B．['#'，'#'，'#'，'#'，'#'，'#'，'#'] C．['#'，'B'，'#'，'#'，'C'；'D'，'A'] D．['#'，'#'，'A'，'B'，'C'，'D'，'#'] 15．以下有关栈和队列的说法正确的是（    ） A．栈和队列都是先进后出 B．栈和队列都是先进先出 C．队列元素前面只有一个，后面有多个 D．栈和队列只允许在端点插入和删除数据 16．某队列中存有12张扑克牌，如题图所示，游戏规则如下：①取队首扑克牌，然后加入到队尾，②打出队首扑克牌；重复①、②两个操作，直到队列为空。 若要根据上述规则用扑克牌打出“一条龙”游戏（注：总共13张牌，从队列中出牌的次序为“A2345678910JQK” ）。请你设计游戏，将扑克牌“10”放到初始队列中正确的位置（    ） A．放置在扑克牌6的后面 B．放置在扑克牌5与扑克牌K之间 C．放置在扑克牌2与扑克牌8之间 D．以上说法均错误 17．有“甲乙丙丁戊”5位小朋友按序沿着一条仅容一人通过的小道行走，途中有一个单向出口的山洞，可容纳2人前后站位休息，如图所示，则5人走出小道的顺序不可能的是（   ） A．甲乙丁戊丙 B．丁戊甲丙乙 C．乙甲丁戊丙 D．丙乙甲戊丁 18．队列m中有0，1，2，3，4，5六个整数，排在队首的元素依次出队，现在要将每个出队的元素都进行入栈、出栈的操作，同时在出栈时输出当前元素，则输出的元素顺序不可能是（   ） A．012345 B．134205 C．254310 D．135024 19．下列关于单向链表的说法正确的是（    ） A．必定有头指针和尾指针 B．每个节点都有一个后继节点 C．删除一个节点，需要修改两个指针 D．查找任一节点的算法时间复杂度为O(n) 20．向一个栈顶指针为head的链式栈中插入一个指针r指向的节点时（节点指针域为next），则应执行的操作是（   ） A．head.next=r B．r.next=head;head=r C．r.next=head.next;head.next=r D．r.next=head;head=head.next 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．A 【详解】本题考查栈操作。 选项B，1、2入栈，2出栈。假设下一个出栈为5，需要3、4、5入栈。不符合题意。选项C，1、2入栈，2出栈。3入栈，3出栈。4、5入栈，5出栈。现在4为栈顶，1无法先于4出栈。不符合题意。选项D，假如6要出栈，则4、5、6要入栈。故不符合题意。故正确答案为：选项A。 2．C 【详解】本题考查的是队列操作。根据题意得知队首到队尾经过TTT操作后，原队列变为d，e，a，b，c，经过Q操作队列变为e，a，b，c，再经过TT操作变为b，c，e，a，最后经过Q操作变为c，e，a，故选项C为正确答案。 3．A 【详解】本题考查的是Python切片操作。切片操作基本表达式：object[start_index : end_index : step]，step：正负数均可，其绝对值大小决定了切取数据时的“步长”，而正负号决定了“切取方向”，正表示“从左往右”取值，负表示“从右往左”取值。当step省略时，默认为1，即从左往右以增量1取值。start_index：表示起始索引（包含该索引本身）；该参数省略时，表示从对象“端点”开始取值，至于是从“起点”还是从“终点”开始，则由step参数的正负决定，step为正从“起点”开始，为负从“终点”开始。end_index：表示终止索引（不包含该索引本身）；该参数省略时，表示一直取到数据“端点”，至于是到“起点”还是到“终点”，同样由step参数的正负决定，step为正时直到“终点”，为负时直到“起点”。s='HAPPY2023'，s[3：]='PY2023'，s[1：3]='AP'，s=s[3：]+s[1：3]=PY2023AP，选项A正确。 4．A 【详解】本题考查了栈和队列的基本特性。栈和队列的共同点是都只允许在端点处插入和删除数据。具体来说：栈（Stack）是先进后出（LIFO）的数据结构，只允许在一端（称为栈顶）插入和删除数据。队列（Queue）是先进先出（FIFO）的数据结构，只允许在一端（称为队尾）插入数据，在另一端（称为队头）删除数据。因此，A选项是正确的。B和C选项分别描述了栈和队列的不同特性，而D选项显然是不正确的。故答案为：A。 5．B 【详解】本题考查的是栈的操作。栈是后进先出。栈s的最大长度是3，初始为空，若元素出栈的顺序是“好”“运”“留”“下”“来”，则“好”入栈可能是第1~3中的某个，故选项A错误；选项C中，“运”第二个出栈，此时栈内还有“留”“下”，出栈顺序“下”肯定在“留”之前，故选项C错误；选项D中“好”“运”出栈后，栈内还有“留”“来”，出栈顺序“来”肯定在“留”之前，故选项D错误。本题应选B。 6．C 【详解】本题考查的是栈的操作。栈的特点是：先进后出。其元素入栈顺序依次为a，b，c，d，e，f，g，经若干次入栈和出栈操作后，栈底至栈顶元素分别为b，d，f，故出栈顺序为：a，c，e……。故第三个出栈为e，选C。 7．B 【详解】本题考查的是栈的操作。依据题意，要将栈内3个元素，借助另外两个栈，实现顺序完全颠倒。首先栈中3个元素必须出栈（到其它栈）即3次出栈，3次入栈，也是3次出栈（从其它栈出栈）。由于可借助的栈只有2个，故其中一个元素还要多出1次到其它栈。故出栈操作的总次数至少是：3+3+1=7。选B。 8．D 【详解】本题考查数据结构栈与队列相关内容。栈的特点是先进后出，队列的特点是先进先出。执行U操作出栈后入队的元素是3，此时3是队首；继续执行U操作，出栈后入队的是2，此时队列中有元素3、2；再执行H操作，出队后再入队得到的顺序为2、3。经过UUH系列操作后，栈s中最后一个元素1出栈入队，所以得到结果为2、3、1。故本题答案是D选项。 9．A 【详解】本题考查队列。队列操作规则为：先进先出原则。 有队列：20.67.89.2.4.3.16.27.1，第一个入队的是20，第二个是67，第三个是89，则出队列时，第三个出队的是89。故正确答案为：选项A。 10．D 【详解】本题主要考查队列的描述。队列是先进先出的线性表，在队尾插入数据，队首删除数据，故本题选D选项。 11．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选项。 12．C 【详解】本题考查栈。对于A选项2，3，5，1，6，4，若按此顺序出栈，在出5之前必须先出4，A选项错误；对于B选项1，2，3，6，5，4，若按此顺序出栈，则必须连续入栈1，2，3，B选项错误；对于C选项2，4，3，1，6，5，按照入栈顺序1，2入栈，2出栈，3，4入栈，4出栈，3出栈，1出栈，5，6入栈，6出栈，5出栈，是可能的出栈序列，C选项正确；对于D选项2，5，4，6，3，1，若按此顺序出栈，则在出栈2之后需要连续三次入栈3，4，5，D选项错误；故答案为：C。 13．C 【详解】本题考查栈的 出栈入栈。观光车每次只允许一人从车后方进出，模拟了一个先进后出的栈结构。上车顺序为12345，需要判断给定的下车顺序是否可能实现。要达到43215的顺序，若4先下车，则此前车上有1234四个人，不符合题意。故答案为：C。 14．D 【详解】本题考查的是堆栈的操作。堆栈的操作原则先进后出。stk可以看做一个堆栈，阅读程序可知对列表a中的字母进行入栈和出栈操作。选项A没有进行入栈和出栈操作，有可能；选项B把字母全部压入栈，有可能；选项C对字母A进行入栈，最后出栈，有可能；选项D，先把字母A、B进行入栈，然后出栈，出栈顺序应为B、A，故选项D不可能。 15．A 【详解】本题主要考查栈和队列数据结构。栈和队列都是先进后出，队头只允许删除元素，队尾只允许插入元素，而栈只允许在栈顶插入和删除元素，故本题选A选项。 16．A 【详解】本题考查队列相关内容。按照游戏规则，以A选项为例，队列中扑克牌出队入队情况如图所示：。A选项可以得出“一条龙”，采用同样的方法，BC选项不能得到“一条龙”，故本题答案是A选项。 17．B 【详解】本题考查的是队列相关知识。选项B中，丁最先走出小道，则甲乙丙需要再洞内，不满足容纳2人前后站位休息，故选项B不可能。选B。 18．D 【详解】本题考查队列与栈。按照题目的要求，每个元素出队后立即入栈，然后进行可能的入栈和出栈操作。按照给出的序列135024进行分析：0出队->入栈（栈：[0]）；1出队->入栈->出栈（输出1，栈：[0]）；2出队->入栈（栈：[0,2]）；3出队->入栈->出栈（输出3，栈：[0,2]）；4出队->入栈（栈：[0,2,4]）；5出队->入栈->出栈（输出5，栈：[0,2,4]）；当前栈状态：[0,2,4]。接下来，按照输出顺序，应该输出0，这意味着0要在2和4之前出栈，但由于栈的后进先出（LIFO）特性，0不可能在2和4之前出栈。因此，输出135024是不可能的。故答案为：D。 19．D 【详解】本题考查单链表的相关知识点。A选项，每个单链表都有一个头指针，不一定有尾指针，故A错误；B选项，在单链表中，尾节点没有后继节点，故B错误；C选项，删除一个节点，只需要更改被删节点的前趋节点的指针即可，不需要修改两个，故C错误；D选项，查找任一节点，需要从头节点出发，其时间复杂度为O(n)，故D正确。本题答案为D 20．B 【详解】本题考查栈。栈顶指针为head，此时指针r指向的节点要进栈，由于是链式栈，因此先将r指向的节点的指针域指向head，即r.next=head，然后让head指向r，即head=r。故答案为：B。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$