2021中国石油大学（北京）数据结构与计算机网络研究生考试大纲 正文

中国石油大学（北京）硕士研究生入学考试
《数据结构与计算机网络》考试大纲
第一部分 考试说明
一、考试性质
数据结构和计算机网络是计算机专业的专业基础课。此次综合考试是为招收计算机学科的硕士研究生而设置的具有选拔性质的联考科目，其目的是科学、公平、有效地测试考生掌握计算机科学与技术学科大学本科阶段专业知识、基本理论、基本方法的水平和分析问题、解决问题的能力，评价的标准是高等院校计算机科学与技术学科优秀本科毕业生所能达到的及格或及格以上水平，以利于计算机各专业的导师择优选拔硕士研究生，确保硕士研究生的招生质量。
二、考试要求
此次考试涵盖数据结构和计算机网络两门专业基础课程。要求考生比较系统地掌握上述基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。
三、考试形式和试卷结构
1.试卷满分及考试时间
本试卷满分为150分，考试时间为180分钟。
2.答题方式
答题方式为闭卷、笔试。
3.试卷内容结构
数据结构   75分
计算机网络 75分
四、主要参考书目
《数据结构》(C语言版)，严蔚敏、吴伟民编著,清华大学出版社,1997.4
《数据结构（AR）》，连远锋、吴双元、朱丹丹编著，清华大学出版社，2019.10
《计算机网络（第7版）》，谢希仁，电子工业出版社，2017.1
五、考查内容
I.数据结构
【考查目标】
1.掌握数据结构的基本概念、基本原理和基本方法。
2.掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。
3.能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。
【考查内容】
    1.数据结构和算法
    数据结构、存储结构的概念；数据类型与抽象数据类型；算法的概念,用C/C++描述算法和程序设计,算法分析初步。
    2.线性表
    线性表的定义和基本操作；线性表的抽象数据类型；线性表的顺序存储结构，应用举例；线性表的链式存储结构(单链表,双链表,循环链表),应用举例。
3.栈
    栈的定义和基本操作；栈的抽象数据类型；顺序栈，链式栈；栈和递归算法, 算术表达式求值,其它应用。
    4．队列
    队列的定义和基本操作；队列的抽象数据类型；顺序队列，链式队列；双端队列的定义和基本操作；应用举例。
    5.数组和字符串
    数组的定义和基本操作；数组的顺序存储结构，应用举例；特殊矩阵和稀疏矩阵的压缩存储。    字符串的定义和基本操作,字符串的存储结构,字符串操作的实现举例,字符串和模式匹配。
    6.树和二叉树
(1)树的基本概念和基本操作,树的抽象数据类型；
(2)二叉树的概念和性质,特殊二叉树；二叉树的存储结构；
(3)二叉树的生成与建立；
    (4)遍历二叉树：前序遍历,中序遍历,后序遍历,层次遍历；
    (5)二叉树其它操作实现举例；
    (6)线索二叉树的概念和存储结构,二叉树的线索化,线索二叉树的遍历；
    (7)树的存储结构,树与二叉树之间的转换,森林与二叉树之间的转换,树和森林的遍历；
    (8)树的路径长度和带权路径长度,哈夫曼树(Huffman)的概念,哈夫曼算法, 哈夫曼编码树；
    (9)二叉排序树的的概念和基本操作,二叉排序树的建立,二叉排序树其它操作实现举例。
    7.图
    (1)图的基本概念和基本操作，图的抽象数据类型；
    (2)图的存储结构：数组表示法(邻接矩阵)；邻接表，逆邻接表，十字链表；邻接多重表；
    (3)图的遍历：深度优先搜索法, 宽度优先搜索法, 求图的连通分量；
(4)生成树、最小生成树的概念；克鲁斯卡尔(Kruskal)算法,普里姆(Prim)算法；
(5)从一个顶点到其余各顶点的最短路径,每对顶点之间的最短路径；
(6)拓扑排序和关键路径。
    8.查找
    (1)查找的概念,关键字比较次数,平均查找长度；
    (2)顺序表的查找:顺序查找,折半查找,分块查找；
    (3)树表的查找:二叉排序树,平衡二叉树。
    (4)哈希(Hash)表的查找:哈希表的概念,哈希函数构造方法,哈希表的建立和查找,冲突处理方法。
    9.排序
