09-20計(jì)算機(jī)統(tǒng)考真題與解析

1、09-20 年408 真題與解析 前 言.1 擇校相關(guān).2 40偷雞法.3 2021 計(jì)算機(jī)統(tǒng)40考研大綱變動(dòng)與解析.4 40考研大綱-數(shù)據(jù)結(jié)構(gòu) .7 40考研大綱-計(jì)算機(jī)組成原理 .10 40考研大綱-操作系統(tǒng) .14 40考研大綱-計(jì)算機(jī)網(wǎng)絡(luò) .18 09-20年408真題與解析-數(shù)據(jù)結(jié)構(gòu)部分.23 2020 年統(tǒng)考408 真題-數(shù)據(jù)結(jié)構(gòu)部分 .25 2019 年統(tǒng)考408 真題-數(shù)據(jù)結(jié)構(gòu)部分 .33 2018 年統(tǒng)考408 真題-數(shù)據(jù)結(jié)構(gòu)部分 .37 2017 年統(tǒng)考408 真題-數(shù)據(jù)結(jié)構(gòu)部分 .41 2016 年統(tǒng)考408 真題-數(shù)據(jù)結(jié)構(gòu)部分 .46 2015 年統(tǒng)考408 真題-數(shù)據(jù)

2、結(jié)構(gòu)部分 .51 2014 年統(tǒng)考408 真題-數(shù)據(jù)結(jié)構(gòu)部分 .56 2013 年統(tǒng)考408 真題-數(shù)據(jù)結(jié)構(gòu)部分 .59 2012 年統(tǒng)考408 真題-數(shù)據(jù)結(jié)構(gòu)部分 .65 2011 年統(tǒng)考408 真題-數(shù)據(jù)結(jié)構(gòu)部分 .70 2010 年統(tǒng)考408 真題-數(shù)據(jù)結(jié)構(gòu)部分 .74 2009 年統(tǒng)考408 真題-數(shù)據(jù)結(jié)構(gòu)部分 .78 09-20年408真題與解析-計(jì)算機(jī)組成原理部分 .82 2020 年統(tǒng)考408 真題-組成原理部分 .85 2019 年統(tǒng)考408 真題-組成原理部分 .89 2018 年統(tǒng)考408 真題-組成原理部分 .94 2017 年統(tǒng)考408 真題-組成原理部分 .100 2

3、016 年統(tǒng)考408 真題-組成原理部分 .106 2015 年統(tǒng)考408 真題-組成原理部分 .111 2014 年統(tǒng)考408 真題-組成原理部分 .116 2013 年統(tǒng)考408 真題-組成原理部分 .121 2012 年統(tǒng)考408 真題-組成原理部分 .125 2011 年統(tǒng)考408 真題-組成原理部分 .131 2010 年統(tǒng)考408 真題-組成原理部分 .135 2009 年統(tǒng)考408 真題-組成原理部分 .141 09-20年408真題與解析-操作系統(tǒng)部分.146 2020 年統(tǒng)考408 真題-操作系統(tǒng)部分 .148 2019 年統(tǒng)考408 真題-操作系統(tǒng)部分 .152 2018

4、年統(tǒng)考408 真題-操作系統(tǒng)部分 .155 2017 年統(tǒng)考408 真題-操作系統(tǒng)部分 .159 2016 年統(tǒng)考408 真題-操作系統(tǒng)部分 .165 2015 年統(tǒng)考408 真題-操作系統(tǒng)部分 .169 2014 年統(tǒng)考408 真題-操作系統(tǒng)部分 .172 ii 09-20 年408 真題與解析 2013 年統(tǒng)考408 真題-操作系統(tǒng)部分 .176 2012 年統(tǒng)考408 真題-操作系統(tǒng)部分 .181 2011 年統(tǒng)考408 真題-操作系統(tǒng)部分 .184 2010 年統(tǒng)考408 真題-操作系統(tǒng)部分 .188 2009 年統(tǒng)考408 真題-操作系統(tǒng)部分 .192 09-20年408真題與解析-

5、計(jì)算機(jī)網(wǎng)絡(luò)部分.196 2020 年統(tǒng)考408 真題-計(jì)算機(jī)網(wǎng)絡(luò)部分.198 2019 年統(tǒng)考408 真題-計(jì)算機(jī)網(wǎng)絡(luò)部分.203 2018 年統(tǒng)考408 真題-計(jì)算機(jī)網(wǎng)絡(luò)部分.205 2017 年統(tǒng)考408 真題-計(jì)算機(jī)網(wǎng)絡(luò)部分.208 2016 年統(tǒng)考408 真題-計(jì)算機(jī)網(wǎng)絡(luò)部分.211 2015 年統(tǒng)考408 真題-計(jì)算機(jī)網(wǎng)絡(luò)部分.214 2014 年統(tǒng)考408 真題-計(jì)算機(jī)網(wǎng)絡(luò)部分.217 2013 年統(tǒng)考408 真題-計(jì)算機(jī)網(wǎng)絡(luò)部分.223 2012 年統(tǒng)考408 真題-計(jì)算機(jī)網(wǎng)絡(luò)部分.227 2011 年統(tǒng)考408 真題-計(jì)算機(jī)網(wǎng)絡(luò)部分.231 2010 年統(tǒng)考408 真題-計(jì)算機(jī)

6、網(wǎng)絡(luò)部分.235 2009 年統(tǒng)考408 真題-計(jì)算機(jī)網(wǎng)絡(luò)部分.239 2021年408計(jì)算機(jī)統(tǒng)考沖沖模擬卷.243 2021年408計(jì)算機(jī)統(tǒng)考沖沖模擬卷-卷一.243 2021年408計(jì)算機(jī)統(tǒng)考沖沖模擬卷-卷一答案.254 2021年408計(jì)算機(jī)統(tǒng)考沖沖模擬卷-卷二.267 2021年408計(jì)算機(jī)統(tǒng)考沖沖模擬卷-卷二答案.279 iii 09-20 年408 真題與解析 前 言 灰灰考研視頻課程包含： -專業(yè)課基礎(chǔ)班/強(qiáng)化班 -復(fù)試機(jī)試班 -408 真題解析 09-20 年408 真題與解析 擇校相關(guān) 考試科目匯總【注意年份】 HYPERLINK /s?_biz=MzUyMzc3NzI2Nw

7、=&mid=2247496756&idx=3&sn=dacb2bb27b12f1a76b9819b208e470b4&chksm=fa35d1a8cd4258bed604e4131f6a59e42006fa33c03dc132390c0ebf63c6dc7746e48bff3409&scene=21#wechat_redirect 20年考一門專業(yè)課985匯總 HYPERLINK /s?_biz=MzUyMzc3NzI2Nw=&mid=2247496756&idx=4&sn=913540c106c84bcb236f57c71580f85b&chksm=fa35d1a8cd4258bee43ba

8、71db7776c727a00164863a31c1b8d4fd16e242f815b25f709d070f4&scene=21#wechat_redirect 20年考兩門專業(yè)課985匯總 HYPERLINK /s?_biz=MzUyMzc3NzI2Nw=&mid=2247496814&idx=2&sn=f670b1941cc7f5b3c529df75b0a194ee&chksm=fa35d1f2cd4258e4a5238e5fbf651867e5c0bcf2f7917400cd5dd5223c3ec2739ec47c5e7574&scene=21#wechat_redirect 20年考三

