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

一、考试要求

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