本《計算機學科綜合(非專業(yè))》考試大綱適用于中國科學院大學非計算機科學與技術一級學科下各專業(yè)的碩士研究生入學考試?！队嬎銠C學科綜合(非專業(yè))》主要內(nèi)容包括數(shù)據(jù)結構、操作系統(tǒng)和計算機網(wǎng)絡三大部分。要求考生對計算機科學與技術及相關學科的基本概念有較深入、系統(tǒng)的理解；掌握各種數(shù)據(jù)結構的定義和實現(xiàn)算法；掌握操作系統(tǒng)和計算機網(wǎng)絡所涉及的關鍵內(nèi)容，并具有綜合運用所學知識分析問題和解決問題的能力。

一、考試內(nèi)容數(shù)據(jù)結構

1、緒論

（1）數(shù)據(jù)結構的基本概念，數(shù)據(jù)的邏輯結構、存儲結構。

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

2、線性表

（1）線性關系、線性表的定義，線性表的基本操作。

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

3、堆棧與隊列

（1）堆棧與隊列的基本概念、基本操作。

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

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

4、串

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

（2）串的模式匹配算法和改進的 KMP 算法

5、數(shù)組和廣義表

（1）數(shù)組的概念，以及表示和實現(xiàn)

（2）矩陣（對稱矩陣和稀疏矩陣）的壓縮存儲

（3）廣義表的基本概念

6、樹與二叉樹

（1）樹的定義和性質(zhì)

（2）二叉樹的概念、性質(zhì)和實現(xiàn)

（3）二叉樹的遍歷和線索二叉樹

（4）樹和森林

（5）赫夫曼樹及其應用

（6）回溯法與樹的遍歷

（7）樹的計數(shù)

7、圖

（1）圖的定義，基本概念，圖的分類，常用名詞術語。

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

（3）圖的遍歷操作。

（4）圖的連通性、最小生成樹

（5）最短路徑的計算

（6）AOV 網(wǎng)與拓撲排序。

8、查找

（1）靜態(tài)查找表：順序表、有序表、靜態(tài)樹表以及索引表的查找。

（2）動態(tài)查找表：二叉排序樹和平衡二叉樹，以及B 樹和 B+樹的基本概念和操作。

（3）哈希表：基本概念和構造方法，沖突處理方法和查詢及性能分析。

9、內(nèi)排序

（1）排序的基本概念，排序方法的分類。

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

操作系統(tǒng)

1、操作系統(tǒng)概述

（1）計算機基本構成、處理器的內(nèi)部結構；

（2）操作系統(tǒng)的概念、演變歷程、特性、分類、運行環(huán)境、功能

（3）存儲器的層次結構：高速處理器緩存、內(nèi)存、外存

2、、進程

進程概念、進程描述及進程狀態(tài)轉(zhuǎn)換

3、線程、對稱多處理 SMP 和微內(nèi)核

（1）線程的概念，定義線程的必要性和可能性；

（2）線程的功能特性與實現(xiàn)方式；

（3）對稱多處理SMP 體系結構；

（4）操作系統(tǒng)的體系架構（微內(nèi)核與宏內(nèi)核）及其性能特性。

4、并發(fā)性

（1）并發(fā)性問題及相關概念，如臨界區(qū)、互斥、信號量和管程等；

（2）進程互斥、同步和通信的各種算法；

（3）死鎖的概念、死鎖的原因和條件

（4）死鎖的預防、避免和檢測算法。

5、存儲器管理

（1）分區(qū)存儲管理、覆蓋與交換；

（2）頁式管理及段式管理；

（3）段、頁式存儲管理方法及實現(xiàn)技術；

（4）虛存的原理及相關的各種算法和數(shù)據(jù)結構。

6、單處理器調(diào)度

（1）進程調(diào)度的各種算法及其特點。

7、多處理器調(diào)度和實時調(diào)度

（1）多處理器對進程調(diào)度的影響

（2）多處理器環(huán)境下的進程和線程調(diào)度算法；

（3）實時進程的特點；

（4）限期調(diào)度和速率單調(diào)調(diào)度方法。

8、設備管理和磁盤調(diào)度

（1）操作系統(tǒng)中輸入/輸出功能的組織；

（2）中斷處理；

（3）設備驅(qū)動程序、設備無關的軟件接口和 spooling 技術；

（4）緩沖策略；

（5）磁盤調(diào)度算法；

（6）磁盤陣列 RAID 技術。

9、文件系統(tǒng)

（1）文件系統(tǒng)特點與文件組織方式；

（2）文件系統(tǒng)的數(shù)據(jù)結構；

（3）目錄的基本性質(zhì)及其實現(xiàn)方法；

（4）磁盤空間的管理；

（5）文件系統(tǒng)日志及作用

10、分布式系統(tǒng)

（1）分布式處理的特點、類型；

