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

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

　　《計算機原理》考試大綱

　　本《計算機原理》考試大綱適用於中國科學院研究生院計算機科學與技術等專業的碩士研究生入學考試。計算機原理是計算機科學與技術及相關學科的重要基礎，主要內容包括資料結構和計算機組成原理兩大部分。要求考生對計算機科學與技術及相關學科的基本概念有較深入、系統的理解，掌握各種資料結構的定義和實現演算法，掌握計算機組成原理所涉及的關鍵內容，並具有綜合運用所學知識分析問題和解決問題的能力 。

　　一、考試內容 資料結構

　　1 、緒論

　　（ 1 ）資料結構的基本概念，資料的邏輯結構、儲存結構。

　　（ 2 ）演算法的定義、演算法的基本特性以及演算法分析的基本概念。

　　2 、線性表

　　（ 1 ）線性關係、線性表的定義，線性表的基本操作。

　　（ 2 ）線性表的順序儲存結構與鏈式儲存結構 ( 包括單鏈表、迴圈連結串列和雙向連結串列 ) 的構造原理。在以上兩種儲存結構上對線性表實施的最主要的操作 ( 包括三種連結串列的建立、插入和刪除、檢索等 ) 的演算法設計。

　　3 、堆疊與佇列

　　（ 1 ）堆疊與佇列的基本概念、基本操作。

　　（ 2 ）堆疊與佇列的順序儲存結構與鏈式儲存結構的構造原理。

　　（ 3 ）在不同儲存結構的基礎上對堆疊與佇列實施插入與刪除等基本操作對應的演算法設計。

　　4 、串

　　（ 1 ）串的基本概念、串的基本操作和儲存結構。

　　（ 2 ）串的模式匹配演算法和改進的 KMP 演算法

　　5 、陣列和廣義表

　　（ 1 ）陣列的概念、多維陣列的實現

　　（ 2 ）對稱矩陣和稀疏矩陣的壓縮儲存

　　（ 3 ）廣義表的.基本概念

　　6 、樹與二叉樹

　　（ 1 ）樹的定義和性質

　　（ 2 ）二叉樹的概念、性質和實現

　　（ 3 ）遍歷二叉樹和線索二叉樹

　　（ 4 ）樹和森林

　　（ 5 ）赫夫曼樹及其應用

　　（ 6 ）樹的計數

　　7 、圖

　　（ 1 ）圖的定義，基本概念，圖的分類，常用名詞術語。

　　（ 2 ）圖的鄰接矩陣儲存方法、鄰接表儲存方法的構造原理。

　　（ 3 ）圖的遍歷操作。

　　（ 4 ）最小生成樹，最短路徑， AOV 網與拓撲排序。

　　8 、檔案及查詢

　　（ 1 ）資料檔案的基本概念和基本術語，資料檔案的基本操作。

　　（ 2 ）順序檔案、索引檔案、雜湊 (Hash) 檔案。

　　（ 3 ）順序檔案的順序查詢方法、排序連續順序檔案的折半查詢方法以及其他檔案的基本查詢方法。

　　9 、內排序

　　（ 1 ）排序的基本概念，排序方法的分類。

　　（ 2 ）插入排序法 ( 含折半插入排序法 ) 、選擇排序法、泡排序法、快速排序法、堆積排序法、歸併排序、基數排序。各種排序方法排序的原理、規律和特點，各種排序演算法的時空複雜度簡單分析。

　　計算機組成原理

　　一．計算機系統概論

　　（ 1 ）計算機的分類

　　（ 2 ）計算機的硬體

　　（ 3 ）計算機的軟體

　　（ 4 ）計算機系統的層次結構

　　二． 運算方法和運算器

　　（ 1 ）資料與文字的表示方法

　　（ 2 ）定點加法、減法運算

　　（ 3 ）定點乘法運算

　　（ 4 ）定點除法運算

　　（ 5 ）定點運算器的組成

　　（ 6 ）浮點運算方法和浮點運算器

　　三． 儲存系統

　　（ 1 ）儲存器概述

　　（ 2 ）隨機讀寫儲存器

　　（ 3 ）只讀儲存器和閃速儲存器

　　（ 4 ）高速儲存器

　　（ 5 ） cache 儲存器

　　（ 6 ）虛擬儲存器

　　四．指令系統

　　（ 1 ）指令系統的發展與效能要求

　　（ 2 ）指令格式

　　（ 3 ）指令和資料的定址方式

