附件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.非导引型传输媒体 第三章 数据链路层 考试要求 本章要求学生掌握链路和数据链路的概念，PPP协议的特点、帧格式、PPP实现透明传输的方法，掌握局域网的拓扑结构，熟悉链路层的两个子层及其功能、媒体共享技术、以太网的两个标准，掌握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协议 (五)电子邮件 1.电子邮件系统的组成结构 2.电子邮件格式与MIME 3.SMTP协议与POP3协议 (六)动态主机配置DHCP 1.DHCP的概念 2.DHCP工作过程