导图社区计算机二级公共基础知识

计算机二级公共基础知识

基于未来教育书籍做的思维导图，这部分是公共基础知识部分，内容全面，

编辑于2020-02-29 04:31:03

魏伟

计算机二级公共基础知识

社区模板帮助中心，点此进入>>

魏伟

相似推荐
大纲

公共基础知识

算法

含义：解决问题的操作步骤。算法不等于程序，程序可以描述算法

特征

可行性

确定性

有穷性

拥有足够情报

复杂度

时间复杂度

含义：执行算法所需要的计算工作量

算法时间复杂度≠算法程序执行所需具体时间

衡量：利用算法所执行的基本运算次数赖衡量，与问题规模有关

在具体分析算法工作量时，同一问题规模下，算法所执行的次数还可能与特定的输入有关。

空间复杂度

含义：执行这个算法所需要的内存空间

组成

输入数据所占的存储空间（即问题规模）

程序本身所占的存储空间

算法输入过程所需要的额外空间

算法执行程序过程中的工作单元

某种数据结构所需要的附加存储空间

算法原地工作：额外空间不随问题规模的变化而变化

减低方法：压缩存储技术（减少输入数据所占存储空间以及额外空间）

数据结构

含义：相互有关联的数据元素的集合

要素

数据

含义：需要处理的数据元素的集合（元素具备共同特征）

结构

含义：集合中各种元素间存在的某种关系

通常把两两元素之间的关系用前后件关系（直接前驱与直接后关系）来描述

包含

数据的逻辑结构

数据元素之间逻辑关系（即前后件关系）

数据的存储结构

数据逻辑结构在计算机存储空间中的存放方式（数据的物理结构）

表示

B=(D,R)

B表示数据结构，D表示数据元素集合，R是D上的数据元素的关系集合

划分

线性结构

含义：非空的数据结构；有且只有一个根节点；每个节点最多只有一个前件和后件

在数据结构中，线性结构习惯称为线性表

名称：线性表（是有限序列）

表示：（a1,a2,...ai,...,an)

存储结构

顺序存储结构

元素一个接一个地存储在相邻区域（也称作顺序表）

特征

元素存储所占空间是连续的

按照逻辑循序排列

链接存储

线性链表（链表/单链表）

第一个元素没有前件，指向链表第一个元素的指针称为头指针（head）

最后一个元素没有后件，最后一个指针域为空用NULL或者0表示

各元素之间可以连续/不连续，位置关系与逻辑关系不一致

前后件关系由存储节点的指针来表示

带链的栈

把栈组织成一个单链表，这种数据结构称为带链的栈

带链的队列

带链的队列就是用一个单链表来表示队列

循环链表

顺序表：优，随机存储任意节点，逻辑关系不需要额外空间；缺，插入与删除效率低，不便于扩充，不便于动态分配；链表与之相反

特殊线性表

栈

栈顶：允许插入与删除

栈底：不允许插入与删除

原则：后进先出或先进后出

基本运算

入栈

退栈

读栈顶元素

实现方法

顺序方式

链接方式

队列

队头：允许删除元素

队尾：允许插入元素

原则：先进先出或后进后出

循环队列

含义：将队列存储空间的最后一个位置绕到第一个位置，形成环状空间

队头指针front的后一个位置到队尾指针real之间的所有元素都为队列中的元素

实现方法

顺序方式

链接方式

非线性结构

除了线性结构的条件，主要指树形结构和网状结构

树

父节点；子节点和叶节点；度；深度；子树

度：一个节点所拥有的后件个数称为该节点的度

所有节点中最大的度称为树的度

深度:定义一棵树的根节点所在层次为1，其他节点在第几层，该节点的深度为几

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

节点数=节点度+1

二叉树

特点

可以为空

非空二叉树有且仅有一个根节点

每个节点最多两棵子树

子树有左右之分，次序不能颠倒

性质

第K层上最多有2∧(K-1)个节点

深度为M的二叉树，最多有2∧M-1个节点

任何一颗二叉树，度为0的节点(叶节点)总是比度为2的节点多一个

具有N个节点的二叉树，其深度至少为[㏒₂n]+1，其中[㏒₂n]表示㏒₂n取整数的部分

具有n个节点的完全二叉树的深度为[㏒₂n]+1

满二叉树

除最后一层外，每层上所有节点都有两个子节点的二叉树

完全二叉树

除最后一层外，每层上所有节点均达到最大值，在最后一层上只缺少右边的若干节点的二叉树

特点

叶子节点只可能出现在最后两层

