南京大學(xué)2020年計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)試題

姓名：__________考號：__________一、單選題(共10題)1.以下哪個算法屬于貪心算法？()A.快速排序B.最長公共子序列C.最短路徑算法（Dijkstra算法）D.動態(tài)規(guī)劃2.在計(jì)算機(jī)網(wǎng)絡(luò)中，以下哪個協(xié)議屬于傳輸層協(xié)議？()A.HTTPB.FTPC.TCPD.UDP3.以下哪個語言不屬于腳本語言？()A.JavaScriptB.PythonC.RubyD.C++4.在數(shù)據(jù)庫中，以下哪個操作會導(dǎo)致數(shù)據(jù)不一致？()A.插入操作B.刪除操作C.更新操作D.查詢操作5.以下哪個算法是用于解決旅行商問題的？()A.暴力法B.貪心算法C.動態(tài)規(guī)劃D.分支限界法6.在計(jì)算機(jī)網(wǎng)絡(luò)中，以下哪個設(shè)備負(fù)責(zé)將數(shù)據(jù)包從源地址傳輸?shù)侥康牡刂罚?)A.路由器B.交換機(jī)C.網(wǎng)橋D.集線器7.以下哪個數(shù)據(jù)結(jié)構(gòu)支持高效的隨機(jī)訪問？()A.鏈表B.棧C.隊(duì)列D.數(shù)組8.在操作系統(tǒng)中，以下哪個功能屬于進(jìn)程管理？()A.文件管理B.存儲管理C.進(jìn)程管理D.設(shè)備管理9.以下哪個算法用于檢測循環(huán)鏈表？()A.快慢指針法B.暴力法C.遞歸法D.分支限界法10.在計(jì)算機(jī)網(wǎng)絡(luò)中，以下哪個協(xié)議屬于應(yīng)用層協(xié)議？()A.IPB.TCPC.HTTPD.UDP二、多選題(共5題)11.在以下哪些情況下，可能會發(fā)生死鎖？()A.兩個進(jìn)程同時請求同一資源B.兩個進(jìn)程競爭同一資源C.進(jìn)程等待某個永遠(yuǎn)不會發(fā)生的信號D.進(jìn)程釋放了已經(jīng)持有的資源12.以下哪些數(shù)據(jù)結(jié)構(gòu)支持高效的隨機(jī)訪問和修改？()A.鏈表B.樹C.數(shù)組D.隊(duì)列13.以下哪些操作是數(shù)據(jù)庫事務(wù)必須滿足的ACID特性？()A.原子性B.一致性C.可持久性D.可串行化14.以下哪些是計(jì)算機(jī)網(wǎng)絡(luò)中的數(shù)據(jù)鏈路層協(xié)議？()A.IPB.TCPC.EthernetD.HTTP15.以下哪些是編譯器的組成部分？()A.詞法分析器B.語法分析器C.語義分析器D.目標(biāo)代碼生成器三、填空題(共5題)16.計(jì)算機(jī)程序設(shè)計(jì)語言中，用于描述算法和程序的語法規(guī)則和結(jié)構(gòu)稱為______。17.在計(jì)算機(jī)網(wǎng)絡(luò)中，______用于將數(shù)據(jù)從發(fā)送方傳輸?shù)浇邮辗健?8.數(shù)據(jù)庫系統(tǒng)中，用于存儲和管理數(shù)據(jù)的結(jié)構(gòu)稱為______。19.在算法分析中，時間復(fù)雜度通常用______表示。20.在操作系統(tǒng)設(shè)計(jì)中，用于管理內(nèi)存分配和回收的機(jī)制稱為______。四、判斷題(共5題)21.一個棧是先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)。()A.正確B.錯誤22.在計(jì)算機(jī)網(wǎng)絡(luò)中，所有的數(shù)據(jù)傳輸都通過TCP協(xié)議進(jìn)行。()A.正確B.錯誤23.一個數(shù)據(jù)庫管理系統(tǒng)（DBMS）必須保證數(shù)據(jù)的一致性和完整性。()A.正確B.錯誤24.在操作系統(tǒng)中，進(jìn)程是資源分配和獨(dú)立調(diào)度的基本單位。()A.正確B.錯誤25.哈希表在查找操作中，時間復(fù)雜度總是O(1)。()A.正確B.錯誤五、簡單題(共5題)26.請簡述什么是動態(tài)規(guī)劃，并舉例說明其在解決實(shí)際問題中的應(yīng)用。27.解釋什么是緩存一致性問題，并說明在多處理器系統(tǒng)中如何解決該問題。28.請解釋什么是哈希沖突，以及如何解決哈希沖突。29.簡述什么是虛擬內(nèi)存，以及它在操作系統(tǒng)中的作用。30.請解釋什么是操作系統(tǒng)中的進(jìn)程調(diào)度，并說明其重要性。

