考试阶段：复试 科目满分值：

100

考试科目：数据结构及算法 科目代码：/

考试方式：闭卷笔试考试时长：

180分钟

一、科目的总体要求

数据结构及算法是区块链工程专业的核心必修课程,要求学生掌握各种基本数据结构的逻辑结构、存储结构、基本操作的算法思想和算法实现, 掌握实际数据处理中常用的排序算法和数据查找算法，以及不同的排序算法之间的性能比较，不同查找算法对查找速度的影响情况。并能够应用高级语言编写算法(C/C++/Java)。

建立有关数据结构最基本的概念，包括数据的逻辑结构、存储结构和算法，算法分析的基本概念与基本方法。

掌握线性表的基本概念以及两种存储结构(顺序和链式)的构造原理，掌握在各种存储结构下对线性表进行的基本操作的算法设计。

掌握堆栈和队列的基本概念与特征，掌握在两种存储结构下如何对堆栈和队列进行插入和删除等操作，以及利用堆栈与队列解决实际问题的基本方法。

掌握数组的基本概念，物理结构和基本操作的实现

充分了解二叉树型结构的逻辑特征，掌握顺序和链式存储结构的构造原理，能够熟练地利用常用的三种遍历方法(递归和非递归实现)，掌握利用二叉树的遍历操作解决实际问题的方法，掌握二叉树的其它相关的操作算法。掌握树的各种存储结构和相关的操作算法。

充分了解图的逻辑结构的特点，掌握常用的两种存储方法(邻接矩阵和邻接链表)，掌握最小生成树(Prim算法和Kruskal算法)、最短路径的具体求解过程。

充分了解各种顺序文件的结构与相应的查找方法;了解各种查找算法之间时空效率的差异;掌握二叉排序树的建立以及相关算法，平衡二叉树的创建过程;比较各种查找方法的性能。

充分了解各种排序方法的排序特点、排序过程和算法实现，对于任意给出的数据元素序列，能够熟练地采用指定排序方法进行排序，并且能够对每一种排序方法排序过程中所进行的元素之间的比较次数、相应排序算法的时间、空间、排序的稳定性等性能进行简单分析。

二、考核内容与考核要求

1、基础知识

1)数据结构的基本概念，数据的逻辑结构、存储结构。

2)算法的定义、算法的基本特性以及算法分析的基本概念。

2、线性表

1)线性关系、线性表的定义，线性表的基本操作。

2)线性表的顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)的构造原理。在以上两种存储结构上对线性表实施的最主要的操作(包括三种链表的建立、插入和删除、检索等)的算法设计、实现和复杂性分析。

3、堆栈与队列

1)堆栈与队列的基本概念、基本操作。

2)堆栈与队列的顺序存储结构与链式存储结构的构造原理。

3)在不同存储结构上对堆栈与队列实施插入与删除等基本操作对应的算法设计、实现和复杂性分析。

4)堆栈与队列的应用算法。

4、数组

1)数组的概念、多维数组的实现。

2)多维数组元素的定位算法。

5、树与二叉树

1)树的定义和性质。

2)二叉树的概念、性质。

3)二叉树的各种存储方式及其特点。

4)遍历二叉树及其应用。

5)树和二叉树的转换。

6、图

1)图的定义，基本概念，图的分类，常用名词术语。

2)图的邻接矩阵存储方法、邻接表存储方法的构造原理。

3)图的遍历操作及连通性问题。

4)最小生成树，最短路径。

7、查找

1)静态查找表的顺序查找算法、二分查找算法和分块查找算法。

2)动态查找表的二叉查找树、平衡二叉树。

8、内排序

1)排序的基本概念，排序方法的分类。

2)插入排序法(含折半插入排序法和希尔排序)、选择排序法(含堆排序)、冒泡排序法、快速排序法、归并排序。各种排序方法排序的原理、规律和特点，各种排序算法的时空复杂度的简单分析。

三、题型结构

考试包含多种题型：填空题、选择题、综合题和算法编写题等。

四、其它要求

具体考试时间以《准考证》为准。