自考02331数据结构大纲.docx

《自考02331数据结构大纲.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章概论1.数据结构的作用、意义、基本概念和术语，要求达到“识记”层次。1.1数据结构所研究的内容；在计算机科学中的作用和意义；Wirth关于程序的定义公式。1.2数据、数据元素、数据对象、数据项、数据结构等概念的定义。1.3数据的逻辑结构、存储结构及数据运算的含义及其相互关系。1.4数据结构的两大类逻辑结构和四种常用的存储表示方法。2.算法的描述和分析，要求达到“领会”层次。2.1算法、算法的时间复杂度和空间复杂度等概念。2.2一个完整算法需要满足的五个准则；算法与程序的关系。2.3算法的分析方法；对于一般算法能分析其时间复杂度。第2章线性表1.线性表的逻辑结构，要求达到

2、“识记”层次。1.1线性表的逻辑定义和性质。1.2线性表上定义的基本运算。2.线性表的顺序存储结构和基本运算，要求达到“领会”层次。2.1顺序表的定义及特点。2.2顺序表上进行插入和删除操作的实现及时间性能分析。2.3理解求顺序表逆置和极值及定位两种算法的实现过程。3.线性表链式存储结构的不同形式及基本运算，要求达到“领会”层次。3.1单链表、循环链表、双向链表的定义及特点。3.2单链表上实现建表、查找、插入和删除等基本算法，并分析其时间复杂度。3.3用尾指针表示单循环链表的意义。3.4双向链表上的插入和删除操作。4.利用顺序表和链表设计算法解决应用问题，要求达到“综合应用”

3、层次。5.顺序表和链表的比较，要求达到“领会”层次。第3章栈和队列1.栈的逻辑结构、存储结构及相关算法，要求达到“简单应用”层次。1.1栈的逻辑定义、特点及运算。1.2顺序栈和链栈上实现进栈、退栈等基本运算。1.3顺序栈的上溢和下溢问题，如何防止溢出。1.队列的逻辑结构、存储结构及相关算法，要求达到“简单应用”层次。1.1队列的逻辑定义、特点及运算。1.2顺序循环队列的表述；队空和队满的判定；顺序循环队列上入队、出队等基本算法。1.3链队列的表述；带头结点和不带头结点两种情况下链队列上的基本算法。2.栈和队列的应用，要求达到“综合应用”层次。2.1圆括号匹配的检验问题。2.2

4、字符串回文的判断问题。2.3数制转换。2.4利用栈实现程序的递归。2.5表达式求值。第1章多维数组和广义表1.多维数组及其运算，要求达到“领会”层次。1.1多维数组的逻辑结构表达及特征。1.2多维数组的顺序存储结构及地址计算方法。1.3多维数组的常用运算。2.矩阵的压缩存储，要求达到“简单应用”层次。2.1特殊矩阵的类型和性质；稀疏矩阵的概念。2.2用一维数组压缩存储特殊矩阵时，存储地址的计算。2.3稀疏矩阵的三元组表表示方法及常用算法。3.广义表，要求达到“领会”层次。3.1广义表的定义及特性。3.2求广义表的深度、表长、表头和表尾运算。第2章树和二叉树1.树的概念，要求达

5、到“识记”层次。1.1树的定义和表示方法。1.2树的常用术语及其含义。2.二叉树的概念，要求达到“领会”层次。2.1二叉树的递归定义。2.2二叉树的性质及其证明，两种特殊形式的二叉树。2.3二叉树的顺序存储和链式存储结构。1.二叉树的运算，要求达到“综合应用”层次。1.1二叉链表的生成。1.2二叉树的递归遍历算法和非递归遍历算法。1.3二叉树的应用。2.线索二叉树，要求达到“简单应用”层次。2.1二叉树线索化的含义、线索二叉树结点的表示方法。2.2对给定二叉树进行线索化的思想和实现。2.3二叉线索链表上的运算：查找某结点的后继结点和线索二叉树的遍历。3.树和森林，要求达到“领

6、会”层次。3.1树的三种存储结构表示方法。3.2树、森林和二叉树之间的相互转换。3.3树和森林的遍历。4.哈夫曼树及其应用，要求达到“简单应用”层次。4.1最优二叉树的概念，哈夫曼算法的思想。4.2哈夫曼算法的实现。4.3编码、前缀编码、哈夫曼编码的概念；根据最优二叉树构造对应的哈夫曼编码。第1章图1.图的概念，要求达到“识记”层次。1.1图的定义和表示方法。1.2图的常用术语及其含义。2.图的存储结构，要求达到“领会”层次。2.1图的邻接矩阵表示法。2.2图的邻接表表示法。3.图的遍历算法，要求达到“简单应用”层次。3.1深度优先搜索遍历的算法思想，以邻接矩阵和邻接表分表作

7、为图的存储结构，其深度优先搜索遍历的算法实现及其时间复杂度。3.2广度优先搜索遍历的算法思想，以邻接矩阵和邻接表分别作为图的存储结构，其广度优先搜索遍历的算法实现及其时间复杂度。3.3深度优先搜索遍历算法中递归的应用和广度优先搜索遍历算法中队列的应用。3.4两种遍历算法的简单应用。1.图的生成树和最小生成树，要求达到“领会”层次。1.1生成树的概念。1.2对遍历给定的图，求其深度优先和广度优先生成树。1.3最小生成树的概念及其性质。1.4Prim算法和Kruskal算法的基本思想及其实现。2.最短路径，