南京大學(xué)2020年計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)試題一、單選題(共10題)1.【答案】C【解析】Dijkstra算法是一種貪心算法，它通過不斷選擇當(dāng)前最短路徑的頂點(diǎn)，逐步構(gòu)建出從源點(diǎn)到所有頂點(diǎn)的最短路徑樹。2.【答案】C【解析】TCP（傳輸控制協(xié)議）和UDP（用戶數(shù)據(jù)報(bào)協(xié)議）都是傳輸層協(xié)議，其中TCP提供可靠的傳輸服務(wù)，而UDP提供不可靠的傳輸服務(wù)。HTTP和FTP是應(yīng)用層協(xié)議。3.【答案】D【解析】C++是一種編譯型語言，它需要編譯成機(jī)器碼才能運(yùn)行。JavaScript、Python和Ruby都是腳本語言，它們可以直接在解釋器中運(yùn)行。4.【答案】C【解析】更新操作可能導(dǎo)致數(shù)據(jù)不一致，因?yàn)槿绻鄠€事務(wù)同時更新同一數(shù)據(jù)，可能會出現(xiàn)部分更新或更新順序錯誤，從而破壞數(shù)據(jù)的一致性。5.【答案】D【解析】旅行商問題（TSP）是一個經(jīng)典的優(yōu)化問題，分支限界法是一種有效的解決方法，它通過剪枝來減少搜索空間。6.【答案】A【解析】路由器負(fù)責(zé)根據(jù)目的地址將數(shù)據(jù)包從源地址傳輸?shù)侥康牡刂罚鶕?jù)路由表選擇最佳路徑。交換機(jī)、網(wǎng)橋和集線器主要用于在同一局域網(wǎng)內(nèi)轉(zhuǎn)發(fā)數(shù)據(jù)包。7.【答案】D【解析】數(shù)組支持高效的隨機(jī)訪問，因?yàn)樗脑卮鎯υ谶B續(xù)的內(nèi)存空間中，可以通過索引直接訪問任意元素。鏈表、棧和隊(duì)列不支持高效的隨機(jī)訪問。8.【答案】C【解析】進(jìn)程管理是操作系統(tǒng)的一個核心功能，它負(fù)責(zé)創(chuàng)建、調(diào)度、同步和終止進(jìn)程。文件管理、存儲管理和設(shè)備管理是操作系統(tǒng)的其他重要功能。9.【答案】A【解析】快慢指針法是一種用于檢測循環(huán)鏈表的算法，它通過兩個指針以不同的速度遍歷鏈表，如果存在循環(huán)，兩個指針最終會相遇。10.【答案】C【解析】HTTP（超文本傳輸協(xié)議）是應(yīng)用層協(xié)議，它用于在Web瀏覽器和服務(wù)器之間傳輸超文本數(shù)據(jù)。IP和TCP是網(wǎng)絡(luò)層和傳輸層協(xié)議，UDP也是傳輸層協(xié)議。二、多選題(共5題)11.【答案】ABC【解析】死鎖通常發(fā)生在以下情況：兩個或多個進(jìn)程同時請求同一資源，進(jìn)程競爭同一資源且資源不足，以及進(jìn)程等待某個永遠(yuǎn)不會發(fā)生的信號。進(jìn)程釋放已經(jīng)持有的資源不會導(dǎo)致死鎖。12.【答案】C【解析】數(shù)組支持高效的隨機(jī)訪問和修改，因?yàn)樗脑卮鎯υ谶B續(xù)的內(nèi)存空間中，可以通過索引直接訪問任意元素。鏈表和樹支持高效的插入和刪除操作，但不支持高效的隨機(jī)訪問。隊(duì)列支持高效的插入和刪除操作，但不是隨機(jī)訪問。13.【答案】ABCD【解析】數(shù)據(jù)庫事務(wù)必須滿足ACID特性，包括原子性（Atomicity）、一致性（Consistency）、可持久性（Durability）和可串行化（Serializability）。這些特性保證了數(shù)據(jù)庫事務(wù)的可靠性和一致性。14.【答案】C【解析】數(shù)據(jù)鏈路層協(xié)議負(fù)責(zé)在相鄰節(jié)點(diǎn)之間可靠地傳輸數(shù)據(jù)幀。其中，Ethernet（以太網(wǎng)）是一種常見的局域網(wǎng)數(shù)據(jù)鏈路層協(xié)議。IP和TCP屬于網(wǎng)絡(luò)層協(xié)議，HTTP屬于應(yīng)用層協(xié)議。15.【答案】ABCD【解析】編譯器通常由詞法分析器、語法分析器、語義分析器和目標(biāo)代碼生成器等組成部分構(gòu)成。這些部分共同工作，將源代碼轉(zhuǎn)換成目標(biāo)代碼。三、填空題(共5題)16.【答案】語言規(guī)范【解析】語言規(guī)范是計(jì)算機(jī)程序設(shè)計(jì)語言中定義的語法規(guī)則和結(jié)構(gòu)，它規(guī)定了如何編寫有效的程序代碼。17.【答案】傳輸層【解析】傳輸層是計(jì)算機(jī)網(wǎng)絡(luò)中的一個重要層次，負(fù)責(zé)在源主機(jī)和目的主機(jī)之間提供端到端的數(shù)據(jù)傳輸服務(wù)。18.【答案】數(shù)據(jù)庫【解析】數(shù)據(jù)庫是一個用于存儲、檢索和管理數(shù)據(jù)的系統(tǒng)，它由數(shù)據(jù)庫管理系統(tǒng)（DBMS）進(jìn)行管理。19.【答案】大O符號【解析】大O符號（O-notation）是算法分析中用來描述算法時間復(fù)雜度的數(shù)學(xué)符號，它表示算法執(zhí)行時間與輸入數(shù)據(jù)規(guī)模的關(guān)系。20.【答案】內(nèi)存管理【解析】內(nèi)存管理是操作系統(tǒng)的一個重要功能，它負(fù)責(zé)管理計(jì)算機(jī)的內(nèi)存資源，包括內(nèi)存分配、回收和內(nèi)存保護(hù)等。四、判斷題(共5題)21.【答案】錯誤【解析】棧是先進(jìn)后出（LIFO）的數(shù)據(jù)結(jié)構(gòu)，即最后進(jìn)入棧的元素最先被取出。22.【答案】錯誤【解析】計(jì)算機(jī)網(wǎng)絡(luò)中，TCP（傳輸控制協(xié)議）和UDP（用戶數(shù)據(jù)報(bào)協(xié)議）是兩種主要的傳輸層協(xié)議，不是所有的數(shù)據(jù)傳輸都通過TCP協(xié)議進(jìn)行。23.【答案】正確【解析】數(shù)據(jù)庫管理系統(tǒng)必須保證數(shù)據(jù)的一致性和完整性，這是數(shù)據(jù)庫設(shè)計(jì)的核心目標(biāo)之一。24.【答案】正確【解析】在操作系統(tǒng)中，進(jìn)程是資源分配和獨(dú)立調(diào)度的基本單位，它代表了正在運(yùn)行的程序?qū)嵗?5.【答案】錯誤【解析】哈希表在理想情況下，查找操作的時間復(fù)雜度是O(1)，但在最壞情況下，如發(fā)生大量沖突時，時間復(fù)雜度可能退化到O(n)。五、簡答題(共5題)26.【答案】動態(tài)規(guī)劃是一種解決優(yōu)化問題的方法，它通過將問題分解為更小的子問題，并存儲子問題的解以避免重復(fù)計(jì)算，從而提高算法效率。動態(tài)規(guī)劃通常用于解決具有重疊子問題和最優(yōu)子結(jié)構(gòu)特征的問題。

