导图社区 计算机二级
- 2.4k
- 223
- 52
- 举报
计算机二级
必看！计算机二级考点整理总结！下图整理总结了算法、软件工程基本概念、数据库设计基础、程序设计基础等内容。希望能够帮助你顺利通过计算机二级考试呀！
编辑于2020-02-06 14:07:26- 相似推荐
- 大纲
计算机二级
算法
算法
基本概念
指解决方案准备而完备【不仅仅是理论的】描述
基本特征
可行性、确定性、有穷性、拥有足够的情报
基本要素
算法对数据的基本运算和操作、算法的控制结构（顺序结构、选择结构、循环结构）
复杂度
时间复杂度：指执行算法所需的计算工作量
空间复杂度：指执行算法时需要的内存空间
数据结构（事物的实体和关系）
探讨的问题
数据集合中各数据之间固有的逻辑关系，即数据的逻辑结构
对数据处理时，各数据在计算机中的存储结构，即数据的存储结构
对各种数据结构的运算
定义
指相互有关联数据元素集合的表示，即数据结构是带有结构的数据元素的集合
应包含内容
表示数据元素信息即数据元素的集合，通常记为D
表示数据元素之间的前后件关系通常记为R，即表示为B=(D,R)
线性结构和非线性结构
线性结构（线性表）：1.有且只有一个根节点2.每一个节点最多有一个前件和一个后件
栈、线性链表和队列
栈
定义
限定在一端插入与删除的线性表
允许插入与删除的一端称为栈顶（TOP），反正为栈底（Bottom）
按照先进后出或后进先出的原则
顺序存储空间（1,m）中，非空情况下S（bottom）为栈底元素，反之栈顶。
top=0表示栈空，top=m表示为栈满
运算
入栈运算是栈顶插入一个元素，top=top+1，如果栈满，不可再入栈，否则出现“上溢”错误
退栈运算是栈顶取出一个元素，top=top-1，如果栈空，不可再退栈，否则出现“下溢”错误
Top=0时，栈的开口向上，元素的个数是top
队列
线性链表
定义
在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据 域，另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点（即 前件或后件）
链式存储方式既可用于表示线性结构，也可用于表示非线性结构。
（1）线性链表 线性表的链式存储结构称为线性链表。 在某些应用中，对线性链表中的每个结点设置两个指针，一个称为左指针，用以指向其前 件结点；另一个称为右指针，用以指向其后件结点。这样的表称为双向链表。
（2）带链的栈 栈也是线性表，也可以采用链式存储结构。带链的栈可以用来收集计算机存储空间中所有 空闲的存储结点，这种带链的栈称为可利用栈。
在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑 关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的
树与二叉树
基本性质
树(tree）是一种简单的非线性结构。在树结构中，每一个结点只有一个前件，称为父结点， 没有前件的结点只有一个，称为树的根结点。每一个结点可以有多个后件，它们称为该结点的 子结点。没有后件的结点称为叶子结点。 在树结构中，一个结点所拥有的后件个数称为该结点的度。叶子结点的度为0。在树中，所 有结点中的最大的度称为树的度。
二叉树
二叉树定义
①非空二叉树只有一个根结点；
②每一个结点最多有两棵子树，且分别称为该结点的左子树和右子树。由以上特点可以看出，在二叉树中，每一个结点的度最大为2，即所有子树（左子树或右子 树）也均为二叉树，而树结构中的每一个结点的度可以是任意的。另外，二叉树中的每个结点 的子树被明显地分为左子树和右子树。在二叉树中，一个结点可以只有左子树而没有右子树， 也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时，该结点即为叶子 结点
二叉树基本性质
性质1：在二叉树的第k层上，最多有2k-1（k≥1）个结点
性质2：深度为m的二叉树最多有2m-1个结点；
性质3：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。
性质4：具有n个结点的二叉树，其深度至少为［log2n］+1，其中［log2n］表示取log2n的整 数部分。
性质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）前序遍历：先访问根结点、然后遍历左子树，最后遍历右子树；并且，在遍历左、右 子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树
（2）中序遍历：先遍历左子树、然后访问根结点，最后遍历右子树；并且，在遍历左、右 子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。
（3）后序遍历：先遍历左子树、然后遍历右子树，最后访问根结点；并且，在遍历左、右 子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点
查找和排序技术
查找技术
顺序查找
实现方法
查找是指在一个给定的数据结构中查找某个指定的元素。从线性表的第一个元素开始，依 次将线性表中的元素与被查找的元素相比较，若相等则表示查找成功；若线性表中所有的元素 都与被查找元素进行了比较但都不相等，则表示查找失败
指定使用情况
（1）线性表为无序表 （2）即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。
效率
长度为n线性表最差次数为n，最大或最小值比较次数为n-1次
二分法查找
实现方法
设有序线性表的长度为n，被查找的元素为i， （1）将i与线性表的中间项进行比较； （2）若i与中间项的值相等，则查找成功； （3）若i小于中间项，则在线性表的前半部分以相同的方法查找； （4）若i大于中间项，则在线性表的后半部分以相同的方法查找。
指定使用情况
顺序存储的有序表
效率
在最坏情况下，二分查找只需要比较log2n次。
排序技术（效率从低到高）
冒泡排序
快速排序
简单插入排序
简单选择排序
希尔排序
堆排序
程序设计基础
结构化程序设计原则
20世纪70年代提出了"结构化程序设计"的思想和方法。结构化程序设计方法引入了工程化 思想和结构化思想，使大型软件的开发和编程得到了极大的改善。结构化程序设计方法的主要 原则为：自顶向下、逐步求精、模块化和限制使用goto语句。 程序设计时，应先考虑总体，后考虑细节；先考虑全局目标，后考虑局部目标；不要一开始就过多追求众 多的细节，先从最上层总目标开始设计，逐步使问题具体化。
面向对象的程序设计
对象
通常把对对象的操作也称为方法或服务。 属性即对象所包含的信息，它在设计对象时确定，操作描述了对象执行的功能，若通过信息的传递，还可以为其他对象使用。 对象具有如下特征：标识惟一性、分类性、多态性、封装性、模块独立性。 一般只能通过执行对象的操作来改变。 属性值应该指的是纯粹的数据值，而不能指对象。
类和实例
类是具有共同属性、共同方法的对象的集合。它描述了属于该对象类型的所有对象的性质， 而一个对象则是其对应类的一个实例。 类是关于对象性质的描述，它同对象一样，包括一组数据属性和在数据上的一组合法操作。
消息
消息是实例之间传递的信息，它请求对象执行某一处理或回答某一要求的信息，它统一了 数据流和控制流。 一个消息由三部分组成：接收消息的对象的名称、消息标识符（消息名）和零个或多个参 数。
继承
广义地说，继承是指能够直接获得已有的性质和特征，而不必重复定义它们。 继承分为单继承与多重继承。单继承是指，一个类只允许有一个父类，即类等级为树形结 构。多重继承是指，一个类允许有多个父类。
多态性
对象根据所接收的消息而做出动作，同样的消息被不同的对象接收时可导致完全不同的行 动，该现象称为多态性。
数据库设计基础
数据、数据库、数据库管理系统
数据是数据库中存储的基本对象，描述事物的符号记录。
数据库是长期储存在计算机内、有组织的、可共享的大量数据的集合，它具有统一的结构 形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序所共享。
数据库管理系统（DBMS，Database Management System）是数据库的机构，它是一种系统 软件，负责数据库中的数据组织、数据操作、数据维护、控制及保护和数据服务等。数据库管理系统是数据系统的核心，主要有如下功能：数据模式定义、数据存取的物理构建、数据操纵、 数据的完整性、安全性定义和检查、数据库的并发控制与故障恢复、数据的服务。 为完成数据库管理系统的功能，数据库管理系统提供相应的数据语言：数据定义语言、数 据操纵语言、数据控制语言。 数据库管理员的主要工作如下：数据库设计、数据库维护、改善系统性能，提高系统效率。
数据库系统的发展
三个阶段
数据库系统的内部结构体系
数据库系统的3级模式
（1）概念模式，也称逻辑模式，是对数据库系统中全局数据逻辑结构的描述，是全体用户 （应用）公共数据视图。一个数据库只有一个概念模式。
（2）外模式，外模式也称子模式，它是数据库用户能够看见和使用的局部数据的逻辑结构 和特征的描述，它是由概念模式推导而出来的，是数据库用户的数据视图，是与某一应用有关 的数据的逻辑表示。一个概念模式可以有若干个外模式
（3）内模式，内模式又称物理模式，它给出了数据库物理存储结构与物理存取方法。 内模式处于最底层，它反映了数据在计算机物理结构中的实际存储形式，概念模式处于中 间层，它反映了设计者的数据全局逻辑要求，而外模式处于最外层，它反映了用户对数据的要 求
tip：内模式处于最底层，它反映了数据在计算机物理结构中的实际存储形式，概念模式处于中间 层，它反映了设计者的数据全局逻辑要求，而外模式处于最外层，它反映了用户对数据的要求。
数据库系统的两级映射
（1）概念模式到内模式的映射。该映射给出了概念模式中数据的全局逻辑结构到数据的物 理存储结构间的对应关系；
（2）外模式到概念模式的映射。概念模式是一个全局模式而外模式是用户的局部模式。一 个概念模式中可以定义多个外模式，而每个外模式是概念模式的一个基本视图
tip：数据库应用系统的7个部分以一定的逻辑层次结构方式组成一个有机的整体，它们的结构关系是：应用系统 工、应用开发工具软件、数据库管理系统、操作系统、硬件。
数据模型
E-R模型
基本概念 （1）实体：现实世界中的事物可以抽象成为实体，实体是概念世界中的基本单位，它们是 客观存在的且又能相互区别的事物。 （2）属性：现实世界中事物均有一些特性，这些特性可以用属性来表示。 （3）码：唯一标识实体的属性集称为码。 （4）域：属性的取值范围称为该属性的域。 （5）联系：在现实世界中事物间的关联称为联系。 两个实体集间的联系实际上是实体集间的函数关系，这种函数关系可以有下面几种：一对 一的联系、一对多或多对一联系、多对多。
E-R模型的图示法 （1）实体表示法：在E-R图中用矩形表示实体集，在矩形内写上该实体集的名字。 （2）属性表示法：在E-R图中用椭圆形表示属性，在椭圆形内写上该属性的名称。 （3）联系表示法：在E-R图中用菱形表示联系，菱形内写上联系名。
层次模型
满足下面两个条件的基本层次联系的集合为层次模型。 （1）有且只有一个结点没有双亲结点，这个结点称为根结点； （2）除根结点以外的其他结点有且仅有一个双亲结点。
关系模型
子主题
关系模型采用二维表来表示，二维表一般满足下面7个性质： (1）二维表中元组个数是有限的--元组个数有限性； （2）二维表中元组均不相同--元组的唯一性； （3）二维表中元组的次序可以任意交换--元组的次序无关性； （4）二维表中元组的分量是不可分割的基本数据项--元组分量的原子性； （5）二维表中属性名各不相同--属性名唯一性； （6）二维表中属性与次序无关，可任意交换--属性的次序无关性； （7）二维表属性的分量具有与该属性相同的值域--分量值域的统一性。 在二维表中惟一标识元组的最小属性值称为该表的键或码。二维表中可能有若干个健，它 们称为表的侯选码或侯选健。从二维表的所有侯选键选取一个作为用户使用的键称为主键或主 码。表A中的某属性集是某表B的键，则称该属性值为A的外键或外码。 关系操纵：数据查询、数据删除、数据插入、数据修改。 关系模型允许定义三类数据约束，它们是实体完整性约束、参照完整性约束以及用户定义 的完整性约束。
关系代数
关系模型的基本操作
关系模型的基本操作：插入、删除、修改和查询。
其中查询包含如下运算： ①投影运算。从R中选择出若干属性列组成新的关系。 ②选择运算。选择运算是一个一元运算，关系R通过选择运算（并由该运算给出所选择的 逻辑条件）后仍为一个关系。设关系的逻辑条件为F，则R满足F的选择运算可写成：σF(R) ③笛卡尔积运算。设有n元关系R及m元关系S，它们分别有p、q个元组，则关系R与S经笛 卡尔积记为R×S，该关系是一个n+m元关系，元组个数是p×q，由R与S的有序组组合而成。
数据库设计与管理
数据库设计概述
数据库设计中有两种方法，面向数据的方法和面向过程的方法
面向数据的方法是以信息需求为主，兼顾处理需求；面向过程的方法是以处理需求为主，兼顾信息需求。由于数据在系统中稳定性高，数据已成为系统的核心，因此面向数据的设计方 法已成为主流
数据库设计目前一般采用生命周期法，即将整个数据库应用系统的开发分解成目标独立的 若干阶段。它们是：需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段、编码阶段、 测试阶段、运行阶段和进一步修改阶段。在数据库设计中采用前4个阶段。
数据库设计中一般采用前4个阶段，它们的成果分别是需求说明书、概念数据模型、逻辑数据模型和数据库 内模式。
软件工程基本概念
软件定义和软件特点
软件指的是计算机系统中与硬件相互依存的另一部分，包括程序、数据和相关文档的完整 集合。程序是软件开发人员根据用户需求开发的、用程序设计语言描述的、适合计算机执行的 指令序列。数据是使程序能正常操纵信息的数据结构。文档是与程序的开发、维护和使用有关 的图文资料。。可见，软件由两部分组成： （1）机器可执行的程序和数据； （2）机器不可执行的，与软件开发、运行、维护、使用等有关的文档。
软件的特点： （1）软件是逻辑实体，而不是物理实体，具有抽象性； （2）没有明显的制作过程，可进行大量的复制； （3）使用期间不存在磨损、老化问题； （4）软件的开发、运行对计算机系统具有依赖性； （5）软件复杂性高，成本昂贵； （6）软件开发涉及诸多社会因素。 根据应用目标的不同，软件可分应用软件、系统软件和支撑软件（或工具软件）。
软件工程过程和软件生命周期
软件设计的基本概念
从技术观点上看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。 （1）结构设计定义软件系统各主要部件之间的关系； （2）数据设计将分析时创建的模型转化为数据结构的定义； （3）接口设计是描述软件内部、软件和协作系统之间以及软件与人之间如何通信； （4）过程设计则是把系统结构部件转换为软件的过程性描述。
从工程管理角度来看，软件设计分两步完成：概要设计和详细设计。 （1）概要设计将软件需求转化为软件体系结构、确定系统级接口、全局数据结构或数据库 模式； （2）详细设计确立每个模块的实现算法和局部数据结构，用适当方法表示算法和数据结构 的细节。
2．软件设计的基本原理 （1）抽象：软件设计中考虑模块化解决方案时，可以定出多个抽象级别。抽象的层次从概 要设计到详细设计逐步降低。 （2）模块化：模块是指把一个待开发的软件分解成若干小的简单的部分。模块化是指解决 一个复杂问题时自顶向下逐层把软件系统划分成若干模块的过程。 （3）信息隐蔽：信息隐蔽是指在一个模块内包含的信息（过程或数据），对于不需要这些 信息的其他模块来说是不能访问的。 （4）模块独立性：模块独立性是指每个模块只完成系统要求的独立的子功能，并且与其他 模块的联系最少且接口简单。模块的独立程度是评价设计好坏的重要度量标准。衡量软件的模 块独立性使用耦合性和内聚性两个定性的度量标准。内聚性是信息隐蔽和局部化概念的自然扩 展。一个模块的内聚性越强则该模块的模块独立性越强。一个模块与其他模块的耦合性越强则 该模块的模块独立性越弱。 内聚性是度量一个模块功能强度的一个相对指标。内聚是从功能角度来衡量模块的联系， 它描述的是模块内的功能联系。内聚有如下种类，它们之间的内聚度由弱到强排列：偶然内聚、 逻辑内聚、时间内聚、过程内聚、通信内聚、顺序内聚、功能内聚。 耦合性是模块之间互相连接的紧密程度的度量。耦合性取决于各个模块之间接口的复杂度、 调用方式以及哪些信息通过接口。耦合可以分为下列几种，它们之间的耦合度由高到低排列： 内容耦合、公共耦合、外部耦合、控制耦合、标记耦合、数据耦合、非直接耦合。 在程序结构中，各模块的内聚性越强，则耦合性越弱。一般较优秀的软件设计，应尽量做到高内聚，低耦合，即减弱模块之间的耦合性和提高模块内的内聚性，有利于提高模块的独立性。
详细设计
详细设计的任务是为软件结构图中的每个模块确定实现算法和局部数据结构，用某种选定 的表达表示工具算法和数据结构的细节。
详细过程设计的常用工具有： （1）图形工具：程序流程图，N-S，PAD，HIPO。 （2）表格工具：判定表。 （3）语言工具：PDL（伪码）。 程序流程图的5种控制结构：顺序型、选择型、先判断重复型、后判断重复型和多分支选择 型。 方框图中仅含5种基本的控制结构，即顺序型、选择型、多分支选择型、WHILE重复型和 UNTIL重复型。 PAD图表示5种基本控制结构，即顺序型、选择型、多分支选择型、WHILE重复型和UNTIL 重复型。 过程设计语言（PDL）也称为结构化的语言和伪码，它是一种混合语言，采用英语的词汇 和结构化程序设计语言，类似编程语言。 PDL可以由编程语言转换得到，也可以是专门为过程描述而设计的。
软件测试（发现程序中的错误）
单元测试
是对软件设计的最小单位--模块（程序单元）进行正确性检验测试。单元测试的 技术可以采用静态分析和动态测试。
集成测试
测试和组装软件的过程，主要目的是发现与接口有关的错误，主要依据是概要 设计说明书。集成测试所设计的内容包括：软件单元的接口测试、全局数据结构测试、边界条 件和非法输入的测试等。集成测试时将模块组装成程序，通常采用两种方式：非增量方式组装 和增量方式组装。
验收测试
确认测试的任务是验证软件的功能和性能，以及其他特性是否满足了需求规格说明中确定 的各种需求，包括软件配置是否完全、正确。确认测试的实施首先运用黑盒测试方法，对软件 进行有效性测试，即验证被测软件是否满足需求规格说明确认的标准。
系统测试
系统测试是通过测试确认软件，作为整个基于计算机系统的一个元素，与计算机硬件、外 设、支撑软件、数据和人员等其他系统元素组合在一起，在实际运行（使用）环境下对计算机 系统进行一系列的集成测试和确认测试。
具体实施一般包括：功能测试、性能测试、操作测试、配置测试、外部接口测 试、安全性测试等。
软件调试
在对程序进行了成功的测试之后将进入程序调试（通常称Debug，即排错）。程序的调试任 务是诊断和改正程序中的错误。调试主要在开发阶段进行。 程序调试活动由两部分组成，一是根据错误的迹象确定程序中错误的确切性质、原因和位 置；二是对程序进行修改，排除这个错误。程序调试的基本步骤： （1）错误定位。从错误的外部表现形式入手，研究有关部分的程序，确定程序中出错位置， 找出错误的内在原因； （2）修改设计和代码，以排除错误； （3）进行回归测试，防止引进新的错误。
调试原则可以从以下两个方面考虑： （1）确定错误的性质和位置时的注意事项 分析思考与错误征兆有关的信息；避开死胡同；只把调试工具当作辅助手段来使用；避免 用试探法，最多只能把它当作最后手段。 （2）修改错误原则 在出现错误的地方，很可能有别的错误；修改错误的一个常见失误是只修改了这个错误的征兆 或这个错误的表现，而没有修改错误本身；注意修正一个错误的同时有可能会引入新的错误； 修改错误的过程将迫使人们暂时回到程序设计阶段；修改源代码程序，不要改变目标代码
n(n-1)/2
最坏情况比较次数