1、中國科學院大學碩士研究生入學考試計算機原理考試大綱本計算機原理考試大綱適用于中國科學院大學非計算機科學與技術一級學科下各 專業的碩士研究生入學考試。計算機原理是計算機科學與技術及相關學科的重要基礎，主 要內容包括數據結構、計算機組成原理和計算機網絡。要求考生對計算機科學與技術及相 關學科的基本概念有較深入、系統的理解，掌握各種數據結構的定義和實現算法，掌握計 算機組成原理所涉及的關鍵內容，掌握計算機網絡基本原理和技術，并具有綜合運用所學 知識分析問題和解決問題的能力 。考試形式閉卷，筆試，考試時間 180 分鐘，總分 150 分。試卷結構常見的數據結構、計算機組成原理和計算機網絡題型，如：概念

2、題（填空、選擇、簡 答），應用題（計算、畫圖、分析）等。三、考試內容（一）數據結構 （ 50 分）1、緒論（1）數據結構的基本概念，數據的邏輯結構、存儲結構。（ 2）算法的定義、算法的基本特性以及算法分析的基本概念。2、線性表（1）線性關系、線性表的定義，線性表的基本操作。（ 2）線性表的順序存儲結構與鏈式存儲結構（包括單鏈表、循環鏈表和雙向鏈表 ）的構造原理。在以上兩種存儲結構上對線性表實施的最主要的操作（包括三種鏈表的建立、 插入和刪除、檢索等 ）的算法設計。3、堆棧與隊列（ 1）堆棧與隊列的基本概念、基本操作。（ 2）堆棧與隊列的順序存儲結構與鏈式存儲結構的構造原理。（3）在不同存儲結構

3、的基礎上對堆棧與隊列實施插入與刪除等基本操作對應的算法設計。4、串（ 1）串的基本概念、串的基本操作和存儲結構。（ 2）串的模式匹配算法和改進的 KMP 算法。5、數組和廣義表（1）數組的概念、多維數組的實現。（2）對稱矩陣和稀疏矩陣的壓縮存儲。（ 3）廣義表的基本概念。6、樹與二叉樹（ 1）樹的定義和性質。（2）二叉樹的概念、性質和實現。（3）遍歷二叉樹和線索二叉樹。（ 4）樹和森林。（5）赫夫曼樹及其應用。（ 6）樹的計數。7、圖（1）圖的定義，基本概念，圖的分類，常用名詞術語。（ 2）圖的鄰接矩陣存儲方法、鄰接表存儲方法的構造原理。（3）圖的遍歷操作。（ 4）最小生成樹，最短路徑， AO

4、V 網與拓撲排序。8、文件及查找（ 1）數據文件的基本概念和基本術語，數據文件的基本操作。（2）順序文件、索引文件、散列（Hash）文件。（ 3）順序文件的順序查找方法、 排序連續順序文件的折半查找方法以及其他文件的基本查 找方法。9、內排序（ 1）排序的基本概念，排序方法的分類。2）插入排序法 （ 含折半插入排序法 ）、選擇排序法、泡排序法、快速排序法、堆排序法、 歸并排序、基數排序。各種排序方法排序的原理、規律和特點，各種排序算法的時空 復雜度簡單分析。（二）計算機組成原理 （50 分）1、計算機系統概論（1）計算機的分類。（2）計算機的硬件。（3）計算機的軟件。（ 4）計算機系統的層次結

5、構。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）

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）計算機網絡的概念、分類

7、、標準、組成與功能。（ 2）計算機網絡分層結構，協議、接口、服務等概念，ISO/OSI 模型和 TCP/IP 模型。2、物理層（1）通信信道、信號、寬帶、碼元、波特、速率、信源與信宿等基本概念，奈奎斯特定理 與香農定理，編碼與調制，電路交換、報文交換與分組交換，數據報與虛電路。（2）雙絞線、同軸電纜、光纖與無線傳輸介質，物理層接口的特性，中繼器，集線器。3、數據鏈路層（ 1）數據鏈路層的功能，組幀，差錯控制（檢錯與糾錯編碼）。（2）流量控制、可靠傳輸與滑輪窗口機制，停止-等待協議，后退 N 幀協議 （GBN） ，選擇重傳協議 （SR）。（ 3）頻分多路復用、時分多路復用、波分多路復用、碼分多路

8、復用的概念和基本原理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

9、 協議。（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 概念，層次域名空

10、間，域名服務器，域名解析過程。( 3) FTP 協議的工作原理，控制連接與數據連接。( 4)電子郵件系統的組成結構，電子郵件格式與MIME ， SMTP 協議與 POP3 協議。( 5) WWW 的概念與組成結構， HTTP 協議。四、考試要求一) 數據結構1 、 掌握有關數據結構的基本概念，包括數據的邏輯結構、存儲結構。2、掌握算法的基本概念以及算法分析的基本方法。3、熟練掌握線性表的基本概念，在兩種存儲結構下的構造原理及相應的操作。4、熟練掌握堆棧和隊列的基本概念與特征以及在兩種存儲結構下如何對堆棧和隊列進 行插入和刪除等操作，具備使用堆棧與隊列解決實際問題的能力。5、熟練掌握串的基本概念

11、以及串的存儲結構和相關的算法。6、掌握數組、廣義表和稀疏矩陣的基本概念以及基本操作。7、 掌握樹型結構的邏輯特征以及各種存儲結構的構造原理，能夠靈活運用基于樹的三種 遍歷方法。8、 掌握二叉排序樹的邏輯特征、建立過程，具備靈活運用二叉樹解決實際問題的能力。9、了解圖的邏輯結構的特點以及常用的兩種存儲方法，了解最小生成樹(Prim 算法和Kruskal 算法 )、最短路徑、拓撲排序的具體求解過程。10、掌握各種順序文件的結構與相應的查找方法以及各種查找算法之間時空效率的差異。了解散列文件的建立、散列函數的選擇（構造 ）原則、處理散列沖突的方法以及基于散列的查找。11、熟練掌握各種排序方法的排序特

12、點和排序過程，能夠對每一種排序方法在時間、 空間、排序的穩定性等方面進行簡單分析。二）計算機組成原理1、掌握計算機的層次結構及軟硬件組成等概念。2、掌握計算機中數據的格式、機器數的表示方法和特點，熟練掌握定點加減的運算方法 和特點，掌握浮點運算方法和特點。3、掌握存儲系統的分類、分級結構與主存儲器的技術指標，了解SRAM 、 DRAM 、EPROM 、閃速存儲器、相聯存儲器的工作原理，掌握 Cache 存儲器、虛擬存儲器的 功能和基本工作原理。4、熟練掌握指令格式、指令和數據的尋址方式，理解RISC 和 CISC 的特點。5、掌握 CPU 的功能、基本組成和各個部分的工作流程，了解微程序控制器的基本工作 原理，了解微程序控制技術和硬布線控制技術，了解流水 CPU 的工作原理及特點。6、掌握總線系統的基本概念和基本技術以及總線仲裁方式的基本工作原來和特點，了解PCI 總線的特點。7、理解顯示設備、打印設備、硬盤的工作原理和特點，能夠計算一些常用的技術指標。8、了解外圍設備的定時方式、信息交換方式的工作原理和特點，理解程序查詢方式、中 斷方式和 DMA 方式原理，了解通道方式。三）計算機網絡1、掌握計算機網絡的基本概念、基本原理和基本方法。2、掌握計算機網絡的體系結構和典型網絡協議，了解典型網絡設備的組成和特點，理解 典型網絡設備的工作原理。3、能夠運用計算機網絡的基