例如，計(jì)算斐波那契數(shù)列的值可以使用動態(tài)規(guī)劃。斐波那契數(shù)列的定義是F(n)=F(n-1)+F(n-2)，其中F(0)=0，F(xiàn)(1)=1。使用動態(tài)規(guī)劃，我們可以存儲已經(jīng)計(jì)算出的F(n-1)和F(n-2)的值，避免重復(fù)計(jì)算，從而提高效率?！窘馕觥縿討B(tài)規(guī)劃的核心思想是將復(fù)雜問題分解為子問題，并存儲子問題的解以避免重復(fù)計(jì)算。它適用于具有最優(yōu)子結(jié)構(gòu)和重疊子問題特征的問題，通過遞歸或迭代的方式解決。27.【答案】緩存一致性問題是指當(dāng)多個處理器共享同一數(shù)據(jù)時，每個處理器的緩存中可能存在相同數(shù)據(jù)的不同副本，而這些副本可能因?yàn)楦虏僮鞫兊貌灰恢?。在多處理器系統(tǒng)中，緩存一致性問題可能導(dǎo)致數(shù)據(jù)競爭和不一致的結(jié)果。

解決緩存一致性問題的方法包括：目錄法、總線法、監(jiān)聽法和寫回法等。目錄法通過維護(hù)一個中央目錄來跟蹤每個緩存行的狀態(tài)；總線法通過在總線上廣播更新信息來保持緩存一致性；監(jiān)聽法通過監(jiān)聽總線上的更新信息來更新本地緩存；寫回法則是在更新數(shù)據(jù)時將數(shù)據(jù)寫回共享存儲器?！窘馕觥烤彺嬉恢滦詥栴}在多處理器系統(tǒng)中是一個重要問題，因?yàn)樗赡軐?dǎo)致數(shù)據(jù)不一致和錯誤的結(jié)果。解決該問題需要使用特定的協(xié)議和機(jī)制來確保緩存中的數(shù)據(jù)保持一致。28.【答案】哈希沖突是指在哈希表中，兩個不同的鍵通過哈希函數(shù)計(jì)算得到相同的哈希值。這會導(dǎo)致在插入數(shù)據(jù)時，原本應(yīng)該存儲在同一個位置的元素被放置在另一個位置，從而影響了哈希表的性能。

