2021中國科學(xué)院大學(xué)計算機專業(yè)綜合專業(yè)研究生考試大綱 正文

中國科學(xué)院大學(xué)碩士研究生入學(xué)考試
《計算機專業(yè)綜合》考試大綱
 
一、考試方法和考試時間
閉卷，筆試，考試時間180分鐘，總分150分。
試卷共16道大題，每題15分，共240分，考生可以任意選擇其中10道大題回答，并在答題紙的該題答案前標明“選做本題”。
如果選做的題目多于10道，則判卷將按照所選做試題的題號順序選擇前10道大題計分，后續(xù)所做視為無效考試內(nèi)容。
 
 
二、試卷結(jié)構(gòu)
題型：概念題（填空、選擇、判斷、簡答），應(yīng)用題（計算、畫圖、分析、設(shè)計）等。
 
三、考試科目
數(shù)據(jù)結(jié)構(gòu)、計算機體系結(jié)構(gòu)、操作系統(tǒng)、編譯原理四門課程，每門課程各占25%左右。
 
四、考試內(nèi)容
I、計算機體系結(jié)構(gòu)部分
 
（一）考試大綱
 
1、計算機體系結(jié)構(gòu)概論
（1）計算機體系結(jié)構(gòu)的發(fā)展
（2）計算機系統(tǒng)層次結(jié)構(gòu)
計算機系統(tǒng)的基本組成，計算機硬件的基本組成，計算機軟件和硬件的關(guān)系，計算機的工作過程
（3）衡量計算機的指標
（4）計算機體系結(jié)構(gòu)的設(shè)計原則
2、指令系統(tǒng)結(jié)構(gòu)
（1）指令系統(tǒng)設(shè)計原則
（2）指令系統(tǒng)的演變
指令集分類，存儲管理，運行級別
（3）指令集結(jié)構(gòu)
指令集的分類，指令操作數(shù)的存儲，指令操作數(shù)的特征，指令操作和編碼，C語言的機器表示
（4）異常與中斷
異常分類，異常處理，中斷機制
（5）存儲管理
MIPS處理器對虛存系統(tǒng)的支持，LINUX操作系統(tǒng)的存儲管理
3、計算機硬件結(jié)構(gòu)
（1）計算機組成原理和結(jié)構(gòu)
馮諾依曼結(jié)構(gòu)，計算機硬件結(jié)構(gòu)的演進，處理器與IO間的通信，計算機系統(tǒng)主要組成部件
（2）計算機總線接口技術(shù)
片上總線，內(nèi)存總線，IO總線
（3）計算機系統(tǒng)啟動過程
處理器核初始化，總線接口初始化，設(shè)備探測及驅(qū)動加載
4、CPU微結(jié)構(gòu)
（1）二進制與邏輯電路
計算機中數(shù)的表示，CMOS邏輯電路
（2）簡單運算器設(shè)計
定點補碼加法，減法，比較，移位
（3）定點補碼乘法器
（4）指令流水線
處理器數(shù)據(jù)通路，五級流水處理器，解決指令相關(guān)
 
（二）計算機體系結(jié)構(gòu)部分考試要求
 
1、掌握從外部I/O與上層應(yīng)用交互的整體軟硬件過程
2、掌握基于MIPS處理器的Linux操作系統(tǒng)TLB例外過程
3、掌握C語言與指令系統(tǒng)的關(guān)系
4、掌握系統(tǒng)初始化時PCI設(shè)備的探測過程
5、掌握I/O通信中DMA傳輸過程
6、能讀懂CMOS電路，根據(jù)晶體管電路給出邏輯表達式
7、掌握先行進位加法器結(jié)構(gòu)及其verilog實現(xiàn)
8、掌握Booth編碼和華萊士樹
9、掌握指令流水線原理，了解解決相關(guān)的方法，能夠用時空圖表達流水線的運行
 
（三）主要參考書目
 
1、計算機體系結(jié)構(gòu)基礎(chǔ)、胡偉武等著;機械工業(yè)出版社，2017年。
 
 
 
II、 數(shù)據(jù)結(jié)構(gòu)
（一）考試大綱
 
1、緒論
（1）數(shù)據(jù)結(jié)構(gòu)的基本概念，數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)。
（2）算法的定義、算法的基本特性以及算法分析的基本概念。
 
