中科院研究生院碩士研究生入學(xué)考試

　　《計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》考試大綱

　　一、考試內(nèi)容

　　數(shù)據(jù)結(jié)構(gòu)

　　1、緒論

　　(1)數(shù)據(jù)結(jié)構(gòu)的基本概念，數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)。

　　(2)算法的定義、算法的基本特性以及算法分析的基本概念。

　　2、線性表

　　(1)線性關(guān)系、線性表的定義，線性表的基本操作。

　　(2)線性表的順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(包括單鏈表、循環(huán)鏈表和雙向鏈表)的構(gòu)造原理。在以上兩種存儲(chǔ)結(jié)構(gòu)上對(duì)線性表實(shí)施的最主要的操作(包括三種鏈表的建立、插入和刪除、檢索等)的算法設(shè)計(jì)。

　　3、堆棧與隊(duì)列

　　(1)堆棧與隊(duì)列的基本概念、基本操作。

　　(2)堆棧與隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的構(gòu)造原理。

　　(3)在不同存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)上對(duì)堆棧與隊(duì)列實(shí)施插入與刪除等基本操作對(duì)應(yīng)的算法設(shè)計(jì)。

　　4、串

　　(1)串的基本概念、串的基本操作和存儲(chǔ)結(jié)構(gòu)。

　　(2)串的模式匹配算法和改進(jìn)的KMP算法

　　5、數(shù)組和廣義表

　　(1)數(shù)組的概念、多維數(shù)組的實(shí)現(xiàn)

　　(2)對(duì)稱(chēng)矩陣和稀疏矩陣的壓縮存儲(chǔ)

　　(3)廣義表的基本概念

　　6、樹(shù)與二叉樹(shù)

　　(1)樹(shù)的定義和性質(zhì)

　　(2)二叉樹(shù)的概念、性質(zhì)和實(shí)現(xiàn)

　　(3)遍歷二叉樹(shù)和線索二叉樹(shù)

　　(4)樹(shù)和森林

　　(5)赫夫曼樹(shù)及其應(yīng)用

　　(6)樹(shù)的計(jì)數(shù)

　　7、圖

　　(1)圖的定義，基本概念，圖的分類(lèi)，常用名詞術(shù)語(yǔ)。

　　(2)圖的鄰接矩陣存儲(chǔ)方法、鄰接表存儲(chǔ)方法的構(gòu)造原理。

　　(3)圖的遍歷操作。

　　(4)最小生成樹(shù)，最短路徑，AOV網(wǎng)與拓?fù)渑判颉?/P>

　　8、文件及查找

　　(1)數(shù)據(jù)文件的基本概念和基本術(shù)語(yǔ)，數(shù)據(jù)文件的基本操作。

　　(2)順序文件、索引文件、散列(Hash)文件。

　　(3)順序文件的順序查找方法、排序連續(xù)順序文件的折半查找方法以及其他文件的基本查找方法。

　　9、內(nèi)排序

　　(1)排序的基本概念，排序方法的分類(lèi)。

　　(2)插入排序法(含折半插入排序法)、選擇排序法、泡排序法、快速排序法、堆積排序法、歸并排序、基數(shù)排序。各種排序方法排序的原理、規(guī)律和特點(diǎn)，各種排序算法的時(shí)空復(fù)雜度簡(jiǎn)單分析。

　　操作系統(tǒng)

　　1、操作系統(tǒng)概述

　　(1)計(jì)算機(jī)基本構(gòu)成、處理器的內(nèi)部結(jié)構(gòu)、高速緩沖存儲(chǔ)器CACHE;

　　(2)操作系統(tǒng)的概念、演變歷程、特性、分類(lèi)、運(yùn)行環(huán)境、功能

　　(3)存儲(chǔ)器的層次結(jié)構(gòu)

　　2、進(jìn)程

　　進(jìn)程、進(jìn)程描述及進(jìn)程狀態(tài)轉(zhuǎn)換

　　3、線程、對(duì)稱(chēng)多處理SMP和微內(nèi)核

　　(1)線程的概念，定義線程的必要性和可能性;

　　(2)線程的功能特性與實(shí)現(xiàn)方式;

　　(3)對(duì)稱(chēng)多處理SMP體系結(jié)構(gòu);

　　(4)操作系統(tǒng)的體系結(jié)構(gòu)(微內(nèi)核與巨內(nèi)核)及其性能分析。

　　4、并發(fā)性

　　(1)并發(fā)性問(wèn)題及相關(guān)概念，如臨界區(qū)、互斥、信號(hào)量和管程等;

　　(2)進(jìn)程互斥、同步和通信的各種算法;

　　(3)死鎖的概念、死鎖的原因和條件

　　(4)死鎖的預(yù)防、避免和檢測(cè)算法。

　　5、存儲(chǔ)器管理

