【盛世清北】北大計(jì)算機(jī)科學(xué)與技術(shù)(智能科學(xué)與技術(shù))考研筆記-北大考研輔導(dǎo)培訓(xùn)班

1、盛世清北】北大計(jì)算機(jī)科學(xué)與技術(shù)（智能科學(xué)與技術(shù)）考研筆記 北大考研輔導(dǎo)培訓(xùn)班盛世清北分享: 2020年注定是不平凡的一年，雖然受到疫情的影響，北大考研復(fù)試推遲數(shù)口，但是絲毫不 會(huì)阻止2021屆考生備考 北京大學(xué)考研的決心。俗話說“早起的鳥兒有蟲吃”基礎(chǔ)差的同學(xué)更該要早做準(zhǔn)備，早規(guī)劃。為了幫助考生在北大考研中能成功上岸，盛世 清北整理了北大各專業(yè)相關(guān)復(fù)習(xí)資料。北大計(jì)算機(jī)科學(xué)與技術(shù)（智能科學(xué)與技術(shù)）考研考試科目: 101思想政治理論201英語一301數(shù)學(xué)一801計(jì)算機(jī)專業(yè)基礎(chǔ)北大計(jì)算機(jī)科學(xué)與技術(shù)（智能科學(xué)與技術(shù)）考研參考書:1.數(shù)據(jù)結(jié)構(gòu)與算法，張銘、王騰蛟、趙海燕,2008-06，高等教育出版社，

2、普通高等教育“十一五”國家級(jí)規(guī)劃教材;2.計(jì)算機(jī)組成與設(shè)計(jì)：硬件與軟件接口，David Patterson & John Hennessy 著， 英文版第4版，機(jī)械工業(yè)出版社;3.微型計(jì)算機(jī)基本原理與應(yīng)用，王克義編著，第二版,北京大學(xué)出版社;4.現(xiàn)代操作系統(tǒng)（原書第4版），（荷）Andrews S. Tanenbaum著，陳向群、馬洪兵等譯，機(jī)械工業(yè)出版社,2017-07 ；5.操作系統(tǒng)一精髓與設(shè)計(jì)原理（原書第8版），（美）William Stallings 著，陳向群、陳渝譯，電子工業(yè)出版社，2017-03 ；6.計(jì)算機(jī)網(wǎng)絡(luò)（中英文）第五版，Andrew S. Tanenebaum

3、andDavid J. Wetherall,華出版社,2012-03 。盛世清北建議參考書的閱讀方法:了解書的內(nèi)在邏輯結(jié)構(gòu)，然后再去深入研目錄法：先通讀各本參考書的目錄，對(duì)于知識(shí)體系有著初步了解,讀書的內(nèi)容。體系法：為自己所學(xué)的知識(shí)建立起框架，否則知識(shí)內(nèi)容浩繁，容易遺忘，最好能夠閉上 眼睛的時(shí)候，眼前出現(xiàn)完整的知識(shí)體系。問題法：將自己所學(xué)的知識(shí)總結(jié)成問題寫出來，每章的主標(biāo)題和副標(biāo)題都是很好的出題 素材。盡可能把所有 的知識(shí)要點(diǎn)都能夠整理成問題。北大計(jì)算機(jī)科學(xué)與技術(shù)（智能科學(xué)與技術(shù)）考研真題:北京大學(xué)801計(jì)算機(jī)專業(yè)基礎(chǔ)考研歷年真題：數(shù)據(jù)結(jié)構(gòu):1. 寫出AVL樹并計(jì)算平均查找長度。G盛世清北&#

4、174;2. n個(gè)數(shù)組成二叉樹，證明排序時(shí)間復(fù)雜度為0 (nlogn)(這個(gè)記憶得有點(diǎn)模糊)3. 一個(gè)數(shù)組，有最多X個(gè)極值，設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度盡可能低的算法。、計(jì)算機(jī)體系結(jié)構(gòu)：1 .結(jié)合流程圖闡述乘法器的工作原理，然后對(duì)其改進(jìn)。2 . MIPS指令集計(jì)算機(jī)網(wǎng)絡(luò)：一個(gè)用戶通過交換機(jī)，集線器向另一個(gè)用戶發(fā)送IP報(bào)文，問交換機(jī)的作用，源地址和目的地址。北京大學(xué)801計(jì)算機(jī)基礎(chǔ)2018年研究生入學(xué)試題i.算法復(fù)朵度丈具體 :已知卜血一串代碼.求英算法時(shí)間復(fù)雜度：int s =i = 0; While (Sn) S K i; i+；)V備注；王道2017年真題本質(zhì)是一樣的A、O(N)BX 0 (Na2)

