2020年《計算機原理》的考試說明

《2020年《計算機原理》的考試說明》由會員分享，可在線閱讀，更多相關(guān)《2020年《計算機原理》的考試說明（7頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 《計算機原理》的考試說明 《計算機原理》考試大綱 本《計算機原理》考試大綱適用于中國科學(xué)院研究生院計算機科學(xué)與技術(shù)等專業(yè)的碩士研究生入學(xué)考試。 計算機原理是計算機科學(xué)與技術(shù)及相關(guān)學(xué)科的重要基礎(chǔ)， 主要內(nèi)容包括數(shù)據(jù)結(jié)構(gòu)和計算機組成原理兩大部分。要求考生對計算機科學(xué)與技術(shù)及相關(guān)學(xué)科的基本概念有較深入、系統(tǒng)的理解，掌握各種數(shù)據(jù)結(jié)構(gòu)的定義和實現(xiàn)算法，掌握計算機組成原理所涉及的關(guān)鍵內(nèi)容， 并具有綜合運用所學(xué)知識分析問題和解決問題的能力。 一、考試內(nèi)容數(shù)據(jù)結(jié)構(gòu) 1 、緒論 （ 1）數(shù)據(jù)結(jié)構(gòu)的基本概念，數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)。

2、 （ 2）算法的定義、算法的基本特性以及算法分析的基本概念。 2 、線性表 （ 1）線性關(guān)系、線性表的定義，線性表的基本操作。 （ 2）線性表的順序存儲結(jié)構(gòu)與鏈式存儲結(jié)構(gòu) ( 包括單鏈表、循環(huán)鏈表和雙向鏈表 ) 的構(gòu)造原理。在以上兩種存儲結(jié)構(gòu)上對線性表實施的最主要的操作 ( 包括三種鏈表的建立、 插入和刪除、檢索等 ) 的算法設(shè)計。 3 、堆棧與隊列 （ 1）堆棧與隊列的基本概念、基本操作。 （ 2）堆棧與隊列的順序存儲結(jié)構(gòu)與鏈式存儲結(jié)構(gòu)的構(gòu)造原理。 （ 3）在不同存儲結(jié)構(gòu)的基礎(chǔ)上對堆棧與隊列實施插入與刪除等

3、基本操作對應(yīng)的算法設(shè)計。 4 、串 （ 1）串的基本概念、串的基本操作和存儲結(jié)構(gòu)。 （ 2）串的模式匹配算法和改進的 KMP算法 5 、數(shù)組和廣義表 （ 1）數(shù)組的概念、多維數(shù)組的實現(xiàn) （ 2）對稱矩陣和稀疏矩陣的壓縮存儲 （ 3）廣義表的基本概念 6 、樹與二叉樹 （ 1）樹的定義和性質(zhì) （ 2）二叉樹的概念、性質(zhì)和實現(xiàn) （ 3）遍歷二叉樹和線索二叉樹 （ 4）樹和森林 （ 5）赫夫曼樹及其應(yīng)用 （ 6）樹的計數(shù) 7 、圖 （ 1

4、）圖的定義，基本概念，圖的分類，常用名詞術(shù)語。 （ 2）圖的鄰接矩陣存儲方法、鄰接表存儲方法的構(gòu)造原理。 （ 3）圖的遍歷操作。 （ 4）最小生成樹，最短路徑， AOV網(wǎng)與拓撲排序。 8 、文件及查找 （ 1）數(shù)據(jù)文件的基本概念和基本術(shù)語，數(shù)據(jù)文件的基本操作。 （ 2）順序文件、索引文件、散列 (Hash) 文件。 （ 3）順序文件的順序查找方法、 排序連續(xù)順序文件的折半查找方法以及其他文件的基本查找方法。 9 、內(nèi)排序 （ 1）排序的基本概念，排序方法的分類。 （ 2）插入

5、排序法 ( 含折半插入排序法 ) 、選擇排序法、泡排序法、快速排序法、堆積排序法、歸并排序、基數(shù)排序。各種排序方法排序的原理、規(guī)律和特點，各種排序算法的時空復(fù)雜度簡單分析。 計算機組成原理 一．計算機系統(tǒng)概論 （ 1）計算機的分類 （ 2）計算機的硬件 （ 3）計算機的軟件 （ 4）計算機系統(tǒng)的層次結(jié)構(gòu) 二．運算方法和運算器 （ 1）數(shù)據(jù)與文字的表示方法 （ 2）定點加法、減法運算 （ 3）定點乘法運算 （ 4）定點除法運算 （ 5）定點運算器的組成 （ 6）浮點運

