考试科目代码：808 考试科目名称：数据结构
一、试卷结构
1、试卷成绩及考试时间
本试卷满分为150分，考试时间为180分钟。
2、答题方式：闭卷、笔试
3、试卷内容结构
数据结构 150分
4、题型结构
名词解释：4小题，每小题5分，共20分
问答题：4小题，每小题5分，共20分
应用题：4小题，每小题15分，共60分
算法设计题：2小题，每小题25分，共50分
二、考试内容与考试要求
参考书目：
1、李春葆.数据结构教程（第5版）.北京：清华大学出版社，2017.
2、马克·艾伦·维斯.数据结构与算法分析：C语言描述（英文版·原书第2版）.北京：机械工业出版社，2020.
●考试目标：
1.深刻理解并领会数据结构的基本概念和基本理论，熟练掌握常用数据结构的逻辑结构、存储结构及其相关的操作算法；
2.掌握算法的时间复杂度分析和空间复杂度分析的方法；
3．针对问题的特点选择合适的数据结构，具有构建实用高效的算法及良好的程序设计能力；
4.准确、恰当地使用计算机专业术语，论述有据，条理清晰，符合逻辑，文字表达通顺。
●考试内容
（一）数据结构绪论
1.数据、数据元素、数据项、数据结构等基本概念；
2.数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系；
3.数据的基本逻辑结构和四种常用的存储表示方法；
4.算法及算法的特点，掌握算法描述和算法分析的方法。
（二）线性表、栈和队列
1．线性表的基本逻辑结构特点、栈和队列的受限特性；
2．线性表、栈、队列在顺序存储结构下的基本运算的实现；
3．线性表、栈、队列在链式存储结构下的基本运算的实现；
4．利用线性表、栈、队列设计算法解决实际的应用问题。
（三）数组和广义表
1．数组和广义表的逻辑结构特征；
2．数组顺序存储结构下随机存储的特性及地址计算方式；
3．特殊矩阵在压缩存储时的地址计算方法；
4．稀疏矩阵压缩存储的三元组表表示方法；
（四）树和二叉树
1.树和二叉树的基本概念、掌握树的逻辑结构特征；
2.树和二叉树的性质；
3.二叉树的在链式存储结构下的基本运算实现，创建二叉树、访问节点，及遍历运算等；
4.三种遍历所得到的相应的结点访问序列；理解以遍历算法为基础，应用递归方法设计有关算法解决简单的应用问题；
5.二叉树线索化的目的及实现；
6.构造二叉树的方法；
7.哈夫曼树的含义，掌握哈夫曼算法的思想及哈夫曼树的应用。
（五）图
1.图的逻辑结构特征，理解图的常用术语；
2.邻接矩阵和邻接表这两种存储结构的特点及适用范围；
3.图的基本运算的实现及图的深度优先搜索和广度优先搜索两种遍历算法；
4.利用图的基本运算设计算法解决实际的应用问题；
5.生成树和最小生成树的概念，根据Prim和Kruskal算法构造出最小生成树；
6.单源最短路径的Dijkstra算法的基本思想，根据Dijkstra算法求解最短路径的过程；
7.关键路径的求取。
（六）查找
1.顺序查找、二分查找、分块查找的基本思想、算法实现和查找效率分析；
2.二叉查找树和B-树的定义和特点以及用途；
3.二叉查找树的插入、删除、建树和查找算法及时间性能；
4.哈希表、哈希函数、哈希地址和装填因子等有关概念；
5.解决哈希冲突的方法；
（七）内排序
1．插入类排序基本思想和典型算法实现；
2. 选择类排序基本思想和典型算法实现；
3. 交换类排序基本思想和典型算法实现；
4．归并排序的基本思想和算法实现。