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

　　考试大纲

　　科目代码：835

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

　　第一部分目标与基本要求

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

　　第二部分具体内容

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

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

　　2.了解抽象数据类型的概念与表示。

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

　　二、基本数据结构

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

　　2.理解栈的性质与特点，如出入栈顺序对应的序列；能够用栈解决常见的问题，例如符号匹配等。

　　3.理解队列的性质与特点，掌握常见的队列表示方法，例如顺序表示和链接表示；能够用队列解决常见问题，例如回文检测、击鼓传花游戏等。

　　三、树

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

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

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

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

　　5.掌握二叉搜索树以及平衡二叉搜索树(AVL)。

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

　　四、图及其算法

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

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

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

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

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

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

　　五、查找和排序

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

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

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

　　六、分治法与动态规划

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

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

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

　　第三部分 有关说明

　　1、命题说明（可包含题型设计）：无

　　2、参考书目:

　　1）《Python数据结构与算法分析》，[美] 布拉德利·米勒(Bradley N.Miller)，戴维·拉努姆(David L.Ranum) 著，吕能，刁寿钧 译， 人民邮电出版社，2019

　　2）《数据结构与算法分析 C语言描述》，[美] 马克·艾伦·维斯(Mark，Allen，Weiss) 著，冯舜玺译 译，机械工业出版社， 2019

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

　　4、本科目考试不得使用计算器。

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

　　考试大纲

　　科目代码：F49

　　科目名称：C语言

　　第三部分目标与基本要求

　　课程的目的是通过对C语言的语法规则、数据类型、数据运算、语句、系统函数、程序结构的学习，掌握应用C语言进行程序设计的技能，掌握C语言常用库函数的使用，为进行各种实用程序的开发打下基础。

　　第四部分具体内容

　　1．C 语言概述

　　（1）了解C语言的发展历史和标准

　　（2）掌握C语言程序的结构

　　（3）了解C语言的特点

　　（4）初步认识程序设计方法和程序设计一般步骤

　　（5）掌握C语言程序编译、连接和运行过程

　　2．数据类型、运算符与表达式

　　（1）掌握C语言标识符的组成

　　（2）理解C语言的基本数据类型（占用内存、数据范围）

　　（3）掌握变量定义的方法

　　（4）掌握定义变量的同时，赋初值的方法

　　（5）掌握常用的运算符（算术、关系、逻辑运算符等）的使用（功能、运算对象数目、优先级和结合性）

　　（6）掌握混合运算的数据转换方法

　　（7）掌握各种表达式的含义与使用要点。

　　3．算法和控制语句

　　（1）理解算法的概念和算法的特性

　　（2）了解算法的不同表示方法

　　（3）掌握算法的流程图表示法

　　（4）掌握常用的基本算法

　　（5）熟练掌握格式输入 / 输出函数的使用方法。

　　（6）熟练掌握 if语句的三种形式

　　（7）掌握 if 语句的基本结构以及 if 语句的嵌套，并能将条件运算符给出的语句转化成 if 语句的形式

　　（8）掌握 switch 语句的一般形式，并能把复杂的分支选择性结构化成 switch 语句来解决问题

　　（9）掌握 while 语句与 do while 语句的结构与使用方法

　　（10）掌握 for 语句的结构，熟练掌握其使用方法

　　（11）会使用常见的循环嵌套形式

　　（12）能正确区分 for 语句、 do...while 语句与 while 语句三者的不同

　　（13）掌握 break 语句和 continue 的应用及其区别

　　（14）分析总结常用的程序设计方法及算法特点，并能编写较复杂的程序

　　4．函数

　　（1）了解函数的分类

　　（2）掌握函数的声明和定义规范

　　（3）掌握函数的形式参数和实际参数的定义和用法

　　（4）掌握函数返回值的大小和类型

　　（5）掌握函数的调用方法和参数传递

　　（6）了解函数的嵌套调用

　　（7）掌握函数的递归调用及其程序规范

　　（8）了解变量存储类型的基本概念

　　（9）掌握局部变量与全局变量的概念

　　（10）能用函数的观点编写C语言程序

　　5．数组

　　（1）熟练掌握一维数组的定义，数组元素的引用方法

　　（2）掌握二维数组的定义，数组元素的引用，了解二维数组的实际意义

　　（3）掌握字符数组与字符串的概念与定义方法，熟悉常用的字符串处理函数

　　（4）掌握数组元素和数组名作为函数的程序设计

　　（5）掌握应用数组进行应用程序的设计的一般方法与典型算法

　　6．指针

　　（1）深刻理解并掌握指针的概念

　　（2）掌握指针变量的定义和应用，指针变量作为函数参数的用法

　　（3）掌握指向数组的指针与指向数组的指针变量的概念、定义和应用

　　（4）掌握指向字符串的指针的定义和应用

　　（5）理解指向函数的指针的定义和用法

　　（6）了解返回指针值的函数的定义和应用

　　（7）了解它与指向函数的指针变量的区别

　　（8）了解指针数组的定义和应用

　　（9）掌握指针的定义和应用

　　（10）了解它指针数组与指向数组的指针变量的区别

　　7．预处理命令

　　（1）了解预编译的概念，掌握宏定义的方法

　　（2）了解 “ 文件包含 ” 与预处理的应用

　　（3）了解条件编译的几种形式

　　8．结构体与共用体

　　（1）理解结构体的含义

　　（2）掌握结构体类型变量的定义方法

　　（3）掌握结构体类型变量的引用方法

　　（4）掌握结构体类型变量如何在定义的同时初始化

　　（5）理解共同体的含义，掌握共同体类型变量的定义方法

　　（6）了解结构体数组的定义和数组元素的引用

　　（7）了解指向结构体类型数据的指针的概念及使用

　　（8）了解链表结点的结构形式，链表的基本操作

　　（9）了解枚举类型的定义，及枚举类型的输入输出

　　（10）了解 TYPEDEF 的作用

　　9．文件

　　（1）了解文件的概念

　　（2）了解文件类型指针的定义和含义

　　（3）掌握文件操作的相关标准函数

　　（4）了解文件定位的操作及相关的标准函数

　　（5）了解出错检测函数的作用

　　第三部分 有关说明

　　5、命题说明（可包含题型设计）：

　　（1）考试目标的能力层次的表述

　　本课程对各考点的能力要求一般分为三个层次用相关词语描述：

　　较低要求--了解、认识、知道；

　　一般要求--理解、熟悉、会；

　　较高要求--掌握、应用。

　　（2）命题考试的若干规定

　　1）本课程的命题考试是根据本大纲规定的考试内容来确定。试卷组配兼顾覆盖面、能力层次、内容、难易程度。

　　2）试题主要题型有：单项选择题、填空题、阅读程序题、编程题等多种题型。

　　3）试卷主要测验考生对有关C语言程序设计的基本概念、基础理论、基本知识的了解熟悉掌握程度，以及运用所学理论分析问题、解决问题问题的能力。

　　6、参考书目:C语言程序设计（第五版）谭浩强

　　7、其他规定：考试方式为闭卷笔试，总分150分（分值在考试科目列表内查询），考试时间为180分钟（硕士初试、复试的考试科目考试时间均为180分钟，同等学力加试科目的考试时间为120分钟）。

　　8、本科目考试不得使用计算器。