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

考试大纲

科目代码:816

科目名称:数据结构

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

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

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

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

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

二、线性表

1．了解线性表的概念:定义，特点，线性表抽象数据类型定义。

2．掌握线性表的顺序表示与实现。

3．掌握线性表的链接表示与实现。

4．掌握线性表的应用。

三、栈和队列

1．掌握栈的概念，特点，抽象数据类型栈的定义。

2．掌握栈的顺序表示和实现，栈的链接表示和实现。

3．掌握队列的概念，特点，抽象数据类型队列的定义。

4．掌握队列的顺序表示和实现，队列的链接表示和实现。

5．掌握栈和队列的应用。

四、串

1．理解串类型的定义:串的定义，特点，串的抽象数据类型定义。

2．掌握串的表示和实现。

3．掌握串的模式匹配。

4．了解串的应用。

五、数组和广义表

1．掌握数组:定义，特点，数组元素存储位置的计算。

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

3．了解广义表:定义，特点，存储及运算。

六、树和二叉树

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

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

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

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

5．掌握线索二叉树的概念和构造。

6．掌握哈夫曼树和哈夫曼编码。

7．掌握树和森林的特点，树的存储结构，树和森林的遍历，树和森林与二叉树的转换。

七、图

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

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

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

八、查找

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

2．掌握静态查找表:顺序表的查找，有序表的查找，索引顺序表的查找。

3．掌握动态查找表:二叉排序树，平衡二叉树，b-树。

4．掌握哈希表及其查找。

九、内部排序

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

2．掌握常用的排序方法:直接插入排序，二分法插入排序，直接选择排序，冒泡排序，希尔排序，快速排序，堆排序，归并排序

，基数排序等。

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

十、其他规定:考试方式为闭卷笔试，总分150分，考试时间为180分钟。本科目考试不得使用计算器。

原标题:南京信息工程大学2022年硕士研究生招生考试自命题科目考试大纲
文章来源:https://yjs.nuist.edu.cn/info/1015/4713.htm