2019年中國科學院大學899計算機專業綜合考研初試大綱

• 2025考研復試伴學班
• 2025考研復試標準班
• 2026考研英語全程班
• 26考研全科上岸規劃營「擇校▪規劃▪備考」
• 中國科學院大學2025考研專業課復習資料「真題▪筆記▪講義▪題庫」

　

中國科學院大學碩士研究生入學考試

《計算機專業綜合》考試大綱

一、考試方法和考試時間

閉卷，筆試，考試時間180分鐘，總分150分。

試卷共16道大題，每題15分，共240分，考生可以任意選擇其中10道大題回答，并在答題紙的該題答案前標明“選做本題”。

如果選做的題目多于10道，則判卷將按照所選做試題的題號順序選擇前10道大題計分，后續所做視為無效考試內容。

二、試卷結構

題型：概念題(填空、選擇、判斷、簡答)，應用題(計算、畫圖、分析、設計)等。

三、考試科目

數據結構、計算機體系結構、操作系統、編譯原理四門課程，每門課程各占25%左右。

四、考試內容

I、計算機體系結構部分

(一)考試大綱

1、計算機體系結構概論

(1)計算機體系結構的發展

(2)計算機系統層次結構

計算機系統的基本組成，計算機硬件的基本組成，計算機軟件和硬件的關系，計算機的工作過程

(3)衡量計算機的指標

(4)計算機體系結構的設計原則

2、指令系統結構

(1)指令系統設計原則

(2)指令系統的演變

指令集分類，存儲管理，運行級別

(3)指令集結構

指令集的分類，指令操作數的存儲，指令操作數的特征，指令操作和編碼，C語言的機器表示

(4)異常與中斷

異常分類，異常處理，中斷機制

(5)存儲管理

MIPS處理器對虛存系統的支持，LINUX操作系統的存儲管理

3、計算機硬件結構

(1)計算機組成原理和結構

馮諾依曼結構，計算機硬件結構的演進，處理器與IO間的通信，計算機系統主要組成部件

(2)計算機總線接口技術

片上總線，內存總線，IO總線

(3)計算機系統啟動過程

處理器核初始化，總線接口初始化，設備探測及驅動加載

4、CPU微結構

(1)二進制與邏輯電路

計算機中數的表示，CMOS邏輯電路

(2)簡單運算器設計

定點補碼加法，減法，比較，移位

(3)定點補碼乘法器

(4)指令流水線

處理器數據通路，五級流水處理器，解決指令相關

(二)計算機體系結構部分考試要求

1、掌握從外部I/O與上層應用交互的整體軟硬件過程

2、掌握基于MIPS處理器的Linux操作系統TLB例外過程

3、掌握C語言與指令系統的關系

4、掌握系統初始化時PCI設備的探測過程

5、掌握I/O通信中DMA傳輸過程

6、能讀懂CMOS電路，根據晶體管電路給出邏輯表達式

7、掌握先行進位加法器結構及其verilog實現

8、掌握Booth編碼和華萊士樹

9、掌握指令流水線原理，了解解決相關的方法，能夠用時空圖表達流水線的運行

(三)主要參考書目

1、計算機體系結構基礎、胡偉武等著;機械工業出版社，2017年。

II、 數據結構

(一)考試大綱

1、緒論

(1)數據結構的基本概念，數據的邏輯結構、存儲結構。

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

2、線性表

(1)線性表的定義、基本操作。

(2)線性表的實現及應用，包括順序存儲結構、鏈式存儲結構(單鏈表、循環鏈表和雙向鏈表)的構造原理，在兩種存儲結構上對線性表實施的主要的操作(三種鏈表的建立、插入和刪除、檢索等)的算法設計與實現。

3、堆棧與隊列

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

(2)堆棧與隊列的順序存儲結構、鏈式存儲結構的構造原理。

(3)在不同存儲結構的基礎上對堆棧、隊列實施基本操作(插入與刪除等)對應的算法設計與實現。

4、數組和廣義表

(1)數組的基本概念、多維數組的實現。

(2)對稱矩陣和稀疏矩陣的壓縮存儲。

(3)廣義表的基本概念。

5、樹與二叉樹

(1)樹的基本概念和性質。

(2)二叉樹的基本概念、性質。

(3)二叉樹的存儲，包括順序存儲、鏈式存儲結構。

(4)二叉樹的遍歷。

(5)線索二叉樹的基本概念和構造。