6、算方法和浮點運算器 三．存儲系統(tǒng) （ 1）存儲器概述 （ 2）隨機讀寫存儲器 （ 3）只讀存儲器和閃速存儲器 （ 4）高速存儲器 （ 5）cache 存儲器 （ 6）虛擬存儲器 四．指令系統(tǒng) （ 1）指令系統(tǒng)的發(fā)展與性能要求 （ 2）指令格式 （ 3）指令和數(shù)據(jù)的尋址方式 （ 4）堆棧尋址方式 （ 5）典型指令 五．中央處理器 （ 1）CPU的功能和組成 （ 2）指令周期 （ 3）時序產(chǎn)生器和控制方式

7、 （ 4）微程序控制器 （ 5）微程序設(shè)計技術(shù) （ 6）硬布線控制器 （ 7）流水 CPU （ 8）RISCCPU 六．總線系統(tǒng) （ 1）總線的概念和結(jié)構(gòu)形態(tài) （ 2）總線接口 （ 3）總線的仲裁定時和數(shù)據(jù)傳送模式 （ 4）PCI 總線 （ 5）ASI 總線 七．外圍設(shè)備 （ 1）外圍設(shè)備概述 （ 2）顯示設(shè)備 （ 3）輸入設(shè)備 （ 4）硬磁盤存儲設(shè)備 （ 5）軟磁盤存儲設(shè)備 （ 6）光盤存儲設(shè)備 八

8、．輸入輸出系統(tǒng) （ 1）外圍設(shè)備的定時方式與信息交換方式 （ 2）程序中斷方式 （ 3）DMA方式 （ 4）通道方式 二、考試要求數(shù)據(jù)結(jié)構(gòu) 1 、掌握有關(guān)數(shù)據(jù)結(jié)構(gòu)的基本概念，包括數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲 結(jié)構(gòu)。 2 、掌握算法的基本概念以及算法分析的基本方法。 3 、掌握線性表的基本概念， 在兩種存儲結(jié)構(gòu)下的構(gòu)造原理及相應(yīng)的操作； 4 、掌握堆棧和隊列的基本概念與特征以及在兩種存儲結(jié)構(gòu)下如何對堆棧和隊列進行插入和刪除等操作， 具備使用堆棧與隊列解決實際問題的能力。 5 、掌

9、握串的基本概念以及串的存儲結(jié)構(gòu)和相關(guān)的算法。 6 、掌握數(shù)組、廣義表和稀疏矩陣的基本概念以及基本操作。 7 、掌握樹型結(jié)構(gòu)的邏輯特征以及各種存儲結(jié)構(gòu)的構(gòu)造原理， 能夠熟練使用基于樹的三種遍歷方法。 8 、掌握二叉排序樹的邏輯特征、建立過程，具備使用其解決實際問題的能力。 8 、了解圖的邏輯結(jié)構(gòu)的特點以及常用的兩種存儲方法， 了解最 小生成樹 (Prim 算法和 Kruskal 算法 ) 、最短路徑、拓撲排序的具體 求解過程。 9 、掌握各種順序文件的結(jié)構(gòu)與相應(yīng)的查找方法以及各種查找算 法之間時空效率的差異；了解散列

10、文件的建立、散列函數(shù)的選擇 ( 構(gòu)造) 原則、處理散列沖突的方法以及基于散列的查找。 10 、掌握各種排序方法的排序特點和排序過程，能夠?qū)γ恳环N 排序方法在時間、空間、排序的穩(wěn)定性等方面進行簡單分析。 計算機組成原理 1 、掌握計算機的層次結(jié)構(gòu)及軟硬件組成等概念。 2 、掌握計算機中數(shù)據(jù)的格式、機器數(shù)的表示方法和特點，掌握定點加減的運算方法和特點，掌握浮點運算方法和特點。 3 、掌握存儲系統(tǒng)的分類、分級結(jié)構(gòu)與主存儲器的技術(shù)指標(biāo)；了解 SRAM、DRAM、EPROM、閃速存儲器、相聯(lián)存儲器的工作原理；掌握 Ca

11、che存儲器、虛擬存儲器的功能和基本工作原理。 4 、掌握指令格式、指令和數(shù)據(jù)的尋址方式，了解 RISC和 CISC 的特點。 5 、掌握 CPU的功能、基本組成和各個部分的工作流程；了解微程序控制器的基本工作原理， 了解微程序控制技術(shù)和硬布線控制技術(shù)；了解流水 CPU的工作原理及特點。 6 、掌握總線系統(tǒng)的基本概念和基本技術(shù)以及總線仲裁方式的基本工作原來和特點，了解 PCI 和 ISA 總線的特點。 7 、掌握顯示設(shè)備、打印設(shè)備、硬盤的工作原理和特點，能夠計算一些常用的技術(shù)指標(biāo)。 8 、掌握外圍設(shè)備的定時方式、 信息交換方式的工作原理和特點，了解程序查詢方式、中斷方式和 DMA方式原理，了解通道方式。 三、主要參考書目 1 、數(shù)據(jù)結(jié)構(gòu)（C語言版），嚴蔚敏，清華大學(xué)出版社 ,1997 年； 2 、計算機組成原理，白中英，科學(xué)出版社， 2000 年，第三版。