专题七 数据的组织 考点清单 考点一 数组 一、数组的概念与特征 数组的概念 数组是由相同类型的变量构成的一个序列。数组使用一个标识符（数组名）命名，并用编号（下标或索引）区分数组内的各个变量。由数组名和下标组成数组的各个变量称为数组的分量，也称为数组元素。常用的数组有一维数组和二维数组。 数组的特性 数组元素的数据类型相同。 通过数组名和下标对数组元素的值进行访问。 存储空间固定不变。 二、数组的基本操作 数组的创建 数组的创建实质是在系统内存中划分一块连续区域，用来保存数组所含的所有数据元素。 数组元素的访问 通过数组名和下标直接访问数组元素。例如，a 表示一维数组 a 中的第一个元素。 数组元素的插入与删除 当需要在数组中某个位置插入一个新的数据时，必须先将该位置及其后的所有数据向后移动一个位置，在保证顺序不变的前提下保存这些数据，最后再修改该位置上的数据为新数据，时间效率较低。 在删除数组元素时，需要将被删除元素位置后的所有元素前移一个位置，同样有时间效率低的问题，而且在删除比较多的元素后，数组中存储的有效数据减少，从而造成存储空间的浪费。因此，在使用数组组织存储数据时应尽量避免数组元素的增删操作。 考点二 链表 一、链表的概念与特性 链表的概念 链表指的是将需要处理的数据对象以节点的形式，通过指针串联在一起的一种数据结构。链表中的每个节点一般由 “数据区域” 和 “指针区域” 两部分构成。链表可以根据每个节点中指针的数量分为单向链表和双向链表。 链表的特性 同一链表中每个节点的结构均相同； 每个链表必定有一个头指针，以实现对链表的引用和边界处理； 链表占用的空间不固定。 二、链表的基本操作 链表的创建 创建链表时，首先要根据问题特点规划节点的数据域和指针域，然后根据规划创建一个空链表。 链表节点的访问与遍历 链表只能通过头指针进行访问，其他节点通过节点间的指针依次访问。链表中的节点通过指针相互链接，当需要访问某个位置的节点元素时，只能通过头指针进入链表并通过节点间的链接关系逐个向下访问，直到找到指定位置的节点。与数组相比，其节点的访问效率较低。 链表节点的插入和删除 链表节点的插入指的是根据新输入的实际数据形成节点，然后修改新节点与其前驱节点的指针，将新节点插入到链表的正确位置。链表节点的删除，则通过将需要删除节点的前驱节点和其后继节点直接相连的方式实现。 三、数组与链表的区别 存储结构 数组使用一块连续的内存空间来存储一组数据，存储空间固定不变；链表不需要一块连续的空间，可通过 “指针” 将零散的空间联系起来。 数据的运算 数组通过下标可快速访问任一位置上的数据，但插入和删除数据的效率较低；链表需通过节点间的链接关系依次访问，但插入和删除数据的效率较高。 对于想要快速访问数据，又不经常插入和删除元素的情形，一般可选数组；对于需要经常插入和删除元素，而对访问元素时的效率没有很高要求的情形，一般可选链表。 考点三 队列 一、队列的概念 队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。队列中的数据元素称为队列元素。在队列中插入一个元素称为入队，从队列中删除一个元素称为出队。元素 a₁最先入队，是队首元素；元素 aₙ最后入队，是队尾元素。 二、队列的特性 先进先出、后进后出 由队列的定义可知，队列具有 “先进先出、后进后出” 的特点。出队时，队首元素 a₁优先出队，紧接着是 a₂，a₃，…，aₙ₋₁，队尾元素 aₙ最后出队。 有限序列性 队列是一种特殊的线性表结构，元素个数是有限的。队列可以是空的，也可以包含多个元素。队列中所有元素呈现线性特征，队首元素只有一个后继点，队尾元素只有一个前驱点，其他元素既有一个前驱点，又有一个后继点。 三、队列的基本操作 （一）队列的存储 队列一般按顺序结构存储，可以用数组来实现。数组 que 中存储了一个队列，共有 4 个元素，队首元素为 a₁，队尾元素为 a₄。head 记录队首元素所在的位置，tail 记录队尾元素的下一个位置。 入队与出队的 head、tail 指针变化 入队 初始时，head 指针与 tail 指针均记录下标为 0 的位置；队列元素 a₁入队，head 值不变，tail+=1；a₂、a₃、a₄入队后，head 值不变，tail 值依次增加，最终为 4。 出队 当 a₁、a₂出队后，head 记录下标为 2 的位置，tail 值不变；当 a₃、a₄出队后，head 与 tail 的值均为 4，队列为空。 队列的链式存储结构 设置队首指针 head 记录链表的头节点，队尾指针 tail 记录链表的队尾节点。 （二）建队 以数组形式存储队列为例，在 Python 程序中，用列表来实现创建队列。例如，有 4 个字母 “A”“B”“C”“D” 按序入队、出队时，可以创建一个队列 que，长度为 4，初始值空串。 Python 代码如下所示： head=0 tail=0 que=*4 （三）入队、出队 入队 字母 “A”“B”“C”“D” 按序入队时，在队列 que 中，用 tail 指针变量跟踪各元素的入队。 入队的 Python 代码如下所示： que ="A" tail=tail+1 que ="B" tail=tail+1 que ="C" tail=tail+1 que ="D" tail=tail+1 出队 出队时，排在队首的元素依次出队，head 指针变量依次加 1，直至 head 值等于 tail 值时，队列为空。 考点四 栈 一、栈的概念 栈是一种操作受限的特殊线性表，仅允许在表的一端进行插入或删除。进行插入或删除操作的一端称为栈顶，位于栈顶位置的元素称为栈顶元素；相应地，将表的另一端称为栈底，位于栈底位置的元素为栈底元素。 二、栈的特性 先进后出、后进先出 最后入栈的元素最先出栈，最先入栈的元素最后出栈。 有限序列性 同队列一样，栈中的元素也是有限的。栈可以是空的，也可以包含多个元素。栈中元素呈线性关系，栈顶元素有一个前驱点，栈底元素有一个后继点，其他元素既有一个前驱点，又有一个后继点。 三、栈与队列的区别与联系 表格 项目 不同点 相同点 队列 先进先出，后进后出 有限序列性 栈 先进后出，后进先出 考点五 树 一、树与二叉树 树（Tree）可以描述为由 n（n≥0）个节点（Node）构成的一个有限集合以及在该集合上定义的一种节点关系。集合中的元素称为树的节点，节点的度是指该节点拥有的子树数目，n=0 的树称为空树。 二叉树的概念 二叉树是一个具有 n（n≥0）个节点的有限集合，它的所有节点的度都小于或者等于 2。当 n=0 时，二叉树是一棵空树；当 n≠0 时，则是一棵由根节点和两棵互不相交的、分别称作这个根节点的左子树和右子树组成的二叉树。 二叉树的性质 二叉树的第 k 层上最多有 2ᵏ⁻¹（k≥1）个节点。 深度为 k 的二叉树最多有 2ᵏ-1（k≥1）个节点。 在任意一棵二叉树中，若度为 2 的节点数量为 n₂，叶子节点（度为 0 的节点）数为 n₀，则 n₀=n₂+1。 二、二叉树的基本操作 二叉树的建立 数组实现 二叉树可以用数组来实现。对于完全二叉树，从二叉树的根节点开始，按从上而下、自左往右的顺序对 n 个节点进行编号，根节点的编号为 0，最后一个节点的编号为 n-1。然后依次将二叉树的节点用一组连续的数组元素来表示，节点编号与数组的下标一一对应。 对于非完全二叉树，先将它补全为一棵完全二叉树，补上的节点及分支用虚线表示，然后将补全后的完全二叉树，从它的根节点开始，按从上而下、自左向右的顺序对 n 个节点进行编号，根节点的编号为 0，最后一个节点的编号为 n-1。依次把完全二叉树中原二叉树的节点用一维数组的各个元素来表示，节点编号与数组的下标一一对应。 链表实现 二叉树也可以采用链表来实现。二叉树的节点至少需要 3 个域：一个数据域和两个指针域。数据域用于存放本节点的数据信息，两个指针域分别指向节点的左孩子和右孩子。这两个指针分别称为左指针和右指针，这样得到的链表也称为二叉链表。当指针不指向任何节点时，指针域用 "" 表示。 二叉树的遍历 二叉树的遍历，是指按照一定的规则和次序访问二叉树中的所有节点，使得每个节点都被访问一次且仅被访问一次。二叉树的遍历方式有很多，主要有前序遍历、中序遍历和后序遍历等。 三、抽象数据类型 数据类型 数据类型是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。每种程序设计语言都提供了一些内置数据类型，并为每个内置类型提供了一批操作。 抽象数据类型 抽象数据类型是指一个数学模型及定义在该模型上的一组操作。程序设计语言的一个内置类型可以看作是一个抽象数据类型。 抽象数据类型的描述 形式要求：类型的名称、操作的名字、参数的个数和类型等。 功能要求：希望这个操作完成什么样的计算或产生什么效果等。 标准格式： ADT 抽象数据类型名: Data 数据元素之间逻辑关系的定义 Operation 操作 1 初始条件 操作结果描述 操作 2 操作 n endADT 考点六 大数据时代的数据的组织 一、实时查询系统中数据的组织 实时查询系统中数据业务特点 能实现上千个请求的实时响应； 支持后续数据信息的更改。 实时查询系统中的数据结构和算法设计 数组 ①查找，即在一个有序序列中查找新增元素的插入位置，可以采用二分查找算法，时间复杂度为 O (log₂n)（n 表示数组元素的总个数），速度比较快。 ②插入，即在找到可以插入的位置 x 后，将新元素插入到找到的位置 x 中，但必须先将位置 x 到 n 之间的所有元素往后移一位，为新元素空出位置，这个时间复杂度就比较大，为 O (n)。当瞬间有上千名用户提出请求，同时进行上千个这样的处理时，时效性较差。 链表 ①插入，在一个链表中插入一个新元素，时间复杂度为 O (1)，大大优于采用数组时 O (n) 的线性复杂度。 ②查找，链表虽然在插入操作时能确保 O (1) 的时间复杂度，但在进行查找时（查找新元素的插入位置），却需要从链表的一端依次遍历查找，时间复杂度为 O (n)。因此，采用链表来存储数据，虽然整体复杂度有所下降，但 O (n) 的复杂度还是达不到现实的需求。 基于链表的数据结构和算法优化设计 ①减少查找插入位置过程中的比较次数； ②借鉴二分查找算法的思想。 其他数据组织与处理方式 大部分的内存数据库主要从以下几个方面来提升数据的处理性能。减少对磁盘的访问；对数据进行分级存储；采用改进后的数据结构来组织、存储数据。 二、POI 数据的组织与应用 POI 数据的概念 POI（兴趣点）作为可以在电子地图中查询到的信息点要素，它描述了空间实体或者区域的空间位置、名称地址等信息。衡量 POI 数据价值的指标有空间位置的准确性和覆盖率、空间位置的数量。 POI 数据的组织与表示 POI 数据一般以表记录或点状数据集的形式存在。POI 数据的组织主要涉及空间索引问题，空间索引是指依据空间对象的位置和形状或者空间对象之间的某种空间关系，按一定的顺序排列的一种数据结构。 考向突破 考向一 数组 数组的创建 在 Python 中使用列表创建一维数组。 例：学校元旦文艺汇演比赛时，现场有 9 位评委给各班节目打分，统计系统需要根据 9 位评委的原始分计算平均分，作为各班表演节目的最终得分。 创建保存评委原始分的一维数组 s 的程序如下： s=*9 print (s) 在 Python 中使用列表实现二维数组有两种方式：一是直接定义，适合创建规模较小的二维数组；二是间接定义，适合创建规模较大的二维数组。 Python 列表中实现增加、删除数组元素的函数 list.append (x)：在列表 list 末尾添加元素 x list.insert (i,x)：在列表 list 中下标为 i 的位置处插入元素 x list.pop (i)：将列表 list 中下标为 i 的元素删除；若 i 不指定，默认为 - 1，即最后一个元素 例 1 （2022A9 协作体返校考，12）有如下 Python 程序段： from random import random i=0 a=*6 while i<=5: a =(int (random ()6+5))(i%2+1) for j in range (i): if a ==a : i=i-1 break i=i+1 程序执行后，数组 a 中的数据可能是 () A. B. C. D. 解析：由代码可知，随机生成的数据，执行后面代码不会改变数据也不会移动位置。当 i 等于 0、2、4 时，生成的随机数为 5~10，不会大于 10，所以 D 中的 12 错误；当 i 等于 1、3、5 时，生成的随机数要乘 2，所以是 10~20 的偶数，所以 C 中 15 错误；从代码 if a ==a :i=i-1 可知，数组 a 中不可能有相等的元素，所以 B 错误。 答案：A 针对训练 1-1（2022 衢州期末，9）小萌编写 Python 程序批量处理 “从身份证号码中提取出生年月日”，将姓名和身份证号码存储在二维数组 sfzh 中，程序划线处填入的代码为 ( ) A.sfzh B.sfzh C.sfzh D.sfzh 答案：B 1-2（2022 杭嘉湖金月考，9）有如下 Python 程序段： import random a=*6 for i in range (1,6): tmp = random.randint (5,24) if tmp%2==0 or i%2==1: a =a +tmp print (a) 运行程序后，数组 a 的值可能是 () A. B. C. D. 答案：A 考向二 链表 链表在 Python 中的表示与应用 在 Python 中创建链表 item=[] #空链表 head=-1# 表示头指针指向为空 链表节点的插入与删除 单向链表中插入新节点的过程 单向链表中删除某一节点的过程 例 2 （2022 七彩阳光返校考，10）有如下 Python 程序段： def bianli (head): pt=head while pt!=-1: print ( data ,data ,"->", end="") pt=data print () data=,,,] head=0 bianli (head) qt=head pt=data 执行该程序段后，链表遍历结果由初始状态变为最终状态，上述程序段中方框处代码的正确顺序是 () A.123B.132C.213 D.231 解析：本程序主要考查的是链表的重新链接，程序实现的效果是 A1->B2->C3->D-1->，变为 A2->C1->B3->D-1->，qt 表示前一指针，pt 表示后一指针，故 'A' 要指向 'C'，'B' 要指向 'D'，然后 'C' 要指向 'B'。 答案：D 针对训练 2-1 采用列表模拟单向链表，data 为数据区域，data 为指针区域。在单向链表指针为 p 的节点之后插入指针为 s 的节点，正确的操作是 A.data =p；data =data B.data =s；data =data C.data =data ；data =s D.data =data ；data =p 答案：C 2-2（2022 浙南名校联盟期末，12）一个头指针 head=2 的单向链表 L=,,,,] 通过以下 Python 程序段，转换为原链表的逆序链表，则方框处语句依次为 () A.321 B.312 C.132 D.123 答案：A 考向三 队列 顺序存储结构与链式存储结构的比较 顺序存储结构 空间利用率高。2) 存取某个元素速度快。3) 插入元素和删除元素存在元素移动，速度慢，耗时。4) 有空间限制，当需要存取的元素个数可能多于顺序表的元素个数时，会出现 “溢出” 问题，当元素个数远少于预先分配的空间时，空间浪费巨大。 链式存储结构 占用额外的空间以存储指针（浪费空间）。2) 存取某个元素速度慢。3) 插入元素和删除元素速度快。4) 没有空间限制，存储元素的个数无上限，基本只与内存空间大小有关。 以查找为主采用顺序表，以插入和删除为主采用链表。 在 Python 中实现队列的操作：顺序队列、循环队列、链队列。 与队列有关的 Python 模块：Python 内建有 queue 模块，可以使用 Queue () 建立对象。 例 3 目前患者到医院的就诊流程是，一般先挂号，挂号后再到相应科室的 “叫号系统” 上进行就诊登记。当科室的其中一个门诊呼叫登记患者姓名时，患者便可前往该门诊室就诊。患者在 “叫号系统” 进行登记和被呼叫去相应的门诊室就诊，分别对应队列操作中的 ( ) A. 入队、入队 B. 入队、出队 C. 出队、出队 D. 出队、入队 解析：登记是入队操作，被呼叫就诊是出队操作。 答案：B 针对训练 3-1 下列对队列的叙述不正确的是 () A. 队列属于线性表 B. 队列按 “先进先出” 原则组织数据 C. 允许插入的一端称为队首 D. 队列可以是空的，也可以包含多个元素 答案：C 3-2 有一个队列，若进队元素依次为 “A,B,C,D,E,F”，则出队的序列是 A.A,B,C,D,E,F B.F,E,D,C,B,A C.A,B,C,D,F,E D.A,B,F,E,D,C 答案：A 考向四 栈 一、栈的结构与存储 栈一般按顺序结构存储，可以用数组实现。由于栈顶元素在数组中的位置会发生改变，因此使用 top 变量来记录栈顶元素在数组中的位置。栈空时，top=-1。 二、栈的创建 在 Python 中，当要存储 n 个元素的栈时，可以用列表创建一个长度为 n 的栈。 三、入栈、出栈 入栈操作：入栈又叫压栈操作，把数据元素压入栈顶。 出栈操作：出栈时把栈顶元素取出，同时 top 值减 1。当栈中没有元素，即 top=-1 时，不能进行出栈操作。 四、建立 stack 类并进行栈操作 class Stack(): def init(self): self.my_stack=[] def push(self,data): self.my_stack.append(data) def pop(self): return self.my_stack.pop() def size(self): return len(self.my_stack) def isEmpty(self): return self.my_stack==[] 例 4 （2022A9 协作体返校考，9）一个栈的入栈序列为 1,2,3,4,5，则其出栈序列不可能为 () A.1,2,3,4,5 B.4,5,3,2,1 C.4,3,5,1,2 D.3,2,1,5,4 解析：对于某个数据而言，在它之前入栈但在它之后出栈的数据，是按入栈顺序的逆序出现的。选项 C 不可能。 答案：C 针对训练 4-1（2022 杭州地区重点中学期中，9）一个序列的入栈顺序为 1,2,3,4,5,6，若 4 第一个出栈，则下列出栈序列中不可能的是 () A.4,2,3,1,5,6 B.4,6,5,3,2,1 C.4,3,5,2,6,1 D.4,5,3,6,2,1 答案：A 4-2 设栈 S 的初始状态为空，现有 8 个元素组成的序列 (5,8,7,9,1,4,6,2)，对该序列在栈 S 上依次进行如下操作，操作后栈 S 的栈顶元素是 A.1 B.2 C.4 D.6 答案：C 考向五 树 满二叉树与完全二叉树 满二叉树：每个节点的度为 2 或 0，所有叶子节点都在同一层。 完全二叉树：至多只有最下两层节点度小于 2，最下一层叶子节点依次靠左排列。 二叉树的三种遍历 前序遍历：根→左→右 中序遍历：左→根→右 后序遍历：左→右→根 抽象数据类型与数据结构的区别 数据结构是计算机存储、组织数据的方式；抽象数据类型是数学模型及定义在模型上的一组操作。 例 5 （2022 七彩阳光返校考，9）已知二叉树中序遍历序列是 BEDAFHCIG，前序遍历序列是 ABDECFHGI，它的后序遍历序列是 () A.BDEFHCIGA B.IGHFEDCBA C.EDBFHIGCA D.EDBHFIGCA 答案：D 针对训练 5-1（2022 浙南名校联盟期末，11）已知一棵完全二叉树，其第 4 层有 3 个叶子节点，这棵二叉树的节点数量不可能是 A.25 B.24 C.11 D.10 答案：C 5-2（2022 衢州期末，10）有一棵二叉树如图所示，该二叉树的后序遍历结果正确的是 () A.XBCDAYEF B.FEYADCBX C.DBEAFXCY D.DEFABYCX 答案：D 考向六 大数据时代的数据的组织 POI 数据处理中的数据结构与算法分析 数据结构：R 树、K-D 树、四叉树；算法：二分查找、B 树查找、数据库索引查找、GeoHash。 网格索引的空间索引技术 将地理范围均等划分为 M 行 N 列网格区域，为每个网格建立空间索引，减小检索空间。 例 6 POI 数据的组织主要涉及空间索引问题。下列有关空间索引问题的描述中错误的是 () A. 空间索引是一种特殊的数据结构 B. 空间索引可以使空间操作快速访问对象 C. 空间索引技术大致分为基于链表结构和基于图结构两种 D. 经常使用网格空间索引来对 POI 建立空间索引 解析：空间索引技术大致分为基于树结构、基于网格划分等。 答案：C 针对训练 6-1 对于海量的 POI 数据进行存储及计算，下列说法错误的是 A. 基于 HDFS 文件系统的高容错性和高吞吐量特点存储空间影像数据 B. 基于单机的计算能力对地理信息专题数据进行信息提取 C. 基于 HBase 的存储可靠性强、检索性能高、存储列可按需增加的特点存储地理信息专题数据 D. 采用 Hadoop 作为地理信息存储与计算的基础框架 答案：B 6-2 有如下图所示跳跃表，若要在链表中查找元素 27，则查找次数为 A.1 B.2 C.3 D.4 答案：C