(6)樹和森林的存儲結構、遍歷。

(7)哈夫曼(Huffman)樹和哈夫曼編碼。

6、圖

(1)圖的基本概念和性質。

(2)圖的存儲，包括鄰接矩陣法、鄰接表法。

(3)圖的遍歷操作，包括深度優先搜索、廣度優先搜索。

(4)最小生成樹、最短路徑、關鍵路徑、拓撲排序算法的原理、實現和應用。

7、查找

(1)順序查找法、分塊查找法、折半查找方法的原理、實現和應用。

(2)二叉排序樹、平衡二叉樹、鍵樹的原理、實現和應用。

(3)B樹及其基本操作、B+樹的基本概念。

(4)哈希(Hash)表的原理、實現和應用。

(5)字符串模式匹配算法的原理和實現。

8、排序

(1)排序的基本概念。

(2)直接插入排序、折半插入排序、氣泡排序、簡單選擇排序、快速排序、堆排序、二路歸并排序、基數排序、外部排序算法的原理、實現和復雜度。

(3)排序算法的應用。

(二)考試要求

1、掌握數據結構的基本概念、基本原理和基本方法。

2、掌握數據的邏輯結構、存儲結構及基本操作的實現，能夠對算法進行基本的時間復雜度與空間復雜度的分析。

3、能夠運用數據結構基本原理和方法進行問題的分析與求解，具備采用C或C++語言設計與實現算法的能力。

(三)主要參考書目

1、數據結構(C語言版)、 嚴蔚敏，吳偉民 編著，北京：清華大學出版社，2007年。

III、 編譯原理

(一) 考試大綱

1、編譯系統的概念和架構

(1)編譯的概念、分類、編譯系統的組成

(2)程序設計語言的基礎知識、作用域、參數傳遞等

(3)四類形式文法的相關概念

(4)構建編譯系統的相關科學以及編譯技術的應用等

2、詞法分析

(1)詞法分析器的作用

(2)詞法符號的描述(包括正則式、正則定義等內容)

(3)基于狀態轉換的詞法分析實現

(4)有限狀態自動機概念，正則表達式、NFA、DFA間的轉換，DFA的化簡

3、語法分析

(1)語法分析基礎，上下文無關文法、二義性文法

(2)文法的設計：二義性的消除、消除左遞歸、提取左因子等

(3)自上而下的分析方法、遞歸下降分析和非遞歸的預測分析器等

(4)自下而上的分析方法、LR分析

4、語法制導的翻譯

(1)屬性文法、繼承屬性和綜合屬性

(2)語法制導定義、求值順序

(3)語法制導翻譯的應用

(4)語法制導的翻譯方案

(5)實現L屬性的SDD

5、中間代碼生成

(1)語法樹的變體、DAG

(2)三地址代碼

(3)類型和聲明的處理

(4)表達式的翻譯

(5)靜態類型檢查

(6)控制流的處理等

6、運行時環境

(1)存儲組織、靜態分配、棧式分配的基本概念等

(2)作用域的運行時實現、非局部名字的訪問等

7、目標代碼生成簡介

(1)代碼生成器設計中的問題

(2)目標代碼中的地址處理

(3)基本塊和流圖

(4)基本塊的優化

(5)代碼生成器的簡單實現

(6)窺孔優化

(7)寄存器分配和指派

(8)指令調度等

(二)考試要求

1、掌握編譯系統構成的基本概念和相關原理

2、熟悉詞法分析的基礎理論，明晰正則式、正則定義、有限狀態自動機等基本概念以及相關轉換的方法，能夠按照要求構造簡單的有限狀態自動機，并實施必要的變換

3、熟悉語法分析的基本理論，掌握上下文無關文法的基本概念、推導等，明晰文法、句子、語言之間的關系;能夠根據需要對文法進行必要的改寫(如消除二義性、消除左遞歸、提取左因子等);對自上而下和自下而上的典型分析方法能夠熟悉其流程、構建相關的分析表等

4、熟悉語法制導翻譯的典型方法(如語法制導定義、翻譯方案)及其基本概念(如繼承屬性、綜合屬性等)，掌握S屬性和L屬性定義，并理解在語法分析框架中實現翻譯的方法和過程

5、能夠利用語法制導翻譯的理論指導中間代碼生成，對三地址代碼有基本了解，熟悉對典型語句的翻譯處理、理解類型檢查的原則和典型的靜態類型檢查的方法

