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

第一章 认识数据和数据结构 学校:___________姓名：___________班级：___________考号：___________ 一、选择题 1．下列关于数据结构的说法，正确的是（   ） A．基本数据类型是在程序设计时利用结构数据类型构造出的新类型 B．数据结构设计主要考虑数据之间的存储结构 C．Python列表中数据的存储结构和逻辑结构相同 D．行优先的6行10列方阵a首地址为SA，每个元素占10个字节，那么a[2][3]的起始地址为SA+230 2．在线性数据结构中，当前元素的后一位元素被称为（   ） A．首元素 B．前趋元素 C．尾元素 D．后继元素 3．什么是数据的逻辑结构（     ） A．数据元素在计算机中的实际存储方式 B．数据元素之间的逻辑关系 C．数据的物理存储单元 D．数据的计算方式 4．有五个元素的出栈顺序依次为1,2,3,4,5。则这五个元素的入栈顺序可能是（   ） A．1,4,5,3,2 B．2,4,3,1,5 C．3,5,4,1,2 D．5,4,1,3,2 5．队列Q从队首到队尾的元素依次为0，1，2，3，约定：A操作是指队首元素出队，P操作是指队首元素出队后立即从队尾入队，经过APA系列操作后，队列中队首到队尾的元素依次为（   ） A．3，0，2 B．2，0 C．3，1 D．1，3，0 6．关于栈，下列说法错误的是(  ) A．栈是先进后出（FILO）表。它的数据元素只能在同一端（称为栈顶）进行操作，添加（进栈），删除（出栈） B．pop(0)方法可以删除列表的尾元素(相当于栈的“出栈”操作) C．pop()方法可以删除列表的尾元素(相当于栈的“出栈”操作) D．append方法可以在列表尾部添加一个数据元素（相当于栈的“入栈”操作） 7．如图所示的线性数据结构，下列说法错误的是(  ) A．正向编号，首元素索引号为0，向后走，索引号递增 B．反向编号，尾元素编号为-1，向首元素方向依次递减 C．线性数据结构只包括队列与栈 D．栈：后进先出，添加和删除都在栈顶实现，队列：先进先出，删除在队首，添加在队尾 8．以下数据结构中哪一个是非线性结构？（   ） A．队列 B．列表 C．树 D．线性表 9．有一单向链表，链表结构如下图所示： 现要在尾指针p所指节点之后插入新节点r（r指针所指节点），则应进行的操作为（   ） A．p.next=r B．r.next=p C．p.next=r；r.next=null D．r.next=p；r.next=null 10．栈初始为空，经过一系列入栈、出栈操作后，栈又为空。若元素入栈的顺序为“生”“旦”“净”“末”“丑”，则所有可能的出栈序列中，以“旦”结尾的序列个数为（   ） A．3 B．4 C．5 D．6 11．某完全二叉树包含5个节点，其根节点在后序遍历序列、中序遍历序列中的位置序号分别记为x，y，则x-y的值为（   ） A．0 B．1 C．2 D．3 12．数据结构中栈和队列的共同特点是（ ） A．处理数据时满足先进后出 B．处理数据时满足先进先出 C．只允许在端点处插入和删除数据 D．没有共同点 13．栈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 14．下列有关数据结构的描述，正确的是（   ） A．常见的数据结构有数组、链表、队列、栈、树、图等 B．数据元素之间的逻辑关系也称为数据的物理结构 C．数据元素及其关系在计算机存储器内的表示称为数据的逻辑结构 D．数据结构设计的目的是确保数据处理的正确性，不用考虑数据处理的效率 15．下列不是栈的基本运算的是（   ） A．删除栈顶元素 B．删除栈底元素 C．判断栈是否为空 D．将栈置为空 16．某二叉树前序遍历为ABDGHECF；中序遍历为GDHBEAFC，以下说法正确的是（    ） A．此二叉树为完全二叉树 B．此二叉树有5个叶子节点 C．此二叉树的后序遍历结果为GHDEBFCA D．将二叉树以数组方式存储结果如图 17．某二叉树用一维数组来表示如下表所示。该二叉树从根节点开始，按照从上到下，从左到右的顺序依次用 A-H 字母表示，该二叉树的中序遍历为（   ） A．DBGEACFH B．DBGEACHF C．DBEGACHF D．ABCDEFGH 18．关于数据结构的描述，以下选项中错误的是(  ) A．数据结构指相互有关联的数据元素的集合 B．数据的存储结构有顺序存储、链接存储、索引存储和散列存储 C．数据结构不可以直观地用图形表示 D．数据的逻辑结构主要有集合结构、线性结构、树结构和图结构四种类型 19．一份有效的数据分析报告，能够帮助用户（   ） A．了解事物发展现状，预判事物发展趋势 B．有效判断所需解决问题的影响因素 C．有针对性地选择解决问题的方案 D．以上都是 20．队列是一种有限制的（ ）结构。特点是数据元素只能在（ ）依次添加（称为[ ]）， 在（ ）依次删除（称为[ ]）。 A．线性；一端；进队；另一端；出队 B．线性；二端；进队；二端；出队 C．队列；一端；进队；另一端；出队 D．队列；二端；进队；二端；出队 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．D 【详解】本题主要考查数据结构的描述。结构数据类型是在程序设计时利用结构数据类型构造出的新类型；数据结构设计主要考虑数据之间的相互关系，即数据的组织形式；Python列表中数据的存储结构和逻辑结构不相同；行优先的6行10列方阵a首地址为SA，每个元素占10个字节，那么a[2][3]的起始地址为SA+230（（2*10+3）*10=230），故本题选D选项。 2．D 【详解】本题考查线性数据结构的描述。在线性数据结构中，当前元素的后一位元素被称为后记元素，当前元素的前一位元素被称为前趋元素。故选D。 3．B 【详解】本题考查数据逻辑结构。数据的逻辑结构关注的是数据元素之间的关系，而非它们的物理存储方式。故选择B。 4．D 【详解】本题考查数据结构栈操作相关内容。栈的特点是：先进后出。A选项，1,2,3可以依次出栈，由于4早于5入栈，出栈时，4晚于5出栈，不可能得到出栈序列1,2,3,4,5；B选项，1出栈后，第二个出栈的可能是3或5，不可能得到出栈序列1,2,3,4,5；C选项，1出栈后，第二个出栈的可能是2或4，若第二个是2出栈，则第三个是4出栈，不可能得到出栈序列1,2,3,4,5；D选项，1出栈后，3,2依次入栈，栈中元素为2,3,4,5（栈顶到栈底），依次出栈，可得出栈序列1,2,3,4,5。故本题答案是D选项。 5．C 【详解】本题考查数据结构队列操作相关内容。分析题目内容，执行“A”操作，队首元素0出队，队列中元素为：1，2，3；执行“P”操作，队首元素1出队后立即入队，队列中元素为：2，3，1；执行“A”操作，队首元素2出队，队列中元素为：3，1。故本题答案是C选项。 6．B 【详解】本题主要考查栈数据结构。栈是先进后出（FILO）表。它的数据元素只能在同一端（称为栈顶）进行操作，添加（进栈），删除（出栈）；pop()方法可以删除列表的尾元素(相当于栈的“出栈”操作)；append方法可以在列表尾部添加一个数据元素（相当于栈的“入栈”操作），故本题选B选项。 7．C 【详解】本题主要考查数据结构。正向编号，首元素索引号为0，向后走，索引号递增；反向编号，尾元素编号为-1，向首元素方向依次递减；线性数据结构包括队列、栈、线性表及数组等；栈：后进先出，添加和删除都在栈顶实现，队列：先进先出，删除在队首，添加在队尾，故本题选C选项。 8．C 【详解】本题考查的是数据结构。常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)。故本题应选C。 9．C 【详解】本题考查数据结构链表相关内容。要在尾指针p所指节点之后插入新节点r，应先将p节点的next指针指向r节点，然后将r节点的next指针赋值为null(空)，故本题答案为C选项。 10．C 【详解】本题考查栈操作相关内容。栈的特点是先进后出。入栈的顺序为“生”“旦”“净”“末”“丑”，且要求以“旦”结尾。分析题目内容，推知：要以“旦”结尾，“生”一定是第一个出栈，剩余3个元素的排列有6种方案：净、末、丑；末、丑、净；丑、末、净；末、净、丑；净、丑、末；丑、净、末。但丑、净、末不可能是出栈序列（丑出栈，说明净和末都在栈内，且末在净上面，出栈时，末先于净出栈），则所有可能的出栈序列为：（1）生、净、末、丑、旦；（2）生、末、丑、净、旦；（3）生、丑、末、净、旦；（4）生、末、净、丑、旦；（5）生、净、丑、末、旦。即以“旦”结尾的序列个数为5，故本题答案是C选项。 11．B 【详解】本题考查树的遍历相关内容。分析题目内容，推知： 该二叉树为完全二叉树且包含5个节点，其结构如图所示：，由后序遍历规则知，其访问过程为：3-4-1-2-0，则其根节点的位置x处于第5个，即x=5；由中序遍历的规则知，其访问过程为：3-1-4-0-2，则其根节点的位置y处于第4个，即y=4；由此得出：x-y=1，故本题答案是B选项。 12．C 【详解】本题主要考查数据结构。栈仅允许在表的一端进行插入和删除运算，这一端被称为栈顶，相对地，把另一端称为栈底。队列是一种特殊的线性表，特殊之处在于它只允许在表的前端进行删除操作，而在表的后端进行插入操作。故数据结构中栈和队列的共同特点是只允许在端点处插入和删除数据，故本题选C选项。 13．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选项。 14．A 【详解】本题考查数据结构。数据元素之间的逻辑关系也称为数据的逻辑结构，因此B选项错误；数据元素及其关系在计算机存储器内的表示称为数据的物理结构或数据的存储结构，因此C选项错误；数据结构设计的目的既要确保数据处理的正确性，又要提高编程实现和数据处理的效率，因此D选项错误；常见的数据结构有数组、链表、队列、栈、树、图等，A选项正确。故答案为：A。 15．B 【详解】本题考查数据结构相关内容。栈的操作有删除栈顶元素、判断栈是否为空、将栈置为空等。栈的插入和删除操作只能在栈顶进行，故本题答案为B选项。 16．C 【详解】本题考查二叉树操作相关内容。由前序遍历及后序遍历序列，可得二叉树，如图所示：。A选项，该二叉树不是完全二叉树，选项错误。B选项，该二叉树有4个叶子节点，选项错误。C选项，该二叉树的后序遍历结果为GHDEBFCA，选项正确。D选项，该二叉树以数组方式存储结果如图所示:，选项错误。故本题答案是C选项。 17．A 【详解】本题考查二叉树相关内容。由二叉树存储结构可推知其形态如图所示：。该二叉树的中序遍历为：DBGEACFH，故本题答案是A选项。 18．C 【详解】本题主要考查数据结构。数据结构指相互有关联的数据元素的集合；数据的存储结构有顺序存储、链接存储、索引存储和散列存储；数据结构可以直观地用图形表示，如图结构等；数据的逻辑结构主要有集合结构、线性结构、树结构和图结构四种类型，故本题选C选项。 19．D 【详解】本题主要考查数据分析。一份有效的数据分析报告，能够帮助用户了解事物发展现状，预判事物发展趋势； 有效判断所需解决问题的影响因素； 有针对性地选择解决问题的方案，故本题选D选项。 20．A 【详解】本题主要考查队列数据结构。队列是一种有限制的线性结构。特点是数据元素只能在一端依次添加（称为[进队]）， 在另一端依次删除（称为[出队 ]），故本题选A选项。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$