全国计算机等级考试二级公共基础知识教程

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

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

考试内容

一、 基本数据结构与算法

1. 算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。

2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。

3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算。 4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5. 线性单链表、双向链表与循环链表的结构及其基本运算。 6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。

7. 顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。 二、 程序设计基础 1. 程序设计方法与风格。 2. 结构化程序设计。

3. 面向对象的程序设计方法，对象，方法，属性及继承与多态性。 三、 软件工程基础

1. 软件工程基本概念，软件生命周戎概念，软件工具与软件开发环境。

2. 结构化分析方法，数据流图，数据字典，软件需求规格说明书。

第1页

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

3. 结构化设计方法，总体设计与详细设计。

4. 软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。 5. 程序的调试，静态调试与动态调试。 四、 数据库设计基础

1. 数据库的基本概念：数据库，数据库管理系统，数据库系统。 2. 数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。

3. 关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。

4. 数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。 考试方式

公共基础的考试方式为笔试，与C语言（VisualBASIC、Visual FoxPro、Java、Access、Visual C++）的笔试部分合为一张试卷。公共基础部分占全卷的30分。公共基础知识有10道选择题和5道填空题。

第2页

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

第一章 数据结构与算法

一、内容要点 （一）算法 1．算法的基本概念

算法是指解题方案的准确而完整的描述。即是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，没有二义性，同时该规则将在有限次运算后可终止。 1）算法的基本特征

（1）可行性

由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的，因此，它总是受到计算工具的限制，使执行产生偏差。

如：计算机的数值有效位是有限的，当大数和小数进行运算时，往往会因为有效位数的影响而使小数丢失，因此，在算法设计时，应该考虑到这一点。

（2）确定性

算法的设计必须是每一个步骤都有明确的定义，不允许有模糊的解释，也不能有多义性。

例如，一个实际的问题，小宝和萍萍共有12个苹果，小宝比萍萍多4个，请问小宝和萍萍各有几个苹果？这个问题，我们可以立一

第3页

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

?x?y?12个方程?来求解，要求x和y的值，公式是正确的，但如

?x?y?4何让计算能够进行计算，我们的算法不能把公式直接输进去，而应该设计出解题的步骤和过程。

即设计的算法是计算工具所能够正常解决问题的过程。 （3）有穷性

算法的有穷性，即在一定的时间是能够完成的，即算法应该在计算有限个步骤后能够正常结束。

例如，在数学中的无穷级数，在计算机中只能求有限项，即计算的过程是有穷的。

（4）拥有足够的情报

算法的执行与输入的数据和提供的初始条件相关，不同的输入或初始条件会有不同的输出结果，提供准确的初始条件和数据，才能使算法正确执行。 2）算法的基本要素

一是数据对象的运算和操作，二是算法的控制结构。 （1）算法中对数据的运算和操作

算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。即算法是计算机所能够处理的操作所组成的指令序列。

（2）算法的控制结构

算法的功能不仅取决于所选用的操作，而且还与各操作之间的顺

第4页

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

序有关。

在算法中，操作的执行顺序又称算法的控制结构，一般的算法控制结构有三种：顺序结构、选择结构和循环结构。

在算法描述是，有相关的工具对这三种结构进行描述，常用的描述工具有：流程图、N-S结构图和算法描述语言等。 3）算法设计的基本方法

为用计算机解决实际问题而设计的算法，即是计算机算法。 通常的算法设计有如下几种： （1）列举法

列举法的基本思想是，根据提出的问题，列举出所有可能的情况，并用问题中给定的条件检验哪些是满足条件的，哪些是不满足条件的。列举法通常用于解决“是否存在”或“有哪些可能”等问题。

例如，我国古代的趣味数学题：“百钱买百鸡”、“鸡兔同笼”等，均可采用列举法进行解决。

使用列举法时，要对问题进行详细的分析，将与问题有关的知识条理化、完备化、系统化，从中找出规律。

（2）归纳法

归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。归纳是一种抽象，即从特殊现象中找出一般规律。但由于在归纳法中不可能对所有的情况进行列举，因此，该方法得到的结论只是一种猜测，还需要进行证明。

（3）递推

第5页

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

递推，即是从已知的初始条件出发，逐次推出所要求的各个中间环节和最后结果。其中初始条件或问题本身已经给定，或是通过对问题的分析与化简而确定。

递推的本质也是一种归纳，递推关系式通常是归纳的结果。 例如，裴波那契数列，是采用递推的方法解决问题的。 （4）递归

在解决一些复杂问题时，为了降低问题的复杂程序，通常是将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，并没有对问题进行求解，而只是当解决了最后的问题那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的方法。

递归分为直接递归和间接递归两种方法。如果一个算法直接调用自己，称为直接递归调用；如果一个算法A调用另一个算法B，而算法B又调用算法A，则此种递归称为间接递归调用。

（5）减半递推技术

减半递推即将问题的规模减半，然后，重复相同的递推操作。 例如，一元二次方程的求解。 （6）回溯法

有些实际的问题很难归纳出一组简单的递推公式或直观的求解步骤，也不能使用无限的列举。对于这类问题，只能采用试探的方法，通过对问题的分析，找出解决问题的线索，然后沿着这个线索进行试探，如果试探成功，就得到问题的解，如果不成功，再逐步回退，换

第6页

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

别的路线进行试探。这种方法，即称为回溯法。

