南京信息工程大学硕士研究生招生入学考试

考试大纲

科目代码：853

科目名称：数据结构与算法分析

第一部分  目标与基本要求

数据结构与算法分析考试是为南京信息工程大学招收电子信息类（人工智能方向）专业学位硕士研究生而设置的具有选拔性质的全国统一入学考试科目，其目的是科学、公平、有效地测试学生掌握大学本科阶段数据结构与算法分析的基本知识、基本理论，以及运用数据结构与算法分析的理论和方法分析和解决问题的能力。评价的标准是高等学校本科毕业生能达到的及格或及格以上水平，以保证被录取者在开展人工智能方向的研究工作中，具有基本的计算机程序设计、数据结构与算法分析的理论素质，并具有理解和分析工程实际问题和具有工程实际应用的基本能力。

第二部分 内容与考核目标

一、数据结构及相关基本概念

1．了解什么是数据结构。

2．理解数据结构有关的概念和术语：数据、数据元素、数据对象、数据结构、线性结构、树形结构、图结构、集合结构。

3．了解抽象数据类型的概念与表示。

4. 掌握算法及其分析：算法的定义，特性，时间复杂度，空间复杂度。

二、基本数据结构

1．掌握线性数据结构：线性表的顺序表示与实现、线性表的链接表示与实现。

2．理解栈的性质与特点，能够用栈解决常见的问题，例如括号匹配等。

3．理解队列的性质与特点，掌握常见的队列表示方法，例如顺序表示和链接表示。

 三、树

1．理解树的定义及相关概念。

2．掌握二叉树定义及性质。

3．掌握二叉树的顺序存储结构合连接存储结构。

4．掌握二叉树的遍历运算及其实现。

5．掌握二叉搜索树以及平衡二叉搜索树（AVL）。

6. 掌握二叉堆实现优先队列的方法。

四、图及其算法

1．理解图的定义及相关概念。

2．掌握图的存储结构：邻接矩阵，邻接表。

3．掌握图的宽度优先搜索与深度优先搜索，能够用深度优先搜索分析和解决骑士游历问题。

4. 掌握图的拓扑排序、强连通分量。

5．掌握图的最短路径问题的求解方案，理解并能够分析Dijistra算法。

6．掌握图的最小生成树问题的解决方法。

五、查找和排序 

1．掌握顺序查找、二分查找、哈希查找方法，并能够进行分析。

2．掌握常用的排序方法：直接插入排序，直接选择排序，冒泡排序，希尔排序，快速排序，堆排序，归并排序，基数排序等。

3．理解各类内部排序方法的特点：时间复杂度，空间复杂度，稳定性。

六、分治法与动态规划 

1．理解分治法和动态规划方法的主要特点和所适用的不同场景。

2. 掌握常见的适用于分治法的典型问题，例如二分搜索、归并排序、快速排序、大整数乘法、快速傅立叶变换等等，能够对分治法解决的问题进行算法分析。

3. 掌握常见的适用于动态规划的典型问题，例如图的最短路径问题、斐波那契数列问题、最长公共子序列等，能够对动态规划解决的问题进行算法分析。

第三部分  有关说明与实施要求

1、命题说明：无

2、参考书目: 《Python数据结构与算法分析》（第2版），布拉德利·米勒（Bradley N.Miller），戴维·拉努姆（David L.Ranum）著，人民邮电出版社，2019年

3、其他规定：考试方式为闭卷笔试，总分 150分，考试时间为 180 分钟。