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

　　考试大纲

　　科目代码：844

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

　　第一部分目标与基本要求

　　目标：

　　“数据结构与算法”考试包含“数据结构”、“算法设计与分析”等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。

　　基本要求：

　　1. 理解数据结构的基本概念；掌握数据的逻辑结构、存储结构以及各种基本操作的实现。

　　2. 在掌握基本的数据处理原理和方法的基础上，能够针对具体问题进行算法设计与分析。

　　3. 能够选择合适的数据结构和方法进行问题求解。

　　4. 理解分治法、贪心法、动态规划法和回溯法的算法设计策略，能够运用这四种算法对典型实际问题进行数学建模，设计合理的算法，实现算法时间复杂度和空间复杂度的优化。

　　5. 具备采用C/C++语言设计与实现算法的能力。

　　第二部分具体内容

　　1．数据结构及相关基本概念

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

　　（2）掌握算法时间复杂度的分析：递归算法时间复杂度的分析、非递归算法时间复杂度的分析。

　　2．线性表

　　（1）理解线性表的概念、定义及其特点；

　　（2）掌握线性表的顺序存储表示与实现；

　　（3）掌握线性表的链式存储表示与实现；

　　（4）掌握线性表的应用。

　　3．栈和队列

　　（1）理解栈的概念、定义及其特点；

　　（2）掌握栈的顺序存储表示和实现、栈的链式存储表示和实现；

　　（3）理解队列的概念、定义及其特点；

　　（4）掌握队列的顺序存储表示和实现、队列的链式存储表示和实现；

　　（5）掌握栈和队列的应用。

　　4．串

　　（1）理解串的概念、串的定义以及串的特点；

　　（2）掌握串的存储表示方法（定长顺序存储表示、堆分配存储表示、块链存储表示）以及串的基本操作；

　　（3）掌握串的模式匹配算法（简单模式匹配算法、KMP算法）。

　　5．数组

　　（1）掌握数组的顺序存储表示（行序为主序、列序为主序），能够进行数组元素存储位置的运算；

　　（2）掌握特殊矩阵（对称矩阵、上（下）三角矩阵、对角矩阵）的压缩存储及其运算；

　　（3）掌握稀疏矩阵的三元组存储表示及其应用。

　　6．树和二叉树

　　（1）理解树的定义及相关概念；

　　（2）掌握二叉树的定义及性质；

　　（3）掌握二叉树的顺序存储结构和链式存储结构；

　　（4）掌握二叉树遍历的概念、算法和应用；

　　（5）理解线索二叉树的概念和构造；

　　（6）掌握哈夫曼树的概念、构造方法和哈夫曼编码；

　　（7）了解树和森林的概念；

　　（8）掌握树的存储结构、树的遍历方法以及森林的遍历方法；

　　（9）掌握“树与二叉树”、“森林与二叉树”相互转换的方法。

　　7．图

　　（1）理解图的定义及相关概念；

　　（2）掌握图的存储结构：邻接矩阵、邻接表；

　　（3）掌握图的遍历算法：深度优先遍历、广度优先遍历；

　　（4）掌握图的应用：最小生成树、拓扑排序、重连通图和关节点、最短路径、关键路径。

　　8．查找

　　（1）理解查找的定义及相关概念；

　　（2）掌握静态查找表的概念和算法：顺序表的查找，有序表的查找；

　　（3）掌握动态查找表的概念和算法：二叉排序树，平衡二叉树；

　　（4）掌握哈希表的构造、查找及其处理冲突的方法。

　　9．内部排序

　　（1）理解排序的定义及相关概念；

　　（2）掌握常用的排序算法及应用：直接插入排序，折半插入排序，选择排序，冒泡排序，希尔排序，快速排序，堆排序，二路归并排序，基数排序等；

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

　　10．算法部分

　　（1）理解分治法、贪心法、动态规划法、回溯法的设计思想和算法框架；

　　（2）掌握应用分治法求解以下问题的求解策略：

　　1) 查找第k小问题，

　　2) 查找两个等长有序序列的中位数问题，

　　3) 循环赛日常表的安排问题；

　　（3）掌握应用贪心法求解以下问题的求解策略：

　　1) 活动安排问题，

　　2) 一般背包问题，

　　3) 多机调度问题，

　　4) 流水作业调度问题；

　　（4）掌握应用动态规划法求解以下问题的求解策略：

　　1) 最大连续子序列和问题，

　　2) 最长公共子序列问题，

　　3) 资源分配问题；

　　（5）掌握应用回溯法求解以下问题的求解策略：

　　1) 0/1背包问题，

　　2) n皇后问题，

　　3) 图的m着色问题；

　　（6）掌握分治算法、贪心算法、动态规划算法和回溯算法的时间复杂度的分析方法。

　　第三部分有关说明

　　1．命题说明

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

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

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

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

　　较高要求：掌握、能够、运用。

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

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

　　2）题型主要有：单项选择题、填空题、判断题、综合应用题、算法题等多种题型。

　　3）试卷主要考察考生对有关“数据结构”和“算法设计与分析”的基本概念、基础原理、基本知识的了解熟悉程度，以及运用所学理论知识分析问题、解决问题的能力。

　　2．参考教材

　　（1）《数据结构（C语言版）》，严蔚敏，吴伟民，清华大学出版社；

　　（2）《算法设计与分析（第2版）》, 李春葆, 清华大学出版社。

　　3．其他规定