如人工智能中的机器人下棋。 2．算法复杂度

算法的复杂度包括时间复杂度和空间复杂度。 1）时间复杂度

即实现该算法需要的计算工作量。算法的工作量用算法所执行的基本运算次数来计算。

同一个问题规模下，如果算法执行所需要的基本次数取决于某一特定输入时，可以用以下两种方法来分析算法的工作量：

算法工作量=f(n) （1）平均性态

用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。

设x是某个可能输入中的某个特定输入，p(x)是x出现的概率，t(x)是算法在输入为x时所执行的基本运算次数，则算法的平均性态定义为：

A(n)?x?Dn?p(x)t(x)

Dn表示当规模为n时，算法执行时所有可能输入的集合。 （2）最坏情况复杂度

指在规模为n时，算法所执行的基本运算的最大次数。它定义为：

W(n)?max{t(x)}

x?Dn第7页

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

例如，在具有n个元素的数列中搜索一个数x。

q(n?1)qA(n)??piti??i?(1?q)n??(1?q)n 平均性态：

i?1i?1n2n?1n即该数在数列中任何位置出现的数列是相同的，也有可能不存在，存在的概率为q。

如果有一半的机会存在，则概率q为1/2，平均性态：

1(n?1)?132A(n)??(1?)n?n

224如果查找的元素一定在数列中，则每个数存在的概率即为1，则

n?1n? 平均性态为：A(n)?22最坏情况分析：即要查找的元素X在数列的最后或不在数列中，显然，它的最坏情况复杂度为：W(n)?max{ti|1?i?n?1}?n 2）算法的空间复杂度

指要执行该算法所需要的内存空间。算法所占用的内存空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间，如执行过程中工作单元以及某种数据结构所需要的附加存储空间等。 （二）数据结构的基本概念 1．概念

数据结构是指相互有关联的数据元素的集合。它包括以下两个方面：

第8页

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

? 表示数据元素的信息 ? 表示各数据之间的前后件关系 1）数据的逻辑结构

是指反映数据元素之间的逻辑关系的数据结构。 数据的逻辑结构有两个要素： ? 数据元素的集合，记作D ? 数据之间的前后件关系，记作R 则数据结构B=（D，R） 2）数据的存储结构

数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构，或数据的物理结构。

即数据存储时，不仅要存放数据元素的信息，而且要存储数据元素之间的前后件关系的信息。

通常的数据存储结构有顺序、链接、索引等存储结构。 2．数据结构的图形表示

数据结构的图形表示有两个元素：

? 中间标有元素值的方框表示数据元素，称为数据结点 ? 用有向线段表示数据元素之间的前后件关系，即有向线段从前件结点指向后件结点

注意：在结构图中，没有前件的结点称为根结点，没有后件的结点称为终端结点，也称叶子结点。

第9页

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

3．线性结构与非线性结构

如果一个数据元素都没有，该数据结构称为空数据结构；在空数据结构中插入一个新的元素后数据结构变为非空数据结构；将数据结构中的所有元素均删除，则该数据结构变成空数据结构。

如果一个非空的数据结构满足如下条件，则该数据结构为线性结构：

? 有且只有一个根结点

? 每一个结点最多只有一个前件，也最多只有一个后件 线性结构又称线性表。

注意：在线性结构表中插入或删除元素，该线性表仍然应满足线性结构。

如果一个数据结构不满足线性结构，则称为非线性结构。 （三）线性表及其顺序存储结构 1．基本概念

线性表是最常用的数据结构，它由一组数据元素组成。 注意：这里的数据元素是一个广义的数据元素，并不仅仅是指一个数据。如，矩阵、学生记录表等。

非空线性表的结构特征： ? 有且只有一个根结点，它无前件 ? 有且只有一个终端结点，它无后件

? 除根结点和终端结点之外，所有的结点有且只有一个前件和一

第10页

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

基于上述情况，对于大的线性表或元素变动频繁的大线性表不宜采用顺序存储结构，而应采用链式存储结构。 3）链式存储结构

假设每一个数据结点对应一个存储单元，该存储单元称为存储结点，简称结点。

在链式存储方式中，要求每一个结点由两部分组成：一部分用于存放数据元素，你为数据域；另一部分用于存放指针，称为指针域。该指针用于指向该结点的前一个或后一个结点。

在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系不一致，而数据元素之间的逻辑关系是由指针域来确定的。

链式存储结构既可以用于线性结构，也可用于非线性结构。 4）线性链表

线性表的链式存储结构称为线性链表。

将存储空间划分成若干的小块，每块占用若干个字节，这些小块称为存储结点。

将存储结点分为两个部分，一部分用于存储数据元素的值，称为数据域；另一部分用于存储元素之间的前后件关系，即存放下一个元素在存储序号（即存储地址），即指向后件结点，称为指针域。

在线性链表中用一个专门的指针HEAD指向线性链表中第一个数据元素的结点（即存放第一个元素的地址）。线性表中最后一个元素没有后件，因此，线性链表中的最后一个结点的指针域为空（用Null

第16页

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

或0表示），表示链终结。

在线性链表中，各元素的存储序号是不连续的，元素间的前后件关系与位置关系也是不一致的。在线性链表中，前后件的关系依靠各结点的指针来指示，指向表的第一个元素的指针HEAD称为头指针，当HEAD=NULL时，表示该链表为空。

对于线性链表，可以从头指针开始，沿着各结点的指针扫描到链表中的所有结点。