2、線性表
（1）線性表的定義、基本操作。
（2）線性表的實現(xiàn)及應(yīng)用，包括順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)（單鏈表、循環(huán)鏈表和雙向鏈表）的構(gòu)造原理，在兩種存儲結(jié)構(gòu)上對線性表實施的主要的操作（三種鏈表的建立、插入和刪除、檢索等）的算法設(shè)計與實現(xiàn)。
 
3、堆棧與隊列
（1）堆棧與隊列的基本概念、基本操作。
（2）堆棧與隊列的順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)的構(gòu)造原理。
（3）在不同存儲結(jié)構(gòu)的基礎(chǔ)上對堆棧、隊列實施基本操作（插入與刪除等）對應(yīng)的算法設(shè)計與實現(xiàn)。
 
4、數(shù)組和廣義表
（1）數(shù)組的基本概念、多維數(shù)組的實現(xiàn)。
（2）對稱矩陣和稀疏矩陣的壓縮存儲。
（3）廣義表的基本概念。
 
5、樹與二叉樹
（1）樹的基本概念和性質(zhì)。
（2）二叉樹的基本概念、性質(zhì)。
（3）二叉樹的存儲，包括順序存儲、鏈式存儲結(jié)構(gòu)。
（4）二叉樹的遍歷。
（5）線索二叉樹的基本概念和構(gòu)造。
（6）樹和森林的存儲結(jié)構(gòu)、遍歷。
（7）哈夫曼（Huffman）樹和哈夫曼編碼。
 
6、圖
（1）圖的基本概念和性質(zhì)。
（2）圖的存儲，包括鄰接矩陣法、鄰接表法。
（3）圖的遍歷操作，包括深度優(yōu)先搜索、廣度優(yōu)先搜索。
（4）最小生成樹、最短路徑、關(guān)鍵路徑、拓撲排序算法的原理、實現(xiàn)和應(yīng)用。
 
7、查找
（1）順序查找法、分塊查找法、折半查找方法的原理、實現(xiàn)和應(yīng)用。
（2）二叉排序樹、平衡二叉樹、鍵樹的原理、實現(xiàn)和應(yīng)用。
（3）B樹及其基本操作、B+樹的基本概念。
（4）哈希（Hash）表的原理、實現(xiàn)和應(yīng)用。
（5）字符串模式匹配算法的原理和實現(xiàn)。
 
8、排序
（1）排序的基本概念。
（2）直接插入排序、折半插入排序、氣泡排序、簡單選擇排序、快速排序、堆排序、二路歸并排序、基數(shù)排序、外部排序算法的原理、實現(xiàn)和復(fù)雜度。
（3）排序算法的應(yīng)用。
 
（二）考試要求
 
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++語言設(shè)計與實現(xiàn)算法的能力。
 
（三）主要參考書目
 
1、數(shù)據(jù)結(jié)構(gòu)（C語言版）、 嚴蔚敏，吳偉民 編著，北京：清華大學(xué)出版社，2007年。
 
 
 
III、 編譯原理
（一） 考試大綱
 
1、編譯系統(tǒng)的概念和架構(gòu)
（1）編譯的概念、分類、編譯系統(tǒng)的組成
（2）程序設(shè)計語言的基礎(chǔ)知識、作用域、參數(shù)傳遞等
（3）四類形式文法的相關(guān)概念
（4）構(gòu)建編譯系統(tǒng)的相關(guān)科學(xué)以及編譯技術(shù)的應(yīng)用等
 
2、詞法分析
（1）詞法分析器的作用
（2）詞法符號的描述（包括正則式、正則定義等內(nèi)容）
（3）基于狀態(tài)轉(zhuǎn)換的詞法分析實現(xiàn)
（4）有限狀態(tài)自動機概念，正則表達式、NFA、DFA間的轉(zhuǎn)換，DFA的化簡
 
3、語法分析
（1）語法分析基礎(chǔ)，上下文無關(guān)文法、二義性文法
（2）文法的設(shè)計：二義性的消除、消除左遞歸、提取左因子等
（3）自上而下的分析方法、遞歸下降分析和非遞歸的預(yù)測分析器等
（4）自下而上的分析方法、LR分析
 
4、語法制導(dǎo)的翻譯
（1）屬性文法、繼承屬性和綜合屬性
（2）語法制導(dǎo)定義、求值順序
（3）語法制導(dǎo)翻譯的應(yīng)用
（4）語法制導(dǎo)的翻譯方案
（5）實現(xiàn)L屬性的SDD
 
