《数据结构(本科)课程期末复习》由会员分享，可在线阅读，更多相关《数据结构(本科)课程期末复习（10页珍藏版）》请在金锄头文库上搜索。
1、数据结构数据结构( (本科本科) )课程期末复习课程期末复习精品文档！欢迎下载大家下载阅读！数据结构（本科）课程期末复习-根据直播复习课堂整理徐孝凯： 同学们好！这一讲是数据结构课程的第四次直播，也是最后一次直播，这一讲专题讨论该课程复习考试的有关问题。殷老师，数据结构课程内容丰富、实用，而学时数又相对较少，要想在这有限的时间内，学习好并掌握好教材中的全部内容是很困难的，这是同学们和各地电大的辅导老师们的普遍反映。现在面临期末复习考试，同学们都很着急，该课程内容很多，要考什么，如何复习，他们心里没有底，都希望你能够在这次直播课堂上，对复习考试的内容提出明确和具体的要求，使同学们既能够在复习中掌
2、握好这门课程的基本概念和基本知识，又能够在期末考试中取得较好的成绩。殷老师，下面请你给同学们介绍一下每一章的具体复习要求和要掌握的具体内容。殷老师：总复习* 本学期各章考核的要点* 考核的示例第二章 数组* 二维数组定义、给定下标后计算数组元素实际存放地址* 顺序表的插入与删除算法* 在顺序表中插入及删除时计算平均移动元素个数* 对称矩阵按上三角或下三角压缩存储时的地址转换公式第三章 链接表* 单链表(带表头结点和不带表头结点)的插入与删除算法* 双向循环链表(带表头结点)的插入与删除算法* 单链表的递归算法* 搜索含 x 结点* 删除 x 结点* 统计单链表中结点个数第四章 栈与队列* 栈、
3、队列与优先队列的定义顺序存取 (LIFO, FIFO, 按优先级)* 用循环队列实现双端队列(两端都可插入删除)的插入与删除算法* 用单链表表示栈或队列时栈顶指针或队头、队尾指针初始时指向何处* 用堆表示优先级队列时的插入与删除算法第五章 递归与广义表* 递归与递归过程的定义* 用迭代改尾递归算法为非递归算法* 用递归工作栈改递归算法为非递归算法* 广义表的定义与性质空表 线性表 纯表共享表 递归表第六章 树* 二叉树的几个性质* 二叉树各层最大结点数 2i ( i=0,1,.* 二叉树高度为 h 时的最大结点数 n* 完全二叉树有 n 个结点时的高度 h* 完全二叉树顺序存储时结点 i 的双
4、亲结点、子女结点、兄弟结点的位置 ( 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 n-1* n 个顶点的有向图或强连通图中最多边数和最少边数 n(n-1) n 或 0* 图的邻接矩阵中矩阵元素的个数与图中顶点个数的关系矩阵元
6、素个数只与顶点个数有关矩阵中非零元素个数与边数有关* 对图进行深度优先搜索的递归算法* 求重连通图的关节点的方法 (不要算法)* 拓扑排序的算法* 能够给出执行拓扑排序实例的过程中栈的变化第九章 排序* 直接插入排序、折半插入排序、起泡排序、快速排序、简单选择排序、堆排序、锦标赛排序、归并排序* 排序过程执行实例* 关键码比较次数* 对象移动次数* 稳定性各种排序方法的比较 当待排序的关键码序列已经基本有序时，用直接插入排序最快，快速排序显著变慢。 当在 n 个数据（n 很大）中选出最小的 5 ? 8 个数据时，锦标赛排序最快，堆排序其次。 锦标赛排序算法将待排序数据个数 n 补足到 2 的
7、k 次幂2k-1 在堆排序中将待排序的数据组织成完全二叉树的顺序存储。 归并排序对待排序关键码的初始排列不敏感，故排序速度较稳定。 外排序：* 多路平衡归并排序的过程* 多路平衡归并排序的时间分析* 最佳归并树的构造及 WPL 计算第十章 索引与散列* B_树的定义、平衡 m 路搜索树与 m 阶 B_树关系* 有 n 个关键码的 m 阶 B_树的最大高度和最小高度* 最大高度为 ?log?m/2?(n+1)/2)? + 1* 最小层数为 ?logm(n + 1)? (包括失败结点所在层次)* B_树的插入 (包括结点分裂)、删除 (包括结点调整与合并)方法* 散列表中散列函数的设计原则及除留余
8、数法的设计 (注意除数的选择)* 解决地址冲突的线性探查法的运用，平均探查次数计算* 线性探查法的删除问题、散列表中必须为各地址设置的三个状态（ Active, Empty, Deleted )* 解决地址冲突的双散列法的运用，平均探查次数的计算* 双散列法中再散列函数的设计：要求 计算结果与表长 m 互质 (m 设计为质数)* 解决地址冲突的二次散列法的运用，平均探查次数计算* 二次散列法中装填因子 ? 与表长 m 的设置： ? 不大于 0.5, m为满足 4 j + 3 的质数* 装填因子 ? 与平均搜索长度的关系（记住表中的公式）徐孝凯：殷老师，你刚才把每一章的具体复习内容和要求都给同学
9、们作了详细的介绍，我想同学们就能够有针对性地做好复习了。殷老师，在该课程的考试题型中，有选择题，就是从多个答案中选择一个正确的结果，或者判断一个叙述的正误；有算法理解题，就是指出已知算法的功能；有简答题，就是考查数据结构的一些基本知识；有综合算法题，就是根据所给问题设计出算法；有算法填空题，就是分析一个算法，把缺少的语句补上。殷老师，请你就重点和难点的题，给同学们做一些典型的分析和解答，使同学们体会一下解题的思路，对复习考试将会有所帮助。殷老师：例 1 求散列表大小并设计散列函数* 设有一个含 200 个表项的散列表，用二次探查法解决冲突，按关键码查询时找到一个新表项插入位置的平均探查次数不超
10、过 1.5，则散列表项应能够至少容纳多少个表项。再设计散列函数（设搜索不成功的平均搜索长度为 Un1 / (1 -), 其中 为装填因子）* 解答：设表中表项个数 n = 200，搜索不成功的平均搜索长度Un1 / (1 -) ? 1.5 = ? ? 1/3 ? n/m = 200/m = ? ? 1/3m ? 600 又 二次散列要求 m 必须是满足 4j+3 的质数，故 m 可以取 601* 散列函数 hash( key ) = key % m例 2 计数排序（count Sorting）* 有一个用数组表示的待排序的表。* 算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录
11、的关键码比该记录的关键码小。* 假设针对某一个记录，统计出的计数值为 c，那么，这个记录在新的有序表中的合适的存放位置即为 c。* 排序结果存放到另一个新的表中。* 表中所有待排序的关键码互不相同。* 适用于计数排序的数据表定义const int DefaultSize = 100;template class datalisttemplate class Element private:Type key; /关键码field otherdata; /其它数据成员public:Type getKey ( ) return key; void setKey ( const Type x ) ke
12、y = x; template class datalist public:datalist ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) Vector = new Element MaxSz; private:Element * Vector;int MaxSize, CurrentSize; template void countsort ( datalist int *c = new intinitList.CurrentSize;/ c 是存放计数的临时表for ( i = 0; i void BinT
13、ree : unknown ( BinTreeNode * t ) BinTreeNode *p = t, *temp;if ( p != NULL ) temp = pleftChild; pleftChild = prightChild;prightChild = temp;unknown ( pleftChild );unknown (prightChild);* 指出该算法完成了什么功能。* 试写一个算法，不用栈将以上算法中的第二个递归语句消去。精品文档！欢迎下载大家下载阅读！* 试再写一个算法，用栈将以上算法中的第一个递归语句也消去。void BinTree : unknown (
14、BinTreeNode * t ) BinTreeNode *p = t, *temp;while ( p != NULL ) temp = pleftChild; pleftChild = prightChild;prightChild = temp;unknown ( pleftChild );p = prightChild;* 使用栈消去递归算法中的两个递归语句：temp = pleftChild; pleftChild = prightChild;prightChild = temp;if ( prightChild != NULL )S.push ( prightChild );if ( pleftChild != NULL )S.push ( pleftChild ); 徐孝凯：殷老师，由于时间关系，这一堂课就上到这里。同学们看了这堂课后，将对复习和考试大有帮助。希望同学们能够按照殷老师这堂课所讲的要求，认真地做好复习，真正把数据结构课程的基本知识学到手，争取在期末考试中取得较好的成绩，同时也为学习后序课程打下基础。好！同学们再见！11精品文档！欢迎下载大家下载阅读！