这种线性链表称为线性单链表，即可以从表头开始向后扫描链表中的所有结点，而不能从中间或表尾结点向前扫描位于该结点之前的元素。

这种链表结构的缺点是不能任意地对链表中的元素按下同的方向进行扫描。在某些应用时，如果对链表中的元素设置两个指针域，一个为指向前件的指针域，称为左指针（LLink），一个为指向后件的指针域，称为右指针（RLink）。则这种链表是双向链表。 5）带链的栈

带链的栈即是用来收集计算机存储空间中的所有空闲的存储结点，这种带链的栈称为可利用栈。

当需要存储结点时，即从可利用的栈的顶部取出栈顶结点；当系统要释放一个存储结点时，将该结点空间放回到可利用栈的栈顶。

即在计算机中所有空闲的空间，均可以以结点的方式链接到可利用栈中，随着其他线性链表中结点的插入与删除，可利用栈处于动态变化之中，即可利用栈经常要进行退栈和入栈操作。

第17页

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

6）带链的队列

队列也是线性表，也可利用链式存储结构来进行保存。 2．线性链表的基本运算

线性链表包括的基本运算：

? 在链表中包含指定元素的结点之前插入一个新元素 ? 在链表中删除包含指定元素的结点 ? 将两个线性链表按要求合并成一个线性链表 ? 将一个线性链表按要求进行分解 ? 逆转线性链表 ? 复制线性链表 ? 线性链表的排序 ? 线性链表的查找 1）线性链表中查找指定的元素

在线性链表中查找元素X：从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为X为止。

元素的查找，经常是为了进行插入或删除操作而进行的，因此，在查找时，往往是需要记录下该结点的前一个结点。 2）线性链表的插入

线性链表的插入即在链式存储结构的线性表中插入一个新元素。 在线性链表中包含元素x的结点之前插入新元素b，插入过程： （1）从可利用栈中取得一个结点，设该结点号为p，即取得的

第18页

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

结点的存储序号存放在变量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）将删除的结点送回可利用栈。

从以上的删除操作可见，删除一个指定的元素，不需要移动其他的元素即可实现，这是顺序存储的线性表所不能实现的。同时，此操作还可更有效地利用计算机的存储空间。

第19页

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

3．循环链表及其基本操作

在线性链表中，虽然对数据元素的插入和删除操作比较简单，但由于它对第一个结点和空表需要单独处理，使得空表与非空表的处理不一致。

循环链表，即是采用另一种链接方式，它的特点如下： （1）在循环链表中增加一个表头结点，其数据域为任意或根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。

（2）循环链表中最后一个结点的指针域不是空的，而是指向表头结点。在循环链表中，所有结点的指针构成一个环状链。

在循环链表中，只要指出表中任何一个结点的位置，均可以从它开始扫描到所有的结点，而线性链表做不到，线性链表是一种单向的链表，只能按照指针的方向进行扫描。

循环链表中设置了一个表头结点，因此，在任何时候都至少有一个结点，因此空表与非空表的运算相统一。 （六）树与二叉树 1．树的基本概念

树是一种简单的非线性结构。在树结构中，数据元素之间有着明

A B E J M K N F L 第20页 C G D H I

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

显的层次结构。在树的图形表示中，用直线连接两端的结点，上端点为前件，下端点为后件。

在树结构中，每一个结点只有一个前件，称为父结点。如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。

在树中，某结点的一个子结点为根构成的树称作该结点的子树。叶子结点没有子树。

第21页

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

在计算机中，可以用树来表示算术表达式。原则如下： （1）表达式中每一个运算符在树中对应一个结点，称为运算符结点

（2）运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）

（3）运算对象中的单变量均为叶子结点

树在计算机中用多重链表表示。多重链表中的每个结点描述了树中对应结点的信息，而每个结点中的链域（即指针域）个数将随着树中该结点的度而定义。

如果在树中，每一个结点的子结点的个数不相同，因此在多重链中各结点的链域个数也不相同，会导致算法太复杂。因此，在树中，常采用定长结点来表示树中的每一个结点，即取树的度作为每个结点的链域的个数。这样，管理相对简化了，但会造成空间的浪费，因为有许多的结点存在空链域。 2．二叉树及其基本性质 1）二叉树的定义

二叉树的特点：

? 非空二叉树只有一个根结点

? 每一个结点最多只有两个子结点，且结点分左右。则一个结点最多可以有两棵子树，分别称为左子树和右子树

在二叉树中，每一个结点的度最大为2，即二叉树的度为2。在二叉树中，任何的子树也均为二叉树。

第22页

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

在二叉树中，每一个结点的子树被分为左子树和右子树。在二叉树中，允许某一个结点只有左子树或只有右子树。如果一个结点既没有左子树，也没有右子树，则该结点为叶子结点。 2）二叉树的性质

性质1：在二叉树的第k层上，最多有2k-1（k≥1）个结点。 性质2：深度为m的二叉树最多有2m-1个结点。

性质3：在任意一棵二叉树中，度为0的结点（即叶子结点）总比度为2的结点多一个。

性质4：具有n个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示log2n的整数部分。 3）满二叉树与完全二叉树

（1）满二叉树 满二叉树的特点：

除最后一层外，每一层上的所有结点都有两个子结点。即在满二

A B D H I J E K L F M C G N O 满二叉树

