发布时间 : 星期三 文章全国计算机等级考试二级C语言公共基础知识（附例题）更新完毕开始阅读66f32eb5f121dd36a32d82e7
已经指向存储空间的最后一个位置时，说明栈空间已满，不可能再进行入栈操作。这种情况称为栈\上溢\错误。
（2）退栈运算：退栈是指取出栈顶元素并赋给一个指定的变量。首先将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量，然后将栈顶指针减一（即top减1）。当栈顶指针为0时，说明栈空，不可进行退栈操作。这种情况称为栈的\下溢\错误。
（3）读栈顶元素：读栈顶元素是指将栈顶元素赋给一个指定的变量。这个运算不删除栈顶元素，只是将它赋给一个变量，因此栈顶指针不会改变。当栈顶指针为0时，说明栈空，读不到栈顶元素。
小技巧：栈是按照\先进后出\或\后进先出\的原则组织数据，但是出栈方式有多种选择，在考题中经常考查各种不同的出栈方式。
考点6 线性链表的基本概念 考试链接：
考点6在笔试考试中出现的几率为30%，主要是以选择的形式出现，分值为2分，此考点为识记内容。重点识记结点的组成。
在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域，另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点（即前件或后件）。
链式存储方式既可用于表示线性结构，也可用于表示非线性结构。 （1）线性链表
线性表的链式存储结构称为线性链表。
在某些应用中，对线性链表中的每个结点设置两个指针，一个称为左指针，用以指向其前件结点；另一个称为右指针，用以指向其后件结点。这样的表称为双向链表。
（2）带链的栈
栈也是线性表，也可以采用链式存储结构。带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。
疑难解答：在链式结构中，存储空间位置关系与逻辑关系是什么？
在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
1.4树与二叉树
考点7 树与二叉树及其基本性质 考试链接：
考点7在笔试考试中，是一个必考的内容，在笔试考试中出现的几率为100%，主要是以选择的形式出现，有时也有出现在填空题中，分值为2分，此考点为重点掌握内容。重点识记树及二叉树的性质。 误区警示：
满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。应该注意二者的区别。
1、树的基本概念
树(tree）是一种简单的非线性结构。在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点。每一个结点可以有多个后件，它们称为该结点的子结点。没有后件的结点称为叶子结点。
在树结构中，一个结点所拥有的后件个数称为该结点的度。叶子结点的度为0。在树中，所有结点中的最大的度称为树的度。
2、二叉树及其基本性质 （1）二叉树的定义
二叉树是一种很有用的非线性结构，具有以下两个特点： ①非空二叉树只有一个根结点；
②每一个结点最多有两棵子树，且分别称为该结点的左子树和右子树。 由以上特点可以看出，在二叉树中，每一个结点的度最大为2，即所有子树（左子树或右子树）也均为二叉树，而树结构中的每一个结点的度可以是任意的。另外，二叉树中的每个结点的子树被明显地分为左子树和右子树。在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时，该结点即为叶子结点。
（2）二叉树的基本性质 二叉树具有以下几个性质：
性质1：在二叉树的第k层上，最多有2^(k-1)（k≥1）个结点； 性质2：深度为m的二叉树最多有2^m-1个结点；
性质3：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。
性质4：具有n个结点的二叉树，其深度至少为［log2n］+1，其中［log2n］表示取log2n的整数部分。
小技巧：在二叉树的遍历中，无论是前序遍历，中序遍历还是后序遍历，二叉树的叶子结点的先后顺序都是不变的。
3、满二叉树与完全二叉树
满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点。在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2^(k-1)个结点，且深度为m的满二叉树有2^m－1个结点。
完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。
对于完全二叉树来说，叶子结点只可能在层次最大的两层上出现：对于任何一个结点，若其右分支下的子孙结点的最大层次为p，则其左分支下的子孙结点的最大层次或为p，或为p+1。
完全二叉树具有以下两个性质：
性质5:具有n个结点的完全二叉树的深度为［log2n］+1。
性质6:设完全二叉树共有n个结点。如果从根结点开始，按层次（每一层从左到右）用自然数1，2，……，n给结点进行编号，则对于编号为k（k=1，2，……，n）的结点有以下结论：
①若k=1，则该结点为根结点，它没有父结点；若k>1，则该结点的父结点编号为INT（k/2）。
②若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。
③若2k+1≤n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。
考点8 二叉树的遍历 考试链接：
考点8在笔试考试中考核几率为30%，分值为2分，读者应该熟练掌握各种遍历的具体算法，能由两种遍历的结果推导另一种遍历的结果。
在遍历二叉树的过程中，一般先遍历左子树，再遍历右子树。在先左后右的原则下，根据访问根结点的次序，二叉树的遍历分为三类：前序遍历、中序遍历和后序遍历。
（1）前序遍历：先访问根结点、然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
（2）中序遍历：先遍历左子树、然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。
（3）后序遍历：先遍历左子树、然后遍历右子树，最后访问根结点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。
疑难解答：树与二叉树的不同之处是什么？
在二叉树中，每一个结点的度最大为2，即所有子树（左子树或右子树）也均为二叉树，而树结构中的每一个结点的度可以是任意的。
1.5查找技术
考点9 顺序查找 考试链接：
考点9在笔试考试中考核几率在30%，一般出现选择题中，分值为2分，读者应该具体掌握顺序查找的算法。
查找是指在一个给定的数据结构中查找某个指定的元素。从线性表的第一个元素开始，依次将线性表中的元素与被查找的元素相比较，若相等则表示查找成功；若线性表中所有的元素都与被查找元素进行了比较但都不相等，则表示查找失败。
在下列两种情况下也只能采用顺序查找：
（1）如果线性表为无序表，则不管是顺序存储结构还是链式存储结构，只能用顺序查找。
（2）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。 考点10 二分法查找 考试链接：
考点10在笔试考试中考核几率为30%，一般出现填空题中，分值为2分，考核比较多查找的比较次数，读者应该具体掌握二分查找法的算法。
二分法只适用于顺序存储的，按非递减排列的有序表，其方法如下：