　　(1)分區(qū)存儲(chǔ)管理、覆蓋與交換;

　　(2)頁(yè)式管理及段式管理;

　　(3)段、頁(yè)式存儲(chǔ)管理方法及實(shí)現(xiàn)技術(shù);

　　(4)虛存的原理及相關(guān)的各種算法和數(shù)據(jù)結(jié)構(gòu)。

　　6、單處理器調(diào)度

　　(1)處理器的三種調(diào)度類(lèi)型;

　　(2)進(jìn)程調(diào)度的各種算法及其特點(diǎn)。

　　7、多處理器調(diào)度和實(shí)時(shí)調(diào)度

　　(1)多處理器對(duì)進(jìn)程調(diào)度的影響

　　(2)多處理器環(huán)境下的進(jìn)程和線程調(diào)度算法;

　　(3)實(shí)時(shí)進(jìn)程的特點(diǎn);

　　(4)限期調(diào)度和速率單調(diào)調(diào)度方法。

　　8、設(shè)備管理和磁盤(pán)調(diào)度

　　(1)操作系統(tǒng)中輸入/輸出功能的組織;

　　(2)中斷處理;

　　(3)設(shè)備驅(qū)動(dòng)程序、設(shè)備無(wú)關(guān)的軟件接口和spooling技術(shù);

　　(4)緩沖策略;

　　(5)磁盤(pán)調(diào)度算法;

　　(6)磁盤(pán)陣列。

　　9、文件系統(tǒng)

　　(1)文件系統(tǒng)特點(diǎn)與文件組織方式;

　　(2)文件系統(tǒng)的數(shù)據(jù)結(jié)構(gòu);

　　(3)目錄的基本性質(zhì)及其實(shí)現(xiàn)方法;

　　(4)磁盤(pán)空間的管理。

　　10、分布式系統(tǒng)

　　(1)分布式處理的特點(diǎn)、類(lèi)型;

　　(2)多層體系結(jié)構(gòu)、中間件技術(shù);

　　(3)機(jī)群系統(tǒng);

　　(4)分布式進(jìn)程管理相關(guān)的操作系統(tǒng)設(shè)計(jì)問(wèn)題。

　　計(jì)算機(jī)組成原理

　　1. 計(jì)算機(jī)系統(tǒng)概述

　　(1)計(jì)算機(jī)系統(tǒng)簡(jiǎn)介

　　(2)計(jì)算機(jī)的軟硬件概念，計(jì)算機(jī)組成、體系結(jié)構(gòu)及工作過(guò)程

　　2. 計(jì)算機(jī)的發(fā)展史和基本概念

　　3. 系統(tǒng)總線

　　(1)總線的基本概念

　　(2)總線的分類(lèi)、結(jié)構(gòu)及特性

　　(3)總線接口

　　(4)總線的仲裁和數(shù)據(jù)傳送模式

　　(5)典型系統(tǒng)總線

　　4. 存儲(chǔ)器

　　(1)存儲(chǔ)器的分類(lèi)和層次結(jié)構(gòu)

　　(2)隨機(jī)讀寫(xiě)存儲(chǔ)器、只讀存儲(chǔ)器、閃速存儲(chǔ)器、高速存儲(chǔ)器、高速緩沖存儲(chǔ)器和虛擬存儲(chǔ)器

　　(3)主存儲(chǔ)器、高速緩沖存儲(chǔ)器和輔助存儲(chǔ)器的工作原理和校驗(yàn)

　　5. 輸入輸出系統(tǒng)

　　(1)基本的輸入輸出設(shè)備及工作原理

　　(2)程序查詢(xún)方式

　　(3)中斷方式

　　(4)DMA方式

　　6.計(jì)算機(jī)的運(yùn)算方法

　　(1)計(jì)算機(jī)中數(shù)的概念和表示方法

　　(2)無(wú)符號(hào)數(shù)和有符號(hào)數(shù)

　　(3)數(shù)的定點(diǎn)和浮點(diǎn)表示

　　(4)定點(diǎn)運(yùn)算

　　(5)浮點(diǎn)運(yùn)算

　　(6)定點(diǎn)運(yùn)算器

　　(7)浮點(diǎn)運(yùn)算器

　　7. 指令系統(tǒng)

　　(1)計(jì)算機(jī)指令系統(tǒng)概述

　　(2)指令格式

　　(3)操作數(shù)類(lèi)型

　　(4)指令和數(shù)據(jù)的尋址方式

　　(5)典型指令

　　(6)RISC技術(shù)

　　8. CPU

　　(1)CPU的功能和結(jié)構(gòu)

　　(2)指令執(zhí)行周期

　　(3)指令流水線

　　(4)中斷系統(tǒng)

　　9. 控制單元

　　(1)控制單元的功能

