全国计算机等级考试二级公共基础知识考纲.docx
《全国计算机等级考试二级公共基础知识考纲.docx》由会员分享，可在线阅读，更多相关《全国计算机等级考试二级公共基础知识考纲.docx（108页珍藏版）》请在冰点文库上搜索。
全国计算机等级考试二级公共基础知识考纲
全国计算机等级考试二级公共基础知识考纲
考试内容
一、基本数据结构与算法
1、算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。
2、数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。
3、线性表的定义；线性表的顺序存储结构及其插入与删除运算。
4、栈和队列的定义；栈和队列的顺序存储结构及其基本运算。
5、线性单链表、双向链表与循环链表的结构及其基本运算。
6、树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。
7、顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。
二、程序设计基础
1、程序设计方法与风格。
2、结构化程序设计。
3、面向对象的程序设计方法，对象，方法，属性及继承与多态性。
三、软件工程基础
1、软件工程基本概念，软件生命周戎概念，软件工具与软件开发环境。
2、结构化分析方法，数据流图，数据字典，软件需求规格说明书。
3、结构化设计方法，总体设计与详细设计。
4、软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统
测试。
5、程序的调试，静态调试与动态调试。
四、数据库设计基础
1、数据库的基本概念：
数据库，数据库管理系统，数据库系统。
2、数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。
3、关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。
4、数据库设计方法和步骤：
需求分析、概念设计、逻辑设计和物理设计的相关策略。
考试方式：
公共基础的考试方式为笔试，与C语言（VisualBASIC、VisualFoxPro、Java、Access、Visual
C++）的笔试部分合为一张试卷。
公共基础部分占全卷的30分。
公共基础知识有10道选择题和5道填空题。
第一章数据结构与算法
一、内容要点
（一）算法
1．算法的基本概念：
算法是指解题方案的准确而完整的描述。
即是一组严谨地定义运算顺序的规则，并且
每一个规则都是有效的，且是明确的，没有二义性，同时该规则将在有限次运算后可
终止。
2、算法的基本特征
（1）可行性：
由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的，因此，它总是受到计算工具的限制，使执行产生偏差。
如：
计算机的数值有效位是有限的，当大数和小数进行运算时，往往会因为有效位数的影响而使小数丢失，因此，在算法设计时，应该考虑到这一点。
（2）确定性：
算法的设计必须是每一个步骤都有明确的定义，不允许有模糊的解释，也不能有多义性。
例
如，一个实际的问题，小宝和萍萍共有12个苹果，小宝比萍萍多4个，请问小宝和萍萍各
x
y
12
x和y的值，公
有几个苹果？
这个问题，我们可以立一个方程
y
来求解，要求
x
4
式是正确的，但如何让计算能够进行计算，我们的算法不能把公式直接输进去，而应该设计
出解题的步骤和过程。
即设计的算法是计算工具所能够正常解决问题的过程。
（3）有穷性：
算法的有穷性，即在一定的时间是能够完成的，即算法应该在计算有限个步骤后能够正常结束。
例如，在数学中的无穷级数，在计算机中只能求有限项，即计算的过程是有穷的。
（4）拥有足够的情报：
算法的执行与输入的数据和提供的初始条件相关，不同的输入或初始条件会有不同的输出结果，提供准确的初始条件和数据，才能使算法正确执行。
3、算法的基本要素：
一是数据对象的运算和操作，二是算法的控制结构。
（1）算法中对数据的运算和操作：
算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。
即算法是计算机所能够处理的操作所组成的指令
序列。
（2）算法的控制结构
①算法的功能不仅取决于所选用的操作，而且还与各操作之间的顺序有关。
②在算法中，操作的执行顺序又称算法的控制结构，一般的算法控制结构有三种：
顺序结构、选择结构和
循环结构。
③在算法描述是，有相关的工具对这三种结构进行描述，常用的描述工具有：
流程图、N-S结构图和算法
描述语言等。
4、算法设计的基本方法：
为用计算机解决实际问题而设计的算法，即是计算机算法。
通常的算法设计有如
下几种：
（1）列举法：
列举法的基本思想是，根据提出的问题，列举出所有可能的情况，并用问题中给定的条件检验哪些是满足条件的，哪些是不满足条件的。
列举法通常用于解决“是否存在”或“有哪些
可能”等问题。
例如，我国古代的趣味数学题：
“百钱买百鸡”、“鸡兔同笼”等，均可采用
列举法进行解决。
使用列举法时，要对问题进行详细的分析，将与问题有关的知识条理化、
完备化、系统化，从中找出规律。
（2）归纳法：
归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。
归纳是
一种抽象，即从特殊现象中找出一般规律。
但由于在归纳法中不可能对所有的情况进行列举，因此，该方法得到的结论只是一种猜测，还需要进行证明。
（3）递推：
递推，即是从已知的初始条件出发，逐次推出所要求的各个中间环节和最后结果。
其中初始条件或问题本身已经给定，或是通过对问题的分析与化简而确定。
递推的本质也是一种归纳，递推关系式通常是归纳的结果。
例如，裴波那契数列，是采用递推的方法解决问题的。
（4）递归：
在解决一些复杂问题时，为了降低问题的复杂程序，通常是将问题逐层分解，最后归结为一些最简单的问题。
这种将问题逐层分解的过程，并没有对问题进行求解，而只是当解决了最后的问题那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的方法。
递归分为直接递归和间接递归两种方法。
如果一个算法直接调用自己，称为直接递归调用；如果一个算法A调用另一个算法B，而算法B又调用算法A，则此种递归称为间接递归调用。
（5）减半递推技术：
减半递推即将问题的规模减半，然后，重复相同的递推操作。
如，一元二次方程求解。
（6）回溯法：
有些实际的问题很难归纳出一组简单的递推公式或直观的求解步骤，也不能使用无限的列举。
对于这类问题，只能采用试探的方法，通过对问题的分析，找出解决问题的线索，然后沿着这个线索进行试探，如果试探成功，就得到问题的解，如果不成功，再逐步回退，换别的路线进行试探。
这种方法，即称为回溯法。
如人工智能中的机器人下棋。
5、算法复杂度：
算法的复杂度包括时间复杂度和空间复杂度。
（1）时间复杂度：
即实现该算法需要的计算工作量。
算法的工作量用算法所执行的基本运算次数来计算。
同一个问题规模下，如果算法执行所需要的基本次数取决于某一特定输入时，可以用以
下两种方法来分析算法的工作量：
算法工作量
=f（n）
①平均性态：
用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。
设
x是某个可能输入
中的某个特定输入，p（x）
是x出现的概率，t（x）
是算法在输入为x时所执行的基本运算次数，
则算法的平均性态定义为：
A（n）
p（x）t（x）。
Dn表示当规模为
n时，算法执行时
xDn
所有可能输入的集合。
②最坏情况复杂度指在规模为n时，算法所执行的基本运算的最大次数。
它定义为：
W（n）max{t（x）}
xDn
例如，在具有n个元素的数列中搜索一个数x。
n1
n
③平均性态：
A（n）
piti
i1
i1
q
（n1）q
q）n
i（1q）n
（1
n
2
即该数在数列中任何位置出现的数列是相同的，也有可能不存在，存在的概率为q。
如果有一半的机会存在，则概率q为1/2，平均性态：
1
（n1）
1
3
A（n）
2
（1
2
）n
n
2
4
如果查找的元素一定在数列中，则每个数存在的概率即为1，则平均性态为：
A（n）
n1n
22
④最坏情况分析：
即要查找的元素X在数列的最后或不在数列中，显然，它的最坏情况复杂度为：
W（n）max{ti|1in1}n
（2）算法的空间复杂度：
指要执行该算法所需要的内存空间。
算法所占用的内存空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间，
如执行过程中工作单元以及某种数据结构所需要的附加存储空间等。
（二）数据结构的基本概念
1、概念：
数据结构是指相互有关联的数据元素的集合。
它包括以下两个方面：
表示数据元素的信息；表示各数据之间的前后件关系。
（1）数据的逻辑结构：
是指反映数据元素之间的逻辑关系的数据结构。
数据的逻辑结构有两个要素：
数据
元素的集合，记作D；数据之间的前后件关系，记作R。
则数据结构B=（D，R）
（2）数据的存储结构：
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构，或数据的物理结构。
即数据存储时，不仅要存放数据元素的信息，而且要存储数据元素之间的
前后件关系的信息。
通常的数据存储结构有顺序、链接、索引等存储结构。
2、数据结构的图形表示
①数据结构的图形表示有两个元素：
中间标有元素值的方框表示数据元素，称为数据结点；用有向线段表示数据元素之间的前后件关系，即有向线段从前件结点指向后件结点。
②注意：
在结构图中，没有前件的结点称为根结点，没有后件的结点称为终端结点，也称叶子结点。
3、线性结构与非线性结构：
（1）如果一个数据元素都没有，该数据结构称为空数据结构；在空数据结构中插入一个新的元素后数据结
构变为非空数据结构；将数据结构中的所有元素均删除，则该数据结构变成空数据结构。
（2）如果一个非空的数据结构满足如下条件，则该数据结构为线性结构：
①有且只有一个根结点；每一个结点最多只有一个前件，也最多只有一个后件线性结构又称线性表。
②注意：
在线性结构表中插入或删除元素，该线性表仍然应满足线性结构。
（3）如果一个数据结构不满足线性结构，则称为非线性结构。
（三）线性表及其顺序存储结构
1、基本概念：
（1）线性表是最常用的数据结构，它由一组数据元素组成。
（2）注意：
这里的数据元素是一个广义的数据元素，并不仅仅是指一个数据。
如，矩阵、学生记录表等。
（3）非空线性表的结构特征：
有且只有一个根结点，它无前件；有且只有一个终端结点，它无后件；除根结点和终端结点之外，所有的结点有且只有一个前件和一个后件。
线性表中
结点的个数称为结点的长度n。
当n=0时，称为空表。
2、顺序存储结构
（1）顺序存储结构的特点：
线性表中所有的元素所占的存储空间是连续的；线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
（2）通常，顺序存储结构中，线性表中每一个数据元素在计算机存储空间中的存储地址由该元素在线性表中的位置序号唯一确定。
（3）线性表的顺序存储结构下的基本运算：
①在指定位置插入一个元素；
②删除线性表中的指定元素；
③查找某个或某些特定的元素；
④线性表的排序；
⑤按要求将一个线性表拆分为多个线性表；
⑥将多个线性表合并为一个线性表；
⑦复制线性表；
⑧逆转一个线性表。
3、线性表的基本操作
（1）顺序表的插入运算：
在顺序存储结构的线性表中插入一个元素。
注意：
找到插入位置后，将插入位置开始的所有元素从最后一个元素开始顺序后移。
另外，在定义线性表时，一定要定义足够的空间，否则，将不允许插入元素。
（2）顺序表的删除运算：
在顺序在存储结构的线性表中删除一个元素。
注意：
找到删除的数据元素后，从该元素位置开始，将后面的元素一一向前移动，在移动完成后，线性表的长度减1。
（四）栈和队列
1、栈及其基本运算
（1）栈：
栈是一种特殊的线性表，它是限定在一端进行插入和删除的线性表。
它的插入和删除只能在表的一端进行，而另一端是封闭的，不允许进行插入和删除操作。
在栈中，允许插入和删除操作一端称为栈顶，不允许插入和删除操作的一端则称为栈底。
栈顶的元素总是最后被插入的元素，也是
最先被删除的元素。
它遵循的原则是：
先进后出或后进先出。
堆栈指针总是指向栈顶元素的。
（2）栈的顺序存储及其运算：
在栈的顺序存储空间S（1：
m）中，S（bottom）通常为栈底元素，S（top）
为栈顶元素。
Top=0表示栈空；top=m表示栈满。
①入栈运算：
在栈的顶部插入一个新元素。
操作方式：
将栈顶指针加1，再将元素插入至指针所指的位置。
②退栈运算：
退栈运算即将栈顶元素取出并赋给一个指定的变量。
操作方式是：
先将栈顶元素赋给指定的
变量，再将栈顶指针减1。
③读栈顶元素：
将栈顶元素赋给某一指定变量，但栈顶指针不变。
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值的定义：
1表示队列空
s
1表示队列满
判断队列空与队列满的条件下：
队列空的条件：
s=0；队列满的条件：
s=1、front=rear
①入队运算：
即在队尾加入一个新元素。
这个运算有两个基本操作：
首先，将队尾指针加1，即rear=rear+1，
当rear=m+1时，置rear=1，然后，将新元素插入到队尾指针指向的位置。
当循环队列非空（s=1），
且front=rear时，队列满，不能进行入队操作。
此情况称“上溢”。
②退队操作：
即将队首的元素赋给一个指定的变量。
该运算也有两个基本操作：
首先，将排头指针加
1，
即front=front+1，当front=m+1时，置front=1，然后，将排头指针指向的元素赋给指定
的变量。
当循环队列为空（s=0）时，不能进行退队运算。
此种情况称为“下溢”。
（五）线性链表
1、基本概念：
前面的线性表均是采用顺序存储结构及在顺序存储结构下的运算。
（1）顺序存储的优点：
结构简单；运算方便。
（2）顺序存储结构的缺点：
①要在顺序存储的线性表中插入一个新元素或删除一个元素时，为了保证插入或删除后的线性表仍然为顺
序存储。
在插入或删除元素时，需要移动大量的数据元素，因此运算效率较低。
②如果一个线性表分配顺序存储空间后，如果出现线性表的存储空间已满，但还需要插入元素时，会发生
“上溢”错误。
③在实际应用时，可能有多个线性表同时使用存储空间，这样给存储空间的分配带来问题，有可能使有的
队列空间不够或过多造成浪费。
·基于上述情况，对于大的线性表或元素变动频繁的大线性表不宜采用顺序存储结构，而应采用链式存储
结构。
（3）链式存储结构：
①假设每一个数据结点对应一个存储单元，该存储单元称为存储结点，简称结点。
在链式存储方式中，要求每一个结点由两部分组成：
一部分用于存放数据元素，你为数据域；另一部分用于存放指针，称为指针域。
该指针用于指向该结点的前一个或后一个结点。
②在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系不一致，而数据元素之间的逻辑关系是由指针域来确定的。
链式存储结构既可以用于线性结构，也可用于非线性结构。
（4）线性链表
·线性表的链式存储结构称为线性链表。
将存储空间划分成若干的小块，每块占用若干个字节，这些小块称为存储结点。
将存储结点分为两个部分，一部分用于存储数据元素的值，称为数据域；另一部分用于
存储元素之间的前后件关系，即存放下一个元素在存储序号（即存储地址），即指向后件结点，称为指
针域。
在线性链表中用一个专门的指针HEAD指向线性链表中第一个数据元素的结点（即存放第一个元
素的地址）。
线性表中最后一个元素没有后件，因此，线性链表中的最后一个结点的指针域为空（用Null
或0表示），表示链终结。
在线性链表中，各元素的存储序号是不连续的，元素间的前后件关系与位置关系也是不一致的。
在线性链表中，前后件的关系依靠各结点的指针来指示，指向表的第一个元素的指
针HEAD称为头指针，当HEAD=NULL时，表示该链表为空。
对于线性链表，可以从头指针开始，沿着各结点的指针扫描到链表中的所有结点。
这种线性链表称为线性单链表，即可以从表头开始向后扫描链表
中的所有结点，而不能从中间或表尾结点向前扫描位于该结点之前的元素。
这种链表结构的缺点是不能任意地对链表中的元素按下同的方向进行扫描。
在某些应用时，如果对链表中的元素设置两个指针域，
一个为指向前件的指针域，称为左指针（LLink），一个为指向后件的指针域，称为右指针（RLink）。
则
这种链表是双向链表。
（5）带链的栈
·带链的栈即是用来收集计算机存储空间中的所有空闲的存储结点，这种带链的栈称为可利用栈。
当需要存储结点时，即从可利用的栈的顶部取出栈顶结点；当系统要释放一个存储结点时，将该结点空间放回到可利用栈的栈顶。
即在计算机中所有空闲的空间，均可以以结点的方式链接到可利用栈中，随着其他线性链表中结点的插入与删除，可利用栈处于动态变化之中，即可利用栈经常要进行退栈和入栈操作。
（6）带链的队列：
队列也是线性表，也可利用链式存储结构来进行保存。
2、线性链表的基本运算
①在链表中包含指定元素的结点之前插入一个新元素；
②在链表中删除包含指定元素的结点；
③将两个线性链表按要求合并成一个线性链表；
④将一个线性链表按要求进行分解；
⑤逆转线性链表；
⑥复制线性链表；
⑦线性链表的排序；
⑧线性链表的查找。
（1）线性链表中查找指定的元素
·在线性链表中查找元素X：
从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为X为止。
元素的查找，经常是为了进行插入或删除操作而进行的，因此，在查找时，往往是需要记录下该结点的前一个结点。
（2）线性链表的插入：
线性链表的插入即在链式存储结构的线性表中插入一个新元素。
在线性链表中包含
元素x的结点之前插入新元素b，插入过程：
①从可利用栈中取得一个结点，设该结点号为p，即取得的结点的存储序号存放在变量p中。
并置结点p
的数据域为插入的元素值b。
②在线性链表中寻找包含元素x的前一个结点，该结点的存储序号为q。
③将结点p插入到结点q之后。
具体的操作：
首先，使结点p插入到结点q之后（即结点q的后件结点），
然后，使结点q的指针域内容改为指向结点p。
·线性链表的插入操作，新结点是为来自于可利用栈，因此不会造成线性表的溢出。
同样，由于可利用栈
可被多个线性表利用，因此，不会造成存储空间的浪费，大家动态地共同使用存储空间。
（3）线性链表的删除：
线性链表的删除，是在链式存储结构下的线性表中删除指定元素的结点。
操作方式：
①在线性表中找到包含指定元素x的前一个结点p
②将该结点p后的包含元素x的结点从线性链表中删除，然后将被删除结点的后一个结点q的地址提供给
结点p的指针域，即将结点p指向结点q。
③将删除的结点送回可利用栈。
·从以上的删除操作可见，删除一个指定的元素，不需要移动其他的元素即可实现，这是顺序存储的线性
表所不能实现的。
同时，此操作还可更有效地利用计算机的存储空间。
3、循环链表及其基本操作
·在线性链表中，虽然对数据元素的插入和删除操作比较简单，但由于它对第一个结点和空表需要单独处理，使得空表与非空表的处理不一致。
循环链表，即是采用另一种链接方式，它的特点如下：
（1）在循环链表中增加一个表头结点，其数据域为任意或根据需要来设置，指针域指向线性表的第一个元素的结点。
循环链表的头指针指向表头结点。
（2）循环链表中最后一个结点的指针域不是空的，而是指向表头结点。
在循环链表中，所有结点的指针构成一个环状链。
在循环链表中，只要指出表中任何一个结点的位置，均可以从它开始扫描到所有的结点，而线性链表做不到，线性链表是一种单向的链表，只能按照指针的方向进行扫描。
循环链表中设
置了一个表头结点，因此，在任何时候都至少有一个结点，因此空表与非空表的运算相统一。
（六）树与二叉树
1、树的基本概念：
树是一种简单的非线性结构。
在树结构中，数据元素之间有着明显的层次结构。
在树的图形表示中，用直线连接两端的结点，上端点为前件，下端点为后件。
A
BCD
EFGHI
JKL
MN
·在树结构中，每一个结点只有一个前件，称为父结点。
如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）表达式中
升级会员 