5、C、0(I0gN)D、類似這樣的答案2.線性表龍具體A下面關(guān)于線性表的敘述中，不幣確的是哪些()？A、B、C、D、采用順序存儲(chǔ)的線性表, 采用順序存儲(chǔ)的線性表, 采用鏈接存儲(chǔ)的線性表, 采用鏈慘存儲(chǔ)的緯悴天必須占用一片連續(xù)的存儲(chǔ)單元; 便于進(jìn)行插入和刪除操作.不必占用一片連續(xù)的存儲(chǔ)單兀, 便丁插入和刪除操作；V備注承線性表的荷儲(chǔ)結(jié)構(gòu)鏈接和順序3.棧混洗具體：給了個(gè)字符串HAPPY.按照這個(gè)IW序入棧，則出棧如序不可能依個(gè)()A. HAYPPB. HPPAYC. HYAPAD. HAPPY備注?；煜搭愵}H,群里有具體算法代碼但是一般只考選擇題具體算法思想：采用一個(gè)中間枚水記錄每 段小棧的信息。復(fù)

6、雜JUO (n2)，圖的鄰接矩陣具體：某連通圖的鄰接矩陣為A'若點(diǎn)i到點(diǎn)j存仔一條長麼為m的粘徑那么可以看哪個(gè)矩陣aij是否為1()R mAC. AA1T1D AA(In-I)V備注：5. IMS, BFS,連通圖相關(guān)概念【較一版有更改】 對(duì)于聯(lián)通無向圖.請(qǐng)問以下說法正確的是：G盛世清北®A.廣度優(yōu)先您先進(jìn)后出：B.連通的MST %極大連通于圖C.廣提優(yōu)先搜索是遞歸實(shí)現(xiàn)的：7y每次探哎優(yōu)先搜索都能得到一個(gè)聯(lián)通分支；V具體:6 二叉樹的前，中，后遍歷相關(guān)類型題V具體；葉節(jié)點(diǎn)相對(duì)順序前中后序遍歷是否一樣()A.完全一樣B. 完全不一樣C. 前序和后序一樣D前沖和中樣一樣7. 森林

7、.二叉樹轉(zhuǎn)換V具體若森林F對(duì)應(yīng)的一叉樹R中有m個(gè)點(diǎn).R的根節(jié)點(diǎn)r的右子樹同rfn個(gè)節(jié)點(diǎn)那么 徐林F中第I顆樹的結(jié)點(diǎn) 個(gè)數(shù)為：As m-n B、m-n-l C、nr 1 D、不確ifilV缶江；不難，宴砒題&散列農(nóng)，二次黃找法V具體:希值為ke哈希農(nóng)K 14線性衷插入到15, 38, 61. 84, 8,最后播入49.那么利用二次探測(cè)法.49應(yīng)該放在下標(biāo)為多少的表頂中？A. 3B. 5C. 8D. 99. b樹與b+樹V其體RB+樹不同B樹的待.點(diǎn)之一是A、B樹和B+樹都是AVL枸R、R樹和R+材都能用丁文件系統(tǒng)C、B樹和B+樹都日勺效支持順斤介找D、B樹和B+樹都有效支持隨機(jī)進(jìn)找V備江

8、： b樹和樹是否支持馳機(jī)責(zé)找和順序查找10. V具體A針對(duì)以下無向連通圖從點(diǎn)I開始，使用Dijkstra Sr法尋找單源最短路徑.依次加入的點(diǎn)是()A. ?B 1> 2、 4、 3、 7. 5、 balabciluD. ?備注iA給了個(gè)圖，止給出根島算法所得到的次序土逍上血許多題F1類似11.歸并段、創(chuàng)路歸并，WPL具體、：若初始?xì)w并及大小分別為，5 9 12 13 14 16 17 18 20 28 30 37 42,那么垠佳|并樹的帶權(quán)路徑長度WPL 是()A. 46()B. 472C. 480D. 486二簡存題(弟一題6分，第二題8分，第三題9分)：K 一顆空AVL樹中.H頁序插