　　(2)控制單元的設(shè)計(jì)和實(shí)現(xiàn)

　　二、考試要求

　　數(shù)據(jù)結(jié)構(gòu)

　　1、 建立有關(guān)數(shù)據(jù)結(jié)構(gòu)最基本的概念，包括數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和算法，算法分析的基本概念與基本方法

　　2、 掌握線性表的基本概念以及兩種存儲(chǔ)結(jié)構(gòu)的構(gòu)造原理，掌握在各種存儲(chǔ)結(jié)構(gòu)下對(duì)線性表進(jìn)行的基本操作的算法設(shè)計(jì)。

　　3、 掌握堆棧和隊(duì)列的基本概念與特征，掌握在兩種存儲(chǔ)結(jié)構(gòu)下如何對(duì)堆棧和隊(duì)列進(jìn)行插入和刪除等操作，以及利用堆棧與隊(duì)列解決實(shí)際問(wèn)題的基本方法。

　　4、 充分了解串的基本概念、掌握串的存儲(chǔ)結(jié)構(gòu)和相關(guān)的操作算法。

　　5、 掌握數(shù)組、廣義表和稀疏矩陣的基本概念，物理結(jié)構(gòu)和基本操作的實(shí)現(xiàn)

　　6、 充分了解樹(shù)型結(jié)構(gòu)的邏輯特征，掌握各種存儲(chǔ)結(jié)構(gòu)的構(gòu)造原理，能夠熟練地利用常用的三種遍歷方法，掌握利用二叉樹(shù)的遍歷操作解決實(shí)際問(wèn)題的方法，掌握二叉排序樹(shù)的建立以及在二叉排序樹(shù)中查找一個(gè)結(jié)點(diǎn)存在與否的過(guò)程。

　　7、 充分了解圖的邏輯結(jié)構(gòu)的特點(diǎn)，掌握常用的兩種存儲(chǔ)方法，掌握最小生成樹(shù)(Prim算法和Kruskal算法)、最短路徑、拓?fù)渑判虻木唧w求解過(guò)程。

　　8、 充分了解各種順序文件的結(jié)構(gòu)與相應(yīng)的查找方法;了解各種查找算法之間時(shí)空效率的差異;從結(jié)構(gòu)與操作上了解散列文件的建立、散列函數(shù)的選擇(構(gòu)造)原則、處理散列沖突的方法以及在散列文件中查找一個(gè)記錄存在與否的過(guò)程。

　　9、 充分了解各種排序方法的排序特點(diǎn)和排序過(guò)程，對(duì)于任意給出的數(shù)據(jù)元素序列，能夠熟練地采用指定排序方法進(jìn)行排序，并且能夠?qū)γ恳环N排序方法排序過(guò)程中所進(jìn)行的元素之間的比較次數(shù)、相應(yīng)排序算法的時(shí)間、空間、排序的穩(wěn)定性等性能進(jìn)行簡(jiǎn)單分析。

　　操作系統(tǒng)

　　1、 了解操作系統(tǒng)所管轄的軟、硬件資源;了解操作系統(tǒng)的關(guān)鍵概念，從整體上把握操作系統(tǒng)的特性與功能等概念;建立操作系統(tǒng)的資源管理和應(yīng)用接口的職能概念。

　　2、 掌握進(jìn)程的本質(zhì)特征，明確進(jìn)程的動(dòng)態(tài)特性，熟悉進(jìn)程狀態(tài)間轉(zhuǎn)換的原因，建立進(jìn)程是資源分配單元和一種運(yùn)行實(shí)體的基本理念。

　　3、 理解引入線程作為基本運(yùn)行實(shí)體的必要性和可能性;掌握線程各種實(shí)現(xiàn)方式及其特點(diǎn);熟悉SMP體系結(jié)構(gòu)、操作系統(tǒng)的體系結(jié)構(gòu)(微內(nèi)核與巨內(nèi)核)。

　　4、 能夠利用信號(hào)量、管程等技術(shù)解決互斥合同步問(wèn)題;理解死鎖的概念和產(chǎn)生死鎖的充分必要條件;熟練掌握死鎖的預(yù)防、避免和檢測(cè)算法;了解處理死鎖問(wèn)題時(shí)避免饑餓的方法。

　　5、 了解存儲(chǔ)管理的功能及存儲(chǔ)管理對(duì)多道程序設(shè)計(jì)的支持;掌握段、頁(yè)式存儲(chǔ)管理方法及實(shí)現(xiàn)技術(shù); 重點(diǎn)掌握虛存的原理及相關(guān)的各種算法和數(shù)據(jù)結(jié)構(gòu)。

　　6、 了解長(zhǎng)程、中程和短程三種調(diào)度類(lèi)型;重點(diǎn)掌握進(jìn)程調(diào)度的各種算法及其適用環(huán)境。

