中国传媒大学硕士研究生入学考试

中国传媒大学硕士研究生入学考试中国传媒大学硕士研究生入学考试中国传媒大学硕士研究生入学考试《《《《数据结构与计算机网络数据结构与计算机网络数据结构与计算机网络数据结构与计算机网络》》》》考试大纲考试大纲考试大纲考试大纲一一一一、、、、考试的总体要求考试的总体要求考试的总体要求考试的总体要求《数据结构与计算机网络》是计算机科学与技术及相关学科的重要基础,本科目要求考生在数据结构方面:掌握数据结构的基本概念、基本原理和基本方法;掌握数据的逻辑结构、存储结构及基本操作的实现,能够对算法进行基本的时间复杂度与空间复杂度的分析;能够运用数据结构基本原理和方法进行问题的分析与求解,具备采用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.
117.
广域网:广域网的基本概念,PPP协议8.
数据链路层设备:网桥的概念和基本原理,局域网交换机及其工作原理.