云南省2008年普通专升本考试《数据结构》考纲

一、绪论
考试要点
数据结构的基本概念
数据的逻辑结构、存储结构
算法的特性和要求
算法的时间复杂度分析
二、线性表
考试要点
线性结构的特点
线性表的逻辑结构
线性表的顺序存储结构及其操作
线性表的链式存储结构及其操作
线性循环链表和双向链表的定义、实现以及操作
三、栈与队列
栈的基本概念、表示和实现
栈与递归的运用
队列的基本概念、表示和实现
循环队列定义、实现和操作
四、树和二叉树
考试要点
树的定义和基本术语
二叉树的定义、性质和存储结构
二叉树的三种遍历DLR、LDR、LRD
线索二叉树
树的存储结构
森林与二叉树的转换
赫夫曼树的概念、构造及赫夫曼编码
五、图
考试要点
图的定义和术语
图的存储结构
图的遍历（深度优先和广度优先搜索）
图的连通性
构造最小生成树的两种算法（普里姆算法和克鲁斯尔算法）
拓扑排序的概念
最短路徑及其应用
六、查找
考试要点
查找的基本概念
平均查找长度（ASL）的计算
顺序查找、折半查找、索引顺序查找的思想和算法
二叉排序树和平衡二叉树的概念
哈希表的基本概念
构造哈希表的方法
哈希表的冲突和处理哈希表冲突的方法
七、内部排序
考试要点
以下几种排序方法的思想和算法：插入排序，希尔排序，快速排序，选择排序；各种内部排序方法的比较。