中國科學院研究生院《計算機軟件基礎》2011年考研大綱

中科院研究生院碩士研究生入學考試
　　《計算機軟件基礎》考試大綱

　　本《計算機軟件》考試大綱適用于中國科學院研究生院計算機科學與技術等專業的碩士研究生入學考試。計算機軟件是計算機科學與技術及相關學科的重要基礎，主要內容包括數據結構、編譯原理和操作系統三大部分。要求考生對計算機科學與技術及相關學科的基本概念有較深入、系統的理解，掌握各種數據結構的定義和實現算法，掌握操作系統和編譯原理所涉及的關鍵內容，并具有綜合運用所學知識分析問題和解決問題的能力。
　　一、考試內容
　　數據結構
　　1、緒論
　　（1）數據結構的基本概念，數據的邏輯結構、存儲結構。
　　（2）算法的定義、算法的基本特性以及算法分析的基本概念。
　　2、線性表
　　（1）線性關系、線性表的定義，線性表的基本操作。
　　（2）線性表的順序存儲結構與鏈式存儲結構(包括單鏈表、循環鏈表和雙向鏈表)的構造原理。在以上兩種存儲結構上對線性表實施的比較主要的操作(包括三種鏈表的建立、插入和刪除、檢索等)的算法設計。
　　3、堆棧與隊列
　　（1）堆棧與隊列的基本概念、基本操作。
　　（2）堆棧與隊列的順序存儲結構與鏈式存儲結構的構造原理。
　　（3）在不同存儲結構的基礎上對堆棧與隊列實施插入與刪除等基本操作對應的算法設計。
　　4、串
　　（1）串的基本概念、串的基本操作和存儲結構。
　　（2）串的模式匹配算法和改進的KMP算法
　　5、數組和廣義表
　　（1）數組的概念、多維數組的實現
　　（2）對稱矩陣和稀疏矩陣的壓縮存儲
　　（3）廣義表的基本概念
　　6、樹與二叉樹
　　（1）樹的定義和性質
　　（2）二叉樹的概念、性質和實現
　　（3）遍歷二叉樹和線索二叉樹
　　（4）樹和森林
　　（5）赫夫曼樹及其應用
　　（6）樹的計數
　　7、圖
　　（1）圖的定義，基本概念，圖的分類，常用名詞術語。
　　（2）圖的鄰接矩陣存儲方法、鄰接表存儲方法的構造原理。
　　（3）圖的遍歷操作。
　　（4）比較小生成樹，比較短路徑，AOV網與拓撲排序。
　　8、文件及查找
　　（1）數據文件的基本概念和基本術語，數據文件的基本操作。
　　（2）順序文件、索引文件、散列(Hash)文件。
　　（3）順序文件的順序查找方法、排序連續順序文件的折半查找方法以及其他文件的基本查找方法。
　　9、內排序
　　（1）排序的基本概念，排序方法的分類。
　　（2）插入排序法(含折半插入排序法)、選擇排序法、泡排序法、快速排序法、堆積排序法、歸并排序、基數排序。各種排序方法排序的原理、規律和特點，各種排序算法的時空復雜度簡單分析。
　　操作系統
　　1、操作系統概述
　　（1）計算機基本構成、處理器的內部結構、高速緩沖存儲器CACHE；
　　（2）操作系統的概念、演變歷程、特性、分類、運行環境、功能
　　（3）存儲器的層次結構
　　2、、進程
　　進程、進程描述及進程狀態轉換
　　3、線程、對稱多處理SMP和微內核
　　（1）線程的概念，定義線程的必要性和可能性；
　　（2）線程的功能特性與實現方式；
　　（3）對稱多處理SMP體系結構；
　　（4）操作系統的體系結構（微內核與巨內核）及其性能分析。
　　4、并發性
　　（1）并發性問題及相關概念，如臨界區、互斥、信號量和管程等；
　　（2）進程互斥、同步和通信的各種算法；
　　（3）死鎖的概念、死鎖的原因和條件
　　（4）死鎖的預防、避免和檢測算法。
　　5、存儲器管理
　　（1）分區存儲管理、覆蓋與交換；
　　（2）頁式管理及段式管理；
　　（3）段、頁式存儲管理方法及實現技術；
　　（4）虛存的原理及相關的各種算法和數據結構。
　　6、單處理器調度
　　（1）處理器的三種調度類型；
　　（2）進程調度的各種算法及其特點。
　　7、多處理器調度和實時調度
　　（1）多處理器對進程調度的影響
　　（2）多處理器環境下的進程和線程調度算法；
　　（3）實時進程的特點；
　　（4）限期調度和速率單調調度方法。
　　8、設備管理和磁盤調度
　　（1）操作系統中輸入/輸出功能的組織；
　　（2）中斷處理；
　　（3）設備驅動程序、設備無關的軟件接口和spooling技術；
　　（4）緩沖策略；
　　（5）磁盤調度算法；
　　（6）磁盤陣列。
　　9、文件系統
　　（1）文件系統特點與文件組織方式；
　　（2）文件系統的數據結構；
　　（3）目錄的基本性質及其實現方法；
　　（4）磁盤空間的管理。
　　10、分布式系統
　　（1）分布式處理的特點、類型；
　　（2）多層體系結構、中間件技術；
　　（3）機群系統；
　　（4）分布式進程管理相關的操作系統設計問題。
　　編譯原理
　　1、引論
　　（1）編譯器的基本概念
　　（2）編譯階段和編譯器伙伴
　　2、詞法分析
　　（1）詞法分析器
　　（2）正規式
　　（3）有限自動機和掃描器生成器
　　3、語法分析
　　（1）上下文無關文法
　　（2）各種語法分析技術，如自上而下分析和自下而上分析，LR分析器
　　4、語法制導的翻譯
　　（1）S屬性和L屬性
　　（2）自上而下翻譯
　　（3）繼承屬性的自上而下計算
　　（4）遞歸計算
　　5、類型檢查
　　（1）類型體制
　　（2）簡單類型檢查器
　　（3）類型表達式的等價
　　（4）函數和算符的重載
　　6、運行環境
　　運行時存儲空間和組織管理
　　7、中間代碼生成
　　（1）常用的中間代碼表示：后綴表示、圖形表示和三地址表示
　　（2）聲明、賦值和布爾表達式
　　8、代碼生成
　　（1）代碼生成涉及的主要問題
　　（2）目標機器
　　（3）基本塊和流圖
　　9、代碼優化
　　（1）優化的主要種類
　　（2）流圖中的循環
　　（3）全局數據流分析介紹
　　（4）代碼改進變換

