表示栈底。
第3页，共 26 页
2．栈的顺序存储及其运算
栈的基本运算有三种：.入栈运算、退栈运算和.读栈顶元素。
4.2 队列及其基本运算 1．什么是队列
队列是允许在一端进行插入、 而在另一端进行删除的特殊的线性表。允许插入的一端称为队尾， 允许删除的
一端称为排头(或队头)。
队列又称为\先进先出\或\后进后出\的线性表，它体现了\先来先服务\的原则。 往队列的队尾插入一个元素称为入队运算，从队列的排头删除一个元素称为退队运算。 2．循环队列及其运算
所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环 使用。
队列空和队列满的条件如下： 队列空的条件为 s=0 ;
队列满的条件为 s=1 且 front=rear.
循环队列主要有两种基本运算：入队运算和退队运算。
a.入队运算：在循环队列的队尾加入一个新元素，首先将队尾指针进一(即 rear=rear+1)，并当 rear=m+1 时置 rear=1；然后将新元素插入到队尾指针指向的位置。
注意：当循环队列非空 (s=1)且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算，这种情 况称为\上溢\。
b. 退队运算： 指在循环队列的排头位置退出一个元素并赋给指定的变量。首先将排头指针进一 ( 即 front=front+1)，并当 front=m+1 时置 front=1;然后将排头指针指向的元素赋给指定的变量。 注意：当循环队列为空 (s=0)时，不能进行退队运算，这种情况称为\下溢\。
历届的考题：
1、下列关于栈的描述中错误的是(_______)[2005.4] A）栈是先进后出的线性表 B）栈只能顺序存储 C）栈具有记忆作用 D）对栈的插入与删除操作中，不需要改变栈底指针 2、按照\后进先出\原则组织数据的数据结构是(______)[2006.4] A)队列 B)栈 C)双向链表 D)二叉树
3、列关于栈的描述正确的是(______)[2005.9] A）在栈中只能插入元素而不能删除元素 B）在栈中只能删除元素而不能插入元素
C）栈是特殊的线性表，只能在一端插入或删除元素
D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素
第4页，共 26 页
4、数据结构分为逻辑结构和存储结构，循环队列属于____结构。[2005.9] 5、按“先进后出”原则组织数据的数据结构是_____。[2006.9]
1.5 线性链表
5.1 线性链表的基本概念 1.链式存储
在顺序存储方式中所有的数据元素在内存中是相邻存放的， 从而造成了在插入与删除数据元素时， 需要大量
移动相应的数据元素。 为了解决这种问题， 可以将每个数据元素存储在内存中不相邻的不同位置， 并利用上一个
数据元素在存有数据的同时，也存放下一个数据元素所在的位置地址(称为一个存储单元，即结点)，以便查找。 这就是链式存储方式。
在链式存储方式中， 要求每个结点由两部分组成：一部分用于存放数据元素值， 称为数据域； 另一部分用于
存放地址，称为指针域。其中指针用于指向该结点的前一个或后一个结点 (即前件或后件)。
注意：a、在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的
head
头结点
开始结点
a1 a2
…
终端结点 an ∧
逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
b、 链式存储方式既可以用于表示线性结构， 也可以用于表示非线性结构。 在用链式结构表示较复杂的非线
性结构时，其指针域的个数要多一些。 2．线性链表 线性表的链式存储结构称为线性链表。 如果结点中有两个指针， 一个用于指向前一个结点， 而另一上用于指
向后一个结点，则称之为双向链表。
dhead
头结点
开始结点
a1
a2
…
终端结点
an ∧
3．带链的栈：栈的链式存储结构称为带链的栈。
4．带链的队列：队列的链式存储结构称为带链的队列。 5.2 线性链表的基本运算 ：查找、插入、删除。
历届的考题：
1、下列对于线性链表的描述中正确的是(____)[2005.4]
A）存储空间不一定是连续，且各元素的存储顺序是任意的
B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面 C）存储空间必须连续，且前件元素一定存储在后件元素的前面 D）存储空间必须连续，且各元素的存储顺序是任意的 2、下列叙述中正确的是(_____)[2006.4]
A)线性链表是线性表的链式存储结构 C)双向链表是非线性结构
B)栈与队列是非线性结构
D)只有根结点的二叉树是线性结构
3、数据结构分为线性结构和非线性结构，带链的队列属于____。[2006.9]
1.6 树与二叉树
6.1 树的基本概念
树是一种简单的非线性结构，所有元素之间具有明显的层次特性。
a.在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称 为树的根。 b.在树结构中，一个结点所拥有的后件个数称为该结点的度；在树中，所有结点中的最大的度称为树的度。
c.树具有明显的层次关系，即树是一种层次结构。 d.数的最大层次称为树的深度。
第5页，共 26 页
f.在树中，叶子结点没有子树。
A E B F C G H D I K L J 如左图中， 1、A 为根结点； 2、E、F、J、H、K、L、 M 为叶子结点。 3、树中A、I 都有 3 个子 结点，故树的度为 3。 M 4、 整个树中， 总共分为4 层，故树的深度为 4。 树形表示法 二叉树 6.2 二叉树及其基本性质
1．什么是二叉树：
二叉树是一种很有用的非线性结构。 二叉树具有以下两个特点： a.非空二叉树只有一个根结点；
b.每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
由以上特点可以看出，在二叉树中，每一个结点的度最大为2。 2．二叉树的基本性质：(重要)
a.在二叉树的第 k 层上，最多有 2k-1(k>=1)个结点。
b.深度为 m 的二叉树最多有 2m-1 个结点。深度为 m 的二叉树是指二叉树共有 m 层。 c.在任意一棵二叉树中，度为 0 的结点(即叶子结点)总是比深度为 2 的结点多一个。
d.具有 n 个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示取 log2n 的整数部分。
A、 第四层中，最多有 24-1=23=8 个结点。 B、树的深度为 4，最多有 24-1=16-1=15 个
结点。 C、度为 0 的结点有 8 个， 度为2 的结点有7
个。
3．满二叉树与完全二叉树
满二叉树与完全二叉树是两种特殊形态的二叉树。
a.满二叉树：除最后一层外，每一层上的所有结点都有两个子结点。这就是说，在满二叉树中，每一层上的 结点数都达到最大值，即在满二叉树的第k 层上有 2k-1 个结点，且深度为 m 的满二叉树有 2m-1 个结点。
b.完全二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。 注意：满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。 完全二叉树还具有以下性质：
a.具有 n 个结点的完全二叉树的深度为log2n] +1。 完全二叉树
满二叉树 非满二叉树 6.3 二叉树的存储结构
在计算机中，二叉树通常采用链式存储结构。 6.4 二叉树的遍历：(重要)
在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍
第6页，共 26 页