6、熟悉運行時環境、存儲組織等的基本概念、熟悉對非局部名字訪問的處理方法

7、熟悉代碼生成的基本概念，對基本塊、流圖等有充分認識，對簡單的優化方法(如DAG的優化、窺孔優化、寄存器分配、指令調度等)有初步了解

(三)主要參考書目

1、英文原版：《Compilers Principles, Techniques and Tools》Alfred V、 Aho, Monica S、 Lam, Ravi Sethi, Jeffrey D. Ullman, second edtion,機械工業出版社有影印版

2、英文原版的中譯本《編譯原理》;趙建華、鄭滔、戴新宇譯，機械工業出版社2009年1月，2015年10月第二次印刷

IV.操作系統

(一) 考試大綱

1、操作系統概述

(1)計算機基本構成、處理器的內部結構、高速緩沖存儲器CACHE

(2)操作系統的概念、演變歷程、特性、分類、運行環境、功能

(3)系統調用的功能和過程。

2、進程

進程、進程描述、進程地址空間分布及進程狀態轉換

3、線程、對稱多處理SMP和微內核

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

(2)線程的功能特性與實現方式;

(3)操作系統的體系結構(微內核與巨內核)及其性能分析。

4、處理器調度

(1)處理器的三種調度類型;

(2)進程調度的各種算法及其特點。

(3)多處理器對進程調度的影響

(4)實時進程的特點，限期調度和速率單調調度方法。

5、并發性

(1)并發性問題及相關概念，如臨界區、互斥、信號量和管程等;

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

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

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

6、存儲器管理

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

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

(3)段、頁式存儲管理方法及實現技術;

(4)虛存的原理及相關的各種算法和數據結構。

7、設備管理和磁盤調度

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

(2)中斷處理;

(3)設備驅動程序、設備無關的軟件接口和spooling技術;

(4)緩沖策略;

(5)磁盤調度算法;

(6)磁盤陣列。

8、文件系統

(1)文件系統特點與文件組織方式;

(2)文件系統的數據結構;

(3)目錄的基本性質及其實現方法;

(4)磁盤空間的管理。

(5)分布式文件系統

9、分布式系統

(1)分布式處理的特點、類型;

(2)機群系統。

10、操作系統安全

(1)操作系統安全保護目標及相關技術

(2)常見操作系統攻擊方法的原理和防護

(二)考試要求

1、了解操作系統所管轄的軟、硬件資源;了解操作系統的關鍵概念，從整體上把握操作系統的特性與功能等概念;建立操作系統的資源管理和應用接口的職能概念。理解系統調用的執行過程。

2、掌握進程的本質特征，明確進程的動態特性，理解進程的地址空間分布，熟悉進程狀態間轉換的原因，建立進程是資源分配單元和一種運行實體的基本理念。

3、理解引入線程作為基本運行實體的必要性和可能性;掌握線程各種實現方式及其特點;熟悉SMP體系結構、操作系統的體系結構。

4、了解批處理、交互式、實時三種調度類型;重點掌握進程調度的各種算法及其適用環了解實時進程的本質，掌握限期調度和速率單調調度方法。

5、靈活運用信號量、管程等技術解決互斥合同步問題;理解死鎖的概念和產生死鎖的充分必要條件;熟練掌握死鎖的預防、避免和檢測算法;了解處理死鎖問題時避免饑餓的方法。

6、理解存儲管理的功能及存儲管理對多道程序設計的支持;掌握段、頁式存儲管理方法及實現技術;掌握虛存的原理及相關的各種替換算法和數據結構。

7、理解輸入輸出設備及操作系統中輸入/輸出功能的組織、掌握中斷處理、設備驅動程序、設備無關的軟件接口和spooling等技術，重點掌握各種用于提高性能的緩沖策略和磁盤調度算法;了解可提高性能和可靠性的各種磁盤陣列配置方式。

8、理解文件系統特點與文件組織，掌握文件系統的基本數據結構，了解文件、目錄的基本性質及其實現方法;重點掌握磁盤空間的管理、文件系統的性能及可靠性、文件系統的安全性及保護機制，分布式文件系統的問題和特點等。

9、了解分布式處理的特點、類型;掌握多層體系結構和機群系統的基本概念和特點。

10、了解操作系統安全保密性、完整性和可用性的基本概念及保護方法。了解常用的攻擊和防御技術的原理。

(三)主要參考書目

1、《現代操作系統(第三版)》 Andrew S、 Tanenbaum ， 2008