（2）多層體系結構、中間件技術；

（3）機群系統(tǒng)。。

計算機網(wǎng)絡

1、緒論

    （1）計算機網(wǎng)絡的概念、分類、標準、組成與功能

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

（3）計算機網(wǎng)絡的性能評價指標與評價方法

2、物理層

    （1）通信信道、信號、寬帶、碼元、波特、速率、信源與信宿等基本概念，電路交換、報文交換與分組交換

    （2）雙絞線，物理層接口的特性，中繼器，集線器

3、數(shù)據(jù)鏈路層

    （1）數(shù)據(jù)鏈路層的功能，組幀，差錯控制（檢錯與糾錯編碼） 

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

    （3）CSMA/CD、CSMA/CA 協(xié)議 

    （4）局域網(wǎng)的概念及其體系結構

4、網(wǎng)絡層

    （1）網(wǎng)絡層的功能，異構網(wǎng)絡互聯(lián)，分組轉(zhuǎn)發(fā)

    （2）路由算法，靜態(tài)路由與動態(tài)路由，距離矢量算法，鏈路狀態(tài)算法，路徑向量算法

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

    （4）IPv6 的主要特點，IPv6 地址

    （5）路由協(xié)議，自治系統(tǒng)，域內(nèi)路由與域間路由，RIP 路由協(xié)議、OSPF 路由協(xié)議、BGP 路由協(xié)議

    （6）組播的概念，IP 組播地址

    （7）路由器的組成和功能，路由表與路由轉(zhuǎn)發(fā)

5、傳輸層

    （1）傳輸層功能，多路分解與復用，傳輸層尋址與端口，無連接服務與面向連接服務

    （2）UDP 協(xié)議，UDP 數(shù)據(jù)報，UDP 校驗

（3）TCP 協(xié)議，連接管理，可靠傳輸，自適應重傳，流量控制與擁塞控制

6、應用層

    （1）基本服務模型，客戶/服務器模型，P2P 模型

    （2）DNS 概念，層次域名空間，域名服務器，域名解析過程

    （3）FTP 協(xié)議的工作原理，控制連接與數(shù)據(jù)連接

    （4）電子郵件系統(tǒng)的組成結構，SMTP 協(xié)議與 POP3 協(xié)議

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

（6）網(wǎng)關的基本概念與典型應用

二、考試要求數(shù)據(jù)結構

1、 建立有關數(shù)據(jù)結構最基本的概念，包括數(shù)據(jù)的邏輯結構、存儲結構和算法，算法分析的基本概念與基本方法

2、 掌握線性表的基本概念以及兩種存儲結構的構造原理，掌握在各種存儲結構下對線性表進行的基本操作的算法設計。

3、 掌握堆棧和隊列的基本概念與特征，掌握在兩種存儲結構下如何對堆棧和隊列進行插入和刪除等操作，以及利用堆棧與隊列解決實際問題的基本方法。

4、 充分了解串的基本概念、掌握串的存儲結構和相關的操作算法。

5、 掌握數(shù)組、廣義表和稀疏矩陣的基本概念，物理結構和基本操作的實現(xiàn)

6、 充分了解樹型結構的邏輯特征，掌握各種存儲結構的構造原理，能夠熟練地利用常用的三種遍歷方法，掌握利用二叉樹的遍歷操作解決實際問題的方法，掌握二叉排序樹的建立以及在二叉排序樹中查找一個結點存在與否的過程。了解回溯方法以及樹的遍歷問題。

7、 充分了解圖的邏輯結構的特點，掌握常用的兩種存儲方法，掌握最小生成樹(Prim 算法和 Kruskal 算法)、最短路徑、拓撲排序的具體求解過程。

8、 充分了解各種順序文件的結構與相應的查找方法；了解各種查找算法之間時空效率的差異；從結構與操作上了解散列文件的建立、散列函數(shù)的選擇(構造)原則、處理散列沖突的方法以及在散列文件中查找一個記錄存在與否的過程。

9、 充分了解各種排序方法的排序特點和排序過程，對于任意給出的數(shù)據(jù)元素序列，能夠熟練地采用指定排序方法進行排序，并且能夠?qū)γ恳环N排序方法排序過程中所進行的元素

之間的比較次數(shù)、相應排序算法的時間、空間、排序的穩(wěn)定性等性能進行簡單分析。

操作系統(tǒng)

1、  了解操作系統(tǒng)所管轄的軟、硬件資源；了解操作系統(tǒng)的關鍵概念，從整體上把握操作系統(tǒng)的特性與功能等概念；建立操作系統(tǒng)的資源管理和應用接口的職能概念。

2、   掌握進程的本質(zhì)特征，明確進程的動態(tài)特性，熟悉進程狀態(tài)間轉(zhuǎn)換的原因，建立進程是資源分配單元和一種運行實體的基本理念。

