(图文版)计算机二级公共基础知识

计算机二级公共基础知识是计算机中综合性知识，包含的科目有数据结构，软件工程，算法设计与分析，数据库设计等。这些科目都属于计算机专业必修课，也是一个程序员的必备理论基础。

计算机二级公共基础知识

数据结构与算法

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

算法不等于程序

特征：

可行性

确定性

有穷性：必须在有限的时间内做完，必须在执行有限个步骤后终止

足够的情报：有输入输出

对数据对象的运算和操作

算术运算

逻辑运算

关系运算

数据传输

算法的控制结构

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

描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等

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

时间和空间复杂度

时间复杂度

是指执行算法所需要的计算工作量，可以用算法所执行的基本运算次数度量

不是指执行具体所需时间

空间复杂度

是指执行算法所需要的内存空间。包括算法程序、输入的初始数据以及算法执行过程中需要的额外空间

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

数据结构

数据：需要处理的数据元素的集合，一般来说，这些数据元素具有某个共同的特征

数据元素是数据的基本单位，即数据集合中的个体

有时一个数据元素可由若干数据项组成。数据项是数据的最小单位

结构：是集合中各个数据元素之间存在的某种关系（或联系）

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

数据结构的分类

逻辑结构

指反应数据元素之间的逻辑关系（即前后件关系）的数据结构

线性结构

特点

有且只有一个根节点，它无前件

每个节点最多有一个前件，也最多有一个后件

线性表

线性表是n（n>=0）个数据元素构成的有限序列，表中除第一个元素外的每一个元素，有且只有一个一个前件，除最后一个元素外，有且只有一个后件

线性表的顺序存储结构

通常，线性表可以采用顺序存储和链式存储，但一般使用顺序存储结构

线性表的顺序存储又叫做顺序表、顺序分配

特点：

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

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

可以随机访问数据元素

做插入、删除时需移动大量元素，因此线性表不便于插入和删除元素

线性表的链式存储结构

线性表的链式存储结构成为线性链表

特点

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

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

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

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

链式存储插入删除元素比顺序存储灵活

双向链表

循环链表

栈

是限定在一端进行插入和删除的线性表

特点

栈只能在栈顶进行插入和删除

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

指针

栈底指针bottom

栈顶指针top

空栈时均指向栈底

栈中有元素时，top指向最后入栈的元素，bottom始终指向栈底

入栈

栈满

出栈

栈底指针不变，栈中元素随栈顶指针的变化而动态变化

栈具有记忆功能

栈支持子程序调用

运算

队列

是指允许在一端进行插入，而在另一端进行删除的线性表。原则是：先进先出，后进后出

指针

队头指针front

队尾指针rear

入队

出队

特点

队列只允许在队尾进行插入，而在队头进行删除

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

队列中元素随队头指针和队尾指针的变化而动态变化

循环队列

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

非线性结构

特点

不满足线性结构两个条件的数据结构就称为非线性结构

树

树是n（n>0）个元素的有限集合。它有且仅有一个称为根的元素；其余元素是互不相交的子树

常用术语

父节点：前件为后件的父节点

子节点：后件为前件的子节点

根节点：没有前件的节点A为根节点

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

结点的度：一个结点所拥有的后件的个数叫做结点的度

树的度：所有的结点中最大的度称为树的度

树的深度：层数，从1开始数

子树：以某个节点的一个子节点为根所构成的树

二叉树

二叉树是一个有限的结点集合，该集合或者为空，或者由一个根节点及其两棵互不相交的左右二叉子树所组成

特点

非空二叉树只有一个根节点

每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树，左右次序不能颠倒

二叉树基本状态

特殊二叉树

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

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

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

性质

非空二叉树只有一个根节点，每个节点最多有两棵子树，分别称为左子树和右子树

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

深度为m的二叉树最多有2^m-1个结点

度为0的结点（叶子节点）总比度为2的结点多一个

有n个结点的二叉树深度至少为([]为向下取整)

二叉树的遍历

前序遍历

访问根结点

前序遍历左子树

前序遍历右子树

->从左至右一列一列的访问（根左右）

中序遍历

中序遍历左子树

访问根节点

中序遍历右子树

->左根右

后序遍历

后序遍历左子树

后序遍历右子树

访问根节点

->左右根

图

存储结构

