2016年中国传媒大学0810J2新媒体考研大纲

　　《数据结构与计算机网络》考试大纲
　　一、考试的总体要求
　　《数据结构与计算机网络》是计算机科学与技术及相关学科的重要基础，本科目要求考生在数据结构方面：掌握数据结构的基本概念、基本原理和基本方法；掌 握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析；能够运用数据结构基本原理和方法进行问题的分析与求 解，具备采用C或C++或JAVA语言设计与实现算法的能力。在计算机网络方面：掌握计算机网络的基本概念、基本原理和基本方法；掌握计算机网络的体系结 构和典型网络协议，了解典型网络的组成和特点，理解典型网络设备的工作原理；能够运用计算机网络的基本概念、基本原理和基本方法进行网络系统的分析、设计 和应用。

　　二、考试的内容
　　（一）线性表
　　1.线性表的定义和基本操作
　　2.线性表的实现：顺序存储，链式存储，线性表的应用

　　（二）栈、队列和数组
　　1.栈和队列的基本概念
　　2.栈和队列的顺序存储结构
　　3.栈和队列的链式存储结构
　　4.栈和队列的应用
　　5.特殊矩阵的压缩存储

　　（三）树与二叉树
　　1.树的概念
　　2.二叉树：二叉树的定义及其主要特征，二叉树的顺序存储结构和链式存储结构，二叉树的遍历，线索二叉树的基本概念和构造
　　3.树、森林：树的存储结构，森林与二叉树的转换，树和森林的遍历
　　4.树与二叉树的应用：二叉排序树，平衡二叉树，哈夫曼（Huffman）树和哈夫曼编码

　　（四）图
　　1.图的基本概念
　　2.图的存储及基本操作：邻接矩阵法，邻接表法
　　3.图的遍历：深度优先搜索，广度优先搜索
　　4.图的基本应用：最小（代价）生成树，最短路径，拓扑排序，关键路径

　　（五）查找
　　1.查找的基本概念
　　2.顺序查找法
　　3.折半查找法
　　4.散列（Hash）表
　　5.查找算法的分析及应用

　　（六）排序
　　1.排序的基本概念
　　2.插入排序
　　3.起泡排序（BubbleSort）
　　4.简单选择排序
　　5.希尔排序（ShellSort）
　　6.快速排序
　　7.堆排序
　　8.二路归并排序（MergeSort）
　　9.各种内部排序算法的比较

　　（七）计算机网络体系结构
　　1.计算机网络概述：计算机网络的概念、组成与功能，计算机网络的分类，计算机网络与互联网的发展历史，计算机网络的标准化工作及相关组织
　　2.计算机网络体系结构与参考模型：计算机网络分层结构，计算机网络协议、接口、服务等概念，ISO/OSI参考模型和TCP/IP模型

　　（八）物理层
　　1.通信基础：信道、信号、宽带、码元、波特、速率、信源与信宿等基本概念，奈奎斯特定理与香农定理，编码与调制，电路交换、报文交换与分组交换，数据报与虚电路
　　2.传输介质：双绞线、同轴电缆、光纤与无线传输介质，物理层接口的特性，物理层设备，中继器，集线器

　　（九）数据链路层
　　1.数据链路层的功能
　　2.组帧
　　3.差错控制：检错编码，纠错编码
　　4.流量控制与可靠传输机制：流量控制、可靠传输与滑轮窗口机制，停止-等待协议，后退N帧协议（GBN），选择重传协议（SR）
　　5.信道划分介质访问控制：频分多路复用、时分多路复用、波分多路复用、码分多路复用的概念和基本原理；随机访问介质访问控制：CSMA协议、CSMA/CD协议、CSMA/CA协议。
　　6.局域网：局域网的基本概念与体系结构，以太网与IEEE802.3，IEEE802.11
　　7.广域网：广域网的基本概念，PPP协议
　　8.数据链路层设备：网桥的概念和基本原理，局域网交换机及其工作原理。

　　（十）网络层
　　1.网络层的功能：异构网络互联，路由与转发，拥塞控制
　　2.路由算法：静态路由与动态路由，距离-向量路由算法，链路状态路由算法，层次路由
　　3.IPv4：IPv4分组，IPv4地址与NAT，子网划分与子网掩码、CIDR，ARP协议、DHCP协议与ICMP协议
　　4.IPv6：IPv6的主要特点，IPv6地址
　　5.路由协议：自治系统，域内路由与域间路由，RIP路由协议，OSPF路由协议，BGP路由协议
　　6.IP组播：组播的概念，IP组播地址
　　7.网络层设备：路由器的组成和功能，路由表与路由转发

　　（十一）传输层
　　1.传输层提供的服务：传输层的功能，传输层寻址与端口，无连接服务与面向连接服务
　　2.UDP协议：UDP数据报，UDP校验
　　3.TCP协议：TCP段，TCP连接管理，TCP可靠传输，TCP流量控制与拥塞控制

　　（十二）应用层
　　1.网络应用模型：客户/服务器模型，P2P模型
　　2.DNS系统：层次域名空间，域名服务器，域名解析过程
　　3.FTP：FTP协议的工作原理，控制连接与数据连接
　　4.电子邮件：电子邮件系统的组成结构，电子邮件格式与MIME，SMTP协议与POP3协议
　　5.WWW：WWW的概念与组成结构，HTTP协议

　　三、考试的基本题型
　　本试卷满分为150分。
　　主要题型有：选择题、综合应用题等。

　　四、考试的形式及时间
　　笔试，不需要任何辅助工具。考试时间为三小时。

　　（实习编辑：杨颖雄）