全国计算机等级考试二级公共基础知识考纲.doc

. .
目录
二级公共根底知识考纲 ………………………………………………………………1
第一章 数据构造与算法…………………………………………………………2
第二章 程序设计根底……………………………………………………………19
第三章 软件工程根底……………………………………………………………23
第四章 数据库设计根底…………………………………………………………32
全国计算机等级考试二级公共根底知识考纲
考试内容
一、 根本数据构造与算法
1. 算法的根本概念；算法复杂度的概念和意义〔时间复杂度与空间复杂度〕。
2. 数据构造的定义；数据的逻辑构造与存储构造；数据构造的图形表示；线性构造与非线性构造的概念。
3. 线性表的定义；线性表的顺序存储构造及其插入与删除运算。
4. 栈和队列的定义；栈和队列的顺序存储构造及其根本运算。
5. 线性单链表、双向链表与循环链表的构造及其根本运算。
6. 树的根本概念；二叉树的定义及其存储构造；二叉树的前序、中序和后序遍历。
7. 顺序查找与二分法查找算法；根本排序算法〔交换类排序，选择类排序，插入类排序〕。
二、 程序设计根底
1. 程序设计方法与风格。
2. 构造化程序设计。
3. 面向对象的程序设计方法，对象，方法，属性及继承与多态性。
三、 软件工程根底
1. 软件工程根本概念，软件生命周戎概念，软件工具与软件开发环境。
2. 构造化分析方法，数据流图，数据字典，软件需求规格说明书。
3. 构造化设计方法，总体设计与详细设计。
4. 软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。
5. 程序的调试，静态调试与动态调试。
四、 数据库设计根底
1. 数据库的根本概念：数据库，数据库管理系统，数据库系统。
2. 数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。
3. 关系代数运算，包括集合运算及选择、投影、连接运算，数据库规X化理论。
4. 数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。
考试方式
公共根底的考试方式为笔试，与C语言〔VisualBASIC、Visual FoxPro、Java、Access、Visual C++〕的笔试局部合为一X试卷。公共根底局部占全卷的30分。公共根底知识有10道选择题和5道填空题。

