《計(jì)算機(jī)原理》的考試說(shuō)明

　　《計(jì)算機(jī)原理》考試大綱

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

　　一、考試內(nèi)容 數(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)性關(guān)系、線(xiàn)性表的定義，線(xiàn)性表的基本操作。

　�。� 2 ）線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ( 包括單鏈表、循環(huán)鏈表和雙向鏈表 ) 的構(gòu)造原理。在以上兩種存儲(chǔ)結(jié)構(gòu)上對(duì)線(xiàn)性表實(shí)施的最主要的操作 ( 包括三種鏈表的建立、插入和刪除、檢索等 ) 的算法設(shè)計(jì)。

　　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ì)。

　　4 、串

　�。� 1 ）串的基本概念、串的基本操作和存儲(chǔ)結(jié)構(gòu)。

　�。� 2 ）串的模式匹配算法和改進(jìn)的 KMP 算法

　　5 、數(shù)組和廣義表

　�。� 1 ）數(shù)組的概念、多維數(shù)組的實(shí)現(xiàn)

　�。� 2 ）對(duì)稱(chēng)矩陣和稀疏矩陣的壓縮存儲(chǔ)

　�。� 3 ）廣義表的基本概念

　　6 、樹(shù)與二叉樹(shù)

　�。� 1 ）樹(shù)的定義和性質(zhì)

　�。� 2 ）二叉樹(shù)的概念、性質(zhì)和實(shí)現(xiàn)

　�。� 3 ）遍歷二叉樹(shù)和線(xiàn)索二叉樹(shù)

　�。� 4 ）樹(shù)和森林

　�。� 5 ）赫夫曼樹(shù)及其應(yīng)用

　　（ 6 ）樹(shù)的計(jì)數(shù)

　　7 、圖

　　（ 1 ）圖的定義，基本概念，圖的分類(lèi)，常用名詞術(shù)語(yǔ)。

　　（ 2 ）圖的鄰接矩陣存儲(chǔ)方法、鄰接表存儲(chǔ)方法的構(gòu)造原理。

　�。� 3 ）圖的遍歷操作。

　�。� 4 ）最小生成樹(shù)，最短路徑， AOV 網(wǎng)與拓?fù)渑判颉?/p>

　　8 、文件及查找

　�。� 1 ）數(shù)據(jù)文件的基本概念和基本術(shù)語(yǔ)，數(shù)據(jù)文件的基本操作。

　�。� 2 ）順序文件、索引文件、散列 (Hash) 文件。

　�。� 3 ）順序文件的順序查找方法、排序連續(xù)順序文件的折半查找方法以及其他文件的基本查找方法。

　　9 、內(nèi)排序

　�。� 1 ）排序的基本概念，排序方法的分類(lèi)。

　�。� 2 ）插入排序法 ( 含折半插入排序法 ) 、選擇排序法、泡排序法、快速排序法、堆積排序法、歸并排序、基數(shù)排序。各種排序方法排序的原理、規(guī)律和特點(diǎn)，各種排序算法的時(shí)空復(fù)雜度簡(jiǎn)單分析。

　　計(jì)算機(jī)組成原理

　　一．計(jì)算機(jī)系統(tǒng)概論

　�。� 1 ）計(jì)算機(jī)的分類(lèi)

　　（ 2 ）計(jì)算機(jī)的硬件

　�。� 3 ）計(jì)算機(jī)的軟件

　　（ 4 ）計(jì)算機(jī)系統(tǒng)的層次結(jié)構(gòu)

　　二． 運(yùn)算方法和運(yùn)算器

　　（ 1 ）數(shù)據(jù)與文字的表示方法

　�。� 2 ）定點(diǎn)加法、減法運(yùn)算

　　（ 3 ）定點(diǎn)乘法運(yùn)算

　�。� 4 ）定點(diǎn)除法運(yùn)算

　�。� 5 ）定點(diǎn)運(yùn)算器的組成

　�。� 6 ）浮點(diǎn)運(yùn)算方法和浮點(diǎn)運(yùn)算器

　　三． 存儲(chǔ)系統(tǒng)

　�。� 1 ）存儲(chǔ)器概述

　　（ 2 ）隨機(jī)讀寫(xiě)存儲(chǔ)器

　�。� 3 ）只讀存儲(chǔ)器和閃速存儲(chǔ)器

　�。� 4 ）高速存儲(chǔ)器

　�。� 5 ） cache 存儲(chǔ)器

　　（ 6 ）虛擬存儲(chǔ)器

　　四．指令系統(tǒng)

　�。� 1 ）指令系統(tǒng)的發(fā)展與性能要求

　　（ 2 ）指令格式

　�。� 3 ）指令和數(shù)據(jù)的尋址方式

　�。� 4 ）堆棧尋址方式

　　（ 5 ）典型指令

　　五．中央處理器

　�。� 1 ） CPU 的功能和組成

　�。� 2 ）指令周期

　�。� 3 ）時(shí)序產(chǎn)生器和控制方式

　　（ 4 ）微程序控制器

　�。� 5 ）微程序設(shè)計(jì)技術(shù)

　�。� 6 ）硬布線(xiàn)控制器

　　（ 7 ）流水 CPU

　�。� 8 ） RISC CPU

　　六． 總線(xiàn)系統(tǒng)

　�。� 1 ）總線(xiàn)的概念和結(jié)構(gòu)形態(tài)

　�。� 2 ）總線(xiàn)接口

