全国计算机二级公共基础知识汇总.doc

二级公共基础知识总结(30 分：10 选择+5 填空)

复习与应试建议：

　　1．考生的复习必须遵守：“80/20 的原则”

　　二级考试的公共知识部分的覆盖面广，至少涵盖了计算机应用专业的四门核心课程：算法与数据结构、程序设计基础、

软件工程基础和数据库。事实上，这些课程本身的涉与面就很广，难度系数较大。因此，这些课程甚至也是计算机专业学生

基本知识和面向对象程序设计的最常见概念；软件工程基础部分主要考查软件工程的基本概念与软件生命周期的各个阶段的

基础知识；数据库基础部分主要考查数据库基本概念、数据模型、关系代数基础知识、数据库设计方法和步骤。对常见考点

的准确把握会使考生避免盲目学习，从而能够轻松面对考试。

　　二级考试中要求的知识点都是最基本的、最简单的，真正需要“灵活”掌握的考点极少。很多考生在考试过程中可能已

经发现，该部分的题目“会做就是不懂”。所以建议在复习过程中不要急于“灵活”，其实等到把基本的知识点掌握后自然就

“灵活”了。

　　公共知识部分仅占 30%分，题目相对简单。因此，在答题过程中，这部分要争取速度快、准确度高。

　　总的原则是如果一道题在两分钟没有任何思路，就应该跳过此题，把时间给后面的题目。记住：二级考试是一种合格考

试，不是竞赛，与格就行了。

使用说明：

算法是一组严谨地定义运算顺序的规则，每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。所以其四个

基本特征包括：

（1）确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性；

（2）有穷性，算法必须能在有限的时间做完，即能在执行有限个步骤后终止；

（3）可行性，算法原则上能够精确地执行；

（4）拥有足够的情报。

算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。

指令系统：一个计算机系统能执行的所有指令的集合。

基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。

算法的三种基本控制结构：顺序结构、选择结构、循环结构。

1.2 数据结构的基本概念

数据结构：指相互有关联的数据元素的集合。

数据结构研究的三个方面：

（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；

（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；

（3）对各种数据结构进行的运算。

数据的逻辑结构应包含：

线性结构的条件，(一个非空数据结构)：

（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。

非线性结构：不满足线性结构条件的数据结构。

1.3 线性表与其顺序存储结构

线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。

在复杂线性表中，由若干项数据元素组成的数据元素称为记录；

由多个记录构成的线性表称为文件。

非空线性表的结构特征：

（1）且只有一个根结点 a1，它无前件；

（2）有且只有一个终端结点 an，它无后件；

（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。

1.4 线性链表

数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。

结点由两部分组成：(1) 用于存储数据元素值，称为数据域；

(2)用于存放指针，称为指针域，用于指向前一个或后一个结点。

在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻

辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。

链式存储方式即可用于表示线性结构，也可用于表示非线性结构。

线性单链表中，HEAD 称为头指针，HEAD=NULL（或 0）称为空表。

如果是双项链表的两指针：左指针（Llink）指向前件结点，右指针（Rlink）指向后件结点。

线性链表的基本运算：查找、插入、删除。

1.5 栈和队列

栈按照“先进后出”（FILO）或“后进先出”（LIFO）组织数据，栈具有记忆作用。

栈的基本运算：(1) 入栈运算，在栈顶位置插入元素；

(2) 退栈运算，删除元素(取出栈顶元素并赋给一个指定的变量)；

(3)读栈顶元素，将栈顶元素赋给一个指定的变量，此时指针无变化。

用 rear 指针指向队尾，用 front 指针指向队头元素的前一个位置。

队列是“先进先出”（FIFO）或“后进后出”（LILO）的线性表。

队列运算包括：(1) 入队运算：从队尾插入一个元素；(2)退队运算：从队头删除一个元素。

队列的顺序存储结构一般采用队列循环的形式。

1.6 树与二叉树

在树结构中，每一个结点只有一个前件，称为父结点。

没有前件的结点只有一个，称为树的根结点，简称树的根。

每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。

在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。

二叉树的特点：(1) 非空二叉树只有一个根结点；

(2) 每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。

满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则 k 层上有 2

完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。

二叉树基本性质：

(1)在二叉树的第 k 层上，最多有 2

（k=1,2….n），有以下结论：

补充：增加度为 1 的结点不会影响二叉树的叶子结点数，每增加一个度为 2 的结点便会增加一个叶子结点，没有度为 2 的

结点时叶子结点数为 1。

已知完全二叉树有 x 个结点，求其叶子结点数：

①确定层数为 k； ②第 k 层的结点数 y=x-(2

③第 k-1 层的叶子结点数 n=2

二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。

二叉树的遍历：

（树根在第一，下走不跳结点）

（有左先左，再找右，后寻根，到最右一路上行，树根在最后）