第一章 数据构造与算法
一、内容要点
〔一〕算法
1．算法的根本概念
算法是指解题方案的准确而完整的描述。即是一组严谨地定义运算顺序的规那么，并且每一个规那么都是有效的，且是明确的，没有二义性，同时该规那么将在有限次运算后可终止。
1〕算法的根本特征
〔1〕可行性
由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的，因此，它总是受到计算工具的限制，使执行产生偏差。
如：计算机的数值有效位是有限的，当大数和小数进展运算时，往往会因为有效位数的影响而使小数丧失，因此，在算法设计时，应该考虑到这一点。
〔2〕确定性
算法的设计必须是每一个步骤都有明确的定义，不允许有模糊的解释，也不能有多义性。
例如，一个实际的问题，小宝和萍萍共有12个苹果，小宝比萍萍多4个，请问小宝和萍萍各有几个苹果？这个问题，我们可以立一个方程 来求解，要求x和y的值，公式是正确的，但如何让计算能够进展计算，我们的算法不能把公式直接输进去，而应该设计出解题的步骤和过程。
即设计的算法是计算工具所能够正常解决问题的过程。
〔3〕有穷性
算法的有穷性，即在一定的时间是能够完成的，即算法应该在计算有限个步骤后能够正常完毕。
例如，在数学中的无穷级数，在计算机中只能求有限项，即计算的过程是有穷的。
〔4〕拥有足够的情报
算法的执行与输入的数据和提供的初始条件相关，不同的输入或初始条件会有不同的输出结果，提供准确的初始条件和数据，才能使算法正确执行。
2〕算法的根本要素
一是数据对象的运算和操作，二是算法的控制构造。
〔1〕算法中对数据的运算和操作
算法实际上是按解题要求从环境能进展的所有操作中选择适宜的操作所组成的一组指令序列。即算法是计算机所能够处理的操作所组成的指令序列。
〔2〕算法的控制构造
算法的功能不仅取决于所选用的操作，而且还与各操作之间的顺序有关。
在算法中，操作的执行顺序又称算法的控制构造，一般的算法控制构造有三种：顺序构造、选择构造和循环构造。
在算法描述是，有相关的工具对这三种构造进展描述，常用的描述工具有：流程图、N-S构造图和算法描述语言等。
3〕算法设计的根本方法
为用计算机解决实际问题而设计的算法，即是计算机算法。
通常的算法设计有如下几种：
〔1〕列举法
列举法的根本思想是，根据提出的问题，列举出所有可能的情况，并用问题中给定的条件检验哪些是满足条件的，哪些是不满足条件的。列举法通常用于解决“是否存在〞或“有哪些可能〞等问题。
例如，我国古代的趣味数学题：“百钱买百鸡〞、“鸡兔同笼〞等，均可采用列举法进展解决。
使用列举法时，要对问题进展详细的分析，将与问题有关的知识条理化、完备化、系统化，从中找出规律。
〔2〕归纳法
归纳法的根本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。归纳是一种抽象，即从特殊现象中找出一般规律。但由于在归纳法中不可能对所有的情况进展列举，因此，该方法得到的结论只是一种猜想，还需要进展证明。
〔3〕递推
递推，即是从的初始条件出发，逐次推出所要求的各个中间环节和最后结果。其中初始条件或问题本身已经给定，或是通过对问题的分析与化简而确定。
递推的本质也是一种归纳，递推关系式通常是归纳的结果。
例如，裴波那契数列，是采用递推的方法解决问题的。
〔4〕递归
在解决一些复杂问题时，为了降低问题的复杂程序，通常是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，并没有对问题进展求解，而只是当解决了最后的问题那些最简单的问题后，再沿着原来分解的逆过程逐步进展综合，这就是递归的方法。
递归分为直接递归和间接递归两种方法。如果一个算法直接调用自己，称为直接递归调用；如果一个算法A调用另一个算法B，而算法B又调用算法A，那么此种递归称为间接递归调用。
〔5〕减半递推技术
减半递推即将问题的规模减半，然后，重复一样的递推操作。
例如，一元二次方程的求解。
〔6〕回溯法
有些实际的问题很难归纳出一组简单的递推公式或直观的求解步骤，也不能使用无限的列举。对于这类问题，只能采用试探的方法，通过对问题的分析，找出解决问题的线索，然后沿着这个线索进展试探，如果试探成功，就得到问题的解，如果不成功，再逐步回退，换别的路线进展试探。这种方法，即称为回溯法。
如人工智能中的机器人下棋。
2．算法复杂度
算法的复杂度包括时间复杂度和空间复杂度。
1〕时间复杂度
即实现该算法需要的计算工作量。算法的工作量用算法所执行的根本运算次数来计算。
同一个问题规模下，如果算法执行所需要的根本次数取决于某一特定输入时，可以用以下两种方法来分析算法的工作量：
算法工作量=f(n)
〔1〕平均性态
用各种特定输入下的根本运算次数的加权平均值来度量算法的工作量。
设x是某个可能输入中的某个特定输入，p(x)是x出现的概率，t(x)是算法在输入为x时所执行的根本运算次数，那么算法的平均性态定义为：

Dn表示当规模为n时，算法执行时所有可能输入的集合。
〔2〕最坏情况复杂度
指在规模为n时，算法所执行的根本运算的最大次数。它定义为：

例如，在具有n个元素的数列中搜索一个数x。
平均性态：
即该数在数列中任何位置出现的数列是一样的，也有可能不存在，存在的概率为q。
如果有一半的时机存在，那么概率q为1/2，平均性态：

