计算机二级公共基础知识

全国ຫໍສະໝຸດ Baidu算机等级考试
二级公共基础知识
第一章 数据结构与算法(30%)
考试大纲
1. 算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复 杂度）。 2. 数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表 示；线性结构与非线性结构的概念。 3. 线性表的定义；线性表的顺序存储结构及其插入与删除运算。 4. 栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5. 线性单链表、双向链表与循环链表的结构及其基本运算。 6. 树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序 和后序遍历。 7. 顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类 排序，插入类排序）。
HEAD ∧
… …
∧
HEAD
…
HEAD
树及其基本概念
树是一种简单的非线性结构，在树 中，所有的数据元素之间具有明显 的层次性关系。
树是(n≥0)个结点的有限集合，在 任意一棵非空树中：
(1)有且仅有一个特定的结点称为根 结点。
(2)当n>1时，其余的结点可分为m 个 中互每不个相有交限的子子集集本身T1,又T2是,…一Tm棵，树其， 并且称为根的子树。
树型结构的常用术语
结点的度 一个结点的子树的
个数； Q：结点A、G的度数？
A
树的度 树中所有结点度的最 大值；Q：右图中树的度？ 终端结点 度为0的结点；
Q：图中叶子结点有几个？7
B
CD
E
F GH I
J KM
非终端结点 度不为0的结点；
Q：图中非终端结点有几个？ 5
树型结构的常用术语
结点的层次 树中根结点的层
1. 数据集合中各数据元素之间的逻辑关系，即 数据的逻辑结构。
2. 在对数据进行处理时，各数据元素在计算机 中的存储关系，即数据的存储结构。
3. 对各种数据结构进行的运算。
数据的逻辑结构
数据逻辑结构是对数据 元素之间存在的逻辑关 系的描述，它可以用一 个数据元素的集合和定 义在此集合上的若干关 系表示。
历左子树和遍历右子树可如同遍历二叉树一样"递归"进行。
先序遍历二叉树
中序遍历二叉树
后序遍历二叉树
在循环队列为空或为满时，均有front=rear，因此需 要设置标志s进行区分，定义s=0表示队列为空，s=1 表示队列非空。
单链表
线性表的链式存储结构的特点是用一组任意的存 储单元(可以连续，也可以不连续)存储线性表的数 据元素，为了表示每个数据元素ai与其直接后继元 素ai+1之间的逻辑关系，对数据元素ai来说，除了 存储其本身的信息(数据域)之外，还需要存储其后 继元素的存储位置信息(指针域)。
D0
5
G
11 0 B 0
13 0 H 0
10P0
i L(i) V(i) R(i)
1
0
P
0
2
0
A
0
3
4
6
F
9
5
13
G
1
6
2
C
8
7
8
11
D
0
9
0
E
5
10
11
0
B
0
12
13
0
H
0
二叉树的遍历
二叉树的遍历指不重复地访问二叉树的所有结点。从二叉树的结 构定义得知，二叉树是由"根结点"、"左子树"和"右子树"三部分 构成，则遍历二叉树的操作可分解为"访问根结点"、"遍历左子树 "和"遍历右子树"三个子操作，并且由二叉树的递归定义可知，遍
知识点归纳
算法的基本概念 所谓算法是指解题方案的准确而完整的
描述。严格来说，一个算法必须具有以 下五个主要特征：
算法的基本特征
一个算法应该具有以下五个重要的特征：
有穷性 确定性 输入 输出 可行性
一个算法必须保证执行有限步之后结束；
算法的每一步骤必须有确切的定义；
一个算法有0个或多个输入，以刻画运算对象的 初始情况，所谓0个输入是指算法本身定义了初 始条件； 一个算法有一个或多个输出，以反映对输入数据 加工后的结果。没有输出的算法是毫无意义的； 算法原则上能够精确地运行
从以上定义可知，满二叉树也是完全二叉树，反之则不然。
A
B
C
满二叉树
D
EF
最大层的结点 均向左靠齐
完全二叉树
二叉树的基本性质
性质5 如果对一棵有 n 个结点的完全二叉树（其深度为 [log2n] +1）的结点按层序（从第1层到第[log2n] +1 层，每 层从左到右）从1起开始编号，则对任一编号为 i 的结点 (1≤i≤n)，则:
↑
↑
基地址
一个数据元素所占存储量
线性表的插入和删除运算
插入运算是指在线性表的某个指定位置增加一个 新结点。
一般情况下，要在第i(1≤i≤n)个元素之前插入一个 新元素时，首先要从最后一个元素开始，直到第i 个元素之间共n-i+1个元素依次向后移动一个位置， 然后将新元素插入到第i项。
删除运算是指撤销结构中的某个结点。 一般情况，要删除第i(1≤i≤n)个元素，要从第i+1
单链表的插入和删除
pa
b
px
x
pa
b
px
x
pa
b
c
双向链表和循环链表
在双向链表中的结点包含两个指针域，其中一个指向直接后继，另 一个指向直接前驱。
循环链表的特点是表中最后一个结点的指针域指向第一个结点，整 个链表成为一个由链指针相链接的环。据此，从表中任一节点出发 均可找到表中其它结点。在循环链表中增加了一个表头结点，其指 针域指向第一个元素结点，头指针则指向头结点。
[log2n] +1
满二叉树和完全二叉树
满二叉树除最后一层外，每一层上的所有结点都有两个子节点，也就 是说每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1 个结点，且深度为m的满二叉树有2m-1个结点。
完全二叉树除最后一层外，每一层上的结点数均达到最大值，在最后 一层上只缺少右边的若干结点。具有n个结点的完全二叉树，其深度为 [log2n] +1。
集合为空的树简称为空树；树中的 元素称为结点。
树的主要术语
结点的度：结点拥有的子树数。 叶节点(终端结点)：度为0的结点。 双亲、孩子和兄弟：结点的子树的根节点称为
该结点的孩子，该结点称为孩子结点的双亲结 点。同一个双亲结点的孩子互称为兄弟。 层次：结点的层次从根开始定义，根为第一层， 根的孩子为第二层。 深度：树中结点的最大层次称为树的深度或高 度。
(1) 如果 i=1，则编号为 i 的结点是二叉树的根，无双亲； 如果 i>1，则其双亲结点 parent(i)的编号是[i/2]。
(2) 如果 2i>n，则编号为 i 的结点无左孩子（编号为 i 的结 点为叶子结点）；否则其左孩子结点 lChild(i) 的编号是 2i 。
(3) 如果 2i+1>n，则编号为 i 的结点无右孩子；否则其右 孩子结点 rChild(i) 的编号是结点 2i+1。
二叉树是另一种树型结构，其特 点是每个结点至多有两棵子树， 并且二叉树的子树有左右之分， 其顺序不能任意颠倒。
二叉树的基本性质
性质1 在二叉树的第i层上至多有2i-1个结点（i≥1） 性质2 深度为k的二叉树至多有2k -1个结点（k≥1） 性质3 对任何一棵二叉树T，如果其终端结点数为
n0，度为2的结点数为n2 ，则：n0 =n2+1 性质4 具有n个结点的二叉树，其深度至少为
①
次为1，根结点子树的根为第2层，
以此类推；
②B
A CD
树的深度 树中所有结点层次的 ③ E
最大值； Q：图中树的深度？
④
F GH I J KM
二叉树
二叉树是n(n≥0)个数据元素的 有限集，它或为空集,或者含有 唯一的称为根的元素，且其余元 素分成两个互不相交的子集，每 个子集自身也是一棵二叉树，分 别称为根的左子树和右子树。
算法的基本概念
算法的组成要素
算法中对数据的运算和操作
算法的控制结构
算法设计基本方法
列举法 基本运算和操作
归纳法 递推
算术运算
递归 减半递推
关系运算
回溯法
逻辑运算
数据传输
控制结构
顺序 选择 循环
算法的复杂度
算法的复杂度可分为时间复杂度和空间 复杂度，是衡量算法优劣的量度。
二叉树的链式存储结构
在二叉树的链式存储结构中，每个结点设置三个域， 即数据域，左指针域和右指针域，两个指针域分别 存储左右子树根节点的存储位置，即指针。
Lchild value Rchild
L(i) V(i) R(i)
F
C
E
二叉树的链式存储结构
A
D
G
B
H
P
BT
BT
4
F
6
C
90E
2 0 A0 8
通常用指针top指示栈顶位置，用指针bottom指示栈底位置。
入栈
出栈
栈顶 top
an
……
a2
栈底 bottom
a1
栈的顺序存储及运算
用一维数组S(1:m)作为栈的顺序存储空间，m为栈 的最大容量。top=0表示栈为空，top=m表示栈 满。
栈的操作
入栈：在栈顶位置插入一个新元素，栈顶指针top加1。 退栈：取出栈顶元素并赋值给一个指定的变量，栈顶指
线性表的顺序存储
线性表的顺序存储结构用一组地址连续的存储单元依次存放线 性表中的数据元素，即以“存储位置相邻”表示“位序相继的 两个数据元素之间的前驱和后继的关系，并以表中第一个元素 的存储位置作为线性表的起始地址，称作线性表的基地址。
所有数据元素的存储位置均可由第一个数据元素的存储位置得到
ADR(ai) = ADR(a1) + (i-1)×C
个元素开始，直到第n个元素，共n-i个元素依次向 前移动一个位置。
栈
栈是限定仅在表的一端进行插入和删除操作的线性表。允许插入和 删除的一端称为栈顶，另一端称为栈底。
栈顶元素总是最后被插入的元素，从而也是最先被删除的元素；栈 底元素总是最先被插入，也是最后被删除的元素。因此，栈是一种 后进先出的线性表。
针top减1。 取栈顶元素：将栈顶元素的值赋给一个指定的变量，不
删除栈顶元素，栈顶指针不变。
队列
队列是一种先进先出的线性表，它只允许在表的一端插入元 素(队尾)，在另一端删除元素(队头)。通常定义头指针front 指向队头元素的前一个位置，定义尾指针rear指向队尾元素 的位置。
队列是一种先进先出的数据结构。 向队尾插入一个元素的操作称为入队，从队头删除一个元素
线性结构和非线性结构
线性结构
在数据元素的非空有限集合中，线性结构的逻辑特征 如下：
存在一个唯一的被称为“第一个”的数据元素 存在一个唯一的被称为“最后一个”的数据元素 除第一个之外，集合中的每个数据元素均有且只有一
个直接前驱 除最后一个之外，集合中的每个数据元素均有且只有
一个直接后继
非线性结构
1.算法的时间复杂度 算法的时间复杂度是指执行算法所需要
的工作量。一般情况下，算法中的基本 操作重复执行的次数是问题规模n的某个 函数f(n)。
算法的复杂度
算法的空间复杂度 算法的空间复杂度是指执行这个算法所
需要的内存空间。空间复杂度作为算法 所需存储空间的量度
数据结构
利用计算机进行数据处理是计算机应用的一 个重要领域。数据结构主要研究和讨论以下 三个方面的问题：
的操作称为退队。
退队
A
B
C
D
E
F
Front
Rear
入队
循环队列
将队列存储空间的最后一个位置绕到第一个位置，形 成逻辑上的环状空间。
循环队列初始状态为空，即front=rear=m。
入队操作时，rear加1，若rear=m+1，则置rear=1； 退队操作时，front加1，若front=m+1，则置front=1。
指针域中存储的信息称为指针或链，N个结点链 接成一个链表，即为线性表的链式存储结构。由 于结点中只包含一个指针域，故称为单链表。
单链表
通常以单链表中第一个数据元素的存储地址 作为作为单链表的地址，称为头指针。整个 链表的存储必须从头指针开始(顺序存取)， 头指针指示链表中第一个结点的存储位置。 最后一个数据元素没有直接后继，其指针域 为空。
与数据在计算机中的存 储位置无关，是独立于 计算机的。
数据的存储结构
数据的存储结构是数据元素及其关系在计算机存储器中 的表示。存储结构的主要内容是指在存储空间中使用一 个存储结点来存储一个数据元素，在存储空间中建立各 存储结点之间的关联，来表示数据元素之间的逻辑关系。
常见的存储结构：
顺序存储结构 链式存储结构 索引存储结构 散列存储结构
非线性结构的逻辑特征是：一个结点可能有多个直接 前驱和直接后继，树和图都属于非线性结构。
线性表
通常以下列 n 个数据元素的序列”表示 线性表 ： (a1,a2 ,...,ai ,...,an)
序列中数据元素的个数 n 定义为线性表 的表长；n=0 时的线性表被称为空表。 称 i 为ai在线性表中的位序。