北京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)研究生考試試卷考試時(shí)長(zhǎng)：120分鐘滿分：100分班級(jí)：__________姓名：__________學(xué)號(hào)：__________得分：__________北京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)研究生考試試卷考核對(duì)象：報(bào)考北京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)的碩士研究生考生題型分值分布：-判斷題（總共10題，每題2分）——總分20分-單選題（總共10題，每題2分）——總分20分-多選題（總共10題，每題2分）——總分20分-案例分析（總共3題，每題6分）——總分18分-論述題（總共2題，每題11分）——總分22分總分：100分---一、判斷題（每題2分，共20分）1.計(jì)算機(jī)網(wǎng)絡(luò)中的TCP協(xié)議是一種面向連接的、可靠的傳輸協(xié)議。2.冒泡排序的時(shí)間復(fù)雜度在最好情況下可以達(dá)到O(1)。3.在數(shù)據(jù)庫(kù)設(shè)計(jì)中，范式越高的關(guān)系模式一定越優(yōu)。4.機(jī)器學(xué)習(xí)中的過(guò)擬合是指模型在訓(xùn)練數(shù)據(jù)上表現(xiàn)良好，但在測(cè)試數(shù)據(jù)上表現(xiàn)較差。5.圖靈機(jī)是圖靈提出的理論計(jì)算模型，可以模擬任何可計(jì)算的算法。6.在面向?qū)ο缶幊讨?，繼承和多態(tài)是兩個(gè)核心概念，但封裝不是。7.二叉搜索樹(shù)的查找時(shí)間復(fù)雜度始終為O(logn)。8.分布式系統(tǒng)的CAP定理指出，系統(tǒng)最多只能同時(shí)滿足一致性、可用性和分區(qū)容錯(cuò)性中的兩項(xiàng)。9.在自然語(yǔ)言處理中，詞嵌入技術(shù)可以將詞語(yǔ)映射到高維向量空間。10.深度優(yōu)先搜索和廣度優(yōu)先搜索是兩種常見(jiàn)的圖遍歷算法，但它們的時(shí)間復(fù)雜度相同。二、單選題（每題2分，共20分）1.下列哪種排序算法的平均時(shí)間復(fù)雜度是O(nlogn)？A.快速排序B.插入排序C.選擇排序D.冒泡排序2.在關(guān)系數(shù)據(jù)庫(kù)中，外鍵主要用于維護(hù)？A.數(shù)據(jù)完整性B.數(shù)據(jù)一致性C.數(shù)據(jù)冗余D.數(shù)據(jù)安全性3.下列哪種算法不屬于貪心算法？A.貪心選擇B.分治C.動(dòng)態(tài)規(guī)劃D.最小生成樹(shù)4.在計(jì)算機(jī)組成原理中，ALU指的是？A.中央處理器B.累加器C.算術(shù)邏輯單元D.控制單元5.下列哪種數(shù)據(jù)結(jié)構(gòu)是棧的典型應(yīng)用？A.隊(duì)列B.棧C.鏈表D.樹(shù)6.在計(jì)算機(jī)網(wǎng)絡(luò)中，HTTP協(xié)議屬于？A.應(yīng)用層協(xié)議B.傳輸層協(xié)議C.網(wǎng)絡(luò)層協(xié)議D.物理層協(xié)議7.下列哪種數(shù)據(jù)庫(kù)模型最適合處理事務(wù)性數(shù)據(jù)？A.關(guān)系型數(shù)據(jù)庫(kù)B.非關(guān)系型數(shù)據(jù)庫(kù)C.搜索引擎D.分布式數(shù)據(jù)庫(kù)8.在機(jī)器學(xué)習(xí)中，支持向量機(jī)（SVM）主要用于？A.分類(lèi)問(wèn)題B.回歸問(wèn)題C.聚類(lèi)問(wèn)題D.關(guān)聯(lián)問(wèn)題9.下列哪種算法不屬于圖算法？A.Dijkstra算法B.Floyd-Warshall算法C.快速排序D.Kruskal算法10.在操作系統(tǒng)內(nèi)核中，中斷處理主要用于？A.進(jìn)程調(diào)度B.內(nèi)存管理C.設(shè)備驅(qū)動(dòng)D.文件系統(tǒng)三、多選題（每題2分，共20分）1.下列哪些是數(shù)據(jù)庫(kù)范式的類(lèi)型？A.第一范式B.第二范式C.第三范式D.BCNF范式2.下列哪些是圖遍歷算法？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.Dijkstra算法D.Floyd-Warshall算法3.下列哪些是機(jī)器學(xué)習(xí)中的常見(jiàn)損失函數(shù)？A.均方誤差B.交叉熵C.hingelossD.均值絕對(duì)誤差4.下列哪些是計(jì)算機(jī)組成原理中的基本部件？A.CPUB.內(nèi)存C.輸入/輸出設(shè)備D.控制單元5.下列哪些是棧的應(yīng)用場(chǎng)景？A.函數(shù)調(diào)用棧B.表達(dá)式求值C.括號(hào)匹配D.隊(duì)列實(shí)現(xiàn)6.下列哪些是計(jì)算機(jī)網(wǎng)絡(luò)中的常見(jiàn)協(xié)議？A.TCPB.UDPC.IPD.HTTP7.下列哪些是數(shù)據(jù)庫(kù)設(shè)計(jì)中的常見(jiàn)范式？A.第一范式B.第二范式C.第三范式D.BCNF范式8.下列哪些是機(jī)器學(xué)習(xí)中的常見(jiàn)模型？A.線性回歸B.決策樹(shù)C.支持向量機(jī)D.神經(jīng)網(wǎng)絡(luò)9.下列哪些是操作系統(tǒng)中的常見(jiàn)概念？A.進(jìn)程B.內(nèi)存管理C.文件系統(tǒng)D.設(shè)備驅(qū)動(dòng)10.下列哪些是圖算法的應(yīng)用場(chǎng)景？A.最短路徑B.最小生成樹(shù)C.圖遍歷D.排序四、案例分析（每題6分，共18分）1.數(shù)據(jù)庫(kù)設(shè)計(jì)案例：某電商公司需要設(shè)計(jì)一個(gè)數(shù)據(jù)庫(kù)來(lái)管理商品信息，包括商品ID、商品名稱(chēng)、價(jià)格、庫(kù)存數(shù)量、分類(lèi)ID和分類(lèi)名稱(chēng)。分類(lèi)名稱(chēng)有“電子產(chǎn)品”、“家居用品”、“服裝”等。請(qǐng)?jiān)O(shè)計(jì)一個(gè)符合第三范式的數(shù)據(jù)庫(kù)表結(jié)構(gòu)，并說(shuō)明外鍵的作用。2.算法應(yīng)用案例：給定一個(gè)無(wú)向圖，其中節(jié)點(diǎn)表示城市，邊表示城市之間的道路，每條邊有一個(gè)權(quán)重（表示距離）。請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，找出所有城市中任意兩個(gè)城市之間的最短路徑。說(shuō)明算法的適用場(chǎng)景和復(fù)雜度。3.機(jī)器學(xué)習(xí)應(yīng)用案例：某公司希望利用機(jī)器學(xué)習(xí)預(yù)測(cè)用戶(hù)的購(gòu)買(mǎi)行為。已知數(shù)據(jù)集包含用戶(hù)的年齡、性別、購(gòu)買(mǎi)歷史和購(gòu)買(mǎi)金額。請(qǐng)?jiān)O(shè)計(jì)一個(gè)簡(jiǎn)單的機(jī)器學(xué)習(xí)模型，并說(shuō)明如何評(píng)估模型的性能。五、論述題（每題11分，共22分）1.計(jì)算機(jī)網(wǎng)絡(luò)中的TCP協(xié)議：請(qǐng)?jiān)敿?xì)論述TCP協(xié)議的工作原理，包括三次握手、四次揮手、流量控制和擁塞控制等機(jī)制，并說(shuō)明TCP協(xié)議在互聯(lián)網(wǎng)中的重要性。2.深度優(yōu)先搜索與廣度優(yōu)先搜索：請(qǐng)?jiān)敿?xì)比較深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）的優(yōu)缺點(diǎn)，并說(shuō)明它們?cè)诓煌瑘?chǎng)景下的應(yīng)用。---標(biāo)準(zhǔn)答案及解析一、判斷題1.√2.×（最好情況為O(n)）3.×（高范式不一定最優(yōu)，需結(jié)合業(yè)務(wù)需求）4.√5.√6.×（封裝也是核心概念之一）7.×（最壞情況為O(n)）8.√9.√10.×（時(shí)間復(fù)雜度不同，DFS為O(V+E)，BFS為O(V+E)）二、單選題1.A2.A3.B4.C5.B6.A7.A8.A9.C10.C三、多選題1.A,B,C,D2.A,B3.A,B,C,D4.A,B,C,D5.A,B,C6.A,B,C,D7.A,B,C,D8.A,B,C,D9.A,B,C,D10.A,B,C,D四、案例分析1.數(shù)據(jù)庫(kù)設(shè)計(jì)案例：-表結(jié)構(gòu)：```CREATETABLECategory(CategoryIDINTPRIMARYKEY,CategoryNameVARCHAR(50)NOTNULL);CREATETABLEProduct(ProductIDINTPRIMARYKEY,ProductNameVARCHAR(100)NOTNULL,PriceDECIMAL(10,2)NOTNULL,StockINTNOTNULL,CategoryIDINT,FOREIGNKEY(CategoryID)REFERENCESCategory(CategoryID));```-外鍵作用：維護(hù)商品分類(lèi)的引用完整性，確保每個(gè)商品都屬于一個(gè)有效的分類(lèi)。2.算法應(yīng)用案例：-算法：Dijkstra算法-適用場(chǎng)景：?jiǎn)卧醋疃搪窂絾?wèn)題，適用于帶權(quán)無(wú)向圖或有權(quán)向圖。-復(fù)雜度：時(shí)間復(fù)雜度為O((V+E)logV)，其中V是節(jié)點(diǎn)數(shù)，E是邊數(shù)。3.機(jī)器學(xué)習(xí)應(yīng)用案例：-模型：線性回歸或邏輯回歸-評(píng)估方法：使用均方誤差（MSE）或準(zhǔn)確率（Accuracy）評(píng)估模型性能。五、論述題1.計(jì)算機(jī)網(wǎng)絡(luò)中的TCP協(xié)議：-工作原理：-三次握手：客戶(hù)端發(fā)送SYN，服務(wù)器回復(fù)SYN-ACK，客戶(hù)端發(fā)送ACK。-四次揮手：客戶(hù)端發(fā)送FIN，服務(wù)器回復(fù)ACK，服務(wù)器發(fā)送FIN，客戶(hù)端回復(fù)ACK。-流量控制：通過(guò)滑動(dòng)窗口機(jī)制控制發(fā)送速率，防止接收端過(guò)載。-擁塞控制：通過(guò)慢啟動(dòng)、擁塞避免、快速重傳和快速恢復(fù)等機(jī)制控制網(wǎng)絡(luò)擁塞。-重要性：TCP協(xié)議提供可靠的數(shù)據(jù)傳輸服務(wù)，是互聯(lián)網(wǎng)通信的基礎(chǔ)。2.