计算机二级公共知识速通

定义：对解题方案的准确而完整的描述。

要素：

1. 对数据对象的运算和操作

2. 算法的控制结构，即运算或操作间的顺序

指令：计算机上可以执行的基本操作

计算机工作的本质是：取指令、分析指令和执行指令

计算机软件——>指令系统——>计算机硬件

算法复杂度 体现在所需资源的大小

 1. 时间复杂度：执行算法所需要的计算工作量

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

即数据+结构

数据:需要处理的数据元素的集合 

结构:即关系，集合中各个元素之间存在的某种关系

数据的结构分为数据的逻辑结构和存储结构

逻辑结构:各数据元素之间逻辑关系

逻辑结构主要分为两种:

线性结构 符合以下两种条件

1 . 有且只有一个根节点

2 . 每个节点最多有一个前件 最多有一个后件

非线性结构

不满足以上两种条件

存储结构:逻辑结构在计算机存储空间的存放方式

存储结构分为两种：

1. 顺序存储结构 适用于线性的存储结构

2. 链式存储结构 在每个节点中至

线性表:某些元素构成的有限序列

既可以是顺序存储结构，也可以是链式存储结构

线性链表（也简称为链表）：用一组不连续的存储单元存储线性表的每个元素（还要一个头指针）

每个元素除了需要存储自身的信息外，还要存储一个指示后件的信息

一个存储节点包括：数据域和指针域

栈：是一种特殊的线性表

规则：先进后出，后进先出

插入与删除都限定在表的一端进行

队列：也是一种特殊的线性表

规则：先进先出，后进后出

在一端进行插入，在另一端进行删除

栈和队列都可以用链表来表示

二叉树

满二叉树：除了最后一层，每一层节点都有两个子节点的二叉树

完全二叉树：除了最后一层，每一层节点都有两个子节点的二叉树，最后一层只缺少右边的节点

满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

二叉树的存储结构一般为链式存储结构

一个存储结构包括左指针域 数据域 右指针域

n0（叶子节点） = n2 + 1

对象

客观世界的任何实体，可以是实体的抽象，也可以是人为的概念

由对象名属性操作组成

特点： 标识唯一性

分类性

多态性

封装性

模块独立性好

面向对象方法的重要概念：

对象

类和实例

消息

继承

多态性

结构化程序设计

自顶向下，逐步求精，模块化，限制使用goto语句

结构化分析

需求分析阶段 ：

数据流图 箭头表示数据流 方框表示源 圆表示加工 

数据字典 对数据流中所有元素定义的集合

详细设计:

程序流程图 方框表示一个加工步骤 菱形表示一个逻辑条件 箭头表示控制流

软件设计

内聚性 一个模块内部各个元素彼此结合的紧密程度

耦合性 不同模块彼此间互相依赖的紧密程度

应该要求内聚尽可能高，耦合尽可能低

投影运算 π_A(R) R是表，A是要取出的属性  e.g. π_性别(学生表) 会提取性别这一列

选择运算 σ_c(R) R是表，c是要取出的属性  e.g.  σ_哈哈(学生表) 会筛选哈哈这一行

笛卡尔积R × S 得到 R 和 S 属性的并集

自然连接 R ⋈ S 将所有同名且值相等的属性作为桥梁连接