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

第三章 线性数据的组织和存储 学校:___________姓名：___________班级：___________考号：___________ 一、选择题 1．若有一批元素的出栈顺序为“i,n,p,u,t”，其入栈顺序不可能是（   ） A．n,i,t,u,p B．n,i,u,t,p C．t,u,p,n,i D．i,n,p,u,t 2．队列Q从队首到队尾的元素依次是1，3，5，栈S从栈底到栈顶的元素依次是2，4，6，现约定：A操作是指元素出队后入栈，B操作是指元素出栈后入队。经过BAAB系列操作后，队列中队首到队尾的元素依次为（    ） A．5,2,1 B．5,2,4 C．5,6,1 D．5,6,3 3．队列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 4．下列哪个操作可以实现字符串的大小写转换（     ） A．str.lower() B．str.upper() C．str.capitalize() D．以上均可 5．有如下Python程序段，运行程序后，其输出结果不可能是（   ） import random stack=['', '', '', '', ''] s, i, top="ABCDE", 0, -1 while i < len(s):     if random. randint (0, 10) % 2 == 0:         top +=l         stack[top] = s[i]         i += 1     elif top>=0:         print(stack[top] , end='')         top -= l while top >= 0:     print(stack[top] , end='')     top -= l A．ABCDE B．EDCBA C．DCEAB D．BEDCA 6．有如下Python程序段： st=[0]*10 a=[4，6，1，7，2，8，6] top=0；st[top]=a[0] for i in range(1,len(a))： while top！=-1 and a[i]<st[top]：   top-=1 top+=1 st[top]=a[i] 执行该程序段后，变量top的值为（    ） A．-1 B．1 C．2 D．3 7．栈和队列的共同特点是（     ） A．都是线性表 B．都只允许在表的一端进行插入或删除 C．操作受限的线性表 D．允许在两端进行插入和删除 8．设栈S和队列Q的初始状态为空,元素按e1,e2,e3,e4,e5,e6的顺序依次通过栈S后进入队列Q。若队列Q中的元素依次e2,e4,e3,e6,e5,e1,则栈S的容量至少为（   ） A．6 B．4 C．3 D．2 9．一个栈的初始状态为空，若它的输入序列为a、b、c、d，则它的输出序列为(    ) A．a、b、c、d B．d、c、b、a C．b、a、c、d D．d、b、a、c 10．某诊所叫号系统中，利用队列来储存当前正在排队病人的编号，head指向队首元素，tail指向队尾元素的下一个位置。若当前没有病人，则head与tail的关系是（   ） A．head!=tail B．head>tail C．head==tail D．head<tail 11．5个小朋友坐观光车，每次只允许一人从车后方进出（如图所示），可容纳1-3人乘坐，按12345的顺序上车，下车的顺序不可能是（    ） A．12345 B．21435 C．43215 D．21354 12．有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 13．字符串“Hello,world!”的长度是（     ） A．11 B．12 C．13 D．14 14．下列关于数据结构的说法正确的是（    ） A．“撤销”操作，是“队列”的应用 B．排队就餐， 是“栈”的应用 C．“链表”存储相邻节点不需要连续空间 D．“树”中每个节点的前后都只有一个相邻节点 15．元素x1、x2、x3、x4、x5、x6依次入栈，若第1个出栈的元素是x4，则不可能是第3个出栈的元素是（   ） A．x1 B．x2 C．x3 D．x5 16．有一个空栈，若元素“P”、“y”、“t”、“h”、“o”、“n”依次入栈，其中“o”第一个出栈。则当所有元素全部出栈后，下列说法正确的是（   ） A．出栈的最后一个元素一定为“P” B．出栈的最后一个元素一定为“n” C．元素“h”一定比“P”、“y”、“t”先出栈 D．元素“P”、“y”、“t”、“h”、“o”的出栈序列是不确定的 17．有一个空栈，规定用I表示一个元素入栈，用O表示一个元素出栈。现经过IIOIOOIO系列操作后，元素的出栈顺序是4，1，3，2，则元素的入栈顺序是（   ） A．1,3,4,2 B．3,4,1,2 C．2,3,1,4 D．1,4,3,2 18．有如下 Python 程序段： s = input('请输入一串小写字母') head =  0; tail = 0; top = -1 s1 = [""]*((len(s)+1)//2) s2 = [""]*(len(s)//2) for i in range(len(s)): if i % 2 == 0: s1[tail] = s[i] tail += 1 else: top += 1 s2[top] = s[i] x = "" while head < tail and top > -1: x = s1[head] + x head += 1 x = x + s2[top] top -= 1 print(x) 执行该程序段，输入字符串“abcdefg”，则输出的结果是（   ） A．acegbdf B．acegfdb C．gecafdb D．ecafdb 19．小王在使用队列解决问题的过程中，初始时，队列为空，队列的首指针和尾指针分别为head、tail，接着小王开始进行了一系列的操作，操作序列为：入队、入队、入队、出队、入队、入队、出队、出队、出队、入队、入队，则操作结束时head和tail的值分别为（   ） A．4 7 B．4 8 C．5 7 D．5 8 20．下列对栈的描述，正确的是（   ） A．栈的特点是后进后出 B．栈仅允许在表的一端进行插入或删除操作 C．入栈操作时，将把数据元素压入栈底 D．出栈操作时，先将栈顶指针加1，然后将栈顶元素取出 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．B 【详解】本题考查栈。栈的特点是先进后出。对于选项A，入栈顺序为n,i,t,u,p，可能的进出栈过程为：n进栈，i进栈，i出栈，n出栈，t进栈，u进栈，p进栈，p出栈，u出栈，t出栈，符合出栈顺序“i,n,p,u,t”；对于选项B，入栈顺序为n,i,u,t,p，若先入栈n和i，i出栈，n出栈，接着入栈u，入栈t，入栈p，p出栈，此时u要先于t出栈，不符合出栈顺序“i,n,p,u,t”；对于选项C，入栈顺序为t,u,p,n,i，可能的进出栈过程为：t进栈，u进栈，p进栈，n进栈，i进栈，i出栈，n出栈，p出栈，u出栈，t出栈，符合出栈顺序；对于选项D，入栈顺序为i,n,p,u,t，可能的进出栈过程为：i进栈，i出栈，n进栈，n出栈，p进栈，p出栈，u进栈，u出栈，t进栈，t出栈，符合出栈顺序。故答案为：B。 2．D 【详解】本题考查栈、队列相关内容。栈的特点是后进先出，队列的特点是先进先出。初始状态，队列Q从队首到队尾的元素依次是1，3，5，栈S从栈底到栈顶的元素依次是2，4，6。 第一次，执行“B”操作，栈S中元素（6）出栈后入队，此时，栈S从栈底到栈顶的元素依次是2，4；队列Q从队首到队尾的元素依次是1，3，5，6。 第二次，执行“A”操作，队列Q中元素（1）出队后入栈，此时，栈S从栈底到栈顶的元素依次是2，4，1；队列Q从队首到队尾的元素依次是3，5，6。 第三次，执行“A”操作，队列Q中元素（3）出队后入栈，此时，栈S从栈底到栈顶的元素依次是2，4，1，3；队列Q从队首到队尾的元素依次是5，6。 第四次，执行“B”操作，栈S中元素（3）出栈后入队，此时，栈S从栈底到栈顶的元素依次是2，4，1；队列Q从队首到队尾的元素依次是5，6，3。 则经过经过BAAB系列操作后，队列中队首到队尾的元素依次为：5，6，3。故本题答案是D选项。 3．B 【详解】本题考查队列和栈。根据操作规则，数字先入栈，然后出栈后入队。按照给定的操作序列PPTTPPTPT，首先数字1入栈，接着2入栈，然后2出栈入队，接着1出栈入队，然后3入栈，接着4入栈，接着4出栈入队，接着5入栈，然后5出栈入队，依次类推。最终队列中从队首到队尾的元素依次为2、1、4、5。故答案为：B。 4．D 【详解】本题考查Python字符串。Python提供了多种字符串大小写转换的方法，包括将字符串转为小写(str.lower()), 大写(str.upper())，或者仅首字母大写(str.capitalize())。故答案为：D。 5．C 【详解】本题考查堆栈。选项C，ABCD进栈，D，C出栈，E进栈。则栈里ABE，出栈为E，B，A。最终出栈为D，C，E，B，A。A在栈底，这时栈顶为B，不可能先于栈顶出栈。故选择C选项。 6．C 【详解】本题考查的是栈的操作。阅读程序可知，先入栈a[0]，然后遍历列表a剩余元素，如果大于栈顶元素继续入栈，否则弹出栈顶元素。因此程序执行完后栈内元素为：126，故top值（top初始为0）为2。故选C。 7．C 【详解】本题考查栈和队列。栈和队列都是线性表，但操作受限，栈只能在一端进行插入和删除，队列在两端操作，但必须遵循先进先出规则。故答案为：C。 8．C 【详解】本题考查栈的入栈和出栈操作。入栈和出栈的操作顺序是：e1 入、e2 入、e2 出、e3 入、e4 入、e4 出、e3 出、e5 入、e6 入、e6 出、e5 出、e1 出。e4入栈时，栈中有3个元素e1、e2、e3；e6入栈时，栈中也有3个元素e1、e5、e6；这两个时候栈容量为3，其它情况栈中都不超过3个元素，所以答案为3。故答案为：C。 9．B 【详解】本题考查的栈的操作。堆栈是一个后进先出的数据结构，若它的输入序列为a、b、c、d，则它的输出序列为d、c、b、a。故本题应选B。 10．C 【详解】本题考查队列。head、tail分别是队首和队尾指针，当队列为空时，指针head和tail指向同一个位置，即head==tail。故答案为：C。 11．C 【详解】本题考查栈的 出栈入栈。观光车每次只允许一人从车后方进出，模拟了一个先进后出的栈结构。上车顺序为12345，需要判断给定的下车顺序是否可能实现。要达到43215的顺序，若4先下车，则此前车上有1234四个人，不符合题意。故答案为：C。 12．C 【详解】本题考查的是队列操作。根据题意得知队首到队尾经过TTT操作后，原队列变为d，e，a，b，c，经过Q操作队列变为e，a，b，c，再经过TT操作变为b，c，e，a，最后经过Q操作变为c，e，a，故选项C为正确答案。 13．B 【详解】本题考查字符串。字符串“Hello,world!”包括12个字符，包括逗号和感叹号。故答案为：B。 14．C 【详解】本题主要考查数据结构的描述。“撤销”操作，是“栈”的应用；排队就餐， 是“队列”的应用；“链表”存储相邻节点不需要连续空间；“树”结构不一定是二叉树，也不一定只有一个相邻节点，故本题选C选项。 15．A 【详解】本题考查栈的基本操作。由于第1个出栈的元素是x4，此时，栈中从栈顶到栈底的元素分别为x3、x2、x1，因此元素x1最早为第4个出栈，故答案为：A。 16．C 【详解】本题考查栈的操作。根据题干描述，“O”第一个出栈，此时“n”还没有进栈，最后一个出栈的也可能是“n”也可能是“p”，故A、B选项错误。因入栈顺序为“p”“y”“t”“h”“o”，此时中间没有出栈的，故出栈的顺序为“o”“h”“t”“y”“p”是固定的。故D选项错误。故答案为：C。 17．B 【详解】本题考查栈的常见操作。 “I”表示入栈，“O”表示出栈。操作序列为“IIOIOOIO”，元素的出栈序列为“4，1，3，2”。根据操作序列可推演处操作过程如下所示： 操作序列 执行操作 IIOIOOIO 2出栈 IIOIOOI 2入栈 IIOIOO 1，3出栈 IIOI 1入栈 IIO 4出栈 II 3，4入栈 由此可得，入栈序列为：3，4，1，2。故答案为：B。 18．D 【详解】本题主要考查Python及数据结构的应用。根据题意，s1为队列，s2为栈，每读取s一个字母时，偶数次取出放入s1中，奇数次取出放入s2中，存储后再依次取出，取时必须同时满足 head<tail and top>-1，故只取最少次数。故输入字母串 abcdefg 时，存入队列中的为aceg，存入栈中的为bdf。队列从head指向处顺序取出，反接在x中；栈从top指向处逆序取出，正接在x中，故输出的结果是ecafdb，故本题选D选项。 19．A 【详解】本题考查队列。初始时，队列为空，队首指针head和队尾指针tail的值均为0，队列不为空时，队首指针指向队首元素，队尾指针指向队尾元素的下一个位置，本题中共进行了7次入队操作和4次出队操作，因此最终head和tail的值分别为4、7。故答案为：A。 20．B 【详解】本题考查数据结构栈。栈的特点是先进后出，或后进先出，因此A选项错误；入栈操作时，将把数据元素压入栈顶，因此C选项错误；出栈操作时，先将栈顶元素取出，然后将栈顶指针减1，因此D选项错误；栈仅允许在表的一端进行插入或删除操作，栈的另一端是封闭的，B选项正确。故答案为：B。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$