第六章 大数据时代数据的组织 课时1 实时查询系统中数据的组织 一、基础巩固 1.下列关于分布式存储系统说法错误的是( ) A.分布式存储系统需要使用多台服务器共同存储数据 B.分布式存储系统需要多台服务器同时工作 C.分布式存储系统中的多台服务器通过网络进行连接 D.在有服务器出现故障的情况下分布式存储系统将不可用 2.使用数组来组织并存储数据时，使用二分查找算法在一个有序序列中查找新增元素的插入位置，其时间复杂度为( ) A.O(1) B.O(n) C.O(log2n) D.O(n2) 3.使用链表来组织并存储数据时，要在链表中查找新元素的插入位置，其时间复杂度为( ) A.O(1) B.O(n) C.O(log2n) D.O(n2) 4.下列有关跳跃表的描述中，不正确的是( ) A.跳跃表是一种特殊的有序链表 B.跳跃表是由多层有序链表组合而成的，最底一层的链表保存了所有的数据 C.相邻的两层链表中元素相同的节点之间存在引用关系 D.使用跳跃表不仅提高了查询效率，同时也节省了存储空间 5.有如图所示跳跃表： 若要在原链表中插入元素12，需比较的次数为( ) A.1次 B.3次 C.4次 D.5次 二、能力提升 6.有如下图所示跳跃表： 若要在原链表中查找元素27，则查找次数为( ) A.1次 B.2次 C.3次 D.4次 7.有如下图所示的跳跃表： 请画出删除元素6后的链表状态。 _____ _____ _____ 8.跳跃表是一种立足链表，借鉴二分查找的思想而形成的数据结构。能否立足有序数组，借鉴链表的思想构造一种新的数据结构来解决上述问题？ _____ 9.在组织、处理大数据时，可采用内存数据库与磁盘数据库，请从处理速度和安全性两方面说明内存数据与传统的磁盘数据库相比存在哪些优势和不足。 (1)内存数据库的优势：_____ _____ (2)内存数据库的不足：_____ _____ 课时1 实时查询系统中数据的组织 1.D [本题主要考查的是分布式存储系统。分布式存储系统需要使用多台服务器共同存储数据，但随着服务器数量的增加，服务器出现故障的概率也会不断增加。为了保证在有服务器出现故障的情况下系统仍然可用，分布式存储系统一般采用把一个数据分成多份存储在不同的服务器中的方法来解决，因此，在有服务器出现故障的情况下分布式存储系统仍将可用，答案为D。] 2.C [本题主要考查二分查找算法的时间复杂度。使用二分查找算法查找某个位置的时间复杂度为O(log2n)，因此，答案为C。] 3.B [本题主要考查的是在链表中的进行数据查找的时间复杂度。在链表中查找数据或数据位置时，需要从链表的一端依次遍历查找，因此其时间复杂度为O(n)，因此，答案为B。] 4.D [本题主要考查的是跳跃表的特点。使用跳跃表的目的在于提高了查询效率，但同时也增加一定的存储空间，因此答案为D。] 5.C [本题主要考查的是跳跃表的插入操作。要在原链表中插入元素12，关键是要找到插入的位置，通过与关键节点1、5、10、15的比较，可确定插入的位置，因此比较次数为4次，答案为C。] 6.C [本题主要考查的是在跳跃中查找数据元素。首先从二级索引中经过2次比较确定一个大致区间，然后通过对应关系到达一级索引，最终到达原链表中找到元素27，因此共查找次数为3次，答案为C。] 7.删除元素6后的链表状态为： 解析 本题主要考查的是删除跳跃表中的关键节点。当原链表中的数据元素被删除时，各级索引中的关键节点也需要随之删除，删除时按照查找时的层次从上往下依次进行，每当找到对应的元素，就删除当前层的关键节点，直到最底层的原链表。 8.能。有序数组在查找数据方面的效率较高，但在插入新数据的效率较低，因为新数据后面的数据元素需要连续后移，因此需要进行优化。将原来一个数组中的数据均匀分解存储到k个数组中，这样就将原来O(n)的移动复杂度降为O()。 9.(1)内存数据库的优势：内存数据库是将需要处理 ... ...
~~ 您好，已阅读到文档的结尾了 ~~
