硕士研究生入学考试《数据结构》考试大纲

一、考试要求

《数据结构》是一门专业基础课，要求考生能够理解数据结构的基本概念;掌握数据结构中逻辑结构、存储结构的基本概念和差异，以及各种基本操作的实现；在掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析；能够选择合适的数据结构和方法进行问题求解；能够针对具体问题设计正确的数据结构加以应用；具备采用类c或c++或JAVA语言设计与实现算法的能力。

本课程包括：算法的基本概念、分析和设计方法；软件开发中常用的各类结构，包括线性结构、树结构、图结构；查找、排序等各类常用算法。主要考察学生对数据结构基础知识的理解、是否具备对现有常用结构和算法的应用能力、是否具备针对具体应用设计合适数据结构的能力。

二、主要参考书目

《数据结构 (C语言版)》，严蔚敏，吴伟民， 清华大学出版社；

三、其它参考书目

《数据结构与算法分析（ java语言描述）（第二版）》，Frank M.Carrano，清华大学出版社；

《数据结构（用面向对象方法与C++语言描述）第二版》，殷人昆，清华大学出版社

四、考试题型及权重（共75分）

⑴选择: 30分；

⑶简答题:15分；

⑷算法应用题:20分；

⑸算法设计题:10分。

五、考查范围

（1）基本概念和算法分析

本部分的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义。重点要求理解数据结构的基本概念、算法的基本要素和基本要求。掌握简单的算法时间/空间复杂度分析方法。理解抽象数据结构的定义，理解最好、最坏和平均复杂度的分析和计算方法。

（2）线性表

本部分的目的是介绍线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。重点要求熟练掌握线性表的定义和基本操作，能够熟练掌握线性表的两种实现方法（顺序存储和随机存储），熟知线性表的应用范围。理解线性表的各种存储结构、操作实现的异同点，优缺点。

（3）栈和队列

本部分的目的是介绍栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本运算。重点要求熟练掌握栈和队列的基本概念，以及栈和队列的两种实现方法（顺序存储结构实现和链式存储结构实现）及其操作的实现。能够掌握栈和队列的基本应用。

（4）树和二叉树

本部分的目的是介绍二叉树的定义、性质、存储结构、遍历、线索化；树的定义、存储结构、遍历、树和森林的转换及赫夫曼树及其赫夫曼编码等内容。重点要求熟练掌握树的基本概念、基本性质。熟练掌握二叉树的定义及其主要特征、二叉树的顺序存储结构和链式存储结构、二叉树的遍历操作；掌握线索二叉树的基本概念和构造；掌握基于二叉树遍历操作所衍生出的各类操作，例如二叉树的构造、二叉树叶子节点的统计、求二叉树深度操作等。理解树的存储结构，掌握森林和二叉树的相互转换，树和森林的遍历操作。理解二叉排序树的基本原理和算法，掌握平衡二叉树的各种操作；掌握哈夫曼(Huffman)树和哈夫曼编码，并能够在实际的问题中加以应用。

（5）图

本部分的目的是介绍图的基本概念、两种常用的存储结构、两种遍历方法以及图的应用算法。重点要求掌握图的基本概念，基本性质。掌握图的存储方法，掌握图存储的邻接矩阵法和邻接表法。掌握图的两种遍历方法：深度优先遍历、广度优先遍历。理解基于图的最小(代价)生成树算法、最短路径算法、拓扑排序算法。了解关键路径算法。

（6）查找

本部分的目的是介绍线性表、树和哈希表的查找方法、算法实现以及各种查找方法的时间性能（平均查找长度）分析。重点要求掌握顺序查找、折半查找、二叉排序树和哈希表查找的基本思想和算法实现。了解平衡二叉树、B-树的基本概念及基本操作、B+树的基本概念。能够理解各种不同查找算法的适用情况，以及不同算法的性能分析。

（7）内部排序

内部排序部分的目的是介绍五大类内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析；并且对各种排序方法进行比较。重点要求掌握直接插入排序、快速排序、堆排序和归并排序的基本思想和排序过程。理解基数排序、折半插入排序等排序方法的基本思想和排序过程。掌握各类排序方法的性质、效率对比。

硕士研究生入学考试《计算机网络》考试大纲

一、考试要求

1. 掌握计算机网络的基本概念、基本原理和基本方法。

2. 掌握计算机网络的体系结构和典型网络协议，了解典型网络设备的组成和特点，理解典型网络设备的工作原理。

3. 能够运用计算机网络的基本概念、基本原理和基本方法进行网络系统的分析、设计和应用

二、主要参考书目

《计算机网络(第5版)》，谢希仁，电子工业出版社；

三、其它参考书目

