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

第一章 认识数据和数据结构2024—2025学年高中信息技术粤教版（2019）选修1 一、选择题 1．在浏览网页时，可以通过超链接的方式实现网页间的跳转。与这种网页之间相互链接的表现形式相似的数据结构是（   ） A．队列 B．栈 C．链表 D．树 2．图结构中的每个顶点（ ）与其他顶点有边相连，数据元素之间是（ ）的关系。 A．都可以；一对多 B．都可以；多对多 C．不都可以；多对多 D．不都可以；一对多 3．以下选项中，属于integer类型常量的是（   ） A．123 B．3.1415 C．’ 1.23E+04’ D．True 4．现有如下Python程序：   List = [ "Happy", "new", "year!" ]   s = List[ 1 ]   d = s[ : -1 ] 执行该程序后，d的值为（） A．"py" B．"Happ" C．"ew" D．"ne" 5．在线性数据结构中，当前元素的后一位元素被称为（   ） A．首元素 B．前趋元素 C．尾元素 D．后继元素 6．某二叉树的树形结构如图所示， 其后序遍历结果为“物技化数英语”，则中序遍历结果为（   ） A．语数英物化技 B．物数技化语英 C．语数物化技英 D．化物技英数语 7．图中有关数据结构的概念中错误的是（  ） A．图中有9个数据元素 B．图中每个数据元素有7个数据项 C．数据项名称为“姓名”的数据值类型是一样的 D．第4个数据元素第3个数据项的值为“86” 8．一个栈的入栈序列为1，2，3，4，5，其出栈序列为s1，s2，s3，s4，s5。若s2是3，则s1不可能是（    ） A．1 B．2 C．4 D．5 9．栈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 10．下列关于线性表的描述，正确的是（    ） A．链表在访问、插入、删除节点操作时，算法效率比数组高 B．栈是一种“先进先出，后进后出”的线性表结构 C．循环队列是首尾相连的队列，数据入队时无需考虑是否会“溢出” D．字符串是元素个数有限的线性表结构 11．栈S最大长度为3，若元素a，b，c，d依次入栈，则可能的出栈序列为（   ） A．d，c，b，a B．b，a，d，c C．c，a，b，d D．c，d，a，b 12．下列有关数据结构的说法不正确的是：（　　） A．频繁进行数据插入和删除操作，链表效率要比数组高 B．单击浏览器“后退”按钮可回到刚才浏览过的网页， 说明网页数据是采用栈进行组织的 C．队列是一种先进先出的线性表，插入一端为队首，删除一端为队尾 D．使用数组在进行数据插入和删除操作时，不一定会引起数据移动 13．队列Q从队首到队尾的元素依次为3，1，2，栈S初始为空。约定以下操作：H操作是指元素出队后再入队，T操作是指元素出队后入栈，P操作是指元素出栈。经过一系列操作后，最终出栈顺序为1，2，3，以下操作不可能的是（   ） A．TTPTPP B．HTTTPPP C．THTTPPP D．HΤΡΤΡΤΡ 14．以下说法错误的是（   ） A．栈是一种先进后出的数据结构 B．队列是一种先进先出的数据结构 C．C++ STL中的map查询时间复杂度为0(1) D．使用哈希时，可能会发生哈希冲突 15．有如下Python程序段: a=[1,20,15,6,9,12,30,8,7,5] n=len(a) sumx=0 for i in range(n):     if a[i]%3==2:         sumx=sumx+a[i] print(sumx) 该程序段执行后,输出的结果为（   ） A．25 B．28 C．33 D．72 16．树结构是一种具有层次关系的非线性结构。树是由n(n≥0)个节点组成的有限集合，如图所示，下列说法错误的是(  ) A．任何一个非空树均仅有一个称为根的节点，如图中A,n=0时为空树 B．当n>0时，其余节点可分为m ( m≥0)个互不相交的有限集合，其中每个集合又是一棵树，并称为根的子树 C．节点A为根节点，B、C、D为A的子树的根节点，同理，E、F、G是B的子树的根节点，B是E、F、G的父节点 D．在树结构中，数据元素之间是一对一的关系 17．已知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'］ 18．在查找算法中，顺序查找的时间复杂度是（   ） A．O(n) B．O(n^2) C．O(logn) D．O(nlogn) 19．下列有关Series对象的说法中错误的是(　　) A．Series对象中必须指定index B．通过索引可以选取Series对象中的值，通过赋值语句修改Series对象中的值 C．Series对象中的index和values长度必须一致 D．Series对象是一种一维的数据结构，包含一个数组的数据和一个与数据关联的索引 20．在一个单向链表中，每个节点由数据域data和指针域next组成，现要在指针p所指向的节点后面插入一个指针r所指节点，则下列代码能实现的是（   ） A．p.next=r B．p.next=r；r.next=p.next.next C．r.next=p.next；p.next=r.next D．r.next=p.next；p.next=r 试卷第1页，共3页 试卷第1页，共3页 学科网（北京）股份有限公司 参考答案： 1．C 【详解】本题考查数据结构相关内容。网页之间通过超链接的方式来实现网页间的跳转，符合链表的特征，故本题答案为C选项。 2．B 【详解】本题主要考查数据结构。图结构中的每个顶点都可以与其他顶点有边相连，数据元素之间是多对多的关系，故本题选B选项。 3．A 【详解】本题主要考查程序数据类型。选项依次是整型（integer）、浮点型、字符型、布尔型常量，故本题选A选项。 4．D 【详解】本题主要考查Python列表运算。 s = List[ 1 ]="new"， d = s[ : -1 ]="ne"（表示去除字符串s最后一个字符剩下的部分），故本题选D选项。 5．D 【详解】本题考查线性数据结构的描述。在线性数据结构中，当前元素的后一位元素被称为后记元素，当前元素的前一位元素被称为前趋元素。故选D。 6．B 【详解】本题考查二叉树相关内容。结合树形结构及后序遍历结果，可知该二叉树形态如图所示：。则其中序遍历结果为：物数技化语英。故本题答案是B选项。 7．D 【详解】本题主要考查数据结构。由图可知，图中有9个数据元素图中每个数据元素；有7个数据项；数据项名称为“姓名”的数据值类型是一样的；第4个数据元素第3个数据项的值为“85”，故本题选D选项。 8．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选项。 9．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选项。 10．D 【详解】本题主要考查线性表的描述。链表在访问节点操作时，算法效率比数组低；栈是一种“先进后出，后进先出”的线性表结构；循环队列是首尾相连的队列，数据入队时需要考虑是否会“溢出”；字符串是元素个数有限的线性表结构，故本题选D选项。 11．B 【详解】本题考查栈操作相关内容。栈的特点是：先进后出。题干中限定条件栈s的最大长度为3：A选项，若d先出栈，说明c，b，a均在栈内，栈的容量至少为4，超出最大长度，选项错误。B选项，若b先出栈，说明a在栈内，a可以出栈，此时栈空，c，d先后入栈，再依次出栈，可得出栈序列：b，a，d，c，选项正确。CD选项中，a不应先于b出栈，选项错误。故本题答案是B选项。 12．C 【详解】本题主要考查数据结构的描述。队列是一种先进先出的线性表，插入一端为队尾，删除一端为队首，故本题选C选项。 13．B 【详解】本题考查数据结构栈和队列操作相关内容。栈的特点是先进后出，队列的特点是先进先出。结合题目，推知： A选项，操作序列为TTPTPP，T-->3出队后入栈，栈中元素为3；T-->1出队后入栈，栈中元素为1，3；P-->1出栈，栈中元素为3，出栈顺序为1；T-->2出队后入栈，栈中元素为2，3；P-->2出栈，栈中元素为3，出栈顺序为1，2；P-->3出栈，栈为空，出栈顺序为1，2，3。 B选项，操作序列为HTTTPPP，H-->3出队后入队，队列元素为1，2，3；T-->1出队后入栈，栈中元素为1；T-->2出队后入栈，栈中元素为2，1；T-->3出队后入栈，栈中元素为3，2，1；执行PPP，连续三次出栈，栈为空，出栈顺序为3，2，1。 C选项，操作序列为THTTPPP，T-->3出队后入栈，栈中元素为3；H-->1出队后入队，队列元素为2，1；T-->2出队后入栈，栈中元素为2，3；T-->1出队后入栈，栈中元素为1，2，3；执行PPP，连续三次出栈，栈为空，出栈顺序为1，2，3。 D选项，操作序列为HΤΡΤΡΤΡ，H-->3出队后入队，队列元素为1，2，3；T-->1出队后入栈，栈中元素为1；P-->1出栈，出栈顺序为1，栈空；T-->2出队后入栈，栈中元素为2；。P-->2出栈，出栈顺序为1，2，栈空；T-->3出队后入栈，栈中元素为3，P-->3出栈，出栈顺序为1，2，3。 故本题答案是B选项。 14．C 【详解】本题主要考查数据结构的描述。C++ STL中的map查询时间复杂度为O(logN)，故本题选C选项。 15．C 【详解】本题考查Python程序设计相关内容。程序段功能是求数组a中的除3余2的元素之和，除3余2的数据有:20、8、5，因此sumx=20+8+5=33，故本题答案为C选项。 16．D 【详解】本题主要考查数据结构。任何一个非空树均仅有一个称为根的节点，如图中A，n=0时为空树；当n>0时，其余节点可分为m ( m≥0)个互不相交的有限集合，其中每个集合又是一棵树，并称为根的子树；节点A为根节点，B、C、D为A的子树的根节点，同理，E、F、G是B的子树的根节点，B是E、F、G的父节点；在树结构中，数据元素之间是一对多的关系，故本题选D选项。 17．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选项。 18．A 【详解】本题考查查找算法相关内容。顺序查找是一种基本的查找算法，‌其基本思想是从列表的一端开始，‌逐个检查每一个元素，‌直到找到目标元素或搜索完整个列表。‌这种查找方式不需要额外的存储空间，‌但它的效率取决于列表的长度和元素的分布。‌在最坏的情况下，‌即当目标元素不在列表中时，‌顺序查找需要检查列表中的每一个元素，‌因此其时间复杂度为O(n)，‌其中n是列表的长度。‌这意味着，‌无论列表如何排序，‌顺序查找都需要进行n次比较才能确定目标元素是否存在。故本题答案是A选项。 19．A 【详解】本题考查的是Series对象相关知识。Series对象中可以省略index，index值默认是从0起递增的整数，因此答案为A。 20．D 【详解】本题考查数据结构链表操作相关内容。要在指针p所指向的节点后面插入一个指针r所指节点，应先将r节点的next指针指向p节点的next指针指向的节点，然后将p节点的next指针指向r节点，因此代码为:r.next=p.next;p.next=r，故本题答案为D选项。 答案第1页，共2页 答案第1页，共2页 学科网（北京）股份有限公司 $$