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

中國(guó)科學(xué)院大學(xué)碩士研究生入學(xué)考試
《計(jì)算機(jī)專(zhuān)業(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ì)算、畫(huà)圖、分析、設(shè)計(jì)）等。
 
三、考試科目
數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)體系結(jié)構(gòu)、操作系統(tǒng)、編譯原理四門(mén)課程，每門(mén)課程各占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)的演變
指令集分類(lèi)，存儲(chǔ)管理，運(yùn)行級(jí)別
（3）指令集結(jié)構(gòu)
指令集的分類(lèi)，指令操作數(shù)的存儲(chǔ)，指令操作數(shù)的特征，指令操作和編碼，C語(yǔ)言的機(jī)器表示
（4）異常與中斷
異常分類(lèi)，異常處理，中斷機(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ī)總線(xiàn)接口技術(shù)
片上總線(xiàn)，內(nèi)存總線(xiàn)，IO總線(xiàn)
（3）計(jì)算機(jī)系統(tǒng)啟動(dòng)過(guò)程
處理器核初始化，總線(xiàn)接口初始化，設(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）指令流水線(xiàn)
處理器數(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、掌握指令流水線(xiàn)原理，了解解決相關(guān)的方法，能夠用時(shí)空?qǐng)D表達(dá)流水線(xiàn)的運(yùn)行
 
（三）主要參考書(shū)目
 
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、線(xiàn)性表
（1）線(xiàn)性表的定義、基本操作。
（2）線(xiàn)性表的實(shí)現(xiàn)及應(yīng)用，包括順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（單鏈表、循環(huán)鏈表和雙向鏈表）的構(gòu)造原理，在兩種存儲(chǔ)結(jié)構(gòu)上對(duì)線(xiàn)性表實(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ēng)矩陣和稀疏矩陣的壓縮存儲(chǔ)。
（3）廣義表的基本概念。
 
5、樹(shù)與二叉樹(shù)
（1）樹(shù)的基本概念和性質(zhì)。
（2）二叉樹(shù)的基本概念、性質(zhì)。
（3）二叉樹(shù)的存儲(chǔ)，包括順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。
（4）二叉樹(shù)的遍歷。
（5）線(xiàn)索二叉樹(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)算法的能力。
 
（三）主要參考書(shū)目
 
1、數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）、 嚴(yán)蔚敏，吳偉民 編著，北京：清華大學(xué)出版社，2007年。
 
 
 
III、 編譯原理
（一） 考試大綱
 
1、編譯系統(tǒng)的概念和架構(gòu)
（1）編譯的概念、分類(lèi)、編譯系統(tǒng)的組成
（2）程序設(shè)計(jì)語(yǔ)言的基礎(chǔ)知識(shí)、作用域、參數(shù)傳遞等
（3）四類(lèi)形式文法的相關(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）類(lèi)型和聲明的處理
（4）表達(dá)式的翻譯
（5）靜態(tài)類(lèi)型檢查
（6）控制流的處理等
 
6、運(yùn)行時(shí)環(huán)境
（1）存儲(chǔ)組織、靜態(tài)分配、棧式分配的基本概念等
（2）作用域的運(yùn)行時(shí)實(shí)現(xiàn)、非局部名字的訪(fǎng)問(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)行必要的改寫(xiě)（如消除二義性、消除左遞歸、提取左因子等）；對(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ǔ)句的翻譯處理、理解類(lèi)型檢查的原則和典型的靜態(tài)類(lèi)型檢查的方法
6、熟悉運(yùn)行時(shí)環(huán)境、存儲(chǔ)組織等的基本概念、熟悉對(duì)非局部名字訪(fǎng)問(wèn)的處理方法
7、熟悉代碼生成的基本概念，對(duì)基本塊、流圖等有充分認(rèn)識(shí)，對(duì)簡(jiǎn)單的優(yōu)化方法（如DAG的優(yōu)化、窺孔優(yōu)化、寄存器分配、指令調(diào)度等）有初步了解
 
（三）主要參考書(shū)目
 
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)的概念、演變歷程、特性、分類(lèi)、運(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、線(xiàn)程、對(duì)稱(chēng)多處理SMP和微內(nèi)核
（1）線(xiàn)程的概念，定義線(xiàn)程的必要性和可能性；
（2）線(xiàn)程的功能特性與實(shí)現(xiàn)方式；
（3）操作系統(tǒng)的體系結(jié)構(gòu)（微內(nèi)核與巨內(nèi)核）及其性能分析。
4、處理器調(diào)度
（1）處理器的三種調(diào)度類(lèi)型；
（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è)備管理和磁盤(pán)調(diào)度
（1）操作系統(tǒng)中輸入/輸出功能的組織；
（2）中斷處理；
（3）設(shè)備驅(qū)動(dòng)程序、設(shè)備無(wú)關(guān)的軟件接口和spooling技術(shù)；
（4）緩沖策略；
（5）磁盤(pán)調(diào)度算法；
（6）磁盤(pán)陣列。
8、文件系統(tǒng)
（1）文件系統(tǒng)特點(diǎn)與文件組織方式；
（2）文件系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)；
（3）目錄的基本性質(zhì)及其實(shí)現(xiàn)方法；
（4）磁盤(pán)空間的管理。
（5）分布式文件系統(tǒng)
9、分布式系統(tǒng)
（1）分布式處理的特點(diǎn)、類(lèi)型；
（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、理解引入線(xiàn)程作為基本運(yùn)行實(shí)體的必要性和可能性；掌握線(xiàn)程各種實(shí)現(xiàn)方式及其特點(diǎn)；熟悉SMP體系結(jié)構(gòu)、操作系統(tǒng)的體系結(jié)構(gòu)。
4、了解批處理、交互式、實(shí)時(shí)三種調(diào)度類(lèi)型；重點(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)掌握各種用于提高性能的緩沖策略和磁盤(pán)調(diào)度算法；了解可提高性能和可靠性的各種磁盤(pán)陣列配置方式。
8、理解文件系統(tǒng)特點(diǎn)與文件組織，掌握文件系統(tǒng)的基本數(shù)據(jù)結(jié)構(gòu)，了解文件、目錄的基本性質(zhì)及其實(shí)現(xiàn)方法；重點(diǎn)掌握磁盤(pán)空間的管理、文件系統(tǒng)的性能及可靠性、文件系統(tǒng)的安全性及保護(hù)機(jī)制，分布式文件系統(tǒng)的問(wèn)題和特點(diǎn)等。
9、了解分布式處理的特點(diǎn)、類(lèi)型；掌握多層體系結(jié)構(gòu)和機(jī)群系統(tǒng)的基本概念和特點(diǎn)。
10、了解操作系統(tǒng)安全保密性、完整性和可用性的基本概念及保護(hù)方法。了解常用的攻擊和防御技術(shù)的原理。
 
（三）主要參考書(shū)目
 
1、《現(xiàn)代操作系統(tǒng)（第三版）》 Andrew S、 Tanenbaum ， 2008 
                                                     編制單位：中國(guó)科學(xué)院大學(xué)
編制日期：2019年6月8日
 

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

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