9、入(5942 I 38 | ；(1)、嚴(yán)格遵循AVL操作，畫出播入后的AVLW (畫出每一步；(2)、全祁插入后，求等概率下的查找成功的T均檢索長質(zhì)。2、 二義樹的內(nèi)部埒徑長度：假設(shè)N個(gè)互不柑同的隨機(jī)元素插入棵空一又搜索樹明得到的一又搜索樹的內(nèi)部路徑長 喪期墊為0( NIOgN > 03、 恰定個(gè)長提為N的數(shù)組，保i正其中至多存在C個(gè)極值點(diǎn)Qi為極值點(diǎn)，則滿址IViVMili-1 <iiiI&&QEE)或者(ai-Dai)&A (aiai*l) . C可以看做個(gè)常數(shù)請(qǐng)?jiān)O(shè)計(jì)個(gè)時(shí)間復(fù)余喪盡可能低的算 法對(duì)N排序計(jì)算機(jī)組成原理、選擇題(1 11題為單選題，每小題2

10、分)1.繪出-串16誑制數(shù)()X | 234567X9()河用大端法和小瑞法存分別堤名少？A小端從覽址小爻且大12 3456 78 90從地址小到人大端90 78 56 34 12G盛世清北®B. ?67 9 >D. ?2. 3. 14的16進(jìn)制數(shù)是XXXX,問它的階碼用二進(jìn)制表示是莖少？A. ?Ble)OO(X) 00C. ?D. ?3問下列兒個(gè)哪個(gè)不是的諾依曼結(jié)構(gòu)的基礎(chǔ)部件？A. CPU D.內(nèi)存C碩盤D.打印機(jī)問主頻為多少?4,實(shí)Jur 5級(jí)流水線.每個(gè)階段的運(yùn)行時(shí)長為如(3ms 5ms 2ms 6ms 4ms ), A . I66MHZB. 248MHZC. 333MH

11、zD. ?G盛世清北®5 .行波進(jìn)位和超前進(jìn)位的概念題V 題考慮到電路的負(fù)雜性與延遲-ALU的加法器實(shí)現(xiàn)通常是山:A.務(wù)個(gè)小規(guī)模超前進(jìn)位加法器耕接而成B.多個(gè)小規(guī)模超前進(jìn)位J川法器和行波進(jìn)位加法器級(jí)聯(lián)而成C.大規(guī)模行波進(jìn)位加法器組成D.大規(guī)模超前進(jìn)位加法器組成6 程序金詢、中斷、DMA三種方式的概念題？下列關(guān)于程序查詢、中以DMA的三種方說法正確的是A. DMA對(duì)外部輸入輸出的響應(yīng)實(shí)時(shí)性最高；B.中斷仍需要經(jīng)過CPU寄存器傳輸數(shù)據(jù)C.除程序代詢方式外，中斷和DMA都不再需耍編寫程序執(zhí)行D. DMA總是性能最高7 .中斷向量表存儲(chǔ)的是？A.中斷服務(wù)程序的入II地址8 .中斷號(hào)?？C.中

12、斷狀態(tài)字8.路組相聯(lián)的一個(gè)計(jì)哪真題G i chc采用4路 組相聯(lián) 每塊32B 16組（編號(hào)0-15） , iW OXDEADBEEF映射到 哪一組？A. set7B. SetllC. sc i 13D - set 159.流木1紐的柑關(guān)晚念題裕）Htfn關(guān)于流水線說法iF瀟的是（）A.通過不斷加深流水線的級(jí)數(shù)，流水線的效率可以不斷捉高B.泳水段的平均延遲彤響了流水線的最高頻率？C沆水線中的呂險(xiǎn)都HJ以通過推入流水線停頓來解決D. ?10.磁盤的轉(zhuǎn)速為7200RPM,尋道時(shí)間為9nls每個(gè)碓道有400個(gè)扇區(qū)，數(shù)Ie分布均勻，問讀 奴一個(gè)扇區(qū)的平均時(shí)仙（）A. 4.70mSB. 9.20msC.

13、7.56TTiSD. 5.74msI I .X干硬布線控制岳和微指令控制器的對(duì)比，下列說法正確的是（）A.頷指令控制器執(zhí)行效率更高B.硬布線控制器電路組織更簡單C.諛布線扯制器指令執(zhí)彳亍效率更高D脫侑線易于擴(kuò)展和修改功能一、解答題（第一制9分.第一球14分）1.（1給出了個(gè)木比化的乘濃貉的線跑圖，訛描述乘法器的運(yùn)行步驟.訥用流程圖和文字描述掛T作過程:（2）該乘法器還可以代化.請(qǐng)畫出比化心的乘達(dá)器的線賂圖，并描述做了嗡些優(yōu)化。Multiplicand 岡儂10 0 0 x 1 0 0 1twotwo,J-V8-bit Adder8-bitProductSMnghtMultiplier8-btt

