大數據算法 課后答案總匯

大數據算法(課后答案總匯)

第一講大數據算法概述

大數據算法概述

第一講作業(yè)

第二講亞線性算法

亞線性算法概述

亞線性算法概述單元測驗

第三講亞線性算法例析

亞線性算法例析

第三講作業(yè)

第四講外存算法概述

外存算法概述

第四講作業(yè)

第五講外存查找結構

外存查找結構

第五講作業(yè)

第六講外存圖數據算法

外存圖數據算法

第六講作業(yè)

第七講基于MapReduce的并行算法設計

基于MapReduce的并行算法設計

第七講作業(yè)

第八講MapReduce算法例析

MapReduce算法例析

第九講超越MapReduce的并行大數據處理

超越MapReduce的并行大數據處理

第九講作業(yè)

第十講眾包算法

眾包算法

第十講作業(yè)

1【單選題】

以下關于大數據的特點,敘述錯誤的是()。

A、速度慢

B、多元、異構

C、數據規(guī)模大

D、基于高度分析的新價值

我的答案：A

2【單選題】在《法華經》中，“那由他”描寫的“大”的數量級是()。

A、10A7

B、10A14

C、10A28

D、10A56

我的答案：C

3【多選題】以下選項中，大數據涉及的領域中包括()。

A、社交網絡

B、醫(yī)療數據

C、計算機藝術

D、醫(yī)療數據

我的答案：ABCD

4【多選題】大數據的應用包括()。

A、預測

B、推薦

C、商業(yè)情報分析

D、科學研究

我的答案：ABCD

5【判斷題】目前,關于大數據已有公認的確定定義。

我的答案：X

6【判斷題】大數據種類繁多,在編碼方式、數據格式、應用特征等方面都存在差異。()

我的答案：J

【單選題】

大數據求解計算問題過程的第三步一般是()。

A、判斷可計算否

B、判斷能行可計算否

C、算法設計與分析

D、用計算機語言實現算法

我的答案：C

2【多選題】在大數據求解計算問題中,判斷是否為能行可計算的因素包括()。

A、數據量

B、資源約束

C、速度約束

D、時間約束

我的答案：ABD

3【判斷題】大數據求解計算問題過程的第一步是確定該問題是否可計算。

我的答案：，

4【判斷題】大數據計算模型與一般小規(guī)模計算模型一樣，都使用的是圖靈機模型。

我的答案：，

【多選題】資源約束包括()。

A、CPU

B、網絡帶寬

C、內存

D、外存

我的答案：ABCD

2【多選題】大數據算法可以不是()。

A、云計算

B、精確算法

C、內存算法

D、串行算法

我的答案：BCD

3【判斷題】大數據算法是在給定的時間約束下，以大數據為輸入,在給定資源約束內可以生成滿足給定約束結果的算法。

我的答案：x

4【判斷題】MapReduce是一種比較好實現大數據算法的編程架構，在生產中得到廣泛應用。

我的答案：，

5【判斷題】大數據算法是僅在電子計算機上運行的算法。

我的答案：x

1【單選題】

眾包算法是用來解決()。

A、訪問全部數據時間過長

B、數據難于放入內存計算

C、單個計算機難以保存全部數據，計算需要整體數據

D、計算機計算能力不足或知識不足,需要人來幫忙

我的答案：D

2【單選題】大數據算法存在很多難題,對于訪問全部數據時間過長的問題，采用的解決方案是()。

A、將數據存儲到磁盤上

B、僅基于少量數據進行計算

C、讀取部分數據

D、并行處理

我的答案：C

3【多選題】大數據算法的()特點，使其與大數據算法密切相關的。

A、數據量大

B、基于高度分析的新價值

C速度快

D、多樣性、復雜性

我的答案：AC

4【判斷題】為解決單個計算機難以保存全部數據的問題，通常會采用并行處理的技術,此技術會涉及到時間亞線性算法。

我的答案：x

【單選題】大數據算法涉及到外存的時候，通常要分析()。

