一、 课程性质和任务

本科目由计算机网络和数据结构两部分组成。计算机网络部分要求学生掌握计算机网络的基本概念、基本原理和基本方法，理解典型网络协议的工作原理， 具备良好的计算机网络技术理论基础，以及基本的网络系统分析和设计能力。数据结构部分要求学生掌握数据组织、存储和运算的基本原理和方法，各类数据结构和相关算法的分析和设计的能力，能够编写出正确、清晰和较高质量的算法和程序。

二、试卷内容结构

计算机网络部分占比 50%，数据结构部分占比 50%。

三、课程内容和要求

第一部分 计算机网络

(一)概述

基本要求：了解因特网的组成，熟练掌握网络性能指标，掌握网络体系结构。教学内容：

1. 因特网的组成：因特网的边缘部分、因特网的核心部分。

2. 计算机网络的类别。

3. 计算机网络的性能(重点)：速率、带宽、吞吐量、时延、时延带宽积等计算机网络性能指标。

4. 计算机网络的体系结构(重点)：协议与划分层次、五层协议的体系结构、协议与服务、TCP/IP 体系结构。

(二)物理层

基本要求：掌握物理层的基本概念，了解数据通信的基础知识、了解网络传输媒体，掌握信道复用技术及数字传输系统。

教学内容：

1. 物理层的基本概念。

2. 数据通信的基础知识：数据通信系统的模型、信道的极限容量、信道的极限信息传输速率。

3. 物理层下面的传输媒体：导向传输媒体、非导向传输媒体。

4. 信道复用技术(重点)：频分复用、时分复用和统计时分复用、波分复用、码分复用。

5. 数字传输系统：PCM 编码、E1 的数据率。

(三)数据链路层

基本要求：掌握数据链路和帧的概念，理解数据链路层的三个基本问题，掌握 CSMA/CD 协议，掌握如何在不同层次扩展局域网，理解透明网桥的工作原理， 了解生成树协议和虚拟局域网的作用。

教学内容：

1. 数据链路和帧的概念、封装成帧、透明传输、差错检测。

2. 局域网的数据链路层、CSMA/CD 协议(重点)。

3. 共享式以太网和交换式以太网，以太网的争用期、最小帧长和理想的信道利用率。

4. 扩展的以太网(重点)：冲突域和广播域、在物理层扩展以太网、在数据链路层扩展以太网。

(四)网络层

基本要求：掌握网际协议 IP，IP 分组格式及分段操作，使用 CIDR 划分子网、进行地址聚合和路由汇聚，ARP 和 ICMP 在 IP 分组转发中的作用。理解层次路由的概念，掌握静态路由设计方法，理解 RIP 协议工作过程和 Bellman-ford 算法，了解 OSPF 协议的基本特点，了解 BGP 的基本内容。

教学内容：

1. 网际协议 IP(重点)：分类的 IP 地址、IP 地址与硬件地址的区别、地址解析协议 ARP、IP 数据报的格式、IP 层转发分组的流程。

2. 划分子网和地址聚合(重点、难点)：使用 CIDR 的子网 IP 地址设计、路由器中的地址聚合和路由汇聚。

3. 地址解析协议 ARP：直接交付 ARP 和间接交付 ARP 过程，ARP 的分组格式及地址的变化。

4. 网际控制报文协议 ICMP。

5. 因特网的路由(重点、难点)：给定拓扑的静态路由设计、自治系统的概念，RIP 协议的工作原理、OSPF 协议的设计思想及其与 RIP 的不同、外部网关协议 BGP 的作用、路由器的构成及其对 IP 分组的转发流程。

(五)运输层

基本要求：了解运输层的地位和作用，理解端口和运输层复用的概念，了解

UDP 协议的基本特点，掌握 TCP 的报文格式，理解 TCP 可靠传输的实现，掌握

TCP 的流量控制和拥塞控制方法，掌握 TCP 的连接建立和释放过程。教学内容：

1. 运输层协议概述：进程通信、端口。

2. 用户数据报协议 UDP：UDP 特点、UDP 的 PDU 格式，面向报文流的概念。

3. 传输控制协议 TCP：TCP 的 PDU 格式、TCP 面向字节流的概念。

4. 可靠传输的工作原理(重点)：TCP 的滑动窗口、序号和确认号的交互变化、连接的建立和释放。

5. TCP 的拥塞控制(重点)：Reno 版本拥塞控制算法。

