碩士研究生入學考試《數據結構》考試大綱

一、考試要求

《數據結構》是一門專業基礎課，要求考生能夠理解數據結構的基本概念;掌握數據結構中邏輯結構、存儲結構的基本概念和差異，以及各種基本操作的實現;在掌握基本的數據處理原理和方法的基礎上，能夠對算法進行設計與分析;能夠選擇合適的數據結構和方法進行問題求解;能夠針對具體問題設計正確的數據結構加以應用;具備采用類c或c++或JAVA語言設計與實現算法的能力。

本課程包括：算法的基本概念、分析和設計方法;軟件開發中常用的各類結構，包括線性結構、樹結構、圖結構;查找、排序等各類常用算法。主要考察學生對數據結構基礎知識的理解、是否具備對現有常用結構和算法的應用能力、是否具備針對具體應用設計合適數據結構的能力。

二、考試題型及權重(共75分)

⑴選擇: 30分;

⑶簡答題:15分;

⑷算法應用題:20分;

⑸算法設計題:10分。

三、考查范圍

(1)基本概念和算法分析

本部分的目的是介紹數據結構中常用的基本概念和術語以及學習數據結構的意義。重點要求理解數據結構的基本概念、算法的基本要素和基本要求。掌握簡單的算法時間/空間復雜度分析方法。理解抽象數據結構的定義，理解最好、最壞和平均復雜度的分析和計算方法。

(2)線性表

本部分的目的是介紹線性表的邏輯結構和各種存儲表示方法，以及定義在邏輯結構上的各種基本運算及其在存儲結構上如何實現這些基本運算。重點要求熟練掌握線性表的定義和基本操作，能夠熟練掌握線性表的兩種實現方法(順序存儲和隨機存儲)，熟知線性表的應用范圍。理解線性表的各種存儲結構、操作實現的異同點，優缺點。

(3)棧和隊列

本部分的目的是介紹棧和隊列的邏輯結構定義及在兩種存儲結構上如何實現棧和隊列的基本運算。重點要求熟練掌握棧和隊列的基本概念，以及棧和隊列的兩種實現方法(順序存儲結構實現和鏈式存儲結構實現)及其操作的實現。能夠掌握棧和隊列的基本應用。

(4)樹和二叉樹

本部分的目的是介紹二叉樹的定義、性質、存儲結構、遍歷、線索化;樹的定義、存儲結構、遍歷、樹和森林的轉換及赫夫曼樹及其赫夫曼編碼等內容。重點要求熟練掌握樹的基本概念、基本性質。熟練掌握二叉樹的定義及其主要特征、二叉樹的順序存儲結構和鏈式存儲結構、二叉樹的遍歷操作;掌握線索二叉樹的基本概念和構造;掌握基于二叉樹遍歷操作所衍生出的各類操作，例如二叉樹的構造、二叉樹葉子節點的統計、求二叉樹深度操作等。理解樹的存儲結構，掌握森林和二叉樹的相互轉換，樹和森林的遍歷操作。理解二叉排序樹的基本原理和算法，掌握平衡二叉樹的各種操作;掌握哈夫曼(Huffman)樹和哈夫曼編碼，并能夠在實際的問題中加以應用。

(5)圖

本部分的目的是介紹圖的基本概念、兩種常用的存儲結構、兩種遍歷方法以及圖的應用算法。重點要求掌握圖的基本概念，基本性質。掌握圖的存儲方法，掌握圖存儲的鄰接矩陣法和鄰接表法。掌握圖的兩種遍歷方法：深度優先遍歷、廣度優先遍歷。理解基于圖的最小(代價)生成樹算法、最短路徑算法、拓撲排序算法。了解關鍵路徑算法。

(6)查找

本部分的目的是介紹線性表、樹和哈希表的查找方法、算法實現以及各種查找方法的時間性能(平均查找長度)分析。重點要求掌握順序查找、折半查找、二叉排序樹和哈希表查找的基本思想和算法實現。了解平衡二叉樹、B-樹的基本概念及基本操作、B+樹的基本概念。能夠理解各種不同查找算法的適用情況，以及不同算法的性能分析。

(7)內部排序

內部排序部分的目的是介紹五大類內部排序方法的基本思想、排序過程、算法實現、時間和空間性能的分析;并且對各種排序方法進行比較。重點要求掌握直接插入排序、快速排序、堆排序和歸并排序的基本思想和排序過程。理解基數排序、折半插入排序等排序方法的基本思想和排序過程。掌握各類排序方法的性質、效率對比。

碩士研究生入學考試《計算機網絡》考試大綱

一、考試要求

1. 掌握計算機網絡的基本概念、原理和方法。

2. 理解TCP/IP協議。

二、考試題型及權重(共75分)

1. 選擇題: 20題，40分;

2. 簡答題: 2題，10分;

4. 綜合應用: 2題，25分;

三、考查范圍

1. 第一章 計算機網絡概述

(1)因特網的邏輯組成與端到端設計原則;

(2)計算機網絡的主要分類方法;

(3)電路交換、報文交換與分組交換的區別;

(4)計算機網絡協議的分層方法;

(5)OSI模型與TCP/IP模型;

2. 第二章 物理層

(1)數據傳輸的基本概念，包括：數據與信號的關系、通信方式和傳輸介質;

(2)常見編碼方式與基本帶通調制技術;

(3)信道的極限容量，包括：奈奎斯特定理與香農定理;

(4)多路復用技術;

3. 第三章 數據鏈路層

(1)數據鏈路層的基本概念，包括：鏈路協議分類、幀的概念和鏈路層的三個基本問題;

(2)常見的組幀技術;

(3)CRC檢錯編碼方法;

(4)PPP協議的主要內容，包括：協議特點，基本組成和幀格式;

(5)以太網的主要內容：CSMA/CD協議、MAC地址和幀格式;

(6)網橋與交換機的工作原理;

(7)VLAN的工作原理;

4. 第四章 網絡層

(1)網絡層的基本概念，包括：異構互連問題、網絡層服務模型和設計思想;

(2)IP協議的基本概念，包括：主要特點和協議組成;

(3)IP編址方法，包括：分類的IP地址、帶掩碼的IP地址、CIDR編址;

(4)NAT地址轉換技術的工作原理;

(5)ARP協議的工作原理;

(6)IP分組的封裝格式，包括：TTL字段的作用、IP分片方法;

(7)ICMP協議的作用;

(8)RIP路由協議的工作原理和特點;

(9)OSPF 路由協議的特點和工作原理;

5. 第五章 傳輸層

(1)進程間的通信與端口的概念;

(2)兩種運輸層協議TCP和UDP的區別;

(3)UDP協議，包括：報文格式和主要特點;

(4)TCP報文段的分段與首部格式;

(5)TCP的滑動窗口機制和確認號;

(6)TCP的可靠傳輸機制，包括流量控制方法和擁塞控制方法;

(7)TCP的連接管理;

6. 第6章 應用層

(1) 兩種網絡應用模型的主要特點，包括：客戶/服務器模型和P2P模型;

(2) DNS系統工作原理;

(3)DHCP協議的作用;

(4) 電子郵件的基本概念，包括SMTP協議和pop3協議;

(5)WWW服務和HTTP協議的基本概念;