14、2- (I) 將 MIPS 令集精簡為 MIPSse 指令集包括 ADDU. SUBIE ORL LW. SW. BEQoCPu數(shù)據(jù)通路圖如下：Instruction Fetch Unit dk-> KU)Instruction Wordrd rtbusW&J2AdrData ln:cbusBK.iiRw Ra RbRegFile 327*32Clkl rMemmRegr°Datadk > MemoryfuncOPCOdO(OP)100000IOOoIO/000000000000001I0I10001II0I011OOoIOOadduSUbUOriIWSWbeqR

15、egDSt10XALUSrC11MemtOReg001XRegWr1MeJeWr0nPC SQI0000EXtOPX1ALUCtr<l:0>00(ADD)01 (SUB)10 (OR)(2)、分析指令需求以集成控制信號(hào).沽境寫下列農(nóng)格。(3)若將加上單用期處理器改造成為旅水線處理器，ID6- /i個(gè)渝水段F (tR值)、DG盛世清北®（譯碼）、E （執(zhí)行）、M （訪存）、W （寫回），那么流水線會(huì)產(chǎn)生哪些冒險(xiǎn)？舉例說明針對(duì)以卜,冒險(xiǎn),若?；魉€，應(yīng)該增加什么劑件或者怎樣修改祁件，諸用文寧t魁.操作系統(tǒng)一、選擇題VI-9為單選題，每題2分）I.楓擁操作系統(tǒng)進(jìn)程狀態(tài)圖（圖

16、*）判斷進(jìn)秤狀態(tài)哪個(gè)對(duì)?A. 1-創(chuàng)建態(tài)B 2 新建C. 3 就緒D. 4-陰塞V備注：原題就是把里面查個(gè)狀態(tài)換成I, 2. 3, 4. 5 讓你猜里面的哪一個(gè)是正確的2 .問什么時(shí)候不一定會(huì)發(fā)牛進(jìn)程切換？A.進(jìn)程時(shí)間片用完B.當(dāng)進(jìn)程創(chuàng)建了一個(gè)子進(jìn)程之后C.進(jìn)廳讀盤操作D.進(jìn)程運(yùn)行過程中產(chǎn)牛了異常3 .安全狀態(tài)和死鎖的關(guān)系？V模擬題類似題：關(guān)于死鎖狀態(tài)與不安全狀態(tài)的關(guān)系，下列描述正確的有：（）A.死鎖是一種不安全狀態(tài)B.系統(tǒng)處T不安傘狀態(tài)，一定產(chǎn)牛了死鋰C.不安金狀態(tài)是死鎖的必要條件D不安余狀態(tài)是死鎖的充分條件4.使用LRU,問哪個(gè)被換出？ V給了-,個(gè)表格以及一些參數(shù)題H給出了頁號(hào)，頁框號(hào)，

17、修 改位，訪問位，T時(shí)間內(nèi)訪問的次數(shù)G盛世清北®A. ?B. ?D. ? ?5.給了信號(hào)垃的定義.問N個(gè)進(jìn)程競爭一個(gè)資源.需要幾個(gè)信號(hào)垃？ 給出P (S) VS)的實(shí)現(xiàn)代碼A. IB. NC N 1I) . N+1I.給淀頁表大小為512寧.抬令療了 2頁，藪據(jù)存1頁，然后怡了一段程序更初始化一個(gè)1024* 1024的矩陣，問 缺貝婁少次？(其中數(shù)組A1 1024 | | 1024 |為IMERGER類里貝農(nóng)人小為512字,Ai. JI-0)A. 1024* 1024B. 1024*512C. 1024D. 1024*26.關(guān)T FAT文件系統(tǒng)下列說區(qū)不正確的址()A. FAT文件系