　�。� 3 ）總線(xiàn)的仲裁定時(shí)和數(shù)據(jù)傳送模式

　　（ 4 ） PCI 總線(xiàn)

　�。� 5 ） ASI 總線(xiàn)

　　七． 外圍設(shè)備

　�。� 1 ）外圍設(shè)備概述

　�。� 2 ）顯示設(shè)備

　�。� 3 ）輸入設(shè)備

　�。� 4 ）硬磁盤(pán)存儲(chǔ)設(shè)備

　�。� 5 ）軟磁盤(pán)存儲(chǔ)設(shè)備

　　（ 6 ）光盤(pán)存儲(chǔ)設(shè)備

　　八． 輸入輸出系統(tǒng)

　�。� 1 ）外圍設(shè)備的定時(shí)方式與信息交換方式

　　（ 2 ）程序中斷方式

　�。� 3 ） DMA 方式

　　（ 4 ）通道方式

　　二、考試要求 數(shù)據(jù)結(jié)構(gòu)

　　1、 掌握有關(guān)數(shù)據(jù)結(jié)構(gòu)的基本概念，包括數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)。

　　2、 掌握算法的基本概念以及算法分析的基本方法。

　　3、 掌握線(xiàn)性表的基本概念， 在兩種存儲(chǔ)結(jié)構(gòu)下的構(gòu)造原理及相應(yīng)的操作；

　　4、 掌握堆棧和隊(duì)列的基本概念與特征以及在兩種存儲(chǔ)結(jié)構(gòu)下如何對(duì)堆棧和隊(duì)列進(jìn)行插入和刪除等操作，具備使用堆棧與隊(duì)列解決實(shí)際問(wèn)題的能力。

　　5、 掌握串的基本概念以及串的存儲(chǔ)結(jié)構(gòu)和相關(guān)的算法。

　　6、 掌握數(shù)組、廣義表和稀疏矩陣的基本概念以及基本操作。

　　7、 掌握樹(shù)型結(jié)構(gòu)的邏輯特征以及各種存儲(chǔ)結(jié)構(gòu)的構(gòu)造原理，能夠熟練使用基于樹(shù)的三種遍歷方法。

　　8 、 掌握二叉排序樹(shù)的邏輯特征、建立過(guò)程， 具備使用其解決實(shí)際問(wèn)題的能力。

　　8、 了解圖的邏輯結(jié)構(gòu)的特點(diǎn)以及常用的兩種存儲(chǔ)方法，了解最小生成樹(shù) (Prim 算法和 Kruskal 算法 ) 、最短路徑、拓?fù)渑判虻木唧w求解過(guò)程。

　　9、 掌握各種順序文件的結(jié)構(gòu)與相應(yīng)的查找方法以及各種查找算法之間時(shí)空效率的差異；了解散列文件的建立、散列函數(shù)的選擇 ( 構(gòu)造 ) 原則、處理散列沖突的方法以及基于散列的查找。

　　10、 掌握各種排序方法的排序特點(diǎn)和排序過(guò)程，能夠?qū)γ恳环N排序方法在時(shí)間、空間、排序的穩(wěn)定性等方面進(jìn)行簡(jiǎn)單分析。

　　計(jì)算機(jī)組成原理

　　1、 掌握計(jì)算機(jī)的層次結(jié)構(gòu)及軟硬件組成等概念。

　　2、 掌握計(jì)算機(jī)中數(shù)據(jù)的格式、機(jī)器數(shù)的表示方法和特點(diǎn)，掌握定點(diǎn)加減的運(yùn)算方法和特點(diǎn)，掌握浮點(diǎn)運(yùn)算方法和特點(diǎn)。

　　3、 掌握存儲(chǔ)系統(tǒng)的分類(lèi)、分級(jí)結(jié)構(gòu)與主存儲(chǔ)器的技術(shù)指標(biāo)；了解 SRAM 、 DRAM 、 EPROM 、閃速存儲(chǔ)器、相聯(lián)存儲(chǔ)器的工作原理；掌握 Cache 存儲(chǔ)器、虛擬存儲(chǔ)器的功能和基本工作原理。

　　4、 掌握指令格式、指令和數(shù)據(jù)的尋址方式，了解 RISC 和 CISC 的特點(diǎn)。

　　5、 掌握 CPU 的功能、基本組成和各個(gè)部分的工作流程；了解微程序控制器的基本工作原理，了解微程序控制技術(shù)和硬布線(xiàn)控制技術(shù)；了解流水 CPU 的工作原理及特點(diǎn)。

　　6、 掌握總線(xiàn)系統(tǒng)的基本概念和基本技術(shù)以及總線(xiàn)仲裁方式的基本工作原來(lái)和特點(diǎn)，了解 PCI 和 ISA 總線(xiàn)的特點(diǎn)。

　　7、 掌握顯示設(shè)備、打印設(shè)備、硬盤(pán)的工作原理和特點(diǎn)，能夠計(jì)算一些常用的技術(shù)指標(biāo)。

　　8、 掌握外圍設(shè)備的定時(shí)方式、信息交換方式的工作原理和特點(diǎn)，了解程序查詢(xún)方式、中斷方式和 DMA 方式原理，了解通道方式。

　　三、主要參考書(shū)目

　　1 、數(shù)據(jù)結(jié)構(gòu)（ C 語(yǔ)言版），嚴(yán)蔚敏，清華大學(xué)出版社 ,1997 年；

　　2 、 計(jì)算機(jī)組成原理 ，白中英，科學(xué)出版社， 2000 年，第三版。