9、門專業(yè)課985匯總 HYPERLINK /s?_biz=MzUyMzc3NzI2Nw=&mid=2247496814&idx=3&sn=cca05e0f0e13fa737eea7a6220e9cdc0&chksm=fa35d1f2cd4258e4884adbd651c2f8a59c3b5eed0b2e66cd75f279bad60cca5e727b79b1a493&scene=21#wechat_redirect 20年考四門專業(yè)課985匯總 HYPERLINK /s?_biz=MzUyMzc3NzI2Nw=&mid=2247496756&idx=5&sn=9ae6fed432de262f48

10、f41ede91ad7073&chksm=fa35d1a8cd4258be11cfd7790b1e6d34a405cf219ec6a0e2b59d625cd3f489dd2abfa61b49c3&scene=21#wechat_redirect 20年408985匯總 HYPERLINK /s?_biz=MzUyMzc3NzI2Nw=&mid=2247496836&idx=1&sn=b319bdfef8a54f761905b5d04ad27c3f&chksm=fa35d118cd42580e9b787606f60d9d338e3d6312d0ee2f6dd82c45fbbb6f07fc46eb

11、6fdf495c&scene=21#wechat_redirect 20年考一門專業(yè)課211匯總 HYPERLINK /s?_biz=MzUyMzc3NzI2Nw=&mid=2247496838&idx=2&sn=a19db93b98fb428af2be7a49d23e2a95&chksm=fa35d11acd42580c178113293800d88a96fd1770694a1f82720041b7f64394ab207129b6c37d&scene=21#wechat_redirect 20年考兩門專業(yè)課211匯總 HYPERLINK /s?_biz=MzUyMzc3NzI2Nw=&mid

12、=2247496838&idx=3&sn=2f2f717f14497eab5e7c70cf833d67cf&chksm=fa35d11acd42580c807dc07aabf1de06a958ced88c84b60dc2e9f966caff4a14808d5ecd219b&scene=21#wechat_redirect 20年考三門專業(yè)課211匯總 HYPERLINK /s?_biz=MzUyMzc3NzI2Nw=&mid=2247496838&idx=4&sn=a128d40fd19d557e8b921b15d88b327a&chksm=fa35d11acd42580c9216627b98

13、d6893914ac8f9ce6221d3a97eb21c37044ed339f60eb107a3e&scene=21#wechat_redirect 20年考四門專業(yè)課211匯總 HYPERLINK /s?_biz=MzUyMzc3NzI2Nw=&mid=2247496836&idx=3&sn=4c0b986a9f0689ac35a5356df90d6c62&chksm=fa35d118cd42580e60b517b236dba2d52d49b20e2327d591c3e8efdb52c7558df016a7749b23&scene=21#wechat_redirect 20年408211匯

14、總 HYPERLINK /s?_biz=MzUyMzc3NzI2Nw=&mid=2247496836&idx=4&sn=af548f4cad32cba098195819d9705906&chksm=fa35d118cd42580ec0b7bed1e1cbf3a6c517a33fca7ea1c9823e82bb7514113dedaa7dbbec01&scene=21#wechat_redirect 20只考數(shù)據(jù)結(jié)構(gòu)211院校匯總 HYPERLINK /s?_biz=MzUyMzc3NzI2Nw=&mid=2247496709&idx=1&sn=5352d8e05a9c4eee01ed90c0b

15、9603ae4&chksm=fa35d199cd42588fe3183a6bf62dc3ab605bed93b515a7e13ef0e498382b847e31ea766330bc&scene=21#wechat_redirect 【20擇?！咳珖?guó)985/211計(jì)算機(jī)考研專業(yè)目錄、招生人數(shù) HYPERLINK /s?_biz=MzUyMzc3NzI2Nw=&mid=2247502497&idx=8&sn=4ace5102307a722a71728a1dc942c1db&chksm=fa35ef3dcd42662b3889a5e5fd9c14cf81b30783711899e1fbedda9c8

16、ffee8dd89877f5360c8&scene=21#wechat_redirect 【20考研】那些考408的學(xué)校都怎么樣了？ HYPERLINK /s?_biz=MzUyMzc3NzI2Nw=&mid=2247504033&idx=1&sn=84fbb4373c4340096fe0f432bf0dbeb1&chksm=fa35f53dcd427c2b5ac66429fa99c1cfeebe7690c6e7a51304ab7b0c39e716e9a9d6f0e82661&scene=21#wechat_redirect 【20考研】39所985計(jì)算機(jī)錄取情況詳解（上） HYPERLINK

17、 /s?_biz=MzUyMzc3NzI2Nw=&mid=2247504051&idx=1&sn=b3a4c4d23f9ce2e3587cfaf1ee984d65&chksm=fa35f52fcd427c39164f5684a419a8fd3f8fbae3a72aca87b51d2603833c0082e131c2a1117c&scene=21#wechat_redirect 【20考研】39所985計(jì)算機(jī)錄取情況詳解（下） HYPERLINK /s?_biz=MzUyMzc3NzI2Nw=&mid=2247504080&idx=1&sn=5a95dc7db80ab3ca343adde489b

18、ccf02&chksm=fa35f54ccd427c5a3110e773fcabb1ac56df430c79874ae123b1be3083184194f45fe022e19c&scene=21#wechat_redirect 【20考研】全國(guó)211計(jì)算機(jī)錄取情況詳解（上） HYPERLINK /s?_biz=MzUyMzc3NzI2Nw=&mid=2247504138&idx=1&sn=25d4c227a957a49bb74a46abadb7547c&chksm=fa35f496cd427d80e4bbccadb3a50a7af5ffcb64f7c76bcc1d9ca908bca401744

19、d821de813c3&scene=21#wechat_redirect 【20考研】全國(guó)211計(jì)算機(jī)錄取情況詳解（中） HYPERLINK /s?_biz=MzUyMzc3NzI2Nw=&mid=2247504212&idx=1&sn=091dc1de5964ec4a41d1fd7ae863299a&chksm=fa35f4c8cd427ddecbd4187bbe822438e3fbab0b1fc1873e0b49ec6c6c69f596b5321c69185f&scene=21#wechat_redirect 【20考研】全國(guó)211計(jì)算機(jī)錄取情況詳解（下） 2 09-20 年408 真題與

20、解析 408偷雞法 -材料哥復(fù)習(xí)法 4天足矣1天數(shù)據(jù)結(jié)構(gòu)、1天操作系統(tǒng)、1天計(jì)算機(jī)網(wǎng)絡(luò)、1天計(jì)算機(jī)組成 原理。 -放棄復(fù)門，專門 計(jì)算機(jī)網(wǎng)絡(luò)只有 25 分，和英語大作文一個(gè)分?jǐn)?shù)，如果只是為了過國(guó)家線， 甚至可以不復(fù)習(xí)！ 此外如果時(shí)間實(shí)在不夠可以適當(dāng)放棄一些知識(shí)【比如計(jì)算機(jī)組成原理 中的除法】，專攻可以拿到分?jǐn)?shù)的科目。 -數(shù)據(jù)結(jié)構(gòu)算法題別管最優(yōu)算法了 直接懟一個(gè)暴力上去，13分穩(wěn)7分 -抓重點(diǎn)復(fù)習(xí) 數(shù)據(jù)結(jié)構(gòu)全沖！代碼一般考察線性表的操作，往年考的代碼題基本來源 leetcode。 操作系統(tǒng)重點(diǎn)：內(nèi)存管理【每年整個(gè)十幾分】、設(shè)備管理、用戶態(tài)轉(zhuǎn)換。 計(jì)算機(jī)組成原理重點(diǎn)： cache基本原理，cach

