浙江大學(xué)課程計(jì)算機(jī)科學(xué)試卷考試時(shí)長(zhǎng)：120分鐘滿分：100分班級(jí)：__________姓名：__________學(xué)號(hào)：__________得分：__________浙江大學(xué)課程計(jì)算機(jī)科學(xué)試卷考核對(duì)象：計(jì)算機(jī)科學(xué)專業(yè)本科二年級(jí)學(xué)生題型分值分布：-判斷題（10題，每題2分）——20分-單選題（10題，每題2分）——20分-多選題（10題，每題2分）——20分-案例分析（3題，每題6分）——18分-論述題（2題，每題11分）——22分總分：100分---一、判斷題（每題2分，共20分）1.數(shù)據(jù)結(jié)構(gòu)中的“堆”是一種非線性結(jié)構(gòu)。2.快速排序在最壞情況下的時(shí)間復(fù)雜度是O(n2)。3.在二叉搜索樹(shù)中，任意節(jié)點(diǎn)的左子樹(shù)只包含小于該節(jié)點(diǎn)的值，右子樹(shù)只包含大于該節(jié)點(diǎn)的值。4.動(dòng)態(tài)規(guī)劃適用于解決具有重疊子問(wèn)題和最優(yōu)子結(jié)構(gòu)的問(wèn)題。5.并發(fā)控制中的“鎖”是一種用于實(shí)現(xiàn)線程同步的機(jī)制。6.圖的廣度優(yōu)先搜索（BFS）使用隊(duì)列實(shí)現(xiàn)，深度優(yōu)先搜索（DFS）使用棧實(shí)現(xiàn)。7.哈希表的時(shí)間復(fù)雜度在平均情況下為O(1)。8.遞歸算法一定比迭代算法效率更高。9.TCP協(xié)議是一種面向連接的、可靠的傳輸層協(xié)議。10.在面向?qū)ο缶幊讨?，繼承和多態(tài)是兩個(gè)核心概念。二、單選題（每題2分，共20分）1.下列數(shù)據(jù)結(jié)構(gòu)中，最適合實(shí)現(xiàn)棧的是（）。A.鏈表B.數(shù)組C.隊(duì)列D.堆2.快速排序的平均時(shí)間復(fù)雜度是（）。A.O(n2)B.O(nlogn)C.O(n3)D.O(logn)3.在二叉搜索樹(shù)中，查找一個(gè)元素的最壞情況時(shí)間復(fù)雜度是（）。A.O(1)B.O(logn)C.O(n)D.O(n2)4.動(dòng)態(tài)規(guī)劃與分治法的區(qū)別在于（）。A.動(dòng)態(tài)規(guī)劃適用于遞歸，分治法適用于迭代B.動(dòng)態(tài)規(guī)劃解決重疊子問(wèn)題，分治法不解決C.動(dòng)態(tài)規(guī)劃適用于無(wú)序數(shù)據(jù)，分治法適用于有序數(shù)據(jù)D.動(dòng)態(tài)規(guī)劃不需要存儲(chǔ)中間結(jié)果，分治法需要5.以下哪種同步機(jī)制可能導(dǎo)致死鎖？（）A.信號(hào)量B.互斥鎖C.讀寫(xiě)鎖D.樂(lè)觀鎖6.圖的鄰接矩陣表示法適用于（）。A.稀疏圖B.稠密圖C.無(wú)向圖D.有向圖7.哈希表沖突解決方法中，鏈地址法的時(shí)間復(fù)雜度是（）。A.O(1)B.O(logn)C.O(n)D.O(n2)8.遞歸算法的核心是（）。A.隊(duì)列B.棧C.堆D.哈希表9.TCP協(xié)議與UDP協(xié)議的主要區(qū)別在于（）。A.TCP面向連接，UDP無(wú)連接B.TCP傳輸速度快，UDP傳輸慢C.TCP適用于實(shí)時(shí)應(yīng)用，UDP適用于非實(shí)時(shí)應(yīng)用D.TCP安全性高，UDP安全性低10.在面向?qū)ο缶幊讨?，封裝的目的是（）。A.提高代碼可讀性B.隱藏內(nèi)部實(shí)現(xiàn)細(xì)節(jié)C.增強(qiáng)代碼可維護(hù)性D.以上都是三、多選題（每題2分，共20分）1.以下哪些屬于非線性數(shù)據(jù)結(jié)構(gòu)？（）A.棧B.隊(duì)列C.鏈表D.圖E.樹(shù)2.快速排序的優(yōu)化方法包括（）。A.隨機(jī)選擇樞軸B.三數(shù)取中法C.尾遞歸優(yōu)化D.使用鏈表代替數(shù)組E.分塊排序3.二叉搜索樹(shù)的性質(zhì)包括（）。A.左子樹(shù)所有節(jié)點(diǎn)小于根節(jié)點(diǎn)B.右子樹(shù)所有節(jié)點(diǎn)大于根節(jié)點(diǎn)C.左右子樹(shù)都是二叉搜索樹(shù)D.根節(jié)點(diǎn)可以有任意值E.左右子樹(shù)的高度差不超過(guò)14.動(dòng)態(tài)規(guī)劃的基本要素包括（）。A.子問(wèn)題定義B.狀態(tài)轉(zhuǎn)移方程C.邊界條件D.遞歸實(shí)現(xiàn)E.優(yōu)化存儲(chǔ)空間5.并發(fā)控制機(jī)制包括（）。A.互斥鎖B.信號(hào)量C.讀寫(xiě)鎖D.樂(lè)觀鎖E.可重入鎖6.圖的表示方法包括（）。A.鄰接矩陣B.鄰接表C.邊集數(shù)組D.堆E.哈希表7.哈希表沖突解決方法包括（）。A.鏈地址法B.開(kāi)放地址法C.雙哈希法D.負(fù)載因子調(diào)整E.哈希函數(shù)優(yōu)化8.遞歸算法的優(yōu)缺點(diǎn)包括（）。A.代碼簡(jiǎn)潔B.易于理解C.可能導(dǎo)致棧溢出D.重復(fù)計(jì)算子問(wèn)題E.時(shí)間復(fù)雜度較高9.TCP協(xié)議的特性包括（）。A.面向連接B.可靠傳輸C.全雙工通信D.流量控制E.頭部固定長(zhǎng)度10.面向?qū)ο缶幊痰暮诵母拍畎ǎǎ?。A.封裝B.繼承C.多態(tài)D.抽象E.泛型四、案例分析（每題6分，共18分）1.問(wèn)題描述：某公司需要設(shè)計(jì)一個(gè)任務(wù)調(diào)度系統(tǒng)，任務(wù)以優(yōu)先級(jí)隊(duì)列的形式存儲(chǔ)，高優(yōu)先級(jí)任務(wù)優(yōu)先執(zhí)行。請(qǐng)回答以下問(wèn)題：（1）若使用最小堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列，插入和刪除操作的時(shí)間復(fù)雜度分別是多少？（2）若改為使用最大堆，如何保證高優(yōu)先級(jí)任務(wù)先執(zhí)行？（3）比較兩種實(shí)現(xiàn)方式的時(shí)間復(fù)雜度優(yōu)劣。2.問(wèn)題描述：某社交平臺(tái)需要設(shè)計(jì)一個(gè)用戶關(guān)系圖，節(jié)點(diǎn)表示用戶，邊表示關(guān)注關(guān)系。請(qǐng)回答以下問(wèn)題：（1）若使用鄰接表表示該圖，如何高效判斷用戶A是否關(guān)注用戶B？（2）若需要找出用戶A的所有好友（直接鄰居），時(shí)間復(fù)雜度是多少？（3）若該圖包含環(huán)，如何避免在BFS或DFS中無(wú)限循環(huán)？3.問(wèn)題描述：某電商系統(tǒng)需要設(shè)計(jì)一個(gè)商品庫(kù)存管理系統(tǒng)，使用哈希表存儲(chǔ)商品ID與庫(kù)存數(shù)量。請(qǐng)回答以下問(wèn)題：（1）若使用鏈地址法解決沖突，插入一個(gè)新商品的時(shí)間復(fù)雜度是多少？（2）若哈希表負(fù)載因子為0.7，刪除一個(gè)商品可能導(dǎo)致哪些問(wèn)題？（3）如何優(yōu)化哈希函數(shù)以減少?zèng)_突？五、論述題（每題11分，共22分）1.論述題：請(qǐng)論述動(dòng)態(tài)規(guī)劃與分治法的區(qū)別與聯(lián)系，并舉例說(shuō)明動(dòng)態(tài)規(guī)劃適用于哪些問(wèn)題。2.論述題：請(qǐng)論述TCP協(xié)議如何實(shí)現(xiàn)可靠傳輸，并分析TCP協(xié)議在實(shí)時(shí)應(yīng)用中的局限性。---標(biāo)準(zhǔn)答案及解析一、判斷題1.×（堆是線性結(jié)構(gòu)，但具有堆性質(zhì)）2.√3.√4.√5.√6.√7.√8.×（遞歸可能導(dǎo)致重復(fù)計(jì)算，不一定比迭代效率高）9.√10.√二、單選題1.B2.B3.C4.B5.A6.B7.C8.B9.A10.D三、多選題1.D,E2.A,B,C3.A,B,C4.A,B,C,E5.A,B,C,D6.A,B,C7.A,B,C8.A,B,C,E9.A,B,C,D10.A,B,C,D四、案例分析1.答案：（1）最小堆插入時(shí)間復(fù)雜度O(logn)，刪除時(shí)間復(fù)雜度O(1)。（2）使用最大堆時(shí)，高優(yōu)先級(jí)任務(wù)位于堆頂，直接執(zhí)行即可。（3）最小堆插入較慢但刪除快，最大堆相反。實(shí)際選擇需根據(jù)使用場(chǎng)景權(quán)衡。2.答案：（1）鄰接表通過(guò)用戶A的鏈表查找用戶B，時(shí)間復(fù)雜度O(degree(A))。（2）遍歷用戶A的鏈表，時(shí)間復(fù)雜度O(degree(A))。（3）BFS/DFS需標(biāo)記已訪問(wèn)節(jié)點(diǎn)，避免重復(fù)訪問(wèn)。3.答案：（1）鏈地址法插入時(shí)間復(fù)雜度O(1)（平均），O(n)（最壞）。（2）刪除可能導(dǎo)致沖突鏈斷裂，需重新哈希。