PAGEPAGE22022年研究生入學考試自命題科目考試大綱科目代碼：903科目名稱：計算機綜合一、參考書目1.《數據結構（C語言版）第二版》嚴蔚敏主編，人民郵電出版社,2015；2.《計算機網絡》（第7版），謝希仁，電子工業出版社，2017；3.《ComputerNetworking:ATopDownApproach》,JamesF.KuroseandKeithW.Rose(陳鳴譯),機械工業出版社,2017。二、考試內容及要求（一）數據結構1．緒論考試內容：數據結構，抽象數據類型，時間復雜度，空間復雜度。考試要求：了解《數據結構》的研究內容，數據結構的基本概念和術語，熟悉抽象數據類型的表示與實現，掌握算法的時間復雜度的計算方法。2．線性表考試內容：線性表的類型定義、順序表示和實現、鏈式表示和實現，線性表在一元多項式相加中的應用。考試要求：（1）了解線性表的邏輯結構特性，線性表的兩種存儲實現方式和描述方法。（2）掌握順序表的定義與實現，包括查找、插入、刪除算法的實現。（3）掌握在各種鏈式結構中實現線性表操作的基本方法，能在實際應用中選用適當的鏈表結構。（4）能夠從時間和空間復雜度的角度綜合比較線性表兩種存儲結構的不同特點及其適用場合。（5）了解線性表在一元多項式相加中的應用。3．棧和隊列考試內容：棧的定義、表示和實現，隊列的定義、表示和實現，棧的應用，棧與遞歸的實現。考試要求：（1）了解棧和隊列的定義、特性，并能正確應用它們解決實際問題。（2）掌握棧的順序表示、鏈式表示以及相應操作的實現。注意棧空和棧滿的條件。（3）掌握隊列的順序表示、鏈式表示以及相應操作的實現。注意循環隊列中隊頭與隊尾指針的變化情況。（4）了解棧與遞歸的實現。4．串考試內容：串的類型定義，串的表示和實現，串的模式匹配算法。考試要求：（1）了解串的定義、基本操作。（2）掌握順序存儲結構上串各種操作的方法。（3）掌握KMP算法。5．數組與廣義表考試內容：數組，稀疏矩陣，數組的順序表示，壓縮存儲，廣義表。考試要求：（1）了解數組的定義，掌握數組的順序表示和實現。（2）掌握特殊矩陣、稀疏矩陣壓縮存儲方式。（3）了解廣義表的概念、表示及存儲結構。6．樹和二叉樹考試內容：二叉樹與樹，二叉樹性質，二叉樹與樹的存儲結構，二叉樹的遍歷和線索化，森林與二叉樹的轉換，赫夫曼樹及其應用。考試要求：（1）了解樹和二叉樹的定義和性質。（2）掌握二叉樹的結構特性、存儲結構及適用范圍、遍歷算法。（3）掌握樹存儲結構及其特點、樹、森林與二叉樹的轉換方法。（4）掌握建立赫夫曼樹和赫夫曼編碼的方法及帶權路徑長度的計算。7．圖考試內容：圖的定義和存儲結構、圖的遍歷、圖的連通性問題、拓撲排序、關鍵路徑、最短路徑。考試要求：（1）理解圖的基本概念，熟悉圖的各種存儲結構及其構造算法。（2）掌握圖的深度優先和廣度優先兩種路徑遍歷算法。（3）了解AOV網絡、AOE網絡。（4）掌握拓撲排序和關鍵路徑算法。（5）掌握kruskul和prim算法構造最小生成樹算法。（6）掌握Dijkstra算法求解單源最短路徑，理解floyd算法求多源頂點間最短路徑問題。7．查找考試內容：順序表、有序表的查找，二叉排序樹和平衡二叉樹，哈希表的構造方法和處理沖突的方法。考試要求：（1）掌握順序表和有序表的查找算法及其性能分析方法。（2）掌握二叉排序樹的構造和查找算法及其性能分析方法。（3）理解AVL樹的維護平衡方法。（4）理解B_樹、B+的特點、查找及構造方法。（5）掌握哈希函數的構造及解決沖突的方法。8．查找考試內容：插入排序，快速排序，選擇排序，歸并排序，基數排序。考試要求：（1）掌握排序的基本概念和各種排序方法的特點，并能加以靈活應用。（2）掌握插入排序、交換排序、選擇排序、歸并排序的方法及其性能分析方法。（3）了解基數排序方法及其性能分析方法。（二）計算機網絡1．計算機網絡體系結構考試內容：計算機網絡的概念、組成與功能，計算機網絡的分類，因特網的組成，計算機網絡的性能，計算機網絡體系結構與參考模型。考試要求：（1）掌握計算機網絡的基本概念、組成和基本功能；掌握因特網邊緣和電路交換、報文交換與分組交換等因特網核心的基本概念；掌握衡量網絡性能的速率、帶寬、時延、時延帶寬積、往返時間RTT、吞吐量等概念；掌握網絡協議分層的基本原理和方法，計算機網絡協議、實體、接口和服務等概念；掌握TCP/IP協議的體系結構；掌握客戶/服務器、P2P等典型的網絡應用模型。（2）理解計算機網絡的分類方法和標準；理解計算機網絡的標準化工作及相關組織機構的特點和職能范圍；理解因特網的標準化工作過程。（3）了解計算機網絡與因特網的發展歷程和發展趨勢；了解網絡協議的ISO/OSI參考模型。2．物理層考試內容：數據通信的基礎知識，物理層下面的傳輸媒體，信道復用技術，數字傳輸系統，寬帶接入技術。考試要求：（1）掌握物理層的基本概念、數據通信系統模型、信道和信道容量等基礎知識；掌握頻分復用、時分復用、碼分復用等信道復用技術的基本原理；掌握ADSL、HFC和FTTx等寬帶接入技術的基本原理和實現方法。（2）理解導引型和非導引型各類傳輸媒體的特點和應用場合；理解奈奎斯特定理與香農定理的基本內容；理解信道編碼與調制的基本概念；理解統計時分復用的原理和基本實現方法；理解中繼器、集線器等典型物理層設備的工作原理和應用場合。（3）了解光的波分復用技術；了解SDH和SONET等數字傳輸系統。3．數據鏈路層考試內容：使用點對點信道的數據鏈路層和點對點協議PPP，使用廣播信道的數據鏈路層，以太網和CSMA/CD協議，無線局域網WLAN協議，高速以太網。考試要求：（1）掌握數據鏈路和幀的基本概念，數據鏈路層要解決的封裝成幀、透明傳輸、差錯檢測三個基本問題；掌握PPP協議的特點、幀格式和工作狀態；掌握CSMA/CD協議的基本內容和使用方式；掌握在物理層和鏈路層擴展以太網的原理和方法；掌握局域網交換機的工作原理和使用方法。（2）理解以太網MAC層的基本內涵；理解網橋的概念和基本原理；理解無線局域網WLAN協議IEEE802.11的工作原理和實現方法；理解100BASE-T、吉比特和10吉比特以太網的實現原理和方法；理解使用以太網進行寬帶接入的方法。（3）了解以太網信道利用率的分析和計算方法。4．網絡層考試內容：網絡層提供的服務，IP地址與IP協議，劃分子網和構造超網，網際控制報文協議ICMP協議，因特網的路由選擇協議；IP多播，虛擬專用網VPN和網絡地址轉換NAT。考試要求：（1）掌握網絡層提供的虛電路和數據報服務的基本原理和方法，虛擬互連網絡的概念；掌握IP地址、物理地址的概念，地址解析協議ARP作用、工作原理和實現方法；掌握IP層轉發分組的基本流程；掌握子網掩碼的概念和劃分子網的方法、使用子網時分組轉發的方法、使用無分類編址CIDR構造超網的原理和方法；掌握網際控制報文協議ICMP的作用、報文的種類和應用場合；掌握靜態路由與動態路由的基本概念，內部網關協議RIP、OSPF和外部網關協議BGP等典型因特網路由選擇協議的工作原理和應用場合，自治系統的基本概念；掌握虛擬專用網VPN和網絡地址轉換NAT的基本原理和實現方法。（2）理解IP數據報的格式及各協議字段的含義；理解地址聚合的概念和作用；理解典型路由器的基本構成部件；理解IP多播的概念、在局域網上進行硬件多播的實現方法、網際組管理協議IGMP和多播路由選擇協議的工作原理和實現方法。（3）了解IPv6的主要特點和各協議字段的含義；了解移動IP的概念和移動IP的通信過程。5．運輸層考試內容：運輸層協議的概念，用戶數據報協議UDP，可靠傳輸的工作原理，傳輸控制協議TCP的特點、TCP報文段的首部格式和TCP可靠傳輸的實現方法，TCP的流量控制和擁塞控制，TCP的運輸連接管理。考試要求：（1）掌握進程間通信的概念、運輸層端口的作用和意義；掌握UDP協議的特點、首部格式和應用場合；掌握TCP協議的特點和TCP連接的概念，停止等待協議、連續ARQ協議等可靠傳輸協議的工作原理；掌握TCP報文段首部各字段的含義和作用，TCP協議實現可靠傳輸的滑動窗口、字節編號、確認、超時重傳等基本機制；掌握擁塞控制的一般原理、TCP協議實現擁塞控制的方法。（2）理解選擇確認SACK的實現方法；理解TCP協議實現流量控制的方法；理解利用隨機早期檢測RED實現TCP擁塞控制的原理；理解TCP連接的建立、釋放等TCP運輸連接管理的實現方法。（3）了解影響TCP效率和TCP連接吞吐量的各類因素和TCP連接吞吐量的基本計算方法；了解TCP協議有限狀態機。6．應用層考試內容：域名系統DNS，文件傳輸協議FTP，遠程終端協議TELNET，萬維網WWW，電子郵件，動態主機配置協議DHCP，簡單網絡管理協議SNMP，應用進程跨越網絡的通信。考試要求：（1）掌握域名系統的基本概念、因特網的域名結構、域名服務器概念和作用、域名查詢的過程；掌握FTP協議的概念和FTP的基本工作原理；掌握萬維網的基本概念，統一資源定位符URL的作用，超文本傳送協議HTTP的工作原理和實現方法，萬維網文檔、信息檢索系統和微博的概念；掌握電子郵件的概念，簡單郵件傳送協議SMTP的工作原理，電子郵件的信息格式，郵件讀取協議POP3和IMAP的作用和工作原理，基于萬維網實現電子郵件的方法，通用因特網郵件擴充MIME的實現方法；掌握DHCP協議的作用和工作原理；掌握網絡管理的基本概念和SNMP協議的實現方法。（2）理解簡單文件傳送協議TFTP的工作原理；理解系統調用和應用編程接口的概念。（3）了解TELNET協議的作用和基本工作原理；了解SNMP的協議數據