21、e訪問，分頁分段，CPU，流水線。 計(jì)算機(jī)網(wǎng)絡(luò)重點(diǎn)： 1.緒論：ISO/OSI，TCP/IP模型 2.物理層：奈奎斯特定理和香農(nóng)定理 3.數(shù)據(jù)鏈路層流量控制滑動(dòng)機(jī)制CSMA協(xié)議MAC幀的分析交換機(jī)機(jī) 制 4.網(wǎng)絡(luò)層：IP數(shù)據(jù)報(bào)，CIDR，ARP協(xié)議，路由協(xié)議以及路由器 5.傳輸層：TCP段分析，TCP傳輸機(jī)制（GBN，SR），UDP協(xié)議 6.應(yīng)用層：DNS，F(xiàn)TP -刷真題 09-20年共12年真題！ 09-20年408解析系列 數(shù)據(jù)結(jié)構(gòu)： HYPERLINK /video/BV1rK4y1e7JR /video/BV1rK4y1e7JR 操作系統(tǒng)： HYPERLINK /video/BV1c

22、54y1D7VC /video/BV1c54y1D7VC 計(jì)算機(jī)組成原理： HYPERLINK /video/BV1mK411J7DE/ /video/BV1mK411J7DE/ 計(jì)算機(jī)網(wǎng)絡(luò)： HYPERLINK /video/BV1Vk4y1m734/ /video/BV1Vk4y1m734/ 3 09-20 年408 真題與解析 2021 計(jì)算機(jī)統(tǒng)408考研大綱變動(dòng)與解析 2021計(jì)算機(jī)統(tǒng)考408變動(dòng)情況 數(shù)據(jù)結(jié)構(gòu) 2020 2021 線性表的定義和基本操作 【改動(dòng)】線性表的基本概念 棧和隊(duì)列的應(yīng)用 【改動(dòng)】棧、隊(duì)列和數(shù)組的應(yīng)用 【新增】多維數(shù)組的存儲(chǔ) 二叉排序樹 【改動(dòng)】二叉搜索樹 計(jì)算

23、機(jī)組成原理 2020 2021 【新增】計(jì)算機(jī)性能指標(biāo)增加： EFLOPS、ZFLOPS 計(jì)算機(jī)的發(fā)展歷程 【刪除】 BCD碼、校驗(yàn)碼 【刪除】 總線的仲裁：集中仲裁方式、分布仲裁方式 【刪除】 光盤存儲(chǔ)器 【刪除】 計(jì)算機(jī)網(wǎng)絡(luò) 2020 2021 計(jì)算機(jī)網(wǎng)絡(luò)的標(biāo)準(zhǔn)化工作及相關(guān)組織 【改動(dòng)】計(jì)算機(jī)網(wǎng)絡(luò)主要性能指標(biāo) 操作系統(tǒng) 2020 2021 交換與覆蓋 【刪除】 皮皮灰： 整體難度有所下調(diào) 改動(dòng)4處，刪除5處，新增2處 計(jì)組難度有所下調(diào)；DS網(wǎng)絡(luò)OS微調(diào) 4 09-20 年408 真題與解析 通過分析大綱，408計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合考查目標(biāo)沒有發(fā)生變化， 還是要求我們熟練掌握相關(guān)考查科目的

24、基本知識(shí)，并且強(qiáng)調(diào)知識(shí)的整體把 握，能夠綜合所學(xué)的基本原理和基本方法分析、解決實(shí)際問題。今年的小 改動(dòng)主要是關(guān)于知識(shí)點(diǎn)的，不過這些變動(dòng)對(duì)考生都是友好型的，添加了一 點(diǎn)點(diǎn)不太常考的，刪除了一些低頻點(diǎn)，具體變化各個(gè)科目都有涉及，但主 要是計(jì)算機(jī)組成原理和數(shù)據(jù)結(jié)構(gòu)，操作系統(tǒng)和計(jì)算機(jī)網(wǎng)絡(luò)各有一點(diǎn)點(diǎn)改 動(dòng)。 下面對(duì)各科目進(jìn)行具體分析。 數(shù)據(jù)結(jié)構(gòu)主要的改動(dòng)是添加了對(duì)多維數(shù)組的存儲(chǔ)和數(shù)組的應(yīng)用的考查，這 一部分內(nèi)容往些年也有涉及，只21年新大綱有了明確，并且進(jìn)行了拓 展，題型大概率還是選擇題，只是出題點(diǎn)可能不再局限于一維和二維數(shù) 組，可能上升為三維或者四維，存儲(chǔ)考查應(yīng)該還是計(jì)算數(shù)組元素的存儲(chǔ)地 址或者地址公

25、式的推導(dǎo)；應(yīng)用考查可能會(huì)在算法題有所涉及。針對(duì)這一具 體變動(dòng)，考生應(yīng)該多多關(guān)注，選取相關(guān)題目加以練習(xí)。另外還有兩處變 動(dòng)，大家可以放心，這兩處變化幾乎等于沒變，將“線性表的定義和基本 操作”改為了“線性表的基本概念”屬于描述上的改動(dòng)，“二叉排序樹” 改為了“二叉搜索樹”屬于名字上的改動(dòng)，本質(zhì)沒有發(fā)生變化。新大綱上 其他知識(shí)點(diǎn)一字不差，大家可以按部就班繼續(xù)復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)。 計(jì)算機(jī)組成原理這門課變動(dòng)點(diǎn)還是比較多的，添加和刪除都有，但是對(duì)于 考生來說非常友好。這是因?yàn)殡m然改變比較多，但是可以發(fā)現(xiàn)涉及的點(diǎn)都 屬于低頻考點(diǎn)或者目前還沒考的點(diǎn)，縮小了考生的復(fù)習(xí)范圍。 具體變化包括：計(jì)算機(jī)性能指標(biāo)添加ETLO

26、PSZTLOPS，刪除的知識(shí)點(diǎn) 包括計(jì)算機(jī)發(fā)展歷程、BCD碼、校驗(yàn)碼、總線仲裁（集中仲裁方式和分布 仲裁方式）和光盤存儲(chǔ)器。到這里大家是不是松了一口氣？那就請(qǐng)大家繼 續(xù)放心備考計(jì)算機(jī)組成原理。 操作系統(tǒng)部分僅刪除了交換和覆蓋，其他并沒有發(fā)生任何變化。刪除的這 一小知識(shí)本來也屬于低頻考點(diǎn)，現(xiàn)在可以直接跳過，大膽往前復(fù)習(xí)。 計(jì)算機(jī)網(wǎng)絡(luò)將“計(jì)算機(jī)網(wǎng)絡(luò)的標(biāo)準(zhǔn)化工作及相關(guān)組織”改為“計(jì)算機(jī)網(wǎng)絡(luò) 主要性能指標(biāo)”。這一改動(dòng)其實(shí)是將考查的知識(shí)點(diǎn)更加具體化了，這樣大 家復(fù)習(xí)起來也更具有針對(duì)性。這一小部分知識(shí)大概率情況下以選擇題的形 式考一些計(jì)算問題。除此之外，計(jì)算機(jī)網(wǎng)絡(luò)其他部分與往年一致。 總而言之，我們可以發(fā)

