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

考试概要

科目代码：816

科目名字：数据结构

1、数据结构及有关基本定义

1．知道什么是数据结构。

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

3．知道抽象数据种类的定义与表示。

4. 学会算法及其剖析：算法的概念，特质，时间复杂度，空间复杂度。

2、线性表

1．知道线性表的定义：概念，特征，线性表抽象数据种类概念。

2．学会线性表的顺序表示与达成。

3．学会线性表的链接表示与达成。

4．学会线性表的应用。

3、栈和队列

1．学会栈的定义，特征，抽象数据种类栈的概念。

2．学会栈的顺序表示和达成，栈的链接表示和达成。

3．学会队列的定义，特征，抽象数据种类队列的概念。

4．学会队列的顺序表示和达成，队列的链接表示和达成。

5．学会栈和队列的应用。

4、串

1．理解串种类的概念：串的概念，特征，串的抽象数据种类概念。

2．学会串的表示和达成。

3．学会串的模式匹配。

4．知道串的应用。

5、数组和广义表

1．学会数组：概念，特征，数组元素存储地方的计算。

2．学会特殊矩阵的压缩存储及其运算。

3．知道广义表：概念，特征，存储及运算。

6、树和二叉树

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

2．学会二叉树概念及性质。

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

4．学会二叉树的遍历运算及其达成。

5．学会线索二叉树的定义和架构。

6．学会哈夫曼树和哈夫曼编码。

7．学会树和森林的特征，树的存储结构，树和森林的遍历，树和森林与二叉树的转换。

7、图

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

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

3．学会图的常用运算：图的遍历，无向图的连通分量和生成树，最小生成树，有向无环图及其应用、最短路径。

8、查找

1．理解查找的概念及有关定义。

2．学会静态查找表：顺序表的查找，有序表的查找，索引顺序表的查找。

3．学会动态查找表：二叉排序树，平衡二叉树，B-树。

4．学会哈希表及其查找。

9、内部排序

1．理解排序的概念及有关定义。

2．学会常见的排序办法：直接插入排序，二分法插入排序，直接选择排序，冒泡排序，希尔排序，迅速排序，堆排序，归并排序，基数排序等。

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

10、其他规定：考试方法为闭卷笔试，总分150分，考试时间为180分钟。本科目考试不能用计算器。