科目代码：816

科目名称：计算机综合

一、考试范围(数据结构、计算机网络)

1. 数据结构

1.1 绪论

(1)数据结构的基本概念，数据的逻辑结构、存储结构

(2)算法的定义、算法的基本特性以及算法分析的基本概念

1.2 线性表

(1)线性关系、线性表的定义，线性表的基本操作

(2)线性表的顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)的构造原理，在以上两种存储结构上对线性表实施的最主要的操作(包括三种链表的建立、插入和删除、检索等)的算法设计

1.3 堆栈与队列

(1)堆栈与队列的基本概念、基本操作

(2)堆栈与队列的顺序存储结构与链式存储结构的构造原理

(3)在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作对应的算法设计

1.4 串

(1)串的基本概念、串的基本操作和存储结构

(2)串的模式匹配算法和改进的KMP算法

1.5 数组和广义表

(1)数组的概念，以及表示和实现

(2)矩阵(对称矩阵和稀疏矩阵)的压缩存储

(3)广义表的基本概念

1.6 树与二叉树

(1)树的定义和性质

(2)二叉树的概念、性质和实现

(3)遍历二叉树和线索二叉树

(4)树和森林

(5)赫夫曼树及其应用

(6)回溯法与树的遍历

(7)树的计数

1.7 图

(1)图的定义，基本概念，图的分类，常用名词术语

(2)图的邻接矩阵存储方法、邻接表存储方法的构造原理

(3)图的遍历操作

(4)图的连通性、最小生成树

(5)最短路径的计算

(6)AOV网与拓扑排序

1.8 查找

(1)静态查找表：顺序表、有序表、静态树表以及索引表的查找

(2)动态查找表：二叉排序树和平衡二叉树，以及B树和B+树的基本概念和操作

(3)哈希表：基本概念和构造方法，冲突处理方法和查询及性能分析

1.9 内排序

(1)排序的基本概念，排序方法的分类

(2)插入排序法(包含折半插入排序法)、选择排序法、快速排序法、堆排序法、归并排序、基数排序;各种排序方法排序的原理、规律和特点;各种排序算法的时空复杂度简单分析

2、计算机网络

2.1 绪论

(1)计算机网络的概念、分类、标准、组成与功能

(2)计算机网络分层结构，协议、接口、服务等概念，ISO/OSI模型和TCP/IP模型

2.2 物理层

(1)通信信道、信号、宽带、码元、波特、速率、信源与信宿等基本概念，奈奎斯特定理与香农定理，编码与调制，电路交换、报文交换与分组交换，数据报与虚电路

(2)双绞线、同轴电缆、光纤与无线传输介质，物理层接口的特性，中继器，集线器

2.3 数据链路层

(1)数据链路层的功能，组帧，差错控制(检错与纠错编码)

(2)流量控制、可靠传输与滑轮窗口机制，停止-等待协议，后退N帧协议(GBN)，选择重传协议(SR)

(3)频分多路复用、时分多路复用、波分多路复用、码分多路复用的概念和基本原理 ALOHA协议、CSMA协议、CSMA/CD协议、CSMA/CA协议

(4)局域网的概念及其体系结构，以太网协议，IEEE802.11标准协议

(5)广域网的概念，PPP协议，HDLC协议

(6)网桥的概念和原理，交换机及其工作原理

2.4 网络层

(1)网络层的功能，异构网络互联，路由与转发

(2)路由算法，静态路由与动态路由，距离-向量路由算法，链路状态路由算法，层次路由

(3)IPv4分组，IPv4地址与NAT，子网划分与子网掩码、CIDR，ARP协议、ICMP协议

(4)IPv6的主要特点，IPv6地址

(5)路由协议，自治系统，域内路由与域间路由，RIP路由协议、OSPF路由协议、BGP路由协议

(6)路由器的组成和功能，路由表与路由转发

2.5 传输层

(1)传输层的功能，传输层寻址与端口，无连接服务与面向连接服务

(2)UDP协议，UDP数据报，UDP校验

(3)TCP协议，TCP段，TCP连接管理，TCP可靠传输，TCP流量控制与拥塞控制

2.6 应用层

(1)客户/服务器模型，P2P模型

(2)DNS概念，层次域名空间，域名服务器，域名解析过程

(3)FTP协议的工作原理，控制连接与数据连接

(4)电子邮件系统的组成结构，电子邮件格式与MIME，SMTP协议与POP3协议

(5)WWW的概念与组成结构，HTTP协议

(6)DHCP协议

二、考试形式

闭卷，题型包括选择题、填空题、简答题、综合设计题

三、参考书目

1、《数据结构---从概念到C实现》，王红梅，皮德常 编著，北京: 清华大学出版社，2021年。

2、《计算机网络》，谢希仁编著，北京：电子工业出版社，2017年(第7版)。