27、408改動(dòng)對(duì)各個(gè)科目的考查更具體和針對(duì)。從這 個(gè)角度來看，這樣的變化對(duì)于考生無疑是一個(gè)好消息。 5 09-20 年408 真題與解析 I考試性質(zhì) 計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合考試是為高等院校和科研院所招收計(jì)算機(jī)科學(xué)與 技術(shù)學(xué)科的碩士研究生而設(shè)置的具有選拔性質(zhì)的聯(lián)考科目其目的是科學(xué) 有效地測(cè)試考生掌握計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科大學(xué)本科階段專業(yè)知識(shí)、基本理論、 基本方法的水平和分析問題解決問題的能力評(píng)價(jià)的標(biāo)準(zhǔn)是高等院校計(jì)算機(jī)科 學(xué)與技術(shù)學(xué)科優(yōu)秀本科畢業(yè)生所能達(dá)到的及格或及格以上水平以利于各高等院 校和科研院所擇優(yōu)選拔，確保碩士研究生的招生質(zhì)量。 II考查目標(biāo) 計(jì)算機(jī)學(xué)科專業(yè)基礎(chǔ)綜合考試涵蓋數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)組成原

28、理操作系統(tǒng)和 計(jì)算機(jī)網(wǎng)絡(luò)等學(xué)科專業(yè)基礎(chǔ)課程要求考生比較系統(tǒng)地掌握上述專業(yè)基礎(chǔ)課程的 基本概念基本原理和基本方法 判斷和解決有關(guān)理論問題和實(shí)際問題。 III考試形式和試卷結(jié)構(gòu) 一、試卷滿分及考試時(shí)間 本試卷滿分為150分，考試時(shí)間為180分鐘。 二、答題方式 答題方式為閉卷、筆試。 三、試卷內(nèi)容結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)45分 計(jì)算機(jī)組成原理45分 操作系統(tǒng)35分 計(jì)算機(jī)網(wǎng)絡(luò)25分 四、試卷題型結(jié)構(gòu) 單項(xiàng)選擇題80分(40小題，每小題2分) 綜合應(yīng)用題70分 6 09-20 年408 真題與解析 408考研大綱-數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)2021考研大綱 【藍(lán)色代表修改，刪除線代表刪除，紅色代表新增】 【考查目標(biāo)】

29、 1.掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法。 2.掌握數(shù)據(jù)的邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)及基本操作的實(shí)現(xiàn) 的時(shí)間復(fù)雜度與空間復(fù)雜度的分析。 3.能夠運(yùn)用數(shù)據(jù)結(jié)構(gòu)基本原理和方法進(jìn)行問題的分析與求解具備采用C C+語言設(shè)計(jì)與實(shí)現(xiàn)算法的能力。 一、線性表 (一)線性表的基本概念【20版本：線性表的定義和基本操作】 (二)線性表的實(shí)現(xiàn) 1.順序存儲(chǔ) 2.鏈?zhǔn)酱鎯?chǔ) 3.線性表的應(yīng)用 二、棧、隊(duì)列和數(shù)組 (一)棧和隊(duì)列的基本概念 (二)棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu) (三)棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) (四)棧、隊(duì)列和數(shù)組的應(yīng)用【20版本：棧和隊(duì)列的應(yīng)用】 (五)特殊矩陣的壓縮存儲(chǔ) (六)多維數(shù)組的存儲(chǔ)【新增】 三、樹與二叉

30、樹 (一)樹的基本概念 (二)二叉樹 1.二叉樹的定義及其主要特征 2.二叉樹的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 3.二叉樹的遍歷 4.線索二叉樹的基本概念和構(gòu)造 7 09-20 年408 真題與解析 (三)樹、森林 1.樹的存儲(chǔ)結(jié)構(gòu) 2.森林與二叉樹的轉(zhuǎn)換 3.樹和森林的遍歷 (四)樹與二叉樹的應(yīng)用 1.二叉搜索樹【20版本：二叉排序樹】 2.平衡二叉樹 3.哈夫曼(Huffman)樹和哈夫曼編碼 四、圖 (一)圖的基本概念 (二)圖的存儲(chǔ)及基本操作 1.鄰接矩陣法 2.鄰接表法 3.鄰接多重表、十字鏈表 (三)圖的遍歷 1.深度優(yōu)先搜索 2.廣度優(yōu)先搜索 (四)圖的基本應(yīng)用 1.最小(代價(jià))生成

31、樹 2.最短路徑 3.拓?fù)渑判?4.關(guān)鍵路徑 五、查找 (一)查找的基本概念 (二)順序查找法 (三)分塊查找法 (四)折半查找法 (五)B樹及其基本操作、B+樹的基本概念 (六)散列(Hash)表 8 09-20 年408 真題與解析 (七)字符串模式匹配 (八)查找算法的分析及應(yīng)用 六、排序 (一)排序的基本概念 (二)插入排序 1.直接插入排序 2.折半插入排序 (三)起泡排序(BubbleSort) (四)簡(jiǎn)單選擇排序 (五)希爾排序(ShellSort) (六)快速排序 (七)堆排序 (八)二路歸并排序(MergeSort) (九)基數(shù)排序 (十)外部排序 (十一)各種排序算法的比較

32、 (十二)排序算法的應(yīng)用 9 09-20 年408 真題與解析 408考研大綱-計(jì)算機(jī)組成原理 【藍(lán)色代表修改，刪除線代表刪除，紅色代表新增】 【考查目標(biāo)】 1.理解單處理器計(jì)算機(jī)系統(tǒng)中各部件的內(nèi)部工作原理 接方式，具有完整的計(jì)算機(jī)系統(tǒng)的整機(jī)概念。 2.理解計(jì)算機(jī)系統(tǒng)層次化結(jié)構(gòu)概念熟悉硬件與軟件之間的界面 集體系結(jié)構(gòu)的基本知識(shí)和基本實(shí)現(xiàn)方法。 3.能夠綜合運(yùn)用計(jì)算機(jī)組成的基本原理和基本方法 中的理論和實(shí)際問題進(jìn)行計(jì)算、分析，對(duì)一些基本部件進(jìn)行簡(jiǎn)單設(shè)計(jì); 級(jí)程序設(shè)計(jì)語言(如C語言)中的相關(guān)問題進(jìn)行分析。 一、計(jì)算機(jī)系統(tǒng)概述 (一)計(jì)算機(jī)發(fā)展歷程【刪除】 (二)計(jì)算機(jī)系統(tǒng)層次結(jié)構(gòu) 1.計(jì)算機(jī)系統(tǒng)的

