2331数据结构自考大纲.doc

第 1 章 概论(一) 课程内容1.1 引言1.2 数据、逻辑结构和运算1.3 存储实现和运算实现(二) 学习的目的与要求本章集中介绍贯穿和应用与数据结构课程始终的基本概念和主要工具，概括反映了后继各章的基本问题，为进入具体内容的学习提供了必要的引导本章总的要求是：理解数据、数据元素和数据项的概念及其相互关系；理解逻辑结构、基本运算和数据结构的概念、意义和分类；理解存储结构与逻辑结构的关系；了解机内表示的级别和四种基本存储方式；理解算法的概念；了解算法分析的基本概念、时间复杂性及其量级的概念本章重点是逻辑结构和数据结构的概念难点是算法的时间复杂性分析第 2 章 线性表(一) 课程内容2.1 线性表的基本慨念2.2 线性表的顺序实现2.3 线性表的链实现2.4 其它运算在单链表上的实现2.5 其它链表2.6 顺序实现与链接实现的比较2.7 串(二 ) 学习的目的与要求顺序表和单链表分别是最简单、基本的顺序存储结构和链式存储结构顺序表和单链表上实现基本运算的算法是数据结构中最简单、基本的算法这些内容构成以下各章的重要基础，因此本章是本课程的重点之一维持对本章有较高的要求：深刻理解线性结构的定义和特点；理解线性表的概念；熟练掌握顺序表和单链表的组织方法及实现基本运算的算法；掌握在顺序表和单链表上进行算法设计的基本技能；了解顺序表与链表的优缺点；了解串的概念、运算和存储方法。

本章重点：线性结构的定义和特点；线性表的运算；顺序表和单链表的组织方法和算法设计难点：单链表上的算法设计第 3 章 栈、队列和数组(一) 课程内容3.1 栈3.2 队列3.3 数组 3.4 综合应用示例栈和队列的逻辑结构与线性表的逻辑结构相同，二维数组逻辑结构可以看成是线性结构的推广；而它们的运算都可以看成是线性表运算的限制本章总的要求是：理解栈和队列的定义、特点及与线性表的异同；熟悉顺序栈和链栈的组织方法，队满、队空的判断条件及其描述；掌握链队的组织方法、算法并能自行设计其它简单算法本章重点：栈和队列的特点；顺序栈和链栈上基本运算的实现和简单算法；链队上基本运算的实现和简单算法设计难点：循环队的组织，队满、队空的条件及算法设计第 4 章 树(一) 课程内容4.1 树的基本概念4.2 二叉树4.3 二叉树的存储结构4.4 二叉树的遍历4.5 树和森林4.6 判定树和哈弗曼树(二) 学习的目的与要求树形结构是有广泛英语背景的分支、层次结构二叉树是一种运算简单且能间接表达一般树形结构的重要的数据结构因此，二叉树是本课程的一个重点内容本章总的要求是：理解树形结构的基本概念和术语；深刻领会二叉树的定义和存储结构，熟悉二叉树的遍历次序并熟练掌握遍历算法；了解树和森林的定义、树的存储结构并掌握树、森林、二叉树之间的相互转换方法。

本章重点：树形结构的概念；二叉树的定义、存储结构和遍历算法难点：二叉树的遍历算法第 5 章 图(一) 课程内容5.1 图的基本概念5.2 图的存储结构5.3 图的遍历5.4 最小生成树5.5 拓扑排序(二) 学习的目的与要求图与树一样，也是一种有广泛实际背景的非线性结构，但比树更复杂因此，本章在运算实现方面着重研究图的遍历这一常用运算的实现，以及最小生成树和拓扑排序这两个典型的应用问题的求解本章总的要求是：理解图的概念并熟悉有关术语；熟练掌握邻接矩阵表示法和邻接表表示法；深刻理解连通图遍历的基本思想和算法；理解最小生成树的有关概念和算法；理解拓扑排序的概念、步骤和背景本章重点：图的存储结构和连通图的遍历难点：Prim 算法第 6 章 查找表(一) 课程内容6.1 基本概念6.2 静态查找表的实现6.3 树表6.4 散列表查找(二) 学习的目的与要求数据结构课程中的集合是四类基本逻辑结构之一查找表是一种以集合为逻辑结构的常见的数据结构，其基本特点是以查找运算为核心因此，如何高效率地实现查找运算是本章的核心问题本章总的要求是：了解集合的基本概念；理解查找表的定义、分类和各类的特点；掌握顺序查找和二分查找的思想和算法；理解二叉排序树的概念和有关运算的实现方法；掌握散列表、散列函数的构造方法、以及处理冲突的方法；掌握散列存储和散列查找的基本思想及有关方法、算法。

本章重点：二分查找；二叉排序树的查找；散列表的查找难点：二叉排序树的插入算法第 7 章 文件(一) 课程内容7.1 基本概念7.2 顺序文件7.3 索引文件7.4 ISAM 文件7.5 VSAM 文件7.6 多关键子文件(二) 学习的目的与要求本章专门讨论外部存储器中数据的数据结构、存储结构、运算及其实现方法由于文件放在外存中，数据的组织方式和操作方式有其特殊的问题本章总的要求是：熟悉文件的基本概念，熟悉顺序文件、索引文件和散列文件的组织方式和操作方式第 8 章 排序(一) 课程内容8.1 概述8.2 插入排序8.3 交换排序8.4 选择排序8.5 归并排序8.6 外排简介(二) 学习的目的与要求在很多实际问题中，排序是一种常用运算，而且对这种运算的时、空性能有较高的要求，由此而发展出各种巧妙的排序方法和技术本章总的要求是：深刻理解各类内部排序方法的知道思想和特点；熟悉各种内部排序算法并理解其基本思想；了解各种内部排序算法的优缺点、时空性能和适用场合本章重点：快速排序、堆排序难点：堆排序。