超星爾雅學(xué)習(xí)通《大數(shù)據(jù)算法（哈爾濱工業(yè)大學(xué)）》2024章節(jié)測試答案

超星爾雅學(xué)習(xí)通《大數(shù)據(jù)算法（哈爾濱工業(yè)大學(xué)）》2024章節(jié)測試答案1.1大數(shù)據(jù)的定義與特點1、以下關(guān)于大數(shù)據(jù)的特點，敘述錯誤的是（）。A、速度慢B、多元、異構(gòu)C、數(shù)據(jù)規(guī)模大D、基于高度分析的新價值正確答案：A2、在《法華經(jīng)》中，“那由他”描寫的“大”的數(shù)量級是（）。A、10^7B、10^14C、10^28D、10^56正確答案：C3、以下選項中，大數(shù)據(jù)涉及的領(lǐng)域中包括（）。A、社交網(wǎng)絡(luò)B、醫(yī)療數(shù)據(jù)C、計算機藝術(shù)D、醫(yī)療數(shù)據(jù)正確答案：ABC（D）4、大數(shù)據(jù)的應(yīng)用包括（）。A、預(yù)測B、推薦C、商業(yè)情報分析D、科學(xué)研究正確答案：ABCD5、目前，關(guān)于大數(shù)據(jù)已有公認(rèn)的確定定義。A、正確B、錯誤正確答案：B6、大數(shù)據(jù)種類繁多，在編碼方式、數(shù)據(jù)格式、應(yīng)用特征等方面都存在差異。（）A、正確B、錯誤正確答案：A1.2大數(shù)據(jù)算法（1）1、大數(shù)據(jù)求解計算問題過程的第三步一般是（）。A、判斷可計算否B、判斷能行可計算否C、算法設(shè)計與分析D、用計算機語言實現(xiàn)算法正確答案：C2、在大數(shù)據(jù)求解計算問題中，判斷是否為能行可計算的因素包括（）。A、數(shù)據(jù)量B、資源約束C、速度約束D、時間約束正確答案：ABD3、大數(shù)據(jù)求解計算問題過程的第一步是確定該問題是否可計算。A、正確B、錯誤正確答案：A4、大數(shù)據(jù)計算模型與一般小規(guī)模計算模型一樣，都使用的是圖靈機模型。A、正確B、錯誤正確答案：A1.3大數(shù)據(jù)算法（2）1、資源約束包括（）。A、CPUB、網(wǎng)絡(luò)帶寬C、內(nèi)存D、外存正確答案：ABCD2、大數(shù)據(jù)算法可以不是（）。A、云計算B、精確算法C、內(nèi)存算法D、串行算法正確答案：BCD3、大數(shù)據(jù)算法是在給定的時間約束下，以大數(shù)據(jù)為輸入，在給定資源約束內(nèi)可以生成滿足給定約束結(jié)果的算法。A、正確B、錯誤正確答案：B4、MapReduce是一種比較好實現(xiàn)大數(shù)據(jù)算法的編程架構(gòu)，在生產(chǎn)中得到廣泛應(yīng)用。A、正確B、錯誤正確答案：A5、大數(shù)據(jù)算法是僅在電子計算機上運行的算法。A、正確B、錯誤正確答案：B1.4大數(shù)據(jù)的特點與大數(shù)據(jù)算法1、眾包算法是用來解決（）。A、訪問全部數(shù)據(jù)時間過長B、數(shù)據(jù)難于放入內(nèi)存計算C、單個計算機難以保存全部數(shù)據(jù)，計算需要整體數(shù)據(jù)D、計算機計算能力不足或知識不足，需要人來幫忙正確答案：D2、大數(shù)據(jù)算法存在很多難題，對于訪問全部數(shù)據(jù)時間過長的問題，采用的解決方案是（）。A、將數(shù)據(jù)存儲到磁盤上B、僅基于少量數(shù)據(jù)進(jìn)行計算C、讀取部分?jǐn)?shù)據(jù)D、并行處理正確答案：C3、大數(shù)據(jù)算法的（）特點，使其與大數(shù)據(jù)算法密切相關(guān)的。A、數(shù)據(jù)量大B、基于高度分析的新價值C、速度快D、多樣性、復(fù)雜性正確答案：AC4、為解決單個計算機難以保存全部數(shù)據(jù)的問題，通常會采用并行處理的技術(shù)，此技術(shù)會涉及到時間亞線性算法。A、正確B、錯誤正確答案：B1.5大數(shù)據(jù)算法設(shè)計與分析1、大數(shù)據(jù)算法涉及到外存的時候，通常要分析（）。A、時間空間復(fù)雜性B、IO復(fù)雜性C、結(jié)果質(zhì)量D、通訊復(fù)雜性正確答案：B2、下列選項中，屬于智能仿生算法的是（）。A、遺傳算法B、近似算法C、模擬退火算法D、數(shù)據(jù)流算法正確答案：AC3、在線算法/數(shù)據(jù)流算法是面向大數(shù)據(jù)速度快的特點提出的。（）A、正確B、錯誤正確答案：A4、對于數(shù)據(jù)流算法或在線算法，經(jīng)常要分析結(jié)果的近似比。（）A、正確B、錯誤正確答案：B5、隨機算法是利用隨機化的方法來進(jìn)行大數(shù)據(jù)處理，是大數(shù)據(jù)算法設(shè)計技術(shù)之一。（）A、正確B、錯誤正確答案：A2.1亞線性算法的定義1、計算在一個給定社交網(wǎng)絡(luò)中平均每人的朋友個數(shù)，在不訪問所有頂點的情況下，進(jìn)行精確計算最少需要訪問（）個頂點。A、n2B、n+1C、2nD、n-1正確答案：D2、亞線性是指（）等的消耗是輸入規(guī)模o。（）A、時間B、空間C、IOD、通訊正確答案：ABCD3、性質(zhì)檢測算法屬于亞線性空間算法的一類。（）A、正確B、錯誤正確答案：B2.2水庫抽樣——空間亞線性算法1、在經(jīng)典的水庫抽樣中，要求空間復(fù)雜性為O（k），是指與抽樣大小有關(guān)，而與整個數(shù)據(jù)的數(shù)據(jù)量無關(guān)。A、正確B、錯誤正確答案：A2、水庫抽樣算法的采樣是均勻的。A、正確B、錯誤正確答案：A2.3平面圖直徑——時間亞線性計算算法1、以下（）不是衡量分析近似解代價與優(yōu)化解代價差距的方法。A、RatioBoundB、相對誤差C、絕對誤差D、（1-?）-近似正確答案：C2、利用平面圖的直徑近似算法得到的解，在最壞情況下，也不會小于最優(yōu)解的（）。A、二分之一B、三分之一C、四分之一D、十分之一正確答案：A3、采用平面圖的直徑近似算法的動機是無法在要求的時間內(nèi)得到（）。A、相似解B、完整解C、精確解D、近似解正確答案：C4、在平面圖的直徑近似算法中，要求點之間的距離滿足三角不等式是指在i、j、k三個點中，i到j(luò)的距離加上j到k的距離小于i到k的距離。A、正確B、錯誤正確答案：B5、近似算法能給出一個優(yōu)化問題的優(yōu)化解。A、正確B、錯誤正確答案：B6、RatioBound越大，則近似解越壞。（）A、正確B、錯誤正確答案：A2.4全0數(shù)組判定——時間亞線性判定算法1、在判定問題的近似中，對于近似解需要區(qū)分的是（）。A、是B、否C、差不離D、差得很遠(yuǎn)正確答案：AD2、全0數(shù)組判定的近似算法的證據(jù)引理是：如果一次測試以大于等于p的概率獲得一個證據(jù)，那么s=2/p輪測試得到證據(jù)的概率大于等于1/2。A、正確B、錯誤正確答案：B3、判定問題的近似解是指：輸入滿足某種性質(zhì)或近似滿足某種性質(zhì)。A、正確B、錯誤正確答案：B3.1數(shù)據(jù)流中頻繁元素1、Zipf原則是指典型的頻率分布是高度偏斜的，存在很多頻繁元素。（）A、正確B、錯誤正確答案：B2、在數(shù)據(jù)流模型中，從數(shù)據(jù)流中可以計算簡單的函數(shù)，如最大值、最小值、求和等，且處理這些函數(shù)時通常使用單個寄存器s。（）A、正確B、錯誤正確答案：A3、數(shù)據(jù)流模型中，數(shù)據(jù)流是指來自某個域中的元素序列。（）A、正確B、錯誤正確答案：A4、在數(shù)據(jù)流模型中，內(nèi)存遠(yuǎn)遠(yuǎn)大于數(shù)據(jù)的規(guī)模。（）A、正確B、錯誤正確答案：B3.2頻繁元素計算算法1、頻繁元素計算算法又稱為（）算法。A、MMB、MGC、GMD、MP正確答案：B2、頻繁元素計算算法有效的原因是源于（）。A、取近似解B、證據(jù)引理C、錯誤界限和k成反比D、Zipf原則正確答案：D3、在頻繁元素計算算法中，計數(shù)器x減少的次數(shù)依賴于有幾個減少計數(shù)器的步驟。（）A、正確B、錯誤正確答案：A4、在頻繁元素計算算法中，當(dāng)數(shù)據(jù)流中元素的總個數(shù)遠(yuǎn)大于估計值與真實值相差的最多值時，可以得到頻繁項一個好的估計。A、正確B、錯誤正確答案：A3.3最小生成樹1、時間亞線性算法的思想是：利用特定子圖聯(lián)通分量的數(shù)量估計最小生成樹的（）。A、近似值B、精確值C、權(quán)重D、界限正確答案：C2、求最小生成樹是一個貪心法，可以用（）算法來解決。A、PrimeB、并行C、MGD、內(nèi)存正確答案：A3、對聯(lián)通分量個數(shù)的估計可以利用隨機化方法。A、正確B、錯誤正確答案：A3.4序列有序的判定1、對于輸入n個數(shù)的數(shù)組（x1，x2，x3，……，xn），輸出：這個數(shù)組是否有序。?遠(yuǎn)離意味著必須刪除大于（）個元素才能保證剩下的元素有序。A、?-nB、?nC、?/nD、n/?正確答案：B2、如果一次測試以大于等于p的概率獲得一個證據(jù)，那么s=2/p輪測試得到證據(jù)的概率大于等于3/4。A、正確B、錯誤正確答案：B3、關(guān)于證明如果輸入?遠(yuǎn)離有序，則存在大于?n個“壞索引”的問題，可以采用證明其逆否命題的方法。A、正確B、錯誤正確答案：A4.1外存存儲結(jié)構(gòu)與外存算法1、下列選項中敘述正確的是（）。A、磁盤的訪問可以隨機讀、隨機取B、磁盤系統(tǒng)傳輸大規(guī)模連續(xù)的數(shù)據(jù)塊的范圍是18-32kC、磁盤訪問比主存訪問的速度快D、大多數(shù)程序在RAM模型上運行正確答案：D2、對于大數(shù)據(jù)而言，標(biāo)準(zhǔn)計算理論模型失效的原因之一是內(nèi)存是有限的，無法存儲所有的內(nèi)存。（）A、正確B、錯誤正確答案：A3、當(dāng)內(nèi)存不夠或者算法設(shè)計不好時，如果數(shù)據(jù)量達(dá)到一定規(guī)模以上，運行時間會急劇增加。A、正確B、錯誤正確答案：A4、現(xiàn)代計算機有復(fù)雜的存儲層次，存儲單元的訪問是以塊為單位的數(shù)據(jù)移動。（）A、正確B、錯誤正確答案：A4.2.1外存算法示例：外存排序算法（1）1、外存歸并排序，以（）為單位進(jìn)行調(diào)度。A、比特B、兆C、塊D、層正確答案：C2、排序分為內(nèi)部排序和外部排序，外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序內(nèi)容，在排序過程中需要訪問外存。（）A、正確B、錯誤正確答案：A4.2.2外存算法示例：外存排序算法（2）1、在外排序的快速排序中，分割元素的選擇非常重要。A、正確B、錯誤正確答案：A4.3外存數(shù)據(jù)結(jié)構(gòu)示例：外存查找樹1、在內(nèi)存中的二分搜索樹中，通常使用（）來維護(hù)樹的平衡。（）A、置換B、分裂C、旋轉(zhuǎn)D、合并正確答案：C2、二叉搜索樹是在n個元素之間搜索的標(biāo)準(zhǔn)方法，一般把元素保存在根處。（）A、正確B、錯誤正確答案：B3、為更快地保存外部搜索樹，可采取按BFS的順序?qū)⑵浞指睢＃ǎ〢、正確B、錯誤正確答案：A5.1B樹（1）1、如果T是一個（a，b）-樹（a≧2且b≧2a-1），其根結(jié)點的度在（）之間。A、2到aB、2到bC、a到bD、2到4正確答案：B2、在（a，b）-樹中，a和b表示的是每個節(jié)點當(dāng)中鍵值的上限和下限。（）A、正確B、錯誤正確答案：B3、B-樹中右邊的指針指向的是鍵值小于最右鍵值的子數(shù)。（）A、正確B、錯誤正確答案：B5.2B樹（2）1、元素都在葉子中的B-樹有時被稱為（）。A、B+樹B、B-+樹C、B+-樹D、B+-數(shù)正確答案：C2、關(guān)于（a，b）—樹的刪除操作，刪除操作出現(xiàn)問題的情形是：從葉子v刪除元素后，v的兒子小于a-1個。（）A、正確B、錯誤正確答案：A3、關(guān)于（a，b）-樹的插入，插入涉及到的結(jié)點最多到樹高+1。（）A、正確B、錯誤正確答案：A5.3KD樹1、KD樹在（）層使用水平線。A、偶數(shù)層B、奇數(shù)層C、最底層D、最高層正確答案：A2、KdB-樹的插入可以使用（）的方法。A、近似B、置換C、對數(shù)D、重構(gòu)正確答案：C3、構(gòu)建KDB-樹時，完成網(wǎng)格建立之后，計算每個網(wǎng)格中點的個數(shù)，并且存儲在（）中。A、外存B、數(shù)據(jù)庫C、寄存器D、內(nèi)存正確答案：D4、基于位置的查找實際上是一種三維空間的查找。（）A、正確B、錯誤正確答案：B5、KD樹可以看成是兩個二叉樹的交疊。（）A、正確B、錯誤正確答案：A6.1表排序及其應(yīng)用1、為數(shù)T的每個結(jié)點標(biāo)上子樹大小的I/O復(fù)雜度為（）。A、IO（sort（N））B、O（sort（N））C、IO（scan（N））D、O（scan（N））正確答案：B2、前序計數(shù)的I/O復(fù)雜度為（）。A、IO（sort（N））B、O（sort（N））C、IO（scan（N））D、O（scan（N））正確答案：B3、對給定頂點鄰接鏈表T，其一個歐拉回路可以以（）IO復(fù)雜性求得。A、O（sort（N））B、O（scan（N））C、O（scan（N））IOD、IO（scan（N））正確答案：C4、外存算法最壞情況的I/O數(shù)位Ω（N）。（）A、正確B、錯誤正確答案：B5、圖中的獨立集是指圖當(dāng)中點的集合，其任意兩點之間不存在邊。（）A、正確B、錯誤正確答案：A6.2時間前向處理方法1、查找規(guī)模為N的表L中，每個獨立集（MIS）的大小至少為（）。A、n+1B、2nC、n/2D、n/3正確答案：D2、時間前向的處理方法是按照（）來訪問邊。A、歐拉回路B、表排序C、拓?fù)湫駾、結(jié)點序正確答案：C3、求最大獨立集的基本思想是使用貪心法。（）A、正確B、錯誤正確答案：A6.3縮圖法1、圖算法包含三種計數(shù)，其中將圖問題表示為有向無環(huán)圖的估值問題的是（）。A、自舉B、縮圖法C、時間前向處理D、連通分量正確答案：C2、半外存算法是假設(shè)（）。A、邊放在內(nèi)存中，頂點在外面B、頂點放在內(nèi)存中，邊在外面C、頂點和邊都放在內(nèi)存當(dāng)中D、頂點和邊都不在內(nèi)存當(dāng)中正確答案：B3、圖的連通性算法可擴增為求圖G最小生成樹（MST）的算法。（）A、正確B、錯誤正確答案：A4、在求最小生成樹時，壓縮后圖中某條邊的權(quán)值等于該邊代表的所有邊的權(quán)值最大值。（）A、正確B、錯誤正確答案：B7.1MapReduce概述1、MapReduce是由（）開發(fā)的分布式編程模型。A、MicrosoftB、GoogleC、TencentD、AlibabaGroup正確答案：B2、在實現(xiàn)MapReduce程序時，需要注意的事項不包括（）。A、避免創(chuàng)建對象B、避免緩沖C、避免通信D、避免Mapper和Reducer間的全局變量傳遞正確答案：C3、MapReduce的執(zhí)行框架處理的內(nèi)容包括（）。A、調(diào)度B、數(shù)據(jù)分布C、將中間數(shù)據(jù)進(jìn)行聚集、排序或洗牌D、進(jìn)行錯誤處理正確答案：ABCD4、理想的可擴展性有（）。A、數(shù)據(jù)加倍，運行時間減半B、數(shù)據(jù)加倍，運行時間加倍C、資源加倍，運行時間減半D、資源加倍，運行時間加倍正確答案：BC5、Map（）和Reduce（）兩個函數(shù)不能夠并行運行。（）A、正確B、錯誤正確答案：B7.2字?jǐn)?shù)統(tǒng)計1、在版本1的字?jǐn)?shù)統(tǒng)計中，在Map里使用了一個數(shù)組H，其作用是為每一個出現(xiàn)的單詞作（）。A、序列B、基數(shù)C、集合正確答案：B7.3平均數(shù)計算1、大部分時候reducer不能用作combiner。（）A、正確B、錯誤正確答案：A2、combiner的運行次數(shù)可能有多次。A、正確B、錯誤正確答案：A7.4單詞共現(xiàn)矩陣的計算1、關(guān)于單詞共現(xiàn)矩陣的計算，說法正確的是（）。A、計算文本集合中詞的共現(xiàn)矩陣B、詞的個數(shù)如果為N，輸出為M*N的矩陣C、是一種測量語義距離的方法D、語義距離可用于許多語言處理任務(wù)正確答案：ACD2、用單詞共現(xiàn)矩陣解決大規(guī)模計數(shù)問題的基本方法是（）。A、Mapper生成部分計數(shù)B、Reducer生成部分計數(shù)C、Reducer聚合部分計數(shù)D、Mapper聚合部分計數(shù)正確答案：AC3、“條紋法”的優(yōu)點有（）。A、易于實現(xiàn)B、對key-value對的排序和洗牌少得多C、潛在對象更大D、能更好地利用combiner正確答案：BD4、在“詞對法”中，每個mapper處理一個句子。（）A、正確B、錯誤正確答案：A5、“詞對法”的缺點是不易實現(xiàn)，排序和洗牌代價高。（）A、正確B、錯誤正確答案：B6、f（B|A）詞對法必須確定所有a被傳遞到同一個combiner。（）A、正確B、錯誤正確答案：B8.1連接（join）算法1、在repartitionjoin的改進(jìn)中，說法錯誤的是（）。A、Map函數(shù)的輸出鍵作為連接鍵B、Map函數(shù)的輸出鍵變化為連接鍵和表名的組合。C、Partition函數(shù)中Hashcode僅從組合鍵的連接鍵計算D、Grouping函數(shù)僅根據(jù)連接鍵分組紀(jì)錄正確答案：A2、用MR進(jìn)行多重集相似連接算法的常見計算包括（）。A、三角函數(shù)B、單元函數(shù)C、合取函數(shù)D、析取函數(shù)正確答案：BCD3、自然連接是從兩個關(guān)系的笛卡爾積中選取給定屬性間滿足一定條件的元組。（）A、正確B、錯誤正確答案：B4、等值連接不必在結(jié)果中去掉重復(fù)的屬性。（）A、正確B、錯誤正確答案：A8.2圖算法1、在迭代MapReduce中，reduce的輸出必須和map的輸入兼容。（）A、正確B、錯誤正確答案：A2、“推薦好友”是圖算法在社交網(wǎng)絡(luò)中的一種實際用例。（）A、正確B、錯誤正確答案：A8.3基于路徑的算法1、找到一個稠密圖的最小生成樹的算法易于并行化的原因是每個子圖的（）可以被并行計算。A、邊B、頂點C、結(jié)點D、最小生成樹正確答案：D2、基于路徑的算法的例子不包括（）。A、單源最短路徑B、最小生成樹C、分布式不動點運算D、拓?fù)渑判蛘_答案：C3、在基于路徑的算法中，邊的標(biāo)記包括（）。A、代價B、距離C、相似性D、屬性正確答案：ABC4、Dijkstra算法需要并行化。（）A、正確B、錯誤正確答案：B9.1基于迭代處理平臺的并行算法1、緩存迭代的方法是（）。A、在Mapper前加入輸入緩存B、在Mapper后加入輸出緩存C、在Reducer前加入輸入緩存D、在Reducer后加入輸出緩存正確答案：ACD2、MapReduce是一種非遞歸描述性語言的通用運行平臺。（）A、正確B、錯誤正確答案：A3、Reducer輸入緩存的條件是使用靜態(tài)劃分方法，即意味著沒有新的結(jié)點。（）A、正確B、錯誤正確答案：A9.2基于圖處理平臺的并行算法1、關(guān)于并行節(jié)點計算，下列選項中關(guān)于節(jié)點敘述不準(zhǔn)確的是（）。A、每一個節(jié)點接受上一個superstep發(fā)出的消息B、執(zhí)行相同的用戶定義函數(shù)C、所有節(jié)點根據(jù)用戶定義函數(shù)修改它的值D、沒有額外工作要做時繼續(xù)迭代正確答案：D2、Pregel系統(tǒng)中Master的作用不包括（）。A、維護(hù)workerB、恢復(fù)workers產(chǎn)生的錯誤C、提供Web-UI監(jiān)督工作進(jìn)程工具D、與worker交流正確答案：D3、并行結(jié)點計算的終止條件是（）。A、消息傳送到其他點后B、所有頂點同時變?yōu)榉腔钴S狀態(tài)C、迭代結(jié)束D、沒有信息傳遞正確答案：BD4、用Pregel計算子圖同構(gòu)問題，其三個步驟是（）。A、查詢分解B、搜索C、迭代D、Join正確答案：ABD5、Pregel的編程形式，在執(zhí)行計算的機器上每一階段都利用整個圖的全部狀態(tài)。（）A、正確B、錯誤正確答案：B10.1眾包的定義1、眾包通過一系列的機制和方法來指導(dǎo)和協(xié)調(diào)（）的行為，從而達(dá)到目的。A、個人B、計算機C、群體D、軟件正確答案：C2、外包與眾包的區(qū)別