A、時間空間復雜性

B、10復雜性

C、結果質量

D、通訊復雜性

我的答案：B

2【多選題】下列選項中，屬于智能仿生算法的是()。

A、遺傳算法

B、近似算法

C、模擬退火算法

D、數據流算法

我的答案：AC

3【判斷題】在線算法/數據流算法是面向大數據速度快的特點提出的。()

我的答案：，

4【判斷題】對于數據流算法或在線算法，經常要分析結果的近似比。()

我的答案：x

5【判斷題】隨機算法是利用隨機化的方法來進行大數據處理，是大數據算法設計技術之一。()

我的答案：，

1【單選題】計算在一個給定社交網絡中平均每人的朋友個數，在不訪問所有頂點的情況下,進行精確計算最少需要訪問()個頂點。

A、n2

B、n+1

C、2n

D、n-1

我的答案：D

2【多選題】亞線性是指()等的消耗是輸入規(guī)模()

A、時間

B、空間

Cs10

D、通訊

我的答案：ABCD

3【判斷題】性質檢測算法屬于亞線性空間算法的一類。()

我的答案：x

【判斷題】

在經典的水庫抽樣中，要求空間復雜性為0(k),是指與抽樣大小有關，而與整個數據的數據量無關。

我的答案：V

2【判斷題】水庫抽樣算法的采樣是均勻的。

我的答案：V

【單選題】

以下()不是衡量分析近似解代價與優(yōu)化解代價差距的方法。

A、RatioBound

B、相對誤差

C、絕對誤差

D、(1-E)-近似

我的答案：C

2【單選題】利用平面圖的直徑近似算法得到的解，在最壞情況下,也不會小于最優(yōu)解的()。

A、二分之一

B、三分之一

C、四分之一

D、十分之一

我的答案：A

3【單選題】采用平面圖的直徑近似算法的動機是無法在要求的時間內得到()。

A、相似解

B、完整解

C、精確解

D、近似解

我的答案：C

4【判斷題】在平面圖的直徑近似算法中，要求點之間的距離滿足三角不等式是指在i、j、k三個點中,i到j的距離加上j到k的距離小于i到k的距

離。

我的答案：x

5【判斷題】近似算法能給出一個優(yōu)化問題的優(yōu)化解。

我的答案：x

6【判斷題】RatioBound越大，則近似解越壞。()

我的答案：，

1【多選題】

在判定問題的近似中，對于近似解需要區(qū)分的是()。

As是

B、否

C、差不離

D、差得很遠

我的答案：AD

2【判斷題】全0數組判定的近似算法的證據引理是:如果一次測試以大于等于p的概率獲得一個證據，那么s=2/p輪測試得到證據的概率大于

等于1/2。

我的答案：x

3【判斷題】判定問題的近似解是指:輸入滿足某種性質或近似滿足某種性質。

我的答案：x

1【判斷題】

Zipf原則是指典型的頻率分布是高度偏斜的,存在很多頻繁元素。()

我的答案：x

2【判斷題】在數據流模型中，從數據流中可以計算簡單的函數，如最大值、最小值、求和等，且處理這些函數時通常使用單個寄存器s。()

我的答案：，

3【判斷題】數據流模型中，數據流是指來自某個域中的元素序列。()

我的答案：，

4【判斷題】在數據流模型中,內存遠遠大于數據的規(guī)模。()

我的答案：x

1【單選題】

頻繁元素計算算法又稱為()算法。

A、MM

B、MG

C、GM

D、MP

我的答案：B

2【單選題】頻繁元素計算算法有效的原因是源于()。

A、取近似解

B、證據引理

C、錯誤界限和k成反比

D、Zipf原則

我的答案：D

3【判斷題】在頻繁元素計算算法中,計數器x減少的次數依賴于有幾個減少計數器的步驟。()

我的答案：V

4【判斷題】在頻繁元素計算算法中，當數據流中元素的總個數遠大于估計值與真實值相差的最多值時，可以得到頻繁項一個好的估計。