33、基本組成 2.計(jì)算機(jī)硬件的基本組成 3.計(jì)算機(jī)軟件和硬件的關(guān)系 4.計(jì)算機(jī)系統(tǒng)的工作過程 (三)計(jì)算機(jī)性能指標(biāo) 吞吐量響應(yīng)時(shí)間CPU時(shí)鐘周期主頻CPICPU執(zhí)行時(shí)間MIPSMFLOPS GFLOPS、TFLOPS、PFLOPS、EFLOPS、ZFLOPS【新增】。 二、數(shù)據(jù)的表示和運(yùn)算 (一)數(shù)制與編碼 1.進(jìn)位計(jì)數(shù)制及其相互轉(zhuǎn)換 2.真值和機(jī)器數(shù) 3.BCD碼【刪除】 4.字符與字符串 5.校驗(yàn)碼【刪除】 (二)定點(diǎn)數(shù)的表示和運(yùn)算 1.定點(diǎn)數(shù)的表示 10 09-20 年408 真題與解析 無符號(hào)數(shù)的表示，帶符號(hào)整數(shù)的表示。 2.定點(diǎn)數(shù)的運(yùn)算 定點(diǎn)數(shù)的位移運(yùn)算原碼定點(diǎn)數(shù)的加/減運(yùn)算補(bǔ)碼定點(diǎn)數(shù)的

34、加/減運(yùn)算 點(diǎn)數(shù)的乘/除運(yùn)算，溢出概念和判別方法。 (三)浮點(diǎn)數(shù)的表示和運(yùn)算 1.浮點(diǎn)數(shù)的表示 IEEE754標(biāo)準(zhǔn)。 2.浮點(diǎn)數(shù)的加/減運(yùn)算 (四)算術(shù)邏輯單元ALU 1.串行加法器和并行加法器 2.算術(shù)邏輯單元ALU的功能和結(jié)構(gòu) 三、存儲(chǔ)器層次結(jié)構(gòu) (一)存儲(chǔ)器的分類 (二)存儲(chǔ)器的層次化結(jié)構(gòu) (三)半導(dǎo)體隨機(jī)存取存儲(chǔ)器 1.SRAM存儲(chǔ)器 2.DRAM存儲(chǔ)器 3.只讀存儲(chǔ)器 4.Flash存儲(chǔ)器 (四)主存儲(chǔ)器與CPU的連接 (五)雙口RAM和多模塊存儲(chǔ)器 (六)高速緩沖存儲(chǔ)器(Cache) 1.Cache的基本工作原理 2.Cach和主存之間的映射方式 3.Cache中主存塊的替換算法

35、4.Cache寫策略 (七)虛擬存儲(chǔ)器 1.虛擬存儲(chǔ)器的基本概念 2.頁式虛擬存儲(chǔ)器 11 09-20 年408 真題與解析 3.段式虛擬存儲(chǔ)器 4.段頁式虛擬存儲(chǔ)器 5.TLB(快表) 四、指令系統(tǒng) (一)指令格式 1.指令的基本格式 2.定長(zhǎng)操作碼指令格式 3.擴(kuò)展操作碼指令格式 (二)指令的尋址方式 1.有效地址的概念 2.數(shù)據(jù)尋址和指令尋址 3.常見尋址方式 (三)CISC和RISC的基本概念 五、中央處理器(CPU) (一)CPU的功能和基本結(jié)構(gòu) (二)指令執(zhí)行過程 (三)數(shù)據(jù)通路的功能和基本結(jié)構(gòu) (四)控制器的功能和工作原理 1.硬布線控制器 2.微程序控制器 微程序微指令和微命令

36、微指令格式微命令的編碼方式 方式。 (五)指令流水線 1.指令流水線的基本概念 2.指令流水線的基本實(shí)現(xiàn) 3.超標(biāo)量和動(dòng)態(tài)流水線的基本概念 六、總線 (一)總線概述 1.總線的基本概念 12 09-20 年408 真題與解析 2.總線的分類 3.總線的組成及性能指標(biāo) (二)總線仲裁【刪除】 1.集中仲裁方式【刪除】 2.分布仲裁方式【刪除】 (三)總線操作和定時(shí) 1.同步定時(shí)方式 2.異步定時(shí)方式 (四)總線標(biāo)準(zhǔn) 七、輸入輸出(I/O)系統(tǒng) (一)I/O系統(tǒng)基本概念 (二)外部設(shè)備 1.輸入設(shè)備：鍵盤、鼠標(biāo) 2.輸出設(shè)備：顯示器、打印機(jī) 3.外存儲(chǔ)器：硬盤存儲(chǔ)器、磁盤陣列、光盤存儲(chǔ)器【刪除】

37、(三)I/O接口(I/O控制器) 1.I/O接口的功能和基本結(jié)構(gòu) 2.I/O端口及其編址 (四)I/O方式 1.程序查詢方式 2.程序中斷方式 中斷的基本概念中斷響應(yīng)過程中斷處理過程 念。 3.DMA方式 DMA控制器的組成，DMA傳送過程。 13 09-20 年408 真題與解析 408考研大綱-操作系統(tǒng) 【藍(lán)色代表修改，刪除線代表刪除，紅色代表新增】 【考查目標(biāo)】 1.掌握操作系統(tǒng)的基本概念基本原理和基本功能 行過程。 2.掌握操作系統(tǒng)進(jìn)程內(nèi)存文件和I/O管理的策略算法 關(guān)系。 3.能夠運(yùn)用所學(xué)的操作系統(tǒng)原理方法與技術(shù)分析問題和解決問題 用C語言描述相關(guān)算法。 一、操作系統(tǒng)概述 (一)操作

38、系統(tǒng)的概念、特征、功能和提供的服務(wù) (二)操作系統(tǒng)的發(fā)展與分類 (三)操作系統(tǒng)的運(yùn)行環(huán)境 1.內(nèi)核態(tài)與用戶態(tài) 2.中斷、異常 3.系統(tǒng)調(diào)用 (四)操作系統(tǒng)體系結(jié)構(gòu) 二、進(jìn)程管理 (一)進(jìn)程與線程 1.進(jìn)程概念 2.進(jìn)程的狀態(tài)與轉(zhuǎn)換 3.進(jìn)程控制 4.進(jìn)程組織 5.進(jìn)程通信 共享存儲(chǔ)系統(tǒng)，消息傳遞系統(tǒng)，管道通信。 6.線程概念與多線程模型 (二)處理機(jī)調(diào)度 1.調(diào)度的基本概念 2.調(diào)度時(shí)機(jī)、切換與過程 14 09-20 年408 真題與解析 3.調(diào)度的基本準(zhǔn)則 4.調(diào)度方式 5.典型調(diào)度算法 先來先服務(wù)調(diào)度算法短作業(yè)(短進(jìn)程短線程)優(yōu)先調(diào)度算法時(shí)間片輪轉(zhuǎn) 調(diào)度算法優(yōu)先級(jí)調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算

39、法多級(jí)反饋隊(duì)列調(diào)度算 法。 (三)同步與互斥 1.進(jìn)程同步的基本概念 2.實(shí)現(xiàn)臨界區(qū)互斥的基本方法 軟件實(shí)現(xiàn)方法，硬件實(shí)現(xiàn)方法。 3.信號(hào)量 4.管程 5.經(jīng)典同步問題 生產(chǎn)者-消費(fèi)者問題，讀者-寫者問題，哲學(xué)家進(jìn)餐問題。 (四)死鎖 1.死鎖的概念 2.死鎖處理策略 3.死鎖預(yù)防 4.死鎖避免 系統(tǒng)安全狀態(tài)，銀行家算法。 5.死鎖檢測(cè)和解除 三、內(nèi)存管理 (一)內(nèi)存管理基礎(chǔ) 1.內(nèi)存管理概念 程序裝入與鏈接，邏輯地址與物理地址空間，內(nèi)存保護(hù)。 2.交換與覆蓋【刪除】 3.連續(xù)分配管理方式 4.非連續(xù)分配管理方式 分頁管理方式，分段管理方式，段頁式管理方式。 15 09-20 年408 真題與