　　二、考試要求
　　數據結構
　　1、 建立有關數據結構比較基本的概念，包括數據的邏輯結構、存儲結構和算法，算法分析的基本概念與基本方法
　　2、 掌握線性表的基本概念以及兩種存儲結構的構造原理，掌握在各種存儲結構下對線性表進行的基本操作的算法設計。
　　3、 掌握堆棧和隊列的基本概念與特征，掌握在兩種存儲結構下如何對堆棧和隊列進行插入和刪除等操作，以及利用堆棧與隊列解決實際問題的基本方法。
　　4、 充分了解串的基本概念、掌握串的存儲結構和相關的操作算法。
　　5、 掌握數組、廣義表和稀疏矩陣的基本概念，物理結構和基本操作的實現
　　6、 充分了解樹型結構的邏輯特征，掌握各種存儲結構的構造原理，能夠熟練地利用常用的三種遍歷方法，掌握利用二叉樹的遍歷操作解決實際問題的方法，掌握二叉排序樹的建立以及在二叉排序樹中查找一個結點存在與否的過程。
　　7、 充分了解圖的邏輯結構的特點，掌握常用的兩種存儲方法，掌握比較小生成樹(Prim算法和Kruskal算法)、比較短路徑、拓撲排序的具體求解過程。
　　8、 充分了解各種順序文件的結構與相應的查找方法；了解各種查找算法之間時空效率的差異；從結構與操作上了解散列文件的建立、散列函數的選擇(構造)原則、處理散列沖突的方法以及在散列文件中查找一個記錄存在與否的過程。
　　9、 充分了解各種排序方法的排序特點和排序過程，對于任意給出的數據元素序列，能夠熟練地采用指定排序方法進行排序，并且能夠對每一種排序方法排序過程中所進行的元素之間的比較次數、相應排序算法的時間、空間、排序的穩定性等性能進行簡單分析。
　　操作系統
　　1、 了解操作系統所管轄的軟、硬件資源；了解操作系統的關鍵概念，從整體上把握操作系統的特性與功能等概念；建立操作系統的資源管理和應用接口的職能概念。
　　2、 掌握進程的本質特征，明確進程的動態特性，熟悉進程狀態間轉換的原因，建立進程是資源分配單元和一種運行實體的基本理念。
　　3、 理解引入線程作為基本運行實體的必要性和可能性；掌握線程各種實現方式及其特點；熟悉SMP體系結構、操作系統的體系結構。
　　4、 靈活運用信號量、管程等技術解決互斥合同步問題；理解死鎖的概念和產生死鎖的充分必要條件；熟練掌握死鎖的預防、避免和檢測算法；了解處理死鎖問題時避免饑餓的方法。
　　5、 理解存儲管理的功能及存儲管理對多道程序設計的支持；掌握段、頁式存儲管理方法及實現技術；掌握虛存的原理及相關的各種算法和數據結構。
　　6、 了解長程、中程和短程三種調度類型；重點掌握進程調度的各種算法及其適用環境。
　　7、 熟悉掌握多處理器環境下進程和線程調度算法，了解實時進程的本質，掌握限期調度和速率單調調度方法。
　　8、 理解輸入輸出設備及操作系統中輸入/輸出功能的組織、掌握中斷處理、設備驅動程序、設備無關的軟件接口和spooling等技術，重點掌握各種用于提高性能的緩沖策略和磁盤調度算法；了解可提高性能和可靠性的各種磁盤陣列配置方式。
　　9、 理解文件系統特點與文件組織，掌握文件系統的基本數據結構，了解文件、目錄的基本性質及其實現方法；重點掌握磁盤空間的管理、文件系統的性能及可靠性、文件系統的安全性及保護機制等。
　　10、 了解分布式處理的特點、類型；掌握多層體系結構、中間件技術和機群系統的基本概念和特點；重點掌握進程遷移、分布式全局狀態的認定、分布式互斥與死鎖預防等技術。
　　編譯原理
　　1、 了解編譯器的基本概念和基本結構
　　2、 了解詞法分析器的作用，掌握記號的描述和識別方法，掌握識別有限自動機的基本定義和從正規式建立識別器的方法
　　3、 了解語法分析器的作用，掌握上下文無關語言和文法的相關概念和性質，掌握各種語法分析技術，如自上而下分析，自下而上分析，以及LR分析器。
　　4、 掌握上下文無關文法制導下的語言翻譯，
　　5、 了解類型體制的基本概念，了解簡單類型檢查器和類型表達式的等價
　　6、 了解程序的運行時存儲空間和組織管理
　　7、 了解中間代碼的表示，了解程序設計語言的結構如何翻譯成中間形式
　　8、 了解代碼生成中涉及的基本問題，包括存儲管理、指令選擇、寄存器分配和計算次序選擇等基本問題
　　9、 掌握代碼優化的主要種類和代碼改進變換。
　　三、主要參考書目
　　1、《數據結構》嚴蔚敏，清華大學出版社；2002
　　2、《編譯原理和技術》，陳意云，中國科學技術大學出版社；2003
　　3、《計算機操作系統》，湯子瀛，西安電子科技大學出版社。2002