　　7、 了解調(diào)度粒度的概念，熟悉多處理器環(huán)境下進(jìn)程和線程調(diào)度算法，了解實(shí)時(shí)進(jìn)程的本質(zhì)，掌握限期調(diào)度和速率單調(diào)調(diào)度方法。

　　8、 了解輸入輸出設(shè)備及操作系統(tǒng)中輸入/輸出功能的組織、掌握中斷處理、設(shè)備驅(qū)動(dòng)程序、設(shè)備無(wú)關(guān)的軟件接口和spooling等技術(shù)，重點(diǎn)掌握各種用于提高性能的緩沖策略和磁盤(pán)調(diào)度算法;了解可提高性能和可靠性的各種磁盤(pán)陣列配置方式。

　　9、 了解文件系統(tǒng)特點(diǎn)與文件組織，掌握文件系統(tǒng)的基本數(shù)據(jù)結(jié)構(gòu)，了解文件、目錄的基本性質(zhì)及其實(shí)現(xiàn)方法;重點(diǎn)掌握磁盤(pán)空間的管理、文件系統(tǒng)的性能及可靠性、文件系統(tǒng)的安全性及保護(hù)機(jī)制等。

　　10、 了解分布式處理的特點(diǎn)、類(lèi)型;掌握多層體系結(jié)構(gòu)、中間件技術(shù)和機(jī)群系統(tǒng)的基本概念和特點(diǎn);重點(diǎn)掌握進(jìn)程遷移、分布式全局狀態(tài)的認(rèn)定、分布式互斥與死鎖預(yù)防等技術(shù)。

　　計(jì)算機(jī)組成原理

　　1. 1. 掌握計(jì)算機(jī)的基本概念，層次結(jié)構(gòu)和硬件框圖，以及馮•諾伊曼計(jì)算機(jī)的基本特點(diǎn)

　　2. 掌握計(jì)算機(jī)總線的基本概念，分類(lèi)和結(jié)構(gòu)及特性，總線仲裁方式的基本工作原理和特點(diǎn)，了解PCI總線的特點(diǎn)

　　3. 熟練掌握存儲(chǔ)系統(tǒng)的分類(lèi)和層次結(jié)構(gòu)，掌握主存儲(chǔ)器、Cache和輔助存儲(chǔ)器的工作原理，了解主存儲(chǔ)器容量擴(kuò)張方法、Cache訪問(wèn)過(guò)程，計(jì)算硬盤(pán)的容量和訪問(wèn)時(shí)間計(jì)算方法

　　4. 熟悉基本的輸入輸出設(shè)備及工作原理，掌握程序查詢(xún)、中斷和DMA這三種方式的工作過(guò)程、關(guān)聯(lián)性和優(yōu)缺點(diǎn)，了解定時(shí)方式、信息交換方式的工作原理和特點(diǎn)

　　5. 掌握計(jì)算機(jī)中數(shù)據(jù)的格式，機(jī)器數(shù)的表示方法和特點(diǎn)，了解IEEE 754的內(nèi)容及定點(diǎn)和浮點(diǎn)運(yùn)算方法

　　6. 了解海明碼、CRC碼和奇偶校驗(yàn)等編碼方法的概念及生成算法

　　7. 掌握計(jì)算機(jī)指令系統(tǒng)的概念和格式，熟悉常見(jiàn)指令的意義、編碼和尋址方式

　　8. 了解RISC和CISC的定義和區(qū)別

　　9. 熟悉CPU的功能、結(jié)構(gòu)和各部分的工作流程，掌握指令執(zhí)行周期的概念和指令流水線的分析

　　10. 熟悉控制單元的設(shè)計(jì)和實(shí)現(xiàn)，掌握組合邏輯和時(shí)序邏輯的特點(diǎn)和區(qū)別

　　三、主要參考書(shū)目

　　1、《數(shù)據(jù)結(jié)構(gòu)》嚴(yán)蔚敏，清華大學(xué)出版社;2001

　　2、《計(jì)算機(jī)組成原理》(第二版)，唐朔飛，高等教育出版社，2008年

　　3、計(jì)算機(jī)組成原理(第四版)，白中英等編著，科學(xué)出版社，2007年

　　4、William Stallings. Operating Systems: Internals and Design Principles. Fourth Edition, Prentice Hall. 2001

　　5、《計(jì)算機(jī)操作系統(tǒng)》，湯子瀛，西安電子科技大學(xué)出版社。2002

　　相關(guān)推薦：

　　學(xué)位授予和人才培養(yǎng)學(xué)科目錄(2011年)

　　2012年考研招生簡(jiǎn)章、目錄及書(shū)目專(zhuān)題 

　　各個(gè)專(zhuān)業(yè)的全國(guó)頂尖高校排名情況統(tǒng)計(jì)名單