40、解析 (二)虛擬內(nèi)存管理 1.虛擬內(nèi)存基本概念 2.請(qǐng)求分頁管理方式 3.頁面置換算法 最佳置換算法(OPT)，先進(jìn)先出置換算法(FIFO)，最近最少使用置換算法 (LRU)，時(shí)鐘置換算法(CLOCK)。 4.頁面分配策略 5.工作集 6.抖動(dòng) 四、文件管理 (一)文件系統(tǒng)基礎(chǔ) 1.文件概念 2.文件的邏輯結(jié)構(gòu) 順序文件，索引文件，索引順序文件。 3.目錄結(jié)構(gòu) 文件控制塊和索引節(jié)點(diǎn)單級(jí)目錄結(jié)構(gòu)和兩級(jí)目錄結(jié)構(gòu)樹形目錄結(jié)構(gòu) 形目錄結(jié)構(gòu)。 4.文件共享 5.文件保護(hù) 訪問類型，訪問控制。 (二)文件系統(tǒng)實(shí)現(xiàn) 1.文件系統(tǒng)層次結(jié)構(gòu) 2.目錄實(shí)現(xiàn) 3.文件實(shí)現(xiàn) (三)磁盤組織與管理 1.磁盤的結(jié)構(gòu) 2.

41、磁盤調(diào)度算法 3.磁盤的管理 五、輸入輸出(I/O)管理 16 09-20 年408 真題與解析 (一)I/O管理概述 1.I/O控制方式 2.I/O軟件層次結(jié)構(gòu) (二)I/O核心子系統(tǒng) 1.I/O調(diào)度概念 2.高速緩存與緩沖區(qū) 3.設(shè)備分配與回收 4.假脫機(jī)技術(shù)(SPOOLing) 17 09-20 年408 真題與解析 408考研大綱-計(jì)算機(jī)網(wǎng)絡(luò) 【藍(lán)色代表修改，刪除線代表刪除，紅色代表新增】 【考查目標(biāo)】 1.掌握計(jì)算機(jī)網(wǎng)絡(luò)的基本概念、基本原理和基本方法。 2.掌握計(jì)算機(jī)網(wǎng)絡(luò)的體系結(jié)構(gòu)和典型網(wǎng)絡(luò)協(xié)議 理解典型網(wǎng)絡(luò)設(shè)備的工作原理。 3.能夠運(yùn)用計(jì)算機(jī)網(wǎng)絡(luò)的基本概念基本原理和基本方法進(jìn)行網(wǎng)絡(luò)

42、系統(tǒng)的分 析、設(shè)計(jì)和應(yīng)用。 一、計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu) (一)計(jì)算機(jī)網(wǎng)絡(luò)概述 1.計(jì)算機(jī)網(wǎng)絡(luò)的概念、組成與功能 2.計(jì)算機(jī)網(wǎng)絡(luò)的分類 3. 計(jì)算機(jī)網(wǎng)絡(luò)主要性能指【20版本計(jì)算機(jī)網(wǎng)絡(luò)的標(biāo)準(zhǔn)化工作及相關(guān)組 織】 (二)計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)與參考模型 1.計(jì)算機(jī)網(wǎng)絡(luò)分層結(jié)構(gòu) 2.計(jì)算機(jī)網(wǎng)絡(luò)協(xié)議、接口、服務(wù)等概念 3.ISO/OSI參考模型和TCP/IP模型 二、物理層 (一)通信基礎(chǔ) 1.信道、信號(hào)、寬帶、碼元、波特、速率、信源與信宿等基本概念 2.奈奎斯特定理與香農(nóng)定理 3.編碼與調(diào)制 4.電路交換、報(bào)文交換與分組交換 5.數(shù)據(jù)報(bào)與虛電路 (二)傳輸介質(zhì) 1.雙絞線、同軸電纜、光纖與無線傳輸介質(zhì) 2.物

43、理層接口的特性 (三)物理層設(shè)備 18 09-20 年408 真題與解析 1.中繼器 2.集線器 三、數(shù)據(jù)鏈路層 (一)數(shù)據(jù)鏈路層的功能 (二)組幀 (三)差錯(cuò)控制 1.檢錯(cuò)編碼 2.糾錯(cuò)編碼 (四)流量控制與可靠傳輸機(jī)制 1.流量控制、可靠傳輸與滑動(dòng)窗口機(jī)制 2.停止-等待協(xié)議 3.后退N幀協(xié)議(GBN) 4.選擇重傳協(xié)議(SR) (五)介質(zhì)訪問控制 1.信道劃分 頻分多路復(fù)用時(shí)分多路復(fù)用波分多路復(fù)用 原理。 2.隨機(jī)訪問 ALOHA協(xié)議，CSMA協(xié)議，CSMA/CD協(xié)議，CSMA/CA協(xié)議。 3.輪詢?cè)L問 令牌傳遞協(xié)議 (六)局域網(wǎng) 1.局域網(wǎng)的基本概念與體系結(jié)構(gòu) 2.以太網(wǎng)與IEEE80

44、2.3 3.IEEE802.11 4.令牌環(huán)網(wǎng)的基本原理 (七)廣域網(wǎng) 1.廣域網(wǎng)的基本概念 2.PPP協(xié)議 19 09-20 年408 真題與解析 3.HDLC協(xié)議 (八)數(shù)據(jù)鏈路層設(shè)備 1.網(wǎng)橋的概念及其基本原理 2.局域網(wǎng)交換機(jī)及其工作原理。 四、網(wǎng)絡(luò)層 (一)網(wǎng)絡(luò)層的功能 1.異構(gòu)網(wǎng)絡(luò)互連 2.路由與轉(zhuǎn)發(fā) 3.擁塞控制 (二)路由算法 1.靜態(tài)路由與動(dòng)態(tài)路由 2.距離-向量路由算法 3.鏈路狀態(tài)路由算法 4.層次路由 (三)IPv4 1.IPv4分組 2.IPv4地址與NAT 3.子網(wǎng)劃分、路由聚集、子網(wǎng)掩碼與CIDR 4.ARP協(xié)議、DHCP協(xié)議與ICMP協(xié)議 (四)IPv6 1.I

45、Pv6的主要特點(diǎn) 2.IPv6地址 (五)路由協(xié)議 1.自治系統(tǒng) 2.域內(nèi)路由與域間路由 3.RIP路由協(xié)議 4.OSPF路由協(xié)議 5.BGP路由協(xié)議 (六)IP組播 20 09-20 年408 真題與解析 1.組播的概念 2.IP組播地址 (七)移動(dòng)IP 1.移動(dòng)IP的概念 2.移動(dòng)IP通信過程 (八)網(wǎng)絡(luò)層設(shè)備 1.路由器的組成和功能 2.路由表與路由轉(zhuǎn)發(fā) 五、傳輸層 (一)傳輸層提供的服務(wù) 1.傳輸層的功能 2.傳輸層尋址與端口 3.無連接服務(wù)與面向連接服務(wù) (二)UDP協(xié)議 1.UDP數(shù)據(jù)報(bào) 2.UDP校驗(yàn) (三)TCP協(xié)議 1.TCP段 2.TCP連接管理 3.TCP可靠傳輸 4.T