如果查找的元素一定在数列中，那么每个数存在的概率即为1，那么平均性态为：
最坏情况分析：即要查找的元素X在数列的最后或不在数列中，显然，它的最坏情况复杂度为：
2〕算法的空间复杂度
指要执行该算法所需要的内存空间。算法所占用的内存空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间，如执行过程中工作单元以及某种数据构造所需要的附加存储空间等。
〔二〕数据构造的根本概念
1．概念
数据构造是指相互有关联的数据元素的集合。它包括以下两个方面：
l 表示数据元素的信息
l 表示各数据之间的前后件关系
1〕数据的逻辑构造
是指反映数据元素之间的逻辑关系的数据构造。
数据的逻辑构造有两个要素：
l 数据元素的集合，记作D
l 数据之间的前后件关系，记作R
那么数据构造B=〔D，R〕
2〕数据的存储构造
数据的逻辑构造在计算机存储空间中的存放形式称为数据的存储构造，或数据的物理构造。
即数据存储时，不仅要存放数据元素的信息，而且要存储数据元素之间的前后件关系的信息。
通常的数据存储构造有顺序、、索引等存储构造。
2．数据构造的图形表示
数据构造的图形表示有两个元素：
l 中间标有元素值的方框表示数据元素，称为数据结点
l 用有向线段表示数据元素之间的前后件关系，即有向线段从前件结点指向后件结点
注意：在构造图中，没有前件的结点称为根结点，没有后件的结点称为终端结点，也称叶子结点。
3．线性构造与非线性构造
如果一个数据元素都没有，该数据构造称为空数据构造；在空数据构造中插入一个新的元素后数据构造变为非空数据构造；将数据构造中的所有元素均删除，那么该数据构造变成空数据构造。
如果一个非空的数据构造满足如下条件，那么该数据构造为线性构造：
l 有且只有一个根结点
l 每一个结点最多只有一个前件，也最多只有一个后件
线性构造又称线性表。
注意：在线性构造表中插入或删除元素，该线性表仍然应满足线性构造。
如果一个数据构造不满足线性构造，那么称为非线性构造。
〔三〕线性表及其顺序存储构造
1．根本概念
线性表是最常用的数据构造，它由一组数据元素组成。
注意：这里的数据元素是一个广义的数据元素，并不仅仅是指一个数据。如，矩阵、学生记录表等。
非空线性表的构造特征：
l 有且只有一个根结点，它无前件
l 有且只有一个终端结点，它无后件
l 除根结点和终端结点之外，所有的结点有且只有一个前件和一个后件。线性表中结点的个数称为结点的长度n。当n=0时，称为空表。
2．顺序存储构造
顺序存储构造的特点：
l 线性表中所有的元素所占的存储空间是连续的
l 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的
通常，顺序存储构造中，线性表中每一个数据元素在计算机存储空间中的存储地址由该元素在线性表中的位置序号唯一确定。
线性表的顺序存储构造下的根本运算：
l 在指定位置插入一个元素
l 删除线性表中的指定元素
l 查找某个或某些特定的元素
l 线性表的排序
l 按要求将一个线性表拆分为多个线性表
l 将多个线性表合并为一个线性表
l 复制线性表
l 逆转一个线性表
3．线性表的根本操作
1〕顺序表的插入运算
在顺序存储构造的线性表中插入一个元素。
注意：找到插入位置后，将插入位置开场的所有元素从最后一个元素开场顺序后移。另外，在定义线性表时，一定要定义足够的空间，否那么，将不允许插入元素。
2〕顺序表的删除运算
在顺序在存储构造的线性表中删除一个元素。
注意：找到删除的数据元素后，从该元素位置开场，将后面的元素一一向前移动，在移动完成后，线性表的长度减1
〔四〕栈和队列
1．栈及其根本运算
1〕栈
栈是一种特殊的线性表，它是限定在一端进展插入和删除的线性表。它的插入和删除只能在表的一端进展，而另一端是封闭的，不允许进展插入和删除操作。
在栈中，允许插入和删除操作一端称为栈顶，不允许插入和删除操作的一端那么称为栈底。栈顶的元素总是最后被插入的元素，也是最先被删除的元素。它遵循的原那么是：先进后出或后进先出。
堆栈指针总是指向栈顶元素的。
2〕栈的顺序存储及其运算
在栈的顺序存储空间S〔1：m〕中，S〔bottom〕通常为栈底元素，S〔top〕为栈顶元素。Top=0表示栈空；top=m表示栈满。
1〕入栈运算
即在栈的顶部插入一个新元素。操作方式是：将栈顶指针加1，再将元素插入至指针所指的位置。
2〕退栈运算
退栈运算即将栈顶元素取出并赋给一个指定的变量。操作方式是：先将栈顶元素赋给指定的变量，再将栈顶指针减1。
3〕读栈顶元素
将栈顶元素赋给某一指定变量，但栈顶指针不变。
2．队列及其根本运算
1〕队列
队列即是允许在一端进展插入，而在另一端进展删除的线性表。允许插入的一端称为队尾，通常用一个尾指针指向队尾；允许删除的一端称为队首，通常用一个队首指针指向排队元素的前一个位置。
队列遵循的规那么是：先进先出或后进后出
2〕循环队列及其运算
队列的顺序存储构造一般采用循环队列的形式。
循环队列，即是次队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。
在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置，因此，从排头指针front指向的后一个位置到队尾指针rear指向的位置之间所有的元素均为队列中的元素。
循环队列的初始状态为空，即rear=front=m。这里m即为队列的存储空间。
循环队列的根本运算：入队运算和退队运算。
入队运算：每进展一次入队运算，队尾指针加1。当队尾指针rear=m+1时，即表示队列空间的尾部已经放置了元素，那么下一个元素应该旋转到队列空间的首部，即rear=1
退队运算：每退队一个元素，排头指针加1。当排头指针front=m+1时，即排头指针指向队列空间的尾部，退队后，排头指针指向队列空间的开场，即front=1。
在队列操作时，循环队列满时，front=rear，队列空时，也有rear=front，即在队列空或满时，排头指针和队尾指针均指向同一个位置。要判断队列空或满时，还应增加一个标志，s值的定义：

