《計(jì)算機(jī)軟件基礎(chǔ)》考試大綱

1、中國(guó)科學(xué)院大學(xué)碩士研究生入學(xué)考試計(jì)算機(jī)原理考試大綱本計(jì)算機(jī)原理考試大綱適用于中國(guó)科學(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ò)。要求考生對(duì)計(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í)分析問(wèn)題和解決問(wèn)題的能力。一、 考試形式閉卷，筆試，考試時(shí)間180分鐘，總分150分。二、 試卷結(jié)構(gòu)常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)組成原理和計(jì)算機(jī)網(wǎng)絡(luò)題型，如：概念題（填空

2、、選擇、簡(jiǎn)答），應(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)上對(duì)線性表實(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ì)堆棧與隊(duì)列實(shí)施插

3、入與刪除等基本操作對(duì)應(yīng)的算法設(shè)計(jì)。4、串（1）串的基本概念、串的基本操作和存儲(chǔ)結(jié)構(gòu)。（2）串的模式匹配算法和改進(jìn)的KMP算法。5、數(shù)組和廣義表（1）數(shù)組的概念、多維數(shù)組的實(shí)現(xiàn)。（2）對(duì)稱矩陣和稀疏矩陣的壓縮存儲(chǔ)。（3）廣義表的基本概念。6、樹(shù)與二叉樹(shù)（1）樹(shù)的定義和性質(zhì)。（2）二叉樹(shù)的概念、性質(zhì)和實(shí)現(xiàn)。（3）遍歷二叉樹(shù)和線索二叉樹(shù)。（4）樹(shù)和森林。（5）赫夫曼樹(shù)及其應(yīng)用。（6）樹(shù)的計(jì)數(shù)。7、圖（1）圖的定義，基本概念，圖的分類，常用名詞術(shù)語(yǔ)。（2）圖的鄰接矩陣存儲(chǔ)方法、鄰接表存儲(chǔ)方法的構(gòu)造原理。（3）圖的遍歷操作。（4）最小生成樹(shù)，最短路徑，AOV網(wǎng)與拓?fù)渑判颉?、文件及查找（1）數(shù)據(jù)文件的基

4、本概念和基本術(shù)語(yǔ)，數(shù)據(jù)文件的基本操作。（2）順序文件、索引文件、散列(Hash)文件。（3）順序文件的順序查找方法、排序連續(xù)順序文件的折半查找方法以及其他文件的基本查找方法。9、內(nèi)排序（1）排序的基本概念，排序方法的分類。（2）插入排序法(含折半插入排序法)、選擇排序法、泡排序法、快速排序法、堆排序法、歸并排序、基數(shù)排序。各種排序方法排序的原理、規(guī)律和特點(diǎn)，各種排序算法的時(shí)空復(fù)雜度簡(jiǎn)單分析。（二）計(jì)算機(jī)組成原理 （50分）1、計(jì)算機(jī)系統(tǒng)概論（1）計(jì)算機(jī)的分類。（2）計(jì)算機(jī)的硬件。（3）計(jì)算機(jī)的軟件。（4）計(jì)算機(jī)系統(tǒng)的層次結(jié)構(gòu)。2、 運(yùn)算方法和運(yùn)算器（1）數(shù)據(jù)與文字的表示方法。（2）定點(diǎn)加法、減