5、中間代碼生成
（1）語法樹的變體、DAG
（2）三地址代碼
（3）類型和聲明的處理
（4）表達式的翻譯
（5）靜態(tài)類型檢查
（6）控制流的處理等
 
6、運行時環(huán)境
（1）存儲組織、靜態(tài)分配、棧式分配的基本概念等
（2）作用域的運行時實現(xiàn)、非局部名字的訪問等
 
7、目標代碼生成簡介
（1）代碼生成器設(shè)計中的問題
（2）目標代碼中的地址處理
（3）基本塊和流圖
（4）基本塊的優(yōu)化
（5）代碼生成器的簡單實現(xiàn)
（6）窺孔優(yōu)化
（7）寄存器分配和指派
（8）指令調(diào)度等
 
（二）考試要求
 
1、掌握編譯系統(tǒng)構(gòu)成的基本概念和相關(guān)原理
2、熟悉詞法分析的基礎(chǔ)理論，明晰正則式、正則定義、有限狀態(tài)自動機等基本概念以及相關(guān)轉(zhuǎn)換的方法，能夠按照要求構(gòu)造簡單的有限狀態(tài)自動機，并實施必要的變換
3、熟悉語法分析的基本理論，掌握上下文無關(guān)文法的基本概念、推導(dǎo)等，明晰文法、句子、語言之間的關(guān)系；能夠根據(jù)需要對文法進行必要的改寫（如消除二義性、消除左遞歸、提取左因子等）；對自上而下和自下而上的典型分析方法能夠熟悉其流程、構(gòu)建相關(guān)的分析表等
4、熟悉語法制導(dǎo)翻譯的典型方法（如語法制導(dǎo)定義、翻譯方案）及其基本概念（如繼承屬性、綜合屬性等），掌握S屬性和L屬性定義，并理解在語法分析框架中實現(xiàn)翻譯的方法和過程
5、能夠利用語法制導(dǎo)翻譯的理論指導(dǎo)中間代碼生成，對三地址代碼有基本了解，熟悉對典型語句的翻譯處理、理解類型檢查的原則和典型的靜態(tài)類型檢查的方法
6、熟悉運行時環(huán)境、存儲組織等的基本概念、熟悉對非局部名字訪問的處理方法
7、熟悉代碼生成的基本概念，對基本塊、流圖等有充分認識，對簡單的優(yōu)化方法（如DAG的優(yōu)化、窺孔優(yōu)化、寄存器分配、指令調(diào)度等）有初步了解
 
（三）主要參考書目
 
1、英文原版：《Compilers Principles, Techniques and Tools》Alfred V、 Aho, Monica S、 Lam, Ravi Sethi, Jeffrey D. Ullman, second edtion,機械工業(yè)出版社有影印版
2、英文原版的中譯本《編譯原理》；趙建華、鄭滔、戴新宇譯，機械工業(yè)出版社2009年1月，2015年10月第二次印刷
 
 
IV．操作系統(tǒng)
（一） 考試大綱
 
1、操作系統(tǒng)概述
（1）計算機基本構(gòu)成、處理器的內(nèi)部結(jié)構(gòu)、高速緩沖存儲器CACHE
（2）操作系統(tǒng)的概念、演變歷程、特性、分類、運行環(huán)境、功能
（3）系統(tǒng)調(diào)用的功能和過程。
2、進程
進程、進程描述、進程地址空間分布及進程狀態(tài)轉(zhuǎn)換
3、線程、對稱多處理SMP和微內(nèi)核
（1）線程的概念，定義線程的必要性和可能性；
（2）線程的功能特性與實現(xiàn)方式；
（3）操作系統(tǒng)的體系結(jié)構(gòu)（微內(nèi)核與巨內(nèi)核）及其性能分析。
4、處理器調(diào)度
（1）處理器的三種調(diào)度類型；
（2）進程調(diào)度的各種算法及其特點。
（3）多處理器對進程調(diào)度的影響
（4）實時進程的特點，限期調(diào)度和速率單調(diào)調(diào)度方法。
5、并發(fā)性
（1）并發(fā)性問題及相關(guān)概念，如臨界區(qū)、互斥、信號量和管程等；
（2）進程互斥、同步和通信的各種算法；
（3）死鎖的概念、死鎖的原因和條件
（4）死鎖的預(yù)防、避免和檢測算法。
6、存儲器管理
（1）分區(qū)存儲管理、覆蓋與交換；
（2）頁式管理及段式管理；
（3）段、頁式存儲管理方法及實現(xiàn)技術(shù)；
（4）虛存的原理及相關(guān)的各種算法和數(shù)據(jù)結(jié)構(gòu)。
7、設(shè)備管理和磁盤調(diào)度
（1）操作系統(tǒng)中輸入/輸出功能的組織；
（2）中斷處理；
（3）設(shè)備驅(qū)動程序、設(shè)備無關(guān)的軟件接口和spooling技術(shù)；
（4）緩沖策略；
（5）磁盤調(diào)度算法；
（6）磁盤陣列。
8、文件系統(tǒng)
（1）文件系統(tǒng)特點與文件組織方式；
（2）文件系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)；
（3）目錄的基本性質(zhì)及其實現(xiàn)方法；
（4）磁盤空間的管理。
（5）分布式文件系統(tǒng)
9、分布式系統(tǒng)
（1）分布式處理的特點、類型；
（2）機群系統(tǒng)。
10、操作系統(tǒng)安全
（1）操作系統(tǒng)安全保護目標及相關(guān)技術(shù)
（2）常見操作系統(tǒng)攻擊方法的原理和防護
 