(1)排序的概念；排序的稳定性；比较关键字次数,移动记录次数；
(2)内排序方法与算法：
1) 交换排序:冒泡排序,快速排序；
2) 插入排序:直接插入排序,2路插入排序,折半插入排序,希尔排序；
3) 接选择排序,锦标赛排序,堆排序；
4) 归并排序；
5) 基数排序；
(3)各种排序算法的评价和应用。
II.计算机网络
【考查目标】
1.掌握计算机网络的基本概念、基本原理和基本方法。
2.掌握计算机网络的体系结构和典型网络协议，了解典型网络的组成和特点，理解典型网络设备的工作原理。
3.能够运用计算机网络的基本概念、基本原理和基本方法进行网络系统的分析、设计和应用。
【考查内容】
1.计算机网络体系结构
(1)计算机网络概述：计算机网络的概念、计算机网络组成与功能、计算机网络的分类、计算机网络的标准化工作及相关组织、计算机网络的性能。
(2)计算机网络体系结构与参考模型：计算机网络分层结构、计算机网络协议、计算机接口和服务等概念、ISO/OSI参考模型、TCP/IP模型和五层协议体系结构。
2.物理层
(1)通信基础:通信的基本概念（信道、信号、宽带、码元、波特、速率、信源与信宿等）、
奈奎斯特定理与香农定理、编码与调制、电路交换和分组交换、数据报与虚电路;
(2)传输介质:有线传输介质（双绞线、同轴电缆、光纤）与无线传输介质、物理层接口的特性、物理层设备（中继器和集线器）。
3.数据链路层
(1)数据链路层的功能；
(2)组帧；
(3)差错控制；
(4)介质访问控制:信道划分（频分多路复用、时分多路复用、波分多路复用、码分多路复用的概念和基本原理）、随机访问（CSMA/CD协议、CSMA/CA协议）、轮询访问（令牌传递协议）；
(5)局域网:局域网的基本概念与体系结构、以太网与IEEE802.3、IEEE802.11、虚拟局域网；
     (6)广域网:广域网的基本概念、PPP协议；
 (7)数据链路层设备:网桥的概念及其基本原理、局域网交换机及其工作原理。
4.网络层
(1)网络层的功能:异构网络互连、路由与转发、拥塞控制；
(2)路由算法:静态路由与动态路由、距离-向量路由算法、链路状态路由算法、层次路由；
(3)IPv4:IPv4分组、IPv4地址与NAT、子网划分、路由聚集、子网掩码与CIDR、ARP协议和ICMP协议；
(4)IPv6:IPv6的主要特点、IPv6地址；
(5)路由协议:自治系统、域内路由与域间路由、RIP路由协议、OSPF路由协议、BGP路由协议；
(6)IP组播:组播的概念、IP组播地址；
 (7)网络层设备:路由器的组成和功能、路由表与路由转发。
5.传输层
(1)传输层提供的服务:传输层的功能、传输层寻址与端口、无连接服务与面向连接服务；
(2)UDP协议:UDP数据报、UDP校验；
(3)TCP协议:TCP报文段、TCP连接管理、TCP可靠传输（停止等待协议、后退N帧协议GBN、选择重传协议SR）；
(4)TCP流量控制与拥塞控制。
6.应用层
(1)网络应用模型:客户/服务器模型、P2P模型；
(2)DNS系统:层次域名空间、域名服务器、域名解析过程；
(3)FTP:FTP协议的工作原理、控制连接与数据连接；
(4)电子邮件:电子邮件系统的组成结构、电子邮件格式与MIME、SMTP协议与POP3协议；
(5)WWW:WWW的概念与组成结构、HTTP协议。
7.DHCP协议
8.简单网络管理协议SNMP（网络管理的基本概念、SNMP协议数据单元和报文）。
 

中国石油大学(北京)

本文来源：http://www.okaoyan.com/zhongguoshiyouda/cankaoshumu_390348.html