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

1、中國(guó)科學(xué)院大學(xué)碩士研究生入學(xué)考試計(jì)算機(jī)原理考試大綱本計(jì)算機(jī)原理考試大綱適用于中國(guó)科學(xué)院大學(xué)非計(jì)算機(jī)科學(xué)與技術(shù)一級(jí)學(xué)科下各 專(zhuān)業(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ì)算、畫(huà)圖、分析）等。三、考試內(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)

3、的基礎(chǔ)上對(duì)堆棧與隊(duì)列實(shí)施插入與刪除等基本操作對(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ēng)矩陣和稀疏矩陣的壓縮存儲(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）圖的定義，基本概念，圖的分類(lèi)，常用名詞術(shù)語(yǔ)。（ 2）圖的鄰接矩陣存儲(chǔ)方法、鄰接表存儲(chǔ)方法的構(gòu)造原理。（3）圖的遍歷操作。（ 4）最小生成樹(shù)，最短路徑， AO

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

5、構(gòu)。2、運(yùn)算方法和運(yùn)算器（ 1）數(shù)據(jù)與文字的表示方法。（ 2）定點(diǎn)加法、減法運(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ī)讀寫(xiě)存儲(chǔ)器。（ 3）只讀存儲(chǔ)器和閃速存儲(chǔ)器。（ 4）高速存儲(chǔ)器。（5） cache存儲(chǔ)器。（ 6）虛擬存儲(chǔ)器。4、指令系統(tǒng)（ 1）指令系統(tǒng)的發(fā)展與性能要求。（ 2）指令格式。（ 3）操作數(shù)類(lèi)型。4）指令和數(shù)據(jù)的尋址方式。5）典型指令。5、中央處理器（ 1）CPU 的功能和組成。（2）指令周期。（ 3）時(shí)序產(chǎn)生器和控制方式。（4）微程序控制器。（ 5）微程序設(shè)計(jì)技術(shù)。（ 6）

6、硬布線控制器。（ 7）流水 CPU。（ 8） RISC CPU 。6、總線系統(tǒng)（ 1）總線的概念和結(jié)構(gòu)形態(tài)。（ 2）總線接口。（3）總線的仲裁定時(shí)和數(shù)據(jù)傳送模式。（ 4）HOST 總線和 PCI 總線。（ 5） InfiniBand 標(biāo)準(zhǔn)。7、外圍設(shè)備（1）外圍設(shè)備概述。（2）磁盤(pán)存儲(chǔ)設(shè)備及其技術(shù)發(fā)展。（3）磁帶存儲(chǔ)設(shè)備。（4）光盤(pán)和磁光盤(pán)存儲(chǔ)設(shè)備。（ 5）顯示設(shè)備。（ 6）輸入設(shè)備和打印設(shè)備。8、輸入輸出系統(tǒng)（ 1）外圍設(shè)備的速度分級(jí)與信息交換方式。（2）程序查詢(xún)方式。（3）程序中斷方式。（ 4）DMA 方式。5）通道方式。（三）計(jì)算機(jī)網(wǎng)絡(luò)（ 50 分）1、緒論 （1）計(jì)算機(jī)網(wǎng)絡(luò)的概念、分類(lèi)

7、、標(biāo)準(zhǔn)、組成與功能。（ 2）計(jì)算機(jī)網(wǎng)絡(luò)分層結(jié)構(gòu)，協(xié)議、接口、服務(wù)等概念，ISO/OSI 模型和 TCP/IP 模型。2、物理層（1）通信信道、信號(hào)、寬帶、碼元、波特、速率、信源與信宿等基本概念，奈奎斯特定理 與香農(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ù)用、碼分多路

8、復(fù)用的概念和基本原理ALOHA 協(xié)議、 CSMA 協(xié)議、 CSMA/CD 協(xié)議、 CSMA/CA 協(xié)議、令牌傳遞協(xié)議。 （4）局域網(wǎng)的概念及其體系結(jié)構(gòu)，以太網(wǎng)與IEEE 802.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

9、 協(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) IP 的通信過(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)客戶(hù)/服務(wù)器模型，P2P模型。( 2) DNS 概念，層次域名空

10、間，域名服務(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)的基本概念，包括數(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、熟練掌握串的基本概念

11、以及串的存儲(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)以及常用的兩種存儲(chǔ)方法，了解最小生成樹(shù)(Prim 算法和Kruskal 算法 )、最短路徑、拓?fù)渑判虻木唧w求解過(guò)程。10、掌握各種順序文件的結(jié)構(gòu)與相應(yīng)的查找方法以及各種查找算法之間時(shí)空效率的差異。了解散列文件的建立、散列函數(shù)的選擇（構(gòu)造 ）原則、處理散列沖突的方法以及基于散列的查找。11、熟練掌握各種排序方法的排序特

12、點(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)的分類(lèi)、分級(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è)備、硬盤(pán)的工作原理和特點(diǎn)，能夠計(jì)算一些常用的技術(shù)指標(biāo)。8、了解外圍設(shè)備的定時(shí)方式、信息交換方式的工作原理和特點(diǎn)，理解程序查詢(xú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、能夠運(yùn)用計(jì)算機(jī)網(wǎng)絡(luò)的基