自命题科目考试大纲

命题单位：计算机与信息技术学院           

考试科目代码：      820     

考试科目名称：    数据结构  

一、试卷满分及考试时间

试卷满分为150分，考试时间为180分钟。

二、答题方式

答题方式为闭卷、笔试。

三、试卷内容结构

线性表25%，树25%，图30%，查找10%，排序10%。

四、试卷题型结构

试卷题型结构为：单选题10小题，每题1分，共10分；简答题6小题，每题8分，共48分；算法设计题，共5小题，分数分别为14分、16分、20分、20分、22分，共92分。

五、考试内容及知识点说明

（一）线性表

考试内容：线性表的定义；线性表的抽象数据类型定义、数学表示及含义；线性表常用的基本运算；线性表的顺序存储结构及基本运算的实现；线性表的链式存储结构及基本运算的实现。

考试要求：了解线性表的逻辑结构和常用的一些运算，掌握线性表的两种存储结构及其用法，掌握这两种存储结构各自的优缺点。在算法实现方面要求，能够根据实际问题的需求来决定采用何种存储结构并给出具体的算法，如：插入、删除满足条件的链表节点，在链表上排序等。

（二）栈和队列

考试内容：栈的定义，逻辑结构和常用运算；栈的存储结构；栈的实际应用；栈与递归的关系；队列的定义及存储结构；队列的应用。

考试要求：了解栈和队列的逻辑结构定义，掌握栈和队列运算特点，掌握栈和递归的关系，掌握栈和队列的顺序存储结构。在算法实现方面要求，可以熟练利用栈和队列的顺序存储结构解决实际的问题，如：走迷宫问题、表达式括号匹配问题等。

（三）串

考试内容：串的存储结构及基本运算的实现；串的模式匹配；KMP算法

考试要求：掌握字符串的两种存储结构，即定长存储结构和堆存储结构，能够在两中存储结构上实现字符串的各种运算，掌握字符串的模式匹配运算及相应的改进算法。

（四）数组和广义表

考试内容：数组的逻辑结构定义，数据的特点；数据的存储结构；稀疏矩阵的压缩存储；广义表的定义及存储结构

考试要求：了解数组及广义表的定义及特点，掌握数组的特点、存储结构及广义表的实际应用，掌握稀疏矩阵的压缩存储方法，能够在压缩存储下实现矩阵的各种运算。

（五）树和二叉树

考试内容：树和二叉树的定义；二叉树的性质；树和二叉树的存储结构；二叉树和树的遍历，线索二叉树，二叉树的层序遍历；哈夫曼树及其应用。

考试要求：了解树的逻辑结构定义，掌握二叉树的定义、性质、存储结构和运算，掌握树和二叉树之间的关系。在算法实现方面要求，熟练掌握二叉树的递归和非递归遍历，并能够用之解决实际问题，如：计算树的层数、度，查找满足条件的节点等。

（六）图

考试内容：图的定义及基本术语；图的存储结构；图的两种遍历方法及算法；图的连通性；拓扑排序和关键路径；最短路径；最小生成树。

考试要求：了解图的逻辑结构定义，掌握图的术语、图的两种常用存储结构，即邻接矩阵和邻接表。在算法实现方面要求，熟练掌握图的两种遍历方法，并能够根据图的基本原理解决一些应用问题，如：判定图的连通性、判定是否有环、计算特定路径等。

（七）查找

考试内容：查找方法的分类；各类查找表常用的查找方法；典型查找方法的算法实现。

考试要求：了解动态查找表和静态查找表的逻辑结构定义，掌握静态查找表的三类查找方法的思想，对数据元素的要求、数据元素的存储结构，平均查找长度。掌握二叉排序树的定义及构造方法，二叉树的平衡化处理。掌握散列表的定义及创建散列表的方法，以及查找散列表的方法。

（八）内排序

考试内容：排序的基本概念，排序方法分类的依据；插入排序、快速排序、选择排序、归并排序、基数排序中各种常用的排序方法。

考试要求：了解排序的定义及术语，排序方法的评价方法，掌握的排序方法有：直接插入排序、shell插入排序，快速排序，堆排序，二路归并排序，链式基数排序，要知道它们的排序思想，并能描述排序过程。

六、参考书

数据结构（C语言版），严蔚敏，吴伟民著，清华大学出版社，2017年。