834 計算機專業基礎綜合(數據結構、計算機網絡)研究生入學考試大綱

數據結構部分(占60%)

【考試范圍】

線性表(包括隊列、堆棧等特殊線性表)的基本邏輯結構特征理解與應用;線性表(包括隊列、堆棧等特殊線性表)的物理存貯結構;特殊矩陣的存貯及應用;樹、圖等非線性結構的基本邏輯結構特征理解與應用;樹、圖等非線性結構的物理存貯結構。排序與查找算法;一些算法的設計與時間復雜度分析。

【具體內容】

一 緒論

1引言

2 什么是數據結構

3 相關基本概念和術語

4 算法的基本特征

5 算法分析相關概念

二 線性表

1 線性表的概念，線性表的抽象數據類型，基本操作

2 線性表的順序存儲結構：靜態分配，動態分配

3 順序表的插入刪除算法，移動元素次數分析

4 順序存儲結構的優缺點，引出單鏈表的結構類型定義

5 單鏈表的算法：生成先進先出單鏈表，后進先出單鏈表

6 單鏈表的算法：生成不帶表頭的遞增有序單鏈表，生成帶表頭的遞增有序單鏈表

7 單鏈表的算法：在指定位置插入一個新結點;刪除指定值的結點;在指定位置刪除一個結點;

8 單鏈表的合并：兩個遞增有序的單鏈表合并成一個遞增有序的單鏈表

9 循環鏈表的概念，雙向循環鏈表的概念，插入和刪除結點

10 多項式的鏈表表示，算法思想

三 棧和隊列

1 棧的相關概念與特性

2 順序棧的基本操作

3 鏈式棧的基本操作

4 棧的應用

5 隊列的相關概念

6 鏈式隊列的基本操作

7 順序隊列的基本操作

四 數 組

1 抽象數據類型數組的說明

2 數組的物理結構

3 特殊矩陣的壓縮存儲: 對稱矩陣與三對角矩陣的壓縮存儲

4 稀疏矩陣的壓縮存儲：三元組順序表與十字鏈表

5 稀疏矩陣的運算(轉置算法)

6 廣義表的概念：概念、物理結構、遞歸算法

五 樹與二叉樹

1 樹的有關概念

2 二叉樹的定義與性質

3 二叉樹的存儲結構

4 二叉樹的遍歷

5二叉樹遍歷的應用

6 樹的存儲結構

7 樹與二叉樹的相互轉換

8 樹與森林的遍歷

9 哈夫曼樹

10、哈夫曼算法

六 圖

1 圖的定義及術語

2 圖的物理存貯結構：鄰接矩陣、鄰接表、十字鏈表和鄰接多重表

3 圖的遍歷：深度優先搜索遍歷與廣度優先搜索遍歷

4 圖的連通性問題：DFS與BFS生成樹、強連通分量的求解，最小生成樹

5 有向無環圖及應用: 拓撲排序、關鍵路徑

6 最短路徑：迪杰斯特拉算法、弗洛伊德算法

七 查找

1 查找問題概述

2 順序查找法

3 折半查找法

4 分塊查找法

5 二叉排序樹查找法

6 平衡二叉排序樹查找法

7 B-樹查找法和B+樹查找法

8 鍵樹查找法

9 哈希查找法

八 排序

1 查找問題概述、插入排序法

2 交換排序法

3 選擇排序法

4 歸并排序法

5 基數排序法

計算機網絡部分(占40%)

【考試范圍】

重點考查計算機網絡的構成和計算機網絡核心的兩種數據交換方法、計算機網絡的層次化體系結構、計算機網絡的性能度量指標、四種主流的因特網應用的工作原理(萬維網/電子郵件/域名解析/P2P)、數據可靠傳輸的基本原理和方法、數據傳輸中流量控制和擁塞控制的基本原理和方法、計算機網絡中的三種設備標識方式(域名/IP地址/MAC地址)及其映射關系、端口的概念和TCP/UDP的工作原理、IP協議和路由協議、共享信道的協調方法和以太網的工作原理、無線局域網的構成和基本工作原理等內容。

【具體內容】

一 計算機網絡和因特網

1 計算機網絡的構成和功能

2 因特網的接入方式

3 因特網核心的數據交換方式

4 計算機網絡的層次模型及相關概念

5 OSI/RM模型和TCP/IP模型

二 應用層

1 應用層協議的原理及網絡應用模型

2 Web應用和HTTP協議

3 因特網中的電子郵件

4 域名服務DNS

5 P2P文件共享

三 運輸層

1 運輸層的工作原理和提供的服務

2 多路復用與多路分解

3 UDP協議和TCP協議的報文結構和工作機制

4 可靠數據傳輸的基本原理及其在TCP協議中的應用

5 擁塞控制的基本原理及其在TCP協議中的應用

6 流量控制的基本原理及其在TCP協議中的應用

四 網絡層

1 網絡層的工作原理及其提供的服務

2 虛電路和數據報網絡的工作原理及對比

3 路由器的構成和工作原理

4 IP地址的分類、子網劃分和CIDR的工作原理

5. IPv4分組結構及轉發機制

6 NAT協議的工作原理和應用場景

7 ARP、DHCP和ICMP協議

8 選路算法：RIP、OSPF和BGP-4

9 IP組播的概念和IP組播地址

10 IPv6地址、數據報格式和鄰居發現協議

五 數據鏈路層和以太網

1 數據鏈路層的工作原理及其提供的服務

2 差錯檢測和糾錯技術

3 多址訪問協議的分類和工作原理

4 鏈路層的編址方式

5 以太網

6 集線器和交換機的工作原理

7 點對點協議PPP

8 虛擬局域網

六 無線網絡和移動網絡

1 無線網絡的概念、組成、分類和工作原理

2 無線鏈路和網絡特征

3 802.11無線局域網的工作原理

4 無線局域網中的多址訪問協議

5 移動IP