南华大学2012年硕士研究生入学考试大纲
855数据结构
一、考试内容
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） 外排序的基本概念
二、考试形式与试卷结构
（一）试卷成绩及考试时间
本试卷满分为100分，考试时间为120分钟。
（二）答题方式
答题方式为闭卷、笔试。
（三）试卷内容结构
数据结构基本概念：20%顺序与链式线性表：15% 栈与队列：15%
树与二叉树：20% 图：15% 查找与排序：15%
（四）试卷题型结构
简答题（约20分）；应用题（约45分）；算法分析（约20分） 算法设计（约15分）。
您现在的位置： 