3.2 数据与结构 2024-2025学年高中信息技术教科版（2019）必修1

3.2 数据与结构2024-2025学年高中信息技术教科版（2019）必修1 一、选择题 1．以下哪个算法不是时间复杂度为O(n^2)的排序算法（   ） A．冒泡排序 B．插入排序 C．选择排序 D．快速排序 2．在树形结构中，每个节点除了连接它的父节点外，可以有多个子节点，这种结构称为（   ） A．线性结构 B．分层结构 C．树状结构 D．网状结构 3．树的度指的是（   ） A．树中边的数量 B．树中节点的最大子节点数 C．树的深度 D．树的广度 4．关于Python语言的浮点数类型，以下选项中描述错误的是（   ） A．Python语言要求所有浮点数必须带有小数部分 B．浮点数类型与数学中实数的概念一致 C．小数部分不可以为0 D．浮点数类型表示带有小数的类型 5．对于如图所示的二叉树，下列说法正确的是（   ） A．叶子节点有4个 B．是完全二叉树，树的高度为4 C．前序遍历的结果是一个递增序列 D．可以使用数组[2,5,10,7,8,13,9,15]存储 6．下列哪种数据结构不是线性结构（   ） A．数组 B．链表 C．栈 D．二叉树 7．关于线性链表的描述，以下选项中正确的是（   ） A．存储空间不一定连续，且各元素的存储顺序是任意的 B．存储空间必须连续，且各元素的存储顺序是任意的 C．存储空间不一定连续，且前件元素一定存储在后件元素的前面 D．存储空间必须连续，且前件元素一定存储在后件元素的前面 8．在日常幻灯片(如使用 PowerPoint 制作的讲稿) 的放映中， 可以通过超链接的方式进行幻灯片之间的任意跳转。与这种幻灯片的组织方式相似的数据结构是（    ） A．链表 B．队列 C．栈 D．树 9．Python的元组与列表类似，下列说法错误的是（   ） A．元组的元素不能修改，元组中只包含一个元素时，需要在元素后面添加逗号 B．元组使用小括号，列表使用方括号 C．元组创建很简单，只需要在括号中添加元素，并使用逗号隔开即可 D．元组BookInfo1=("ID2315937",20,2)，BookInfo1[2]=4用于修改元组BookInfo1[2]的值 10．有一种元素除首元素没有前驱元素、尾元素没有后继元素外，其它元素都只有一个前驱元素和一个后继元素。具有以上特点的数据结构是（    ） A．树结构 B．选择结构 C．线性结构 D．网状结构 11．一个栈的入栈序列为1，2，3，4，5，其出栈序列为s1，s2，s3，s4，s5。若s2是3，则s1不可能是（    ） A．1 B．2 C．4 D．5 12．集合是一个可变容器，集合是无序的存储结构，集合内的数据没有先后关系，集合内的数据对象都是唯一的(不能重复)，集合相当于是只有键没有值得字典(键就是集合中的数据)，集合内的元素是不可变的，下列说法正确的是（） A．s={1,2,3,3,2,1},pring(s)执行后，输出：{1,2,3} B．s={6,7,8,9}，s.add(9)添加1后s={6,7,8,9,9} C．s={6,7,8,9}，s.pop()执行后，s={6,7,8} D．s={3,4,5,6,7,8,9}，s.remove(5)执行后,s={3,4,5,6,7,9} 13．一个汉字的存储容量约为（   ）。 A．1b B．2b C．8b D．16b 14．队列属于（   ） A．线性结构 B．树结构 C．图结构 D．以上均不是 15．下列关于二叉树，说法不正确的是（   ） A．用数组的方式存储二叉树，容易造成空间浪费 B．若有前序和中序遍历可以推导出一棵唯一的二叉树 C．只有最下面两层有叶子节点的二叉树称为完全二叉树 D．完全二叉树的第3层有3个叶子节点，则该树的节点数量可能是8 16．数据结构也称逻辑结构，以下不是数据结构的是（     ） A．集合结构 B．线性结构 C．网状结构 D．顺序结构 17．队列是一种有限制的（ ）结构。特点是数据元素只能在（ ）依次添加（称为[ ]）， 在（ ）依次删除（称为[ ]）。 A．线性；一端；进队；另一端；出队 B．线性；二端；进队；二端；出队 C．队列；一端；进队；另一端；出队 D．队列；二端；进队；二端；出队 18．某校智慧校园建设在原来非接触式一卡通的基础上，引入了人脸识别等人工智能应用。其中人脸识别系统需先对应一卡通卡号采集学生正面标准照后才可使用。学生经过寝室考勤机时，需要先刷卡后刷脸的双重认证，系统根据考勤机采集的数据和学校的请假数据进行匹配，给出考勤信息，宿管员根据缺勤（考勤机未认证且未请假）信息进行人工查证。根据阅读材料，下列说法错误的是（    ） A．该信息系统提高了工作效率 B．采集得到的人脸照片是结构化数据 C．双重认证能有效提高学生考勤准确率 D．考勤机读取校园卡的过程采用了射频识别技术 19．关于队列，下列说法错误的是（   ） A．队列是先进先出（FIFO）表，它的数据元素只能在一端依次添加（进队），在另一端依次删除（出队） B．pop()方法可以删除列表的首元素（相当于队列的“出队”操作） C．pop(0)方法可以删除列表的首元素（相当于队列的“出队”操作） D．append方法可以在列表尾部添加一个数据元素（相当于队列的“入队”操作） 20．在排序算法中，选择结构通常用于（   ） A．快速排序 B．归并排序 C．堆排序 D．所有以上排序算法 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．D 【详解】本题考查排序算法。冒泡排序、插入排序和选择排序的平均时间复杂度都是O(n^2)，而快速排序的平均时间复杂度是O(n log n)，因此快速排序不是时间复杂度为O(n^2)的排序算法。故选D。 2．C 【详解】本题考查树形结构。在树形结构中，每个节点除了连接它的父节点外，还可以有多个子节点，这种结构称为树状结构。树状结构是一种分层的层次结构，但它特指的是具有父子关系的节点结构。线性结构是指数据按顺序排列，网状结构是指节点之间可以有多对多的关系。故选C。 3．B 【详解】本题考查的是树相关知识。树的度指的是树中节点子节点的最大数目。对于一颗非空树，其度指的是该树中度最大的节点的子节点个数。故选B。 4．C 【详解】本题考查浮点数。Python中的浮点数小数部分可以为0，如1.0。故选项C错误。其它选项正确。故正确答案为选项C。 5．C 【详解】本题考查二叉树、完全二叉树的基本概念、遍历、存储等知识点。选项A，其叶子节点为：7、9、15，共3个，A选项错误；选项B，根据完全二叉树的概念可以得知，其不满足完全二叉树的定义，B选项错误；选项C，其前序遍历序列为：2、5、7、8、9、10、13、15，为递增序列，C选项正确；D选项，使用数组存储，形式为：  ，D选项错误。故本题答案为C。 6．D 【详解】本题考查数据结构。线性结构是指数据元素之间存在一对一的线性关系。数组、链表和栈都是线性结构，而二叉树是一种非线性结构。故答案为：D。 7．A 【详解】本题考查线性链表。具有链接存储结构的线性表，它用一组地址任意的存储单元存放线性表中的数据元素，逻辑上相邻的元素在物理上不要求也相邻。选项A正确，其它选项错误。故正确答案为选项A。 8．A 【详解】本题主要考查链表数据结构。链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。在日常幻灯片(如使用 PowerPoint 制作的讲稿) 的放映中， 可以通过超链接的方式进行幻灯片之间的任意跳转。与这种幻灯片的组织方式相似的数据结构是链表，故本题选A选项。 9．D 【详解】本题考查元组。元组的元素是不可修改的，因此 BookInfo1[2]=4是错误的，无法修改元组元素的值。其它选项正确。故正确答案为选项D。 10．C 【详解】本题考查数据结构。线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，串。除最后元素之外，其它数据元素均有唯一的后继，除第一元素之外，其它数据元素均有唯一的前驱。故本题选项C为正确选项。 11．D 【详解】本题主要考查栈数据结构。1先入栈后再出栈，接着2、3入栈，3出栈，s1可能是1；1先入栈未出栈，其次2入栈后再出栈，s1可能是2；1、2、3、4依次入栈，接着4和3出栈，s1可能是4。3和5之间有4，故s1不可能是5，故本题选D选项。 12．A 【详解】本题主要考查集合数据结构。s={1,2,3,3,2,1}，print(s)执行后，输出：{1,2,3}；s={6,7,8,9}，s.add(9)添加9，元素已存在，则不进行任何操作；s.pop()删除的元素是随机的；s={3,4,5,6,7,8,9}，s.remove(5)执行后,s={3,4,6,7,8,9}，故本题选A选项。 13．D 【详解】本题考查数据单位。计算机中最小单位为bit(位)，8bit=1Byte，1024Byte=1KB，1024KB=1MB，1024MB=1GB。一个汉字的存储容量约为16b，即两个字节。故本题D选项为正确选项。 14．A 【详解】本题考查数据结构相关内容。数据结构分为集合、线性结构、树结构、图结构。队列属于线性结构，其操作特点是：先进先出。故本题答案是A选项。 15．C 【详解】本题考查二叉树的存储、遍历及完全二叉树的相关内容。使用数组存储二叉树时，若为一般非完全二叉树，则需要添加一些并不存在的空节点，会造成存储空间的浪费，选项A说法正确；可以由前序、中序遍历序列或中序、后序遍历序列唯一确定一颗二叉树，选项B说法正确；完全二叉树的定义是一个深度为k的有n个节点的二叉树，对树中的节点按从上至下、从左到右的顺序进行编号，如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同。选项虽然明确最下面两层有叶子节点，但未明确所有叶子节点按照从上至下、从左到右的顺序排列，选项C说法错误；完全二叉树第3层为叶子节点，说明前两层为满二叉树，由此得出，该数叶子节点为8，选项D说法正确。故答案为C选项。 16．D 【详解】本题考查数据结构相关知识。数据结构也称逻辑结构，数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。集合结构，线性结构，网状结构都属于数据结构。选项D不属于数据结构，它是算法的结构。故本题选D。 17．A 【详解】本题主要考查队列数据结构。队列是一种有限制的线性结构。特点是数据元素只能在一端依次添加（称为[进队]）， 在另一端依次删除（称为[出队 ]），故本题选A选项。 18．B 【详解】本题考查的是数据相关知识。相对于结构化数据（即行数据，存储在数据库里，可以用二维表结构来逻辑表达实现的数据）而言，不方便用数据库二维逻辑表来表现的数据即称为非结构化数据，包括所有格式的办公文档、文本、图片、XML、HTML、各类报表、图像和音频/视频信息等等。采集得到的人脸照片是非结构化数据。故选项B说法错误。 19．B 【详解】本题考查数据结构。pop()方法是删除列表的最后一个元素，而不是首元素，这是错误的。其它选项正确。故正确答案为选项B。 20．D 【详解】本题考查排序算法。在排序算法中，选择结构的用途是多样的。快速排序、归并排序、堆排序在它们的实现过程中都会用到选择结构。故答案为D选项。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$