資源簡介

第六章　大數據時代數據的組織
課時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)內存數據庫的優勢：內存數據庫是將需要處理的數據保存在內存中并直接操作的數據庫，內存的讀寫速度比磁盤高出幾個數量級，因此內存數據庫在數據的輸入和輸出上極大地提高了系統的性能。內存數據庫數據處理速度比傳統數據庫的數據處理速度一般都在10倍以上。
(2)內存數據庫的不足：內存在系統中是稀缺的資源，因此內存數據庫的容量大小受物理內存的限制，通常只有熱點或者高頻數據進行處理，而不是全部數據。安全性是內存數據庫最大的問題，電腦一旦斷電或重啟，內存中的信息將會丟失，因此在使用內存數據庫時，通常需要提前對內存上的數據采取一些保護機制，比如備份，記錄日志，熱備或集群，與磁盤數據庫同步等方式。課時2　POI數據的組織與應用
1.隨著計算機技術、通信技術和3S技術的發展融合，互聯網環境中的地理信息服務已經成為人們網絡生活的重要組成部分，這里的3S是指地理信息系統GIS、全球定位系統GPS和(　　)
A.通信技術 B.遙感技術
C.虛擬現實技術 D.無線網絡技術
2.在導航地圖中搜索“美食”后顯示效果如圖所示，可知該電子地圖上表示POI的圖標是(　　)
A.圓點 B.形狀 C.氣泡 D.直線
3.衡量POI數據價值的指標有(　　)
①空間位置的準確性 ②信息點的類別
③空間位置的數量 ④信息點的經緯度
⑤空間位置的覆蓋率
A.①③⑤ B.③④⑤
C.①③④⑤ D.①②③④⑤
4.以下不屬于POI數據的組織采用空間索引目的的是(　　)
A.快速訪問空間對象 B.縮短空間查詢時間
C.縮小空間搜索范圍 D.提供海量存儲空間
5.如圖所示，將一幅地圖的地理范圍均等劃分為M行N列，得到M×N個小矩形網格區域。每一個網格區域為一個索引項，該技術的名稱為(　　)
A.網格索引 B.樹結構索引 C.云計算 D.表格劃分
二、能力提升
6.以下關于POI數據的描述中不正確的是(　　)
A.電子地圖上的景點、公司、商場、飯館等，都是POI
B.POI描述了空間實體或者區域的空間位置、名稱地址等信息
C.POI數據一般用Access等小型數據庫來進行組織和存儲
D.Hadoop為海量POI數據的存儲與計算提供了保障
7.下列有關空間索引問題的描述中，錯誤的是(　　)
A.空間索引包含對象的概要信息，如對象的標識等
B.空間索引可以縮短空間查詢時間，提高效率
C.POI數據可能出現在多個索引位置中，經常使用網格空間索引來對POI建立空間索引
D.空間索引是指依據空間對象的位置和形狀或對象間某種空間關系，按一定順序排列的數據結構
8.將一個經緯度信息，轉換成一個可以排序，可以比較的字符串編碼，如下圖所示，從而做到高效地查找臨近POI點的算法稱為(　　)
A.二分查找 B.對分查找 C.N分查找 D.GeoHash
課時2　POI數據的組織與應用
1.B　[本題主要考查的是3S技術。3S技術是指遙感技術(Remote sensing，RS)、地理信息系統(Geography information systems，GIS)和全球定位系統(Global positioning systems，GPS)的統稱，因此，答案為B。]
2.C　[本題主要考查的是電子地圖上POI的表示形式。該電子地圖表示POI的圖標是氣泡，因此，答案為C。]
3.A　[衡量POI數據價值的指標有空間位置的準確性和覆蓋率、空間位置的數量，因此，答案為A。]
4.D　[本題考查的是POI數據的組織與表示。空間索引可以使空間操作快速訪問對象，縮短空間查詢時間，縮小空間搜索范圍，從而提高效率。提供海量存儲空間不屬于POI數據的組織采用空間索引目的，因此，答案為D。]
5.A　[本題考查的是POI數據的組織與表示。空間索引技術大致分為基于樹結構、基于網格劃分等。本題的描述是網格索引的空間索引技術。]
6.C　[本題考查的是POI數據的概念、組織與表示等。POI海量數據不可能用小型數據庫來進行組織和存儲。]
7.C　[本題主要考查的是POI數據的組織中空間索引問題。POI數據本身是點信息，一個數據僅可能出現在一個索引位置中，因此經常使用網格空間索引來對POI建立空間索引，因此，答案為C。]
8.D　[本題主要考查的是GeoHash算法。GeoHash算法把一個坐標點映射到一個字符串上，每個字符串代表的就是一個以經緯度劃分的矩形區域，而每個區域又可以劃分為許多個子區域，并對經緯度不斷地進行二分，最終確定到想要的精度，每個區域最后都得到一個二進制的字符串，這樣就可以快速進行周邊POI查找之類的功能。]

展開更多......

收起↑