研究生入學考試計算機統(tǒng)考大綱

1、教正版圖書！2012年碩士研究生入學考試計算機學科考試大綱感謝王道會員手工錄入了這份大綱，任何組織和個人無權(quán)將其用于任何商業(yè)贏利為目的的活動！予人玫瑰，手有余香，王道論壇伴你一路同行！本文檔僅供學習和交流使用,任何組織和個人無權(quán)用于任何商業(yè)贏利活動！下載后 24 小時請刪除,請支持高教正版圖書！考試性質(zhì)計算機學科專業(yè)基礎(chǔ)綜合考試是為高等院校和科研院所招收計算機科學與技術(shù)學科的碩士研究生而設(shè)置的具有選拔性質(zhì)的聯(lián)考科目，其目的是科學、公平、有效地測試考生掌握計算機科學與技術(shù)學科大學本科階段專業(yè)基礎(chǔ)知識、基本理論、基本方法的水平和分析問題、解決問題的能力，評價的標準是高等院校計算機科學與技術(shù)學科優(yōu)秀

2、本科畢業(yè)生所能達到的及格或及格以上水平，以利于各高等院校和科研院所擇優(yōu)選拔，確保碩士研究生的招生質(zhì)量?？疾槟繕擞嬎銠C學科專業(yè)基礎(chǔ)綜合考試涵蓋數(shù)據(jù)機構(gòu)、計算機組成原理、操作系統(tǒng)和計算機網(wǎng)絡(luò)等學科專業(yè)基礎(chǔ)課程。要求考生比較系統(tǒng)地掌握上述專業(yè)基礎(chǔ)課程的概念、基本原理和基本方法，能夠綜合運用所學的基本原理和基本方法分析、判斷和解決有關(guān)理論問題和實際問題。考試形式和試卷結(jié)構(gòu)一、試卷滿分及考試時間本試卷滿分為 150 分，考試時間為 180 分鐘二、答題方式答題方式為閉卷、筆試三、試卷內(nèi)容結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 45 分計算機組成原理 45 分操作系統(tǒng) 35 分計算機網(wǎng)絡(luò) 25 分四、試卷題型結(jié)構(gòu)單項選擇題80 分

3、（40 小題，每小題 2 分）綜合應(yīng)用題 70 分本文檔僅供學習和交流使用,任何組織和個人無權(quán)用于任何商業(yè)贏利活動！下載后 24 小時請刪除,請支持高教正版圖書！考查內(nèi)容數(shù)據(jù)結(jié)構(gòu)【考查目標】1.掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、基本原理和基本方法；2.掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及基本操作的實現(xiàn)，能夠?qū)λ惴ㄟM行基本的時間復(fù)雜度與空間復(fù)雜度的分析。3.能夠運用數(shù)據(jù)結(jié)構(gòu)的基本原理和方法進行問題的分析與求解，具備采用 C 或 C+或 JAVA語言設(shè)計與實現(xiàn)算法的能力。一、線性表（一）線性表的定義和基本操作（二）線性表的實現(xiàn)1.順序存儲2.鏈式存儲3.線性表的應(yīng)用二、棧、隊列和數(shù)組（一）棧和隊列的基本概念（二）

4、棧和隊列的順序存儲結(jié)構(gòu)（三）棧和隊列的鏈式存儲結(jié)構(gòu)（四）棧和隊列的應(yīng)用（五）特殊矩陣的壓縮存儲三、樹與二叉樹（一）樹的基本概念（二）二叉樹1.二叉樹的定義及其主要特征2.二叉樹的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)3.二叉樹的遍歷4.線索二叉樹的基本概念和構(gòu)造（三）樹、森林1.樹的存儲結(jié)構(gòu)2.森林與二叉樹的轉(zhuǎn)換3.樹和森林的遍歷（四）樹與二叉樹的應(yīng)用1.二叉排序樹2.平衡二叉樹3.哈夫曼（Huffman）樹和哈夫曼編碼四、圖（一） 圖的基本概念（二） 圖的存儲及基本操作1. 鄰接矩陣法2. 鄰接表法（三） 圖的遍歷1. 深度優(yōu)先搜索2. 廣度優(yōu)先搜索（四） 圖的基本應(yīng)用1. 最?。ù鷥r）生成樹本文檔僅供

