俄亥俄州大学南华大学2020年881数据结构

附件

5

南华大学

年硕士研究生入学考试大纲

招生学院

计算机学院

招生专业代码

083500

085400

招生专业名称

软件工程

电子信息

考试科目代码及名称

881

数据结构

一、考试内容

1

、

数据结构基本概念及简单的算法分析

1)

数据结构、

抽象数据类型、数据类型、算法的基本概念

2)

算法性能分析与度量：

算法 的性能标准；

算法的空间复杂度与时间复杂度

概念与分析方法；时间复杂 度的渐进表示法；

2

、线性表

1)

顺序表：顺序表的定义和特点； 顺序表的类定义；顺序表的查找、插入和

删除；

顺序表的优缺点

2)

单链表：

单链表的结构；

单链表的 类定义；

单链表中

的插入与删除；带表头结点的单链表；静态链表

；链表的优缺点

3)

表：

循环链表的类定义；

用循环链表解约瑟夫 问题；

4)

双向链表的基本操作

3

、栈和队列

1)

栈：栈的抽象数据类型；栈的顺序存储表示；栈的链接存储表示

2)

队列

：队列的抽象数据类型；队列的顺序存储表示；队列的链接存储表

示；

3)

栈和队列的应用

4

、树与森林

1)

树和森林的概念：树的定义；树的术语；树的抽象数据类型

2)

二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型

3)

二叉树的表示：顺序表表示；链表存储表示

4)

二叉树遍历：

中序遍历；

前序遍历；

后序遍历；

不用栈的二叉树中序遍历

算法

5)

线索化二叉树：线索；中序线索化二叉树；前序与后序的线索化

6)

树与森林：

树的存储表示；

森林与二叉树的转换；

树的遍历；

森林的遍历；

7)

霍夫曼树：带权路径长度；霍夫曼树；霍夫曼编码

5

、

图

1)

图的基本概念：图的基本概念；图的抽象数据类型

2)

图的存储表示：邻接矩阵；邻接表；邻接多重表

3)

图的遍历与连通性：深度优先搜索；广度优先搜索；连通分量；

4)

图的基本算法：

最小生成树：克鲁斯卡尔算法；普里姆算法；最短路径；

关键路径

6

、查找

1)

查找、查找表及平均查找长度的基本概念

2

）顺序查找；基于有序顺序表的二分查找算法及分析

3)

二叉排序树：定义；二叉排序上的查找、插入与删除；

4) AVI

树：

AVI

树的定义；平衡化旋转；

5)

散列：

散列表与散列方 法；

散列函数；

处理溢出的闭散列方法；

处理溢出

的开散列方法；散列表分析

7

、排序

1

）

排序的基本术语与概念

2)

插入排序：

直接插入排序；

对分插入排序；

链

表插入排序；

希尔排序

3)

交换排序：

起泡排序；

快速排序

4)

选择排序：

直

接选择排序；堆排序

5)

归并排序：归并；迭代的归并排序算法；递归的表归

并排序

6)

基数排序：多关键码排序；链式基数排序

7)

外排序的基本概念