北京大學(xué)2021年信息科學(xué)專業(yè)自主招生考試試題

姓名：__________考號(hào)：__________題號(hào)一二三四五總分評(píng)分一、單選題(共10題)1.什么是哈希表？()A.一種線性表B.一種樹(shù)形結(jié)構(gòu)C.一種基于鍵值對(duì)的存儲(chǔ)結(jié)構(gòu)D.一種堆結(jié)構(gòu)2.以下哪個(gè)算法的平均時(shí)間復(fù)雜度最接近O(nlogn)？()A.快速排序B.冒泡排序C.選擇排序D.插入排序3.在深度優(yōu)先搜索中，回溯算法的作用是什么？()A.找到一條路徑B.回到上一個(gè)節(jié)點(diǎn)C.遍歷所有節(jié)點(diǎn)D.檢測(cè)是否有環(huán)4.以下哪個(gè)算法可以用于求解單源最短路徑問(wèn)題？()A.最大堆排序B.冒泡排序C.Dijkstra算法D.快速排序5.什么是機(jī)器學(xué)習(xí)中的過(guò)擬合？()A.模型對(duì)訓(xùn)練數(shù)據(jù)的擬合程度過(guò)高B.模型對(duì)測(cè)試數(shù)據(jù)的擬合程度過(guò)高C.模型對(duì)驗(yàn)證數(shù)據(jù)的擬合程度過(guò)高D.模型對(duì)訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)的擬合程度都過(guò)高6.以下哪個(gè)語(yǔ)言不是一種面向?qū)ο蟮木幊陶Z(yǔ)言？()A.JavaB.C++C.PythonD.JavaScript7.什么是區(qū)塊鏈技術(shù)的主要優(yōu)勢(shì)？()A.安全性高B.可擴(kuò)展性強(qiáng)C.中心化程度低D.以上都是8.以下哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用于實(shí)現(xiàn)圖的最短路徑算法？()A.隊(duì)列B.棧C.鏈表D.樹(shù)9.以下哪個(gè)算法可以用于文本分類任務(wù)？()A.決策樹(shù)B.支持向量機(jī)C.神經(jīng)網(wǎng)絡(luò)D.以上都是10.什么是數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則挖掘？()A.從大量數(shù)據(jù)中提取出有用的信息B.發(fā)現(xiàn)數(shù)據(jù)中的潛在關(guān)聯(lián)關(guān)系C.構(gòu)建數(shù)據(jù)模型D.以上都是二、多選題(共5題)11.以下哪些是圖論中的基本概念？()A.節(jié)點(diǎn)B.邊C.路徑D.環(huán)E.樹(shù)12.以下哪些是機(jī)器學(xué)習(xí)中的監(jiān)督學(xué)習(xí)方法？()A.決策樹(shù)B.支持向量機(jī)C.神經(jīng)網(wǎng)絡(luò)D.聚類E.主成分分析13.以下哪些是數(shù)據(jù)庫(kù)設(shè)計(jì)中的范式？()A.第一范式B.第二范式C.第三范式D.第四范式E.第五范式14.以下哪些是計(jì)算機(jī)網(wǎng)絡(luò)中的協(xié)議？()A.TCP/IPB.HTTPC.FTPD.SMTPE.DNS15.以下哪些是人工智能領(lǐng)域的研究方向？()A.計(jì)算機(jī)視覺(jué)B.自然語(yǔ)言處理C.機(jī)器學(xué)習(xí)D.機(jī)器人技術(shù)E.人工智能倫理三、填空題(共5題)16.在計(jì)算機(jī)網(wǎng)絡(luò)中，用于在數(shù)據(jù)鏈路層實(shí)現(xiàn)可靠傳輸?shù)膮f(xié)議是______。17.在數(shù)據(jù)庫(kù)設(shè)計(jì)中，第三范式（3NF）要求表中的每一個(gè)非主屬性都必須______。18.在機(jī)器學(xué)習(xí)中，一種常用的無(wú)監(jiān)督學(xué)習(xí)方法是______，它通過(guò)將數(shù)據(jù)點(diǎn)分為不同的簇來(lái)發(fā)現(xiàn)數(shù)據(jù)的內(nèi)在結(jié)構(gòu)。19.在圖論中，如果一個(gè)無(wú)向圖的所有頂點(diǎn)的度數(shù)都相同，那么這個(gè)圖被稱為_(kāi)_____。20.在人工智能領(lǐng)域，一種基于統(tǒng)計(jì)的機(jī)器學(xué)習(xí)方法是______，它通過(guò)訓(xùn)練模型來(lái)預(yù)測(cè)新數(shù)據(jù)的概率分布。四、判斷題(共5題)21.哈希表可以解決哈希沖突的唯一方法是鏈地址法。()A.正確B.錯(cuò)誤22.動(dòng)態(tài)規(guī)劃算法總是比貪心算法更優(yōu)。()A.正確B.錯(cuò)誤23.一個(gè)有向無(wú)環(huán)圖（DAG）中，所有頂點(diǎn)的出度之和等于所有頂點(diǎn)的入度之和。()A.正確B.錯(cuò)誤24.所有的神經(jīng)網(wǎng)絡(luò)都是遞歸神經(jīng)網(wǎng)絡(luò)（RNN）。()A.正確B.錯(cuò)誤25.在數(shù)據(jù)庫(kù)中，索引可以提高查詢速度，但會(huì)增加插入和刪除操作的開(kāi)銷(xiāo)。()A.正確B.錯(cuò)誤五、簡(jiǎn)單題(共5題)26.請(qǐng)解釋一下什么是時(shí)間復(fù)雜度，并舉例說(shuō)明。27.請(qǐng)描述一下什么是機(jī)器學(xué)習(xí)的監(jiān)督學(xué)習(xí)和非監(jiān)督學(xué)習(xí)，并舉例說(shuō)明。28.請(qǐng)解釋一下什么是深度學(xué)習(xí)，并說(shuō)明它與傳統(tǒng)機(jī)器學(xué)習(xí)的區(qū)別。29.請(qǐng)解釋一下什么是區(qū)塊鏈技術(shù)，并說(shuō)明它的主要特點(diǎn)。30.請(qǐng)解釋一下什么是云計(jì)算，并說(shuō)明它的主要服務(wù)模式。