5、學習和交流使用,任何組織和個人無權(quán)用于任何商業(yè)贏利活動！下載后 24 小時請刪除,請支持高教正版圖書！2. 最短路徑3. 拓撲排序4. 關(guān)鍵路徑五、（一）（二）（三）（四）（五）（六）六、查找查找的基本概念順序查找法折半查找法B 樹及其基本操作、B+樹的基本概念散列（Hash）表查找算法的分析及應(yīng)用內(nèi)部排序（一） 排序的基本概念（二） 插入排序1. 直接插入排序2. 折半插入排序（三） 起泡排序（bubble sort）（四） 簡單選擇排序（五） 希爾排序（shell sort）（六） 快速排序（七） 堆排序（八） 二路歸并排序（merge sort）（九） 基數(shù)排序（十） 外部排序（十一）

6、各種排序算法的比較（十二） 排序算法的應(yīng)用本文檔僅供學習和交流使用,任何組織和個人無權(quán)用于任何商業(yè)贏利活動！下載后 24 小時請刪除,請支持高教正版圖書！計算機組成原理【考查目標】1. 理解單處理器計算機系統(tǒng)中各部件的內(nèi)部工作原理、組成結(jié)構(gòu)以及相互連接方式，具有完整的計算機系統(tǒng)的整機概念。2. 理解計算機系統(tǒng)層次化結(jié)構(gòu)概念，熟悉硬件與軟件之間的界面，掌握指令集體系結(jié)構(gòu)的基本知識和基本實現(xiàn)方法。3. 能夠綜合運用計算機組成的基本原理和基本方法，對有關(guān)計算機硬件系統(tǒng)中的理論和實際問題進行計算、分析，并能對一些基本部件進行簡單設(shè)計。一、計算機系統(tǒng)概述（一） 計算機發(fā)展歷程（二） 計算機系統(tǒng)層次結(jié)構(gòu)1

7、. 計算機硬件的基本組成2. 計算機軟件的分類3. 計算機的工作過程（三） 計算機性能指標吞吐量、響應(yīng)時間；CPU 時鐘周期、主頻、CPI、CPU 執(zhí)行時間；MIPS、MFLOPS。二、數(shù)據(jù)的表示和運算（一） 數(shù)制與編碼1. 進位計數(shù)制及其相互轉(zhuǎn)換2. 真值和機器數(shù)3. BCD 碼4. 字符與字符串5. 校驗碼（二） 定點數(shù)的表示和運算1. 定點數(shù)的表示無符號數(shù)的表示；有符號數(shù)的表示。2. 定點數(shù)的運算定點數(shù)的移位運算；原碼定點數(shù)的加/減運算；補碼定點數(shù)的加/減運算；定點數(shù)的乘/除運算；溢出概念和判別方法。（三） 浮點數(shù)的表示和運算1. 浮點數(shù)的表示IEEE754 標準2. 浮點數(shù)的加/減運算

8、（四） 算術(shù)邏輯單元 ALU1. 串行加法器和并行加法器2. 算術(shù)邏輯單元 ALU 的功能和結(jié)構(gòu)三、存儲器層次機構(gòu)（一） 存儲器的分類（二） 存儲器的層次化結(jié)構(gòu)（三） 半導(dǎo)體隨機存取存儲器1. SRAM 存儲器2. DRAM 存儲器3. 只讀存儲器4. Flash 存儲器（四） 主存儲器與 CPU 的連接（五） 雙口 RAM 和多模塊存儲器（六） 高速緩沖存儲器（Cache）本文檔僅供學習和交流使用,任何組織和個人無權(quán)用于任何商業(yè)贏利活動！下載后 24 小時請刪除,請支持高教正版圖書！1. Cache 的基本工作原理2. Cache 和主存之間的映射方式3. Cache 中主存塊的替換算法4.

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