叉树中，每一层上的结点数都达到最大值，即在满二叉树上的第k层上有2k-1个结点。如下即为一棵满二叉树。

（2）完全二叉树

特点：除最后一层外，每一层上的结点数均达到最大值，在最后

第23页

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

一层上只缺少右边的若干个结点。

即如果从根结点开始，对二叉树的结点自上而下、自左而右用自然数进行连续编号，则深度为m、且有n个结点的二叉树，当且仅当其每一个结点都与深度为m的满二叉树中编号从1到n的结点一一对应，则是完全二叉树。

A B D H P Q R 完全二叉树

C E J K L F M G N O I 对于完全二叉树，叶子结点只能在层次最大的两层中出现；对于任何一个结点，若其右分支下的子树结点的最大层次为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；否则该

第24页

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

结点无左子结点（当然也没有右子结点）

③ 若2k+1≤n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点。 3．二叉树的存储结构

二叉树的存储常采用链式存储结构。

存储二叉树中各元素的存储结点由两个部分组成：数据域和指针域。在二叉树中，由于每个结点可有两个子结点，则它的指针域有两个：一个用于存储该结点的左子结点的存储地址，即称为左指针域；一个用于存储指向该结点的右子结点的存储地址，称为右指针域。

存储结构如下：

i

Lchild L(i) Value V(i) Rchild R(i) 即二叉树的存储结构中每一个存储结点都有两个指针域，因此，二叉树的链式存储结构也称为二叉树的链表。在二叉树在存储中，用一个头指针指向二叉树的根结点的存储地址。

如图所示的二叉树：

第25页

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

A B D H P Q R I J E K L F M C G N O 如果我们将该二叉树的所有结点顺序编号，顺序存放在存储空间里，则它们在内存空间中的存放方式是：

i L(i) V(i) R(i)

2 4 6 8 10 12 14 16 18 0 0 0 0 0 A B C D E F G H I J K L M N 3 5 7 9 11 13 15 17 0 0 0 0 0 0 BT? 1

2 3 4 5 6 7 8 9 10 11 12 13 14 第26页

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

15 16 17 18 0 0 0 0 O P Q R 0 0 0 0 当然，对于满二叉树或完全二叉树而言，也可采用顺序存储的方式，但顺序存储的方式不适合其他的二叉树。 4．二叉树的遍历

二叉树的遍历即是不重复地访问二叉树的所有结点。

在遍历二叉树时，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，二叉树的遍历又可分为三种：前序遍历、中序遍历和后序遍历。 1）前序遍历

前序遍历即先访问根结点，然后遍历左子树，最后遍历右子树。在遍历左子树和遍历右子树时，依然是先遍历根结点，然后是左子树，再是右子树。

操作的具体方式：

? 若二叉树为空，则结束返回。

? 否则：访问根结点?前序遍历左子树?前序遍历右子树 如上图所示的完全二叉树，它的前序遍历结果是：A、B、D、H、P、Q、I、R、E、J、K、C、F、L、M、G、N、O

第27页

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

2）中序遍历

中序遍历，即先遍历左子树，然后访问根结点，最后是遍历右子树。

具体的操作方式：

? 若二叉树为空，则结束返回。

? 否则：中序遍历左子树?访问根结点 ?中序遍历右子树 这里强调，在遍历左子树和右子树时，仍然要采用中序遍历的方法。

如上图所示的完全二叉树，它的中序遍历结果是：P、H、Q、D、R、I、B、J、E、K、A、L、F、M、C、N、G、O 3）后序遍历

后序遍历，即选遍历左子树，然后是遍历右子树，最后访问根结点。

具体的操作方式：

? 若二叉树为空，则结束返回。

? 否则：前序遍历左子树?前序遍历右子树?访问根结点 如上图所示的完全二叉树，它的后序遍历结果是：P、Q、H、R、I、D、J、K、E、B、L、M、F、N、O、G、C、A （七）查找技术

查找即是指在一个给定的数据结构中查找某个指定的元素。

第28页

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

1．顺序查找

顺序查找又称顺序搜索。一般是在线性表中查找指定的元素。 基本操作方法是：

从线性表的第一个元素开始，与被查元素进行比较，相等则查找成功，否则继续向后查找。如果所有的元素均查找完毕后都不相等，则该元素在指定的线性表中不存在。

顺序查找的最好情况：要查找的元素在线性表的第一个元素，则查找效率最高；如果要查找的元素在线性表的最后或根本不存在，则查找需要搜索所有的线性表元素，这种情况是最差情况。

对于线性表而言，顺序查找效率很低。但对于以下的线性表，也只能采用顺序查找的方法：

? 线性表为无序表，即表中的元素没有排列不是按大小顺序进行排列的，这类线性表不管它的存储方式是顺序存储还是链式存储，都只能按顺序查找方式进行查找

? 即使是有序线性表，如果采用链式存储，也只能采用顺序查找方式

例如，现有线性表：7、2、1、5、9、4，要在序列中查找元素6，查找的过程是：

? 整个线性表的长度为5

? 查找计次n=1，将元素6与序列的第一个7元素进行比较，不等，继续查找

? n=2，将6与第二个元素2进行比较，不等，继续

第29页

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

? n=3，将6与第三个元素1进行比较，不等，继续 ? n=4，将6与第四个元素5进行比较，不等，继续 ? n=5，将6与第五个元素9进行比较，不等，继续 ? n=6，将6与第六个元素4进行比较，不等，继续

