数据结构(本科)课程期末复习

《数据结构(本科)课程期末复习》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构(本科)课程期末复习个人总结，仅供交流个人总结数据结构（本科）课程期末复习----根据直播复习课堂整理徐孝凯：同学们好！这一讲是数据结构课程的第四次直播，也是最后一次直播，这一讲专题讨论该课程复习考试的有关问题。殷老师，数据结构课程内容丰富、实用，而学时数又相对较少，要想在这有限的时间内，学习好并掌握好教材中的全部内容是很困难的，这是同学们和各地电大的辅导老师们的普遍反映。现在面临期末复习考试，同学们都很着急，该课程内容很多，要考什么，如何复习，他们心里没有底，都希望你能够在这次直播课堂上，对复习考试的内容提出明确和具体的要求，使同学们既

2、能够在复习中掌握好这门课程的基本概念和基本知识，又能够在期末考试中取得较好的成绩。殷老师，下面请你给同学们介绍一下每一章的具体复习要求和要掌握的具体内容。殷老师：总复习*本学期各章考核的要点*考核的示例第二章数组*二维数组定义、给定下标后计算数组元素实际存放地址*顺序表的插入与删除算法*在顺序表中插入及删除时计算平均移动元素个数*对称矩阵按上三角或下三角压缩存储时的地址转换公式第三章链接表*单链表(带表头结点和不带表头结点)的插入与删除算法*双向循环链表(带表头结点)的插入与删除算法*单链表的递归算法*搜索含x结点*删除x结点*统计单链表中结点个

3、数第四章栈与队列*栈、队列与优先队列的定义顺序存取(LIFO,FIFO,按优先级)*用循环队列实现双端队列(两端都可插入删除)的插入与删除算法*用单链表表示栈或队列时栈顶指针或队头、队尾指针初始时指向何处*用堆表示优先级队列时的插入与删除算法第五章递归与广义表*递归与递归过程的定义*用迭代改尾递归算法为非递归算法*用递归工作栈改递归算法为非递归算法*广义表的定义与性质空表线性表纯表共享表递归表第六章树*二叉树的几个性质*二叉树各层最大结点数2i(i=0,1,...*二叉树高度为h时的最大结点数n*完全二叉树有n个结点时的高度h*完全二叉树顺序存储

4、时结点i的双亲结点、子女结点、兄弟结点的位置(i=0,1,...或i=1,2,...)*有n个结点的不同二叉树与二叉搜索树的棵数*二叉树的前序、中序和后序遍历的递归算法*二叉树的递归算法*求二叉树高度*求二叉树叶结点个数*交换二叉树根结点的左右子树*自左向右链接二叉树的叶结点?利用二叉树的前序和中序序列及利用中序和后序序列构造二叉树?满k叉树的各层最大结点个数、求结点i的双亲结点、孩子结点、兄弟结点的方法?k叉正则树中度为0的结点与度为k的结点的关系?霍夫曼树的构造方法和霍夫曼编码的构造方法，WPL的计算第七章集合与搜索*顺序搜索与折半搜索*构造

5、判定树（扩充二叉搜索树）*计算搜索成功的平均搜索长度及搜索不成功的平均搜索长度*二叉搜索树*搜索含x的结点的算法*计算搜索成功的平均搜索长度及搜索不成功的平均搜索长度*二叉搜索树的构造方法(不要算法)*高度为h的二叉搜索树中最大结点个数和最少结点个数*AVL树的插入、删除方法及平衡旋转的方法(不要算法)*高度为h的AVL树中最少结点个数*有n个结点的AVL树的最大高度和最小高度?log2(n+1)??h+1<3/2?log2(n+1)第八章图*n个顶点的无向图或连通图中最多边数和最少边数n(n-1)/2-->n-1*n个顶点的有向图或强连通图中最

6、多边数和最少边数n(n-1)-->n或0*图的邻接矩阵中矩阵元素的个数与图中顶点个数的关系矩阵元素个数只与顶点个数有关矩阵中非零元素个数与边数有关*对图进行深度优先搜索的递归算法*求重连通图的关节点的方法(不要算法)*拓扑排序的算法*能够给出执行拓扑排序实例的过程中栈的变化第九章排序*直接插入排序、折半插入排序、起泡排序、快速排序、简单选择排序、堆排序、锦标赛排序、归并排序*排序过程执行实例*关键码比较次数*对象移动次数*稳定性各种排序方法的比较>当待排序的关键码序列已经基本有序时，用直接插入排序最快，快速排序显著变慢。>当在n个数据（n很大）中

7、选出最小的5?8个数据时，锦标赛排序最快，堆排序其次。个人总结，仅供交流>锦标赛排序算法将待排序数据个数n补足到2的k次幂个人总结2k-1在堆排序中将待排序的数据组织成完全二叉树的顺序存储。>归并排序对待排序关键码的初始排列不敏感，故排序速度较稳定。>外排序：*多路平衡归并排序的过程*多路平衡归并排序的时间分析*最佳归并树的构造及WPL计算第十章索引与散列*B_树的定义、平衡m路搜索树与m阶B_树关系*有n个关键码的m阶B_树的最大高度和最小高度*最大高度为?log?m/2?((n+1)/2)?+1*最小层数为?logm(n+1)?(

8、包括失败结点所在层次)*B_树的插入(包括结点分裂)、删除(包括结点调整与合并)方法*散列表中散列函数的设计原则及除留余数法的设计(注意