课程二：《数据结构》考试大纲
一、考试总体要求
1．基本理论知识
（l）什么是数据结构、基本概念和基本术语，算法描述和算法分析。
（2）什么是线性表、在线性表上常进行的基本操作以及这些操作分别在顺序存储和链式存储结构下的实现及复杂度分析。
（3）栈和队列的定义、表示方法和实现。
（4）串的定义及其基本操作。
（5）数组的定义、运算和存储、稀疏矩阵的压缩存储。
（6）树的定义、基本术语和存储结构，二叉树的定义和性质、二叉树的存储结构及其各种操作，哈夫曼树。
（7）图的定义和术语、图的存储结构及其各种操作。
（8）各种查找方式的算法、适用范围及时间复杂度的分析。
（9）多种内排序算法的基本思想和算法的时间复杂度分析，不同排序方法的比较。
2．基本技能
（1）能阅读用C语言编写的算法。
（2）能分析算法所完成的功能、运行结果和时间复杂度。
（3）能根据要求用类C语言编写算法。
3.工程应用
（1）能用工程思维思考问题。
（2）能用数据结构的理论实现实际问题求解。
二、考试知识点
1．绪论
（1）数据、数据项、数据元素、数据对象、数据结构、逻辑结构、（存储）物理结构、元素、结点等基本概念。抽象数据类型的定义、表示和实现方法。
（2）算法、算法的特性、如何用类C语言来描述算法。
（3）算法设计的基本要求以及计算语句频度和估算算法时间复杂度的方法。
2．线性表
（1）线性表的定义和操作。
（2）顺序存储线性表的实现和运算。
（3）链式存储线性表，带有附加表头结点和不带附加表头结点的单链表、循环链表和双向链表的创建以及查找、插入、删除等基本操作。
（4）利用线性表的设计电话本（创建以及查找、插入、删除等基本操作）。
3．栈和队列
（1）栈和队列的定义、特点及其存储结构，栈和循环队列的实现。
（2）栈和队列的主要运算。
（3）栈的应用举例，如：数制转换、表达式求值等。
4．串和数组
（1）串的定义、空串、空格串。
（2）串的基本操作（求串的长度，复制串，判断串是否相等，求子串等）。
（3）串的顺序存储结构及在顺序存储结构下基本操作的实现。
（4）串的模式匹配算法（BF算法）。
（5）一维数组和二维数组的实现机制
（6）特殊矩阵的压缩存储
（7）稀疏矩阵的压缩存储
5．树和二叉树
（1）树的定义和术语。
（2）二叉树（完全二叉树、满二叉树）的定义和性质、二叉树的存储结构（顺序表示法和二叉链表表示法）。
（3）二叉树三种遍历的递归算法。
（4）利用哈夫曼树实现字符串的压缩/解压处理
6．图
（1）图的定义。
（2）图的基本术语。
①图及无向图、有向图、网、子图、连通图、强连通图、顶点的度、入度、出度、顶点间路径、路径长度、环。
（3）图的存储结构
①邻接矩阵
②邻接表（含逆邻接表）
（4）遍历图
①深度优先搜索遍历图的思想、算法及其时间复杂度。
②广度优先搜索遍历图的思想、算法及其时间复杂度。
（5）生成树
①生成树、最小生成树的概念。
②最小生成树的构造过程（Prim算法和Kruskal算法）及其时间复杂度。
（6）利用网的遍历思想寻找最短路径。
7．排序
（1）排序的目的、分类和排序方法的稳定性的定义。
（2）插入排序
①直接插入排序的算法。
②希尔排序的思想。
（3）选择排序
①简单的选择排序的算法。
②堆的定义、堆排序的思想。
（4）交换排序
①冒泡排序
②快速排序（重点理解）
（5）各种内部排序方法的比较。
8．查找
（1）查找、关键字、平均查找长度等概念。
（2）静态查找表的查找算法及其效率（最坏和平均查找长度）。
①顺序查找。
②二分查找（重点理解）。
（3）动态查找表
①二叉排序树定义、构造过程及其查找算法和效率。
（4）哈希表
①哈希表的特点。
②构造哈希函数的方法（除留余数法等）。
③处理冲突的方法（开放定址法，重点是线性探测再散列；拉链法）。
三、网络工程专业考试科目《专业综合》
（1）C程序设计（第五版），谭浩强，清华大学出版社，2018年08月第5版；
（2）数据结构（C语言版）（第6版，）朱战立，电子工业出版社，2020年12月。
四：试卷结构
（数据结构部分，50分）
试卷题型比例：
选择题约50%
填空题约30%
计算分析算法题约20%

展开全文