资源简介

(共12张PPT)
一、 实时查询系统中数据的组织
第六章　大数据时代数据的组织
信息技术 选择性必修1 数据与数据结构
必备知识练
1. 下列关于某购物网站数据业务特点的说法,错. 误. 的是(　　)
A. 支持在同一时刻,实现上千名用户的不同查询请求
B. 允许在用户提出查询请求后更改商品信息
C. 能在用户查询结果中,实时显示商品修改信息
D. 被修改的商品信息能显示在后续的查询结果中
【解析】 在用户查询结果已显示的情况下修改商品信息,此最新信息不会显示在已显示的查询结果中,除非再执行一次查询操作,最新的修改信息才会显示在最新的查询结果中,C符合题意。
C
2. 下列数据结构操作与时间复杂度相匹配的是(　　)
A. 数组插入新元素操作——时间复杂度O(1)
B. 数组利用二分法查询某元素——时间复杂度O(n)
C. 链表插入新元素操作——时间复杂度O(1)
D. 跳跃表查询某元素——时间复杂度O(n)
【解析】 数组插入操作的时间复杂度是O(n),A错误;二分法查找元素的时间复杂度是O(log2n),B错误;链表的插入与删除操作的时间复杂度为O(1),C正确;跳跃表查询某元素的时间复杂度是O(log2n),D错误。
C
3. 某跳跃表有二层索引,二级索引节点为 a → m ,下列说法中,正确的是(　　)
A. 其一级索引节点可能为 a → c → f → g → k → y
B. 其顶层索引节点可能为 a
C. 若查找元素 m ,则需要比较4次
D. 已知原始链表包含节点 t ,删除 t 后索引层数可能发生变化
【解析】 二级索引节点是由一级索引节点选取的,因此二级索引的节点在一级索引中必然存在,A错误。顶层索引节点若为1个则没有查找意义,因此顶层索引只有2个节点,B错误。若要查找m,则从二级索引开始,比较2次,找到m后一直下沉到原始链表,中间也算比较次数。因此需要比较4次,C正确。因为节点t不在二级索引中,所以删除t不会影响索引层数,D错误。
C
4. 某跳跃表的原始链表节点为 a → b → d → j → p ,下列说法中,正确的是(　　)
A. 该跳跃表的索引层最多为两层
B. 顶层的索引节点可能为 a → b
C. 在原始链表中插入新节点 y 会使得索引层数增加
D. 删除原始链表的节点 d 不会影响索引层数
【解析】 跳跃表的索引层数是通过一定概率产生的,所以并不确定,A错误;在原始链表中插入新节点,若新节点不出现在后续的索引层中,则不会使得索引层数增加,C错误;反之,在原始链表中删除节点,若节点在顶层索引中出现,则索引层数会减少,D错误。
B
5. 已知某跳跃表有2层索引,原始链表节点为 1 → 4 → 9 → 17 → 21 → 45 ,二级索引节点为 1 → 45 ,若查询节点 21 ,则至少需要比较的次数为(　　)
A. 3 B. 4
C. 5 D. 6
【解析】 若要达到最少比较次数,则一级索引中必须包含节点 21 ,为了减少比较次数,在节点 1 与 21 之间不能增设节点,因此一级索引应当为 1 → 21 → 45 ,此时在二级索引比较2次,下沉到一级索引节点 1 处比较1次,再与一级索引节点 21 比较1次,下沉到原始链表的节点 21 比较1次,总共比较5次。C正确。
C
6. 有如图所示的跳跃表:
若要在原链表中查找元素27,则查找次数为(　　)
A. 1次 B. 2次
C. 3次 D. 4次
【解析】 本题考查在跳跃中查找数据元素。首先从二级索引中经过2次比较确定一个大致区间,然后通过对应关系到达一级索引,最终在原链表中找到元素27,因此查找次数为3,C正确。
C
7. 有如图所示的跳跃表:
请画出删除元素6后的链表状态。
【答案】 删除元素6后的链表状态为:
【解析】 本题考查删除跳跃表中的关键节点。当原链表中的数据元素被删除时,各级索引中的关键节点也需要随之删除,删除时按照查找时的层次从上往下依次进行,每当找到对应的元素,就删除当前层的关键节点,直到最底层的原链表。
8. 跳跃表是一种立足于链表,借鉴二分查找的思想而形成的数据结构。能否立足有序数组,借鉴链表的思想构造一种新的数据结构来解决上述问题 请判断并说明理由。
【答案】 能。有序数组在查找数据方面的效率较高,但在插入新数据的效率较低,因为新数据后面的数据元素需要连续后移,因此需要进行优化。将原来一个数组中的数据均匀分解存储到k个数组中,这样就将原来O(n)的移动复杂度降为O(k)。
9. 组织、处理大数据时,可采用内存数据库与磁盘数据库,请从处理速度和安全性两方面说明内存数据库与传统的磁盘数据库相比存在的优势和不足。
(1)内存数据库的优势:
【答案】 内存数据库是将需要处理的数据保存在内存中并直接操作的数据库,内存的读写速度比磁盘高出几个数量级,因此内存数据库在数据的输入和输出上极大地提高了系统的性能。内存数据库数据处理速度比传统数据库的数据处理速度一般都在10倍以上。
(2)内存数据库的不足:
【答案】 内存在系统中是稀缺的资源,因此内存数据库的容量大小受物理内存的限制,通常只有热点或高频数据进行处理,而不是全部数据。安全性是内存数据库最大的问题,电脑一旦断电或重启,内存中的信息将会丢失,因此在使用内存数据库时,通常需要提前对内存上的数据采取一些保护机制,比如备份、记录日志、热备或集群、与磁盘数据库同步等方式。一、 实时查询系统中数据的组织
1. 下列关于某购物网站数据业务特点的说法,错误的是(　C　)
A. 支持在同一时刻,实现上千名用户的不同查询请求
B. 允许在用户提出查询请求后更改商品信息
C. 能在用户查询结果中,实时显示商品修改信息
D. 被修改的商品信息能显示在后续的查询结果中
【解析】 在用户查询结果已显示的情况下修改商品信息,此最新信息不会显示在已显示的查询结果中,除非再执行一次查询操作,最新的修改信息才会显示在最新的查询结果中,C符合题意。
2. 下列数据结构操作与时间复杂度相匹配的是(　C　)
A. 数组插入新元素操作——时间复杂度O(1)
B. 数组利用二分法查询某元素——时间复杂度O(n)
C. 链表插入新元素操作——时间复杂度O(1)
D. 跳跃表查询某元素——时间复杂度O(n)
【解析】 数组插入操作的时间复杂度是O(n),A错误;二分法查找元素的时间复杂度是O(log2n),B错误;链表的插入与删除操作的时间复杂度为O(1),C正确;跳跃表查询某元素的时间复杂度是O(log2n),D错误。
3. 某跳跃表有二层索引,二级索引节点为 a → m ,下列说法中,正确的是(　C　)
A. 其一级索引节点可能为 a → c → f → g → k → y
B. 其顶层索引节点可能为 a
C. 若查找元素 m ,则需要比较4次
D. 已知原始链表包含节点 t ,删除 t 后索引层数可能发生变化
【解析】 二级索引节点是由一级索引节点选取的,因此二级索引的节点在一级索引中必然存在,A错误。顶层索引节点若为1个则没有查找意义,因此顶层索引只有2个节点,B错误。若要查找m,则从二级索引开始,比较2次,找到m后一直下沉到原始链表,中间也算比较次数。因此需要比较4次,C正确。因为节点t不在二级索引中,所以删除t不会影响索引层数,D错误。
4. 某跳跃表的原始链表节点为 a → b → d → j → p ,下列说法中,正确的是(　B　)
A. 该跳跃表的索引层最多为两层
B. 顶层的索引节点可能为 a → b
C. 在原始链表中插入新节点 y 会使得索引层数增加
D. 删除原始链表的节点 d 不会影响索引层数
【解析】 跳跃表的索引层数是通过一定概率产生的,所以并不确定,A错误;在原始链表中插入新节点,若新节点不出现在后续的索引层中,则不会使得索引层数增加,C错误;反之,在原始链表中删除节点,若节点在顶层索引中出现,则索引层数会减少,D错误。
5. 已知某跳跃表有2层索引,原始链表节点为 1 → 4 → 9 → 17 → 21 → 45 ,二级索引节点为 1 → 45 ,若查询节点 21 ,则至少需要比较的次数为(　C　)
A. 3 B. 4
C. 5 D. 6
【解析】 若要达到最少比较次数,则一级索引中必须包含节点 21 ,为了减少比较次数,在节点 1 与 21 之间不能增设节点,因此一级索引应当为 1 → 21 → 45 ,此时在二级索引比较2次,下沉到一级索引节点 1 处比较1次,再与一级索引节点 21 比较1次,下沉到原始链表的节点 21 比较1次,总共比较5次。C正确。
6. 有如图所示的跳跃表:
若要在原链表中查找元素27,则查找次数为(　C　)
A. 1次 B. 2次
C. 3次 D. 4次
【解析】 本题考查在跳跃中查找数据元素。首先从二级索引中经过2次比较确定一个大致区间,然后通过对应关系到达一级索引,最终在原链表中找到元素27,因此查找次数为3,C正确。
7. 有如图所示的跳跃表:
请画出删除元素6后的链表状态。
【答案】 删除元素6后的链表状态为:
【解析】 本题考查删除跳跃表中的关键节点。当原链表中的数据元素被删除时,各级索引中的关键节点也需要随之删除,删除时按照查找时的层次从上往下依次进行,每当找到对应的元素,就删除当前层的关键节点,直到最底层的原链表。
8. 跳跃表是一种立足于链表,借鉴二分查找的思想而形成的数据结构。能否立足有序数组,借鉴链表的思想构造一种新的数据结构来解决上述问题 请判断并说明理由。
【答案】 能。有序数组在查找数据方面的效率较高,但在插入新数据的效率较低,因为新数据后面的数据元素需要连续后移,因此需要进行优化。将原来一个数组中的数据均匀分解存储到k个数组中,这样就将原来O(n)的移动复杂度降为O(k)。
9. 组织、处理大数据时,可采用内存数据库与磁盘数据库,请从处理速度和安全性两方面说明内存数据库与传统的磁盘数据库相比存在的优势和不足。
(1)内存数据库的优势:
【答案】 内存数据库是将需要处理的数据保存在内存中并直接操作的数据库,内存的读写速度比磁盘高出几个数量级,因此内存数据库在数据的输入和输出上极大地提高了系统的性能。内存数据库数据处理速度比传统数据库的数据处理速度一般都在10倍以上。
(2)内存数据库的不足:
【答案】 内存在系统中是稀缺的资源,因此内存数据库的容量大小受物理内存的限制,通常只有热点或高频数据进行处理,而不是全部数据。安全性是内存数据库最大的问题,电脑一旦断电或重启,内存中的信息将会丢失,因此在使用内存数据库时,通常需要提前对内存上的数据采取一些保护机制,比如备份、记录日志、热备或集群、与磁盘数据库同步等方式。

展开更多......

收起↑