運(yùn)算機(jī)軟件基礎(chǔ)考試大綱4頁

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

2、表的大體操作。（2）線性表的順序存儲結(jié)構(gòu)與鏈?zhǔn)酱鎯Y(jié)構(gòu)（包括單鏈表、循環(huán)鏈表和雙向鏈表）的構(gòu)造原理。在以上兩種存儲結(jié)構(gòu)上對線性表實(shí)施的最要緊的操作（包括三種鏈表的成立、插入和刪除、檢索等）的算法設(shè)計(jì)。3、堆棧與隊(duì)列（1）堆棧與隊(duì)列的大體概念、大體操作。（2）堆棧與隊(duì)列的順序存儲結(jié)構(gòu)與鏈?zhǔn)酱鎯Y(jié)構(gòu)的構(gòu)造原理。（3）在不同存儲結(jié)構(gòu)的基礎(chǔ)上對堆棧與隊(duì)列實(shí)施插入與刪除等大體操作對應(yīng)的算法設(shè)計(jì)。4、串（1）串的大體概念、串的大體操作和存儲結(jié)構(gòu)。（2）串的模式匹配算法和改良的KMP算法五、數(shù)組和廣義表（1）數(shù)組的概念、多維數(shù)組的實(shí)現(xiàn)（2）對稱矩陣和稀疏矩陣的緊縮存儲（3）廣義表的大體概念六、樹與二叉樹（1

3、）樹的概念和性質(zhì)（2）二叉樹的概念、性質(zhì)和實(shí)現(xiàn)（3）遍歷二叉樹和線索二叉樹（4）樹和叢林（5）赫夫顯樹及其應(yīng)用（6）樹的計(jì)數(shù)7、圖（1）圖的概念，大體概念，圖的分類，經(jīng)常使用名詞術(shù)語。（2）圖的鄰接矩陣存儲方式、鄰接表存儲方式的構(gòu)造原理。（3）圖的遍歷操作。（4）最小生成樹，最短途徑，AOV網(wǎng)與拓?fù)渑判?。八、文件及查找?）數(shù)據(jù)文件的大體概念和大體術(shù)語，數(shù)據(jù)文件的大體操作。（2）順序文件、索引文件、散列（Hash）文件。（3）順序文件的順序查找方式、排序持續(xù)順序文件的折半查找方式和其他文件的大體查找方式。九、內(nèi)排序（1）排序的大體概念，排序方式的分類。（2）插入排序法（含折半插入排序法）、選擇

4、排序法、泡排序法、快速排序法、堆排序法、歸并排序、基數(shù)排序。各類排序方式排序的原理、規(guī)律和特點(diǎn)，各類排序算法的時(shí)空復(fù)雜度簡單分析。運(yùn)算機(jī)組成原理一、運(yùn)算機(jī)系統(tǒng)概論（2）運(yùn)算機(jī)的硬件（3）運(yùn)算機(jī)的軟件（4）運(yùn)算機(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)算器3、存儲系統(tǒng)（1）存儲器概述（2）隨機(jī)讀寫存儲器（3）只讀存儲器和閃速存儲器（4）高速存儲器（5）cache存儲器（6）虛擬存儲器4、指令系統(tǒng)（1）指令系統(tǒng)的進(jìn)展與性能要求（2）指令格式（3）操作數(shù)類型（4）指令和數(shù)據(jù)