(六)应用层

基本要求：掌握因特网的域名结构,理解域名系统的工作过程，理解 FTP、

WWW 的工作原理，了解 SMTP、POP 协议以及通用因特网邮件扩充 MIME，掌握 DHCP 的工作过程。

教学内容：

1. 域名系统 DNS(重点)：域名系统概述、因特网的域名结构、域名服务器。

2. 文件传送协议：FTP 概述、FTP 的基本工作原理、简单文件传送协议 TFTP。

3. 万维网 WWW：URL、超文本传送协议 HTTP、万维网的文档。

4. 电子邮件：简单邮件传送协议 SMTP、电子邮件的信息格式、邮件读取协议 POP3、基于万维网的电子邮件、通用因特网邮件扩充 MIME。

5. 动态主机配置协议 DHCP(重点)。

(七)网络安全

基本要求：了解计算机网络面临的安全性威胁，掌握一般的数据加密模型。了解称密钥密码体制的概念及算法体系。掌握公钥密码体制的概念及算法体系、数字签名和报文鉴别的概念。

教学内容：

1. 网络安全问题概述：面临的安全性威胁、计算机网络安全的内容、一般的数据加密模型。

2. 两类密码体制(重点)：对称密钥密码体制、公钥密码体制。

3. 数字签名。

4. 鉴别：报文鉴别、实体鉴别。第二部分 数据结构

(一)数据结构和算法

1. 了解数据结构、逻辑结构、存储结构和抽象数据类型的基本概念。

2. 了解数据结构的发展和地位。

3. 了解各种算法描述方法和算法设计的基本要求。

4. 掌握对算法的评价标准和算法效率的度量方法。

(二)线性表

1. 理解线性表的概念、定义、逻辑结构和存储结构。

2. 熟练掌握线性表的顺序结构及其各种基本运算。

3. 熟练掌握单链表、循环链表、双向链表的存储结构及其各种基本运算。

4. 理解链表的应用——稀疏多项式存储和运算。

(三)栈和队列

1. 掌握栈的定义、表示、实现和应用。

2. 掌握递归的概念和递归的实现过程。

3. 掌握队列的定义以及顺序(循环队列)和链式存储结构的实现。

(四)串

1. 了解串的基本概念及顺序和链式存储结构。

2. 掌握串的各种基本运算。

3. 了解串的模式匹配算法。

(五)数组和广义表

1. 掌握数组的顺序存储结构。

2. 理解稀疏数组的概念和压缩存储的方法。

3. 理解稀疏矩阵的三元组存储结构和基本运算。

4. 了解稀疏矩阵的十字链表存储结构。

5. 理解广义表的基本概念，掌握广义表的存储结构。

(六)树

1. 理解树的基本概念及其存储结构。

2. 熟练掌握二叉树的定义、性质以及各种存储结构和遍历算法。

3. 掌握线索二叉树的概念、存储结构及线索化算法。

4. 掌握树和森林与二叉树间的转换，掌握树和森林的遍历算法。

5. 掌握哈夫曼树的概念、存储结构和应用。

(七)图

1. 理解图的基本概念，掌握图的邻接矩阵和邻接表的存储结构。

2. 了解十字链表，邻接多重表等存储结构。

3. 熟练掌握图的深度优先和广度优先遍历算法。

4. 理解图的连通性、最小生成树的概念。

5. 掌握求最小生成树算法。

6. 理解有向无环图的概念，掌握拓扑排序和关键路径算法。

7. 理解带权最短路径的概念，掌握求最短路径的算法。

(八)查找

1. 理解查找的概念及其效率的评价方法。

2. 理解静态查找表的概念，熟练掌握顺序、折半和分块查找算法。

3. 理解动态查找表和二叉排序树的概念。

4. 了解平衡二叉树的概念。

5. 理解哈希表的含义，掌握哈希函数的构造和处理冲突的基本方法。

(九)内部排序

1. 掌握插入类排序的算法：直接插入排序、希尔排序。

2. 掌握交换类排序的算法：冒泡排序、快速排序。

3. 掌握选择类排序的算法：简单选择排序、堆排序。

4. 了解归并排序、基数排序的思想，了解外排序的概念。

四、参考书目

计算机网络部分：《计算机网络原理与实践》，陈鸣，高等教育出版社。数据结构部分：《数据结构与算法》，王曙燕，高等教育出版社。