18、統(tǒng)文件名區(qū)分大小寫B(tài).卜AT文件系統(tǒng)文件的物理結(jié)構(gòu)於鏈?zhǔn)鼋伩桟. FAT文件系統(tǒng)為了提島效率.采用了1錄頂分解的方法D. ? ?H問下列哪些操作不是為了提升文件系統(tǒng)性能R錄項(xiàng)分解等)？A 目錄項(xiàng)分解B.文件高速緩存C-廄盤調(diào)IsiSliiD.異步I/O9.下列關(guān)于死鎖的選項(xiàng)哪一個(gè)是不正確的()A、安全狀態(tài)一定不會(huì)發(fā)牛死鎖；B、不安全狀態(tài)一定會(huì)發(fā)生死鎖；C、不安全狀態(tài)就是死鎖D、? ?V模擬題：下列關(guān)r死鎖與安全狀態(tài)的敘述中W系一個(gè)是止確的？A.死鎖狀態(tài)-淀是不安全狀態(tài)B.從安全狀態(tài)有可能進(jìn)入死鎖狀態(tài)C.不安全狀態(tài)就是死鎖狀態(tài)D.死鎖狀態(tài)有可能是安全狀態(tài)G盛世清北®二、解答題（第一題1

19、0分，第二題5分1 .操作系統(tǒng)實(shí)現(xiàn)了 20條系統(tǒng)涮用，現(xiàn)在耍添加個(gè)名為Syai121的系統(tǒng)調(diào)用，有3個(gè)參數(shù)輸入.問：（1）、雁實(shí)現(xiàn)這個(gè)函數(shù)碩件需藍(lán)支持什久功能？（2）、問操作系統(tǒng)需耍做什么操作？（3）、編訐容浙耍捏供什么樣的支持？V備注：跟17年的題答差不名2 、 IA寫出第級(jí)反俺從列的訊理.井簡述如何它是如何進(jìn)行渭度的，詳細(xì)論述如何對(duì)待CPU密集型進(jìn)陽/和I/O 帝集型進(jìn)程備注：往年考的是PV操作，現(xiàn)在變成了多級(jí)反饋隊(duì)列的處理，進(jìn)程調(diào)度計(jì)算機(jī)網(wǎng)絡(luò)一.選擇題（1-91以為單選題，每題2分）1. V宜題）下列選項(xiàng)正確的能：（）A.頻分多用每個(gè)用戶可以直蟲用全部信道帶寬；B.時(shí)分多用程個(gè)用戶可以一

20、直占用全部倍適簾寬；C.碼分名目每個(gè)用八可以一自人用全部佑逍帶:找D.碼分多用每個(gè)用戶不可以直占用全部信道帶寬；2. （2道）關(guān)于報(bào)文交換和電路交換下列說法正確的是？A.報(bào)文交換的轉(zhuǎn)發(fā)速度?？於‰娐方粨QB.電路交換的轉(zhuǎn)發(fā)速度?？於?bào)文交換C.當(dāng)數(shù)據(jù)經(jīng)過交檢機(jī)時(shí)，報(bào)文交換冢要將數(shù)抵存儲(chǔ)然后轉(zhuǎn)發(fā)D.當(dāng)數(shù)據(jù)經(jīng)過交換機(jī)時(shí)，電路交換需要將數(shù)據(jù)存儲(chǔ)然后轉(zhuǎn)發(fā)3. 8023協(xié)議概念題（如是否可集）真題 以下 r 802.3協(xié)議的正確選項(xiàng)是（）A. 802. 3為上層提供了可靠的數(shù)呃服務(wù)B. 802.3為上層捉供了不可靠的數(shù)堀服務(wù)C ? 9D. ? ?4 - 802.11協(xié)議概念題（如是否町蹴 是不是解決了隱蔽

21、站問題）？V真題A下列關(guān)于802,11協(xié)議選項(xiàng)正確的是（）A. 802.11提供可靠的單播數(shù)據(jù)服務(wù)B. 802J I%共不可靠的多播數(shù)據(jù)服務(wù)C. 802. 1 I能解決暴節(jié)點(diǎn)問題G盛世清北®D. 802.11不能解決隱藏結(jié)點(diǎn)問題5. IP協(xié)議、UDP協(xié)議.TCP協(xié)議概念題丈真題下列關(guān)于UDP協(xié)議說沫正確的是（）A. UDP為應(yīng)用層桃供了不可靠的數(shù)據(jù)報(bào)服務(wù)B. UDP為提供面向連接的服務(wù)C. UDP向應(yīng)用層提供無連接的服務(wù)D.UDP為應(yīng)用層捉供了可靠的數(shù)掘報(bào)服務(wù)6 .數(shù)期校驗(yàn)的問趣（如問發(fā)送力和接收方是不是用不同的計(jì)算公式等）？真題以下關(guān)于數(shù)據(jù)校駿的選頂正確的是0:A.發(fā)送方和接收方計(jì)算校駿和的公式不同B.編碼效率與校驗(yàn)位數(shù)無關(guān)C.接收方能用校驗(yàn)碼