3.2 数据与结构导学案2024-2025学年高一上学期高中信息技术必修1第3单元教科版（2019））

3.2 数据与结构 【学习目标】 1.熟悉队列结构的概念和特点，能够使用Python语言对队列进行操作。 2.了解树、图结构的基本概念和特点。 3.能够比较不同数据结构的特点，会选用合适的数据结构组织数据解决简单问题。 【知识框架】 数据在计算机中都是以二进制的形式存储，孤立的数据无法直接使用，一定要将数据依据数据关系整合起来，这种数据依据关系有利于数据的操作和管理，进而高效解决实际问题。 知识点1：列表数据类型 在Python中，有 、 、 、 等表示整数、浮点数、布尔值和字符串的数据类型，即简单数据类型。还有一种叫复合数据类型，它是由简单数据类型或者复合数据类型组成的，如 、 、 、 等都属于复合数据类型。 orderList = [”张三”, 16, 34.66]，其中列表名为 ，第一项是 类型，第二项是 类型，最后一项是 类型（从int、float、str中选）。 知识点2：数据结构 数据结构是存在特定关系的 的集合。即一些相关联的数据集中在一起形成一个数据的集合，这种集合能单独或作为一个整体被访问和处理。 数据结构也称为逻辑结构，主要有 结构、 结构、 结构和图结构（又称为网状结构）四种。 知识点3：线性数据结构 线性数据结构又称为 。除了首元素没有 、尾元素没有 外，其他元素都只有一个前驱元素和一个后继元素。元素之间是 的关系。 知识点4：队列 队列：是一种有限制的 ，它的数据元素只能在一端依次添加（进队），在另一端依次删除（出队）。列表实现的过程中pop(0)方法实现出队，append()方法实现进队。 知识点5：栈 栈：是一种特殊的线性表，仅能在一端操作，栈顶允许操作，栈底不允许操作。从栈顶放入元素的操作叫入栈，取出元素叫出栈。 比一比：队列和栈的区别联系 结构类型 进出结构 生活中相应结构应用举例 栈（线性） 栈顶出入 队列（线性） 一端入一端出 上机练习： 小组合作，试着模仿订单数据处理程序，编写单车道死胡同停车管理程序。 案例1：家谱中“隐藏”的数据结构 四大名著之一的《红楼梦》里主要讲述了四大家族的兴衰历程。在《红楼梦》中，主要的故事情节都是以贾家作为主线贯穿的。贾家的人物关系也是错综复杂。 《红楼梦》中贾家的人物关系显然不能用线性结构来表示，那这是一种什么数据结构呢？它具备什么特点？ 知识点6：树结构 树结构是一种具有 的非线性结构。树结构中，数据元素之间是 的关系。树是由n个节点组成的有限集合。n=0为空树。任何一个非空树均满足以下两个条件： 1.仅有一个称为根的节点；2.当n>0时，其余节点可分为m个互不相交的有限集合，其中每个集合又是一棵树，并称为根的子树。 如上图，节点A为 ；BCD为A的子树的 ；B是EFG的 。 知识点7：图结构 图结构：由一组 （称顶点）和一组节点间的连线（称边或弧）构成的一种数据结构。图结构中的每个顶点都可以与其他顶点有边相连，图结构中数据元素之间是 的关系。 如前图，标号是1的顶点与两条边相连，顶点4与2，8，9相连。 比一比：数据结构的比较 结构类型 数据节点之间的关系 生活中相应结构应用举例 队列（线性） 树 图 知识点8：其他数据结构 数据结构可分为 和 两种类型。 本节学习的结构属于逻辑结构，强调数据与数据之间的逻辑关系。逻辑结构主要是应解决问题的需要而建立的数据组织形式。 物理结构指数据在计算机中的表示形式，即数据的逻辑结构在计算机存储空间的存放形式，又称为存储结构。数据的存储结构有顺序存储结构、链式存储结构、索引存储结构和散列存储结构等。 【课后练习】 1.由一组节点（称为顶点）和一组节点间的连线（称为边或弧），构成的一种数据结构是（ ） A.图结构 B.选择结构 C.线性结构 D.树结构 2.有一种元素除首元素没有前驱元素、尾元素没有后继元素外，其他元素都只有一个前驱元素和一个后继元素。具有以上特点的数据结构是（ ） A.树结构 B.选择结构 C.线性结构 D.网状结构 3.数据结构也称逻辑结构，以下不是数据结构的是（ ） A.集合结构 B.线性结构 C.网状结构 D.顺序结构 4.下列选项中不属于线性数据结构的是（ ） A.线性表 B.二叉树 C.队列 D.栈 5.下列选择中数据结构不是图结构的是(　　) A.城市交通图 B.电话网 C.公司组织架构 D.互联网 6.关于数据结构的描述，以下选项中错误的是（　　） A.数据结构指相互有关联的数据元素的集合 B.数据的存储结构有顺序存储、链接存储、索引存储和散列存储 C.数据结构不可以直观地用图形表示 D.数据的逻辑结构主要有集合结构、线性结构、树结构和图结构四种类型 7.如图所示线性数据结构，下列说法错误的是（ ） A.正向编号，首元素索引号0，向后索引号递增 B.反向编号，尾元素编号－1，向首元素方向依次递减 C.线性数据结构只包括队列与栈 D.栈：后进先出，添加和删除都在栈顶实现，队列：先进先出，删除在队首，添加在队尾 8.在解决问题的过程中，数据结构起到非常重要的作用。下列选项中对数据结构的描述不正确的是（ ） A.对于同一事物，可以构造出多种数据结构 B.选择的数据结构不同，解决问题的步骤也不同 C.数据逻辑结构中相邻的数据其存储位置不一定相邻 D.同一操作如插入，不同数据存储结构实现方法相同 9.以下数据结构中哪一个是非线性结构（） A.队列 B.列表 C.树 D.线性表 10.下列具有线性结构的数据结构是（） A.图 B.树 C.堆 D.队列 11.数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。 A.结构 B.关系 C.运算 D.算法 12.下列哪种数据结构中，数据元素之间是多对多的关系是？（ ） A.队列 B.图结构 C.树结构 D.栈 13.有A、B、C、D、E五个人依次进入电梯，结果警告超重了，需要出去一个人才能正常运行，按照数据结构中栈和队列的思维，应离开电梯的人分别是( ) A.栈：A队列：E    B.栈：A队列：A C.栈：E队列：A    D.栈：E队列：E 14.在Python语言的数据结构中，根据数据元素之间的关系可知，下列选项中不属于基本结构的是（ ） A.列表 B.线性结构 C.树结构 D.图结构 15.下列选项中是日常生活中数据结构的应用实例，表述不正确的有（ ） A.条形码和对应价格关系是数据结构中的“非线性表” B.在银行柜台前排队叫号是数据结构中的“队列” C.某公司的组织架构图是数据结构中的“树” D.圆桌上每个人和每盘菜的关系是数据结构中的“图” 16.下面有关数据结构的说法不正确的是（ ） A.在程序设计中，数据结构设计时主要考虑对象之间逻辑关系的实现 B.链表结构适用于初始规模确定但在处理过程中频繁进行插入、删除操作的问题 C.数组结构中的数据访问效率要高于链表结构 D.大多数软件中都有“撤销”功能，在撤销操作中内部依托的数据结构是队列 17.线性数据结构中，当前元素的后一元素被称为（ ） A.首元素 B.前趋元素 C.尾元素 D.后继元素 18.除了首元素没有前趋元素，尾元素没有后继元素外其他所有元素都只有一个前趋元素和后继元素，这种数据结构属于（  ） A.树结构 B.图结构 C.线性结构 D.集合结构 19.下列关于数据结构的说法，正确的是（   ） A.用程序实现问题解决时只能采用一种数据结构 B.数据的逻辑结构是指数据元素间的关系 C.链表比数组更适合大量数据元素的随机访问 D.数组不必占用一片连续存储的单元 20.以下语句是定义空列表的是（ ） A.Bookset={} B.q=[] C.num=() D.dict=dict() 21.创建一个list列表，正确的是（ ） A.list[1,2,3]    B.list=[1,2,3] C.list(1,2,3)    D.list=(1,2,3) 22.列表n=["水果","砂糖橘","苹果","橙子"],请把列表中"苹果"改为"橘子"，选出修改正确的语句（ ） A.n[2]="橘子"    B.n["橘子"] C.n[3]="橘子"    D.list["橘子"] 23.下列python数据中不属于列表的是（ ） A.{23,45,56,78}    B.[23,45,5.6,7.8] C.[23,45,"Info",'a'] D.["A","B","C","D"] 24.下列选项中,( )是列表 A.(1,2,3,4)    B.range(1,5) C.range(10)    D.["苹果",3,"猕猴桃"] 25.下列关于Python 列表的描述错误的是( ) A.列表元素数据类型须一致 B.列表元素可以被修改 C.列表索引从0开始 D.元素可从中间也可末尾添加 26.在Python语言中，列表1ist1=[1,2,3,4,5,6,7]，下列方式获取的结果不同的一项是（ ） A.list1[:3]    B.list1[0:3] C.list1[-5:-8:-1] D.list1[-7:-4] 27.在Python中函数range(6,10,2)生成的列表中元素的个数是（ ） A.2    B.3    C.4    D.5 28.已知列表list1=[3,4,"5",56]，则表达式“print(5 in list1)”运行后结果为（ ） A.True    B.False    C.1    D.0 29.队列的删除操作是在( ) A.队首 B.队尾 C.队列中间位置 D.任意位置 30.一个队列初始为空，若它的输入序列为ａ、ｂ、ｃ、ｄ，则它的输出序列为（ ） A.ｄ、ｃ、ｂ、ａ    B.ｄ、ａ、ｃ、ｂ C.ａ、ｂ、ｃ、ｄ    D.ａ、ｃ、ｂ、ｄ 31.关于队列的描述中,以下描述正确的是( ) A.队列中只能删除数据 B.队列是先进后出的线性表 C.队列中只能插入数据 D.队列是先进先出的线性表 32.队列的“先进先出”特性是指( ) A.最后进入队列的元素总是最后被删 B.每次从队中删除的总是最早插入的元素 C.每当有删除操作时,总要先做一次插入操作 D.当同时进行插入、删除操作时,总是插入操作优先 33.关于队列,下列说法错误的是(　　) A.队列可用列表模拟,空队列可以用函数list()得到 B.队列是先进先出,可以使用append进队、pop出队 C.通过pop(1)可以删除列表首元素,相当于出队操作 D.通过函数len()可以得到队列中元素的个数 34.关于队列，下列说法错误的是（　　） A.队列是先进先出（FIFO）表，它的数据元素只能在一端依次添加（进队），在另一端依次删除（出队） B.pop（）方法可以删除列表的首元素（相当于队列的“出队”操作） C.pop（0）方法可以删除列表的首元素（相当于队列的“出队”操作） D.append方法可以在列表尾部添加一个数据元素（相当于队列的“入队”操作） 35.一个队列的数据入列的序列是1,2,3,4，则该队列的出队序列是（） A.4,3,2,1 B.1,2,3,4 C.1,4,3,2 D.3,2,4,1 36.队列的插入操作是在（ ）进行的 A.队尾 B.队首 C.队列任意位置 D.队首元素后 【学案答案】 1.int 2.float 3.bool 4.str 5.列表 6.元组 7.集合 8.字典 9.orderList 10.str 11.int 12.float 13.数据元素 14.集合 15.线性 16.树 17.线性表 18.前趋元素 19.后继元素 20.一对一 21.线性结构 22.一对多 23.根节点 24.根节点 25.父节点 26.节点 27.多对多 28.物理结构 29.逻辑结构 【课后答案】 1.答案：A解析：由一组节点（称为顶点）和一组节点间的连线（称为边或弧），构成的一种数据结构是图结构。故本题选A。 2.答案：C解析：除最后元素之外，其它数据元素均有唯一的后继，除第一元素之外，其它数据元素均有唯一的前驱。故本题选C。 3.答案：D解析：选项D不属于数据结构，它是算法的结构。故本题选D。 4.答案：B解析：树不是线性数据结构，故选B。 5.答案：C解析：公司的组织架构是树结构，故选C。 6.答案：C解析：数据结构可以通过图形直观的展示。故错误的选C。参考网址 7.答案：C解析：线性数据结构包括队列、栈、线性表、数组。故C错误。 8.答案：D解析：不同的数据存储结构的实现方法不会是一样的，故D错误。 9.答案：C解析：树和图是典型的非线性结构，故选C。 10.答案：D解析：队列是线性结构的数据结构，选D。 11.答案：B解析：研究元素和元素之间的关系，故选B。 12.答案：B解析：元素是多对多的关系是图结构，故选B。 13.答案：C解析：栈是后进先出，故是E，队列是先进先出，故是A，故结论是EA，选C。 14.答案：A解析：基本结构有线性结构、树结构、图结构，故A不属于基本结构。 15.答案：A解析：超市条形码和对应价格关系是一对一关系，属于数据结构中的“线性表”，故A错误。 16.答案：D解析：撤销功能，对应的数据结构是栈，故D错误。 17.答案：D解析：本题考查线性数据结构的描述。在线性数据结构中，当前元素的后一位元素被称为后继元素，当前元素的前一位元素被称为前趋元素。故选D。 18.答案：C解析：除了首元素没有前趋元素，尾元素没有后续元素外其他所有元素都只有一个前趋元素和后续元素，这种数据结构属于线性结构，故选C。 19.答案：B解析：本题主要考查数据结构的描述。用程序实现问题解决时能采用多种数据结构，数据的逻辑结构是指数据元素间的关系，数组更适合大量数据元素的随机访问，数组必须占用一片连续存储的单元，故本题选B选项。 20.答案：B解析：本题考查数据结构。空list的创建：l=list()或者：l=[]。故本题选B。 21.答案：B解析：本题主要考查Python列表。列表必须用中括号[]，赋值给list所以必须用等于号。例如，list[1]对应的是列表1号位置的内容，故本题选B选项。 22.答案：A解析：本题主要考查数组知识点。对应列表中的位置修改相应的数据，列表是从0起点标注位置，故正确的语句是n[2]= ‘橘子’，故本题选A选项。 23.答案：A解析：列表以[ ]进行标识，故本题选A。 24.答案：D解析：A是元组，BC是range对象，D是列表，故选D。 25.答案：A解析：列表中的元素类型可以不一样，故错误的是A。 26.答案：C解析：索引从左到右01234567,从右到左-7-6-5-4-3-2-1,A：123；B：123；C：321；D：123，故本题选C。 27.答案：A解析：range函数左闭右开，第三个参数是递增的步长，故生成的是6 8 两个数字，选A。 28.答案：B解析：数字5不在列表中，故返回False，选B，如果换成'5'，则结果是True。 29.答案：A解析：队列是先进先出，故选A。 30.答案：C解析：队列的特点就是先入先出，故输出即为输入的顺序为abcd，故选C。 31.答案：D解析：BD互斥，队列是先进先出的线性表，故选D。AC只能的说法绝对化，不选。 32.答案：B解析：最早插入的元素最先被删除，先进先出，故B正确。 33.答案：C解析：pop(1)删除的是第二个元素，当参数为0时，删除首元素。故错误的选C。 34.答案：B解析：选B，pop()默认删除的是最后一个元素，故要指定索引号为0。 35.答案：B解析：队列是先进先出，故1234进来，就是1234出去。选B。 36.答案：A解析：队列是先进先出，插入永远是在队列的末尾，故选A。 学科网（北京）股份有限公司 $$