又称为数据的物理结构，是数据的逻辑结构在计算机存储空间中的存放方式

顺序存储

主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里

链式存储

每一个节点至少包含一个指针域，用指针的指向来体现数据元素之间在逻辑上的联系

一种逻辑结构可以有多种存储结构

不同的存储结构其数据处理的效率不同

顺序存储访问更方便

删除插入数据链式存储更方便

运算

插入

删除

查找

顺序查找

对于长度为n的线性表，平均要进行n/2次比较，在最坏情况下进行n次比较

顺序查找适用于无序表或链式线性表（不管无序还是有序）（这两种情况只能顺序查找）

二分查找

适用于顺序存储的有序表，对长度为n的线性表，在最坏情况下进行log2 n 次比较

排序

快速排序

基本思想

在要排序的序列中找一个数作为基准数（通常为第一个数）

通过交换将这个序列中所有比基准数大的数放在右边，比基准数小的数放在左边

以基准数为分割线分为两个子表，对两个子表重读上述步骤

先从后往前找，再从前往后找，重复

选择排序

找出数据中最小值，与排头交换，然后剩下的数据重复

程序设计基础

程序设计方法与风格

良好的程序设计风格：清晰第一，效率第二

程序设计风格规范

源程序内部文档化

选择标识符的名字

注释（序言性和功能性注释）

序言性：一般位于模块首部，用于说明模块的相关信息

包括

程序的标题

功能的说明

主要的算法

模块接口

开发历史

程序设计者

复审者

复审日期

功能性：位于源程序模块内部

程序的视觉组织

数据说明

语句的结构

程序模块化

输入输出

结构化程序设计

原则

自顶向下

先考虑总体，再考虑细节

先考虑全局目标，后考虑局部目标

逐步求精

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

模块化

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

限用goto

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

基本结构

常采用顺序、选择（分支）、和循环三种基本结构

程序设计语言的基本成分

数据成分

运算成分

控制成分

传输成分

面向对象的程序设计

术语

对象

属性：描述对象的状态

方法：描述对象的行为

类：一组具有相同属性和相同操作的对象的集合

对象基本特点

标识唯一性：对象可由内在本质来区分，而不是通过描述来区分

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

多态性：同一操作可以是不同对象的行为

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

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

面向对象程序设计主要特征

封装

继承

多态

抽象

继承

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

消息

是一个实例与另一个实例之间传递的信息。对象间的通信靠消息传递

消息的组成

接受消息的对象的名称

消息标识符，也称消息名

零个或多个参数

多态性

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

软件工程基础

软件工程基本概念

软件

程序

数据

文档

软件分类

系统软件

操作系统

编译系统

汇编系统

网络软件

数据库管理系统

应用软件

事务处理软件

工程与科学计算软件

实时处理软件

人工智能软件

支撑软件（工具软件）

需求分析工具软件

编译工具软件

测试工具软件

维护工具软件

软件危机

需求增长

开发难控

质量难保

难以维护

成本提高

生产率低

软件工程

应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标准和工序；其目的的提高软件生产率、提高软件质量、降低软件成本

其核心思想是把软件当作一个工程产品来处理

软件工程三要素

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

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

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

软件生命周期

将软件产品从提出、实现、使用维护到停止使用退役的过程

分为软件定义、软件开发、软件运行维护3个时期。维护是持续时间最长，花费代价最大的一个时期

软件工程学的一个目的就是提高软件的可维护性，降低维护代价

分为9个阶段

定义

问题定义可行性研究、初步项目计划

产生文档：可行性分析报告

需求分析

确定系统的逻辑模型。参与人员有用户、项目负责人、系统分析员

工作：需求获取、需求分析、编写需求规格说明书、需求评审

产生文档：需求规格说明书（SRS）

作用

便于用户、开发人员进行理解交流

反映用户问题的结构，可以作为软件开发工作的基础和依据

作为确认测试和验收的依据

特点

正确性：体现待开发系统的真实要求

无歧义性：对每个需求只有一种解释

完整性：包括全部有意义的需求

可验证性：每个需求都是可验证的

一致性：各个需求的描述不矛盾

可理解性：需求说明书必须简明易懂

可修改性：结构风格在改变时，是易于实现的

可追踪性：每个需求的来源和流向是清晰的

开发

概要设计

概要设计说明书

详细设计

详细设计说明书