判断队列空与队列满的条件下：
队列空的条件：s=0
队列满的条件：s=1、front=rear
〔1〕入队运算
即在队尾参加一个新元素。这个运算有两个根本操作：首先，将队尾指针加1，即rear=rear+1，当rear=m+1时，置rear=1，然后，将新元素插入到队尾指针指向的位置。
当循环队列非空〔s=1〕，且front=rear时，队列满，不能进展入队操作。此情况称“上溢〞。
〔2〕退队操作
即将队首的元素赋给一个指定的变量。该运算也有两个根本操作：首先，将排头指针加1，即front=front+1，当front=m+1时，置front=1，然后，将排头指针指向的元素赋给指定的变量。
当循环队列为空〔s=0〕时，不能进展退队运算。此种情况称为“下溢〞。
〔五〕线性链表
1．根本概念
前面的线性表均是采用顺序存储构造及在顺序存储构造下的运算。
1〕顺序存储的优点：
l 构造简单
l 运算方便
2〕顺序存储构造的缺点：
l 要在顺序存储的线性表中插入一个新元素或删除一个元素时，为了保证插入或删除后的线性表仍然为顺序存储。在插入或删除元素时，需要移动大量的数据元素，因此运算效率较低。
l 如果一个线性表分配顺序存储空间后，如果出现线性表的存储空间已满，但还需要插入元素时，会发生“上溢〞错误。
l 在实际应用时，可能有多个线性表同时使用存储空间，这样给存储空间的分配带来问题，有可能使有的队列空间不够或过多造成浪费。
基于上述情况，对于大的线性表或元素变动频繁的大线性表不宜采用顺序存储构造，而应采用链式存储构造。
3〕链式存储构造
假设每一个数据结点对应一个存储单元，该存储单元称为存储结点，简称结点。
在链式存储方式中，要求每一个结点由两局部组成：一局部用于存放数据元素，你为数据域；另一局部用于存放指针，称为指针域。该指针用于指向该结点的前一个或后一个结点。
在链式存储构造中，存储数据构造的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系不一致，而数据元素之间的逻辑关系是由指针域来确定的。
链式存储构造既可以用于线性构造，也可用于非线性构造。
4〕线性链表
线性表的链式存储构造称为线性链表。
将存储空间划分成假设干的小块，每块占用假设干个字节，这些小块称为存储结点。
将存储结点分为两个局部，一局部用于存储数据元素的值，称为数据域；另一局部用于存储元素之间的前后件关系，即存放下一个元素在存储序号〔即存储地址〕，即指向后件结点，称为指针域。
在线性链表中用一个专门的指针HEAD指向线性链表中第一个数据元素的结点〔即存放第一个元素的地址〕。线性表中最后一个元素没有后件，因此，线性链表中的最后一个结点的指针域为空〔用Null或0表示〕，表示链终结。
在线性链表中，各元素的存储序号是不连续的，元素间的前后件关系与位置关系也是不一致的。在线性链表中，前后件的关系依靠各结点的指针来指示，指向表的第一个元素的指针HEAD称为头指针，当HEAD=NULL时，表示该链表为空。
对于线性链表，可以从头指针开场，沿着各结点的指针扫描到链表中的所有结点。
这种线性链表称为线性单链表，即可以从表头开场向后扫描链表中的所有结点，而不能从中间或表尾结点向前扫描位于该结点之前的元素。
这种链表构造的缺点是不能任意地对链表中的元素按下同的方向进展扫描。在某些应用时，如果对链表中的元素设置两个指针域，一个为指向前件的指针域，称为左指针〔LLink〕，一个为指向后件的指针域，称为右指针〔RLink〕。那么这种链表是双向链表。
5〕带链的栈
带链的栈即是用来收集计算机存储空间中的所有空闲的存储结点，这种带链的栈称为可利用栈。
当需要存储结点时，即从可利用的栈的顶部取出栈顶结点；当系统要释放一个存储结点时，将该结点空间放回到可利用栈的栈顶。
即在计算机中所有空闲的空间，均可以以结点的方式到可利用栈中，随着其他线性链表中结点的插入与删除，可利用栈处于动态变化之中，即可利用栈经常要进展退栈和入栈操作。
6〕带链的队列
队列也是线性表，也可利用链式存储构造来进展保存。
2．线性链表的根本运算
线性链表包括的根本运算：
l 在链表中包含指定元素的结点之前插入一个新元素
l 在链表中删除包含指定元素的结点
l 将两个线性链表按要求合并成一个线性链表
l 将一个线性链表按要求进展分解
l 逆转线性链表
l 复制线性链表
l 线性链表的排序
l 线性链表的查找
1〕线性链表中查找指定的元素
在线性链表中查找元素X：从头指针指向的结点开场往后沿指针进展扫描，直到后面已没有结点或下一个结点的数据域为X为止。
元素的查找，经常是为了进展插入或删除操作而进展的，因此，在查找时，往往是需要记录下该结点的前一个结点。
2〕线性链表的插入
线性链表的插入即在链式存储构造的线性表中插入一个新元素。
在线性链表中包含元素x的结点之前插入新元素b，插入过程：
〔1〕从可利用栈中取得一个结点，设该结点号为p，即取得的结点的存储序号存放在变量p中。并置结点p的数据域为插入的元素值b。
〔2〕在线性链表中寻找包含元素x的前一个结点，该结点的存储序号为q。
〔3〕将结点p插入到结点q之后。具体的操作：首先，使结点p插入到结点q之后〔即结点q的后件结点〕，然后，使结点q的指针域 内容改为指向结点p。
线性链表的插入操作，新结点是为来自于可利用栈，因此不会造成线性表的溢出。同样，由于可利用栈可被多个线性表利用，因此，不会造成存储空间的浪费，大家动态地共同使用存储空间。
3〕线性链表的删除
线性链表的删除，即是在链式存储构造下的线性表中删除指定元素的结点。
操作方式：
〔1〕在线性表中找到包含指定元素x的前一个结点p
〔2〕将该结点p后的包含元素x的结点从线性链表中删除，然后将被删除结点的后一个结点q的地址提供应结点p的指针域，即将结点p指向结点q。
〔3〕将删除的结点送回可利用栈。
从以上的删除操作可见，删除一个指定的元素，不需要移动其他的元素即可实现，这是顺序存储的线性表所不能实现的。同时，此操作还可更有效地利用计算机的存储空间。
3．循环链表及其根本操作
在线性链表中，虽然对数据元素的插入和删除操作比拟简单，但由于它对第一个结点和空表需要单独处理，使得空表与非空表的处理不一致。
循环链表，即是采用另一种方式，它的特点如下：
〔1〕在循环链表中增加一个表头结点，其数据域为任意或根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。
〔2〕循环链表中最后一个结点的指针域不是空的，而是指向表头结点。在循环链表中，所有结点的指针构成一个环状链。
在循环链表中，只要指出表中任何一个结点的位置，均可以从它开场扫描到所有的结点，而线性链表做不到，线性链表是一种单向的链表，只能按照指针的方向进展扫描。
循环链表中设置了一个表头结点，因此，在任何时候都至少有一个结点，因此空表与非空表的运算相统一。
〔六〕树与二叉树
1．树的根本概念
树是一种简单的非线性构造。在树构造中，数据元素之间有着明显的层次构造。在树的图形表示中，用直线连接两端的结点，上端点为前件，下端点为后件。

