文档介绍：Add the author and the accompanying title
计算机二级公共基础知识
全国计算机等级考试
二级公共基础知识
此文档后面有赠送常用PPT图标,方便大家修订排版编辑
第一章数据结构与
删除运算是指撤销结构中的某个结点，
一般情况,要删除第i 1≤i≤n 个元素,要从第i+1个元素开始,直到第n个元素,共n-i个元素依次向前移动一个位置，
栈
栈是限定仅在表的一端进行插入和删除操作的线性表，允许插入和删除的一端称为栈顶,另一端称为栈底，
栈顶元素总是最后被插入的元素,从而也是最先被删除的元素；栈底元素总是最先被插入,也是最后被删除的元素，因此,栈是一种后进先出的线性表，
通常用指针top指示栈顶位置,用指针bottom指示栈底位置，
栈的顺序存储及运算
用一维数组S 1:m 作为栈的顺序存储空间,m为栈的最大容量，top=0表示栈为空,top=m表示栈满，
栈的操作
入栈：在栈顶位置插入一个新元素,栈顶指针top加1，
退栈：取出栈顶元素并赋值给一个指定的变量,栈顶指针top减1，
取栈顶元素：将栈顶元素的值赋给一个指定的变量,不删除栈顶元素,栈顶指针不变，
队列
队列是一种先进先出的线性表,它只允许在表的一端插入元素队尾 ,在另一端删除元素队头，通常定义头指针front指向队头元素的前一个位置,定义尾指针rear指向队尾元素的位置，
队列是一种先进先出的数据结构，
向队尾插入一个元素的操作称为入队,从队头删除一个元素的操作称为退队，
循环队列
将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间，
循环队列初始状态为空,即front=rear=m，
入队操作时,rear加1,若rear=m+1,则置rear=1；
退队操作时,front加1,若front=m+1,则置front=1，
在循环队列为空或为满时,均有front=rear,因此需要设置标志s进行区分,定义s=0表示队列为空,s=1表示队列非空，
单链表
线性表的链式存储结构的特点是用一组任意的存储单元可以连续,也可以不连续存储线性表的数据元素,为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系,对数据元素ai来说,除了存储其本身的信息数据域之外,还需要存储其后继元素的存储位置信息指针域，
指针域中存储的信息称为指针或链,N个结点链接成一个链表,即为线性表的链式存储结构，由于结点中只包含一个指针域,故称为单链表，
单链表
通常以单链表中第一个数据元素的存储地址作为作为单链表的地址,称为头指针，整个链表的存储必须从头指针开始顺序存取 ,头指针指示链表中第一个结点的存储位置，最后一个数据元素没有直接后继,其指针域为空，
单链表的插入和删除
双向链表和循环链表
在双向链表中的结点包含两个指针域,其中一个指向直接后继,另一个指向直接前驱，
循环链表的特点是表中最后一个结点的指针域指向第一个结点,整个链表成为一个由链指针相链接的环，据此,从表中任一节点出发均可找到表中其它结点，在循环链表中增加了一个表头结点,其指针域指向第一个元素结点,头指针则指向头结点，
HEAD
…
∧
…
∧
HEAD
…
HEAD
树及其基本概念
树是一种简单的非线性结构,在树中,所有的数据元素之间具有明显的层次性关系，
树是 n≥0 个结点的有限集合,在任意一棵非空树中：
1 有且仅有一个特定的结点称为根结点，
2 当n>1时,其余的结点可分为m个互不相交的子集T1,T2,…Tm,其中每个有限子集本身又是一棵树,并且称为根的子树，
集合为空的树简称为空树；树中的元素称为结点，
树的主要术语
结点的度：结点拥有的子树数，
叶节点终端结点：度为0的结点，
双亲、孩子和兄弟：结点的子树的根节点称为该结点的孩子,该结点称为孩子结点的双亲结点，同一个双亲结点的孩子互称为兄弟，
层次：结点的层次从根开始定义,根为第一层,根的孩子为第二层，
深度：树中结点的最大层次称为树的深度或高度，
树型结构的常用术语
A
B
D
F
E
C
G
H
I
J
K
M
结点的度一个结点的子树的个数； Q：结点A、G的度数
树的度树中所有结点度的最大值；Q：右图中树的度
终端结点度为0的结点；
Q：图中叶子结点有几个 7
非终端结点度不为0的结点；
Q：图中非终端结点有几个 5
树型结构的常用术语
A
B
D
F
E
C
G
H
I
J
K
M
结点的层次树中根结点的层次为1,根结点子树的根为第2层,以此类推；
树的深度树中所