(word完整版)计算机二级公共基础知识.doc资源-CSDN文库

需积分: 5 181 浏览量 2022-10-24 01:50:10 上传评论收藏 137KB DOC 举报

资源推荐

资源详情

资源评论

(word 完整版)计算机二级公共基础知识

二级共公基础知识教程

第一章数据结构与算法

1.1 算法

算法:是指解题方案的准确而完整的描述。

算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计.

算法的基本特征：是一组严谨地定义运算顺序的规则,每一个规则都是有效的，是明确的,此顺序将在有限的

次数下终止。特征包括：

(1）可行性；

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

（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含

义;

(4）拥有足够的情报。

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

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

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

算法的控制结构：顺序结构、选择结构、循环结构.

算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法.

算法复杂度：算法时间复杂度和算法空间复杂度。

算法时间复杂度是指执行算法所需要的计算工作量。

算法空间复杂度是指执行这个算法所需要的内存空间.

1。2 数据结构的基本基本概念

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

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

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

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

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

数据的逻辑结构包含:

（1)表示数据元素的信息;

(2)表示各数据元素之间的前后件关系。

数据的存储结构有顺序、链接、索引等。

线性结构条件：

（1）有且只有一个根结点；

（2）每一个结点最多有一个前件，也最多有一个后件。

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

1．3 线性表及其顺序存储结构

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

在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件.

非空线性表的结构特征：

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

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

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

性表的长度，当 n=0 时，称为空表。

线性表的顺序存储结构具有以下两个基本特点：

（1）线性表中所有元素的所占的存储空间是连续的；

（2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

ai 的存储地址为:ADR（ai）=ADR（a1)+（i—1）k，，ADR(a1）为第一个元素的地址，k 代表每个元素占的字

节数。

(word 完整版)计算机二级公共基础知识

顺序表的运算：插入、删除。（详见 14——16 页）

1．4 栈和队列

栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称

为栈底。

栈按照“先进后出”（FILO）或“后进先出"（LIFO）组织数据,栈具有记忆作用。用 top 表示栈顶位置，用

bottom 表示栈底。

栈的基本运算：（1）插入元素称为入栈运算；(2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋

给一个指定的变量，此时指针无变化。

队列是指允许在一端(队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear 指针指向队尾，front

指针指向队头.

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

队列运算包括（1)入队运算:从队尾插入一个元素；（2）退队运算：从队头删除一个元素.

循环队列:s=0 表示队列空，s=1 且 front=rear 表示队列满

1．5 线性链表

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

结点由两部分组成：（1）用于存储数据元素值，称为数据域；（2）用于存放指针，称为指针域，用于指向前

一个或后一个结点。

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

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

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

线性链表，HEAD 称为头指针，HEAD=NULL（或 0）称为空表，如果是两指针：左指针（Llink）指向前件结点,

右指针(Rlink）指向后件结点。

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

1．6 树与二叉树

一、树的基本概念

在树结构中,每一个结点只有一个前件，称为父结点,没有前件的结点只有一个，称为树的根结点,简称为树

的根。

在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点.

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

叶子结点的度为 0。

树的最大层次称为树的深度。

在一个算术表达式中，有运算符和运算对象。一个运算符可以有若干个运算对象.例职,取正（+）等只有一

个运算对象，称为单目运算符；二个运算对象称为双目运算符，三目运算符.

用树来表示算术表达式的原则如下:

表达式中的每一个运算符在树中对应一个结点，称为运算符结点。

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

运算对象中的单变量均为叶子结点.

二、二叉树及其基本性质

1、什么是二叉树

二叉树是一种很有用的非线性结构。二就树具有以下两个特点：

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

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

由以上特点可以看出，在二叉树中，每一个结点的度最大为 2，即所有子树（左子树或右子树）也均为二叉

树，而树结构中的每一个结点的度可以是任意的。另外，二叉树中的每一个结点的子树被明显地分为左子树

与右子树。可以没有其中的一个,也可以全没有。

二叉树的基本性质

性质 1:在二叉树的第 K 层上，最多有（K≥1）个结点。

性质 2:浓度为 M 的二叉树最多有 2m-1 个结点。

(word 完整版)计算机二级公共基础知识

深度为 m 的二叉树是指二叉树共有 m 层。

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

性质 4:具有 n 个结点的二叉树，其深度至少为[ log2n］+1,其中［ log2n]表示取的整数部分.

满二叉树与完全二叉树

满二叉树与完全二叉树是两种特殊形态的二叉树。

满二叉树

所谓满二叉树是指这样的一种二叉树；除最后一层外，每一层上的所有结点都有两个子结点.这就是说,在满

二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第 K 层上有 2K—1 个结点,且深度为 m 的满二

叉树有 2m-1 个结点。

完全二叉树

所谓完全二叉树是指这样的二叉树,除最后一层外，每一层上的结点数均达的最大值；在最后一层上只缺少

右边的若干结点.

列确切地说，如果从根结点起，对二叉树的结点自上而下、自左至右用自然数进行边疆编号,则深度为 m、且

有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 m 的满二叉树中编号从 1 到 n 的结点一一对应时，

称之为完全二叉树。

对于完全二叉树来说，叶子结点只可能在层次最大的两层上出现；对于任何一个结点，若其右分支下的子孙

结点的最大层次为 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 ；否则该结点无左子结点（显然也没有右子结点）。

若 2k+1≤n，则编号为 k 的结点的右子结点编号为 2k+1；否则该结点无右子结点.

三、二叉树的存储结构

二叉树的遍历

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

在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。

1、前序遍历（DLR）

所谓前序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点,然后遍历左子树，

最后遍历右子树;并且，在遍历左、右子树时,仍然先访问根结点，然后遍历左子树,最后遍历右子树。F，C，

A，D，B，E，G，H,P

2、中序遍历（LDR)

所谓中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点,

最后遍历右子树;并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树.A,C，

B,D，F，E，H，G，P

3、后序遍历（LRD）

所谓中序遍历是指在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，

最后访问根结点;并且,在遍历左、右子树时,仍然先遍历左子树，然后遍历右子树，最后访问根结点。A，B，

D,C,H，P，G,E，F

1。7 查找技术

一、顺序查找

顺序查找又称顺序搜索.顺序查找一般是指在线性表中查找指定的元素，其基本方法如下:从线性表的第一个

元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到（即查找成功）；若线性表中所

有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。

顺序查找的效率是很低的。以下两种情况只能采用顺序查找：

如果线性表无序表（即表中元素的排列是无序的)，则不管是顺序存储结构还是链式存储结构，都只能用顺

(word 完整版)计算机二级公共基础知识

序查找。

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

二、二分法查找

二分法查找只适用于存储的有序表。在此所说的有序表是指线性表的中元素按值非递减排列（即从小到大，

但允许相邻元素值相等）。

设有序线性表的长度为 n,被查元素为 x，则对分查找的方法如下：

将 x 与线性表的中间项进行比较：

若中间项的值等于 x，则说明查到,查找结束；

若 x 小于中间项的值，则在线性表的前半部分(即中间项以前的部分）以相同的方法进行查找;

若 x 大于中间项的值,则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。

这个过程一直进行到查找成功或子表长度为 0(说明线性表中没有这个元素）为止.

显然,当有序线性表为顺序存储时才能采用二分查找,并且，二分查找的效率要比顺序查找高得多。可以证明,

对于长度为 n 的有序线性表，在最坏情况下，二分查找只需要比较 log2n 次,而顺序查找需要比较 n 次。

1.8 排序技术

一、交换类排队序法

所谓交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序法与快速排序法都属于

交换类的排序方法。

1、冒泡排序法

基本过程如下：

首先,从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面

的元素大于后面的元素，则将它们互换,称之为消去了一个逆序。放最大值

然后，从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小.若相邻两个元素中，

后面的元素大于前面的元素，则将它们互换，这样就又消去了一个逆序。放最小值.

重复上述过程，直到剩下的线性有变空为止，此时的线性表已经变为有序.

假设线性表的长为 n，则在最坏情况下，冒泡排序需要经过 n/2 遍的葱馨往后的扫描和 n/2 遍的从后往前的

扫描，需要的比较的次数为 n(n—1）/2.

2、快速排序法

快速排序法也是种互换类的排序法，但由于它比冒泡排序法的速度快,因此称之为快速排序法。

基本思想如下：

从线性表中选取一个元素,设 T，将线性表后面小于 T 的元素移到前，而前大于 T 的元素移支后面，结果就将

线性表分成了两部分（称为两个子表)，T 插入到其分界线的位置处,这个过程称为线性表的分割。通过对线

性表的一次分割，就以 T 为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于 T，

而后面子表中的所有元素均不小于 T。

如此反复，则此时的线性表就变成了有序表。

步骤：首先，在表的第一个，中间一个与最后一个元素中选取中项，设为 P（K）,并将 P（K）赋给 T,再将表

中的第一个元素移到 P（K）的位置上。

然后设置两个指针 i 和 j 分别指向表的起始与最后的位置。反复操作以下两步:

(4）将 j 逐渐减小，并逐次比较 P（j）与 T，直到发现一个 P（j）<T 为止，将 P（j）移到 P(i)位

置上。

（5）将 i 逐渐减小,并逐次比较 P（i）与 T，直到发现一个 P(i)>T 为止，将 P(i）移到 P（j）位

置上.

上述两个操作交替进行，直到指针 i 与 j 指向同一个位置（即 i=j）为止，此时将 P（i)的位置上。

分割需要记忆，用栈来实现。

二、插入类排序法

1、简单插入排序法

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

一般来说，假设线性中前 j-1 元素已经有序，现在要将线性表中第 j 个元素插入到前面的有序子表中,插入

过程如下：

(word 完整版)计算机二级公共基础知识

道德将第 j 个元素放到一个变量 T 中，然后从有序子表的最后一个元素（即线性表中第 j—1 个元素）开始，

往前逐个与 T 进行比较，将大于 T 的元素均依次向后移动一个位置,直到发现一个元素不大于 T 为止，此时

就将 T（即原线性表中的第 j 个元素)插入到刚移出的空位置上，有序子表的长度就变为 j 了。效率与冒泡法

相同

在最坏情况下,简单插入排序需要 n（n—1）/2 次比较.

2、希尔排序法

基本思想如下：

将整个无序序列分割成若干小的子序列分别进行插入排序。

子序列的分割方法如下：

将相隔某个增量 H 的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当 H 减到 1 时,进行一

次插入排序，排序就完成。增量序列一般取 h=n/2k（k=1，2,…[log2n]，其中 n 为待排序序列的长度。

其效率与增量序列有关。在最坏情况下，需要的比较次数为 O（Ｎ１.５）。

三、选择类排序法

１、简单选择排序法

基本思想：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的

方法，直到子表空为止。

简单选择排序法在最坏情况下需要比较 n（n—1)/2/次。

２、堆排序法

方法：（1）首先将一个无序序列建成堆。

（2）然后将堆顶元素(序列中的最大项)与堆中最后一个元素交换(最大项应该在序列的最后）。不考虑已经

换到最后的那个元素,只考虑前 n—1 个元素构成的子序,显然,该子序列已不是堆，但左、右子树仍为堆，可

以将该子序列调事为堆。反复做第（2）步,真到剩下的子序列为空为止.适用规模较大的线性表，在最坏情

况下,堆排序需要比较的次数为 O（nlog2n)。

1.7 查找技术

一、顺序查找

顺序查找又称顺序搜索.顺序查找一般是指在线性表中查找指定的元素，其基本方法如下：从线性表的第一

个元素开始,依次将线性表中的元素与被查元素进行比较，若相等则表示找到（即查找成功）；若线性表中所

有的元素都与被查元素进行了比较但都不相等,则表示线性表中没有要找的元素（即查找失败）。

顺序查找的效率是很低的.以下两种情况只能采用顺序查找:

如果线性表无序表（即表中元素的排列是无序的）,则不管是顺序存储结构还是链式存储结构，都只能用顺

序查找。

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

二、二分法查找

二分法查找只适用于存储的有序表。在此所说的有序表是指线性表的中元素按值非递减排列（即从小到大，

但允许相邻元素值相等）。

设有序线性表的长度为 n，被查元素为 x，则对分查找的方法如下:

将 x 与线性表的中间项进行比较：

若中间项的值等于 x，则说明查到,查找结束；

若 x 小于中间项的值，则在线性表的前半部分(即中间项以前的部分）以相同的方法进行查找；

若 x 大于中间项的值，则在线性表的后半部分(即中间项以后的部分）以相同的方法进行查找。

这个过程一直进行到查找成功或子表长度为 0（说明线性表中没有这个元素）为止.

显然，当有序线性表为顺序存储时才能采用二分查找，并且,二分查找的效率要比顺序查找高得多。可以证

明，对于长度为 n 的有序线性表，在最坏情况下，二分查找只需要比较 log2n 次，而顺序查找需要比较 n 次。

1.8 排序技术

一、交换类排队序法

所谓交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序法与快速排序法都属于

交换类的排序方法.

1、冒泡排序法

剩余32页未读，继续阅读

评论收藏

内容反馈

智慧安全方案

粉丝: 3702
资源: 59万+

(word完整版)计算机二级公共基础知识.doc

(word完整版)计算机二级公共基础知识题库.doc

(完整word版)2017计算机二级公共基础知识完整.doc

(完整word版)计算机二级公共基础知识辅导讲义.doc

(完整word版)计算机二级公共基础知识(全).doc

(word完整版)计算机二级公共基础知识(全).doc

(完整word版)计算机二级公共基础知识(全)-(2).doc

(word完整版)国家计算机二级考试公共基础知识教材.doc

(word完整版)全国计算机二级公共基础知识--复习.doc

(完整word版)全国计算机二级考试公共基础知识完整版整合.doc

(完整word版)计算机等级考试二级MS-Office基础知识.doc

(完整word版)计算机二级ms-office考试有关公共基础知识点总结.doc

(完整版)计算机应用基础课程标准.doc

计算机应用基础综合实训指导书.doc

江西电大2018秋-计算机应用基础.doc

计算机信息处理综合作业考核大纲.doc

oracle学习文档 笔记 全面 深刻 详细 通俗易懂 doc word格式 清晰 连接字符串

会计理论考试题

KepOPC DA2UA实现从OPCDA到OPCUA的转换及读写互操作

kkFileView-4.4.0-SNAPSHOT.tar.gz

“未来工厂”建设导则.pdf

2024年Java基础面试题，附带详细解析答案

腾讯QQ秀立项调研PPT

5G介绍PPT.pptx

海盗派测试分析.pdf

2024年最新最全面的Java后端面试资料

CHATGPT训练指令模板.docx

基于SpringBoot的个人博客系统设计与实现-论文.pdf

全国31省份各省数字经济水平测算熵值法+主成分测算原始数据+结果（2011-2022年）

OMML2MML.XSL

最新资源

oracle学习文档笔记全面深刻详细通俗易懂 doc word格式清晰连接字符串