计算机二级Office高级应用知识点文档.doc

计算机二级Office高级应用知识点,文档
计算机二级Office高级应用知识点,文档
计算机二级Office高级应用知识点,文档
计算机二级Office高级应用知识点：数据构造与算法
。
所谓循环队列，就是将队列存储空间的最后一个地点绕到第一个地点，形成逻辑上的环状空间。
入队运算是指在循环队列的队尾加入一个新元素。
当循环队列非空(s=1)且队尾指针等于队头指针时，说明循环队列已满，不能进行人队运算，这种情况称为“上溢”。
计算机二级Office高级应用知识点,文档
计算机二级Office高级应用知识点,文档
计算机二级Office高级应用知识点,文档
退队运算是指在循环队列的队头地点退出一个元素并赋给指定的变量。首先将队头指针进一，然后将排头指针指向的元素赋给指定的变量。当循环队列为空(s=0)时，不能进行退队运算，这种情况称为“下溢”。

在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表或线性链表。
在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域;另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点(即前件或后件)。


树是简单的非线性构造，树中有且仅有一个没有前驱的节点称为“根”，其余节点分成m个互不相交的有限会集T1，T2，，T}mm，每个集
合又是一棵树，称T1，T2，，T}mm为根结点的子树。
?父节点：每一个节点只有一个前件，无前件的节点只有一个，称为树的根结点(简称树的根)。
?子节点：每～个节点可以后多个后件，无后件的节点称为叶子节点。
计算机二级Office高级应用知识点,文档
计算机二级Office高级应用知识点,文档
计算机二级Office高级应用知识点,文档
?树的度：所有节点最大的度。
计算机二级Office高级应用知识点,文档
计算机二级Office高级应用知识点,文档
计算机二级Office高级应用知识点,文档
?树的深度：树的最大层次。

(1)二叉树的定义：二叉树是一种非线性构造，是有限的节点会集，该会集为空(空二叉树)或由一个根节点及两棵互不相交的左右二叉子树组成。
可分为满二叉树和完全二叉树，其中满二叉树一定是完全二叉树，但完
全二叉树不一定是满二叉树。二叉树拥有如下两个特点：
?二叉树可为空，空的二叉树无节点，非空二叉树有且只有一个根结点;
?每个节点最多可有两棵子树，称为左子树和右子树。
(2)二叉树的基本性质。
性质1：在二叉树的第k层上至多有2k-1个结点(k≥1)。
性质2：深度为m的二叉树至多有2m-1个结点。
性质3：对任何一棵二叉树，度为0的结点(即叶子结点)老是比度为2
的结点多一个。
性质4：拥有n个结点的完全二叉树的深度最少为[log2n]+1，其中[log2n]
表示log2n的整数部分。
计算机二级Office高级应用知识点,文档
计算机二级Office高级应用知识点,文档
计算机二级Office高级应用知识点,文档

计算机二级Office高级应用知识点,文档
计算机二级Office高级应用知识点,文档
计算机二级Office高级应用知识点,文档
(1)满二叉树：满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点。满二叉树在其第i层上有2i-1个结点。
从上面满二叉树定义可知，二叉树的每一层上的结点数必须都达到最大，否则就不是满二叉树。深度为m的满二叉树有2m-1个结点。
(2)完全二叉树：完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。
如果—棵拥有n个结点的深度为k的二叉树，它的每—个结点都与深度为k的满二叉树中编号为1～n的结点——对应。

二叉树平时采用链式存储构造，存储节