计算机二级公共基础知识

随着社会的发展，计算机和互联网的应用在生活中愈发深入，计算机二级证书也变成了大学生必备证书，本导图主要导入了计算机二级Ms Office选择题的部分内容。

公共基础知识

数据结构与算法

算法

概念及其基本特征

概念

对解题方法完整而准确的描述，即解决问题的操作步骤（≠程序）

基本特征

可行性

步骤可以实现，执行效果达到预期目的

确定性

步骤明确，不模棱两可，不准有多义性

有穷性

有限的时间完成

拥有足够的情报

算法要有一定的输入数据和必须要有输出结果

算法的基本要素

对数据对象的运算和操作

算术运算

逻辑运算

关系运算

算法的控制结构

算法中各操作之间的执行顺序

描述算法的工具

传统流程图

N-S结构化流程图

算法描述语言

算法复杂度

一个算法一般可以用顺序、选择和循环三种基本结构组合而成

算法的时间复杂度和空间复杂度相互独立

时间复杂度

指执行算法所需要的的计算工作量

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

算法的计算工作量是用算法所执行的基本运算次数来度量的

空间复杂度

指执行这个算法所需要的内存空间

通常采用压缩技术降低算法的空间复杂度

数据结构

概念

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

数据

数据元素是数据的基本单位，数据项是数据的最小单位

需要处理的具有某个共同特征的数据元素的集合

结构

即关系，是集合中各个数据元素之间存在的某种联系

数据结构

一种逻辑结构可以有多种存储结构，不同的存储结构其数据处理效率不同

逻辑结构

反映元素之间的逻辑关系（前后件关系）

线性结构：线性表、栈、队列

有且只有一个根节点

每个节点做多有一个前件，做多有一个后件

非线性结构：树、图

不满足线性结构条件的

存储结构

及物理结构，是逻辑结构在计算机存储空间中的存放方式

顺序存储

链式存储

运算

插入、删除、查找、排序

表示方法

二元组：B=(D,R)

一日三餐为例：B=(D,R) D={早餐,午餐,晚餐} R={(早餐,午餐),(午餐,晚餐)}

图形

如图1所示

标有元素值的方框为数据元素，称为数据节点，即节点

根节点

终端节点（叶子节点）

内部节点

有向线段由前件指向后件

线性结构与非线性结构

线性结构

有且只有一个根节点

每个节点最多有一个前件和一个后件

非线性结构

树形结构

网状结构

线性表及其顺序存储结构

基本概念

概念

数据元素组成的有限序列

特征

只有一个根节点

只有一个终端节点

其他所有节点只有一个前件，也只有一个后件

顺序存储

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

按数据元素的逻辑顺序依次存放

可以随机访问数据元素

做插入、删除时需移动大量元素

栈和队列

栈

概念

栈的所有插入与删除都限定在表的同一端（栈顶）进行

栈的修改原则是“先进后出”或“后进先出”

栈底指针不变，栈顶指针top反映了栈的状态不断变化

栈支持子程序的调用

运算规则

入栈

退栈

读栈顶元素

队列

定义

指允许在一端（队尾）进行插入，另一端（队头）进行删除的线性表

队列的修改原则是“先进先出”或“后进后出”

运算

顺序存储结构的线性表，队头指针front指向队头的前一个元素，队尾指针rear指向队尾的后一个元素

front与rear共同反映了队列中元素的动态变化

循环队列

将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间

当front=rear时，不能确认队列是满还是空。所以，当s=0时，队列为空；当s=1且front=rear时，队列为满

线性链表

基本概念

线性链表

线性表的链式存储结构

单链表

每个节点只有一个指针域

双向链表

每个节点设置左指针（放前件）和右指针（放后件）

二叉链表

二叉树的链式存储结构

特点

各数据结点的存储空间可以不连续

各数据元素的存储顺序与逻辑顺序可以不一致

线性表的链式存储所占存储空间大于顺序存储结构

查找结点时链式存储要比顺序存储慢

链式存储在插入、删除元素时要比顺序存储灵活

存储单元是任意的

指向第一个元素的头指针HEAD等于NULL或者0时，称为空表

带链的栈

带链的队列

顺序表和链表对比

顺序表

优点

可以随机存取表中任意节点

无需为节点逻辑关系增加空间

缺点

插入和删除运算效率很低

不便于扩充

不便于对存储空间的动态分配

链表

优点

插入和删除时只需改变指针

存储空间易于扩充，便于动态分配

缺点

需要额外的空间存储节点之间的逻辑关系

存储密度比顺序表第

循环链表

将表头节点与表尾节点相连接所构成的环状链

在表中没有数据元素的情况下依然存在一个数据节点，使得空表和非空表的运算统一

树与二叉树

