研究生入学考试《计算机专业基础综合》考试大纲
本科目考试内容涵盖数据结构、计算机网络相关知识点。其中，数据结构知识点分值75分，计算机网络知识点分值75分。
一、数据结构考查目标及知识点解析
（一）考查目标
1、掌握数据结构的基本概念、基本原理和基本方法。
2、掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。
3、能够运用数据结构基本原理和方法进行问题的分析与求解，具备采用C或类C语言实现算法的能力。
（二）知识点解析
1、绪论
掌握数据结构的基本概念，常见的4种基本数据结构（集合、线性、树形、图状）的特点，顺序存储结构与链式存储结构各自的优缺点；掌握时间和空间复杂度的概念及度量方法。
2、线性表
掌握线性表的定义和基本操作与实现；在线性表实现方面，掌握线性表的两种存储结构：顺序存储结构和链式存储结构；掌握在顺序表上实现插入、删除、定位等运算的算法；在链式存储结构方面，理解头指针、头结点、首元结点和元素结点的差别，掌握单链表、循环链表、双向链表等几种常用链表的特点及其插入、删除、遍历等操作，并能够设计出实现线性表其他运算的算法；从时间复杂度和空间复杂度的角度综合比较线性表在顺序和链式存储结构下的特点及其各自使用的场合。
3、栈和队列
掌握栈和队列的定义及其相关概念，包括：顺序栈、链栈、循环队列、链队列等，栈与队列存取数据的特点；掌握顺序栈和链栈上的进栈和出栈的算法，理解栈空和栈满的特点，能够利用栈这种数据结构解决实际问题；掌握在链队列上实现入队列和出队列的算法；理解构造循环队列的原理以及队列空及队列满的条件，掌握循环队列中入队列与出队列算法。
4、数组和广义表
掌握数组采用顺序存储表示时两种存储方式：按行优先和按列优先，能够对多维数组中的某个数组元素的地址进行求解；掌握特殊矩阵（对称矩阵、三角矩阵、对角矩阵）的压缩存储方法；掌握稀疏矩阵的三种不同存储方式：三元组、行逻辑链接的顺序表、十字链表存储等；掌握广义表的概念，特别是表头与表尾的定义，掌握广义表链式存储结构的两种表示形式：头尾链表存储表示和扩展线性链表存储表示。
5、树和二叉树
掌握树的定义和基本术语；掌握二叉树的定义以及特殊二叉树的定义，如完全二叉树及满二叉树，能够灵活应用二叉树的5个性质，掌握二叉树的两种存储结构：顺序存储结构和链式存储结构（二叉链表）；掌握二叉树三种遍历方式（先序遍历、中序遍历、后序遍历）的递归算法，能够运用遍历的递归算法编写程序解决实际问题，能够利用二叉树的先序中序序列或后序中序序列构造二叉树；掌握树的三种存储结构：双亲表示法，孩子表示法以及孩子兄弟表示法，掌握树、二叉树、森林之间的相互转换的方法，掌握森林的两种遍历方法：先序遍历和中序遍历；理解赫夫曼树的特点，掌握赫夫曼树的构造过程及赫夫曼编码的原理。
6、图
掌握图的定义和相关的术语；掌握图的三种存储结构：数组表示法，邻接表和十字链表；掌握图的两种遍历方式：深度优先搜索和广度优先搜索；掌握图的相关应用，如最小生成树，拓扑排序，关键路径，最短路径等，理解各种算法的原理及其解决的实际问题。
7、查找
掌握查找表的定义以及两种查找表（静态查找表和动态查找表）的特点及相关操作；在静态查找表方面，掌握顺序表、有序表的查找（折半查找）、索引顺序表的查找的原理，能够运用平均查找长度概念对查找性能进行分析；在动态查找表方面，掌握二叉排序树的定义、构造过程、插入和删除操作以及性能分析，掌握平衡二叉树的定义及特点，掌握平衡调整的4种方式（LL型、LR型、RR型，RL型），掌握B-树的定义、插入和删除操作及性能分析；掌握哈希表的定义，构造方法、处理冲突方法、查找及性能分析。
8、排序
掌握排序的定义以及稳定和不稳定排序方法的定义；掌握直接插入排序、希尔排序、起泡排序、快速排序、简单的选择排序、堆排序、归并排序等排序算法的原理并能灵活运用。
二、计算机网络考查目标及知识点解析
（一）考查目标
1、掌握计算机网络的基本概念、基本原理和基本方法。
2、掌握计算机网络的体系结构和典型网络协议，了解典型网络设备的组成和特点，理解典型网络设备的工作原理。
3、能够运用计算机网络的基本概念、基本原理和基本方法进行网络系统的分析、设计和应用。
（二）知识点解析
1、计算机网络体系结构
网络体系就是为了完成计算机之间的通信合作，把每台计算机相连的功能划分成有明确定义的层次，并固定了同层次的进程通信的协议及相邻之间的接口及服务。这个知识点要求我们对网络的概念、组成、分类、发展过程等内容要有所了解，同时还要理解网络分层结构、网络层协议、接口、服务等概念，掌握ISO/OSI参考模型和TCP/IP模型的区别与联系。
2、物理层
物理层作为OSI模型的最底层、也是各层通信的基础，在计算机考研网络模块中，需要重点复习。要掌握的概念有：信道、信号、宽带、码元、波特、速率、信源与信宿、编码与调制、电路交换、报文交换与分组交换、数据报与虚电路等基本概念。同时，网络技术中有名的两个定理（奈奎斯特定理与香农定理）及其表达公式，需要考生能够熟练掌握与应用。这部分还涉及到综合布线相关知识，如：传输介质（双绞线、同轴电缆、光纤与无线传输介质）、物理层设备（中继器、集线器）及物理层接口的特性。
3、数据链路层
数据链路层功能强大，对该层知识的考查涉及的面比较广。数据链路层的主要功能有：数据帧的拆分与拼接、差错控制（检错编码、纠错编码）、流量控制与可靠传输机制（滑动窗口机制、停止-等待协议、后退N帧协议GBN、选择重传协议SR）、介质访问控制（频分多路复用、时分多路复用、波分多路复用、码分多路复用）的概念和基本原理。另外，还需对数据链路层设备网桥（网桥的概念、透明网桥与生成树算饭、源选径网桥与源选径算法）、交换机及其工作原理等知识进行重点复习。
4、网络层
网络层是OSI参考模型中的核心层，从网络层的功能上看，它的主要功能是路由与转发。路由算法主要包括静态路由与动态路由、距离-向量路由算法、链路状态路由算法、层次路由等。在路由协议方面，要求掌握自治系统（AS）、域内路由与域间路由的概念及常用的三种路由协议（RIP、OSPF、BGP）及其实现。
网络层的主要协议是IP协议，对于这部分内容，要求我们掌握IPv4分组、IP组播、IPv4地址与NAT、子网划分与子网掩码、CIDR。另外，还有与IP协议相关的其它层协议（例如，ARP协议、DHCP协议与ICMP协议等）也将放在一起进行考查。
最后，还要求熟悉网络层设备（路由器）的组成和功能、路由表与路由转发等技术。
5、传输层
传输层要求我们了解无连接服务与面向连接服务这两种服务的区别及两种代表性的传输层协议：UDP协议和TCP协议。UDP协议是提供无连接服务的，要求我们掌握UDP数据报的发送和UDP校验方式。TCP协议是提供面向连接服务的，要求我们掌握TCP连接管理、三次握手协议、TCP可靠传输，以及TCP流量控制与拥塞控制。
6、应用层
应用层要求了解两种网络应用模型（客户/服务器模型、P2P模型）及常用的几种应用服务及其实现，例如：
（1）DNS（域名解析服务）：包括层次域名空间、域名服务器、域名解析过程等。
（2）FTP（文件传输协议）：包括FTP协议的工作原理、控制连接与数据连接等。
（3）E-Mail（电子邮件）：包括电子邮件系统的组成结构、电子邮件格式与MIME、SMTP协议与POP3协议等。
（4）WWW（万维网）：包括WWW的概念与组成结构、HTTP协议等。
对于以上4种常见的服务，要掌握其相关概念、基本工作原理、服务过程、所涉及的网络协议。
三、教材选择
1、《数据结构(C语言版)》（第2版），严蔚敏等编著，人民邮电出版社。
该书比较全面系统地介绍了线性表、树、图等基本类型的数据结构及其应用，同时介绍了查找和排序的各种实现方法及其综合分析比较，并有配套的习题集供考生练习。
2、《计算机网络》（第8版），谢希仁编著，电子工业出版社。
该书比较全面系统地介绍了计算机网络的发展和原理体系结构、物理层、数据链路层、局域网、广域网、网络互连、传输层、应用层、计算机网络的安全和因特网的演进等内容，并且各章均附有练习题。
考试分值为150分，考试时间为180分钟。
原标题：2023年硕士研究生招生初试及复试科目考试大纲
文章来源：http://cst.hpu.edu.cn/info/1033/5678.htm
