《計算機原理》考試大綱

《計算機原理》考試大綱

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

　　一、 考試形式

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

　　二、 試卷結構

　　常見(jiàn)的數據結構、計算機組成原理和計算機網(wǎng)絡(luò )題型，如：概念題(填空、選擇、簡(jiǎn)答)，應用題(計算、畫(huà)圖、分析)等。

　　三、 考試內容

　　(一)數據結構 (50分)

　　1、緒論

　　(1)數據結構的基本概念，數據的邏輯結構、存儲結構。

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

　　2、線(xiàn)性表

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

　　(2)線(xiàn)性表的順序存儲結構與鏈式存儲結構(包括單鏈表、循環(huán)鏈表和雙向鏈表)的構造原理。在以上兩種存儲結構上對線(xiàn)性表實(shí)施的最主要的操作(包括三種鏈表的建立、插入和刪除、檢索等)的算法設計。

　　3、堆棧與隊列

　　(1)堆棧與隊列的基本概念、基本操作。

　　(2)堆棧與隊列的順序存儲結構與鏈式存儲結構的構造原理。

　　(3)在不同存儲結構的基礎上對堆棧與隊列實(shí)施插入與刪除等基本操作對應的算法設計。

　　4、串

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

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

　　5、數組和廣義表

　　(1)數組的概念、多維數組的實(shí)現。

　　(2)對稱(chēng)矩陣和稀疏矩陣的壓縮存儲。

　　(3)廣義表的基本概念。

　　6、樹(shù)與二叉樹(shù)

　　(1)樹(shù)的定義和性質(zhì)。

　　(2)二叉樹(shù)的概念、性質(zhì)和實(shí)現。

　　(3)遍歷二叉樹(shù)和線(xiàn)索二叉樹(shù)。

　　(4)樹(shù)和森林。

　　(5)赫夫曼樹(shù)及其應用。

　　(6)樹(shù)的計數。

　　7、圖

　　(1)圖的定義，基本概念，圖的分類(lèi)，常用名詞術(shù)語(yǔ)。

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

　　(3)圖的遍歷操作。

　　(4)最小生成樹(shù)，最短路徑，AOV網(wǎng)與拓撲排序。

　　8、文件及查找

　　(1)數據文件的基本概念和基本術(shù)語(yǔ)，數據文件的基本操作。

　　(2)順序文件、索引文件、散列(Hash)文件。

　　(3)順序文件的順序查找方法、排序連續順序文件的折半查找方法以及其他文件的基本查找方法。

　　9、內排序

　　(1)排序的基本概念，排序方法的分類(lèi)。

　　(2)插入排序法(含折半插入排序法)、選擇排序法、泡排序法、快速排序法、堆排序法、歸并排序、基數排序。各種排序方法排序的原理、規律和特點(diǎn)，各種排序算法的時(shí)空復雜度簡(jiǎn)單分析。

　　(二)計算機組成原理 (50分)

　　1、計算機系統概論

　　(1)計算機的分類(lèi)。

　　(2)計算機的硬件。

　　(3)計算機的軟件。

　　(4)計算機系統的層次結構。

　　2、 運算方法和運算器

　　(1)數據與文字的表示方法。

　　(2)定點(diǎn)加法、減法運算。

　　(3)定點(diǎn)乘法運算。

　　(4)定點(diǎn)除法運算。

　　(5)定點(diǎn)運算器的組成。

　　(6)浮點(diǎn)運算方法和浮點(diǎn)運算器。

　　3、存儲系統

　　(1)存儲器概述。

　　(2)隨機讀寫(xiě)存儲器。

　　(3)只讀存儲器和閃速存儲器。

　　(4)高速存儲器。

　　(5)cache存儲器。

　　(6)虛擬存儲器。

　　4、指令系統

　　(1)指令系統的發(fā)展與性能要求。

　　(2)指令格式。

　　(3)操作數類(lèi)型。

　　(4)指令和數據的尋址方式。

　　(5)典型指令。

　　5、中央處理器

　　(1)CPU的功能和組成。

　　(2)指令周期。

　　(3)時(shí)序產(chǎn)生器和控制方式。

　　(4)微程序控制器。

　　(5)微程序設計技術(shù)。

　　(6)硬布線(xiàn)控制器。

　　(7)流水CPU。

　　(8)RISC CPU。

　　6、總線(xiàn)系統

　　(1)總線(xiàn)的概念和結構形態(tài)。