46、CP流量控制與擁塞控制 六、應(yīng)用層 (一)網(wǎng)絡(luò)應(yīng)用模型 1.客戶/服務(wù)器模型 2.P2P模型 (二)DNS系統(tǒng) 1.層次域名空間 2.域名服務(wù)器 3.域名解析過程 21 09-20 年408 真題與解析 (三)FTP 1.FTP協(xié)議的工作原理 2.控制連接與數(shù)據(jù)連接 (四)電子郵件 1.電子郵件系統(tǒng)的組成結(jié)構(gòu) 2.電子郵件格式與MIME 3.SMTP協(xié)議與POP3協(xié)議 (五)WWW 1.WWW的概念與組成結(jié)構(gòu) 2.HTTP協(xié)議 22 09-20 年408 真題與解析 09-20年408真題與解析-數(shù)據(jù)結(jié)構(gòu)部分 視頻鏈接： C語言基礎(chǔ)課程 HYPERLINK /video/BV17V411S7u

47、F /video/BV17V411S7uF 專業(yè)課基礎(chǔ)班/強(qiáng)化班 數(shù)據(jù)結(jié)構(gòu)： HYPERLINK /video/BV1s5411a7VW /video/BV1s5411a7VW 操作系統(tǒng)： HYPERLINK /video/BV1164y1F7mk /video/BV1164y1F7mk 計(jì)算機(jī)組成原理： HYPERLINK /video/BV1eh411Z7tZ /video/BV1eh411Z7tZ 計(jì)算機(jī)網(wǎng)絡(luò)： HYPERLINK /video/BV1xT4y1j7AL /video/BV1xT4y1j7AL 09-20年408解析系列 數(shù)據(jù)結(jié)構(gòu)： HYPERLINK /video/BV

48、1rK4y1e7JR /video/BV1rK4y1e7JR 操作系統(tǒng)： HYPERLINK /video/BV1c54y1D7VC /video/BV1c54y1D7VC 計(jì)算機(jī)組成原理： HYPERLINK /video/BV1mK411J7DE/ /video/BV1mK411J7DE/ 計(jì)算機(jī)網(wǎng)絡(luò)： HYPERLINK /video/BV1Vk4y1m734/ /video/BV1Vk4y1m734/ 機(jī)試二十講： HYPERLINK /video/BV1a54y1v7o1 /video/BV1a54y1v7o1 23 09-20 年408 真題與解析 24 09-20 年408 真題

49、與解析 2020 年統(tǒng)考408 真題-數(shù)據(jù)結(jié)構(gòu)部分 數(shù)據(jù)結(jié)構(gòu)部分選擇題： 1. 將一個(gè)10 * 10 對(duì)稱矩陣M 的上三角部分的元素 (1ij10) 按列優(yōu)先存入 C 一維數(shù)組 N 中，元素7,2在 N 中的下標(biāo)是（ 。 A、15 B、16 C、22 D、23 2. 對(duì)空棧 S 進(jìn)行Push與Pop操作，入棧序列 a, b, c, d, e 經(jīng)過Push，Push，Pop， Push，Pop，Push，Push，Pop操作后得到的出棧序列是（ 。 A、b, a, c B、b, a, e C、b, c, a D、b, c, e 3. 對(duì)于任意一棵高度為 5 且有 10 點(diǎn)占 1 至少是（ 。 A

50、、31 B、16 C、15 D、10 4. 已知森林 F 及與之對(duì)應(yīng)的二叉樹 T，若 F 的先根遍歷序列是 a, b, c, d, e, f，中 根遍歷序列是 b, a, d, f, e, c 則 T 的后根遍歷序列是（ 。 A、b, a, d, f, e, c B、b, d, f, e, c, a C、b, f, e, d, c, a D、f, e, d, c, b, a 5. 下列給定的關(guān)鍵字輸入序列中，不能生成如下二叉排序樹的是（ 。 A、4，5，2，1，3 B、4，5，1，2，3 C、4，2，5，3，1 D、4，2，1，3，5 6. 修改遞歸方式實(shí)現(xiàn)的圖的深度優(yōu)先搜（DS算法將輸（訪問

51、定點(diǎn)信息的語句移 到退出遞歸前（即執(zhí)行輸出語句后立刻退出遞歸。采用修改后的算法遍歷有向無環(huán)圖 G，若輸出結(jié)果中包含 G 中的全部頂點(diǎn)，則輸出的頂點(diǎn)序列是 G 的（ 。 A、拓?fù)溆行蛐蛄?B、逆拓?fù)溆行蛐蛄?C、廣度優(yōu)先搜索序列 D、深度優(yōu)先搜索序列 25 09-20 年408 真題與解析 7. 已知無向圖 G 如下所示使用克魯斯卡（rusal算法求圖 G 的最小生成樹 到最小生成樹中的邊依次是（ 。 A、(b,f)(b,d)(a,e)(c,e)(b,e) B、(b,f)(b,d)(b,e)(a,e)(e,c) C、(a,e)(b,e)(c,e)(b,d)(b,f) D、(a,e)(c,e)(b

52、,e)(b,f)(b,d) 8. 若使用 OE 網(wǎng)估算工程進(jìn)度，則下列敘述中正確的是（ 。 A、關(guān)鍵路徑是從原點(diǎn)到匯點(diǎn)邊數(shù)最多的一條路徑 B、關(guān)鍵路徑是從原點(diǎn)到匯點(diǎn)路徑長(zhǎng)度最長(zhǎng)的路徑 C、增加任一關(guān)鍵活動(dòng)的時(shí)間不會(huì)延長(zhǎng)工程的工期 D、縮短任一關(guān)鍵活動(dòng)的時(shí)間將會(huì)縮短工程的工期 9. 下列關(guān)于大根堆（至少含 2 個(gè)元素）的敘述中正確的是（ 。 I 可以將堆看成一棵完全二叉樹； II 可采用順序存儲(chǔ)方式保存堆； III 可以將堆看成一棵二叉排序樹； IV 堆中的次大值一定在根的下一層。 10. 依次將關(guān)鍵字 56913821215 插入初始為空的 4 階 B 樹后 含的關(guān)鍵字是（ 。 A、8 B、6

53、，9 C、8，13 D、9，12 11. 對(duì)大部分元素已有序的數(shù)組進(jìn)行排序時(shí)直接插入排序比簡(jiǎn)單選擇排序效率更高 因是（ 。 I、 直接插入排序過程中元素之間的比較次數(shù)更少 II、 直接插入排序過程中所需要的輔助空間更少 III、 直接插入排序過程中元素的移動(dòng)次數(shù)更少 A、I B、III C、I,II D、I,II,III 26 09-20 年408 真題與解析 數(shù)據(jù)結(jié)構(gòu)部分大題 12. 定義三元組（a, b, c（a,b,c 均為正數(shù)）的距離 D=|a-b|+|b-c|+|c-a|. 給定 3 數(shù)集合 S1, S2 ,S3, 按升序分別存儲(chǔ)在 3 算并輸出所有可能的三元組（a, b, c（a