在树构造中，每一个结点只有一个前件，称为父结点。如A即为结点B、C、D的父结点。
没有父结点的结点只有一个，称为根结点。如上图所示，结点A即为根结点。
每一个结点可以有多个后件，它们均称为该结点的子结点。如结点G、H、I是结点D的子结点。
没有后件的结点，称为叶子结点。上图中，叶子结点有：J、M、N、L、C、G、H、I。
在树构造中，一个结点所拥有的后件结点个数称为该结点的度。例如，结点D的度为3，结点E的度为1等，按此原那么，所有叶子结点的度均为0。
在树中，所有结点中最大的度称为该树的度。上图所示的树中，所有结点中最大的度是3，所以该树的度为3。
树分层，根结点为第一层，往下依次类推。同一层结点的所有子结点均在下一层。如上图：A结点在第1层，B、C、D结点在第2层；E、F、G、H、I在第3层；J、K、L在第4层；M、N在第5层。
树的最大层次称为树的深度。上图树的深度为5。
在树中，某结点的一个子结点为根构成的树称作该结点的子树。叶子结点没有子树。
在计算机中，可以用树来表示算术表达式。原那么如下：
〔1〕表达式中每一个运算符在树中对应一个结点，称为运算符结点
〔2〕运算符的每一个运算对象在树中为该运算符结点的子树〔在树中的顺序为从左到右〕
〔3〕运算对象中的单变量均为叶子结点
树在计算机中用多重链表表示。多重链表中的每个结点描述了树中对应结点的信息，而每个结点中的链域〔即指针域〕个数将随着树中该结点的度而定义。
如果在树中，每一个结点的子结点的个数不一样，因此在多重链中各结点的链域个数也不一样，会导致算法太复杂。因此，在树中，常采用定长结点来表示树中的每一个结点，即取树的度作为每个结点的链域的个数。这样，管理相对简化了，但会造成空间的浪费，因为有许多的结点存在空链域。
2．二叉树及其根本性质
1〕二叉树的定义
二叉树的特点：
l 非空二叉树只有一个根结点
l 每一个结点最多只有两个子结点，且结点分左右。那么一个结点最多可以有两棵子树，分别称为左子树和右子树
在二叉树中，每一个结点的度最大为2，即二叉树的度为2。在二叉树中，任何的子树也均为二叉树。
在二叉树中，每一个结点的子树被分为左子树和右子树。在二叉树中，允许某一个结点只有左子树或只有右子树。如果一个结点既没有左子树，也没有右子树，那么该结点为叶子结点。
2〕二叉树的性质
性质1：在二叉树的第k层上，最多有2k-1〔k≥1〕个结点。
性质2：深度为m的二叉树最多有2m-1个结点。
性质3：在任意一棵二叉树中，度为0的结点〔即叶子结点〕总比度为2的结点多一个。
性质4：具有n个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示log2n的整数局部。
3〕满二叉树与完全二叉树
〔1〕满二叉树
满二叉树的特点：
除最后一层外，每一层上的所有结点都有两个子结点。即在满二叉树中，每一层上的结点数都到达最大值，即在满二叉树上的第k层上有2k-1个结点。如下即为一棵满二叉树。
〔2〕完全二叉树
特点：除最后一层外，每一层上的结点数均到达最大值，在最后一层上只缺少右边的假设干个结点。
即如果从根结点开场，对二叉树的结点自上而下、自左而右用自然数进展连续编号，那么深度为m、且有n个结点的二叉树，当且仅当其每一个结点都与深度为m的满二叉树中编号从1到n的结点一一对应，那么是完全二叉树。
对于完全二叉树，叶子结点只能在层次最大的两层中出现；对于任何一个结点，假设其右分支下的子树结点的最大层次为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；否那么该结点无右子结点。
3．二叉树的存储构造
二叉树的存储常采用链式存储构造。
存储二叉树中各元素的存储结点由两个局部组成：数据域和指针域。在二叉树中，由于每个结点可有两个子结点，那么它的指针域有两个：一个用于存储该结点的左子结点的存储地址，即称为左指针域；一个用于存储指向该结点的右子结点的存储地址，称为右指针域。
存储构造如下：
Lchild Value Rchild
i L(i) V(i) R(i)
即二叉树的存储构造中每一个存储结点都有两个指针域，因此，二叉树的链式存储构造也称为二叉树的链表。在二叉树在存储中，用一个头指针指向二叉树的根结点的存储地址。
如下图的二叉树：