　　(2)總線(xiàn)接口。

　　(3)總線(xiàn)的仲裁定時(shí)和數據傳送模式。

　　(4)HOST總線(xiàn)和PCI總線(xiàn)。

　　(5)InfiniBand標準。

　　7、外圍設備

　　(1)外圍設備概述。

　　(2)磁盤(pán)存儲設備及其技術(shù)發(fā)展。

　　(3)磁帶存儲設備。

　　(4)光盤(pán)和磁光盤(pán)存儲設備。

　　(5)顯示設備。

　　(6)輸入設備和打印設備。

　　8、輸入輸出系統

　　(1)外圍設備的速度分級與信息交換方式。

　　(2)程序查詢(xún)方式。

　　(3)程序中斷方式。

　　(4)DMA方式。

　　(5)通道方式。

　　(三)計算機網(wǎng)絡(luò )(50分)

　　1、緒論

　　(1)計算機網(wǎng)絡(luò )的概念、分類(lèi)、標準、組成與功能。

　　(2)計算機網(wǎng)絡(luò )分層結構，協(xié)議、接口、服務(wù)等概念，ISO/OSI模型和TCP/IP模型。

　　2、物理層

　　(1)通信信道、信號、寬帶、碼元、波特、速率、信源與信宿等基本概念，奈奎斯特定理與香農定理，編碼與調制，電路交換、報文交換與分組交換，數據報與虛電路。

　　(2)雙絞線(xiàn)、同軸電纜、光纖與無(wú)線(xiàn)傳輸介質(zhì)，物理層接口的特性，中繼器，集線(xiàn)器。

　　3、數據鏈路層

　　(1)數據鏈路層的功能，組幀，差錯控制(檢錯與糾錯編碼)。

　　(2)流量控制、可靠傳輸與滑輪窗口機制，停止-等待協(xié)議，后退N幀協(xié)議(GBN)，選 擇重傳協(xié)議(SR)。

　　(3)頻分多路復用、時(shí)分多路復用、波分多路復用、碼分多路復用的概念和基本原理 ALOHA協(xié)議、CSMA協(xié)議、CSMA/CD協(xié)議、CSMA/CA協(xié)議、令牌傳遞協(xié)議。

　　(4)局域網(wǎng)的概念及其體系結構，以太網(wǎng)與IEEE 802.3標準協(xié)議，IEEE802.11標準協(xié)議，令牌環(huán)網(wǎng)。

　　(5)廣域網(wǎng)的概念，PPP協(xié)議，HDLC協(xié)議。

　　(6)網(wǎng)橋的概念和原理，交換機及其工作原理。

　　4、網(wǎng)絡(luò )層

　　(1)網(wǎng)絡(luò )層的功能，異構網(wǎng)絡(luò )互聯(lián)，路由與轉發(fā)，擁塞控制。

　　(2)路由算法，靜態(tài)路由與動(dòng)態(tài)路由，距離-向量路由算法，鏈路狀態(tài)路由算法，層次路由。

　　(3)IPv4分組，IPv4地址與NAT，子網(wǎng)劃分與子網(wǎng)掩碼、CIDR，ARP協(xié)議、DHCP協(xié)議與ICMP協(xié)議。

　　(4)IPv6的主要特點(diǎn)，IPv6地址。

　　(5)路由協(xié)議，自治系統，域內路由與域間路由，RIP路由協(xié)議、OSPF路由協(xié)議、BGP路由協(xié)議。

　　(6)組播的概念，IP組播地址。

　　(7)移動(dòng)IP的概念，移動(dòng)IP的通信過(guò)程。

　　(8)路由器的組成和功能，路由表與路由轉發(fā)。

　　5、傳輸層

　　(1)傳輸層的功能，傳輸層尋址與端口，無(wú)連接服務(wù)與面向連接服務(wù)。

　　(2)UDP協(xié)議，UDP數據報，UDP校驗。

　　(3)TCP協(xié)議，TCP段，TCP連接管理，TCP可靠傳輸，TCP流量控制與擁塞控制。

　　6、應用層

　　(1)客戶(hù)/服務(wù)器模型，P2P模型。

　　(2)DNS概念，層次域名空間，域名服務(wù)器，域名解析過(guò)程。

　　(3)FTP協(xié)議的工作原理，控制連接與數據連接。

　　(4)電子郵件系統的組成結構，電子郵件格式與MIME，SMTP協(xié)議與POP3協(xié)議。