10、址的形式方式。（五） 指令流水線1. 指令流水線的基本概念2. 指令流水線的基本實現(xiàn)3. 超標量和動態(tài)流水線的基本概念（六） 多核處理器的基本概念六、總線（一） 總線概述1. 總線的基本概念2. 總線的分類3. 總線的組成及性能指標（二） 總線仲裁1. 集中仲裁方式2. 分布仲裁方式（三） 總線操作和定時1. 同步定時方式2. 異步定時方式（四） 總線標準本文檔僅供學習和交流使用,任何組織和個人無權(quán)用于任何商業(yè)贏利活動！下載后 24 小時請刪除,請支持高教正版圖書！七、輸入輸出（I/O）系統(tǒng)（一） I/O 系統(tǒng)基本概念（二） 外部設(shè)備1. 輸入設(shè)備：鍵盤、鼠標2. 輸出設(shè)備：顯示器、打印機3.

11、 外存儲器：硬盤存儲器、磁盤陣列、光盤存儲器（三） I/O 接口（I/O 控制器）1. I/O 接口的功能和基本結(jié)構(gòu)2. I/O 端口及其編址3. I/O 地址空間及其編碼（四） I/O 方式1. 程序查詢方式2. 程序中斷方式中斷的基本概念；中斷響應(yīng)過程；中斷處理過程；多重中斷和中斷屏蔽的概念。3. DMA 方式DMA 控制器的組成；DMA 傳送過程。4. 通道方式本文檔僅供學習和交流使用,任何組織和個人無權(quán)用于任何商業(yè)贏利活動！下載后 24 小時請刪除,請支持高教正版圖書！操作系統(tǒng)【考查目標】1. 掌握操作系統(tǒng)的基本概念、基本原理和基本功能，理解操作系統(tǒng)的整體運行。2. 掌握操作系統(tǒng)進程、

12、內(nèi)存、文件和 I/O 管理的策略、算法、機制以及互相關(guān)系。3. 能夠運用所學的操作系統(tǒng)原理、方法與技術(shù)分析問題和解決問題，并能利用 C 語言描述相關(guān)算法。一、操作系統(tǒng)概述（一） 操作系統(tǒng)的概念、特征、功能和提供的服務(wù)（二） 操作系統(tǒng)的發(fā)展與分類（三） 操作系統(tǒng)的運行環(huán)境1. 內(nèi)核態(tài)與用戶態(tài)2. 中斷、異常3. 系統(tǒng)調(diào)用（四） 操作系統(tǒng)體系結(jié)構(gòu)二、進程管理（一） 進程與線程1. 進程概念2. 進程的狀態(tài)與轉(zhuǎn)換3. 進程控制4. 進程組織5. 進程通信共享存儲系統(tǒng)；消息傳遞系統(tǒng)；管道通信。6.線程概念與多線程模型（二）處理機調(diào)度1.調(diào)度的基本概念2.調(diào)度時機、切換與過程3.調(diào)度的基本準則4.調(diào)度方

13、式5.典型調(diào)度算法先來先服務(wù)調(diào)度算法；短作業(yè)（短進程、短線程）優(yōu)先調(diào)度算法；時間片輪轉(zhuǎn)調(diào)度算法；優(yōu)先級調(diào)度算法；高響應(yīng)比優(yōu)先調(diào)度算法；多級反饋隊列調(diào)度算法。（三）同步與互斥1. 進程同步的基本概念2. 實現(xiàn)臨界區(qū)互斥的基本方法軟件實現(xiàn)方法；硬件實現(xiàn)方法。3. 信號量4. 管程5. 經(jīng)典同步問題生產(chǎn)者-消費者問題；讀者-寫者問題；哲學家進餐問題。（四）死鎖1. 死鎖的概念2. 死鎖處理策略3. 死鎖預(yù)防4. 死鎖避免系統(tǒng)安全狀態(tài)：銀行家算法。5. 死鎖檢測和解除三、內(nèi)存管理本文檔僅供學習和交流使用,任何組織和個人無權(quán)用于任何商業(yè)贏利活動！下載后 24 小時請刪除,請支持高教正版圖書?。ㄒ唬?內(nèi)存

