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

第三章 线性数据的组织和存储 学校:___________姓名：___________班级：___________考号：___________ 一、选择题 1．字符串“Hello,world!”的长度是（     ） A．11 B．12 C．13 D．14 2．有如下Python程序：     s1=[0]*5; s2=[0]*5; top1=-1; top2=-1     a=[9,2,5,6,1]     for i in range(len(a)):        while top1 !=-1 and a[i] < s1[top1]:            top2 += 1            s2[top2] = s1[top1]            top1 -= 1        top1 += 1; s1[top1] = a[i]        while top2 != -1:            top1 += 1            s1[top1] = s2[top2]            top2 -= 1     print(s1[top1]) 执行程序后的输出结果是（   ） A．1 B．5 C．6 D．9 3．在Python中，如何创建一个空队列（     ） A．queue = [] B．queue = {} C．from queue import Queue; q = Queue() D．queue = () 4．若已知元素的入栈顺序是1，2，3，4，其出栈顺序不可能的是（   ） A．1，2，3，4 B．3，1，4，2 C．3，2，1，4 D．2，1，4，3 5．有1个栈初始为空，其元素入栈顺序依次为s,t,r,w,u,y,m，若经过进栈和出栈操作后，栈底至栈顶元素分别为t,w,y，则第3个出栈元素为（   ） A．m B．w C．u D．s 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，e，则该序列的出栈顺序不可能为（ ） A．b，a，d，c，e B．d，c，b，a，e C．d，c，e，a，b D．c，b，a，e，d 9．有如下 Python 程序段： s='HAPPY2023' s=s[3：]+s[1：3] print(s) 则输出 s 的结果是（　　） A．PY2023AP B．HAPY2023 C．PY2023HA D．HAPP2023 10．有两个栈，q1和q2.初始为空，约定：（N，d）操作是元素d进行q1入栈，清空q2；（B）操作是q1栈顶元素从q1出栈，q2入栈；（F）操作是q2栈顶元素从q2出栈，q1入栈。经过下列操作，q1栈顶元素为（   ） （N，http://baidu.com） （N，http://sohu.com） （N，http://python123.io） （B） （B） （F） （N，http://cctv.com） （B） A．http://baidu.com B．http://sohu.com C．http://python123.io D．http://cctv.com 11．若已知元素的入栈顺序是a,b,c,d,其出栈序列为Q1,Q2,Q3,Q4,则Q2,Q4不可能是（   ） A．a和c B．a和b C．b和d D．c和d 12．栈和队列的共同特点是（     ） A．都是线性表 B．都只允许在表的一端进行插入或删除 C．操作受限的线性表 D．允许在两端进行插入和删除 13．下列哪一项不是队列的特性（     ） A．元素有序 B．允许在一端添加，在另一端移除 C．支持随机访问 D．以作为缓冲区使用 14．有如下Python程序段： q=[-1]*40 head=tail=0 n=40 for i in range(1,n):     if i%4 == 0 or i%7 == 0:         q[tail]=i         tail+=1 print(tail-head) 执行该程序段后，输出的结果是（   ） A．14 B．13 C．9 D．1 15．某种表达式可通过栈来求解，方法如下：遍历表达式，遇到数值则入栈，遇到运算符，则将栈顶两个数值出栈，用该运算符计算，并将结果入栈。按照该方法直到遍历完表达式，栈顶元素即为表达式的运算结果。若X代表入栈，Y代表出栈，当利用栈求表达式“1 2 3 * +”时，栈的操作序号为（    ） A．XXXYYYYX B．XXXYYXYYX C．XXYYXXYY D．XXXXYYYXXYYYX 16．有“甲乙丙丁戊”5位小朋友按序沿着一条仅容一人通过的小道行走，途中有一个单向出口的山洞，可容纳2人前后站位休息，如图所示，则5人走出小道的顺序不可能的是（   ） A．甲乙丁戊丙 B．丁戊甲丙乙 C．乙甲丁戊丙 D．丙乙甲戊丁 17．栈和队列的共同点是（   ） A．只允许在端点处插入和删除数据 B．都是先进后出 C．都是先进先出 D．没有共同点 18．下列有关字符串的描述，正确的是（   ） A．字符串的负索引从字符串的末端开始编号，第一个位置为-1 B．字符串的长度是指字符串中所包含的字符个数，但不包括空格 C．字符串的元素个数是有限的，只能由1个或多个字符组成 D．字符串的正索引的第一个位置为1 19．向一个栈顶指针为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 20．数字1,2,3依次进栈，则不可能的出栈顺序是 (　　) A．3,2,1 B．3,1,2 C．1,2,3 D．2,1,3 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．B 【详解】本题考查字符串。字符串“Hello,world!”包括12个字符，包括逗号和感叹号。故答案为：B。 2．D 【详解】本题考查的是Python栈的操作。如果s1栈顶元素比列表a元素值大，则将s1栈顶元素出栈压入s2栈，然后将列表a元素压入s1栈，最后将s2栈出栈压入s1栈。按上述流程，s1栈从栈低到栈顶元素是升序排列。a=[9,2,5,6,1]，故最后s1=[1, 2, 5, 6, 9]，栈顶元素是9。故本题应选D。 3．C 【详解】本题考查队列创建。在Python中，要创建一个空的队列，应该导入queue模块并使用Queue()类。故答案为：C。 4．B 【详解】本题考查的是栈的操作。栈的特点是先进后出，后进先出。选项B中，已知元素的入栈顺序是1，2，3，4，第一个出栈是3，则现在从栈低到栈顶依次为1，2，即1的出栈肯定在2的后面，故选项B的出栈顺序不可能。选B。 5．C 【详解】本题考查栈。初始栈为空，元素入栈顺序为s，t，r，w，u，y，m。最终栈底至栈顶元素为t，w，y，说明s，r，u已经出栈。此时栈内元素从上到下为y，w，t。因为s和r已经出栈，所以第一个出栈的是s，第二个出栈的是r，第三个出栈的就是u。故答案为：C。 6．B 【详解】本题考查数据结构队列。要打印的数据是按照先进先出的原则存储在缓冲区中的，因此该缓冲区的逻辑结构是队列，故答案为B。 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．C 【详解】本题主要考查栈数据结构。选项C中先入栈a、b、c、d，接着出栈d、c，再入栈e并出栈，此时只能先出栈b，不可能先出栈a再出栈b，故本题选C选项。 9．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正确。 10．B 【详解】本题考查栈。 用q1和q2来存储，模拟浏览器访问（N，d）、前进（F）、后退（B）操作，每一步操作后 ql 栈顶元素分别为：http://baidu.com、http://sohu.com、http://python123.io、http://sohu.com、http://baidu.com、http://sohu.com、http://cctv.com、http://sohu.com。故正确答案为：选项B。 11．B 【详解】本题考查栈结构相关内容。入栈顺序是a、b、c、d，其出栈序列共14种，分别是：abcd、abdc、acbd、acdb、adcb、bacd、badc、bcad、bcda、bdca、cbad、cbda、cdba、dcba。对比四个选项，B选项不可能出现，故本题答案是B选项。 12．C 【详解】本题考查栈和队列。栈和队列都是线性表，但操作受限，栈只能在一端进行插入和删除，队列在两端操作，但必须遵循先进先出规则。故答案为：C。 13．C 【详解】本题考查队列。队列不支持随机访问，只能在一端添加元素，在另一端移除元素。故答案为：C。 14．B 【详解】本题考查的是队列操作。程序功能是将1~39中能被4或7整除的数入队，输出队列中元素的个数，即求1~39中能被4或7整除的数的个数。1~39中能被4或7整除的数共有13个，故选B。 15．B 【详解】本题考查数据结构栈操作相关内容。利用栈求表达式“1 2 3 * +”，依据求解方法，“1”为数值，执行入栈操作“X”；“2”为数值，执行入栈操作“X”；“3”为数值，执行入栈操作“X”；“*”为运算符，则“3”、“2”依次出栈，即“YY”，执行：3*2操作，并将结果6入栈“X”；“+”为运算符，则“6”、“1”依次出栈，即“YY”，执行：6+1操作，并将结果7入栈“X”。则栈的操作序号为：XXXYYXYYX。故本题答案是B选项。 16．B 【详解】本题考查的是队列相关知识。选项B中，丁最先走出小道，则甲乙丙需要再洞内，不满足容纳2人前后站位休息，故选项B不可能。选B。 17．A 【详解】本题考查了栈和队列的基本特性。栈和队列的共同点是都只允许在端点处插入和删除数据。具体来说：栈（Stack）是先进后出（LIFO）的数据结构，只允许在一端（称为栈顶）插入和删除数据。队列（Queue）是先进先出（FIFO）的数据结构，只允许在一端（称为队尾）插入数据，在另一端（称为队头）删除数据。因此，A选项是正确的。B和C选项分别描述了栈和队列的不同特性，而D选项显然是不正确的。故答案为：A。 18．A 【详解】本题考查字符串。字符串的长度是指字符串中所包含的字符个数，字符串中如有空格，1个空格也算1个字符，因此B选项错误；字符串的元素个数是有限的，只能由0个或多个字符组成，因此C选项错误；字符串的正索引的第一个位置为0，而不是1，因此D选项错误；字符串的负索引从字符串的末端开始编号，第一个位置为-1。故答案为：A选项。 19．B 【详解】本题考查栈。栈顶指针为head，此时指针r指向的节点要进栈，由于是链式栈，因此先将r指向的节点的指针域指向head，即r.next=head，然后让head指向r，即head=r。故答案为：B。 20．B 【详解】本题主要考查栈的操作。数字1,2,3依次进栈，若3先出栈，接着只能是2出栈，不可能是3、1、2，故本题选B选项。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$