　　（ 4 ）堆疊定址方式

　　（ 5 ）典型指令

　　五．中央處理器

　　（ 1 ） CPU 的功能和組成

　　（ 2 ）指令週期

　　（ 3 ）時序產生器和控制方式

　　（ 4 ）微程式控制器

　　（ 5 ）微程式設計技術

　　（ 6 ）硬佈線控制器

　　（ 7 ）流水 CPU

　　（ 8 ） RISC CPU

　　六． 匯流排系統

　　（ 1 ）匯流排的概念和結構形態

　　（ 2 ）匯流排介面

　　（ 3 ）匯流排的仲裁定時和資料傳送模式

　　（ 4 ） PCI 匯流排

　　（ 5 ） ASI 匯流排

　　七． 外圍裝置

　　（ 1 ）外圍裝置概述

　　（ 2 ）顯示裝置

　　（ 3 ）輸入裝置

　　（ 4 ）硬磁碟儲存裝置

　　（ 5 ）軟磁碟儲存裝置

　　（ 6 ）光碟儲存裝置

　　八． 輸入輸出系統

　　（ 1 ）外圍裝置的定時方式與資訊交換方式

　　（ 2 ）程式中斷方式

　　（ 3 ） DMA 方式

　　（ 4 ）通道方式

　　二、考試要求 資料結構

　　1、 掌握有關資料結構的基本概念，包括資料的邏輯結構、儲存結構。

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

　　3、 掌握線性表的基本概念， 在兩種儲存結構下的構造原理及相應的操作；

　　4、 掌握堆疊和佇列的基本概念與特徵以及在兩種儲存結構下如何對堆疊和佇列進行插入和刪除等操作，具備使用堆疊與佇列解決實際問題的能力。

　　5、 掌握串的基本概念以及串的儲存結構和相關的演算法。

　　6、 掌握陣列、廣義表和稀疏矩陣的基本概念以及基本操作。

　　7、 掌握樹型結構的邏輯特徵以及各種儲存結構的構造原理，能夠熟練使用基於樹的三種遍歷方法。

　　8 、 掌握二叉排序樹的邏輯特徵、建立過程， 具備使用其解決實際問題的能力。

　　8、 瞭解圖的邏輯結構的特點以及常用的兩種儲存方法，瞭解最小生成樹 (Prim 演算法和 Kruskal 演算法 ) 、最短路徑、拓撲排序的具體求解過程。

　　9、 掌握各種順序檔案的結構與相應的查詢方法以及各種查詢演算法之間時空效率的差異；瞭解雜湊檔案的建立、雜湊函式的選擇 ( 構造 ) 原則、處理雜湊衝突的方法以及基於雜湊的查詢。

　　10、 掌握各種排序方法的排序特點和排序過程，能夠對每一種排序方法在時間、空間、排序的穩定性等方面進行簡單分析。

　　計算機組成原理

　　1、 掌握計算機的層次結構及軟硬體組成等概念。

　　2、 掌握計算機中資料的格式、機器數的表示方法和特點，掌握定點加減的運算方法和特點，掌握浮點運算方法和特點。

　　3、 掌握儲存系統的分類、分級結構與主儲存器的技術指標；瞭解 SRAM 、 DRAM 、 EPROM 、閃速儲存器、相聯儲存器的工作原理；掌握 Cache 儲存器、虛擬儲存器的功能和基本工作原理。

　　4、 掌握指令格式、指令和資料的定址方式，瞭解 RISC 和 CISC 的特點。

　　5、 掌握 CPU 的功能、基本組成和各個部分的工作流程；瞭解微程式控制器的基本工作原理，瞭解微程式控制技術和硬佈線控制技術；瞭解流水 CPU 的工作原理及特點。

　　6、 掌握匯流排系統的基本概念和基本技術以及匯流排仲裁方式的基本工作原來和特點，瞭解 PCI 和 ISA 匯流排的特點。

　　7、 掌握顯示裝置、列印裝置、硬碟的工作原理和特點，能夠計算一些常用的技術指標。

　　8、 掌握外圍裝置的定時方式、資訊交換方式的工作原理和特點，瞭解程式查詢方式、中斷方式和 DMA 方式原理，瞭解通道方式。

　　三、主要參考書目

　　1 、資料結構（ C 語言版），嚴蔚敏，清華大學出版社 ,1997 年；

　　2 、 計算機組成原理 ，白中英，科學出版社， 2000 年，第三版。

【《計算機原理》的考試說明】相關文章：