14、管理基礎(chǔ)1. 內(nèi)存管理概念程序裝入與鏈接；邏輯地址與物理地址空間；內(nèi)存保護。2. 交換與覆蓋3. 連續(xù)分配管理方式4. 非連續(xù)分配管理方式分頁管理方式；分段管理方式；段頁式管理方式。（二） 虛擬內(nèi)存管理1. 虛擬內(nèi)存基本概念2. 請求分頁管理方式3. 頁面置換算法最佳置換算法（OPT）；先進先出置換算法（FIFO）；最近最少使用置換算法（LRU）；時鐘置換算法（CLOCK）。4. 頁面分配策略5. 工作集6. 抖動四、文件管理（一） 文件系統(tǒng)基礎(chǔ)1. 文件概念2. 文件的邏輯結(jié)構(gòu)順序文件；索引文件；索引順序文件。3. 目錄結(jié)構(gòu)文件控制塊和索引節(jié)點；單級目錄結(jié)構(gòu)和兩級目錄結(jié)構(gòu)；樹形目錄結(jié)構(gòu)；圖形

15、目錄結(jié)構(gòu)。4. 文件共享5. 文件保護訪問類型；訪問控制。（二） 文件系統(tǒng)實現(xiàn)1. 文件系統(tǒng)層次結(jié)構(gòu)2. 目錄實現(xiàn)3. 文件實現(xiàn)（三） 磁盤組織與管理1. 磁盤的結(jié)構(gòu)2. 磁盤調(diào)度算法3. 磁盤的管理五、輸入輸出（I/O）管理（一） 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. 假脫機技術(shù)（SPOOLing）5. 出錯處理本文檔僅供學習和交流使用,任何組織和個人無權(quán)用于任何商業(yè)贏利活動！下載后 24 小時請刪除,請支持高教正版圖書！計算機網(wǎng)絡(luò)【考查目標】1. 掌握計算機網(wǎng)絡(luò)的基本概

16、念、基本原理和基本方法。2. 掌握計算機網(wǎng)絡(luò)的體系結(jié)構(gòu)和典型網(wǎng)絡(luò)協(xié)議，了解典型網(wǎng)絡(luò)的組成和特點，理解典型網(wǎng)絡(luò)設(shè)備的工作原理3. 能夠運用計算機網(wǎng)絡(luò)的基本概念、基本原理和基本方法進行網(wǎng)絡(luò)系統(tǒng)的分析、設(shè)計和應(yīng)用一、計算機網(wǎng)絡(luò)體系結(jié)構(gòu)（一） 計算機網(wǎng)絡(luò)概述1. 計算機網(wǎng)絡(luò)的概念、組成與功能2. 計算機網(wǎng)絡(luò)的分類3. 計算機網(wǎng)絡(luò)與互聯(lián)網(wǎng)的發(fā)展歷史4. 計算機網(wǎng)絡(luò)的標準化工作及相關(guān)組織（二） 計算機網(wǎng)絡(luò)體系結(jié)構(gòu)與參考模型1. 計算機網(wǎng)絡(luò)分層結(jié)構(gòu)2. 計算機網(wǎng)絡(luò)協(xié)議、接口、服務(wù)等概念3. ISO/OSI 參考模型和 TCP/IP 模型二、物理層（一） 通信基礎(chǔ)1. 信道、信號、帶寬、碼元、波特、速率、信源

