2025年數(shù)據(jù)與計(jì)算考試題及答案一、單項(xiàng)選擇題（每題2分，共20分）1.已知某算法的時間復(fù)雜度函數(shù)為T(n)=2n2+3nlog?n+5n+7，其漸進(jìn)時間復(fù)雜度為（）。A.O(n2)B.O(nlogn)C.O(n)D.O(n3)2.關(guān)系數(shù)據(jù)庫中，若一個關(guān)系模式R的所有非主屬性都完全函數(shù)依賴于任意一個候選碼，則R至少滿足（）。A.第一范式（1NF）B.第二范式（2NF）C.第三范式（3NF）D.BC范式（BCNF）3.在Hadoop生態(tài)中，負(fù)責(zé)資源管理和任務(wù)調(diào)度的核心組件是（）。A.HDFSB.MapReduceC.YARND.HBase4.對于長度為n的有序數(shù)組，使用二分查找的平均時間復(fù)雜度為（）。A.O(n)B.O(nlogn)C.O(logn)D.O(n2)5.分布式系統(tǒng)中，CAP理論指的是（）三者無法同時滿足。A.一致性、可用性、分區(qū)容錯性B.一致性、原子性、持久性C.可擴(kuò)展性、可用性、容錯性D.完整性、原子性、分區(qū)容錯性6.某哈希表采用鏈地址法處理沖突，哈希函數(shù)為H(key)=keymod7。若依次插入鍵值對(15,A)、(22,B)、(30,C)、(9,D)，則哈希表中索引為1的鏈表長度為（）。A.1B.2C.3D.47.以下不屬于NoSQL數(shù)據(jù)庫特點(diǎn)的是（）。A.支持ACID特性B.靈活的模式設(shè)計(jì)C.水平擴(kuò)展能力D.非關(guān)系型數(shù)據(jù)模型8.若某二叉樹的前序遍歷序列為ABDCE，中序遍歷序列為BADCE，則其后序遍歷序列為（）。A.BDECAB.BDAECC.BEDCAD.BDCEA9.在Spark中，RDD（彈性分布式數(shù)據(jù)集）的主要特性是（）。A.不可變、可分區(qū)、支持持久化B.可變、全局共享、實(shí)時計(jì)算C.內(nèi)存存儲、不可分區(qū)、單節(jié)點(diǎn)處理D.實(shí)時更新、高一致性、低延遲10.對于事務(wù)的隔離級別，“讀未提交”會導(dǎo)致的主要問題是（）。A.臟讀B.不可重復(fù)讀C.幻讀D.丟失更新二、填空題（每空2分，共20分）1.數(shù)據(jù)結(jié)構(gòu)中，棧的基本操作包括入棧、出棧和__________。2.關(guān)系代數(shù)中，投影操作的符號是__________（用希臘字母表示）。3.HBase的表由行鍵、列族、時間戳和__________組成。4.快速排序的平均時間復(fù)雜度為__________，最壞時間復(fù)雜度為__________。5.分布式系統(tǒng)中，Paxos算法用于解決__________問題。6.機(jī)器學(xué)習(xí)中，監(jiān)督學(xué)習(xí)與無監(jiān)督學(xué)習(xí)的主要區(qū)別在于是否有__________。7.數(shù)據(jù)庫索引分為聚簇索引和__________索引，其中__________索引會改變數(shù)據(jù)的物理存儲順序。8.在MapReduce編程模型中，Map階段輸出的鍵值對會經(jīng)過__________過程，按鍵分組后傳遞給Reduce階段。三、簡答題（每題8分，共40分）1.簡述B樹與B+樹的主要區(qū)別，并說明B+樹在數(shù)據(jù)庫索引中的優(yōu)勢。2.什么是數(shù)據(jù)庫的事務(wù)？簡述事務(wù)的ACID特性及其含義。3.對比HDFS（Hadoop分布式文件系統(tǒng)）與傳統(tǒng)文件系統(tǒng)的差異，說明HDFS適合處理的場景。4.解釋機(jī)器學(xué)習(xí)中的過擬合現(xiàn)象，并列舉至少3種緩解過擬合的方法。5.簡述分布式計(jì)算中“數(shù)據(jù)局部性”原則的含義，以及SparkRDD如何利用該原則優(yōu)化計(jì)算效率。四、計(jì)算題（每題10分，共30分）1.對數(shù)組[5,3,8,1,6,2,7,4]進(jìn)行快速排序（選擇首元素為樞軸），寫出每一趟排序后的數(shù)組狀態(tài)，并計(jì)算總的比較次數(shù)（僅統(tǒng)計(jì)元素間的直接比較）。2.某關(guān)系數(shù)據(jù)庫中有如下關(guān)系模式：學(xué)生（學(xué)號Sno，姓名Sname，年齡Sage，所在系Sdept）課程（課程號Cno，課程名Cname，學(xué)分Credit）選課（Sno，Cno，成績Grade）用關(guān)系代數(shù)表達(dá)式表示以下查詢：（1）查詢選修了課程號為“C01”且成績高于85分的學(xué)生的學(xué)號和姓名；（2）查詢所有年齡小于20歲且所在系為“計(jì)算機(jī)系”的學(xué)生的姓名和所選課程的課程名。3.假設(shè)某分布式系統(tǒng)中有5個節(jié)點(diǎn)，采用Paxos算法達(dá)成共識。當(dāng)前提案編號為n=10，值為v=X。節(jié)點(diǎn)A（提議者）向節(jié)點(diǎn)B、C、D、E（接受者）發(fā)送Prepare請求，其中節(jié)點(diǎn)B、C、D響應(yīng)了Promise（n=10，最大已接受編號為9，值為Y），節(jié)點(diǎn)E未響應(yīng)。此時節(jié)點(diǎn)A需要如何處理？若后續(xù)節(jié)點(diǎn)B、C、D接受了編號為10、值為X的提案，節(jié)點(diǎn)E在恢復(fù)后應(yīng)如何同步狀態(tài)？五、綜合題（20分）某電商平臺需構(gòu)建用戶行為分析系統(tǒng)，要求實(shí)時采集用戶瀏覽、點(diǎn)擊、加購、下單等行為數(shù)據(jù)（日均數(shù)據(jù)量約500TB），支持秒級查詢“最近1小時各商品分類的點(diǎn)擊量”和離線分析“用戶購買路徑轉(zhuǎn)化漏斗”。請?jiān)O(shè)計(jì)系統(tǒng)架構(gòu)，說明關(guān)鍵組件及各組件的作用，并分析需要考慮的性能優(yōu)化點(diǎn)。答案一、單項(xiàng)選擇題1.A2.B3.C4.C5.A6.B7.A8.A9.A10.A二、填空題1.取棧頂元素（或查看棧頂）2.π3.單元格值（或值）4.O(nlogn)、O(n2)5.分布式一致性6.標(biāo)簽（或目標(biāo)變量）7.非聚簇（或輔助）、聚簇8.洗牌（Shuffle）三、簡答題1.主要區(qū)別：B樹的每個節(jié)點(diǎn)存儲鍵和值，所有節(jié)點(diǎn)均可能存儲數(shù)據(jù)；B+樹的內(nèi)部節(jié)點(diǎn)僅存儲鍵，數(shù)據(jù)僅存儲在葉子節(jié)點(diǎn)，且葉子節(jié)點(diǎn)通過指針連接成有序鏈表。優(yōu)勢：B+樹的葉子節(jié)點(diǎn)包含所有數(shù)據(jù)并有序，適合范圍查詢（可通過鏈表順序掃描）；內(nèi)部節(jié)點(diǎn)無數(shù)據(jù)存儲，可容納更多鍵，減少I/O次數(shù)；更適合數(shù)據(jù)庫索引的頻繁查詢場景。2.事務(wù)是數(shù)據(jù)庫中不可分割的最小操作單元。ACID特性：原子性（Atomicity），事務(wù)內(nèi)操作要么全做要么全不做；一致性（Consistency），事務(wù)執(zhí)行前后數(shù)據(jù)庫狀態(tài)保持一致；隔離性（Isolation），事務(wù)間執(zhí)行互不干擾；持久性（Durability），事務(wù)提交后修改永久保存。3.差異：HDFS是分布式文件系統(tǒng)，支持海量數(shù)據(jù)存儲，采用主從架構(gòu)（NameNode+DataNode），文件分塊存儲（默認(rèn)128MB），適合一次寫入多次讀?。粋鹘y(tǒng)文件系統(tǒng)（如NTFS、EXT4）是單機(jī)或局域網(wǎng)文件系統(tǒng)，存儲容量較小，支持頻繁修改。適合場景：海量數(shù)據(jù)的批量處理（如日志分析、大數(shù)據(jù)計(jì)算），不適合小文件或頻繁隨機(jī)讀寫。4.過擬合指模型在訓(xùn)練數(shù)據(jù)上表現(xiàn)良好，但在新數(shù)據(jù)上泛化能力差。緩解方法：增加訓(xùn)練數(shù)據(jù)量；正則化（L1/L2正則）；早停（EarlyStopping）；特征選擇（減少冗余特征）；使用更簡單的模型（降低模型復(fù)雜度）。5.數(shù)據(jù)局部性原則指計(jì)算應(yīng)盡可能靠近數(shù)據(jù)存儲位置，以減少數(shù)據(jù)傳輸開銷。SparkRDD通過分區(qū)（Partition）將數(shù)據(jù)分布在集群各節(jié)點(diǎn)，計(jì)算任務(wù)（Task）被發(fā)送到數(shù)據(jù)所在節(jié)點(diǎn)執(zhí)行（本地化調(diào)度）；RDD的持久化（Cache/Persist）可將常用數(shù)據(jù)緩存到內(nèi)存或磁盤，避免重復(fù)計(jì)算；血緣（Lineage）機(jī)制記錄數(shù)據(jù)提供路徑，故障時僅需重算相關(guān)分區(qū)，減少數(shù)據(jù)傳輸。四、計(jì)算題1.快速排序過程（首元素5為樞軸）：第一趟：分區(qū)后數(shù)組為[3,1,2,4,5,6,7,8]，比較次數(shù)：7次（5與3、8、1、6、2、7、4比較）。第二趟：左子數(shù)組[3,1,2,4]（樞軸3），分區(qū)后[1,2,3,4]，比較次數(shù)：3次（3與1、2、4比較）；右子數(shù)組[6,7,8]（樞軸6），分區(qū)后[6,7,8]，比較次數(shù)：2次（6與7、8比較）。第三趟：左子數(shù)組[1,2]（樞軸1），分區(qū)后[1,2]，比較次數(shù)：1次（1與2比較）；右子數(shù)組無?？偙容^次數(shù)：7+3+2+1=13次。2.（1）πSno,Sname(σCno='C01'∧Grade>85(選課?學(xué)生))（2）πSname,Cname(σSage<20∧Sdept='計(jì)算機(jī)系'(學(xué)生?選課?課程))3.節(jié)點(diǎn)A收到B、C、D的Promise響應(yīng)（最大已接受編號9<10），因此可以提出編號10的提案，值為X（若響應(yīng)中存在已接受的值，需選擇最大編號對應(yīng)的值，此處無沖突，故保持X）。節(jié)點(diǎn)A向B、C、D發(fā)送Accept請求，若多數(shù)（≥3）接受，則提案通過。節(jié)點(diǎn)E恢復(fù)后，需通過Learn階段獲取已達(dá)成共識的提案（n=10，v=X），更新自身狀態(tài)。五、綜合題系統(tǒng)架構(gòu)設(shè)計(jì)：1.數(shù)據(jù)采集層：使用Flume或KafkaConnect實(shí)時采集用戶行為數(shù)據(jù)，通過Kafka消息隊(duì)列緩沖（解決生產(chǎn)與消費(fèi)速率不匹配問題，支持高吞吐量）。2.實(shí)時處理層：采用SparkStreaming或Flink處理實(shí)時數(shù)據(jù)，按商品分類聚合最近1小時點(diǎn)擊量，結(jié)果寫入Redis（內(nèi)存數(shù)據(jù)庫，支持秒級查詢）。3.離線存儲層：Kafka數(shù)據(jù)同步至HDFS（長期存儲）和HBase（列式存儲，支持快速隨機(jī)訪問）；使用Hive構(gòu)建數(shù)據(jù)倉庫，存儲清洗后的結(jié)構(gòu)化數(shù)據(jù)。4.離線分析層：通過Spark或MapReduce處理Hive數(shù)據(jù)，計(jì)算用戶購買路徑轉(zhuǎn)化漏斗，結(jié)果存儲至MySQL或ClickHouse（支持復(fù)雜查詢）。5.查詢服務(wù)層：提供API接口，實(shí)時查詢調(diào)用Redis數(shù)據(jù)，離線分析結(jié)果通過可視化工具（如T