? n=7，超出线性表的长度，查找结束，则该表中不存在要查找的元素。 2．二分查找

二分查找只适用于顺序存储的有序表。此处所述的有序表是指线性中的元素按值非递减排列（即由小到大，但允许相邻元素值相等）。

二分查找的方法如下：

将要查找的元素与有序序列的中间元素进行比较：

? 如果该元素比中间元素大，则继续在线性表的后半部分（中间项以后的部分）进行查找

? 如果要查找的元素的值比中间元素的值小，则继续在线性表的前半部分（中间项以前的部分）进行查找

这个查找过程一直按相同的顺序进行下去，一直到查找成功或子表长度为0（说明线性表中没有要查找的元素）

有序线性表的二分法查找，条件是必须这个有序线性表的存储方式是顺序存储的。它的查找效率比顺序查找要高得多，它的最坏情况的查找次数是log2n次，而顺序查找的最坏情况的查找次数是n次。

当然，二分查找的方法也支持顺序存储的递减序列的线性表。 有非递减有序线性表：1、2、4、5、7、9，要查找元素6。查找

第30页

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

的方法是：

? 序列长度为n=6，中间元素的序号m=[(n+1)/2]=3

? 查找计次k=1，将元素6与中间元素即元素4进行比较，不等，6>4

? 查找计次k=2，查找继续在后半部分进行，后半部分子表的长度为3，计算中间元素的序号：m=3+[(3+1)/2]=5，将元素与后半部分的中间项进行比较，即第5个元素中的7进行比较，不等，6<7

? 查找计次k=3，继续查找在后半部分序列的前半部分子序列中查找，子表长度为1，则中间项序号即为m=3+[(1+1)/2]=4，即与第4个元素5进行比较，不相等，继续查找的子表长度为0，则查找结束 （八）排序技术

排序即是将一个无序的序列整理成按值非递减顺序排列的有序序列。在这里，我们讨论的是顺序存储的线性表的排序操作。 1．交换类排序法

交换类排序法，即是借助于数据元素之间的互相交换进行排序的方法。 1）冒泡排序法

冒泡排序法即是利用相邻数据元素之间的交换逐步将线性表变成有序序列的操作方法。

第31页

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

操作过程如下：

? 从表头开始扫描线性表，在扫描过程中逐次比较相邻两个元素的大小，若相邻两个元素中前一个元素的值比后一个元素的值大，将两个元素位置进行交换，当扫描完成一遍时，则序列中最大的元素被放置到序列的最后。

? 再继续对序列从头进行扫描，这一次扫描的长度是序列长度减1，因为最大的元素已经就位了，采用与前相同的方法，两两之间进行比较，将次大数移到子序列的末尾。

? 按相同的方法继续扫描，每次扫描的子序列的长度均比上一次减1，直至子序列的长度为1时，排序结束。

例如，有序列5、2、9、4、1、7、6，将该序列从小到大进行排列。

采用冒泡排序法，具体操作步骤如下： 序列长度n=7 原序列

5

2

9 9

4 4

1 1

7 7

6 6

第一遍（从前往5?? 2 后）

第一遍结束后

2 2 2 2 2

5 5 3 5 5

9?? 4 4 4 4 4

第32页

1 7 7

6 6 6

9?? 1 1 1 1

9?? 7 7 7

9?? 6 6

9

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

第二遍（从前往2 后）

第二遍结束后

2 2 2 2

5?? 4 1 7 6 9

4 4 4 4

5?? 1 1 1 1

5 5 5 5

7 6 9 9 9 9 9

7?? 6 6 6 6

7 7 7

第三遍（从前往2 后）

第三遍结束

2 2

4?? 1

1 1

4 4 4

5 5 5

6 6 6

7 7 7

9 9 9

第四遍（从前往2?? 1 后）

第四遍结束 最后结果

1 1 1

2 2 2

4 4 4

5 5 5

6 6 6

7 7 7

9 9 9

扫描的次数，最多需要扫描n-1次，如果序列已经就位，则扫描结束。测试是否已经就位，可设置一个标志，如果该次扫描没有数据交换，则说明数据排序结束。 2）快速排序法

冒泡排序方法每次交换只能改变相邻两个元素之间的逆序，速度相对较慢。如果将两个不相邻的元素之间进行交换，可以消除多个逆序。

第33页

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

快速排序的方法是：

从线性表中选取一个元素，设为T，将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果将线性表分成两个部分（称为两个子表），T插入到其分界线的位置处，这个过程称为线性表的分割。对过对线性表的一次分割，就以T为分界线，将线性表分成前后两个子表，且前面子表中的所有元素均不大于T，而后面的所有元素均不小于T。

再将前后两个子表再进行相同的快速排序，将子表再进行分割，直到所有的子表均为空，则完成快速排序操作。

在快速排序过程中，随着对各子表不断的进行分割，划分出的子表会越来越多，但一次又只能对一个子表进行分割处理，需要将暂时不用的子表记忆起来，这里可用栈来实现。

对某个子表进行分割后，可以将分割出的后一个子表的第一个元素与最后一个元素的位置压入栈中，而继续对前一个子表进行再分割；当分割出的子表为空时，可以从栈中退出一个子表进行分割。

这个过程直到栈为空为止，说明所有子表为空，没有子表再需分割，排序就完成。 2．插入类排序法 1）简单插入排序