5、的尋址方式（5）典型指令五、中央處置器（1）CPU的功能和組成（2）指令周期（3）時(shí)序產(chǎn)生器和操縱方式（4）微程序操縱器（5）微程序設(shè)計(jì)技術(shù)（6）硬布線操縱器(7)流水CPU(8)RISCCPU六、總線系統(tǒng)(1)總線的概念和結(jié)構(gòu)形態(tài)(2)總線接口(3)總線的仲裁按時(shí)和數(shù)據(jù)傳送模式(4) HOST總線和PCI總線(5) InfiniBand標(biāo)準(zhǔn)7、外圍設(shè)備(1)外國設(shè)備概述(2)磁盤存儲設(shè)備及其技術(shù)進(jìn)展(3)磁帶存儲設(shè)備(4)光盤和磁光盤存儲設(shè)備(5)顯示設(shè)備(6)輸入設(shè)備和打印設(shè)備八、輸入輸出系統(tǒng)(1)外圍設(shè)備的速度分級與信息互換方式(2)程序查詢方式(3)程序中斷方式(4)DMA方式(5)通

6、道方式二、考試要求數(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、把握堆棧和隊(duì)列的大體概念與特點(diǎn)和在兩種存儲結(jié)構(gòu)下如何對堆棧和隊(duì)列進(jìn)行插入和刪除等操作，具有利用堆棧與隊(duì)列解決實(shí)際問題的能力。5、把握串的大體概念和串的存儲結(jié)構(gòu)和相關(guān)的算法。6、把握數(shù)組、廣義表和稀疏矩陣的大體概念和大體操作。7、把握樹型結(jié)構(gòu)的邏輯特點(diǎn)和各類存儲結(jié)構(gòu)的構(gòu)造原理，能夠熟練利用基于樹的三種遍歷方式。8、把握二叉排序樹的邏輯特點(diǎn)、成立進(jìn)程，具有利用其解決實(shí)際問題的能力。9、了解圖的邏輯結(jié)

7、構(gòu)的特點(diǎn)和經(jīng)常使用的兩種存儲方式，了解最小生成樹（Prim算法和Kruskal算法）、最短途徑、拓?fù)渑判虻木唧w求解進(jìn)程。10、把握各類順序文件的結(jié)構(gòu)與相應(yīng)的查找方式和各類查找算法之間時(shí)空效率的不同：了解散列文件的成立、散列函數(shù)的選擇（構(gòu)造）原那么、處置散列沖突的方式和基于散列的查找。11、把握各類排序方式的排序特點(diǎn)和排序進(jìn)程，能夠?qū)γ恳环N排序方式在時(shí)刻、空間、排序的穩(wěn)固性等方面進(jìn)行簡單分析。運(yùn)算機(jī)組成原理1、把握運(yùn)算機(jī)的層次結(jié)構(gòu)及軟硬件組成等概念。2、把握運(yùn)算機(jī)中數(shù)據(jù)的格式、機(jī)械數(shù)的表示方式和特點(diǎn)，把握定點(diǎn)加減的運(yùn)算方式和特點(diǎn)，把握浮點(diǎn)運(yùn)算方式和特點(diǎn)。3、把握存儲系統(tǒng)的分類、分級結(jié)構(gòu)與主存儲器

8、的技術(shù)指標(biāo)；了解SRAM、DRAM、EPROM、閃速存儲器、相聯(lián)存儲器的工作原理：把握Cache存儲器、虛擬存儲器的功能和大體工作原理。4、把握指令格式、指令和數(shù)據(jù)的尋址方式，了解RISC和CISC的特點(diǎn)。5、把握CPU的功能、大體組成和各個(gè)部份的工作流程：了解微程序操縱器的大體工作原理，了解微程序操縱技術(shù)和硬布線操縱技術(shù)：了解流水CPU的工作原理及特點(diǎn)。6、把握總線系統(tǒng)的大體概念和大體技術(shù)和總線仲裁方式的大體工作原先和特點(diǎn)，了解PCI總線的特點(diǎn)。7、把握顯示設(shè)備、打印設(shè)備、硬盤的工作原理和特點(diǎn)，能夠計(jì)算一些經(jīng)常使用的技術(shù)指標(biāo)。8、把握外圍設(shè)備的按時(shí)方式、信息互換方式的工作原理和特點(diǎn)，了解程序查詢方式、中斷方式和DMA方