我的答案：V

1【單選題】

時間亞線性算法的思想是:利用特定子圖聯(lián)通分量的數量估計最小生成樹的()。

A、近似值

B、精確值

C、權重

D、界限

我的答案：C

2【單選題】求最小生成樹是一個貪心法，可以用()算法來解決。

A、Prime

B、并行

C、MG

D、內存

我的答案：A

3【判斷題】對聯(lián)通分量個數的估計可以利用隨機化方法。

我的答案：V

【單選題】

對于輸入n個數的數組(xl,x2,x3,……,xn),輸出:這個數組是否有序?！赀h離意味著必須刪除大于()個元素才能保證剩下的元素有序。

A、E-n

B、En

CE/n

D、n/E

我的答案：B

2【判斷題】如果一次測試以大于等于p的概率獲得一個證據，那么s=2/p輪測試得到證據的概率大于等于3/4。

我的答案：x

3【判斷題】關于證明如果輸入￡遠離有序，則存在大于個“壞索引”的問題，可以采用證明其逆否命題的方法。

我的答案：V

【單選題】

下列選項中敘述正確的是()。

A、磁盤的訪問可以隨機讀、隨機取

B、磁盤系統(tǒng)傳輸大規(guī)模連續(xù)的數據塊的范圍是18-32k

C、磁盤訪問比主存訪問的速度快

D、大多數程序在RAM模型上運行

我的答案：

2【判斷題】對于大數據而言，標準計算理論模型失效的原因之一是內存是有限的，無法存儲所有的內存。（）

我的答案：，

3【判斷題】當內存不夠或者算法設計不好時，如果數據量達到一定規(guī)模以上，運行時間會急劇增加。

我的答案：，

4【判斷題】現代計算機有復雜的存儲層次，存儲單元的訪問是以塊為單位的數據移動。（）

我的答案：，

【單選題】

在內存中的二分搜索樹中，通常使用（）來維護樹的平衡。（）

A、置換

B、分裂

C、旋轉

D、合并

我的答案：C

2【判斷題】二叉搜索樹是在n個元素之間搜索的標準方法，一般把元素保存在根處。（）

我的答案：x

3【判斷題】為更快地保存外部搜索樹，可采取按BFS的順序將其分割。（）

我的答案：J

1【單選題】

外存歸并排序，以（）為單位進行調度。

A、比特

B、兆

C、塊

D、層

我的答案：C

2【判斷題】排序分為內部排序和外部排序，外部排序是因排序的數據很大，一次不能容納全部的排序內容，在排序過程中需要訪問外存。（）

我的答案：，

1【單選題】在外排序的快速排序中,分割元素的選擇非常重要。

A、正確

B、錯誤

我的答案：A

1【單選題】如果T是一個（a,b）-樹（a三2且b三2a-l）淇根結點的度在（）之間。

A、2到a

B、2到b

C、a到b

D、2到4

我的答案：B

2【判斷題】在（a,b）-樹中,a和b表示的是每個節(jié)點當中鍵值的上限和下限。（）

我的答案：x

3【判斷題】B-樹中右邊的指針指向的是鍵值小于最右鍵值的子數。（）

我的答案：x

【單選題】

元素都在葉子中的B-樹有時被稱為（）。

A、B+樹

B、B-+樹

C、B土樹

D、B士數

我的答案：C

2【判斷題】關于(a,b)一樹的刪除操作，刪除操作出現問題的情形是:從葉子v刪除元素后,v的兒子小于a-1個。()

我的答案：，

3【判斷題】關于(a,b)-樹的插入，插入涉及到的結點最多到樹高+1。()

我的答案：，

【單選題】

KD樹在()層使用水平線。

A、偶數層

B、奇數層

C、最底層

Ds最圖層

我的答案：A

2【單選題】KdB-樹的插入可以使用()的方法。

A、近似

B、置換

C、對數

D、重構

我的答案：C

3【單選題】構建KDB-樹時，完成網格建立之后，計算每個網格中點的個數，并且存儲在()中。

