清華大學(xué)保送生選拔計(jì)算機(jī)科學(xué)試卷考試時長：120分鐘滿分：100分班級：__________姓名：__________學(xué)號：__________得分：__________試卷名稱：清華大學(xué)保送生選拔計(jì)算機(jī)科學(xué)試卷考核對象：計(jì)算機(jī)科學(xué)專業(yè)保送生選拔考生題型分值分布：-判斷題（總共10題，每題2分）總分20分-單選題（總共10題，每題2分）總分20分-多選題（總共10題，每題2分）總分20分-案例分析（總共3題，每題6分）總分18分-論述題（總共2題，每題11分）總分22分總分：100分---一、判斷題（每題2分，共20分）1.在面向?qū)ο缶幊讨?，抽象類可以?shí)例化對象。2.快速排序的平均時間復(fù)雜度為O(n2)。3.SQL中的JOIN操作只能連接兩個表。4.在二叉樹中，滿二叉樹的葉子節(jié)點(diǎn)數(shù)總是比非葉子節(jié)點(diǎn)數(shù)多1。5.TCP協(xié)議是一種無連接的傳輸協(xié)議。6.哈希表的時間復(fù)雜度在最佳情況下可以達(dá)到O(1)。7.在分布式系統(tǒng)中，CAP定理要求系統(tǒng)同時滿足一致性、可用性和分區(qū)容錯性。8.遞歸函數(shù)調(diào)用會導(dǎo)致棧溢出。9.在深度優(yōu)先搜索中，訪問節(jié)點(diǎn)的順序與鄰接表的存儲順序有關(guān)。10.Python中的列表和元組都是可變的數(shù)據(jù)結(jié)構(gòu)。二、單選題（每題2分，共20分）1.下列哪種數(shù)據(jù)結(jié)構(gòu)適合實(shí)現(xiàn)LRU緩存？A.隊(duì)列B.哈希表C.堆D.鏈表2.在TCP三次握手過程中，服務(wù)器發(fā)送SYN-ACK后，客戶端需要發(fā)送什么？A.ACKB.FINC.RSTD.SYN3.下列哪種排序算法在最壞情況下時間復(fù)雜度為O(nlogn)？A.快速排序B.冒泡排序C.插入排序D.選擇排序4.在SQL中，`GROUPBY`子句通常與哪個函數(shù)一起使用？A.`WHERE`B.`HAVING`C.`SELECT`D.`ORDERBY`5.下列哪種算法適用于解決最短路徑問題？A.Dijkstra算法B.Floyd-Warshall算法C.冒泡排序D.快速排序6.在分布式數(shù)據(jù)庫中，分片（Sharding）的主要目的是什么？A.提高查詢速度B.增加數(shù)據(jù)冗余C.減少網(wǎng)絡(luò)延遲D.簡化數(shù)據(jù)管理7.下列哪種設(shè)計(jì)模式屬于創(chuàng)建型模式？A.觀察者模式B.工廠方法模式C.策略模式D.裝飾器模式8.在二叉搜索樹中，刪除一個節(jié)點(diǎn)后，樹的高度最多可能增加多少？A.1B.2C.3D.49.下列哪種網(wǎng)絡(luò)協(xié)議用于實(shí)時音視頻傳輸？A.FTPB.SIPC.SMTPD.HTTP10.在Python中，`lambda`函數(shù)可以用于實(shí)現(xiàn)什么？A.類定義B.函數(shù)裝飾器C.匿名函數(shù)D.異常處理三、多選題（每題2分，共20分）1.下列哪些是數(shù)據(jù)庫事務(wù)的特性？A.原子性B.一致性C.隔離性D.持久性2.在圖論中，下列哪些算法可以用于檢測環(huán)？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.Dijkstra算法D.Floyd-Warshall算法3.下列哪些數(shù)據(jù)結(jié)構(gòu)支持動態(tài)擴(kuò)容？A.數(shù)組B.鏈表C.堆D.哈希表4.在分布式系統(tǒng)中，下列哪些是常見的負(fù)載均衡策略？A.輪詢B.最少連接C.哈希一致性D.負(fù)載預(yù)測5.下列哪些是面向?qū)ο缶幊痰奶匦?？A.封裝B.繼承C.多態(tài)D.抽象6.在TCP協(xié)議中，下列哪些是狀態(tài)？A.SYN_SENTB.ESTABLISHEDC.FIN_WAITD.CLOSE_WAIT7.下列哪些排序算法是穩(wěn)定的？A.快速排序B.插入排序C.堆排序D.歸并排序8.在SQL中，下列哪些是聚合函數(shù)？A.COUNTB.SUMC.AVGD.MAX9.下列哪些是常見的網(wǎng)絡(luò)攻擊類型？A.DDoS攻擊B.SQL注入C.XSS攻擊D.中間人攻擊10.在Python中，下列哪些是可變數(shù)據(jù)類型？A.字符串B.列表C.元組D.字典四、案例分析（每題6分，共18分）案例1：假設(shè)你正在設(shè)計(jì)一個社交網(wǎng)絡(luò)的用戶關(guān)系系統(tǒng)，需要存儲用戶之間的好友關(guān)系。現(xiàn)有兩種數(shù)據(jù)結(jié)構(gòu)可供選擇：1.哈希表（鍵為用戶ID，值為好友列表）。2.二叉搜索樹（節(jié)點(diǎn)為用戶ID，左右子樹分別存儲比當(dāng)前節(jié)點(diǎn)小的和大的用戶ID）。請分析這兩種數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點(diǎn)，并說明在什么場景下更適合使用哪種數(shù)據(jù)結(jié)構(gòu)。案例2：給定一個包含n個整數(shù)的數(shù)組，要求在不使用額外空間的情況下，將數(shù)組中的元素按奇偶性重新排列，使得所有奇數(shù)位于偶數(shù)之前。例如，輸入[3,1,2,4]，輸出[3,1,4,2]。請?jiān)O(shè)計(jì)一個高效的算法，并說明其時間復(fù)雜度。案例3：假設(shè)你正在開發(fā)一個分布式數(shù)據(jù)庫系統(tǒng)，需要設(shè)計(jì)一個分片策略，將數(shù)據(jù)均勻分布在多個節(jié)點(diǎn)上。請說明至少兩種常見的分片策略，并分析每種策略的優(yōu)缺點(diǎn)。五、論述題（每題11分，共22分）論述1：請?jiān)敿?xì)論述什么是數(shù)據(jù)庫事務(wù)的ACID特性，并說明在實(shí)際應(yīng)用中如何保證事務(wù)的原子性和隔離性。論述2：請比較并對比深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）的優(yōu)缺點(diǎn)，并說明在哪些場景下更適合使用DFS或BFS。---標(biāo)準(zhǔn)答案及解析一、判斷題1.×（抽象類不能實(shí)例化對象，必須被繼承）。2.×（快速排序的平均時間復(fù)雜度為O(nlogn)，最壞情況為O(n2)）。3.×（JOIN可以連接多個表）。4.√（滿二叉樹所有非葉子節(jié)點(diǎn)都是度為2的節(jié)點(diǎn)，葉子節(jié)點(diǎn)數(shù)比非葉子節(jié)點(diǎn)數(shù)多1）。5.×（TCP是面向連接的傳輸協(xié)議）。6.√（在最佳情況下，哈希表可以通過避免沖突實(shí)現(xiàn)O(1)時間復(fù)雜度）。7.√（CAP定理指出分布式系統(tǒng)無法同時滿足一致性、可用性和分區(qū)容錯性中的三者）。8.×（遞歸函數(shù)調(diào)用是否導(dǎo)致棧溢出取決于遞歸深度和系統(tǒng)棧大?。?。9.×（深度優(yōu)先搜索的訪問順序與鄰接表的存儲順序無關(guān)）。10.×（Python中的列表是可變的，但元組是不可變的）。二、單選題1.D（鏈表適合實(shí)現(xiàn)LRU緩存，可以通過雙向鏈表和哈希表結(jié)合實(shí)現(xiàn)）。2.A（客戶端需要發(fā)送ACK確認(rèn)連接）。3.A（快速排序在最壞情況下為O(n2)，但平均為O(nlogn)）。4.B（`GROUPBY`與`HAVING`一起使用，`HAVING`用于過濾分組后的結(jié)果）。5.A（Dijkstra算法用于單源最短路徑問題）。6.A（分片的主要目的是提高查詢速度和系統(tǒng)擴(kuò)展性）。7.B（工廠方法模式屬于創(chuàng)建型模式）。8.B（刪除節(jié)點(diǎn)后，樹的高度最多可能增加1）。9.B（SIP用于實(shí)時音視頻傳輸）。10.C（`lambda`函數(shù)用于實(shí)現(xiàn)匿名函數(shù)）。三、多選題1.ABCD（ACID特性包括原子性、一致性、隔離性、持久性）。2.AB（DFS和BFS可以檢測環(huán)，Dijkstra和Floyd-Warshall用于最短路徑）。3.BCD（鏈表、堆、哈希表支持動態(tài)擴(kuò)容，數(shù)組需要重新分配）。4.ABC（輪詢、最少連接、哈希一致性是常見負(fù)載均衡策略）。5.ABCD（封裝、繼承、多態(tài)、抽象是面向?qū)ο缶幊痰奶匦裕?.ABCD（SYN_SENT、ESTABLISHED、FIN_WAIT、CLOSE_WAIT都是TCP狀態(tài)）。7.BD（插入排序和歸并排序是穩(wěn)定的，快速排序和堆排序不穩(wěn)定）。8.ABCD（COUNT、SUM、AVG、MAX都是聚合函數(shù)）。9.ABCD（DDoS、SQL注入、XSS、中間人攻擊都是常見網(wǎng)絡(luò)攻擊類型）。10.BD（列表和字典是可變的，字符串和元組是不可變的）。四、案例分析案例1：-哈希表：優(yōu)點(diǎn)：查找效率高（O(1)），適合快速查找好友關(guān)系。缺點(diǎn)：需要處理哈希沖突，內(nèi)存占用可能較大。適用場景：好友關(guān)系查詢頻繁，且用戶ID分布均勻。-二叉搜索樹：優(yōu)點(diǎn)：可以按用戶ID排序，適合需要有序遍歷的場景。缺點(diǎn)：查找效率較低（O(logn)），插入和刪除操作較復(fù)雜。適用場景：需要按用戶ID排序或范圍查詢的場景。案例2：算法：1.初始化兩個指針，left指向數(shù)組的開始，right指向數(shù)組的末尾。2.當(dāng)left<right時：-如果arr[left]是奇數(shù)，left右移。-如果arr[right]是偶數(shù)，right左移。-如果arr[left]是偶數(shù)且arr[right]是奇數(shù)，交換left和right的值，left右移，right左移。3.最終數(shù)組中所有奇數(shù)都在偶數(shù)之前。時間復(fù)雜度：O(n)案例3：-范圍分片（RangeSharding）：優(yōu)點(diǎn)：數(shù)據(jù)分布均勻，查詢效率高。缺點(diǎn)：需要預(yù)先知道數(shù)據(jù)范圍，不適合動態(tài)增刪數(shù)據(jù)。-哈希分片（HashSharding）：優(yōu)點(diǎn)：數(shù)據(jù)分布均勻，適合動態(tài)增刪數(shù)據(jù)。缺點(diǎn)：可能存在熱點(diǎn)問題（某些節(jié)點(diǎn)負(fù)載過高）。五、論述題論述1：ACID特性：-原子性（Atomicity）：事務(wù)中的所有操作要么全部成功，要么全部失敗。保證方法：使用日志記錄事務(wù)操作，出現(xiàn)故障時通過回滾恢復(fù)。-一致性（Consistency）：事務(wù)必須使數(shù)據(jù)庫從一個一致性狀態(tài)轉(zhuǎn)移到另一個一致性狀態(tài)。保證方法：通過約束、觸發(fā)器等機(jī)制確保數(shù)據(jù)完整性。-隔離性（Isolation）：并發(fā)執(zhí)行的事務(wù)之間互不干擾。保證方法：使用鎖機(jī)制或樂觀并發(fā)控制。-持久性（Durability）：事務(wù)一旦