（二）考試要求
 
1、了解操作系統(tǒng)所管轄的軟、硬件資源；了解操作系統(tǒng)的關(guān)鍵概念，從整體上把握操作系統(tǒng)的特性與功能等概念；建立操作系統(tǒng)的資源管理和應(yīng)用接口的職能概念。理解系統(tǒng)調(diào)用的執(zhí)行過程。
2、掌握進程的本質(zhì)特征，明確進程的動態(tài)特性，理解進程的地址空間分布，熟悉進程狀態(tài)間轉(zhuǎn)換的原因，建立進程是資源分配單元和一種運行實體的基本理念。
3、理解引入線程作為基本運行實體的必要性和可能性；掌握線程各種實現(xiàn)方式及其特點；熟悉SMP體系結(jié)構(gòu)、操作系統(tǒng)的體系結(jié)構(gòu)。
4、了解批處理、交互式、實時三種調(diào)度類型；重點掌握進程調(diào)度的各種算法及其適用環(huán)了解實時進程的本質(zhì)，掌握限期調(diào)度和速率單調(diào)調(diào)度方法。
5、靈活運用信號量、管程等技術(shù)解決互斥合同步問題；理解死鎖的概念和產(chǎn)生死鎖的充分必要條件；熟練掌握死鎖的預(yù)防、避免和檢測算法；了解處理死鎖問題時避免饑餓的方法。
6、理解存儲管理的功能及存儲管理對多道程序設(shè)計的支持；掌握段、頁式存儲管理方法及實現(xiàn)技術(shù)；掌握虛存的原理及相關(guān)的各種替換算法和數(shù)據(jù)結(jié)構(gòu)。
7、理解輸入輸出設(shè)備及操作系統(tǒng)中輸入/輸出功能的組織、掌握中斷處理、設(shè)備驅(qū)動程序、設(shè)備無關(guān)的軟件接口和spooling等技術(shù)，重點掌握各種用于提高性能的緩沖策略和磁盤調(diào)度算法；了解可提高性能和可靠性的各種磁盤陣列配置方式。
8、理解文件系統(tǒng)特點與文件組織，掌握文件系統(tǒng)的基本數(shù)據(jù)結(jié)構(gòu)，了解文件、目錄的基本性質(zhì)及其實現(xiàn)方法；重點掌握磁盤空間的管理、文件系統(tǒng)的性能及可靠性、文件系統(tǒng)的安全性及保護機制，分布式文件系統(tǒng)的問題和特點等。
9、了解分布式處理的特點、類型；掌握多層體系結(jié)構(gòu)和機群系統(tǒng)的基本概念和特點。
10、了解操作系統(tǒng)安全保密性、完整性和可用性的基本概念及保護方法。了解常用的攻擊和防御技術(shù)的原理。
 
（三）主要參考書目
 
1、《現(xiàn)代操作系統(tǒng)（第三版）》 Andrew S、 Tanenbaum ， 2008 
                                                     編制單位：中國科學(xué)院大學(xué)
編制日期：2019年6月8日
 

中國科學(xué)院大學(xué)

本文來源：http://m.zhongzhouzhikong.com/guokeda/cankaoshumu_377358.html