《计算机网络(第5版)》，（美）特南鲍姆，（美）韦瑟罗尔 著，严伟，潘爱民 译，清华大学出版社；

四、考试题型及权重（共75分）

1. 填空题:20分；

2. 选择题:15分；

3. 简答题:20分；

4. 综合应用:20分；

五、考查范围

1. 计算机网络体系结构

1.1 计算机网络概述

1.1.1 计算机网络的概念、组成与功能

1.1.2 计算机网络的分类

1.1.3 计算机网络与互联网的发展历史

1.1.4 计算机网络的标准化工作及相关组织

1.2 计算机网络体系结构与参考模型

1.2.1 计算机网络分层结构

1.2.2 计算机网络协议、接口、服务等概念

1.2.3 ISO/OSI参考模型和TCP/IP模型

2. 物理层

2.1 通信基础

2.1.1 信道、信号、宽带、码元、波特、速率、信源与信宿等基本概念

2.1.2 奈奎斯特定理与香农定理

2.1.3 编码与调制

2.1.4 电路交换、报文交换与分组交换

2.1.5 数据报与虚电路

2.2 传输介质

2.2.1 双绞线、同轴电缆、光纤与无线传输介质

2.2.2 物理层接口的特性

2.3 物理层设备

2.3.1 中继器

2.3.2 集线器

3. 数据链路层

3.1 数据链路层的功能

3.2 组帧

3.3 差错控制

3.3.1 检错编码

3.3.2 纠错编码

3.4 流量控制与可靠传输机制

3.4.1 流量控制、可靠传输与滑轮窗口机制

3.4.2 停止-等待协议

3.4.3 后退N帧协议（GBN）

3.4.4 选择重传协议（SR）

3.5 介质访问控制

3.5.1 信道划分介质访问控制

频分多路复用、时分多路复用、波分多路复用、码分多路复用的概念和基本原理。

3.5.2 随即访问介质访问控制

ALOHA协议；CSMA协议；CSMA/CD协议；CSMA/CA协议。

3.5.3 轮询访问介质访问控制：令牌传递协议

3.6 局域网

3.6.1 局域网的基本概念与体系结构

3.6.2 以太网与IEEE802.3

3.6.3 IEEE802.11

3.6.4 令牌环网的基本原理

3.7 广域网

3.7.1 广域网的基本概念

3.7.2 PPP协议

3.7.3 HDLC协议

3.8 数据链路层设备

3.8.1 网桥的概念和基本原理

3.8.2 局域网交换机及其工作原理。

4. 网络层

4.1 网络层的功能

4.1.1 异构网络互联

4.1.2 路由与转发

4.1.3 拥塞控制

4.2 路由算法

4.2.1 静态路由与动态路由

4.2.2 距离-向量路由算法

4.2.3 链路状态路由算法

4.2.4 层次路由

4.3 IPv4

4.3.1 IPv4分组

4.3.2 IPv4地址与NAT

4.3.3 子网划分与子网掩码、CIDR

4.3.4 ARP协议、DHCP协议与ICMP协议

4.4 IPv6

4.4.1 IPv6的主要特点

4.4.2 IPv6地址

4.5 路由协议

4.5.1 自治系统

4.5.2 域内路由与域间路由

4.5.3 RIP路由协议

4.5.4 OSPF路由协议

4.5.5 BGP路由协议

4.6 IP组播

4.6.1 组播的概念

4.6.2 IP组播地址

4.7 移动IP

4.7.1 移动IP的概念

4.7.2 移动IP的通信过程

4.8 网络层设备

4.8.1 路由器的组成和功能

4.8.2 路由表与路由转发

5. 传输层

5.1 传输层提供的服务

5.1.1 传输层的功能

5.1.2 传输层寻址与端口

5.1.3 无连接服务与面向连接服务

5.2 UDP协议

5.2.1 UDP数据报

5.2.2 UDP校验

5.3 TCP协议

5.3.1 TCP段

5.3.2 TCP连接管理

5.3.3 TCP可靠传输

5.3.4 TCP流量控制与拥塞控制

6. 应用层

6.1 网络应用模型

6.1.1 客户/服务器模型

6.1.2 P2P模型

6.2 DNS系统

6.2.1 层次域名空间

6.2.2 域名服务器

6.2.3 域名解析过程

6.3 FTP

6.3.1 FTP协议的工作原理

6.3.2 控制连接与数据连接

6.4 电子邮件

6.4.1 电子邮件系统的组成结构

6.4.2 电子邮件格式与MIME

6.4.3 SMTP协议与POP3协议

6.5 WWW

6.5.1 WWW的概念与组成结构

6.5.2 HTTP协议