超星爾雅學習通大數據算法(哈爾濱工業大學)網課章節測試答案1.1大數據的定義與特點D、基于高度分析的新價值4、【多選題】大數據的應用包括)。6、【判斷題】大數據種類繁多，在編碼方式、數據格式、應用特征等方面都存在差異。)1.2大數據算法(1)1、【單選題】大數據求解計算問題過程的第三步一般是)。A、判斷可計算否B、判斷能行可計算否C、算法設計與分析D、用計算機語言實現算法2、【多選題】在大數據求解計算問題中，判斷是否為能行可計算的因素包括)。3、【判斷題】大數據求解計算問題過程的第一步是確定該問題是否4、【判斷題】大數據計算模型與一般小規模計算模型一樣，都使用的1.3大數據算法(2)D、外存A、云計算3、【判斷題】大數據算法是在給定的時間約束下，以大數據為輸入，在給定資源約束內可以生成滿足給定約束結果的算法。4、【判斷題】MapReduce是一種比較好實現大數據算法的編程架構，在生產中得到廣泛應用。5、【判斷題】大數據算法是僅在電子計算機上運行的算法。1.4大數據的特點與大數據算法1、【單選題】眾包算法是用來解決)。A、訪問全部數據時間過長B、數據難于放入內存計算C、單個計算機難以保存全部數據，計算需要整體數據2、【單選題】大數據算法存在很多難題，對于訪問全部數據時間過長的問題，采用的解決方案是)。A、將數據存儲到磁盤上B、僅基于少量數據進行計算C、讀取部分數據A、數據量大B、基于高度分析的新價值D、多樣性、復雜性4、【判斷題】為解決單個計算機難以保存全部數據的問題，通常會采1.5大數據算法設計與分析1、【單選題】大數據算法涉及到外存的時候，通常要分析)。A、時間空間復雜性B、IO復雜性C、結果質量2、【多選題】下列選項中，屬于智能仿生算法的是)。C、模擬退火算法3、【判斷題】在線算法/數據流算法是面向大數據速度快的特點提出4、【判斷題】對于數據流算法或在線算法，經常要分析結果的近似5、【判斷題】隨機算法是利用隨機化的方法來進行大數據處理，是大數據算法設計技術之一。)2.1亞線性算法的定義1、【單選題】計算在一個給定社交網絡中平均每人的朋友個數，在不訪問所有頂點的情況下，進行精確計算最少需要訪問)個頂點。2、【多選題】亞線性是指)等的消耗是輸入規模o。)3、【判斷題】性質檢測算法屬于亞線性空間算法的一類。()2.2水庫抽樣——空間亞線性算法1、【判斷題】在經典的水庫抽樣中，要求空間復雜性為0(k),是指與2.3平面圖直徑——時間亞線性計算算法1、【單選題】以下()不是衡量分析近似解代價與優化解代價差距的C、絕對誤差D、(1-)-近似2、【單選題】利用平面圖的直徑近似算法得到的解，在最壞情況下，也不會小于最優解的()。A、二分之一B、三分之一D、十分之一3、【單選題】采用平面圖的直徑近似算法的動機是無法在要求的時A、相似解B、完整解C、精確解D、近似解4、【判斷題】在平面圖的直徑近似算法中，要求點之間的距離滿足三角不等式是指在i、j、k三個點中，i到j的距離加上j到k的距離5、【判斷題】近似算法能給出一個優化問題的優化解。2.4全0數組判定——時間亞線性判定算法1、【多選題】在判定問題的近似中，對于近似解需要區分的是)。C、差不離2、【判斷題】全0數組判定的近似算法的證據引理是：如果一次測試以大于等于p的概率獲得一個證據，那么s=2/p輪測試得到證據的概率大于等于1/2。3、【判斷題】判定問題的近似解是指：輸入滿足某種性質或近似滿足3.1數據流中頻繁元素1、【判斷題】Zipf原則是指典型的頻率分布是高度偏斜的，存在很多頻繁元素。)2、【判斷題】在數據流模型中，從數據流中可以計算簡單的函數，如最大值、最小值、求和等，且處理這些函數時通常使用單個寄存器3.2頻繁元素計算算法1、【單選題】頻繁元素計算算法又稱為)算法。A、MM2、【單選題】頻繁元素計算算法有效的原因是源于)。C、錯誤界限和k成反比3、【判斷題】在頻繁元素計算算法中，計數器x減少的次數依賴于有幾個減少計數器的步驟。()4、【判斷題】在頻繁元素計算算法中，當數據流中元素的總個數遠大于估計值與真實值相差的最多值時，可以得到頻繁項一個好的估計。3.3最小生成樹B、精確值C、權重3.4序列有序的判定個數組是否有序。遠離意味著必須刪除大于(0個元素才能保證剩下2、【判斷題】如果一次測試以大于等于p的概率獲得一個證據，那么s=2/p輪測試得到證據的概率大于等于3/4。3、【判斷題】關于證明如果輸入遠離有序，則存在大于n個“壞索4.1外存存儲結構與外存算法1、【單選題】下列選項中敘述正確的是)。A、磁盤的訪問可以隨機讀、隨機取B、磁盤系統傳輸大規模連續的數據塊的范圍是18-32kC、磁盤訪問比主存訪問的速度快2、【判斷題】對于大數據而言，標準計算理論模型失效的原因之一是內存是有限的，無法存儲所有的內存。)3、【判斷題】當內存不夠或者算法設計不好時，如果數據量達到一定4、【判斷題】現代計算機有復雜的存儲層次，存儲單元的訪問是以塊為單位的數據移動。()4.2.1外存算法示例：外存排序算法(1)2、【判斷題】排序分為內部排序和外部排序，外部排序是因排序的數據很大，一次不能容納全部的排序內容，在排序過程中需要訪問外存。()4.2.2外存算法示例：外存排序算法(2)4.3外存數據結構示例：外存查找樹1、【單選題】在內存中的二分搜索樹中，通常使用()來維護樹的平衡。()元素保存在根處。()3、【判斷題】為更快地保存外部搜索樹，可采取按BFS的順序將其分割。()1、【單選題】如果T是一個(a,b)-樹(a≥2且b≥2a-1),其根結點的度在()之間。2、【判斷題】在(a,b)-樹中，a和b表示的是每個節點當中鍵值的上限和下限。()3、【判斷題】B-樹中右邊的指針指向的是鍵值小于最右鍵值的子3、【判斷題】關于(a,b)-樹的插入，插入涉及到的結點最多到樹高5.3KD樹A、外存6.1表排序及其應用2、【單選題】前序計數的I/0復雜度為)。3、【單選題】對給定頂點鄰接鏈表T,其一個歐拉回路可以以OI0復4、【判斷題】外存算法最壞情況的I/0數位Ω(N)。()5、【判斷題】圖中的獨立集是指圖當中點的集合，其任意兩點之間不存在邊。01、【單選題】查找規模為N的表L中，每個獨立集(MIS)的大小至少2、【單選題】時間前向的處理方法是按照)來訪問邊。A、歐拉回路3、【判斷題】求最大獨立集的基本思想是使用貪心法。()6.3縮圖法1、【單選題】圖算法包含三種計數，其中將圖問題表示為有向無環圖第19頁共30頁1、【單選題】在版本1的字數統計中，在Map里使用了一個數組H,其作用是為每一個出現的單詞作()。C、集合7.3平均數計算7.4單詞共現矩陣的計算A、計算文本集合中詞的共現矩陣B、詞的個數如果為N,輸出為M*N的矩陣C、是一種測量語義距離的方法D、語義距離可用于許多語言處理任務、【多選題】用單詞共現矩陣解決大規模計數問題的基本方法是B、Reducer生成部分計數D、Mapper聚合部分計數B、對key-value對的排序和洗牌少得多C、潛在對象更大8.1連接(join)算法A、Map函數的輸出鍵作為連接鍵B、Map函數的輸出鍵變化為連接鍵和表名的組合。D、Grouping函數僅根據連接鍵分組紀錄2、【多選題】用MR進行多重集相似連接算法的常見計算包括0。3、【判斷題】自然連接是從兩個關系的笛卡爾積中選取給定屬性間滿足一定條件的元組。()4、【判斷題】等值連接不必在結果中去掉重復的屬性。()1、【判斷題】在迭代MapReduce中，reduce的輸出必須和map的輸入兼容。02、【判斷題】“推薦好友”是圖算法在社交網絡中的一種實際用例。8.3基于路徑的算法1、【單選題】找到一個稠密圖的最小生成樹的算法易于并行化的原因是每個子圖的()可以被并行計算。D、最小生成樹2、【單選題】基于路徑的算法的例子不包括()。C、分布式不動點運算9.1基于迭代處理平臺的并行算法A、在Mapper前加入輸入緩存B、在Mapper后加入輸出緩存2、【判斷題】MapReduce是一種非遞歸描述性語言的通用運行平3、【判斷題】Reducer輸入緩存的條件是使用靜態劃分方法，即意味著沒有新的結點。()9.2基于圖處理平臺的并行算法1、【單選題】關于并行節點計算，下列選項中關于節點敘述不準確的A、每一個節點接受上一個superstep發出的消息B、執行相同的用戶定義函數C、所有節點根據用戶定義函數修改它的值D、沒有額外工作要做時繼續迭代B、恢復workers產生的錯誤C、提供Web-UI監督工作進程工具3、【多選題】并行結點計算的終止條件是0。A、消息傳送到其他點后B、所有頂點同時變為非活躍狀態C、迭代結束4、【多選題】用Pregel計算子圖同構問題，其三個步驟是)。A、查詢分解5、【判斷題】Pregel的編程形式，在執行計算的機器上每一階段都利用整個圖的全部狀態。010.1眾包的定義1、【單選題】眾包通過一系列的機制和方法來指導和協調()的行為，2、【判斷題】外包與眾包的區別在于眾包的參與者數量大且不固定第27頁共30頁4、【判斷題】眾包極大程度地使用了人本計算，因此它基本上等同于人本計算。)10.2眾包的實例2、【多選題】下列屬于眾包應用的例子有)。3、【判斷題】眾包技術應用于廣告中的情形之一是區分關鍵詞與廣告的相關程度。()4、【判斷題】目前眾包技術已經可以判斷兩幅畫在藝術風格上是否第28頁共30頁一致。)10.3眾包的要素1、【單選題】眾包中質量控制/數據質量要考慮的問題不包括)。B、垃圾結果檢測D、界面和交互設計2、【多選題】眾包中的參與者包括)。A、請求者3、【多選題】在人機交互中從用戶獲取輸入的方式有)。A、調查C、可用性測試4、【判斷題】眾包中工人的回報