解決哈希沖突的方法包括：鏈地址法、開放尋址法和再哈希法等。鏈地址法是在哈希表中為每個哈希值創(chuàng)建一個鏈表，將具有相同哈希值的元素存儲在同一個鏈表中；開放尋址法是通過探測其他位置來找到下一個空閑的槽位；再哈希法是在哈希沖突發(fā)生時，重新計(jì)算鍵的哈希值?！窘馕觥抗_突是哈希表實(shí)現(xiàn)中常見的問題，解決哈希沖突的方法需要考慮效率、空間復(fù)雜度和哈希函數(shù)的質(zhì)量。29.【答案】虛擬內(nèi)存是一種內(nèi)存管理技術(shù)，它允許操作系統(tǒng)使用硬盤空間作為內(nèi)存來擴(kuò)展物理內(nèi)存。虛擬內(nèi)存通過將內(nèi)存劃分為頁面或段，并在需要時將其加載到物理內(nèi)存中，從而實(shí)現(xiàn)內(nèi)存的動態(tài)管理。

虛擬內(nèi)存的作用包括：提供更大的內(nèi)存空間、提高內(nèi)存利用率、簡化內(nèi)存分配和回收過程、保護(hù)內(nèi)存空間等?！窘馕觥刻摂M內(nèi)存是操作系統(tǒng)內(nèi)存管理的重要組成部分，它通過模擬更多的物理內(nèi)存來擴(kuò)