实现

用户操作手册

测试

测试分析报告

运行维护

使用

维护

退役

结构化分析方法

需求分析方法

结构化需求分析方法

面向对象的分析方法

结构化分析方法

使用数据流图（DFD）、数据字典（DD）（结构化分析的核心）、判定表和判定树等工具，来建立系统的逻辑模型

数据流图（DFD）

结构化方法的需求分析工具

数据流图的图形元素

数据字典（DD）（结构化分析的核心）

是对数据流图中所有元素定义的集合

结构化设计方法

软件设计的划分

从工程管理角度划分

概要设计

概要设计的任务

设计软件系统结构

数据结构及数据库设计

编写概要设计文档

概要设计文档评审

概要设计的工具是程序结构图（SC）

程序结构图的基本图符

程序结构图的基本形式

详细设计

详细设计任务

确立每个模块的实现算法和局部数据结构，用适当方法表示算法和数据结构的细节

详细设计的常用工具：

图形工具：程序流程图、N-S图、PAD、HIPO

程序流程图的基本图符

表格工具：判定表

语言工具：PDL（伪码）

按技术观点划分

结构设计

数据设计

接口设计

过程设计

软件设计基本原理

抽象：在软件设计中，可以定出多个抽象级别，抽象层次从概要设计到详细设计逐步降低

模块化：把一个待开发的软件分解成若干个小的简单的部分，自顶向下逐层把软件划分成若干模块

信息隐蔽：一个模块内的信息，对于不需要这些信息的其他模块来说不能访问

模块独立性：每个模块只能完成独立的子功能，并且与其他模块的联系少且接口简单。模块的独立程度是评价设计好坏的重要度量标准（高内聚，低耦合）

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

耦合性：指模块间互相连接的紧密程度

非直接耦合

数据耦合

标记耦合

控制耦合

外部耦合

公共耦合

内容耦合

软件测试

目的：发现程序中的错误

准则

所有测试都应追溯到用户需求

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

充分注意测试中的群集现象

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

不可能进行穷举测试

妥善保存测试分析报告，为维护提供方便

方法

按是否执行划分

静态测试

不实际运行软件，通过人发挥思维优势发现程序的错误

动态测试

基于计算机的测试，是为了发现错误而执行程序的过程

按功能划分

白盒测试（程序内部逻辑结构）

把测试对象看作一个打开的盒子，利用程序内部的逻辑结构，对程序所有逻辑路径进行测试

逻辑覆盖测试

基本路径测试

黑盒测试（程序外部功能）

完全不考虑程序内部的逻辑结构，只检查程序是否能接受输入数据而产生正确的输入信息

等价类划分法

边界值分析法

错误推测法

步骤

单元测试

是对软件设计的最小单位一一模块进行测试，目的是发现各个模块内部的错误

集成测试

把模块按照设计要求组装起来的同时进行测试，目的是发现与接口有关的错误

确认测试

是验证软件的功能和性能是否满足各种需求，以及软件配置是否完全、正确

系统测试

是将软件作为一个元素，与计算机系统其他元素组合在一起，进行集成测试

程序的调试

任务：诊断和改正程序的错误

基本步骤

错误定位

修改设计和代码，以排除错误

进行回归测试，防止引进新的错误

软件调试方法

强行排除法

回溯法

原因排除法

概要

基本要求

1. 掌握计算机系统的基本概念，理解计算机硬件系统和计算机操作系统。

2. 掌握算法的基本概念。

3. 掌握基本数据结构及其操作。

4. 掌握基本排序和查找算法。

5. 掌握逐步求精的结构化程序设计方法。

6. 掌握软件工程的基本方法，具有初步应用相关技术进行软件开发的能力。 7. 掌握数据库的基本知识，了解关系数据库的设计。

考试内容

计算机系统

1. 掌握计算机系统的结构。

2. 掌握计算机硬件系统结构，包括 CPU 的功能和组成，存储器分层体系，总线和外部设备。

3. 掌握操作系统的基本组成，包括进程管理、内存管理、目录和文件系统、I / O 设备管理。

基本数据结构与算法

1. 算法的基本概念;算法复杂度的概念和意义(时间复杂度与空间复杂度)。

2. 数据结构的定义;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构的概念。

3. 线性表的定义;线性表的顺序存储结构及其插入与删除运算。

