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

年硕士研究生入学考试数据结构考试大纲一考试要求数据结构是一门专业基础课要求考生能够理解数据结构的基本概念掌握数据结构中逻辑结构存储结构的基本概念和差异以及各种基本操作的实现在掌握基本的数据处理原理和方法的基础上能够对算法进行设计与分析能够选择合适的数据结构和方法进行问题求解能够针对具体问题设计正确的数据结构加以应用具备采用类或或语言设计与实现算法的能力本课程包括算法的基本概念分析和设计方法软件开发中常用的各类结构包括线性结构树结构图结构查找排序等各类常用算法主要考察学生对数据结构基础知识的理解是否具备对现有常用结构和算法的应用能力是否具备针对具体应用设计合适数据结构的能力二主要参考书目数据结构语言版严蔚敏吴伟民清华大学出版社三其它参考书目数据结构与算法分析语言描述第二版清华大学出版社数据结构用面向对象方法与语言描述第二版殷人昆清华大学出版社四考试题型及权重共分选择分简答题分算法应用题分算法设计题分五考查范围基本概念和算法分析本部分的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义重点要求理解数据结构的基本概念算法的基本要素和基本要求掌握简单的算法时间空间复杂度分析方法理解抽象数据结构的定义理解最好最坏和平均复杂度的分析和计算方法线性表本部分的目的是介绍线性表的逻辑结构和各种存储表示方法以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算重点要求熟练掌握线性表的定义和基本操作能够熟练掌握线性表的两种实现方法顺序存储和随机存储熟知线性表的应用范围理解线性表的各种存储结构操作实现的异同点优缺点栈和队列本部分的目的是介绍栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本运算重点要求熟练掌握栈和队列的基本概念以及栈和队列的两种实现方法顺序存储结构实现和链式存储结构实现及其操作的实现能够掌握栈和队列的基本应用树和二叉树本部分的目的是介绍二叉树的定义性质存储结构遍历线索化树的定义存储结构遍历树和森林的转换及赫夫曼树及其赫夫曼编码等内容重点要求熟练掌握树的基本概念基本性质熟练掌握二叉树的定义及其主要特征二叉树的顺序存储结构和链式存储结构二叉树的遍历操作掌握线索二叉树的基本概念和构造掌握基于二叉树遍历操作所衍生出的各类操作例如二叉树的构造二叉树叶子节点的统计求二叉树深度操作等理解树的存储结构掌握森林和二叉树的相互转换树和森林的遍历操作理解二叉排序树的基本原理和算法掌握平衡二叉树的各种操作掌握哈夫曼树和哈夫曼编码并能够在实际的问题中加以应用图本部分的目的是介绍图的基本概念两种常用的存储结构两种遍历方法以及图的应用算法重点要求掌握图的基本概念基本性质掌握图的存储方法掌握图存储的邻接矩阵法和邻接表法掌握图的两种遍历方法深度优先遍历广度优先遍历理解基于图的最小代价生成树算法最短路径算法拓扑排序算法了解关键路径算法查找本部分的目的是介绍线性表树和哈希表的查找方法算法实现以及各种查找方法的时间性能平均查找长度分析重点要求掌握顺序查找折半查找二叉排序树和哈希表查找的基本思想和算法实现了解平衡二叉树树的基本概念及基本操作树的基本概念能够理解各种不同查找算法的适用情况以及不同算法的性能分析内部排序内部排序部分的目的是介绍五大类内部排序方法的基本思想排序过程算法实现时间和空间性能的分析并且对各种排序方法进行比较重点要求掌握直接插入排序快速排序堆排序和归并排序的基本思想和排序过程理解基数排序折半插入排序等排序方法的基本思想和排序过程掌握各类排序方法的性质效率对比年硕士研究生入学考试计算机网络考试大纲一考试要求掌握计算机网络的基本概念基本原理和基本方法掌握计算机网络的体系结构和典型网络协议了解典型网络设备的组成和特点理解典型网络设备的工作原理能够运用计算机网络的基本概念基本原理和基本方法进行网络系统的分析设计和应用二主要参考书目计算机网络第版谢希仁电子工业出版社三其它参考书目计算机网络第版美特南鲍姆美韦瑟罗尔著严伟潘爱民译清华大学出版社四考试题型及权重共分填空题分选择题分简答题分综合应用分五考查范围计算机网络体系结构计算机网络概述计算机网络的概念组成与功能计算机网络的分类计算机网络与互联网的发展历史计算机网络的标准化工作及相关组织计算机网络体系结构与参考模型计算机网络分层结构计算机网络协议接口服务等概念参考模型和模型物理层通信基础信道信号宽带码元波特速率信源与信宿等基本概念奈奎斯特定理与香农定理编码与调制电路交换报文交换与分组交换数据报与虚电路传输介质双绞线同轴电缆光纤与无线传输介质物理层接口的特性物理层设备中继器集线器数据链路层数据链路层的功能组帧差错控制检错编码纠错编码流量控制与可靠传输机制流量控制可靠传输与滑轮窗口机制停止等待协议后退帧协议选择重传协议介质访问控制信道划分介质访问控制频分多路复用时分多路复用波分多路复用码分多路复用的概念和基本原理随即访问介质访问控制协议协议协议协议轮询访问介质访问控制令牌传递协议局域网局域网的基本概念与体系结构以太网与令牌环网的基本原理广域网广域网的基本概念协议协议数据链路层设备网桥的概念和基本原理局域网交换机及其工作原理网络层网络层的功能异构网络互联路由与转发拥塞控制路由算法静态路由与动态路由距离向量路由算法链路状态路由算法层次路由分组地址与子网划分与子网掩码协议协议与协议的主要特点地址路由协议自治系统域内路由与域间路由路由协议路由协议路由协议组播组播的概念组播地址移动移动的概念移动的通信过程网络层设备路由器的组成和功能路由表与路由转发传输层传输层提供的服务传输层的功能传输层寻址与端口无连接服务与面向连接服务协议数据报校验协议段连接管理可靠传输流量控制与拥塞控制应用层网络应用模型客户服务器模型模型系统层次域名空间域名服务器域名解析过程协议的工作原理控制连接与数据连接电子邮件电子邮件系统的组成结构电子邮件格式与协议与协议的概念与组成结构协议