附件1： 

 

数据结构与计算机网络科目考试大纲 

 

 

 

一.参考书目 

 

1. 陈桂芬戴小鹏，《数据结构》（2013 年），中国农业出版社 

 

2. 严蔚敏吴伟民，《数据结构》（2009 年），清华大学出版社

 

3. 谢希仁，《计算机网络》（第七版）（2017 年），电子工业出版社 二.考试内容与基本要求 

（一）数据结构部分

 

 第一章绪论[考试要求]

本章要求学生熟悉和了解数据结构的基本概念和述语，了解数据结构的研究内容和地位，掌握数据的逻辑结构和存储结构，算法的特点以及算法分析的度量方法。

[考试内容]

 

1. 数据结构的基本概念； 

 

2. 逻辑结构和存储结构的定义、划分；

 

3. 算法的特性；

 

4. 算法的时间复杂度计算方法；第二章基本的线性表 

[考试要求]

 

掌握线性表的定义和特点；重点掌握顺序表的表示和实现；重点掌握线表的表示和实现。

[考试内容]

 

1. 顺序表的地址计算； 

 

2. 顺序表的类型定义； 

 

3. 顺序表的初始化、插入、删除、查找以及各算法的时间复杂度计算方法； 

 

4. 链表的类型定义； 

 

5. 单链表的初始化、插入、删除、查找以及各算法的时间复杂度计算方法； 

 

6. 顺序表和链表的优缺点对比； 

第三章 受限的线性表——栈和队列[考试要求]

了解栈和队列的概念、操作特点；掌握顺序栈的定义、入栈和出栈操作的实现；掌握顺序队列的定义、入队和出队操作的实现；掌循环队列的基本操作；

[考试内容]

 

1. 栈和队列的操作特点； 

 

2. 顺序栈的类型定义； 

 

3. 顺序栈的初始化、判空、入栈和出栈操作的实现；

 

4. 栈的应用，如数制转换、括号匹配； 

 

5. 顺序队列的入队和出队操作的实现； 

 

6. 循环队列的判空、判满、出队、入队、求长等操作的表达式表示；第六章线性结构的推广——数组和广义表

[考试要求]

 

了解数组和广义表的概念、非线性特点；掌握数组的运算、特殊矩阵的压缩存储、广义表的基本运算；

[考试内容]

 

1. 数线的运算； 

 

2. 对称矩阵、三角矩阵的压缩存储运算； 

 

3. 三元组表的类型定义、转置操作； 

 

4. 广义表的概念、基本运算；第七章树和二叉树

[考试要求]

 

熟悉树型结构的特点；了解树和二叉树的特点区别；掌握二叉树的性质、顺序和链式存储方式的表示和实现；掌握树、森林与二叉树之间的转换；掌哈夫曼树的应用；

[考试内容]

 

1. 二叉树的性质； 

 

2. 二叉树的顺序存储方式；

 

3. 二叉树的链式存储方式；

 

4. 二叉树的遍历操作、线索化操作； 

 

5. 树、森林、二叉树之间的转换； 

6. 哈夫曼树的定义、构造方法及哈夫曼树的编码和解码；第八章图

[考试要求]

 

了解图的定义、基本概念、基本操作特点；掌握图的存储结构、图的遍历、小生成树、拓扑排序、关键路径、短路径等问题；

[考试内容]

 

1. 图的基本术语； 

 

2. 图的邻接矩阵、邻接表存储结构的实现； 

 

3. 图的深度优先遍历和广度优先遍历； 

 

4. 小生成树的概念及构造方法； 

 

5. 拓扑排序的主法、关键路径应用； 

 

6. 单源矩路径算法；第 9 章高效查找

[考试要求]

 

熟悉查找的基本概念；掌握查找算法的基本思想以及查找效率的运算方法；[考试内容]

1. 顺序查找、拆半查找、分块查找； 

 

2. 二叉排序树的构造、查找； 

 

3. 平衡二叉排序的构造； 

 

4. 散列查找函数的构造、解决冲突的方法； 

 

 

第 10 章优化排序[考试要求]

熟悉排序的基本概念；掌握排序算法的基本思想以及排序算法的时间效率的运算；[考试内容]

1. 插入排序、拆半插入、希尔排序； 

 

2. 冒泡排序、快速排序； 

 

3. 直接选择排序、堆排序；

 

4. 归并排序； 

 

 

（二）计算机网络部分

 

 第一章概述[考试要求]

本章要求学生了解因特网的发展阶段和标准化工作、计算机网络在我国的发展，掌握计算机网络重要的两个功能、主机间的两种通信方式、分组交换的过程和特点，理解网络的组成、因特网的组成、电路交换、报文交换的特点，掌握计算机网络的定义和分类、计算机网络的性能指标、计算机网络的层次模型、各层完成的功能和相关概念。 

[考试内容]

 

(一)计算机网络概述

 

1. 计算机网络的概念、组成与功能 

 

2. 计算机网络的分类 

 

