没有合适的资源?快使用搜索试试~ 我知道了~
最新全国计算机等级考试二级基础辅导讲义(.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 13 浏览量
2021-10-30
22:04:25
上传
评论
收藏 318KB PDF 举报
温馨提示
试读
21页
最新全国计算机等级考试二级基础辅导讲义(.pdf
资源推荐
资源详情
资源评论
全国计算机等级考试——二级公共基础知识辅导讲义
第一章 数据结构与算法
1.1 算法
1、算法是指解题方案的准确而完整的描述。换句话说,算法是对特定问题求解步骤的一种
描述。
* :算法不等于程序,也不等于计算方法。程序的编制不可能优于算法的设计。
2、算法的基本特征
(1)可行性。针对实际问题而设计的算法,执行后能够得到满意的结果。
(2)确定性。每一条指令的含义明确,无二义性。并且在任何条件下,算法只有唯一的一
条执行路径,即相同的输入只能得出相同的输出。
(3)有穷性。算法必须在有限的时间内完成。有两重含义,一是算法中的操作步骤为有限
个,二是每个步骤都能在有限时间内完成。
(4)拥有足够的情报。算法中各种运算总是要施加到各个运算对象上,而这些运算对象又
可能具有某种初始状态, 这就是算法执行的起点或依据。 因此, 一个算法执行的结果总是与
输入的初始数据有关, 不同的输入将会有不同的结果输出。 当输入不够或输入错误时, 算法
将无法执行或执行有错。一般说来,当算法拥有足够的情报时,此算法才是有效的;而当提
供的情报不够时,算法可能无效。
* :综上所述,所谓算法,是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的,
且是明确的,此顺序将在有限的次数下终止。
3、算法复杂度主要包括时间复杂度和空间复杂度。
(1)算法时间复杂度是指执行算法所需要的计算工作量,可以用执行算法的过程中所需基
本运算的执行次数来度量。
(2)算法空间复杂度是指执行这个算法所需要的内存空间。
1.2 数据结构的基本概念
1、数据结构是指相互有关联的数据元素的集合。
2、数据结构主要研究和讨论以下三个方面的问题:
(1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构。
数据的逻辑结构包含: 1)表示数据元素的信息; 2)表示各数据元素之间的前后件关系。
(2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构。
数据的存储结构有顺序、链接、索引等。
1)顺序存储。它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里,结点间的逻辑
关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。
2)链接存储。它不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系是由附
加的指针字段表示的。由此得到的存储表示称为链式存储结构。
3)索引存储:除建立存储结点信息外,还建立附加的索引表来标识结点的地址。
* :数据的逻辑结构反映数据元素之间的逻辑关系, 数据的存储结构 (也称数据的物理结构)
是数据的逻辑结构在计算机存储空间中的存放形式。 同一种逻辑结构的数据可以采用不同的
存储结构,但影响数据处理效率。
(3)对各种数据结构进行的运算。
1
3、数据结构的图形表示
一个数据结构除了用二元关系表示外, 还可以直观地用图形表示。 在数据结构的图形表示中,
对于数据集合 D中的每一个数据元素用中间标有元素值的方框表示,一般称之为数据结点,
并简称为结点; 为了进一步表示各数据元素之间的前后件关系, 对于关系 R中的每一个二元
组,用一条有向线段从前件结点指向后件结点。
4、数据结构分为两大类型:线性结构和非线性结构。
(1)线性结构(非空的数据结构)条件: 1)有且只有一个根结点; 2)每一个结点最多有
一个前件,也最多有一个后件。
* :常见的线性结构有线性表、栈、队列和线性链表等。
(2)非线性结构:不满足线性结构条件的数据结构。
* :常见的非线性结构有树、二叉树和图等。
1.3 线性表及其顺序存储结构
1、线性表由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位
置是线性的。 线性表是由 n(n ≥0) 个数据元素组成的一个有限序列, 表中的每一个数据元素,
除了第一个外,有且只有一个前件,除了最后一个外,有且只有一个后件。线性表中数据元
素的个数称为线性表的长度。线性表可以为空表。
* :线性表是一种存储结构,它的存储方式:顺序和链式。
2、线性表的顺序存储结构具有两个基本特点: ( 1)线性表中所有元素所占的存储空间是连
续的;( 2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
* :由此可以看出, 在线性表的顺序存储结构中, 其前后件两个元素在存储空间中是紧邻的,
且前件元素一定存储在后件元素的前面,可以通过计算机直接确定第 i 个结点的存储地址。
3、顺序表的插入、删除运算
(1)顺序表的插入运算:在一般情况下,要在第 i (1≤ i ≤n)个元素之前插入一个新元素
时,首先要从最后一个(即第 n 个)元素开始,直到第 i 个元素之间共 n-i+1 个元素依次向
后移动一个位置,移动结束后,第 i 个位置就被空出,然后将新元素插入到第 i 项。插入结
束后,线性表的长度就增加了 1。
* :顺性表的插入运算时需要移动元素,在等概率情况下,平均需要移动 n/2 个元素。
(2)顺序表的删除运算:在一般情况下,要删除第 i (1≤i ≤ n)个元素时,则要从第 i+1
个元素开始, 直到第 n 个元素之间共 n-i 个元素依次向前移动一个位置。 删除结束后, 线性
表的长度就减小了 1。
* :进行顺性表的删除运算时也需要移动元素,在等概率情况下,平均需要移动( n-1 )/2
个元素。插入、删除运算不方便。
1.4 栈和队列
1、栈及其基本运算
栈是限定在一端进行插入与删除运算的线性表。
在栈中, 允许插入与删除的一端称为栈顶, 不允许插入与删除的另一端称为栈底。 栈顶元素
总是最后被插入的元素, 栈底元素总是最先被插入的元素。 即栈是按照“先进后出”或“后
进先出”的原则组织数据的。
栈具有记忆作用。
栈的基本运算: 1)插入元素称为入栈运算; 2)删除元素称为退栈运算; 3)读栈顶元素是
将栈顶元素赋给一个指定的变量,此时指针无变化。
栈的存储方式和线性表类似,也有两种,即顺序栈和链式栈。
2
2、队列及其基本运算
队列是指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。尾指针
(Rear )指向队尾元素,头指针( front )指向排头元素的前一个位置(队头)。
队列是“先进先出”或“后进后出”的线性表。
队列运算包括: 1)入队运算:从队尾插入一个元素; 2)退队运算:从队头删除一个元素。
循环队列及其运算:所谓循环队列,就是将队列存储空间的最后一个位置绕到第一个位置,
形成逻辑上的环状空间,供队列循环使用。在循环队列中,用队尾指针 rear 指向队列中的
队尾元素, 用排头指针 front 指向排头元素的前一个位置, 因此, 从头指针 front 指向的后
一个位置直到队尾指针 rear 指向的位置之间,所有的元素均为队列中的元素。
* :循环队列中元素的个数 =rear-front 。
1.5 线性链表
1、线性表顺序存储的缺点: ( 1)插入或删除的运算效率很低。在顺序存储的线性表中,插
入或删除数据元素时需要移动大量的数据元素;( 2)线性表的顺序存储结构下,线性表的
存储空间不便于扩充;( 3)线性表的顺序存储结构不便于对存储空间的动态分配。
2、线性链表:线性表的链式存储结构称为线性链表,是一种物理存储单元上非连续、非顺
序的存储结构, 数据元素的逻辑顺序是通过链表中的指针链接来实现的。 因此, 在链式存储
方式中,每个结点由两部分组成:一部分用于存放数据元素的值,称为数据域;另一部分用
于存放指针,称为指针域,用于指向该结点的前一个或后一个结点(即前件或后件),如下
图所示:
线性链表分为单链表、双向链表和循环链表三种类型。
在单链表中, 每一个结点只有一个指针域, 由这个指针只能找到其后件结点, 而不能找到其
前件结点。因此,在某些应用中,对于线性链表中的每个结点设置两个指针,一个称为左指
针,指向其前件结点;另一个称为右指针,指向其后件结点,这种链表称为双向链表,如下
图所示:
3、线性链表的基本运算
(1)在线性链表中包含指定元素的结点之前插入一个新元素。
* :在线性链表中插入元素时,不需要移动数据元素,只需要修改相关结点指针即可,也不
会出现“上溢”现象。
(2)在线性链表中删除包含指定元素的结点。
* :在线性链表中删除元素时,也不需要移动数据元素,只需要修改相关结点指针即可。
(3)将两个线性链表按要求合并成一个线性链表。
(4)将一个线性链表按要求进行分解。
(5)逆转线性链表。
(6)复制线性链表。
(7)线性链表的排序。
(8)线性链表的查找。
* :线性链表不能随机存取。
4、循环链表及其基本运算
data next
数据域 指针域
a
1
a
2
a
n-1
HEAD
,
a
n
^
(a) 结点结构 (b) 一个非空的线性链表示意图
右指针左指针 数据域
(a) 结点结构
^
a
1
^
a
n
a
2
,
HEAD
(b) 一个非空的双向链表示意图
3
在线性链表中, 其插入与删除的运算虽然比较方便, 但还存在一个问题, 在运算过程中对于
空表和对第一个结点的处理必须单独考虑, 使空表与非空表的运算不统一。 为了克服线性链
表的这个缺点,可以采用另一种链接方式,即循环链表。
与前面所讨论的线性链表相比,循环链表具有以下两个特点: 1)在链表中增加了一个表头
结点, 其数据域为任意或者根据需要来设置, 指针域指向线性表的第一个元素的结点, 而循
环链表的头指针指向表头结点; 2)循环链表中最后一个结点的指针域不是空,而是指向表
头结点。即在循环链表中,所有结点的指针构成了一个环状链。
下图 a 是一个非空的循环链表,图 b 是一个空的循环链表:
循环链表的优点主要体现在两个方面: 一是在循环链表中, 只要指出表中任何一个结点的位
置,就可以从它出发访问到表中其他所有的结点, 而线性单链表做不到这一点; 二是由于在
循环链表中设置了一个表头结点, 在任何情况下, 循环链表中至少有一个结点存在, 从而使
空表与非空表的运算统一。
* :循环链表是在单链表的基础上增加了一个表头结点,其插入和删除运算与单链表相同。
但它可以从任一结点出发来访问表中其他所有结点,并实现空表与非空表的运算的统一。
1.6 树与二叉树
1、树的基本概念
树是一种简单的非线性结构。在树这种数据结构中,所有数据元素之间的关系具有明显的
层次特性。
在树结构中,每一个结点只有一个前件,称为父结点。没有前件的结点只有一个,称为树
的根结点,简称树的根。每一个结点可以有多个后件,称为该结点的子结点。没有后件的
结点称为叶子结点。
在树结构中,一个结点所拥有的后件的个数称为该结点的度,所有结点中最大的度称为树
的度。树的最大层次称为树的深度。
2、二叉树及其基本性质
(1)什么是二叉树
二叉树是一种很有用的非线性结构, 它具有以下两个特点: 1)非空二叉树只有一个根结点;
2)每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。
* :根据二叉树的概念可知,二叉树的度可以为 0(叶结点)、 1(只有一棵子树)或 2(有
2 棵子树)。
(2)二叉树的基本性质
性质 1 在二叉树的第 k 层上,最多有 个结点。
性质 2 深度为 m的二叉树最多有个 个结点。
性质 3 在任意一棵二叉树中,度数为 0 的结点(即叶子结点)总比度为 2 的结点多一个。
性质 4 具有 n 个结点的二叉树,其深度至少为 ,其中 表示取
的整数部分。
3、满二叉树与完全二叉树
满二叉树:除最后一层外,每一层上的所有结点都有两个子结点。
完全二叉树: 除最后一层外, 每一层上的结点数均达到最大值; 在最后一层上只缺少右边的
若干结点。
* :根据完全二叉树的定义可得出:度为 1 的结点的个数为 0 或 1。
下图 a 表示的是满二叉树,下图 b 表示的是完全二叉树:
)1(2
1
k
k
12
m
1][log
2
n ][log
2
n n
2
log
4
完全二叉树还具有如下两个特性:
性质 5 具有 n 个结点的完全二叉树深度为 。
性质 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;否则该结点无右子结点。
4、二叉树的存储结构
在计算机中,二叉树通常采用链式存储结构。
与线性链表类似,用于存储二叉树中各元素的存储结点也由两部分组成:数据域和指针域。
但在二叉树中,由于每一个元素可以有两个后件(即两个子结点),因此,用于存储二叉树
的存储结点的指针域有两个:一个用于指向该结点的左子结点的存储地址,称为左指针域;
另一个用于指向该结点的右子结点的存储地址,称为右指针域。
* :一般二叉树通常采用链式存储结构,对于满二叉树与完全二叉树来说,可以按层序进行
顺序存储。
5、二叉树的遍历
二叉树的遍历是指不重复地访问二叉树中的所有结点。二叉树的遍历可以分为以下三种:
(1)前序遍历( DLR):若二叉树为空,则结束返回。否则:首先访问根结点,然后遍历左
子树,最后遍历右子树;并且,在遍历左右子树时,仍然先访问根结点,然后遍历左子树,
最后遍历右子树。
(2)中序遍历( LDR):若二叉树为空,则结束返回。否则:首先遍历左子树,然后访问根
结点, 最后遍历右子树; 并且, 在遍历左、 右子树时, 仍然先遍历左子树, 然后访问根结点,
最后遍历右子树。
(3)后序遍历( LRD):若二叉树为空,则结束返回。否则:首先遍历左子树,然后遍历右
子树, 最后访问根结点, 并且, 在遍历左、 右子树时, 仍然先遍历左子树, 然后遍历右子树,
最后访问根结点。
1.7 查找技术
查找:根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素。
查找结果:(查找成功:找到;查找不成功:没找到。)
平均查找长度:查找过程中关键字和给定值比较的平均次数。
1、顺序查找
基本思想: 从表中的第一个元素开始, 将给定的值与表中逐个元素的关键字进行比较, 直到
两者相符,查到所要找的元素为止。否则就是表中没有要找的元素,查找不成功。
11 12 13 14
3 5 6
1 2
0
987
4
10
3 6
1 2
0
987
54
(a) 满二叉树 (b) 完全二叉树
1][log
2
n
剩余20页未读,继续阅读
资源评论
hfj20200606
- 粉丝: 0
- 资源: 168
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功