微固讲师团二级c公共基础知识.ppt

公共基础知识 电科三班 刘扬 数据结构与算法 软件工程基础 数据库设计基础 程序设计基础 数据结构与算法 重点：栈，队列，二叉树，排序与查找 难点：主要集中在二叉树，考核形式包括给出前序，中序遍历，求后序遍历等问题，满二叉树和完全二叉树的结点问题 栈限定在一端进行插入与删除的线性表； 其允许插入与删除的一端称为栈顶； 不允许插入与删除的另一端称为栈底； 栈按照“先进后出”或“后进先出”组织数据。 栈的存储方式有顺序存储和链式存储 栈的基本运算： (1) 入栈运算 (2) 退栈运算，删除元素 (3) 读栈顶元素  栈顶 栈的输入序列为1,2,3......，n-1，n，输出序列的第一个元素为n，则第i个元素为 ________ A.n-i+1 B.n-1 C.i D.那个元素都无所谓 A 假设用一个长度为50的数组（数组元素的下标从0到49）作为栈的存储空间，栈底指针bottom指向栈底元素，栈顶指针top执向栈顶元素，如果bottom=49，top=30（数组下标），则栈具有____________个元素（2009.3） 元素个数为栈底元素下标—栈顶元素下标+1 20 队列指允许在一端（队尾）进入插入； 而在另一端（队头）进行删除的线性表；队列是“先进先出”或“后进后出”的线性表。队列运算包括：(1) 入队运算 (2) 退队运算计算循环队列的元素个数：“尾指针减头指针”， 若为负数，再加其容量即可 某循环队列的容量为50，头指针front=5（指向队头元素的前一位置），尾指针rear=29（指向队尾元素），则该循环队列中共有_____个元素。（2008.4） 当frontrear时，循环队列中元素的个数为rear-front，当frontrear时，循环队列 中元素的个数为（N-front+rear），其中N为循环队列的容量 24 （根）节点，子树 叶子：没有后继节点（或终端节点） 分支节点：非叶子节点（或非终端节点） 树的度：树中各节点的度的最大值 节点的层次：根节点的层次为一，其他任何层数等于它的父节点的层数加一 树的深度：节点的最大层次值 二叉树的特点：(1) 非空二叉树只有一个根结点；(2) 每一个结点最多有两棵子树， 且分别称为该结点的左子树与右子树。 满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点,深度为m的满二叉树有2m-1个结点。 完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。 二叉树的性质 1.在二叉树的第k层上，最多有2k-1(k≥1)个结点2.深度为m的二叉树最多有2m-1个结点；3.度为0的结点（即叶子结点）总是比度为2的结 点多一个，即： n0=n2+14.具有n个结点的二叉树，其深度至少为[log2n]+1, 其中[log2n]表示取log2n的整数部分，具有n个结 点的完全二叉树的深度为[log2n]+1 深度为5的满二叉树有_____个叶子结点 具有88个节点的二叉树，其深度至少为____ 某二叉树有5个度为2的结点，则该二叉树中叶子结点的个数为______ 对于一个非空的二叉树，叶子结点个数＝度为2的结点个数+1 6 二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。二叉树的遍历：（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树；（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树；（3）后序遍历（LRD）首先遍历左子树，然 后访问遍历右子树，最后访问根结点。 根左右 左根右 左右根 如图，二叉树进行前序遍历的结果为______(2006.4) ABDYECFXZ void preorder(bnode *BT ) { if(BT=NULL) return; else {visit(BT)； if(BT-LC!=NULL)preorder(BT-LC); if(BT-RC!=NULL)preorder(BT-RC);} } 查找技术 二分法查找：设有序线性表的长度为n，被查找的元素为x，则二分法查找的方法如下： （1）将x与线性表的中间项比较 （2）若x的值与中间项的值相等，则说明查到，查找结束 （3）若x小于中间项的值，则在线性表的前半部分以相同的方法查找 （4）若x大于中间项的值，则在线性表的后半部分以相同的方法查找 顺序查找：从表中的的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符查到所要找的元素为止。负责就是表中没有要找的元素，查找不成功。 二