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

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

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

本文來(lái)源：http://www.lyhuahuisp.com/guokeda/cankaoshumu_377358.html