资源简介

(共35张PPT)
专题一　数据与数据的组织、大数据时代
数据的组织
选择性必修1　数据与数据结构
思维导图
归纳提炼
一、数据
1.数据的表现形式
数据的表现形式有数字、数值、文字、图形、图像、音频、视频等。
(1)数字
数字是指由阿拉伯数字“0,1,2,3,4,5,6,7,8,9”或其他含义相同的符号表示。
数字本身是没有意义的,没有量的含义,只有在具体的情境中才有实际意义。
重难点剖析
(2)数值
数值是指由数字符号组成的、具有量的意义的、可以进行算术运算的数据。
(3)其他表现形式
数据的其他表现形式有:在快速处理图形、图像、音频、视频等数据的基础上做出即时的互动反应(如利用虚拟现实技术的活动或游戏中),甚至能做出一些人类特有的智能化行为(如无人驾驶汽车等)。
2.数据的价值与意义
(1)数据促进了人类社会的发展。
(2)大数据推动人类进入一个崭新的时代。
二、数据的组织
1.数据结构的概念
(1)数据元素
①数据元素是数据的基本单位,可由若干个数据项组成。
②数据项是具有独立含义的最小数据表示单位。
(2)数据类型
①数据类型是指具有相同性质的计算机数据的集合及在这个数据集合上的一组操作。
②数据类型可以分为基本数据类型和结构数据类型。
(3)数据结构
①数据结构是指数据之间的相互关系,即数据的组织形式。
②数据结构主要包括数据的逻辑结构、数据的存储结构或物理结构和数据的运算。
2.常见的数据结构
(1)数组
①数组用于存储一批数据,除可以描述数据对象本身之外,还可描述数据所处的位置或数据之间的前后顺序关系。
②可通过下标精确地访问序列中的某个数据元素,又可通过下标依次按顺序遍历序列中的每个数据元素。
(2)链表
①表示一批数据,这类数据之间具有明确的相互链接的前后顺序,但对数据对象本身的位置信息不作要求。
②常用的链表有单向链表、双向链表和循环链表。
(3)队列
①数据具有“先进先出”且中间不能“插队”的组织和操作的性质。
②在队列的头部(队首)进行数据的读取(即出队),在数据序列的尾部(队尾)进行数据的插入(入队)操作。
(4)栈
①数据具有“先进后出”且所有操作只能在一端(栈顶)进行的性质。
②仅可在一端进行数据的读取(出栈)和插入(入栈)操作。
(5)树
数据元素前面只有一个元素,后面可以有0个或多个元素相邻,所有数据元素之间的关系特征像一棵倒放的树。
三、大数据时代数据的组织
(一)实时查询系统中数据的组织
大数据背景下的数据组织和存储方式采用分布式存储系统。分布式存储系统利用分布在不同物理位置的服务器来分担系统存储任务,既能提高数据存储的安全性,又能提升系统数据访问的速度,同时也具有较好的可扩展性。
1.实时查询系统中的数据业务特点
(1)能实现上千个请求的实时响应。
(2)支持后续商品信息的更改。
2.实时查询系统中的数据结构和算法设计
(1)基于数据间线性关系的数据结构设计
读取数据库中的数据并保存到内存中,可采用数组或链表结构来组织和存储。
数据结构 查找操作 插入操作
数组 采用二分查找算法,时间复杂度为O(log2n),查找速度快,效率高 数据移动较多,时间复杂度O(n),效率较低
链表 需从链表的一端依次遍历查找,时间复杂度为O(n),效率较低 不需要数据移动,时间复杂度为O(1),效率较高
使用数组和链表的方式进行数据查找和插入的特点如下表所示。
(2)基于链表的数据结构和算法优化设计
■优化方法
①减少查找插入位置过程中的比较次数。
②借鉴二分查找算法的思想。
■跳跃表
跳跃表,是一种立足链表,借鉴二分查找的思想而形成的数据结构。跳跃表是在原有的有序链表上增加了多级索引,通过索引来实现快速查询。 “跳跃表”以空间换时间,时间复杂度为O(log2n)。
缺点:维护成本高,增加删除都需要更新索引。
解决方法:
①增设关键节点。对新增元素基于“抛硬币”原则的选拔,以确定是否把新增元素提升为上一层的关键节点,并且逐层进行。
②删除关键节点。删除时按照查找时的层次从上往下依次进行,每当找到对应的元素,就删除当前层的关键节点,直到最底层的原链表。
3.其他数据组织与处理方式
(1)采用内存数据库代替传统的磁盘数据库来组织、处理海量的数据。
(2)内存数据库进行数据处理的特点
①减少对磁盘的访问。
内存数据库通过对磁盘的访问,可将数据处理速度提高10~1000倍。
②对数据进行分级存储。
内存数据库对所有需要处理的数据重新进行组织,并进行数据分级,再在处理器缓存中进行分级存储,进一步提升数据的存取效率。
③采用改进后的数据结构来组织、存储数据。
内存数据库将数据在内存中进行重新组织、存储,进行新的体系结构设计,用更快速的算法来处理数据。
(二)POI数据的组织与应用
1.POI数据的概念
(1)POI数据的含义
POI是 “Point of Interest”的缩写,可以翻译成“兴趣点”,有些时候也叫作“Point of Information”,即“信息点”。电子地图上一般用气泡图标来表示POI。
(2)POI数据的内容
POI描述了空间实体或者区域的空间位置、名称、类别、空间坐标信息(经纬度)、地址、电话、邮政编码等信息。
(3)衡量POI数据价值的指标
①空间位置的准确性和覆盖率。
②空间位置的数量。
(4)POI数据的应用
在社会各个领域都得到了广泛的应用,如公交动态数据、车载导航等。
2.POI数据的组织与表示
(1)POI数据的存在形式
一般以表记录或点状数据集的形式存在。
(2)POI数据处理
采用Hadoop作为地理信息存储与计算的基础框架。
(3)网格索引的空间索引技术
将一幅地图的地理范围均等划分为M行N列,得到M×N个小矩形网格区域。每一个网格区域为一个索引项,为全部或者部分落入该网格内的地图对象建立空间索引,检索空间将大大减小。
典型例题
[例1] 某地图导航APP在导航服务中调用全球卫星导航系统,其日定位请求次数超过3 000亿次,使道路交通情况预测的准确度得到提高。下列有关该APP的说法,正确的是(　 　)
A.该APP数据传输时不需要传输介质
B.根据交通路况实时更新导航路线采用批处理计算
C.用户在使用导航数据的同时自身也在产生数据
D.因导航中数据体量大,预测未来交通情况采取抽样数据分析
C
解析:本题主要考查数据及数据传输的相关知识。该APP数据传输时需要传输介质,因此A选项错误;根据交通路况实时更新导航路线采用流计算,因此B选项错误;大数据分析的是全体数据,而不是抽样数据,因此D选项错误;用户在使用导航数据的同时自身也在产生数据,因此C选项正确,故答案为C。
[例2] 下列关于数据结构的描述,正确的是(　 　)
A.数据的物理结构是指数据元素之间的逻辑排列和对应关系
B.数据的逻辑结构是指数据元素及其关系在计算机存储器内的表示
C.数据的运算是指对数据施加的操作,但仅包括插入和删除数据
D.数据结构设计的目的是使数据元素间的相互关系能准确地反映现实问题中的事物逻辑
D
解析:数据的逻辑结构是指数据元素之间的逻辑排列和对应关系,因此A选项错误;数据的物理结构是指数据元素及其关系在计算机存储器内的表示,因此B选项错误;数据的运算不仅包括插入和删除数据,还可以进行查找和修改数据等操作,因此C选项错误;数据结构设计的目的是使数据元素间的相互关系能准确地反映现实问题中的事物逻辑,既确保数据处理的正确性,又提高编程实现和数据处理的效率,因此答案为D。
[例3] 用一带盖的桶来存放碟子,放、取碟子只能在桶的一端进行(另一端为封闭状态),且桶的直径只允许一个碟子进出。若放入碟子的编号序列为1、2、3、4、5,则取出碟子的编号序列不可能是(　 　)
A.1、2、3、4、5 B.1、4、5、2、3
C.5、4、3、2、1 D.3、2、1、4、5
B
解析:桶的一端封闭,放入和取出碟子只能在另一端进行,与数据结构中栈的入栈和出栈过程相似。根据栈的先进后出、后进先出的性质,在放入碟子的顺序固定为1、2、3、4、5的情况下,当第N个碟子出栈后,栈内剩余的碟子是降序出栈的。B选项中,1号、4号、5号出栈后,栈内剩余的是2号和3号,则出栈顺序必然是先3号后2号,因此出栈序列1、4、5、2、3是不可能的,故答案为B。
[例4] 下列关于队列的入队、出队操作的说法中,正确的是(　 　)
A.最先入队的元素最后出队
B.出队时需要判断队列是否为空
C.在队列中添加元素是在队列头部进行的
D.出队操作时,先取出队首元素,然后队尾指针加1
B
解析:本题考查队列的操作。队列的特点是先进先出,因此最先入队的元素最先出队,因此A选项错误;在队列中,插入元素是在队列的尾部进行,因此C选项错误;出队操作时,先取出队首元素,然后队首指针加1,因此D选项错误;出队时需要判断队列是否为空,当队列不为空时,才能执行出队操作,因此B选项正确,故答案为B。
[例5] 数组a中存储的数据情况如下图所示:
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8]
8 6 5 4 2 1 3 0 7
从a[0]开始查找数组元素“2”需要查找的次数为(　 　)
A.1 B.3 C.4 D.5
C
解析:从a[0]开始查找, 数组元素“2”在数组是第5个数据,因此共需查找4次,答案为C。
[例6] 有如下图所示的单向链表:
D
从头指针head指向的节点开始查找数据元素“5”,并删除该节点,下列说法正确的是(　 　)
A.共需查找3次
B.删除数据元素“5”的节点,后续节点需要移动3次
C.头指针head将指向数据元素“7”的节点
D.此时链表中数据元素的个数为6个
解析:从头指针head指向的节点开始查找数据元素“5”,共需查找4次,因此A选项错误;删除数据元素“5”的节点,后续节点不需要移动,因此B选项错误;头指针head始终指向头节点,因此C选项错误;删除数据元素“5”的节点后,链表中的数据元素个数为6个,因此答案为D。
感谢观看

展开更多......

收起↑