A、外存

B、數據庫

C、寄存器

D、內存

我的答案：D

4【判斷題】基于位置的查找實際上是一種三維空間的查找。()

我的答案：x

5【判斷題】KD樹可以看成是兩個二叉樹的交疊。()

我的答案：J

1【單選題】

為數T的每個結點標上子樹大小的1/0復雜度為()。

A、10(sort(N))

B、0(sort(N))

C、IO(scan(N))

D、0(scan(N))

我的答案：B

2【單選題】前序計數的I/O復雜度為()。

As10(sort(N))

B、0(sort(N))

CsIO(scan(N))

DsO(scan(N))

我的答案：B

3【單選題】對給定頂點鄰接鏈表［其一個歐拉回路可以以()10復雜性求得。

A、0(sort(N))

B、O(scan(N))

C、O(scan(N))IO

DsIO(scan(N))

我的答案：C

4【判斷題】外存算法最壞情況的I/O數位Q(N)。()

我的答案：x

5【判斷題】圖中的獨立集是指圖當中點的集合，其任意兩點之間不存在邊。()

我的答案：/

1【單選題】

查找規(guī)模為N的表L中，每個獨立集(MIS)的大小至少為()。

Asn+1

B、2n

C、n/2

D、n/3

我的答案：D

2【單選題】時間前向的處理方法是按照()來訪問邊。

A、歐拉回路

B、表排序

C、拓撲序

D、結點序

我的答案：C

3【判斷題】求最大獨立集的基本思想是使用貪心法。()

我的答案：J

1【單選題】圖算法包含三種計數，其中將圖問題表示為有向無環(huán)圖的估值問題的是()。

A、自舉

B、縮圖法

C、時間前向處理

D、連通分量

我的答案：C

2【單選題】半外存算法是假設()。

A、邊放在內存中，頂點在外面

B、頂點放在內存中，邊在外面

C、頂點和邊都放在內存當中

D、頂點和邊都不在內存當中

我的答案：B

3【判斷題】圖的連通性算法可擴增為求圖G最小生成樹(MST)的算法。()

我的答案：J

4【判斷題】在求最小生成樹時，壓縮后圖中某條邊的權值等于該邊代表的所有邊的權值最大值。()

我的答案：x

1【單選題】MapReduce是由()開發(fā)的分布式編程模型。

A、Microsoft

B、Google

C、Tencent

D、AlibabaGroup

我的答案：B

2【單選題】在實現MapReduce程序時，需要注意的事項不包括()。

A、避免創(chuàng)建對象

B、避免緩沖

C、避免通信

D、避免Mappei■和Reduce函的全局變量傳遞

我的答案：C

3【多選題】MapReduce的執(zhí)行框架處理的內容包括()。

A、調度

B、數據分布

C、將中間數據進行聚集、排序或洗牌

D、進行錯誤處理

我的答案：ABCD

4【多選題】理想的可擴展性有()。

A、數據加倍,運行時間減半

B、數據加倍,運行時間加倍

C、資源加倍,運行時間減半

D、資源加倍,運行時間加倍

我的答案：BC

5【判斷題】Map()和Reduce。兩個函數不能夠并行運行。()

我的答案：x

1【單選題】

在版本1的字數統(tǒng)計中，在Map里使用了一個數組H,其作用是為每一個出現的單詞作()。

A、序列

B、基數

Cs集合

我的答案：B

1【判斷題】

大部分時候reducer■不能用作combiner。()

我的答案：，

2【判斷題】combiner的運行次數可能有多次。

我的答案：，

1【多選題】關于單詞共現矩陣的計算,說法正確的是()。

A、計算文本集合中詞的共現矩陣

B、詞的個數如果為N輸出為M*N的矩陣

C、是一種測量語義距離的方法

D、語義距離可用于許多語言處理任務

我的答案：ACD

2【多選題】用單詞共現矩陣解決大規(guī)模計數問題的基本方法是()。

A、Mapper生成部分計數