4. 栈和队列的定义;栈和队列的顺序存储结构及其基本运算。

5. 线性单链表、双向链表与循环链表的结构及其基本运算。

6. 树的基本概念;二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。

7. 顺序查找与二分法查找算法;基本排序算法(交换类排序，选择类排序，插入类排序)。

程序设计基础

1. 程序设计方法与风格。

2. 结构化程序设计。

3. 面向对象的程序设计方法，对象，方法，属性及继承与多态性。

软件工程基础

1. 软件工程基本概念，软件生命周期概念，软件工具与软件开发环境。

2. 结构化分析方法，数据流图，数据字典，软件需求规格说明书。

3. 结构化设计方法，总体设计与详细设计。

4. 软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。

5. 程序的调试，静态调试与动态调试。

数据库设计基础

1. 数据库的基本概念:数据库，数据库管理系统，数据库系统。

2. 数据模型，实体联系模型及 E-R 图，从 E-R 图导出关系数据模型。

3. 关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。

4. 数据库设计方法和步骤:需求分析、概念设计、逻辑设计和物理设计的相关策略。

考试方式

1. 公共基础知识不单独考试，与其他二级科目组合在一起，作为二级科目考核内容的一部分。

2. 上机考试，10 道单项选择题，占 10 分。

数据库设计基础

数据库系统的基本概念

数据

描述事物的符号记录

软件的数据一定是有结构的，有型与值两个概念

数据库应用系统（DBAS）

数据库系统（DBS）

数据库（DB）

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

两大特点

集成

共享

数据库管理系统（DBMS）

数据库管理系统是数据库系统的核心

属于系统软件

数据定义语言（DDL）

数据模式定义

数据存取的物理构建

数据操纵语言（DML）

数据操纵，包括查询与增、删、改等操作

数据控制语言（DCL）

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

并发控制与故障恢复

数据的完整性

数据库管理员（DBA）

主要工作

数据库设计

数据库维护

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

软件平台

操作系统

开发工具

接口软件

硬件平台

计算机

网络

应用软件

应用界面

数据管理三个阶段

人工管理

文件系统

数据库系统

数据库技术的根本目标

解决数据共享问题、

数据库系统特点

集成性

高共享低冗余

独立性

统一管理控制

三级模式和两级映射

两级映射保证了数据库中数据具有较高的逻辑独立性和物理独立性

数据模型

三要素

数据结构

数据操作

数据约束

按不同应用层次分类

概念数据模型（概念模型）

E-R模型（实体-联系模型）

逻辑数据模型（数据模型）

层次模型

eg：树

网状模型

eg: 无向图

关系模型

采用二维表来表示，简称表，每一个二维表称为一个关系，用以表示实体间的联系

属性（字段）：二维表中的一列称为属性

元组（记录）：二维表中的一行称为元组

一个元组可以由若干个分量组成，分量个数等于属性的元素，分量不可再分

关系操纵：查询、增加、删除和修改

关系中的数据约束

实体完整性约束

主键不能为空

参照完整性约束

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

主关键字：在二维表中可表示唯一元组的

关系数据库中，存取一个学生信息的数据单位是记录（元组）

面向对象模型

物理数据模型（物理模型）

关系代数

关系模型的基本操作

插入

删除

修改

查询

查询运算

投影运算

选择运算

笛卡尔积运算（连接运算）

关系代数中的基本运算

差

T=R-S

并

T=R+S

笛卡尔积运算（积）

T=R*S

选择

选择行

投影

选择列

关系代数中的扩充运算

交运算

求交集

除运算

T=R/S

连接与自然连接运算

属性增加一般是自然连接

数据库设计与管理

数据库设计概述

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

基本任务

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

两种方法

以信息需求为主，兼顾处理需求（面向数据的方法）

以处理需求为主，兼顾信息需求（面向过程的方法）

面向数据的方法已成主流方法

数据库设计的步骤

数据库设计目前一般采用生命周期法，分若干阶段

需求分析阶段

概念设计阶段

逻辑设计阶段

物理设计阶段

编码阶段

测试阶段

运行阶段

进一步修改阶段

在数据库设计采用前四个阶段，并重点以数据结构与模型设计为主线

数据库管理

数据库的建立

数据库的调整

数据库的重组

数据库安全性控制与完整性控制

数据库的故障恢复

数据库监控