插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。

插入排序操作的思路：在线性表中，只包含第1个元素的子表，

第34页

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

作为该有序表。从线性表的第2个元素开始直到最后一个元素，逐次将其中的每一个元素插入到前面的有序的子表中。

该方法与冒泡排序方法的效率相同，最坏的情况下需要n(n-1)/2次比较。

例如，有序列5、2、9、4、1、7、6，将该序列从小到大进行排列。

采用简单插入排序法，具体操作步骤如下： 序列长度n=7

5 2 2 2 1 1

2

9

4 4

1 1 1

7 7 7 7

6 6 6 6 6

?j=2 5 5 4 2 2 2

9

?j=3 9 5 4 4 4

4

?j=4 9 5 5 5

1

?j=5 9 7 6

7

?j=6 9 7

6 ?j=7 9

插入排序后的1 结果

第35页

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

2）希尔排序法

希尔排序法的基本思想：

将整个无序序列分割成若干小的子序列分别进行插入排序。 子序列的分割方法：将相隔某个增量h的元素构成一个子序列，在排序的过程中，逐次减小这个增量，最后当h减小到1时，再进行一次插入排序操作，即完成排序。

增量序列一般取ht=n/2k(k=1,2,?,[log2n])，其中n为待排序序列的长度。 3．选择类排序法 1）简单选择排序法

基本思路：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面，然后对后面的子表采用相同的方法，直到子表为空为止。

对于长度为n的序列，需要扫描n-1次，每一次扫描均找出剩余的子表中最小的元素，然后将该最小元素与子表的第一个元素进行交换。

例如，有序列5、2、9、4、1、7、6，将该序列从小到大进行排列。

采用简单选择排序法，具体操作步骤如下：

原序列

5 2 9 4 1 7 6

第一遍扫描 1 2 9 4 5 7 6 第二遍扫描 1 2 9 4 5 7 6

第36页

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

第三遍扫描 1 2 4 9 5 7 6 第四遍扫描 1 2 4 5 9 7 6 第五遍扫描 1 2 4 5 6 7 9 第六遍扫描 1 2 4 5 6 7 9 排序结果

2）堆排序法

堆排序法属于选择类排序方法。

堆的定义：具有n个元素的序列（h1,h2,?,hn），当且仅当满足

?hi?h2i??hi?h2i?1或hi?h2i（I=1,2,?,n/2）时称之为堆。

hi?h2i?11 2 4 5 6 7 9

本节只讨论满足前者条件的堆。

由堆的定义看，堆顶元素（即第一个元素）必为最大项。 可以用一维数组或完全二叉树来表示堆的结构。

用完全二叉树表示堆时，树中所有非叶子结点值均不小于其左右子树的根结点的值，因此堆顶（完全二叉树的根结点）元素必须为序列的n个元素中的最大项。

例如，有序列5、2、9、4、1、7、6，将该序列从小到大进行排列。

第37页

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

5 2 4 1 7 9 6 4 2 1 9 5 7 6 2 4 1 9 7 5 6 无序堆 调整根结点 调整子树的根结点

建堆的过程

利用堆排序法将该序列进行排序。

操作方式即：先将无序堆的根结点5与左右子树的根结点2、9进行比较，5<9，将5与9进行交换；整后，对左右子树进行堆调整，左子树的根结点2小于其左叶子结点5，调整；右子树的根结点5小于其左右子结点7和6，根据堆的要求，将5与7进行调整。

根据堆的定义，可以得到堆排序的方法： （1）首先将一个无序序列建成堆

（2）然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。 三、本章应考点拨

本章内容在笔试中会出现5-6个题目，是公共基础知识部分出题量比较多的一章，所占分值也比较大，约10分。

第二章 程序设计基础

一、内容要点

（一）程序设计方法与风格

程序设计方法：主要经过了面向过程的结构化程序设计和面向对

第38页

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

象的程序设计方法。

程序设计风格，是指编写程序时所表现出来的特点、习惯和逻辑思路。通常，要求程序设计的风格应强调简单和清晰，必须是可以读的，可以理解的。

要形成良好的程序设计的风格，应考虑如下因素： 1．源程序文档化

（1）符号名的命名：符号名的命名要具有一定的实际含义，便于对程序的理解，即通常说的见名思义；

（2）程序注释：正确的程序注释能够帮助他人理解程序。注释一般包括序言性注释和功能性注释；

（3）视觉组织：为了使程序一目了然，可以对程序的格式进行设置，适当地通过空格、空行、缩进等使程序层次清晰。 2．数据说明方法

（1）数据说明的次序规范化； （2）说明语句中变量安排有序化； （3）使用注释来说明复杂的数据结构。 3．语句的结构

（1）在一行内只写一条语句； （2）程序的编写应该优先考虑清晰性；

（3）除非对效率有特殊的要求，否则，应做到清晰第一，效率第二；

第39页

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

（4）首先保证程序的正确，然后再要求速度； （5）避免使用临时变量使程序的可读性下降； （7）尽量使用库函数，即尽量使用系统提供的资源； （8）避免采用复杂的条件语句；

（9）尽量减少使用“否定”条件的条件语句； （10）数据结构要有利于程序的简化； （11）要模块化，使模块功能尽可能单一化； （12）利用信息隐蔽，确保每一个模块的独立性； （13）从数据出发去构造程序；

（14）不要修补不好的程序，要重新编写。 4．输入和输出