树的基本概念

非线性结构

父节点

每一个节点的前件称为该节点的父节点

根

没有前件的节点称为该树的根

子节点

每一个节点的后件称为该节点的子节点

没有后件的节点称为叶子节点

度

一个节点所拥有的的后件的个数

最大的度称为该树的度

深度

树的最大层次

二叉树及其基本性质

定义

空二叉树没有节点

每个节点最多有两棵子树

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

性质

在二叉树的第k层上，最多有2k-1(k≥1)个节点

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

任意一棵二叉树，度为0的节点总是比度为2的节点多一个

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

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

满二叉树与完全二叉树

满二叉树

除最后一层外，每一层上都有两个子节点

完全二叉树

只在最后一层上缺少右边的若干节点的二叉树

特点

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

对于任一节点，若其右子树深度为m，则其左子树深度为m或m+1

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

二叉树的存储结构

链式存储结构

指向该节点左子节点的为左指针域，指向该节点右子节点的为右指针域

二叉树的遍历

不重复的访问二叉树的所有节点（先左后右）（如图2所示）

前序遍历

A、B、D、H、E、I、C、F、G

中序遍历

H、D、B、E、I、A、C、G、F

后序遍历

H、D、I、E、B、G、F、C、A

已知一棵树的前序遍历和后序遍历不能唯一确定这课二叉树

查找技术

顺序查找

唯一方法

线性表为无序表

链式存储结构

最好的情况下比较1次

最坏的情况下比较n次

二分法查找

满足条件

顺序存储结构

有序表，元素按“从小到大”排列

最坏情况下比较log2n次

程序设计基础

程序设计风格

清晰第一，效率第二

源程序内部文档化

数据说明

语句的结构

输入和输出

结构化程序设计

原则

自顶向下

先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标

逐步求精

对复杂的问题，先设计一个目标作为过渡，然后逐步细化

模块化

把程序要解决的总目标分解为一个一个的模块

限制使用goto语句

程序的质量与goto语句数量成反比

基本结构

顺序结构

选择结构

循环结构

特征：只有一个入口和一个出口

优点

程序易于理解、使用和维护

提高了编程工作效率，降低了软件开发成本

面向对象的程序设计

优点

与人类习惯的思维方式一致

稳定性好

可重用性好

容易开发大型软件产品

可维护性好

概念

对象

标识唯一性

对象可由内在本质来区分，而不是通过描述来区分

分类性

可以将具有相同属性和操作的对象抽象成类

多态性

同一操作可以是不同对象的行为

封装性

从外面看不到对象的内部，只能看到对象的外部特征

模块独立性好

对象是面向对象的软件的基本模块，内聚性强

类和实例

类是具有共同属性、共同方法的对象的集合

一个具体对象则是其对应类的一个实例

消息

消息传递是对象间通信的手段

继承

类与类之间也可以继承，一个子类可继承其父类的全部描述

使用已有的类建立新类的定义技术，能直接获得已有的性质，而不必重复定义他们

多态性

子类对象可以像父类对象那样使用，同样的消息既可以发送给父类对象也可以发送给子类对象

是指同样的消息被不同的对象接收时可导致完全不同的行动的现象

软件设计基础

软件工程基本概念

软件定义与软件特点

定义

由程序、数据及相关文档构成的完整集合

程序和数据是机器可执行的，文档不是

特点

逻辑实体，具有抽象性

没有明显的制作过程

不存在磨损、老化问题

对硬件和换件具有依赖性

复杂性高，成本昂贵

软件的分类

系统软件

最靠近计算机硬件的软件

操作系统、编译程序、汇编程序、网络软件、数据库管理系统

应用软件

应用于特定的领域

事务处理软件、工程与科学计算软件、实时处理软件、人工智能软件

支撑软件

协助用户开发软件的工具型软件

需求分析工具软件、编译工具软件、测试工具软件、维护工具软件

软件工程

要素

方法

完成软件工程项目的技术手段

工具

支持软件的开发、管理和文档生成

过程

支持软件开发的各环节的控制和管理

原则

抽象

信息隐蔽

模块化

局部化

确定性

一致性

完备性

可检验性

软件过程

概念

把输入转为输出的一组彼此相关的资源和活动

基本活动

软件规格说明

软件开发（软件设计与实施）

软件确认

软件演进

软件生命周期

软件定义期

问题定义

可行性研究

可行性分析报告

需求分析

需求规格说明书

软件开发期

概要设计

概要设计说明书

详细设计

详细设计说明书

软件实现

用户操作手册

软件测试

测试分析报告

运行维护期

运行维护

需求分析及其方法

需求分析

概念

需求分析将创建所需的数据模型、功能模型和控制模型

工作的四个方面

需求获取

需求分析

