中科院研究生院2012年程序設計考研大綱

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

　　本《計算機軟件》考試大綱適用于中國科學院研究生院計算機科學與技術等專業的碩士研究生入學考試。計算機軟件是計算機科學與技術及相關學科的重要基礎，主要內容包括數據結構、編譯原理和操作系統三大部分。要求考生對計算機科學與技術及相關學科的基本概念有較深入、系統的理解，掌握各種數據結構的定義和實現算法，掌握操作系統和編譯原理所涉及的關鍵內容，并具有綜合運用所學知識分析問題和解決問題的能力。

　　一、考試內容

　　數據結構

　　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分析器