5、法運(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、存儲(chǔ)系統(tǒng)（1）存儲(chǔ)器概述。（2）隨機(jī)讀寫存儲(chǔ)器。（3）只讀存儲(chǔ)器和閃速存儲(chǔ)器。（4）高速存儲(chǔ)器。（5）cache存儲(chǔ)器。（6）虛擬存儲(chǔ)器。4、指令系統(tǒng)（1）指令系統(tǒng)的發(fā)展與性能要求。（2）指令格式。（3）操作數(shù)類型。（4）指令和數(shù)據(jù)的尋址方式。（5）典型指令。5、中央處理器（1）CPU的功能和組成。（2）指令周期。（3）時(shí)序產(chǎn)生器和控制方式。（4）微程序控制器。（5）微程序設(shè)計(jì)技術(shù)。（6）硬布線控制器。（7）流水CPU。（8）RISC CPU。6、總線系統(tǒng)（1）總線的概念和結(jié)構(gòu)形態(tài)。（2

6、）總線接口。（3）總線的仲裁定時(shí)和數(shù)據(jù)傳送模式。（4）HOST總線和PCI總線。（5）InfiniBand標(biāo)準(zhǔn)。7、外圍設(shè)備（1）外圍設(shè)備概述。（2）磁盤存儲(chǔ)設(shè)備及其技術(shù)發(fā)展。（3）磁帶存儲(chǔ)設(shè)備。（4）光盤和磁光盤存儲(chǔ)設(shè)備。（5）顯示設(shè)備。（6）輸入設(shè)備和打印設(shè)備。8、輸入輸出系統(tǒng)（1）外圍設(shè)備的速度分級(jí)與信息交換方式。（2）程序查詢方式。（3）程序中斷方式。（4）DMA方式。（5）通道方式。（三）計(jì)算機(jī)網(wǎng)絡(luò)（50分）1、緒論（1）計(jì)算機(jī)網(wǎng)絡(luò)的概念、分類、標(biāo)準(zhǔn)、組成與功能。（2）計(jì)算機(jī)網(wǎng)絡(luò)分層結(jié)構(gòu)，協(xié)議、接口、服務(wù)等概念，ISO/OSI模型和TCP/IP模型。2、物理層（1）通信信道、信號(hào)、寬

7、帶、碼元、波特、速率、信源與信宿等基本概念，奈奎斯特定理與香農(nóng)定理，編碼與調(diào)制，電路交換、報(bào)文交換與分組交換，數(shù)據(jù)報(bào)與虛電路。（2）雙絞線、同軸電纜、光纖與無(wú)線傳輸介質(zhì)，物理層接口的特性，中繼器，集線器。3、數(shù)據(jù)鏈路層（1）數(shù)據(jù)鏈路層的功能，組幀，差錯(cuò)控制（檢錯(cuò)與糾錯(cuò)編碼）。（2）流量控制、可靠傳輸與滑輪窗口機(jī)制，停止-等待協(xié)議，后退N幀協(xié)議(GBN)，選 擇重傳協(xié)議(SR)。（3）頻分多路復(fù)用、時(shí)分多路復(fù)用、波分多路復(fù)用、碼分多路復(fù)用的概念和基本原理 ALOHA協(xié)議、CSMA協(xié)議、CSMA/CD協(xié)議、CSMA/CA協(xié)議、令牌傳遞協(xié)議。（4）局域網(wǎng)的概念及其體系結(jié)構(gòu)，以太網(wǎng)與IEEE 802.

8、3標(biāo)準(zhǔn)協(xié)議，IEEE802.11標(biāo)準(zhǔn)協(xié)議，令牌環(huán)網(wǎng)。（5）廣域網(wǎng)的概念，PPP協(xié)議，HDLC協(xié)議。（6）網(wǎng)橋的概念和原理，交換機(jī)及其工作原理。4、網(wǎng)絡(luò)層（1）網(wǎng)絡(luò)層的功能，異構(gòu)網(wǎng)絡(luò)互聯(lián)，路由與轉(zhuǎ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é)議，自治系統(tǒng)，域內(nèi)路由與域間路由，RIP路由協(xié)議、OSPF路由協(xié)議、BGP路由協(xié)議。（6）組播的概念，IP組播地址。（7）移動(dòng)IP的概念，移動(dòng)I

9、P的通信過(guò)程。（8）路由器的組成和功能，路由表與路由轉(zhuǎn)發(fā)。5、傳輸層（1）傳輸層的功能，傳輸層尋址與端口，無(wú)連接服務(wù)與面向連接服務(wù)。（2）UDP協(xié)議，UDP數(shù)據(jù)報(bào)，UDP校驗(yàn)。（3）TCP協(xié)議，TCP段，TCP連接管理，TCP可靠傳輸，TCP流量控制與擁塞控制。6、應(yīng)用層（1）客戶/服務(wù)器模型，P2P模型。（2）DNS概念，層次域名空間，域名服務(wù)器，域名解析過(guò)程。（3）FTP協(xié)議的工作原理，控制連接與數(shù)據(jù)連接。（4）電子郵件系統(tǒng)的組成結(jié)構(gòu)，電子郵件格式與MIME，SMTP協(xié)議與POP3協(xié)議。（5）WWW的概念與組成結(jié)構(gòu)，HTTP協(xié)議。四、 考試要求（一）數(shù)據(jù)結(jié)構(gòu)1、 掌握有關(guān)數(shù)據(jù)結(jié)構(gòu)的基本概念

10、，包括數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)。2、 掌握算法的基本概念以及算法分析的基本方法。3、 熟練掌握線性表的基本概念，在兩種存儲(chǔ)結(jié)構(gòu)下的構(gòu)造原理及相應(yīng)的操作。4、 熟練掌握堆棧和隊(duì)列的基本概念與特征以及在兩種存儲(chǔ)結(jié)構(gòu)下如何對(duì)堆棧和隊(duì)列進(jìn)行插入和刪除等操作，具備使用堆棧與隊(duì)列解決實(shí)際問(wèn)題的能力。5、 熟練掌握串的基本概念以及串的存儲(chǔ)結(jié)構(gòu)和相關(guān)的算法。6、 掌握數(shù)組、廣義表和稀疏矩陣的基本概念以及基本操作。7、 掌握樹(shù)型結(jié)構(gòu)的邏輯特征以及各種存儲(chǔ)結(jié)構(gòu)的構(gòu)造原理，能夠靈活運(yùn)用基于樹(shù)的三種遍歷方法。8、 掌握二叉排序樹(shù)的邏輯特征、建立過(guò)程， 具備靈活運(yùn)用二叉樹(shù)解決實(shí)際問(wèn)題的能力。9、 了解圖的邏輯結(jié)構(gòu)的特點(diǎn)

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