3、  理解引入線程作為基本運行實體的必要性和可能性；掌握線程各種實現(xiàn)方式及其特點；熟悉 SMP 體系結構、操作系統(tǒng)的體系架構。

4、  靈活運用信號量、管程等技術解決互斥和同步問題；理解死鎖的概念和產(chǎn)生死鎖的充分必要條件；熟練掌握死鎖的預防、避免和檢測算法；了解處理死鎖問題時避免饑餓的方法。

5、   理解存儲管理的功能；掌握段、頁式存儲管理方法及實現(xiàn)技術；掌握虛存的原理及相關的各種算法和數(shù)據(jù)結構。

6、 掌握進程調(diào)度的各種算法及其適用環(huán)境。

7、   熟悉掌握多處理器環(huán)境下進程和線程調(diào)度算法，了解實時進程的本質(zhì)，掌握限期調(diào)度和速率單調(diào)調(diào)度方法。

8、   理解輸入輸出設備及操作系統(tǒng)中輸入/輸出功能的組織、掌握中斷處理、設備驅(qū)動程序等技術，重點掌握各種用于提高性能的緩沖策略和磁盤調(diào)度算法；了解可提高性能和可靠性的各種磁盤陣列 RAID 配置方式。

9、   理解文件系統(tǒng)特點與文件組織，掌握文件系統(tǒng)的基本數(shù)據(jù)結構，了解文件、目錄的基本性質(zhì)及其實現(xiàn)方法；重點掌握磁盤空間的管理、文件系統(tǒng)的性能及可靠性、文件系統(tǒng)的安全性及保護機制等。

10、  了解分布式處理的特點、類型；掌握多層體系結構、中間件技術和機群系統(tǒng)的基本概念和特點。

計算機網(wǎng)絡

1、   了解計算機網(wǎng)絡的概念及分類，掌握計算機網(wǎng)絡分層結構及各層基礎協(xié)議，充分理解計算機網(wǎng)絡分層結構設計的基本思想及 ISO/OSI 模型和 TCP/IP 模型的本質(zhì)特征。

2、  了解物理層通信信道、信號、寬帶、碼元、波特、速率、信源與信宿等基本概念， 掌握電路交換、報文交換、分組交換、數(shù)據(jù)報與虛電路等基本原理，掌握中繼器、集線器的基本工作原理。

3、  理解數(shù)據(jù)鏈路層差錯控制機制及流量控制機制，掌握 CSMA/CA 協(xié)議、令牌傳遞協(xié)議的基本工作原理。

4、  了解 IPv4 與 IPv6 的基本特征和不同之處，深刻理解網(wǎng)絡層異構網(wǎng)絡互聯(lián)、路由與轉(zhuǎn)發(fā)、擁塞控制的基本概念和原理，掌握靜態(tài)路由與動態(tài)路由、距離-向量路由算法、鏈路狀態(tài)路由算法的基本原理，重點掌握ARP 協(xié)議、NAT 協(xié)議、ICMP 協(xié)議的工作原理及基本過程，重點掌握路由表設計及路由轉(zhuǎn)發(fā)的基本原理和過程。

5、  理解無連接服務與面向連接服務的基本原理，掌握 UDP 及 TCP 協(xié)議的基本工作過程及可靠傳輸、流量控制、擁塞控制機制。

6、 理解客戶/服務器模型、P2P 模型的基本概念，掌握域名解析、文件傳輸、電子郵件、

WWW 等典型應用的基本通信過程。

7、 能夠運用計算機網(wǎng)絡的基本概念、基本原理和基本方法進行網(wǎng)絡系統(tǒng)的分析、設計和應用。

三、主要參考書目

1、《數(shù)據(jù)結構（C 語言版）》； 嚴蔚敏，吳偉民 編著；北京：清華大學出版社，2011 年

2、《計算機操作系統(tǒng)（第三版）》；湯小丹，梁紅兵，哲鳳屏，湯子瀛；西安電子科技大學出版社，2011 年

3、計算機網(wǎng)絡（第五版）. [美] 特南鮑姆，[美] 韋瑟羅爾  著  嚴偉，潘愛民  譯， 北京：清華大學出版社，2012 年。

4、計算機網(wǎng)絡（第六版）. 謝希仁編著，電子工業(yè)出版社，2013 年。

 

添加中國科學院大學學姐微信，或微信搜索公眾號“考研派小站”，關注[考研派小站]微信公眾號，在考研派小站微信號輸入[中國科學院大學考研分數(shù)線、中國科學院大學報錄比、中國科學院大學考研群、中國科學院大學學姐微信、中國科學院大學考研真題、中國科學院大學專業(yè)目錄、中國科學院大學排名、中國科學院大學保研、中國科學院大學公眾號、中國科學院大學研究生招生）]即可在手機上查看相對應中國科學院大學考研信息或資源。