3. 计算机网络的标准化工作及相关组织(二)计算机网络体系结构与参考模型  1.计算机网络分层结构 

2. 计算机网络协议、接口、服务等概念 

 

3. ISO/OSI 参考模型和TCP/IP 模型第二章物理层 

[考试要求]

 

本章要求学生熟悉数据通信系统模型，数据通信的术语，了解接口的一些特性，掌握三种通信方式，限制码元在信道上的传输速率的因素，香农公式的含义，掌握频分复用技术、时分复用技术、统计时分复用技术，熟悉导向传输媒体，了解非导向传输媒体、波分复用、码分复用。 

[考试内容]   (一)通信基础 

1. 信源、信宿、信号、信道、码元、带宽、速率等基本概念 

 

2. 奈奎斯特定理与香农定理

 

3. 编码与调制 

 

4. 信道复用  (二)传输介质 

1. 导引型传输媒体（双绞线、同轴电缆、光纤） 

2. 非导引型传输媒体第三章 数据链路层[考试要求]

本章要求学生掌握链路和数据链路的概念，  协议的特点、帧格式、  实现透明传输的方法，掌握局域网的拓扑结构，熟悉链路层的两个子层及其功能、媒体共享技术、以太网的两个标准，掌握CSMA/CD 的原理、争用期、集线器的特点、硬件地址的组成、MAC 帧的格式，熟悉截断二进制指数退避算法，熟悉以太网的信道利用率、帧间小间隔、无效的MAC 帧，掌握物理层、链路层扩展以太网的方法，透明网桥自学习和转发帧的过程，交换机的特点。 

[考试内容]

 

(一)数据链路层的功能(二)组帧 

(三)差错检测（CRC）(四)介质访问控制   1.信道划分 

频分多路复用、时分多路复用、波分多路复用、码分多路复用的概念和基本原理。2.随机访问 

CSMA/CD 协议(五)局域网 

1. 局域网的基本概念与体系结构 

 

2. 以太网与IEEE802.3(六)网络设备 

1. 集线器（物理层设备） 

 

2. 交换机（数据链路层设备）第四章网络层

[考试要求]

 

本章要求学生掌握IP 地址的组成及表示方法、分类、特殊的IP 地址，熟悉IP 地址和物理地址的区别，掌握ARP 的作用及原理、IP 数据报的格式，掌握子网划分的方法、子网掩码、子网网络地址、默认的子网掩码，熟悉三级IP 地址的组成，了解IP 地址分类的原因，掌握无分类的两级编址、CIDR 块、CIDR 地址掩码，熟悉路由聚合、构造超网、长前缀匹

配，掌握自治系统AS 的概念、路由选择协议的分类、RIP 协议的要点、路由表的建立和更新过程，掌握OSPF 协议的三个要点、区域、OSPF 分组的分类。 

[考试内容]

 

(一)网络层的功能(二)路由算法

1. 静态路由与动态路由

 

2. 距离-向量路由算法

 

3. 链路状态路由算法(三)IPv4

1. IPv4 分组

 

2. IPv4 地址

 

3. 子网划分、路由聚集、子网掩码与CIDR

 

4. ARP协议与ICMP协议

 

5. VPN与NAT

 

(四)路由协议1.自治系统

2. 域内路由与域间路由

 

3. RIP路由协议

 

4. OSPF 路由协议(五)网络层设备

1. 路由器的组成和功能

 

2. 路由表与路由转发第五章运输层

[考试要求]

 

本章要求学生掌握UDP 的主要特点、TCP 的主要特点，停止等待协议、连续ARQ 协议、TCP 的首部格式，TCP 的流量控制机制，TCP 滑动窗口，TCP 超时重传时间的选择、TCP 的选择确认机制，掌握慢开始、拥塞避免、快重传、快恢复四种拥塞控制方法，熟悉拥塞控制的一般原理，掌握TCP 连接建立和释放的过程。 

[考试内容]

 

(一)传输层提供的服务

1. 传输层的功能

 

2. 传输层寻址与端口

 

3. 无连接服务与面向连接服务(二)UDP协议

1. UDP数据报

 

2. UDP校验

 

(三)TCP协议

 

1. TCP段

 

2. TCP 连接管理

 

3. TCP 可靠传输

 

4. TCP 流量控制与拥塞控制第六章应用层

[考试要求]

 

本章要求学生掌握掌握DNS 的作用、域名的解析过程、FTP 的两个连接和两个端口号，熟悉因特网的域名结构、FTP 的特点，了解域名服务器的层次划分，掌握WWW、电子邮件协议与DHCP 协议。 

[考试内容]

 

(一)网络应用模型1.客户/服务器模型

2.P2P模型

 

(二)域名系统DNS 1.层次域名空间

2. 域名服务器

 

3. 域名解析过程

 

(三)文件传送FTP 1.FTP协议的工作原理

2.控制连接与数据连接(四)万维网WWW

1. WWW的概念与组成结构

 

2. HTTP协议