数据结构期末复习提纲

《数据结构期末复习提纲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构期末复习提纲（2012级）A、总体要求：1、掌握数据结构的基本概念、基本原理和基本方法。2、掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度和空间复杂度的分析。3、能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C语言和C++语言设计与实现算法的能力。一、基本概念1、数据结构、数据元素、数据项、数据类型、抽象数据类型、算法、算法的时间复杂度、算法的空间复杂度、算法的评价标准。2、数据结构的逻辑结构和存储结构及分类。3、线性表的定义及特点。4、顺序表、单链表、双向链表、循环链表的存储结构。5、栈和队列的定义及特点。6、顺序

2、栈、链栈、顺序队列、链队列的存储结构。7、字符串的定义及特点。8、顺序串和链串的存储结构。9、数组的定义及特点。10、数组的按行存储与按列存储。11、对称矩阵、三角矩阵的压缩存储。12、二叉树的定义、一般术语及特点。13、二叉树的五个基本性质。14、完全二叉树与满二叉树的概念。15、二叉树的顺序存储结构。16、二叉树的二叉链表与三叉链表存储结构。17、二叉树的四种遍历方式及特点。18、线索二叉树的存储结构及特点。19、树和森林的概念。20、树的双亲链表和孩子兄弟链表存储结构。21、树和森林的二种遍历方式。22、图的定义、一般术语及特点。23、图的邻接矩阵、邻接表、逆邻接

3、表存储结构。24、图的二种遍历方式及特点、优先遍历生成树的概念。25、图的连通性、连通图、连通分量的概念。26、有向无环图的概念及特点。27、查找、查找表、关键字的概念。28、顺序查找、折半查找的概念。29、二叉排序树和平衡二叉树的定义及特点，平衡因子的概念。30、B_树的定义及存储结构特点。31、哈希函数、哈希表、哈希冲突、哈希查找的概念。32、哈希表装填因子的定义及作用。33、内部排序、外部排序、排序方法、排序方法的稳定性概念。34、希尔排序、快速排序、堆排序、归并排序、基数排序的概念。１０二、数据结构的基本操作算法1、顺序表与单链表的创建、查找、插入、删除、遍历操

4、作算法。2、顺序栈的创建、初始化、取栈顶元素、出栈、入栈操作算法。3、顺序队列和循环队列的创建、初始化、取队头元素、出队、入队操作算法。4、二叉树的先序、中序、后序遍历的递归算法。5、中序线索二叉树的创建和遍历操作算法。6、树和森林的孩子兄弟链表结构的先序和后序遍历操作算法。7、图的邻接矩阵和邻接表结构的创建操作算法。8、图的深度优先和广度优先遍历算法。9、有序顺序表的折半查找算法。10、二叉排序树的创建、查找、插入、删除算法。11、传统的插入、选择、交换排序算法。12、一趟快速排序、归并排序的算法。三、基本方法1、简单程序的算法时间复杂度和空间复杂度的分析。2、比较顺

5、序表与链表、单链表、双向链表、循环链表的应用特点。3、顺序栈的简单应用。4、循环队列和双端队列的特点及简单应用。5、二维、三维数组的按行、按列展开的地址计算及转换。6、二叉树基本性质的应用及简单计算。7、已知二叉树的遍历，求二叉树的形态。8、已知二叉树，画出线索二叉树。9、森林与二叉树的转换方法。10、哈夫曼树的构造和编码方法。11、图的邻接矩阵和邻接表结构及逆邻接表结构的转换方法。12、连通分量、强连通分量的求解方法。13、深度优先和广度优先遍历最小生成树的求解方法。14、最小生成树的求解方法。15、应用栈或队列的拓扑排序的求解方法。16、关键路径的求解方法。17、平

6、衡二叉树的构造方法、平衡因子的计算。18、线性探测再散列和链地址法解决冲突的哈希表构造方法，并计算平均查找长度。19、B_树的构造和查找方法。20、希尔排序、快速排序、堆排序、归并排序、基数排序的方法。21、排序方法的时间性能、空间性能及稳定性的比较。四、算法应用设计1、有序顺序表应用，如：合并、查找、排序、消除重复元素等。2、链表应用，如：链表的合并、排序、查找、删除等。3、二叉链表二叉树的遍历应用，如：查找、求高度和宽度等。4、三叉链表的二叉树的非递归遍历算法。5、图的邻接矩阵和邻接表结构及逆邻接表结构的转换算法。6、图的深度优先和广度优先遍历的应用算法，如：查找、

7、求解通路和最短路径等。１０7、有向无环图的拓扑排序的应用算法。8、习题集算法例题举例：2.15、2.20、2.29、2.37、6.39、6.41、6.44、6.48、6.52、7.22、7.27、7.34、7.35B、试题举例：数据结构试题（2011级）一、单选题（每小题2分）1．抽象数据类型ADT的三个组成部分是A．数据对象、数据关系和基本操作B．数据元素、逻辑结构和存储结构C．数据项、数据元素和数据类型D．数据元素、数据结构和数据类型2.在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是A.对顺序表中元素进行排序B.插入第i个元