（1）对所有的输入输出数据都要检验数据的合法性； （2）检查输入项的各种重要组合的合理性；

（3）输入格式要简单，以使得输入的步骤和操作尽可能简单； （4）输入数据时，应允许自由格式； （5）应允许缺省值；

（6）输入一批数据时，最好使用输入结束标志；

（7）以交互式输入输出方式进行输入时，要在屏幕上使用提示符明确输入的请求，同时在数据输入过程中和输入结束时，应在屏幕上给出状态信息；

（8）当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性；给所有的输出加注释，并设计输出报表格式。

第40页

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

（二）结构化程序设计 1．结构化程序设计的原则

结构化程序设计方法的主要原则：自顶而下、逐步求精，模块化，限制使用goto语句。 1）自顶而下

程序设计时，应先考虑总体，后考虑细节；先考虑全局，后考虑局部目标。即先从最上层总目标开始设计，逐步使问题具体化。 2）逐步求精

对复杂问题，应设计一些子目标作为过渡，逐步细化。 3）模块化

一个复杂问题，都是由若干个稍简单的问题构成的。模块化即是将复杂问题进行分解，即将解决问题的总目标分解成若干个分目标，再进一步分解为具体的小目标，把每一个小目标称作一个模块。 4）限制使用goto语句

goto语句可以提高效率，但对程序的可读性、维护性都造成影响，因此应尽量不用goto语句。 2．结构化程序设计的基本结构与特点

结构化程序设计是程序设计的先进方法和工具，采用结构化程序设计可以使程序结构良好、易读、易理解、易维护。

第41页

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

1）顺序结构

顺序结构即是顺序执行的结构，是按照程序语句行的自然顺序，一条一条语句地执行程序。 2）选择结构

选择结构又称分支结构，它包括简单选择和多分支选择结构。程序的执行是根据给定的条件，选择相应的分支来执行。 3）重复结构

重复结构又称循环结构，根据给定的条件，决定是否重复执行某一相同的或类似的程序段。利用重复结构可以大量简化程序行。 3．结构化程序设计原则和方法的应用

1．使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑；

2．选用的控制结构只允许有一个入口和一个出口；

3．程序语句组成容易识别的块，每块只有一个入口和一个出口； 4．复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现； 5．语言中所有没有的控制结构，应该采用前后一致的方法来模拟；

6．严格控制goto语句的使用：

（1）用一个非结构化的程序设计语言去实现一个结构化的构造； （2）若不使用goto语句会使功能模糊；

（3）在某种可以改善而不是损害程序可读性的情况下。

第42页

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

（三）面向对象的程序设计 1．关于面向对象方法

面向对象方法的本质，是主张从客观世界固有的事物出发来构造系统，提倡用人类在现实生活中常用的思维方法来认识、理解和描述客观事物，强调最终建立的系统能够反映问题域，即系统中的对象以及对象之间的关系能够如实地反映问题域中固有事物及其关系。

面向对象的优点： 1）与人类习惯的思维方法一致

传统的程序设计方法是以算法作为核心，将程序与过程相互独立。

面向对象方法和技术是以对象为核心，对象是由数据和容许的操作组成的封装体，与客观实体有直接的对应关系。对象之间通过传递消息互相联系，以实现模拟世界中不同事物之间的联系。 2）稳定性好

面向对象方法基于构造问题领域的对象模型，以对象为中心构造软件系统。它的基本方法是用对象模拟问题领域中的实体，以对象间的联系刻画实体间的联系。 3）可重用性好

软件的重用性是指在不同的软件开发过程中重复使用相同或相似的软件元素的过程。

第43页

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

4）易于开发大型软件产品

在使用面向对象进行软件开发时，可以把大型产品看作是一系列本质上相互独立的小产品来处理，降低了技术难度，也使软件开发的管理变得容易。 5）可维护性好

（1）利用面向对象的方法开发的软件稳定性比较好 （2）用面向对象的方法开发的软件比较容易修改 （3）用面向对象的方法开发的软件比较容易理解 （4）易于测试和调试 2．面向对象方法的基本概念 1）对象

在面向对象程序设计方法中，对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它执行的一组操作组成。

对象的基本特点： （1）标识的唯一性

对象是可区分的，并且由对象的内在本质来区分，而不是通过描述来区分。

（2）分类性

指可以将具有相同属性和操作的对象抽象成类。 （3）多态性

第44页

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

指同一个操作可以是不同对象的行为。 （4）封装性

从外面看只能看到对象的外部特征，即只需知道数据的取值范围和可以对该数据施加的操作，根本无需知道数据的具体结构以及实现操作的算法。

（5）模块独立性好

对象是面向对象的软件的基本模块，它是由数据及可以对这些数据施加的操作所组成的统一体，而且对象是以数据为中心的，操作围绕对其数据所需做的处理来设置，没有无关的操作。从模块的独立性考虑，对象内容各种元素彼此相结合得很紧密，内聚性强。 2）类和实例

将属性、操作相似的对象归为类。具有共同的属性、共同的方法的对象的集合，即是类。

类是对象的抽象，它描述了属于该对象的所有对象性质，而一个对象则是其对应类的一个实例。 3）消息

消息是一个实例与另一个实例之间传递的信息，它请求对象执行某一处理或回答某一个要求的信息，它统一了数据流和控制流。