17、與信宿等基本概念2. 奈奎斯特定理與香農(nóng)定理3. 編碼與調(diào)制4. 電路交換、報文交換與分組交換5. 數(shù)據(jù)報與虛電路（二） 傳輸介質(zhì)1. 雙絞線、同軸電纜、光纖與無線傳輸介質(zhì)2. 物理層接口的特性（三） 物理層設(shè)備1. 中繼器2. 集線器三、數(shù)據(jù)鏈路層（一） 數(shù)據(jù)鏈路層的功能（二） 組幀（三） 差錯控制1. 檢錯編碼2. 糾錯編碼（四） 流量控制與可靠傳輸機制1. 流量控制、可靠傳輸與滑動窗口機制2. 停止-等待協(xié)議3. 后退 N 幀協(xié)議（GBN）4. 選擇重傳協(xié)議（SR）（五） 介質(zhì)訪問控制1. 信道劃分介質(zhì)訪問控制頻分多路復(fù)用、時分多路復(fù)用、波分多路復(fù)用、碼分多路復(fù)用的概念和基本原理。2.

18、隨機訪問介質(zhì)訪問控制本文檔僅供學習和交流使用,任何組織和個人無權(quán)用于任何商業(yè)贏利活動！下載后 24 小時請刪除,請支持高教正版圖書！ALOHA 協(xié)議；CSMA 協(xié)議；CSMA/CD 協(xié)議；CSMA/CA 協(xié)議。3. 輪詢訪問介質(zhì)訪問控制：令牌傳遞協(xié)議（六） 局域網(wǎng)1. 局域網(wǎng)的基本概念與體系結(jié)構(gòu)2. 以太網(wǎng)與4. 令牌環(huán)網(wǎng)的基本原理（七） 廣域網(wǎng)1. 廣域網(wǎng)的基本概念2. PPP 協(xié)議3. HDLC 協(xié)議（八） 數(shù)據(jù)鏈路層設(shè)備1. 網(wǎng)橋的概念及其基本原理2. 局域網(wǎng)交換機及其工作原理。四、網(wǎng)絡(luò)層（一） 網(wǎng)絡(luò)層的功能1. 異構(gòu)網(wǎng)絡(luò)互聯(lián)2. 路由與轉(zhuǎn)發(fā)3. 擁塞控制（二） 路由算法1. 靜態(tài)路由與

19、動態(tài)路由2. 距離-向量路由算法3. 鏈路狀態(tài)路由算法4. 層次路由（三） IPv41. IPv4 分組2. IPv4 地址與 NAT3. 子網(wǎng)劃分與子網(wǎng)掩碼、CIDR4. ARP 協(xié)議、DHCP 協(xié)議與 ICMP 協(xié)議（四） IPv61. IPv6 的主要特點2. IPv6 地址（五） 路由協(xié)議1. 自治系統(tǒng)2. 域內(nèi)路由與域間路由3. RIP 路由協(xié)議4. OSPF 路由協(xié)議5. BGP 路由協(xié)議（六） IP 組播1. 組播的概念2. IP 組播地址（七） 移動 IP1. 移動 IP 的概念2. 移動 IP 的通信過程（八） 網(wǎng)絡(luò)層設(shè)備1. 路由器的組成和功能2. 路由表與路由轉(zhuǎn)發(fā)五、傳輸

20、層（一） 傳輸層提供的服務(wù)本文檔僅供學習和交流使用,任何組織和個人無權(quán)用于任何商業(yè)贏利活動！下載后 24 小時請刪除,請支持高教正版圖書！1. 傳輸層的功能2. 傳輸層尋址與端口3. 無連接服務(wù)與面向連接服務(wù)（二） UDP 協(xié)議1. UDP 數(shù)據(jù)報2. UDP 校驗（三） TCP 協(xié)議1. TCP 段2. TCP 連接管理3. TCP 可靠傳輸4. TCP 流量控制與擁塞控制六、應(yīng)用層（一） 網(wǎng)絡(luò)應(yīng)用模型1. 客戶/服務(wù)器模型2. P2P 模型（二） DNS 系統(tǒng)1. 層次域名空間2. 域名服務(wù)器3. 域名解析過程（三） FTP1. FTP 協(xié)議的工作原理2. 控制連接與數(shù)據(jù)連接（四） 電子郵