B、Reducer生成部分計數

C、Reducer聚合部分計數

D、Mapper聚合部分計數

我的答案：AC

3【多選題】“條紋法”的優(yōu)點有()。

A、易于實現

B、對key-value對的排序和洗牌少得多

C、潛在對象更大

D、能更好地利用combiner

我的答案：BD

4【判斷題】在“詞對法”中，每個mapper處理一個句子。()

我的答案：，

5【判斷題】“詞對法”的缺點是不易實現,排序和洗牌代價高。()

我的答案：x

6【判斷題】f(B|A)詞對法必須確定所有a被傳遞到同一個combiner。()

我的答案：x

1【單選題】

在repartitionjoin的改進中,說法錯誤的是()。

A、Map函數的輸出鍵作為連接鍵

B、Map函數的輸出鍵變化為連接鍵和表名的組合。

C、Partition函數中Hashcode僅從組合鍵的連接鍵計算

D、Grouping函數僅根據連接鍵分組紀錄

我的答案：A

2【多選題】用MR進行多重集相似連接算法的常見計算包括（）。

A、三角函數

B、單元函數

C、合取函數

D、析取函數

我的答案：BCD

3【判斷題】自然連接是從兩個關系的笛卡爾積中選取給定屬性間滿足一定條件的元組。（）

我的答案：x

4【判斷題】等值連接不必在結果中去掉重復的屬性。（）

我的答案：，

1【判斷題】

在迭代MapReduce中,reduce的輸出必須和map的輸入兼容。（）

我的答案：J

2【判斷題】“推薦好友”是圖算法在社交網絡中的一種實際用例。（）

我的答案：，

【單選題】

找到一個稠密圖的最小生成樹的算法易于并行化的原因是每個子圖的（）可以被并行計算。

A、邊

B、頂點

C、結點

D、最小生成樹

我的答案：D

2【單選題】基于路徑的算法的例子不包括（）。

A、單源最短路徑

B、最小生成樹

C、分布式不動點運算

D、拓撲排序

我的答案：C

3【多選題】在基于路徑的算法中，邊的標記包括（）。

A、代價

B、距離

C、相似性

D、屬性

我的答案：ABC

4【判斷題】Dijkstra算法需要并行化。（）

我的答案：x

【多選題】緩存迭代的方法是（）。

A、在Mapper前加入輸入緩存

B、在Mapper后加入輸出緩存

C、在Reducer■前加入輸入緩存

D、在Reducer后加入輸出緩存

我的答案：ACD

2【判斷題】MapReduce是一種非遞歸描述性語言的通用運行平臺。（）

我的答案：，

3【判斷題】Reducer輸入緩存的條件是使用靜態(tài)劃分方法，即意味著沒有新的結點。（）

我的答案：y

【單選題】

關于并行節(jié)點計算，下列選項中關于節(jié)點敘述不準確的是（）。

A、每一個節(jié)點接受上一個superstep發(fā)出的消息

B、執(zhí)行相同的用戶定義函數

C、所有節(jié)點根據用戶定義函數修改它的值

D、沒有額外工作要做時繼續(xù)迭代

我的答案：D

2【單選題】Pregel系統(tǒng)中Master的作用不包括()。

A、維護worker

B、恢復workers產生的錯誤

C、提供Web-UI監(jiān)督工作進程工具

D、與worker?交流

我的答案：D

3【多選題】并行結點計算的終止條件是()。

A、消息傳送到其他點后

B、所有頂點同時變?yōu)榉腔钴S狀態(tài)

C、迭代結束

D、沒有信息傳遞

我的答案：BD

4【多選題】用Pregel計算子圖同構問題,其三個步驟是()。

A、查詢分解

B、搜索

C、迭代

D、Join

我的答案：ABD

5【判斷題】Pregel的編程形式，在執(zhí)行計算的機器上每一階段都利用整個圖的全部狀態(tài)。()

我的答案：x

1【單選題】

眾包通過一系列的機制和方法來指導和協(xié)調()的