北京大學(xué)2021年信息科學(xué)專業(yè)自主招生考試試題一、單選題(共10題)1.【答案】C【解析】哈希表是一種基于鍵值對(duì)的存儲(chǔ)結(jié)構(gòu)，通過(guò)哈希函數(shù)將鍵映射到表中的位置，從而實(shí)現(xiàn)快速查找。2.【答案】A【解析】快速排序的平均時(shí)間復(fù)雜度為O(nlogn)，而其他幾種排序算法的平均時(shí)間復(fù)雜度都大于O(nlogn)。3.【答案】B【解析】在深度優(yōu)先搜索中，回溯算法的作用是回到上一個(gè)節(jié)點(diǎn)，繼續(xù)探索其他路徑。4.【答案】C【解析】Dijkstra算法可以用于求解單源最短路徑問(wèn)題，它通過(guò)貪心策略逐步找到最短路徑。5.【答案】A【解析】機(jī)器學(xué)習(xí)中的過(guò)擬合是指模型對(duì)訓(xùn)練數(shù)據(jù)的擬合程度過(guò)高，導(dǎo)致在測(cè)試數(shù)據(jù)上表現(xiàn)不佳。6.【答案】B【解析】C++是一種過(guò)程式編程語(yǔ)言，而Java、Python和JavaScript都是面向?qū)ο蟮木幊陶Z(yǔ)言。7.【答案】D【解析】區(qū)塊鏈技術(shù)的主要優(yōu)勢(shì)包括安全性高、可擴(kuò)展性強(qiáng)、中心化程度低等。8.【答案】D【解析】樹(shù)可以用于實(shí)現(xiàn)圖的最短路徑算法，如Dijkstra算法和A*算法。9.【答案】D【解析】決策樹(shù)、支持向量機(jī)和神經(jīng)網(wǎng)絡(luò)都可以用于文本分類任務(wù)，它們各自有不同的特點(diǎn)和適用場(chǎng)景。10.【答案】B【解析】數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則挖掘是指發(fā)現(xiàn)數(shù)據(jù)中的潛在關(guān)聯(lián)關(guān)系，如購(gòu)物籃分析。二、多選題(共5題)11.【答案】ABCDE【解析】節(jié)點(diǎn)、邊、路徑、環(huán)和樹(shù)都是圖論中的基本概念，它們是圖的基本組成部分。12.【答案】ABC【解析】決策樹(shù)、支持向量機(jī)和神經(jīng)網(wǎng)絡(luò)都是監(jiān)督學(xué)習(xí)方法，它們需要標(biāo)簽數(shù)據(jù)進(jìn)行訓(xùn)練。聚類和主成分分析是無(wú)監(jiān)督學(xué)習(xí)方法。13.【答案】ABC【解析】第一范式、第二范式和第三范式是數(shù)據(jù)庫(kù)設(shè)計(jì)中的基本范式，用于確保數(shù)據(jù)的完整性和減少數(shù)據(jù)冗余。第四范式和第五范式是高級(jí)范式。14.【答案】ABCDE【解析】TCP/IP、HTTP、FTP、SMTP和DNS都是計(jì)算機(jī)網(wǎng)絡(luò)中的協(xié)議，分別用于數(shù)據(jù)傳輸、網(wǎng)頁(yè)訪問(wèn)、文件傳輸、電子郵件發(fā)送和域名解析等。15.【答案】ABCDE【解析】計(jì)算機(jī)視覺(jué)、自然語(yǔ)言處理、機(jī)器學(xué)習(xí)、機(jī)器人技術(shù)和人工智能倫理都是人工智能領(lǐng)域的研究方向，涵蓋了人工智能的多個(gè)方面。三、填空題(共5題)16.【答案】停止等待ARQ【解析】停止等待ARQ（停等自動(dòng)重傳請(qǐng)求）是一種簡(jiǎn)單的可靠傳輸協(xié)議，它通過(guò)停止發(fā)送方直到收到確認(rèn)消息來(lái)確保數(shù)據(jù)的可靠傳輸。17.【答案】非傳遞依賴【解析】第三范式（3NF）要求表中的每一個(gè)非主屬性都必須非傳遞依賴于主鍵，即非主屬性之間不能存在依賴關(guān)系。18.【答案】聚類【解析】聚類是一種無(wú)監(jiān)督學(xué)習(xí)方法，它通過(guò)將數(shù)據(jù)點(diǎn)分為不同的簇來(lái)發(fā)現(xiàn)數(shù)據(jù)中的模式和結(jié)構(gòu)，無(wú)需預(yù)先指定標(biāo)簽。19.【答案】正則圖【解析】在圖論中，如果一個(gè)無(wú)向圖的所有頂點(diǎn)的度數(shù)都相同，那么這個(gè)圖被稱為正則圖，其中每個(gè)頂點(diǎn)都有相同數(shù)量的邊。20.【答案】貝葉斯網(wǎng)絡(luò)【解析】貝葉斯網(wǎng)絡(luò)是一種基于統(tǒng)計(jì)的機(jī)器學(xué)習(xí)方法，它通過(guò)概率推理來(lái)預(yù)測(cè)新數(shù)據(jù)的概率分布，并學(xué)習(xí)數(shù)據(jù)之間的依賴關(guān)系。四、判斷題(共5題)21.【答案】錯(cuò)誤【解析】哈希表解決哈希沖突的方法不僅限于鏈地址法，還有開(kāi)放尋址法等。鏈地址法是通過(guò)在每個(gè)哈希槽中存儲(chǔ)一個(gè)鏈表來(lái)處理沖突。22.【答案】錯(cuò)誤【解析】動(dòng)態(tài)規(guī)劃算法并不總是比貪心算法更優(yōu)。動(dòng)態(tài)規(guī)劃適用于問(wèn)題可以通過(guò)將問(wèn)題分解為子問(wèn)題來(lái)解決，而貪心算法在某些情況下可能更快但不是最優(yōu)解。23.【答案】正確【解析】在有向無(wú)環(huán)圖（DAG）中，因?yàn)闆](méi)有環(huán)，所以每個(gè)頂點(diǎn)的出度等于它的入度，因此所有頂點(diǎn)的出度之和等于所有頂點(diǎn)的入度之和。24.【答案】錯(cuò)誤【解析】并不是所有的神經(jīng)網(wǎng)絡(luò)都是遞歸神經(jīng)網(wǎng)絡(luò)（RNN）。神經(jīng)網(wǎng)絡(luò)有多種類型，包括前饋神經(jīng)網(wǎng)絡(luò)、卷積神經(jīng)網(wǎng)絡(luò)（CNN）等，而RNN是一種特殊的神經(jīng)網(wǎng)絡(luò)，用于處理序列數(shù)據(jù)。25.【答案】正確【解析】索引可以加快查詢速度，因?yàn)樗鼈冊(cè)试S數(shù)據(jù)庫(kù)快速定位到數(shù)據(jù)。然而，每次插入或刪除數(shù)據(jù)時(shí)，索引也需要更新，這會(huì)增加這些操作的開(kāi)銷(xiāo)。五、簡(jiǎn)答題(共5題)26.【答案】時(shí)間復(fù)雜度是描述算法執(zhí)行時(shí)間隨輸入規(guī)模增長(zhǎng)趨勢(shì)的一個(gè)量度。它通常用大O符號(hào)表示，例如O(n)、O(n^2)等。時(shí)間復(fù)雜度可以幫助我們分析和比較不同算法的效率。舉例來(lái)說(shuō)，一個(gè)簡(jiǎn)單的線性搜索算法的時(shí)間復(fù)雜度是O(n)，因?yàn)樗枰闅v整個(gè)列表來(lái)找到目標(biāo)元素；而一個(gè)二分搜索算法的時(shí)間復(fù)雜度是O(logn)，因?yàn)樗看味伎梢耘懦话氲脑亍！窘馕觥繒r(shí)間復(fù)雜度是算法分析中的一個(gè)重要概念，它幫助我們理解算法在不同規(guī)模數(shù)據(jù)上的性能表現(xiàn)。通過(guò)比較不同算法的時(shí)間復(fù)雜度，我們可以選擇最優(yōu)的算法來(lái)解決實(shí)際問(wèn)題。27.【答案】機(jī)器學(xué)習(xí)的監(jiān)督學(xué)習(xí)是指通過(guò)訓(xùn)練數(shù)據(jù)（包含輸入和對(duì)應(yīng)的輸出標(biāo)簽）來(lái)學(xué)習(xí)一個(gè)函數(shù)或模型，使得模型能夠?qū)π碌妮斎霐?shù)據(jù)進(jìn)行預(yù)測(cè)。非監(jiān)督學(xué)習(xí)是指在沒(méi)有明確標(biāo)簽的輸入數(shù)據(jù)上學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和模式。監(jiān)督學(xué)習(xí)的例子包括分類和回歸任務(wù)，如使用支持向量機(jī)進(jìn)行手寫(xiě)數(shù)字識(shí)別；非監(jiān)督學(xué)習(xí)的例子包括聚類和降維，如使用K-means算法對(duì)數(shù)據(jù)點(diǎn)進(jìn)行聚類?！窘馕觥勘O(jiān)督學(xué)習(xí)和非監(jiān)督學(xué)習(xí)是機(jī)器學(xué)習(xí)中的兩種主要學(xué)習(xí)方法，它們?cè)谟?xùn)練數(shù)據(jù)和目標(biāo)上有所不同。理解這兩種方法有助于選擇合適的學(xué)習(xí)策略來(lái)解決特定問(wèn)題。28.【答案】深度學(xué)習(xí)是一種利用深層神經(jīng)網(wǎng)絡(luò)進(jìn)行學(xué)習(xí)的技術(shù)。它通過(guò)多層非線性變換來(lái)提取數(shù)據(jù)的特征，從而實(shí)現(xiàn)對(duì)復(fù)雜模式的學(xué)習(xí)。與傳統(tǒng)機(jī)器學(xué)習(xí)相比，深度學(xué)習(xí)通常需要更多的數(shù)據(jù)和計(jì)算資源，但它能夠自動(dòng)學(xué)習(xí)特征，不需要人工設(shè)計(jì)特征。傳統(tǒng)機(jī)器學(xué)習(xí)通常使用較少的層數(shù)，如單層感知機(jī)，而深度學(xué)習(xí)使用多層神經(jīng)網(wǎng)絡(luò)來(lái)提取更復(fù)雜的特征?！窘馕觥可疃葘W(xué)習(xí)是機(jī)器學(xué)習(xí)的一個(gè)分支，它通過(guò)深度神經(jīng)網(wǎng)絡(luò)來(lái)學(xué)習(xí)數(shù)據(jù)中的復(fù)雜模式。與傳統(tǒng)機(jī)器學(xué)習(xí)相比，深度學(xué)習(xí)在處理復(fù)雜數(shù)據(jù)和模式識(shí)別方面有顯著優(yōu)勢(shì)，但同時(shí)也對(duì)計(jì)算資源有更高的要求。29.【答案】區(qū)塊鏈技術(shù)是一種分布式數(shù)據(jù)庫(kù)技術(shù)，它通過(guò)加密算法和數(shù)據(jù)結(jié)構(gòu)（如鏈表）來(lái)確保數(shù)據(jù)的不可篡改性和透明性。區(qū)塊鏈的主要特點(diǎn)是去中心化、安全性高、透明性和不可篡改性。在區(qū)塊鏈中，數(shù)據(jù)被組織成一系列的數(shù)據(jù)塊，每個(gè)數(shù)據(jù)塊包含一定數(shù)量的交易信息，并通過(guò)加密技術(shù)連接起來(lái)，形成一條鏈?！窘馕觥繀^(qū)塊鏈技術(shù)是一種創(chuàng)新的數(shù)據(jù)存儲(chǔ)和傳輸方式，它通過(guò)去中心化和加密技術(shù)提供了安全、透明和不可篡改的數(shù)據(jù)存儲(chǔ)解決方案。了解區(qū)塊鏈技術(shù)有助于理解其在金融、供應(yīng)鏈管理等領(lǐng)域中的應(yīng)用潛力。30.【答案】云計(jì)算是