54、S1,b S2,c S3）中的最小距離。 例如 S1=-1,0,9,S2-25-101011S329173041則最小距離為 2 相應(yīng)的三元組為（9，10，9） 要求： （1）給出算法的基本設(shè)計(jì)思想； （2）根據(jù)設(shè)計(jì)思想，采用 C 或 C+語言描述算法，關(guān)鍵之處給出注釋； （3）說明你所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度。 13. 若任一個(gè)字符的編碼都不是其他字符編碼的前綴則稱這種編碼具有前綴特性 字符（字符個(gè)數(shù)2的不等長(zhǎng)編碼每個(gè)字符的編碼均為二進(jìn)制的 01 序列 為 L 位，且具有前綴特性。請(qǐng)回答下列問題： （1）哪種數(shù)據(jù)結(jié)構(gòu)適宜保存上述具有前綴特性的不等長(zhǎng)編碼？ （2）基于你所設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)

55、，簡(jiǎn)述從 0/1 串到字符串的譯碼過程 （3）簡(jiǎn)述判定某字符集的不等長(zhǎng)編碼是否具有前綴特性的過程 27 09-20 年408 真題與解析 2020 年408 計(jì)算機(jī)統(tǒng)考真題-數(shù)據(jù)結(jié)構(gòu)部分參考答案 B站關(guān)注灰灰考研可查看視頻解析 1. 【皮皮答案】C 【皮皮解析】 上三角矩陣列優(yōu)先的存儲(chǔ)模式先存儲(chǔ)具有一個(gè)元素第一列 的第二列，以此類推 7,2說明1-6列均已存滿，故此元素是第1+2+3+4+5+6+2個(gè)被存儲(chǔ)單元 【注意!】C語言數(shù)組的下標(biāo)從0開始 故7,2在N中的下標(biāo)為23-1=22，即N22 2. 【皮皮答案】D 【皮皮解析】 操作 執(zhí)行該操作后的棧(左側(cè)為棧底) 出棧元素 Push a P

56、ush ab Pop a b Push ac Pop a c Push ad Push ade Pop ad e 3. 【皮皮答案】A 【皮皮解析】 本二叉樹使用順序結(jié)構(gòu)存儲(chǔ)時(shí)，為了保證任意性，其1-5 節(jié)點(diǎn)）全部都要被存儲(chǔ)起來，即考慮成一棵5層的滿二叉樹，存儲(chǔ)單元大小為 1+2+4+8+16 = 31 4. 【皮皮答案】C 【皮皮解析】 任何n 個(gè)不同節(jié)點(diǎn)的二叉樹，都可由它的中序序列和先序序列唯一確定。 28 09-20 年408 真題與解析 此二叉樹T對(duì)應(yīng)的后根遍歷序列是bfedca 5. 【皮皮答案】B 【皮皮解析】基本概念題。 B選項(xiàng)構(gòu)造出的二叉排序樹 6. 【皮皮答案】B 【皮皮解析

57、】 DF是一個(gè)遞歸算法,在遍歷的過程中,先訪問的點(diǎn)被壓入棧底 U 到V 有一條弧,則在拓?fù)湫蛄蠻 一定V 之前. 一條弧,棧的輸出是從最后一個(gè)被訪問點(diǎn)開始輸出,最后一個(gè)輸出的點(diǎn)是第一個(gè)被訪問的 點(diǎn).所以是逆拓?fù)溆行蛐蛄?29 09-20 年408 真題與解析 7. 【皮皮答案】A 【皮皮解析】 rusal 算法：按權(quán)值遞增次序選擇合適的邊構(gòu)造最小生成樹 基本思想：按照權(quán)值的遞增順序選擇n-條邊，并保證這n-條邊不構(gòu)成回路。 具體做法首先構(gòu)造一個(gè)只含個(gè)頂點(diǎn)的森林然后依權(quán)值從小到大從連通網(wǎng)中選 擇邊加入到森林中并使森林中不產(chǎn)生回路 *注：d邊權(quán)值尚不明確，但一定是比1大的某個(gè)數(shù)，不影響解題 第1步

58、：選取邊 邊的權(quán)值最小，因此將它加入到最小生成樹中。 第2步：選取邊 上一步操作之后，邊的權(quán)值最小，將它加入到最小生成樹結(jié)果中。 第3步：選取邊 上一步操作之后，邊的權(quán)值最小，但 跳過邊, 將邊它加入到最小生成樹中。 30 09-20 年408 真題與解析 第4步：選取邊 上一步操作之后，邊的權(quán)值最小，將它加入到最小生成樹中。 第5步：選取邊 上一步操作之后，邊的權(quán)值最小，將它加入到最小生成樹中。 此時(shí)，最小生成樹構(gòu)造完成,它包括的邊是： 8. 【皮皮答案】B 【皮皮解析】基礎(chǔ)概念題。 關(guān)鍵路徑（critical pth：在OE 長(zhǎng)度的路徑 9. 【皮皮答案】I、 II、 IV 【皮皮解析】基

59、礎(chǔ)概念題 堆（Heap）具有以下特點(diǎn)： 1） 完全二叉樹 2） 存儲(chǔ)的值是偏序 大根堆（Max-heap：父節(jié)點(diǎn)的值大于或等于子節(jié)點(diǎn)的值 一般用數(shù)組（順序結(jié)構(gòu)）來表示堆 10. 【皮皮答案】B 【皮皮解析】 B 樹是一種平衡的多路搜索樹 結(jié)點(diǎn)最大的孩子數(shù)目稱為B 樹的階一個(gè)m 階B 有如下屬性： 1.定義任意非葉子結(jié)點(diǎn)最多只有M 個(gè)兒子；且M2 2.根結(jié)點(diǎn)的兒子數(shù)為 2 , M 3.除根結(jié)點(diǎn)以外的非葉子結(jié)點(diǎn)的兒子數(shù)為 M/2, M 4.每個(gè)結(jié)點(diǎn)存放至少M(fèi)/2-1（取上整）和至多M-1 個(gè)關(guān)鍵字（至少2 個(gè)關(guān)鍵字） 5.非葉子結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù) = 指向兒子的指針個(gè)數(shù)-1 6.非葉子結(jié)點(diǎn)的關(guān)鍵字：

60、K 1 , K 2 , , K M-1 ；且K i =（x+1）*（x+1） x=x+l； AO（log n） BO（） C O（n） DO（n2） 2若將一棵樹T 轉(zhuǎn)化為對(duì)應(yīng)的二叉樹T，則下列對(duì)T 的遍歷中，其編歷序列與T 遍歷序列相同的是（ 。 A先序遍歷 B中序遍歷 C后序遍歷 D按層遍歷 3對(duì)n 個(gè)互不相同的符號(hào)進(jìn)行哈夫曼編碼若生成的哈夫曼樹共有115 個(gè)結(jié)點(diǎn)則n 是（ 。 A56 B57 C58 D60 4在任意一棵非空平衡二叉（VL 樹T1 中刪除某結(jié)點(diǎn)v 之后形成平衡二叉樹T2 將v 插入T2 形成平衡二叉樹T3。下列關(guān)于T1 與T3 的敘述中，正確的是（ 。 （I） 若v 是T