编写需求规格说明书

需求评审

需求规格说明书

需求分析阶段的最后成果

重点描述

软件的目标

软件的功能需求

性能需求

外部接口

属性

约束条件

特点

正确性

无歧义性

完整性

可验证性

一致性

可理解性

可修改性

可追踪性

需求分析方法

结构化分析法

面向对象分析法

结构化分析方法的常用工具

数据流图

每个元素都必须命名

编号，既有输入也有输出

数据存储之间不应有数据流

父图、子图关系与平衡规则

数据字典

是结构化分析的核心

结构化英语

判定表

判定树

软件设计及其方法

基本概念

软件设计是确定系统的物理模型

高内聚，低耦合

分类

从工程管理角度划分

概要设计

详细设计

按技术观点划分

结构设计

数据设计

接口设计

过程设计

基本原理

抽象

模块化

信息隐蔽

模块独立性

内聚性

耦合性

概要设计

任务

设计软件系统结构

数据结构及数据库设计

编写概要设计文档

概要设计文档评审

结构图

反映了整个系统的功能实现以及模块与模块之间的关系

顶层高扇出，中间扇出较少，底层高扇入

详细设计

常用工具

程序流程图（PFD）

N-S图

PAD图

HIPO图

判定表

PDL

软件测试

目的和准则

目的

发现软件中的错误

准则

追溯到用户需求

制定测试计划，并严格执行

注意测试中的群集现象

避免由程序编写者测试自己的程序

不可能进行穷举测试

妥善保存测试计划、测试用例、出错统计和最终分析报告

测试方法

是否需要被执行

静态测试

不实际运行，主要通过人工进行分析

动态测试

上机测试

功能

黑盒测试

测试者完全不了解，或不考虑程序的结构和处理过程

等价类划分法

边界值分析法

错误推测法

因果图

白盒测试

测试者完全了解程序的结构和处理过程

逻辑覆盖测试

基本路径测试

测试的实施

单元测试（模块测试）

方法

动态测试通常以白盒测试法为主，测试其结构

静态测试通常以黑盒测试法为主，测试其功能

目的

发现模块内部的错误

集成测试（组装测试）

目的

发现与接口有关的错误

方法

通常采用黑盒测试法

确认测试（验收测试）

白盒测试

测试程序的内部逻辑结构

逻辑覆盖测试

基本路径测试

黑盒测试

测试程序的外部功能

等价划分法

边界值分析法

错误推测法

系统测试

在实际运行环境下对计算机系统进行一系列集成测试和确认测试

程序调试

基本概念

任务是诊断和修正程序中的错误

调试方法

强行排错法

回溯法

原因排除法

数据库设计基础

数据库系统的基本概念

数据库、数据库管理系统和数据库系统

数据

描述事物的符号

数据库

长期存储在计算机内的、有组织的、可共享的数据集合

特点：“集成”与“共享”

数据库管理系统（DBMS）（数据库系统的核心）

数据语言

数据定义语言（DDL）

数据模式定义

数据存取的物理构建

数据操纵语言（DML）

数据操纵

数据控制语言（DCL）

数据的安全性的定义与检查

并发控制与故障修复

数据的完整性

数据库系统（DBS）

数据库管理员（DBA）

数据库设计

数据库维护

改善系统性能，提高系统效率

硬件平台

计算机

网络

软件平台

操作软件

开发工具

接口软件

数据库

数据库管理系统

数据库应用系统

数据库系统

应用软件

应用界面

数据库技术的发展

数据库系统的基本特点

集成性

高共享、低冗余

独立性

统一管理控制

数据库系统的内部结构体系

数据模型

基本概念

概念

三要素

数据结构

数据操作

数据约束

类型

概念数据模型

E-R模型

概念

连接关系

E-R图

逻辑数据模型

层次模型

网状模型

关系模型

面向对象模型

物理数据模型

关系模型

数据结构

完整性约束

实体完整性约束

参照完整性约束

束和用户定义的完整性约束

关系代数

差运算

交运算

并运算

笛卡尔积运算

投影运算

选择运算

除运算

连接运算

数据库设计

概述

设计一个能满足用户要求、性能良好的数据库

基本任务

根据用户对象的信息需求、处理需求和数据库的支持环境设计出数据模式

两种方法

面向数据：以信息需求为主，兼顾处理需求（主流）

面向过程：以处理需求为主，兼顾信息需求

设计步骤

需求分析（建立数据字典）

概念设计（设计E-R图）

逻辑设计（把E-R图转换为关系模式）

物理设计

范式

A

B

D

H

E

I

图2

C

空

F

G

空

图1

连长

排长

班长

战士

战士

战士

班长

战士

战士

战士

排长

班长

战士

战士

战士

班长

战士

战士

战士