12、分級(jí)結(jié)構(gòu)與主存儲(chǔ)器的技術(shù)指標(biāo)，了解SRAM、DRAM、EPROM、閃速存儲(chǔ)器、相聯(lián)存儲(chǔ)器的工作原理，掌握Cache存儲(chǔ)器、虛擬存儲(chǔ)器的功能和基本工作原理。4、 熟練掌握指令格式、指令和數(shù)據(jù)的尋址方式，理解RISC和CISC的特點(diǎn)。5、 掌握CPU的功能、基本組成和各個(gè)部分的工作流程，了解微程序控制器的基本工作原理，了解微程序控制技術(shù)和硬布線控制技術(shù)，了解流水CPU的工作原理及特點(diǎn)。6、 掌握總線系統(tǒng)的基本概念和基本技術(shù)以及總線仲裁方式的基本工作原來(lái)和特點(diǎn)，了解PCI總線的特點(diǎn)。7、 理解顯示設(shè)備、打印設(shè)備、硬盤的工作原理和特點(diǎn)，能夠計(jì)算一些常用的技術(shù)指標(biāo)。8、 了解外圍設(shè)備的定時(shí)方式、信息交換方式的工作原理和特點(diǎn)，理解程序查詢方式、中斷方式和DMA方式原理，了解通道方式。（三）計(jì)算機(jī)網(wǎng)絡(luò)1、 掌握計(jì)算機(jī)網(wǎng)絡(luò)的基本概念、基本原理和基本方法。2、 掌握計(jì)算機(jī)網(wǎng)絡(luò)的體系結(jié)構(gòu)和典型網(wǎng)絡(luò)協(xié)議，了解典型網(wǎng)絡(luò)設(shè)備的組成和特點(diǎn)，理解典型網(wǎng)絡(luò)設(shè)備的工作原理。3、 能