　　考试方式为闭卷笔试，总分150分（数据结构部分占130分，算法部分占20分），考试时间为180分钟。

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

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

　　考试大纲

　　科目代码：F55

　　科目名称：C/C++程序设计基础

　　第一部分目标与基本要求

　　课程的目的是通过学习C/C++语言，掌握常见的算法以及面向过程和面向对象程序设计的思想和方法。通过应用C/C++语言进行程序设计，培养学生编写、修改、调试各类数值计算程序和数据处理程序的技能。此外，课程还旨在提升学生的计算思维能力，加强他们对专业领域问题的抽象能力，并通过应用C/C++语言解决问题的能力，为后续进行专业领域的研究和程序模拟打下基础。

　　第二部分具体内容

　　1.C 语言与基本语法

　　(1)了解计算机程序和计算机语言的概念及C语言的发展历程；

　　(2)掌握简单的C语言程序的编写、调试与运行；

　　(3)掌握顺序程序设计的概念；

　　(4)熟练掌握不同的数据类型，不同类型常量的表示法，变量的定义方法，以及各种运算符和表达式；

　　(5)熟悉不同类型的C语句；

　　(6)掌握数据输入输出的方法，输入输出语句中常用的格式说明、控制字符串；

　　(7)了解预处理的概念，熟悉宏定义的方法，掌握包含语句的使用。

　　2.C语言程序设计结构与算法

　　(1)熟悉结构化程序设计的基本概念；

　　(2)掌握顺序、分支、循环等控制语句的语法；

　　(3)能熟练的使用循环、分支等流程控制语句编写程序；

　　(4)了解什么是算法及其基本特性；

　　(5)了解用自然语言、N-S流程图、伪代码表示算法的方法；

　　(6)熟悉结构化程序设计模式；

　　(7)掌握常用的基本算法。

　　3.数组

　　(1)熟悉数组元素在内存中的存放机制与表示方法；

　　(2)掌握定义、初始化、引用一维数组的方法；

　　(3)掌握定义、初始化、引用二维数组的方法；

　　(4)掌握字符数组的定义和使用，字符串处理函数的使用；

　　(5)掌握数组的典型应用实例，能利用数组编程解决实际问题。

　　4.函数

　　(1)了解函数的概念与类型；

　　(2)掌握函数的声明、定义和调用方法；

　　(3)熟悉函数的递归调用与嵌套调用；

　　(4)熟悉C语言所支持的函数参数类型，掌握函数的参数传递方法；

　　(5)熟悉局部变量和全局变量的概念及有效范围；

　　(6)了解变量的存储方式与生存周期；

　　(7)能熟练应用函数编写程序。

　　5.指针

　　(1)了解地址的基本概念，以及在C语言中的表述方法；

　　(2)掌握不同类型的变量地址和函数地址在C语言中的表示方法；

　　(3)掌握C语言所支持的不同类型的指针变量（如字符串指针、函数指针等）的定义和引用；

　　(4)熟悉指针作为函数参数和指针型返回值，指针数组和指向数组的指针，指向函数的指针，以及具体应用方法。

　　6.用户自定义数据类型

　　(1)了解结构体的含义及结构体变量的概念；

　　(2)掌握结构体变量和结构体数组的定义、初始化及应用方法；

　　(3)熟悉结构体指针的运用；

　　(4)熟悉链表的概念和使用；

　　(5)熟悉枚举类型；

　　(6)了解typedef的使用。

　　7.文件的读写操作

　　(1)了解C语言文件的基本知识；

　　(2)掌握打开和关闭文件的方法；

　　(3)掌握顺序读写文件和随机读写文件的方法；

　　(4)了解文件读写的出错检测。

　　8．类的定义与使用

　　(1)熟悉面向对象程序设计的基本原则；

　　(2)掌握类的定义、对象的定义、对象的初始化；

　　(3)掌握类的成员函数的定义及使用；

　　(4)理解对象的生存期，类的静态成员的定义及使用；

　　(5)掌握类的组合；

　　(6)掌握构造函数、析构函数的功能、定义、使用方法及调用顺序；

　　(7)理解前向引用的功能、定义及使用；

　　(8)熟悉友元函数和友元类的功能、定义及使用；

　　(9)理解常对象、常引用以及用const修饰的类成员。

　　9．类的继承与派生

　　(1)熟悉类继承的基本概念；

　　(2)掌握派生类的定义及使用；

　　(3)理解类型兼容性规则；

　　(4)掌握继承中派生类的构造函数、析构函数的功能、定义、使用方法及调用顺序；

　　(5)了解虚基类。

　　10．多态性

　　(1)熟悉多态与重载的概念；

　　(2)掌握函数与运算符重载的功能、定义及使用方法；

　　(3)理解一般虚函数成员、虚析构函数的功能、定义及使用方法；

　　(4)了解纯虚函数和抽象类。

　　第三部分有关说明

　　1．命题说明

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

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

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

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

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

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

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

　　2）试题主要题型有：单项选择题、填空题、程序填空题、程序改错题、程序设计题等多种题型。

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

　　2．参考书目

　　（1）《C程序设计（第5版）》，谭浩强，清华大学出版社

　　（2）《C++语言程序设计（第5版）》，郑莉，董渊，清华大学出版社

　　3．其他规定

　　考试方式为闭卷笔试，总分150分（C语言部分约占105分，C++部分约占 45分)，考试时间为180分钟。

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