消息只包含传递者的要求，它告诉接受者需要做哪些处理，并不指示接受者怎样去完成这些处理。 4）继承

继承是使用已有的类定义作为基础建立新类的定义技术。已有的

第45页

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

类可当作基类来引用，则新类相应地可作为派生类来引用。

继承即是指能够直接获得已有的性质和特征，而不必重复定义它们。 5）多态性

对象根据所接受的消息而做出动作，同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。

在面向对象技术中，多态性是指子类对象可以像父类对象那样使用，同样的消息可以发送给父类对象也可以发送给子类对象。

多态性机制增加了面向对象软件系统的灵活性，减少了信息冗余，而且显著提高了软件的可重用性可扩充性。 三、本章应考点拨

本章在考试中会出现约1个题目，所占分值大约占2分，是出题量较小的一章。本章内容比较少，也很简单，掌握住基本的概念就可以轻松应对考试了，所以在这部分丢分，比较可惜。

第三章 软件工程基础

一、学习目标与要求

1．了解软件工程的基本概念；

2．了解软件工程过程与软件的生命周期，以及软件工程的目标和原则；

3．了解利用结构化分析法进行软件工程中的需求分析的方法，

第46页

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

并了解需求分析的方法和需要完成的任务；

4．了解数据流图的使用方法；

5．了解如何利用结构化设计方法进行软件设计，并了解软件设计的一些常用用工具；

6．了解软件测试的目的和方法，以及软件测试的准则，了解常用的软件测试方法的区别和各自的功能与特点；

7．了解程序调试的方法和原则。 二、内容要点

（一）软件工程基本概念 1．软件定义与软件特点 1）软件的定义

与计算机系统的操作有关的计算机程序、规程、规则，以及可能有的文件、文档及数据。 2）软件的特点

（1）软件是一种逻辑实体，而不是物理实体，具有抽象性； （2）软件的生产与硬件不同，它没有明显的制作过程； （3）软件在运行、使用期间不存在磨损、老化问题；但为了适应硬件、环境以及需求的变化要进行修改，会导致一些错误的引入，导致软件失效率升高，从而使得软件退化；

（4）软件的开发、运行对计算机系统具有依赖性，受到计算机系统的限制，这导致了软件移植的问题；

第47页

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

（5）软件复杂性高，成本昂贵。软件开发需要投入大量、高强度的脑力劳动，成本高，风险大；

（6）软件开发涉及诸多的社会因素。许多软件的开发和运行涉及软件用户的机构设置，体制问题以及管理方式等，甚至涉及到人们的观念和心理，软件知识产权及法律等问题。 3）软件的分类

按功能分，可分为：

? 应用软件：为解决特定领域的应用而开发的软件

? 系统软件：是计算机管理自身资源，提高计算机使用效率并为计算机用户提供各种服务的软件

? 支撑软件（或工具软件）：介于系统软件和应用软件之间，协助用户开发软件的工具性软件，包括辅助和支持开发和维护应用软件的工具软件 2．软件危机与软件工程 1）软件危机

泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题。它主要表现在：

（1）软件需求的增长得不到满足，用户对系统不满意的情况经常发生；

（2）软件开发成本和进度无法控制。开发的成本超预算和开发周期的超期经常出现；

第48页

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

（3）软件质量难以保证；

（4）软件不可维护或维护程度非常低； （5）软件成本不断提高；

（6）软件开发生产率的提高赶不上硬件的发展和应用需求的增长。 2）软件工程

软件工程的定义：是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序。

软件工程包括3个要素：方法、工具和过程。 方法：完成软件工程项目的技术手段； 工具：支持软件的开发、管理、文档生成； 过程：支持软件开发的各个环节的控制、管理。 3．软件工程过程与软件生命周期 1）软件工程过程

软件工程过程把输入转化为输出的一组彼此相关的资源和活动。支持软件工程过程的两方面内涵：

（1）软件工程过程是指为获得软件产品，在软件工具支持下由软件工程师完成的一系列软件工程活动。它包括4种基本活动： ? P—软件规格说明。规定软件的功能及其运行时的限制； ? D—软件开发。产生满足规格说明的软件； ? C—软件确认。确认软件能够满足客户提出的要求；

第49页

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

? A—软件演进过程。为满足客户的变更要求，软件必须在使用的过程中演进。

（2）使用适当的资源（包括人员、硬软件工具、时间等），为开发软件进行的一组开发活动，在过程结束时将输入（用户要求）转化为输出（软件产品）。

软件工程过程是将软件工程的方法和工具综合起来，以达到合理、及时地进行计算机软件开发的目的。 2）软件生命周期

将软件产品从提出、实现、使用维护到停止使用退役的过程称为软件生命周期。即软件的生命周期就是软件产品从开始考虑其概念开始，到软件产品不能使用为止的整个时期都属于软件生命周期。一般包括可行性研究与需求分析、设计、实现、测试、交付使用以及维护等活动。这些活动可以有重复，执行时也可以有迭代。

生命周期的主要阶段： ? 软件定义 ? 软件开发 ? 软件维护

软件生命周期的主要活动阶段是：

（1）可行性研究与计划制定：确定待开发软件系统的开发目标和总的要求，给出它的功能、性能、可靠性以及接口等方面的可能方案，制定完成开发任务的实话计划；

（2）需要分析。对待开发软件提出的需求进行分析并给出详细

第50页

本文来源：https://www.bwwdw.com/article/stxx.html