南京大學考研計算機科學試卷考試時長：120分鐘滿分：100分班級：__________姓名：__________學號：__________得分：__________試卷名稱：南京大學考研計算機科學試卷考核對象：計算機科學專業(yè)碩士研究生入學考試題型分值分布：-判斷題（總共10題，每題2分）總分20分-單選題（總共10題，每題2分）總分20分-多選題（總共10題，每題2分）總分20分-案例分析（總共3題，每題6分）總分18分-論述題（總共2題，每題11分）總分22分總分：100分---一、判斷題（每題2分，共20分）1.計算機程序的本質是算法的電子實現。2.快速排序算法在最壞情況下的時間復雜度是O(n^2)。3.在TCP/IP協(xié)議簇中，IP協(xié)議負責數據傳輸的可靠性和順序性。4.數據庫中的事務必須滿足原子性、一致性、隔離性和持久性（ACID）四個特性。5.機器學習中的過擬合是指模型對訓練數據擬合過度，泛化能力差。6.二叉搜索樹的查找時間復雜度始終為O(logn)。7.在面向對象編程中，繼承和多態(tài)是兩個核心機制。8.線程和進程的主要區(qū)別在于線程共享進程的內存空間。9.分布式系統(tǒng)的容錯性是指系統(tǒng)在部分節(jié)點失效時仍能正常工作。10.圖的廣度優(yōu)先搜索（BFS）和深度優(yōu)先搜索（DFS）的時間復雜度相同。二、單選題（每題2分，共20分）1.下列哪種數據結構是先進先出（FIFO）的？A.隊列B.棧C.鏈表D.樹2.在關系數據庫中，主鍵的作用是？A.確保數據唯一性B.提高查詢效率C.限制數據類型D.以上都是3.決策樹算法中，選擇分裂屬性的標準通常是？A.信息增益B.熵C.基尼系數D.以上都是4.下列哪種算法不屬于動態(tài)規(guī)劃？A.背包問題B.最長公共子序列C.快速排序D.斐波那契數列5.在計算機網絡中，HTTP協(xié)議屬于？A.應用層協(xié)議B.傳輸層協(xié)議C.網絡層協(xié)議D.數據鏈路層協(xié)議6.操作系統(tǒng)的內存管理中，分頁技術的主要目的是？A.提高內存利用率B.減少內存碎片C.實現虛擬內存D.以上都是7.下列哪種加密算法屬于對稱加密？A.RSAB.AESC.ECCD.SHA-2568.在數據庫索引優(yōu)化中，B+樹索引通常優(yōu)于B樹的原因是？A.B+樹支持范圍查詢B.B+樹節(jié)點密度更高C.B+樹更節(jié)省存儲空間D.以上都是9.下列哪種算法適用于大規(guī)模數據集的聚類分析？A.K-meansB.決策樹C.DijkstraD.快速排序10.在分布式系統(tǒng)中，CAP定理指出系統(tǒng)最多只能同時滿足？A.一致性、可用性、分區(qū)容錯性B.可靠性、可用性、分區(qū)容錯性C.一致性、可靠性、分區(qū)容錯性D.可靠性、一致性、分區(qū)容錯性三、多選題（每題2分，共20分）1.下列哪些屬于算法的時間復雜度表示方法？A.O(1)B.O(logn)C.O(n^2)D.O(n!)2.在數據庫設計中，范式的作用包括？A.減少數據冗余B.提高數據一致性C.增加查詢效率D.簡化數據管理3.機器學習中的監(jiān)督學習包括哪些任務？A.分類B.回歸C.聚類D.降維4.下列哪些屬于常見的網絡攻擊類型？A.DDoS攻擊B.SQL注入C.中間人攻擊D.惡意軟件5.操作系統(tǒng)的進程管理功能包括？A.進程創(chuàng)建與銷毀B.進程調度C.進程同步與互斥D.資源分配6.在數據結構中，下列哪些屬于遞歸算法的應用場景？A.隊列操作B.二叉樹遍歷C.快速排序D.深度優(yōu)先搜索7.下列哪些屬于常見的數據庫事務隔離級別？A.讀未提交B.讀已提交C.可重復讀D.串行化8.在計算機網絡中，下列哪些屬于傳輸層協(xié)議？A.TCPB.UDPC.HTTPD.FTP9.機器學習中的特征工程包括哪些方法？A.特征選擇B.特征縮放C.特征編碼D.模型選擇10.分布式系統(tǒng)的常見架構包括？A.主從架構B.對等架構C.微服務架構D.客戶端-服務器架構四、案例分析（每題6分，共18分）1.數據庫索引優(yōu)化案例某電商平臺的訂單表包含字段：訂單ID（主鍵）、用戶ID、商品ID、訂單金額、下單時間。假設該表有百萬級數據，查詢時經常需要根據用戶ID和下單時間進行組合查詢。請分析以下兩種索引方案，并說明哪種更優(yōu)，理由是什么？-方案一：創(chuàng)建復合索引（用戶ID，下單時間）-方案二：創(chuàng)建兩個單列索引（用戶ID，下單時間）2.分布式系統(tǒng)容錯性設計案例某分布式數據庫系統(tǒng)采用主從復制架構，主節(jié)點負責寫操作，從節(jié)點負責讀操作。假設主節(jié)點發(fā)生故障，系統(tǒng)需要自動切換到從節(jié)點。請分析該架構的容錯性設計要點，并說明可能存在的風險及改進措施。3.機器學習模型調優(yōu)案例某公司使用K-means算法對用戶進行聚類分析，初始聚類中心隨機選擇。發(fā)現聚類效果不理想，用戶分布不均勻。請?zhí)岢鲋辽賰煞N改進方法，并說明原理。五、論述題（每題11分，共22分）1.算法設計與分析論述請論述快速排序算法的原理、時間復雜度分析（最好、最壞、平均情況），并說明其優(yōu)缺點及適用場景。2.數據庫事務管理論述請論述數據庫事務的ACID特性，并分析在實際應用中如何保證事務的隔離性和持久性，舉例說明可能出現的并發(fā)問題（如臟讀、不可重復讀）及其解決方案。---標準答案及解析一、判斷題1.√2.√3.×（IP協(xié)議負責數據傳輸的無連接性，TCP協(xié)議負責可靠性和順序性）4.√5.√6.×（在平衡二叉搜索樹中查找時間復雜度為O(logn)，非平衡樹可能為O(n)）7.√8.√9.√10.×（BFS時間復雜度為O(V+E)，DFS時間復雜度為O(V+E)，但實現方式不同）二、單選題1.A2.A3.D4.C5.A6.D7.B8.D9.A10.A三、多選題1.A,B,C,D2.A,B,C,D3.A,B4.A,B,C,D5.A,B,C,D6.B,C,D7.A,B,C,D8.A,B9.A,B,C10.A,B,C,D四、案例分析1.數據庫索引優(yōu)化案例-方案一更優(yōu)。復合索引可以支持范圍查詢，且查詢效率更高，因為索引樹只需要遍歷部分節(jié)點即可滿足條件。-方案二可能需要全表掃描，效率較低。2.分布式系統(tǒng)容錯性設計案例-設計要點：主從復制、心跳檢測、自動故障切換。-風險：數據一致性問題、切換延遲。-改進措施：增加延遲檢測機制、使用多主架構。3.機器學習模型調優(yōu)案例-方法一：調整初始聚類中心（如K-means++算法）。-方法二：增加數據預處理（如標準化）。五、論述題1.算法設計與分析論述-原理：分治策略，選擇基準元素，分區(qū)排序。-時間復雜度：最好/平均O(nlogn)，最壞O(n^2)。-優(yōu)點：效率高，通用性強。-缺點：最壞情況性能差