編輯推薦
依托王道論壇的平颱與口碑,“王道考研係列”已然成為計算機考研輔導書中的口碑品牌,這一係列書由王道論壇組織名校高分選手編寫,不僅參考瞭同類優秀圖書,更是融入瞭論壇眾多高分考生的智慧、以及論壇交流精華。“書本+在綫”的學習方式是本書最大特色,一方麵它可以使同學們能及時解決復習中的遇到的各種疑問,另一方麵它也能更好的促進王道論壇對《王道考研係列:2016年XXXX聯考復習指導》進行改進和優化。
在過去的3年,有眾多考生通過王道考研輔導書實現瞭自己的名校夢,也正是靠著成功學長的口碑相傳,纔有瞭王道論壇和“王道考研係列”輔導書今天的口碑。雖然王道論壇連續命中2012-2015年的算法設計題等多道大題,但希望大傢在使用王道輔導書時,不要抱有任何投機的心態,踏踏實實去掌握每一個知識點,纔是高分的保障。
輔導書隻是工具,成功隻能靠自己,讓自己更加強大。但我相信,有王道論壇以及王道考研輔導書的支撐,一定會讓同學們的考研之路變得更加輕鬆和高效!
內容簡介
《2016年計算機專業基礎綜閤考試真題思路分析》是計算機專業研究生入學考試真題分析用書,首先給齣2009年至2015全國碩士研究生入學統一考試計算機科學與技術學科聯考計算機學科專業基礎綜閤試題,然後按數據結構篇、計算機組成原理篇、操作係統篇、計算機網絡篇對題進行分析。全書嚴格按照新計算機考研大綱,對大綱所涉及的知識點進行集中梳理,給齣詳細的解題思路,力求達到講練結閤、靈活掌握、舉一反三的功效。同時,創新的"書本+在綫”的學習方式與網上答疑,可大大提高考生的復習效果,達到事半功倍的復習效率。
內頁插圖
目錄
2015年全國碩士研究生入學統一考試計算機科學與技術學科聯考計算機學科專業基礎綜閤試題 1
2014年全國碩士研究生入學統一考試計算機科學與技術學科聯考計算機學科專業基礎綜閤試題 13
2013年全國碩士研究生入學統一考試計算機科學與技術學科聯考計算機學科專業基礎綜閤試題 25
2012年全國碩士研究生入學統一考試計算機科學與技術學科聯考計算機學科專業基礎綜閤試題 37
2011年全國碩士研究生入學統一考試計算機科學與技術學科聯考計算機學科專業基礎綜閤試題 49
2010年全國碩士研究生入學統一考試計算機科學與技術學科聯考計算機學科專業基礎綜閤試題 61
2009年全國碩士研究生入學統一考試計算機科學與技術學科聯考計算機學科專業基礎綜閤試題 73
第1篇 數據結構部分
第1章 緒論 87
真題分布及命題重點 87
考點1:時間復雜度與空間復雜度 87
第2章 綫性錶 90
真題分布及命題重點 90
考點2:綫性錶的順序錶示 90
考點3:綫性錶的鏈式錶示 93
第3章 棧和隊列 99
真題分布及命題重點 99
考點4:棧和隊列的基本性質 99
考點5:棧和隊列的存儲結構 101
考點6:雙端隊列 102
考點7:棧與隊列的應用 103
考點8:特殊矩陣的壓縮存儲 107
第4章 樹與二叉樹 109
真題分布及命題重點 109
考點9:樹的基本性質 109
考點10:二叉樹的定義與性質 110
考點11:二叉樹的遍曆 111
考點12:二叉排序樹 116
考點13:平衡二叉樹 118
考點14:樹、森林與二叉樹的轉換 122
考點15:綫索二叉樹的基本概念和構造 124
考點16:哈夫曼樹與哈夫曼編碼 125
第5章 圖 128
真題分布及命題重點 128
考點17:圖的基本概念 128
考點18:圖的存儲及基本操作 130
考點19:圖的遍曆 135
考點20:最小(代價)生成樹 136
考點21:最短路徑 138
考點22:拓撲排序 140
考點23:關鍵路徑 142
第6章 查找 146
真題分布及命題重點 146
考點24:順序查找法&摺半查找法 146
考點25:B樹及其基本操作、B+樹的基本概念 150
考點26:散列(HASH)錶 153
考點27:字符串模式匹配 155
第7章 排序 156
真題分布及命題重點 156
考點28:插入排序 156
考點29:交換排序 158
考點30:選擇排序 160
考點31:二路歸並排序 163
考點32:基數排序 164
考點33:各種內部排序方法的比較 165
考點34:外部排序的思想 166
第2篇 計算機組成原理部分
第1章 計算機係統概論 169
真題分布及命題重點 169
考點35:計算機係統層次結構 169
考點36:計算機的性能指標 170
第2章 數據的錶示和運算 173
真題分布及命題重點 173
考點37:海明碼 173
考點38:數據的存儲方式 174
考點39:定點數的錶示與運算 176
考點40:IEEE754標準 180
考點41:各種精度數據的轉換 182
考點42:浮點數運算 183
第3章 存儲係統的層次結構 186
真題分布及命題重點 186
考點43:半導體隨機存取存儲器 186
考點44:主存儲器與CPU的連接 188
考點45:低位交叉存儲器 189
考點46:高速緩衝存儲器(CACHE) 190
考點47:虛擬存儲器 195
第4章 指令係統 200
真題分布及命題重點 200
考點48:指令格式 200
考點49:指令的尋址方式 202
考點50:CISC與RISC 207
第5章 中央處理器 209
真題分布及命題重點 209
考點51:CPU的功能和基本結構 209
考點52:指令執行過程 210
考點53:數據通路的功能和基本結構 211
考點54:控製器的功能和工作原理 214
考點55:指令流水綫 216
第6章 總綫 221
真題分布及命題重點 221
考點56:總綫分類 221
考點57:總綫的性能指標 222
考點58:總綫標準 224
第7章 輸入/輸齣係統 225
真題分布及命題重點 225
考點59:外部設備 225
考點60:磁盤與RAID 226
考點61:I/O接口 227
考點62:程序查詢方式 228
考點63:程序中斷方式 228
考點64:DMA方式 231
第3篇 操作係統部分
第1章 操作係統概述 235
真題分布及命題重點 235
考點65:操作係統的概念、特徵和功能 235
考點66:內核態與用戶態 236
考點67:中斷、異常 237
考點68:係統調用 238
第2章 進程管理 240
真題分布及命題重點 240
考點69:進程與綫程 240
考點70:進程狀態與進程控製 242
考點71:處理機調度 243
考點72:進程同步與互斥 246
考點73:經典同步問題 249
考點74:死鎖 254
第3章 內 存 管 理 258
真題分布及命題重點 258
考點75:內存管理的概念 258
考點76:連續分配管理方式 260
考點77:非連續分配管理方式 261
考點78:虛擬頁式存儲管理 264
考點79:抖動 271
第4章 文 件 管 理 272
真題分布及命題重點 272
考點80:目錄結構 272
考點81:文件共享和文件保護 273
考點82:文件的操作 274
考點83:文件實現 275
考點84:磁盤組織與管理 279
第5章 設 備 管 理 282
真題分布及命題重點 282
考點85:I/O控製方式 282
考點86:I/O軟件的層次結構 282
考點87:I/O調度與緩衝區 284
考點88:設備分配與迴收 285
第4篇 計算機網絡部分
第1章 計算機網絡體係結構 287
真題分布及命題重點 287
考點89:計算機網絡的分層結構 287
考點90:ISO/OSI參考模型和TCP/IP模型 288
第2章 物 理 層 290
真題分布及命題重點 290
考點91:以太網與曼徹斯特編碼 290
考點92:奈奎斯特定理和香農定理 291
考點93:電路交換、報文交換與分組交換 293
考點94:物理層接口和物理層設備 294
第3章 數據鏈路層 295
真題分布及命題重點 295
考點95:零比特填充法 295
考點96:流量控製、可靠傳輸與滑動窗口機製 296
考點97:隨機訪問介質訪問控製 298
考點98:局域網 301
考點99:以太網交換機及其工作原理 302
第4章 網 絡 層 304
真題分布及命題重點 304
考點100:IP數據報 304
考點101:子網劃分與子網掩碼、CIDR 307
考點102:ARP協議、ICMP協議與DHCP協議 313
考點103:路由協議 316
考點104:網絡層設備 317
第5章 傳 輸 層 318
真題分布及命題重點 318
考點105:TCP段的分析 318
考點106:TCP連接管理 321
考點107:TCP可靠傳輸 322
考點108:TCP流量控製與擁塞控製 323
考點109:UDP協議 325
第6章 應 用 層 326
真題分析及命題重點 326
考點110:域名係統DNS 326
考點111:文件傳送協議FTP 327
考點112:電子郵件EMAIL 328
考點113:萬維網WWW 329
參考文獻 332
前言/序言
《通往卓越之路:計算機科學深度探索與應試指南》 一、 時代背景與考試的重要性 2016年,信息技術浪潮洶湧澎湃,計算機科學作為引領時代發展的核心驅動力,其人纔培養的重要性日益凸顯。在這一背景下,專業的計算機基礎知識綜閤考試,不僅是對學生知識掌握程度的檢驗,更是對未來計算科學領域人纔儲備的一次重要評估。考試的含金量高,覆蓋麵廣,對考生未來的學術深造或職業發展都具有深遠影響。因此,深入理解考試的命題規律,掌握科學的應試方法,是每一位有誌於在計算機領域深耕的學子必須跨越的門檻。 二、 考試內容體係解析 本指南旨在為備考2016年計算機專業基礎綜閤考試的考生提供一套係統、詳實、富有洞察力的學習方案。考試內容涵蓋瞭計算機科學與技術學科的核心知識體係,主要可以歸納為以下幾個關鍵領域: 1. 數據結構與算法(Data Structures and Algorithms): 核心概念: 數據的邏輯結構和存儲結構,抽象數據類型(ADT),算法的定義、特性、復雜度分析(時間復雜度和空間復雜度)。 基本數據結構: 綫性結構: 數組、鏈錶(單鏈錶、雙嚮鏈錶、循環鏈錶)、棧、隊列。重點理解它們的實現方式、操作效率以及在不同場景下的應用。例如,如何利用棧實現錶達式求值或括號匹配,如何用鏈錶實現動態數組。 非綫性結構: 樹: 二叉樹(滿二叉樹、完全二叉樹)、二叉搜索樹(BST)、平衡二叉搜索樹(AVL樹、紅黑樹)、 B樹、 B+樹。深入理解樹的遍曆(前序、中序、後序、層序)、查找、插入、刪除等操作。特彆是平衡二叉搜索樹的維護機製,是考試的重點和難點。 圖: 圖的定義、錶示(鄰接矩陣、鄰接錶)、遍曆(深度優先搜索 DFS、廣度優先搜索 BFS)、連通性、最短路徑算法(Dijkstra、Floyd-Warshall)、最小生成樹算法(Prim、Kruskal)。理解圖的實際應用,如網絡路由、社交網絡分析等。 排序算法: 內部排序: 冒泡排序、選擇排序、插入排序、希爾排序、快速排序、歸並排序、堆排序。分析它們的穩定性、時間復雜度(最好、最壞、平均)和空間復雜度。重點掌握快排和歸並排序的遞歸思想,以及堆排序的堆結構操作。 外部排序: 多路歸並排序。 查找算法: 順序查找、摺半查找(二分查找)、散列查找(哈希錶)。理解散列函數的構造原則、衝突解決方法(鏈地址法、開放定址法)以及哈希錶的性能分析。 算法設計技巧: 分治法、動態規劃、貪心算法、迴溯法。理解它們的設計思想、適用條件以及如何將其應用於解決具體問題。動態規劃的子問題定義和狀態轉移方程是關鍵。 2. 操作係統原理(Operating System Principles): 操作係統概述: 操作係統的功能、作用、類型、發展曆史。 進程管理: 進程的概念、狀態、PCB(進程控製塊)、進程創建與終止、進程通信(IPC)、綫程的概念與區彆、進程調度算法(FCFS、SJF、RR、優先級調度、多級反饋隊列調度)。理解調度的目標(吞吐量、周轉時間、等待時間、響應時間)以及各種算法的優劣。 內存管理: 地址轉換(邏輯地址、物理地址)、內存分配方式(連續分配、非連續分配)、分頁(頁式管理)、分段(段式管理)、段頁式管理。虛擬內存技術(請求分頁、頁麵置換算法——LRU、FIFO、OPT、Clock算法)。理解頁麵置換算法的原理和性能評估。 文件管理: 文件、目錄(文件夾)、文件係統的概念,文件存儲空間管理(位示圖、空閑鏈錶),文件目錄結構(單級、兩級、樹形、無環圖),文件共享與保護。 設備管理: I/O設備、I/O控製方式(程序控製、中斷控製、DMA)、磁盤調度算法(FCFS、SSTF、SCAN、C-SCAN)。 死鎖: 死鎖的産生條件(互斥、占有並等待、不可搶占、循環等待)、死鎖的預防、避免(銀行傢算法)、檢測與解除。 3. 計算機網絡(Computer Networks): 網絡基本概念: 網絡組成、分類、拓撲結構、傳輸介質、通信綫路。 OSI參考模型與TCP/IP協議簇: 各層的功能、協議(如HTTP、FTP、SMTP、DNS、TCP、UDP、IP、ARP等)。深入理解各層協議的交互和數據傳輸過程。 物理層: 傳輸方式(串行/並行、同步/異步)、編碼、傳輸速率、信道復用技術(FDM、TDM、CDM)。 數據鏈路層: 差錯控製(檢錯、糾錯)、流量控製、介質訪問控製(MAC)——CSMA/CD(以太網)、CSMA/CA。PPP協議。 網絡層: IP地址(IPv4、IPv6)、子網劃分、NAT技術、路由選擇協議(RIP、OSPF、BGP)、ICMP協議。 傳輸層: TCP協議(三次握手、四次揮手、擁塞控製、流量控製)、UDP協議(特點、應用)。端口號。 應用層: DNS、HTTP、FTP、SMTP、POP3、IMAP等協議的原理和工作流程。 網絡安全基礎: 防火牆、加密技術。 4. 計算機組成原理(Computer Organization and Architecture): 計算機係統結構: 指令集體係結構(ISA)、存儲器層次結構。 運算器與控製器: 數據錶示: 原碼、反碼、補碼、移碼,浮點數錶示(IEEE 754)。 運算方法: 定點數運算(加法、減法、乘法、除法)、浮點數運算。 存儲器係統: 主存儲器(RAM、ROM)、高速緩存(Cache)的工作原理、映射方式(直接映射、全關聯映射、組關聯映射),虛擬存儲器。 指令係統: 指令格式、尋址方式、指令周期、指令流水綫。 I/O係統: I/O方式(程序查詢、中斷、DMA)、I/O接口。 5. 數據庫原理(Database Principles): 數據庫係統概述: 數據庫、數據庫管理係統(DBMS)、數據庫係統的組成。 關係模型: 關係、元組、屬性、碼、候選碼、主碼、外碼、函數依賴、多值依賴。 關係代數與SQL語言: 關係代數運算(選擇、投影、連接、除等),SQL查詢語言(SELECT, FROM, WHERE, GROUP BY, HAVING, ORDER BY, JOIN)。熟練掌握SQL語句的編寫。 數據庫設計: 需求分析、概念設計(ER模型)、邏輯設計(關係模式)、物理設計。 事務與並發控製: 事務的ACID特性,並發控製的基本原理(封鎖、時間戳),死鎖。 數據庫恢復: 事務故障、介質故障,恢復技術(延遲更新、立即更新)。 三、 學習策略與備考指導 1. 係統梳理,構建知識框架: 考試內容龐雜,切忌碎片化學習。建議考生首先對上述各個模塊的核心概念、原理和重要算法進行梳理,形成清晰的知識體係圖。可以利用思維導圖、流程圖等工具輔助記憶和理解。 2. 精讀教材,理解透徹: 選擇權威的教材(如《數據結構》嚴蔚敏版,《操作係統》張堯學版,《計算機網絡》謝希仁版,《計算機組成原理》唐朔飛版,《數據庫係統概念》或《數據庫係統原理》等)進行精讀。不僅要掌握概念,更要理解其背後的原理和設計思想。特彆是對於算法的推導、內存管理和網絡協議的工作流程,需要深入理解。 3. 重視算法,動手實踐: 數據結構與算法是計算機科學的基石。要熟練掌握各種數據結構的實現,理解常用算法(特彆是排序、查找、圖算法、動態規劃)的工作原理,並能分析其時間和空間復雜度。建議考生動手編寫代碼實現一些經典算法,加深理解。 4. 題型分析,規律把握: 深入研究曆年真題(包括但不限於2016年),分析考查的重點、難點、題型分布(選擇題、填空題、簡答題、綜閤應用題等)以及命題風格。通過大量練習,總結齣題規律,提高解題速度和準確率。 5. 重點突破,強化練習: 考試往往有其側重點。考生需要根據真題分析,識彆齣自己薄弱的環節,進行有針對性的強化練習。例如,如果某個年份的真題在操作係統死鎖部分考查較多,那麼在復習時就要給予足夠的重視。 6. 迴歸基礎,查漏補缺: 很多題目雖然看似復雜,但其本質仍然是基礎知識的應用。在備考過程中,要不斷迴歸課本,檢查自己是否存在知識盲點或理解誤區。 7. 模擬考試,實戰演練: 在臨近考試時,進行幾次完整的模擬考試,嚴格按照考試時間要求,模擬真實考試場景。這有助於考生調整考試狀態,熟悉考試流程,並能檢驗整體復習效果,及時發現問題。 8. 答題技巧,提升效率: 針對不同題型,掌握相應的答題技巧。例如,選擇題要審題仔細,排除法輔助;簡答題要條理清晰,重點突齣;綜閤題要分析完整,邏輯嚴密。 四、 展望與激勵 計算機科學的魅力在於其不斷的發展和創新。2016年的這場考試,不僅僅是對過去學習成果的一次檢驗,更是開啓未來探索之路的重要起點。通過紮實的知識儲備、科學的復習方法和持之以恒的努力,相信每一位考生都能在這場挑戰中脫穎而齣,為自己在計算機科學的道路上奠定堅實的基礎,迎接更廣闊的天地。願所有考生都能在通往卓越的道路上,收獲知識,實現夢想!