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

一、 考試形式

閉卷，筆試，考試時(shí)間 180 分鐘，總分 150 分。

二、 試卷結(jié)構(gòu)

常見的數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)組成原理和計(jì)算機(jī)網(wǎng)絡(luò)題型，如：概念題（填空、選擇、簡答），應(yīng)用題（計(jì)算、畫圖、分析）等。

三、 考試內(nèi)容

（一）數(shù)據(jù)結(jié)構(gòu) （50 分）

1、緒論

（1）數(shù)據(jù)結(jié)構(gòu)的基本概念，數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)。

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

2、線性表

（1）線性關(guān)系、線性表的定義，線性表的基本操作。

（2）線性表的順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)(包括單鏈表、循環(huán)鏈表和雙向鏈表)的構(gòu)造原理。在以上兩種存儲(chǔ)結(jié)構(gòu)上對線性表實(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ì)列實(shí)施插入與刪除等基本操作對應(yīng)的算法設(shè)計(jì)。

4、串

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

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

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

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

（2）對稱矩陣和稀疏矩陣的壓縮存儲(chǔ)。

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

6、樹與二叉樹

（1）樹的定義和性質(zhì)。

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

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

（4）樹和森林。

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

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

7、圖

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

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

（3）圖的遍歷操作。

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

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

本文來源：http://zhangjiajieline.cn/guokeda/cankaoshumu_462084.html