《計算機原理》考試大綱
本《計算機原理》考試大綱適用於中國科學院大學非計算機科學與技術一級學科下各專業的碩士研究生入學考試。計算機原理是計算機科學與技術及相關學科的重要基礎，主要內容包括資料結構、計算機組成原理和計算機網路。要求考生對計算機科學與技術及相關學科的基本概念有較深入、系統的理解，掌握各種資料結構的定義和實現演算法，掌握計算機組成原理所涉及的關鍵內容，掌握計算機網路基本原理和技術，並具有綜合運用所學知識分析問題和解決問題的能力。
一、 考試形式
閉卷，筆試，考試時間180分鐘，總分150分。
二、 試卷結構
常見的資料結構、計算機組成原理和計算機網路題型，如：概念題(填空、選擇、簡答)，應用題(計算、畫圖、分析)等。
三、 考試內容
(一)資料結構 (50分)
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)插入排序法(含折半插入排序法)、選擇排序法、泡排序法、快速排序法、堆排序法、歸併排序、基數排序。各種排序方法排序的原理、規律和特點，各種排序演算法的時空複雜度簡單分析。
(二)計算機組成原理 (50分)
1、計算機系統概論
(1)計算機的分類。
(2)計算機的硬體。
(3)計算機的軟體。
(4)計算機系統的層次結構。
2、 運算方法和運算器
(1)資料與文字的表示方法。
(2)定點加法、減法運算。
(3)定點乘法運算。
(4)定點除法運算。
(5)定點運算器的組成。
(6)浮點運算方法和浮點運算器。
3、儲存系統
(1)儲存器概述。
(2)隨機讀寫儲存器。
(3)只讀儲存器和閃速儲存器。
(4)高速儲存器。
(5)cache儲存器。
(6)虛擬儲存器。
4、指令系統
(1)指令系統的發展與效能要求。
(2)指令格式。
(3)運算元型別。
(4)指令和資料的定址方式。
(5)典型指令。
5、中央處理器
(1)CPU的功能和組成。
(2)指令週期。
(3)時序產生器和控制方式。
(4)微程式控制器。
(5)微程式設計技術。
(6)硬佈線控制器。
(7)流水CPU。
(8)RISC CPU。
6、匯流排系統
(1)匯流排的概念和結構形態。
(2)匯流排介面。
(3)匯流排的仲裁定時和資料傳送模式。
(4)HOST匯流排和PCI匯流排。
(5)InfiniBand標準。
7、外圍裝置
(1)外圍裝置概述。
(2)磁碟儲存裝置及其技術發展。
(3)磁帶儲存裝置。
(4)光碟和磁光碟儲存裝置。
(5)顯示裝置。
(6)輸入裝置和列印裝置。
8、輸入輸出系統
(1)外圍裝置的速度分級與資訊交換方式。
(2)程式查詢方式。
(3)程式中斷方式。
(4)DMA方式。
(5)通道方式。
(三)計算機網路(50分)
1、緒論
(1)計算機網路的`概念、分類、標準、組成與功能。
(2)計算機網路分層結構，協議、介面、服務等概念，ISO/OSI模型和TCP/IP模型。
2、物理層
(1)通訊通道、訊號、寬頻、碼元、波特、速率、信源與信宿等基本概念，奈奎斯特定理與夏農定理，編碼與調製，電路交換、報文交換與分組交換，資料報與虛電路。
(2)雙絞線、同軸電纜、光纖與無線傳輸介質，物理層介面的特性，中繼器，集線器。
3、資料鏈路層
(1)資料鏈路層的功能，組幀，差錯控制(檢錯與糾錯編碼)。
(2)流量控制、可靠傳輸與滑輪視窗機制，停止-等待協議，後退N幀協議(GBN)，選 擇重傳協議(SR)。
(3)頻分多路複用、時分多路複用、波分多路複用、碼分多路複用的概念和基本原理 ALOHA協議、CSMA協議、CSMA/CD協議、CSMA/CA協議、令牌傳遞協議。
(4)區域網的概念及其體系結構，乙太網與IEEE 802.3標準協議，IEEE802.11標準協議，令牌環網。
(5)廣域網的概念，PPP協議，HDLC協議。
(6)網橋的概念和原理，交換機及其工作原理。
4、網路層
(1)網路層的功能，異構網路互聯，路由與轉發，擁塞控制。
(2)路由演算法，靜態路由與動態路由，距離-向量路由演算法，鏈路狀態路由演算法，層次路由。
(3)IPv4分組，IPv4地址與NAT，子網劃分與子網掩碼、CIDR，ARP協議、DHCP協議與ICMP協議。
(4)IPv6的主要特點，IPv6地址。
(5)路由協議，自治系統，域內路由與域間路由，RIP路由協議、OSPF路由協議、BGP路由協議。
(6)組播的概念，IP組播地址。
(7)移動IP的概念，移動IP的通訊過程。
(8)路由器的組成和功能，路由表與路由轉發。
5、傳輸層
(1)傳輸層的功能，傳輸層定址與埠，無連線服務與面向連線服務。
(2)UDP協議，UDP資料報，UDP校驗。
(3)TCP協議，TCP段，TCP連線管理，TCP可靠傳輸，TCP流量控制與擁塞控制。
6、應用層
(1)客戶/伺服器模型，P2P模型。
(2)DNS概念，層次域名空間，域名伺服器，域名解析過程。
(3)FTP協議的工作原理，控制連線與資料連線。
(4)電子郵件系統的組成結構，電子郵件格式與MIME，SMTP協議與POP3協議。
(5)WWW的概念與組成結構，HTTP協議。
四、 考試要求
(一)資料結構
1、 掌握有關資料結構的基本概念，包括資料的邏輯結構、儲存結構。
2、 掌握演算法的基本概念以及演算法分析的基本方法。
3、 熟練掌握線性表的基本概念，在兩種儲存結構下的構造原理及相應的操作。
4、 熟練掌握堆疊和佇列的基本概念與特徵以及在兩種儲存結構下如何對堆疊和佇列進行插入和刪除等操作，具備使用堆疊與佇列解決實際問題的能力。
5、 熟練掌握串的基本概念以及串的儲存結構和相關的演算法。
6、 掌握陣列、廣義表和稀疏矩陣的基本概念以及基本操作。
7、 掌握樹型結構的邏輯特徵以及各種儲存結構的構造原理，能夠靈活運用基於樹的三種遍歷方法。
8、 掌握二叉排序樹的邏輯特徵、建立過程， 具備靈活運用二叉樹解決實際問題的能力。
9、 瞭解圖的邏輯結構的特點以及常用的兩種儲存方法，瞭解最小生成樹(Prim演算法和Kruskal演算法)、最短路徑、拓撲排序的具體求解過程。
10、 掌握各種順序檔案的結構與相應的查詢方法以及各種查詢演算法之間時空效率的差異。瞭解雜湊檔案的建立、雜湊函式的選擇(構造)原則、處理雜湊衝突的方法以及基於雜湊的查詢。
11、 熟練掌握各種排序方法的排序特點和排序過程，能夠對每一種排序方法在時間、空間、排序的穩定性等方面進行簡單分析。
(二)計算機組成原理
1、 掌握計算機的層次結構及軟硬體組成等概念。
2、 掌握計算機中資料的格式、機器數的表示方法和特點，熟練掌握定點加減的運算方法和特點，掌握浮點運算方法和特點。
3、 掌握儲存系統的分類、分級結構與主儲存器的技術指標，瞭解SRAM、DRAM、EPROM、閃速儲存器、相聯儲存器的工作原理，掌握Cache儲存器、虛擬儲存器的功能和基本工作原理。
4、 熟練掌握指令格式、指令和資料的定址方式，理解RISC和CISC的特點。
5、 掌握CPU的功能、基本組成和各個部分的工作流程，瞭解微程式控制器的基本工作原理，瞭解微程式控制技術和硬佈線控制技術，瞭解流水CPU的工作原理及特點。
6、 掌握匯流排系統的基本概念和基本技術以及匯流排仲裁方式的基本工作原來和特點，瞭解PCI匯流排的特點。
7、 理解顯示裝置、列印裝置、硬碟的工作原理和特點，能夠計算一些常用的技術指標。
8、 瞭解外圍裝置的定時方式、資訊交換方式的工作原理和特點，理解程式查詢方式、中斷方式和DMA方式原理，瞭解通道方式。
(三)計算機網路
1、 掌握計算機網路的基本概念、基本原理和基本方法。
2、 掌握計算機網路的體系結構和典型網路協議，瞭解典型網路裝置的組成和特點，理解典型網路裝置的工作原理。
3、 能夠運用計算機網路的基本概念、基本原理和基本方法進行網路系統的分析、設計和應用。
五、 主要參考書目
1、資料結構(C語言版)，嚴蔚敏，吳偉民 編著，清華大學出版社，2007年。
2、計算機組成原理(第四版)，白中英等 編著，科學出版社，2007年。
3、計算機網路(第五版)，[美] 特南鮑姆，[美] 韋瑟羅爾 著，嚴偉，潘愛民 譯，清華大學出版社，2012年。