如果我们将该二叉树的所有结点顺序编号，顺序存放在存储空间里，那么它们在内存空间中的存放方式是：
i L(i) V(i) R(i)
BTà 1 2 A 3
2 4 B 5
3 6 C 7
4 8 D 9
5 10 E 11
6 12 F 13
7 14 G 15
8 16 H 17
9 18 I 0
10 0 J 0
11 0 K 0
12 0 L 0
13 0 M 0
14 0 N 0
15 0 O 0
16 0 P 0
17 0 Q 0
18 0 R 0
当然，对于满二叉树或完全二叉树而言，也可采用顺序存储的方式，但顺序存储的方式不适合其他的二叉树。
4．二叉树的遍历
二叉树的遍历即是不重复地访问二叉树的所有结点。
在遍历二叉树时，一般先遍历左子树，然后再遍历右子树。在先左后右的原那么下，二叉树的遍历又可分为三种：前序遍历、中序遍历和后序遍历。
1〕前序遍历
前序遍历即先访问根结点，然后遍历左子树，最后遍历右子树。在遍历左子树和遍历右子树时，依然是先遍历根结点，然后是左子树，再是右子树。
操作的具体方式：
l 假设二叉树为空，那么完毕返回。
l 否那么：访问根结点®前序遍历左子树®前序遍历右子树
如上图所示的完全二叉树，它的前序遍历结果是：A、B、D、H、P、Q、I、R、E、J、K、C、F、L、M、G、N、O
2〕中序遍历
中序遍历，即先遍历左子树，然后访问根结点，最后是遍历右子树。
具体的操作方式：
l 假设二叉树为空，那么完毕返回。
l 否那么：中序遍历左子树®访问根结点 ®中序遍历右子树
这里强调，在遍历左子树和右子树时，仍然要采用中序遍历的方法。
如上图所示的完全二叉树，它的中序遍历结果是：P、H、Q、D、R、I、B、J、E、K、A、L、F、M、C、N、G、O
3〕后序遍历
后序遍历，即选遍历左子树，然后是遍历右子树，最后访问根结点。
具体的操作方式：
l 假设二叉树为空，那么完毕返回。
l 否那么：前序遍历左子树®前序遍历右子树®访问根结点
如上图所示的完全二叉树，它的后序遍历结果是：P、Q、H、R、I、D、J、K、E、B、L、M、F、N、O、G、C、A
〔七〕查找技术
查找即是指在一个给定的数据构造中查找某个指定的元素。
1．顺序查找
顺序查找又称顺序搜索。一般是在线性表中查找指定的元素。
根本操作方法是：
从线性表的第一个元素开场，与被查元素进展比拟，相等那么查找成功，否那么继续向后查找。如果所有的元素均查找完毕后都不相等，那么该元素在指定的线性表中不存在。
顺序查找的最好情况：要查找的元素在线性表的第一个元素，那么查找效率最高；如果要查找的元素在线性表的最后或根本不存在，那么查找需要搜索所有的线性表元素，这种情况是最差情况。
对于线性表而言，顺序查找效率很低。但对于以下的线性表，也只能采用顺序查找的方法：
l 线性表为无序表，即表中的元素没有排列不是按大小顺序进展排列的，这类线性表不管它的存储方式是顺序存储还是链式存储，都只能按顺序查找方式进展查找
l 即使是有序线性表，如果采用链式存储，也只能采用顺序查找方式
例如，现有线性表：7、2、1、5、9、4，要在序列中查找元素6，查找的过程是：
l 整个线性表的长度为5
l 查找计次n=1，将元素6与序列的第一个7元素进展比拟，不等，继续查找
l n=2，将6与第二个元素2进展比拟，不等，继续
l n=3，将6与第三个元素1进展比拟，不等，继续
l n=4，将6与第四个元素5进展比拟，不等，继续
l n=5，将6与第五个元素9进展比拟，不等，继续
l n=6，将6与第六个元素4进展比拟，不等，继续
l n=7，超出线性表的长度，查找完毕，那么该表中不存在要查找的元素。
2．二分查找
二分查找只适用于顺序存储的有序表。此处所述的有序表是指线性中的元素按值非递减排列〔即由小到大，但允许相邻元素值相等〕。
二分查找的方法如下：
将要查找的元素与有序序列的中间元素进展比拟：
l 如果该元素比中间元素大，那么继续在线性表的后半局部〔中间项以后的局部〕进展查找
l 如果要查找的元素的值比中间元素的值小，那么继续在线性表的前半局部〔中间项以前的局部〕进展查找
这个查找过程一直按一样的顺序进展下去，一直到查找成功或子表长度为0〔说明线性表中没有要查找的元素〕
有序线性表的二分法查找，条件是必须这个有序线性表的存储方式是顺序存储的。它的查找效率比顺序查找要高得多，它的最坏情况的查找次数是log2n次，而顺序查找的最坏情况的查找次数是n次。
当然，二分查找的方法也支持顺序存储的递减序列的线性表。
有非递减有序线性表：1、2、4、5、7、9，要查找元素6。查找的方法是：
l 序列长度为n=6，中间元素的序号m=[(n+1)/2]=3
l 查找计次k=1，将元素6与中间元素即元素4进展比拟，不等，6>4
l 查找计次k=2，查找继续在后半局部进展，后半局部子表的长度为3，计算中间元素的序号：m=3+[(3+1)/2]=5，将元素与后半局部的中间项进展比拟，即第5个元素中的7进展比拟，不等，6<7
l 查找计次k=3，继续查找在后半局部序列的前半局部子序列中查找，子表长度为1，那么中间项序号即为m=3+[(1+1)/2]=4，即与第4个元素5进展比拟，不相等，继续查找的子表长度为0，那么查找完毕
〔八〕排序技术
排序即是将一个无序的序列整理成按值非递减顺序排列的有序序列。在这里，我们讨论的是顺序存储的线性表的排序操作。
1．交换类排序法
交换类排序法，即是借助于数据元素之间的互相交换进展排序的方法。
1〕冒泡排序法
冒泡排序法即是利用相邻数据元素之间的交换逐步将线性表变成有序序列的操作方法。
操作过程如下：
l 从表头开场扫描线性表，在扫描过程中逐次比拟相邻两个元素的大小，假设相邻两个元素中前一个元素的值比后一个元素的值大，将两个元素位置进展交换，当扫描完成一遍时，那么序列中最大的元素被放置到序列的最后。
l 再继续对序列从头进展扫描，这一次扫描的长度是序列长度减1，因为最大的元素已经就位了，采用与前一样的方法，两两之间进展比拟，将次大数移到子序列的末尾。
l 按一样的方法继续扫描，每次扫描的子序列的长度均比上一次减1，直至子序列的长度为1时，排序完毕。
例如，有序列5、2、9、4、1、7、6，将该序列从小到大进展排列。
采用冒泡排序法，具体操作步骤如下：
序列长度n=7
原序列 5 2 9 4 1 7 6
第一遍〔从前往后〕 5¬® 2 9 4 1 7 6
2 5 9¨ 4 1 7 6
2 5 4 9¨ 1 7 6
2 3 4 1 9¨ 7 6
2 5 4 1 7 9¨ 6
第一遍完毕后 2 5 4 1 7 6 9
第二遍〔从前往后〕 2 5¬® 4 1 7 6 9
2 4 5¨ 1 7 6 9
2 4 1 5 7¨ 6 9
2 4 1 5 6 7 9
第二遍完毕后 2 4 1 5 6 7 9
第三遍〔从前往后〕 2 4¬® 1 5 6 7 9
2 1 4 5 6 7 9
第三遍完毕 2 1 4 5 6 7 9
第四遍〔从前往后〕 2¬® 1 4 5 6 7 9
1 2 4 5 6 7 9
第四遍完毕 1 2 4 5 6 7 9
最后结果 1 2 4 5 6 7 9
扫描的次数，最多需要扫描n-1次，如果序列已经就位，那么扫描完毕。测试是否已经就位，可设置一个标志，如果该次扫描没有数据交换，那么说明数据排序完毕。
2〕快速排序法
冒泡排序方法每次交换只能改变相邻两个元素之间的逆序，速度相对较慢。如果将两个不相邻的元素之间进展交换，可以消除多个逆序。
快速排序的方法是：
从线性表中选取一个元素，设为T，将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果将线性表分成两个局部〔称为两个子表〕，T插入到其分界限的位置处，这个过程称为线性表的分割。对过对线性表的一次分割，就以T为分界限，将线性表分成前后两个子表，且前面子表中的所有元素均不大于T，而后面的所有元素均不小于T。
再将前后两个子表再进展一样的快速排序，将子表再进展分割，直到所有的子表均为空，那么完成快速排序操作。
在快速排序过程中，随着对各子表不断的进展分割，划分出的子表会越来越多，但一次又只能对一个子表进展分割处理，需要将暂时不用的子表记忆起来，这里可用栈来实现。
对某个子表进展分割后，可以将分割出的后一个子表的第一个元素与最后一个元素的位置压入栈中，而继续对前一个子表进展再分割；当分割出的子表为空时，可以从栈中退出一个子表进展分割。
这个过程直到栈为空为止，说明所有子表为空，没有子表再需分割，排序就完成。
2．插入类排序法
1〕简单插入排序
插入排序，是指将无序序列中的各元素依次插入到