　　(5)WWW的概念與組成結構，HTTP協(xié)議。

　　四、 考試要求

　　(一)數據結構

　　1、 掌握有關(guān)數據結構的基本概念，包括數據的邏輯結構、存儲結構。

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

　　3、 熟練掌握線(xiàn)性表的基本概念，在兩種存儲結構下的構造原理及相應的操作。

　　4、 熟練掌握堆棧和隊列的基本概念與特征以及在兩種存儲結構下如何對堆棧和隊列進(jìn)行插入和刪除等操作，具備使用堆棧與隊列解決實(shí)際問(wèn)題的能力。

　　5、 熟練掌握串的基本概念以及串的存儲結構和相關(guān)的算法。

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

　　7、 掌握樹(shù)型結構的邏輯特征以及各種存儲結構的構造原理，能夠靈活運用基于樹(shù)的三種遍歷方法。

　　8、 掌握二叉排序樹(shù)的邏輯特征、建立過(guò)程， 具備靈活運用二叉樹(shù)解決實(shí)際問(wèn)題的能力。

　　9、 了解圖的邏輯結構的特點(diǎn)以及常用的兩種存儲方法，了解最小生成樹(shù)(Prim算法和Kruskal算法)、最短路徑、拓撲排序的具體求解過(guò)程。

　　10、 掌握各種順序文件的結構與相應的查找方法以及各種查找算法之間時(shí)空效率的差異。了解散列文件的建立、散列函數的選擇(構造)原則、處理散列沖突的方法以及基于散列的查找。

　　11、 熟練掌握各種排序方法的排序特點(diǎn)和排序過(guò)程，能夠對每一種排序方法在時(shí)間、空間、排序的穩定性等方面進(jìn)行簡(jiǎn)單分析。

　　(二)計算機組成原理

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

　　2、 掌握計算機中數據的格式、機器數的表示方法和特點(diǎn)，熟練掌握定點(diǎn)加減的運算方法和特點(diǎn)，掌握浮點(diǎn)運算方法和特點(diǎn)。

　　3、 掌握存儲系統的分類(lèi)、分級結構與主存儲器的技術(shù)指標，了解SRAM、DRAM、EPROM、閃速存儲器、相聯(lián)存儲器的工作原理，掌握Cache存儲器、虛擬存儲器的功能和基本工作原理。

　　4、 熟練掌握指令格式、指令和數據的尋址方式，理解RISC和CISC的特點(diǎn)。

　　5、 掌握CPU的功能、基本組成和各個(gè)部分的工作流程，了解微程序控制器的基本工作原理，了解微程序控制技術(shù)和硬布線(xiàn)控制技術(shù)，了解流水CPU的工作原理及特點(diǎn)。

　　6、 掌握總線(xiàn)系統的基本概念和基本技術(shù)以及總線(xiàn)仲裁方式的基本工作原來(lái)和特點(diǎn)，了解PCI總線(xiàn)的特點(diǎn)。

　　7、 理解顯示設備、打印設備、硬盤(pán)的工作原理和特點(diǎn)，能夠計算一些常用的技術(shù)指標。

　　8、 了解外圍設備的定時(shí)方式、信息交換方式的工作原理和特點(diǎn)，理解程序查詢(xún)方式、中斷方式和DMA方式原理，了解通道方式。

　　(三)計算機網(wǎng)絡(luò )

　　1、 掌握計算機網(wǎng)絡(luò )的基本概念、基本原理和基本方法。

　　2、 掌握計算機網(wǎng)絡(luò )的體系結構和典型網(wǎng)絡(luò )協(xié)議，了解典型網(wǎng)絡(luò )設備的組成和特點(diǎn)，理解典型網(wǎng)絡(luò )設備的工作原理。

　　3、 能夠運用計算機網(wǎng)絡(luò )的基本概念、基本原理和基本方法進(jìn)行網(wǎng)絡(luò )系統的分析、設計和應用。

　　五、 主要參考書(shū)目

　　1、數據結構(C語(yǔ)言版)，嚴蔚敏，吳偉民 編著(zhù)，清華大學(xué)出版社，2007年。

　　2、計算機組成原理(第四版)，白中英等 編著(zhù)，科學(xué)出版社，2007年。

　　3、計算機網(wǎng)絡(luò )(第五版)，[美] 特南鮑姆，[美] 韋瑟羅爾 著(zhù)，嚴偉，潘愛(ài)民 譯，清華大學(xué)出版社，2012年。