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

3.2 数据与结构 学校:___________姓名：___________班级：___________考号：___________ 一、选择题 1．下列有关数据结构的说法正确的是（   ） A．数组是一种适合用于组织、存储涉及频繁插入与删除的数据结构 B．链表中数据元素的逻辑顺序是通过链表中的指针链接次序实现的 C．链表在访问、插入和删除元素时，算法效率比数组高 D．树结构中，每个子节点的父节点可以有多个 2．在排序算法中，选择结构通常用于（   ） A．快速排序 B．归并排序 C．堆排序 D．所有以上排序算法 3．关于队列，下列说法错误的是（   ） A．队列是先进先出（FIFO）表，它的数据元素只能在一端依次添加（进队），在另一端依次删除（出队） B．pop()方法可以删除列表的首元素（相当于队列的“出队”操作） C．pop(0)方法可以删除列表的首元素（相当于队列的“出队”操作） D．append方法可以在列表尾部添加一个数据元素（相当于队列的“入队”操作） 4．下列哪个算法不是基于比较的排序算法（   ） A．冒泡排序 B．插入排序 C．选择排序 D．计数排序 5．下列关于二叉树，说法不正确的是（   ） A．用数组的方式存储二叉树，容易造成空间浪费 B．若有前序和中序遍历可以推导出一棵唯一的二叉树 C．只有最下面两层有叶子节点的二叉树称为完全二叉树 D．完全二叉树的第3层有3个叶子节点，则该树的节点数量可能是8 6．在树形结构中，每个节点除了连接它的父节点外，可以有多个子节点，这种结构称为（   ） A．线性结构 B．分层结构 C．树状结构 D．网状结构 7．一个汉字的存储容量约为（   ）。 A．1b B．2b C．8b D．16b 8．Python的集合中，“&”表示两集合的交集、“-”表示两集合的差集、“|”表示两集合的并集、“^”表示两集合的对称差，对于BookInfo1={9,8,7,6,5,4,3}，BookInfo2={1,2,3,4,5,6,7}，下列选择错误的是（   ） A．print(BookInfo1&BookInfo2)执行后输出的值是:{3,4,5,6,7,8} B．print(BookInfo1-BookInfo2)执行后输出的值是:{8,9} C．print(BookInfo1^BookInfo2)执行后输出的值是:{1,2,8,9} D．print(BookInfo1|BookInfo2)执行后输出的值是:{1,2,3,4,5,6,7,8,9} 9．已知一棵完全二叉树共有5个节点，前序遍历为ABCDE，下列说法正确的是（   ） A．该二叉树的高度为3 B．该二叉树中只有1个度为2的节点 C．节点C的父节点是A D．该二叉树共有2个叶子节点 10．以下不是简单数据类型的是（    ） A．float B．str C．bool D．dict 11．图结构中的元素之间存在的关系是(  )。 A．一对一 B．一对多 C．多对一 D．多对多 12．在树形结构中，没有的是（）？ A．根的父节点 B．父节点 C．根 D．子树 13．下列关于数据结构的说法，正确的是（   ） A．用程序实现问题解决时只能采用一种数据结构 B．数据的逻辑结构是指数据元素间的关系 C．链表比数组更适合大量数据元素的随机访问 D．数组不必占用一片连续存储的单元 14．一个栈的入栈序列为1，2，3，4，5，其出栈序列为s1，s2，s3，s4，s5。若s2是3，则s1不可能是（    ） A．1 B．2 C．4 D．5 15．关于线性链表的描述，以下选项中正确的是（   ） A．存储空间不一定连续，且各元素的存储顺序是任意的 B．存储空间必须连续，且各元素的存储顺序是任意的 C．存储空间不一定连续，且前件元素一定存储在后件元素的前面 D．存储空间必须连续，且前件元素一定存储在后件元素的前面 16．全国航运图属于（   ） A．线性结构 B．树结构 C．图结构 D．以上均不是 17．如图所示的线性数据结构，下列说法错误的是(  ) A．正向编号，首元素索引号为0，向后走，索引号递增 B．反向编号，尾元素编号为-1，向首元素方向依次递减 C．线性数据结构只包括队列与栈 D．栈：后进先出，添加和删除都在栈顶实现，队列：先进先出，删除在队首，添加在队尾 18．下列不属于复合数据类型的是（   ） A．元组 B．整型 C．列表 D．集合 19．关于数据结构的描述，以下选项中错误的是(  ) A．数据结构指相互有关联的数据元素的集合 B．数据的存储结构有顺序存储、链接存储、索引存储和散列存储 C．数据结构不可以直观地用图形表示 D．数据的逻辑结构主要有集合结构、线性结构、树结构和图结构四种类型 20．以下关于数据结构的描述，不正确的是（   ） A．数据的逻辑结构是指数据元素之间的逻辑排列和对应关系 B．数据的存储结构包括数据元素的存储及数据元素之间关系的存储 C．数据的运算是指对数据施加的操作，包括删除、查找、插入数据等 D．数据结构设计时不需要考虑编程实现和数据处理的效率 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．B 【详解】本题考查数据结构。A选项错误。数组在涉及频繁插入与删除时，由于元素在数组中的位置是固定的，插入和删除可能涉及移动大量元素，效率较低。B选项正确。链表中的元素通过指针链接，每个元素保存下一个元素的地址，从而形成逻辑上的顺序。C选项错误。链表在插入和删除元素时确实具有较高的灵活性和效率，但在访问元素时，由于需要遍历链表，效率相对较低，特别是对于随机访问。D选项错误。在一棵树中，每个子节点只有一个父节点，这是树结构的基本特性。故答案为：B。 2．D 【详解】本题考查排序算法。在排序算法中，选择结构的用途是多样的。快速排序、归并排序、堆排序在它们的实现过程中都会用到选择结构。故答案为D选项。 3．B 【详解】本题考查数据结构。pop()方法是删除列表的最后一个元素，而不是首元素，这是错误的。其它选项正确。故正确答案为选项B。 4．D 【详解】本题考查排序算法。冒泡排序、插入排序和选择排序都是基于比较的排序算法，它们通过比较元素之间的大小来决定元素的顺序。而计数排序是一种非比较排序算法，它通过计数数组中元素出现的次数来确定元素的位置，从而进行排序。故答案为D选项。 5．C 【详解】本题考查二叉树的存储、遍历及完全二叉树的相关内容。使用数组存储二叉树时，若为一般非完全二叉树，则需要添加一些并不存在的空节点，会造成存储空间的浪费，选项A说法正确；可以由前序、中序遍历序列或中序、后序遍历序列唯一确定一颗二叉树，选项B说法正确；完全二叉树的定义是一个深度为k的有n个节点的二叉树，对树中的节点按从上至下、从左到右的顺序进行编号，如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同。选项虽然明确最下面两层有叶子节点，但未明确所有叶子节点按照从上至下、从左到右的顺序排列，选项C说法错误；完全二叉树第3层为叶子节点，说明前两层为满二叉树，由此得出，该数叶子节点为8，选项D说法正确。故答案为C选项。 6．C 【详解】本题考查树形结构。在树形结构中，每个节点除了连接它的父节点外，还可以有多个子节点，这种结构称为树状结构。树状结构是一种分层的层次结构，但它特指的是具有父子关系的节点结构。线性结构是指数据按顺序排列，网状结构是指节点之间可以有多对多的关系。故选C。 7．D 【详解】本题考查数据单位。计算机中最小单位为bit(位)，8bit=1Byte，1024Byte=1KB，1024KB=1MB，1024MB=1GB。一个汉字的存储容量约为16b，即两个字节。故本题D选项为正确选项。 8．A 【详解】本题考查集合。A选项输出的结果应该是3、4、5、6、7，而不是3、4、5、6、7、8。其它选项正确。故正确答案为选项A。 9．A 【详解】本题考查完全二叉树。B选项，该二叉树中2个度为2的节点。C选项，节点C的父节点是B。D选项，3个叶子节点。故正确选项A。 10．D 【详解】本题考查的是数据类型。float是浮点型数据，str是字符型，bool是布尔型，dict是字典。字典不是简单数据类型，故应选D。 11．D 【详解】本题主要考查图结构。图结构中的元素之间存在的关系是多对多，故本题选D选项。 12．A 【详解】本题主要考查树形结构。一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点（除了顶部的第一个节点）以及零个或多个子节点，因此A选项符合题意。 【点睛】 13．B 【详解】本题主要考查数据结构的描述。用程序实现问题解决时能采用多种数据结构，数据的逻辑结构是指数据元素间的关系，数组更适合大量数据元素的随机访问，数组必须占用一片连续存储的单元，故本题选B选项。 14．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选项。 15．A 【详解】本题考查线性链表。具有链接存储结构的线性表，它用一组地址任意的存储单元存放线性表中的数据元素，逻辑上相邻的元素在物理上不要求也相邻。选项A正确，其它选项错误。故正确答案为选项A。 16．C 【详解】本题考查图数据结构的描述。图是最为复杂的数据结构，如果数据元素之间存在一对多或者多对多的关系，那么这种数据的组织结构就叫作图结构。全国航运图存在多对多的关系，属于图结构。线性结构和树结构不存在多对多的关系。故选C。 17．C 【详解】本题主要考查数据结构。正向编号，首元素索引号为0，向后走，索引号递增；反向编号，尾元素编号为-1，向首元素方向依次递减；线性数据结构包括队列、栈、线性表及数组等；栈：后进先出，添加和删除都在栈顶实现，队列：先进先出，删除在队首，添加在队尾，故本题选C选项。 18．B 【详解】本题考查Python数据类型相关内容。在Python中，复合数据类型是指能够存储多个值的数据类型。Python提供了多种复合数据类型，包括：列表、元组、集合和字典。列表是一种有序、可变的数据类型；元组是一种有序、不可变的数据类型；集合是一种无序、可变的数据类型，且不能存储重复的值；字典由键值对组成，其中每个键都对应一个值。这些数据类型允许我们在一个变量中存储多个值，而且这些值可以是不同类型的数据。故本题答案是B选项。 19．C 【详解】本题主要考查数据结构。数据结构指相互有关联的数据元素的集合；数据的存储结构有顺序存储、链接存储、索引存储和散列存储；数据结构可以直观地用图形表示，如图结构等；数据的逻辑结构主要有集合结构、线性结构、树结构和图结构四种类型，故本题选C选项。 20．D 【详解】本题考查数据结构基本概念。数据的逻辑结构是指数据元素之间的关系和组织方式，包括线性结构、树形结构、图形结构等，A选项正确；数据的存储结构是数据在计算机中的表⽰（⼜称映像）⽅法，是数据的逻辑结构在计算机中的存储实现，因此在存储时应包含两⽅⾯的内容——数据元素本⾝及数据元素之间的关系，B选项正确；数据的运算是指对数据施加的操作，包括插入、删除、查找数据等，C选项正确；在设计的过程中，需要根据实际需求选择合适的算法，并考虑编程实现和数据处理的效率（时间复杂度），D选项错误。故本题答案是D选项。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$