第一章 认识数据和数据结构 2024-2025学年高中信息技术粤教版(2019) 选修1

第一章 认识数据和数据结构 学校:___________姓名：___________班级：___________考号：___________ 一、选择题 1．已知列表a=[2,3,4,5]，要将列表a更新为[1,2,3,4,5]，则下列可实现该功能的操作是（   ） A．a="1"+a B．a.append(1) C．a=[1]+a D．a=1+a 2．某二叉树的树形结构如图所示， 其后序遍历结果为“物技化数英语”，则中序遍历结果为（   ） A．语数英物化技 B．物数技化语英 C．语数物化技英 D．化物技英数语 3．以下关于Python自带数据结构的运算结果中正确的是哪一项？（ ） A．l=[1，2，3，4，5]del l[2：4]则运算之后1为[1，2，3] B．basket=['apple'，'banana'，'apple'，'orange']fruit=set（basket）len（fruit） 的结果是5 C．basket=['apple'，'banana'，'apple'，'orange'，'melo']fruit=set（basket）len（fruit） 的运算结果是3 D．1=[2，1，3，5，4]remove(3)sort()则运算之后1为[1,2,4,5] 4．以下关于数据结构的描述，不正确的是（   ） A．数据的逻辑结构是指数据元素之间的逻辑排列和对应关系 B．数据的存储结构包括数据元素的存储及数据元素之间关系的存储 C．数据的运算是指对数据施加的操作，包括删除、查找、插入数据等 D．数据结构设计时不需要考虑编程实现和数据处理的效率 5．数据结构在程序设计中的作用不包括（     ） A．提高程序运行效率 B．方便数据的存储和检索 C．增加代码的复杂度 D．有助于算法设计 6．树结构中元素之间存在的关系是（   ）。 A．—对一 B．一对多 C．多对一 D．多对多 7．已知Python列表a=［'W'，'o'，'r'，'d'］，依次执行a.pop()、a.append(1)、a.append(d)操作，列表a的值为（　　） A．［'W'，'o'，'r'，'d'］ B．［'W'，'o'，'r'，'1'，'d'］ C．［'o'，'r'，'d'，'1'，'d'］ D．［'1'，'d'，'o'，'r'，'d'］ 8．下列关于数据结构的说法正确的是（   ） A．常见的线性关系数据结构有数组、队列、栈、树和图等 B．链表是一种适合用于组织、存储涉及频繁插入与删除的数据结构 C．Excel软件中的撤销操作体现了队列的思想 D．计算机操作系统中文件夹的组织与管理，通常借助栈来完成 9．如图所示的线性数据结构，下列说法错误的是(  ) A．正向编号，首元素索引号为0，向后走，索引号递增 B．反向编号，尾元素编号为-1，向首元素方向依次递减 C．线性数据结构只包括队列与栈 D．栈：后进先出，添加和删除都在栈顶实现，队列：先进先出，删除在队首，添加在队尾 10．以下说法错误的是（   ） A．栈是一种先进后出的数据结构 B．队列是一种先进先出的数据结构 C．C++ STL中的map查询时间复杂度为0(1) D．使用哈希时，可能会发生哈希冲突 11．栈S初始为空，将1,4,1,1,4,5,2,5,3,2,3依次入栈，当某个元素入栈后，如果此刻栈顶元素和栈中其他元素相同，将这两个元素间的所有数据出栈（包括这两个元素），再继续后面数据的入栈操作，最后栈中栈顶到栈底的元素依次为（   ） A．1,4 B．1,4,5,3 C．4,1 D．3,5,2 12．栈S从栈底到栈顶的元素依次为1，2，3，队列Q初始为空。约定：U操作是指元素出栈后入队，H操作是指元素出队后再入队。经过UUHU系列操作后，队列中队首到队尾的元素依次为（   ） A．2,1,3 B．3,1,2 C．1,3,2 D．2,3,1 13．列表d中存入了一列数据如表所示，采用顺序查找的方法查找数据，以下叙述正确的是（    ） d[1] d[2] d[3] d[4] d[5] d[6] d[7] d[8] d[9] d[10] 12 33 15 －7 11 13 17 19 43 29 A．顺序查找只能从d[1]开始，逐一进行比较 B．无论是否找到，顺序查找必须完成对所有的数据的比对查找 C．在数据规模较大的情况下，顺序查找的平均查找效率低于对分查找 D．必须先将数据排序之后才可以采用顺序查找 14．某二叉树的前序遍历为EFHIGJK，中序遍历为HFIEJKG。则该二叉树根节点的右孩子节点是（    ） A．E B．F C．G D．H 15．单车道胡同路边停车，先进去的车只能从另一出口出来，阅读程序代码，下列说法错误的是(  ) listque=[]                                  #定义列表listque存储停车状况 max=8                                       #停车位最大容量 while(True):                                     print(' 1.停车')                  # 表示换行打印     print('2. 开车离开')     print('3. 查看停车库')     print('其他. 退出')     x=input("输入你的选择:")                #输入选择项     if x=='1':         if len(listque)<max:             print("还有"+str(max-len(listque))+"个停车位。")                 listque.append(input("请输入停车车牌:"))              else:             print("对不起，停车位已满。")     elif x=='2':         if len(listque)==0:                              print("停车库为空。")         else:             print(listque.pop(0)+"开出。")        elif x=='3':         print(listque)                           else:         break A．listque.append(  )语句的作用是输入停车车牌 B．listque.pop(0)表示开车离开，删除停车车牌 C．此程序的数据结构方式是先进先出的栈 D．while(True)语句表示永远执行循环 16．下面关于数据结构描述不正确的是（   ） A．数据元素是数据的最小单位，数据项是具有独立含义的基本单位 B．EXCEL 中的“撤销”操作可以使用栈来实现 C．数据结构指的是数据之间的相互关系，即数据的组织形式 D．队列的特点是先进先出，栈的特点是先进后出，后进先出 17．有如下python程序段： a=[[3,2],[2,3],[7,1],[1,0]] p=head=0 while a[p][1]!=head:     print(a[p][0],end="->")      print(a[p][0]) 上述程序段要遍历链表中的所有元素，划线处应添加的代码是（） A．p+=1 B．a[p][1]+=1 C．p=a[p][1] D．a[p][1]=a[a[p][1]][1] 18．下列关于线性表的描述，正确的是（    ） A．链表在访问、插入、删除节点操作时，算法效率比数组高 B．栈是一种“先进先出，后进后出”的线性表结构 C．循环队列是首尾相连的队列，数据入队时无需考虑是否会“溢出” D．字符串是元素个数有限的线性表结构 19．栈S和队列Q的初始状态为空，每个数据按照进栈、出栈、入队、出队的顺序操作。已知栈S中依次有字母0、T、P、Y、H、N进栈，队列Q依次有数据P、Y、T、H、O、N出队。则栈S的容量至少是（   ） A．2 B．3 C．4 D．6 20．数据结构设计的主要目的是（     ） A．只为了数据的存储 B．反映数据之间的逻辑关系并提高数据处理效率 C．仅仅为了美观地展示数据 D．无特定目的，仅作为编程习惯 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．C 【详解】本题考查Python数据结构。a=[1]+a使用列表拼接操作，将列表[1]与a拼接，得到[1,2,3,4,5]，符合题目要求。故答案为：C。 2．B 【详解】本题考查二叉树相关内容。结合树形结构及后序遍历结果，可知该二叉树形态如图所示：。则其中序遍历结果为：物数技化语英。故本题答案是B选项。 3．D 【详解】本题主要考查Python数据结构。l =[1，2，3，4，5]del 1[2：4]则运算之后1为[1，2，5]；basket=['apple'，'banana'，'apple'，'orange']，set() 函数创建一个无序不重复元素，fruit=set（basket），故len（fruit） 的结果是3；同理basket=['apple'，'banana'，'apple'，'orange'，'melo']fruit=set（basket）len（fruit） 的运算结果是4；l=[2，1，3，5，4]remove(3)sort()则运算之后l为[1,2,4,5]，故本题选D选项。 4．D 【详解】本题考查数据结构基本概念。数据的逻辑结构是指数据元素之间的关系和组织方式，包括线性结构、树形结构、图形结构等，A选项正确；数据的存储结构是数据在计算机中的表⽰（⼜称映像）⽅法，是数据的逻辑结构在计算机中的存储实现，因此在存储时应包含两⽅⾯的内容——数据元素本⾝及数据元素之间的关系，B选项正确；数据的运算是指对数据施加的操作，包括插入、删除、查找数据等，C选项正确；在设计的过程中，需要根据实际需求选择合适的算法，并考虑编程实现和数据处理的效率（时间复杂度），D选项错误。故本题答案是D选项。 5．C 【详解】本题考查数据结构。良好的数据结构设计应降低代码复杂度，而不是增加。故选择C。 6．B 【详解】本题主要考查数据结构。树结构是一种非线性存储结构，存储的是具有一对多关系的数据元素的集合，故本题选B选项。 7．B 【详解】本题主要考查Python列表的操作。已知Python列表a=［'W'，'o'，'r'，'d'］，依次执行a.pop()、a.append(1)、a.append(d)操作，即先删除最后一个元素'd'，再添加元素'1'和'd'，此时列表a的值为［'W'，'o'，'r'，'1'，'d'］，故本题选B选项。 8．B 【详解】本题考查数据结构相关内容。A选项，常见的线性关系数据结构有数组、队列、栈，非线性结构有树和图等，选项错误。B选项，链表是一种适合用于组织、存储涉及频繁插入与删除的数据结构，选项正确。C选项，Excel软件中的撤销操作体现了栈的思想，选项错误。D选项，计算机操作系统中文件夹的组织与管理，通常借助树结构来完成，选项错误。故本题答案是B选项。 9．C 【详解】本题主要考查数据结构。正向编号，首元素索引号为0，向后走，索引号递增；反向编号，尾元素编号为-1，向首元素方向依次递减；线性数据结构包括队列、栈、线性表及数组等；栈：后进先出，添加和删除都在栈顶实现，队列：先进先出，删除在队首，添加在队尾，故本题选C选项。 10．C 【详解】本题主要考查数据结构的描述。C++ STL中的map查询时间复杂度为O(logN)，故本题选C选项。 11．C 【详解】本题考查数据结构栈操作相关内容。栈的特点是先进后出。1、4、1依次入栈，栈顶到栈底的元素依次为1、4、1，符合出栈条件，1、4、1出栈，栈空；1、4、5、2、5依次入栈，栈顶到栈底的元素依次为5、2、5、4、1，符合出栈条件，5、2、5出栈，栈中剩余元素为4、1；3、2、3依次入栈，栈顶到栈底的元素依次为3、2、3、4、1，符合出栈条件，3、2、3出栈，栈中剩余元素为4、1。故本题答案是C选项。 12．D 【详解】本题考查栈、队列相关内容。栈的特点是后进先出，队列的特点是先进先出。初始状态，栈中从栈顶到栈底的元素为3、2、1，队列为空。第一次操作：U，即将栈顶元素3出栈后入队，队列中队首元素为3；第二次操作：U，即将栈顶元素2出栈后入队，队列中队首元素为3，队尾元素为2；第三次操作：H，即将队首元素3出队后再入队，队列中队首元素为2，队尾元素为3；第四次操作：U，即将栈顶元素1出栈后再入队，队列中从队首到队尾各元素依次为2、3、1。故本题答案是D选项。 13．C 【详解】本题考查顺序查找相关内容。顺序查找是一种基本的查找算法，它按照数据元素的顺序从前往后依次查找目标元素。顺序查找的基本思路是将目标元素与当前位置的元素进行比较，若相等则查找成功；否则继续向后查找，直到找到目标元素或搜索到末尾位置为止。顺序查找适用于线性表的顺序存储结构和链式存储结构，对数据的存储和记录的有序性没有特殊要求。顺序查找的缺点是当数据量较大时，平均查找长度会较大，导致查找效率较低。A选项，顺序查找既可以从表头开始，也可以从表尾开始，选项说法错误。B选项，在查找过程中若找到目标元素，则无需再继续查找，选项说法错误。C选项，在数据规模较大的情况下，顺序查找的平均查找效率低于对分查找，选项说法正确。D选项，顺序查找不需要提前对数据进行排序，选项说法错误。故本题答案是C选项。 14．C 【详解】本题考查数据结构二叉树操作相关内容。由前序遍历为EFHIGJK，中序遍历为HFIEJKG知，该二叉树形态如图所示：。则该二叉树根节点的右孩子节点是G。故本题答案是C选项。 15．C 【详解】本题主要考查队列数据结构及Python程序实现。分析程序可知，listque.append( )语句的作用是输入停车车牌；listque.pop(0)表示开车离开，删除停车车牌；此程序的数据结构方式是先进先出的队列；while(True)语句表示永远执行循环，故本题选C选项。 16．A 【详解】本题考查数据结构相关内容。A选项，数据项是数据的不可分割的最小单位，数据元素是具有独立含义的基本单位，选项错误。B选项，栈结构可以很方便的用来实现操作的“撤销和恢复”功能，例如：浏览器的前进和后退、EXCEL的撤销和恢复等，选项正确。C选项，数据结构指的是数据之间的相互关系，即数据的组织形式，选项正确。D选项，队列的特点是先进先出，栈的特点是先进后出，后进先出，选项正确。故本题答案是A选项。 17．C 【详解】本题主要考查Python程序的调试。用二维数组模拟链表，第一个元素是当前节点的数值，第二个元素是下一个节点的索引，划线处需要更新p为下一个节点的索引，即当前节点的a[p][1]，故本题选C选项。 18．D 【详解】本题主要考查线性表的描述。链表在访问节点操作时，算法效率比数组低；栈是一种“先进后出，后进先出”的线性表结构；循环队列是首尾相连的队列，数据入队时需要考虑是否会“溢出”；字符串是元素个数有限的线性表结构，故本题选D选项。 19．B 【详解】本题考查数据结构栈与队列操作相关内容。栈的特点是先进后出，队列的特点是先进先出。队列Q中P先出队，表明在栈S中，P先出栈，则O、T、P均已在栈中，此时，栈S的容量至少是3；Y第二个出队，则O、T、Y均已在栈中，此时，栈S的容量至少是3；T第三个出队，则O、T均已在栈中，此时，栈S的容量至少是2；H第四个出队，则O、H均已在栈中，此时，栈S的容量至少是2；O第五个出队，则O已在栈中，此时，栈S的容量至少是1；N第五个出队，则N已在栈中，此时，栈S的容量至少是1。依据题目描述，栈S的容量至少是3，故本题答案是B选项。 20．B 【详解】本题考查数据结构。数据结构设计的根本目的是为了更好地表达数据间的逻辑关系，从而提高数据处理和算法执行的效率。故选择B。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$