对于任意节点，若右子树的深度为m则左子树的深度为m+1

采用链式存储结构

在计算机中，二叉树通常采用链式存储结构

数据域

指针域

顺序存储

满二叉树

完全二叉树

二叉树的遍历

不重复的访问二叉树中的所有节点

先左后右

遍历原则

前序遍历

根左右

中序遍历

左根右

后序遍历

左右根

已知前序遍历和中序遍历可以唯一确定二叉树，已知后序遍历和中序遍历可以唯一确定二叉树

查找技术

顺序查找：从线性表的第一个元素开始，逐个将线性表中的元素与被查找的元素进行比较，若成功停止查找，不成功继续查找直至整个线性表查找完毕，查找失败

最好：第一个就是要找的元素1次

最坏：最后一个元素才是要找的元素，或者是没有找到元素n次

平均情况：n/2

只能用顺序查找

线性表是无序的

线性表是有序的，但存储结构为链式存储

二分法查找

条件

顺序存储结构

线性表是有序的（从小到大排序，但允许相邻元素相等）

过程

X值与中间值进行比较如果相同，结束查找

X值＜中间值，则在线性表的前半部分以二分法继续查找

X值＞中间值，则在线性表的后半部分以二分法继续查找

排序技术

含义：将无序序列整理成按从小到大排序的有效序列

交换类排序法

含义：借助数据元素的交换来进行排序的一种方法

冒泡排序法

两两相邻数据元素之间的比较和交换，不断地消去逆序（某个元素后存在比其小的元素），直到所有数据元素有序为止

最坏：对长度n的线性表进行排序，冒泡排序需要比较的次数为n(n-1)/2

快速排序

在待排序的n个元素中抽取一个，以这个元素K作为分割标准，把所有小于K的元素，移到K的左边，把所有大于K的元素，移到K的右边。

以K为分界线，把线性表分成两个子表（成为一趟排序），两个子表重复上述过程。直至子表长度为1

在最坏情况下需要进行n(n-1)/2次比较，但实际的排序效率要比冒泡排序高

插入类排序

含义：将每次将一个待排序的元素，按其值大小插入到前面已经排好序的子表中

简单插入排序

把n个待排序的元素看成一个有序表和一个无序表，开始时有序表只有一个元素，每次取一个无序表中的元素插入到有序表的正确位置。最后有序表长度为n，无序表长度为0

最坏的情况：排序进行n(n-1)/2次

希尔排序

先取一个整数d₁小于n，把所有元素分成d₁个组，所有距离为d₁倍数的元素放在一起，组成子序列对每个子序列进行简单插入排序。然后去d₂小于d₁重复上述过程，直到di=1

最坏的情况：n∧r

选择类排序法

含义：每次从待排序序列中选出值最小的一个，顺序放在已排好序的有序子表的后面，直至排好序

简单选择排序法

从n个带排序的元素中选择最小的一个与第一个交换，再从剩下的元素中找到最小的元素与第二个交换，重复以上过程直至排序完成。

最坏的情况：排序进行n(n-1)/2次

堆排序法

若有n个元素的序列，将元素按照顺序组成一个完全二叉树，满足Hi≥H2i且Hi≥H2i+1或者Hi≤H2i且Hi≤H2i+1

Hi≥H2i且Hi≥H2i+1为大根堆，所有节点值大于或者等于左右子节点的值

Hi≤H2i且Hi≤H2i+1为小根堆，所有节点值小于或者等于左右子节点的值

最坏的结果：n㏒₂n

没有数据元素☞

程序设计基础

程序的质量

方法

技术

风格

源程序文档化

数据说明风格

语句结构

输入与输出

程序设计

结构化程序设计

原则

自顶向下

逐步求精

模块化

限制使用goto语句

基本结构

循序结构

选择结构

循环结构

一个入口一个出口

优点：易于理解、使用和维护，提高效率，降低开发成本

面向对象程序设计

优点：与人类思维一致，稳定性好，可重用性好，容易开发大型软件产品，可维护性好

对象

数据(也叫属性)

方法(也叫操作)

特点：标识唯一性，分类性，多态性，封装性，模块独立性好

类和实例

类：具有共同属性和共同方法的对象的集合

实例：即类中的一个具体对象

消息

对象间通信的手段

继承

类与类之间可以继承，一个子类可以重新定义其父类的全部描述，也可以定义自己的属性和操作。

继承具有传递性

多态性

子类对象可以和父类对象那样使用，消息可以发给父类对象也可以发给子类对象。

软件工程基础

计算机系统

计算机软件

组成