21、件1. 電子郵件系統(tǒng)的組成結(jié)構(gòu)2. 電子郵件格式與 MIME3. SMTP 協(xié)議與 POP3 協(xié)議（五） WWW1. WWW 的概念與組成結(jié)構(gòu)2. HTTP 協(xié)議本文檔僅供學習和交流使用,任何組織和個人無權(quán)用于任何商業(yè)贏利活動！下載后 24 小時請刪除,請支持高教正版圖書！附錄各位道友：目前已經(jīng)有越來越多的高校采用上機考試的形式來考察考生的實際動手編程能力，研究生復(fù)試上機將是未來的一個趨勢。為了方便各位道友練習機試，我們搭建了九度 Online Judge，并收集了全國各大高校的復(fù)試上機真題，希望能給大家復(fù)試上機考試提供強有力的支持。九度Online Judge（）正式開放，您可以直接使用王道

22、論壇的帳號進行登錄。如果您在使用過程中遇到問題，歡迎你到復(fù)試機試討論專區(qū)發(fā)貼提出。目前已經(jīng)收錄了我們能夠收集到的各高校上機復(fù)試真題，歡迎大家繼續(xù)向我們提供各高校上機真題，具體請聯(lián)系浩帆。此外，華科的上機題我們經(jīng)過了變形，將其中一些便于修改成 OJ 判題的題目收錄進了我們的 OJ。浙江大學2011 A+B for MatricesGradingMedianGraduate Admission2010 A+B2009 xxx定律2008又一版 A+BZOJ問題ZOJ歐拉回路奧運排序問題繼續(xù)xxx定律繼續(xù)暢通工程最短路徑問題尋找大富翁魔咒詞典二叉搜索樹找出直系親屬畢業(yè)bg2007最小長方形2006還

23、是A+B2005 A + B統(tǒng)計字符火星A+B最大連續(xù)子序列游船出租還是暢通工程暢通工程EXCEL排序統(tǒng)計同成績學生人數(shù)開門人和關(guān)門人暢通工程簡單計算器排名最大報銷額哈爾濱工業(yè)大學2011數(shù)組逆置最大公約數(shù)眾數(shù)20102009完數(shù)百雞問題數(shù)字階梯求和求最大值找x素數(shù)判定互換最大最小數(shù)判斷三角形類型字符串內(nèi)排序字符串去特定字符上海交通大學2011二次方程計算器整除問題2010后綴子串排序2009日期差值最短路徑取中值計算表達式字母統(tǒng)計最小面積子矩陣2008 Prime Number2007 Old Bill2006 Fibonacci2005數(shù)字反轉(zhuǎn)Simple SortingPowerful

24、CalculatorWERTYU路徑打印CoincidenceSum of FactorialsString Matching棋盤游戲Day of WeekZero-complexity Transposition2 的冪次方Pre-Post本文檔僅供學習和交流使用,任何組織和個人無權(quán)用于任何商業(yè)贏利活動！下載后 24 小時請刪除,請支持高教正版圖書！清華大學2011最小花費2010特殊乘法2009遞推數(shù)列2008手機鍵盤2007質(zhì)因數(shù)的個數(shù)2006 N的階乘2003球的半徑和體積約數(shù)的個數(shù)整數(shù)拆分代理服務(wù)器進制轉(zhuǎn)換10進制 VS 2進制最大序列和查找學生信息剩下的樹求root(N, k)最小郵票數(shù)二叉樹遍歷今年的第幾天？2002有多少不同的面值組合(第 楊輝三角形(第一 對稱平方數(shù)(第二 斐波那契數(shù)列(第二一套) 套) 套) 套)2001 分段函數(shù)(第一套)2000反序輸出整數(shù)和(第一套)abc反序數(shù)(第一套)完數(shù)VS盈數(shù)輸出梯形(第二套)成績排序字符串排序(第二 n的階乘 (第二套) 套)吉林大學2011字符串的反碼數(shù)字之和搬水果堆棧的使用連通圖北京大