1、计算机二级考试公共基础知识冲刺复习笔记计算机二级公共基础知识复习笔记全部的基本概念Point1：算法的基本概念1、算法：是指解题方案的准确而完整的描述。(1)算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。程序也可以作为算法的一种描述，但程序通常还要考虑程序运行时的环境限制等。(2)算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。2、算法的基本特征：(1)可行性(2)确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性；例在特殊情况时，数学公式是正确的，但计算机就是无法操作。(3)有穷性，算法必须
2、能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义。例如1/3的无理数问题。(4)拥有足够的情报。所有的各种可能情况都要考虑到。3、一个算法的优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。(1)算法的时间复杂度是指执行算法所需要的计算工作量，可以执行算法的过程中所需要的基本运算的执行次数来度量。分析算法工作量的方法有：平均性态分析、最坏情况分析。(2)算法的空间复杂度是指执行这个算法所需要的内存空间。主要包括：算法程序所占的空间；输入的初始数据所占的空间；算法执行过程中所需要的额外空间。Poi
3、nt2：软件工程基本概念考点精讲1、计算机软件是包括程序、数据及相关文档的完整集合。是计算机系统中与硬件相互依存的部分。软件按功能分为应用软件、系统软件、支撑软件（或工具软件）。2、软件工程源自于软件危机。(1)软件危机主要表现在成本、质量、生产率等问题。(2)软件工程的主要思想是强调在软件开发过程中需要应用工程化原则，软件工程学的主要研究对象包括软件开发与维护的技术、方法、工具和管理等方面。(3)软件工程包括三个要素，即方法、工具和过程。3、通常把软件产品从提出、实现、使用、维护到停止使用(退役)的过程称为软件生命周期。(1)可以将软件生命周期分为软件定义、软件开发及软件运行维护三个阶段。(
4、2)软件生命周期的主要活动阶段是：可行性研究与计划制定；需求分析；软件设计；软件实现；软件测试；运行和维护。Point3：数据库的基本概念考点精讲1、数据库的基本概念(1)数据：实际上就是描述事物的符号记录。数据的特点：有一定的结构，有型与值之分，如整型、实型、字符型等。而数据的值给出了符合给定型的值，如整型值15。(2)数据库(DataBase，简称为DB)：是数据的集合，具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序共享。数据库存放数据是按数据所提供的数据模式存放的，具有集成与共享的特点。数据库技术的根本目标是要解决数据的共享问题。2、数据库系统(Da
5、taBaseSystem，简称为DBS)由数据库(数据)、数据库管理系统(软件)、数据库管理员(人员)、硬件平台(硬件)、软件平台(软件)五个部分构成。(1)数据库管理系统提供以下的数据语言：数据定义语言（DDL）：负责数据的模式定义与数据的物理存取构建；数据操纵语言：负责数据的操纵，如查询与增加、删除、修改等；数据控制语言：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等。(2)数据库系统的特点：数据的集成性；数据高共享性与低冗余性；数据独立性：数据独立性是数据与程序之间互不依赖，也就是数据的逻辑结构、存储结构与存取方式的改变不会影响应用程序。3、据库管理系统(DataBaseMa
6、nagementSystem，简称为DBMS)是系统软件，负责对数据库的数据组织、数据操纵、数据维护、控制及保护和数据服务等。数据库管理系统是数据库系统的核心。4、数据管理经历了人工管理、文件系统、数据库系统三个阶段。文件系统阶段的特点是数据满足一个特定格式而存储，不同程序中使用的数据仍会出现重复存储，也会导致数据冗余。数据库技术的主要目的是有效地管理和存取大量的数据资源，数据库系统阶段的数据独立性最高。5、数据独立性包括物理独立性和逻辑独立性。-11-(1)物理独立性：数据的物理结构(如存储设备更换、物理存储方式)的改变，不影响数据库的逻辑结构，也不引起应用程序的变化。(2)逻辑独立性：数据
7、库整体逻辑结构(如修改数据、增加新数据类型、改变数据间联系等)改变，不需要修改应用程序。6、数据库系统在其内部具有三级模式：概念模式、内部模式与外部模式。(1)概念模式：它是数据库系统中全局数据逻辑结构的描述，是全体用户（应用）的公共数据视图。概念模式主要描述数据的概念记录类型以及它们之间的关系，它还包括一些数据间的语义约束，对它的描述可用DBMS中的DDL语言定义。(2)内部模式：又称物理模式，它给出了数据库物理存储结构与物理存取方法，如数据存储的文件结构、索引、集簇及hash等存取方式与存取路径，内模式的物理特性主要体现在操作系统及文件级上，它还未深入到设备级(如磁盘及磁盘操作)上。DBM
8、S一般提供相关的内模式描述语言(内模式DDL)。(3)外部模式：也称子模式或用户模式，它是用户的数据视图，也就是用户所见到的数据模式，它由概念模式推导而出。在一般的DBMS中都提供相关的外模式描述语言(外模式DDL)。7、数据库系统的两级映射：概念模式到内部模式的映射，外部模式到概念模式的映射。(1)数据的物理独立性：当数据库的存储结构发生变化时，通过修改“概念模式到内部模式的映射”，使得数据库的概念模式不变，其外模式不变，应用程序不用修改，保证了数据的物理独立性。(2)数据的逻辑独立性：当概念模式发生变化时，通过修改“外部模式到概念模式的映射”，使得用户所用的外模式不变，从而应用程序也不用修
9、改，保证了数据的逻辑独立性。Point4：程序设计方法与风格考点精讲1、养成良好的程序设计的设计风格，主要应考虑下述因素：(1)源程序文档化：符号名的命名有一定含义，便于理解；正确的注释帮助读者理解程序；程序层次清晰。-16-(2)数据说明的方法：数据说明的次序规范化；说明语句中变量安排有序化；使月注释来说明复杂数据结构。(3)语句的结构：程序应该简单易懂，语句构造应该简单直接。(4)输入和输出。2、注释分序言性注释和功能性注释，语句结构清晰第一、效率第二。Point5：结构化程序设计考点精讲1、结构化程序设计的主要目的是使程序结构良好、易读、易理解、易维护。它的原则主要包括：自顶向下；逐步求
10、精；模块化；限制使用goto语句。2、结构化程序设计方法可用三种基本结构实现：顺序结构；选择结构；重复结构。3、在结构化程序设计的具体实施中，要注意把握如下要素：(1)使用程序设计语言中的顺序结构、选择结构、循环结构等控制结构来表示程序的控制逻辑。(2)选用的控制结构只准许有一个入口和一个出口。(3)程序语句组成容易识别的程序块，每块只有一个入口和一个出口。(4)复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现。(5)语言中所没有的控制结构，应该采用前后一致的方法来模拟。(6)严格控制goto语句的使用。Point6：面向对象的程序设计方法考点精讲1、对象(object)：对象用来表示客观世
11、界中的任何实体。面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。2、类(class)和实例(instance)：将属性、操作相似的对象归为类，类是具有共同属性、共同方法的对象的集合；一个具体对象称为类的实例。3、消息(message)：面向对象的世界是通过对象与对象间彼此的相互合作来推动的，对象间的这种相互合作需要一个机制协助进行，这个机制称为消息。消息是一个实例与另一个实例之间传递的信息，是请求对象执行某一处理或回答某一要求的信息，它统一了数据流和控制流。4、继承(inheritance)：
12、继承是面向对象方法的一个主要特征。继承是使用已有的类作为基础（直接获得已有的性质和特征）建立新类的定义技术。已有的类可以当做基类引用，则新类可当做派生类引用。5、多态性(polymorphism)：对象根据所接受的消息而作出动作，同样的消息被不同的对象接受时可导致完全不同的行动，该现象称为多态性。Point7：基本排序与查找的算法考点精讲1、查找(1)顺序查找是一种最基本和最简单的查找方法。它的思路是，从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。对于长度为n的有序线性表，在最坏情况下，顺序查找需要
13、比较n次。(2)对于大的线性表来说，顺序查找的效率是很低的。虽然顺序查找的效率不高，但在下列两种情况下也只能采用顺序查找：无序的线性表；即使是有序的线性表，如果采用链式存储结构，也只能顺序查找。-21-(3)二分查找是针对有序表进行查找的简单、有效而又较常用的方法。其基本思想是：首先选择有序表中间位置的记录，将其关键字与给定关键字k进行比较，若相等，则查找成功；否则，若k值比该关键字值大，则要找的元素一定在表的后半部分(或称右子表)，则继续对右子表进行二分查找；若k值比该关键字值小，则要找的元素一定在表的前半部分(左子表)，同样应继续对左子表进行二分查找。每进行一次比较，要么找到要查找的元素，
14、要么将查找的范围缩小一半。如此递推，直到查找成功或把要查找的范围缩小为空(查找失败)。(4)显然，仅当有序线性表为顺序存储时才能用二分查找，并且，二分查找的效率要比顺序查找高得多。可以证明，对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较log2n次，而顺序查找需要比较n次。2、排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。常用的排序方法(1)交换类排序法：冒泡排序法，需要比较的次数为n(n-1)/2；快速排序法，最坏情况需要比较的次数为n(n-1)/2。(2)插入类排序法：简单插入排序法，最坏情况需要n(n-1)/2次比较；希尔排序法，最坏情况需要O(n1.5)次比较。
15、(3)选择类排序法：简单选择排序海最坏情况需要n(n-1)/2次比较；堆排序法，最坏情况需要O(nlog2n)次比较。软件工程与数据库设计Point1：数据模型考点精讲1、数据模型的概念：是数据特征的抽象，从抽象层次上描述了系统的静态特征、动态行为和约束条件，为数据库系统的信息表与操作提供一个抽象的框架。描述了数据结构、数据操作及数据约束。2、数据模型分为三种：(1)概念数据模型：简称概念模型，是对客观世界复杂事物的结构描述及它们之间的内在联系的刻画。主要有：E-R模型、扩充的E-R模型、面向对象模型及谓词模型等。(2)逻辑数据模型：又称物理模型，是一种面向数据库系统的模型，该模型着重于在数据
16、库系统一级的实现。主要有：层次模型、网状模型、关系模型、面向对象模型等。(3)物理数据模型：又称物理模型，它是一种面向计算机物理表示的模型，此模型给出-25-了数据模型在计算机上物理结构的表示。3、E-R模型(1)E-R模型的基本概念实体：现实世界中的事物；属性：事物的特性；联系：现实世界中事物间的关系。(2)实体集的关系有一对一（一个学校和一个校长）、一对多（学生和宿舍）、多对多（老师与学生）的联系。两个实体集间联系可分为：一对一联系(onetoonerelationship)简记为1:1。一对多联系(onetomanyrelationship)简记为1:m或m:1。多对多联系(monyto
17、manyrelationship)简记为m:n。(3)E-R模型三个基本概念之间的联接关系：实体是概念世界中的基本单位，属性有属性域，每个实体可取属性域内的值。一个实体的所有属性值叫元组。(4)E-R模型的图示法：实体集表示法：在矩形内写上实体集的名字；属性表示法：在椭圆形内写上属性的名称；联系表示法：用菱形内写上联系的名称；实体集与属性的联接关系：用无向线段来表示；实体集与联系间的联接关系；E-R模型由实体、属性、联系这三个基本概念细成。只有实体、联系、属性三者结合起来才能表示一个现实世界。4、关系模型(1)在关系模型中，把数据看成一个二维表，每一个二维表称为一个关系。表中的每一列称为一个属
18、性，相当于记录中的一个数据项，对属性的命名称为属性名，表中的一行称为一个元组，相当于记录值。(2)在二维表中凡能唯一标识元组的最小属性称为键或码。从所有侯选健中选取一个作为用户使用的键称主键。表A中的某属性是某表B的键，则称该属性集为A的外键或外码。(3)关系中的数据约束：实体完整性约束：约束关系的主键中属性值不能为空值；参照完全性约束：是关系之间的基本约束；用户定义的完整性约束：它反映了具体应用中数据的语义要求。(4)关系模型的数据操作即是建立在关系上的数据操作，一般有查询、增加、删除和修改四种操作。Point2：软件定义阶段考点精讲1、软件定义阶段：包括制定计划与需求分析。可行性研究与计划
19、制定：确定总目标，可行性研究，探讨解决方案，制定开发计划。2、需求分析：对待开发软件提出的需求进行分析并给出详细的定义。主要工作是编写软件需求规格说明书及用户手册。(1)需求分析的任务是导出目标系统的逻辑模型，解决“做什么”的问题。(2)需求分析一般分成4个阶段：需求获取，需求分析，编写需求规格说明书，需求评审。(3)软件需求规格说明书（SRS），是需求分析阶段的最后成果，是软件开发中的重要文档之一。该说明把在软件计划中确定的软件范围加以展开，制定出完整的信息描述，详细的功能说明，恰当的检验标准以及其他与要求有关的数据。其特点有：正确性；无岐义性；完整性；可验证性；一致性；可理解性；可追踪性。
20、(4)需求分析的方法：结构化分析方法：包括面向数据流的结构化分析方法（SA），面向数据结构的Jackson方法（JSD）和面向数据结构的结构化数据系统开发方法（DSSD）。面向对象的分析的方法（OOA）。从需求分析建立的模型的特性来分：静态分析和动态分析。3、结构化方法的核心和基础是结构化程序设计理论。结构化分析方法的实质：面向数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。数据字典是结构化分析的核心。(1)结构化分析的常用工具有：数据流图；数据字典；判定树；判定表。(2)数据流图（DFD）：描述数据处理过程的工具，是需求理解的逻辑模型的图形
21、表示，它直接支持系统功能建模。建立数据流图的步骤：由外向里，自顶向下，逐层分解，完善求精。数据流图的主要图形元素：椭圆：代表加工（转换）。输入数据经加工变换产生输出。箭头：代表数据流。沿箭头方向传送数据的通道，一般在旁边标注数据流名。双横线：代表存储文件（数据）。表示处理过程中存入各种数据的文件。矩形：代表源，潭。表示系统和环境的接口，属系统之外的实体。(3)数据字典：是结构化分析的核心。是对所有与系统相关的数据元素的一个有组织的列表，以及精确的、严格的定义，使得用户和系统分析员对于输入、输出、存储成分和中间计算结果有共同的理解。概括地说，数据字典是对DFD中出现的被命名的图形元素的确切解释。
22、(4)判定树：是从问题定义的文字描述中分清哪些是判定的条件，哪些是判定的结论，根据描述材料中的连接词找出判定条件之间的从属关系、并列关系、选择关系，根据它们-31-构造判定树。(5)判定表：与判定树相似，当数据流图中的加工要依赖于多个逻辑条件的取值，即完成该加工的一组动作是由于某一组条件取值的组合而引发的，使用判定表描述比较适宜。Point3：关系代数考点精讲1、关系模型的基本运算：并、差、交、广义笛卡尔积、投影、选择、连接、除。关系是有序组的集合，可将关系操作看成是集合的运算。2、并、差、交(1)并运算。RS。(2)差运算。R-S。(3)交运算。交运算是将两个关系中共有元组表示为RS。3、广
23、义笛卡尔积、除(1)广义笛卡尔积。笛卡儿积运算：两个关系的合并操作可用笛卡儿积表示。设有n元关系R及m元关系R，它们分别有p，q个元组，则R与S的笛卡儿积为RS，该关系是一个n+m元关系，元组个数是pq。(2)除运算。将一个关系中元组去除另一个关系中元组，表示为：R/S。4、投影运算：投影运算是一个一元运算，一个关系通过投影运算后仍为一个关系R。R是这样一个关系，它是R中投影运算所指出的那些域的列所组成的关系。5、选择运算：选择运算是一个一元运算，关系R通过选择运算后仍为一个关系。这个关系是由R中那些满足逻辑条件的元组所组成。6、连接运算：Point4：软件设计阶段考点精讲1、软件设计是软件工
24、程的重要阶段，是一个把软件需求持换为软件表示的过程。软件设计的基本目标是用比较抽象慨括的方式确定目标系统如何完成预定的任务，即软件设计是确定系统的物理模型。(1)需求分析主要解决“做什么”问题，软件设计解决“怎么做”的问题。从技术观点来看，软件设计包括软件结构设计、数据设计、接口设计、过程设计。结构设计：定义软件系统各主要部件之间的关系。数据设计：将分析时创建的模型转化为数据结构的定义。接口设计：描述软件内部、软件和协作系统之间以及软件与人之间如何通信。过程设计：把系统结构部件转换成软件的过程描述。(2)从工程管理角度来看，软件设计包括：概要设计和详细设计。2、软件设计中应该遵循的基本原理和与
25、软件设计有关的概念(1)抽象：就是把事物本质的共同特征提取出来而不考虑其他细节。(2)模块化：是指把一个待开发的软件分解成若干小的简单的部分。但划分模块不是越多越好。(3)信息隐蔽：是指在一个模块中包含的信息，对于不需求这些信息的其他模块来说是不能访问的。(4)模块独立性：每个模块只完成系统要求的独立的子功能，并且与其他模块的联系最少且接口简单。这是评价设计好坏的重要度量标准。3、衡量软件模块独立性使用耦合性和内聚性两个定性的度量标准：(1)内聚性是一个模块内部各个元素间彼此结合的紧密程度的度量。内聚是从功能角度来度量模块内的联系。(2)耦合性：耦合性是模块间互相连接的紧密程度的度量。耦合性的
26、强弱取决于各个模块之间接口的复杂度、调用方式以及哪些信息通过接口。在程序结构中各模块的内聚性越强，则耦合性越弱。优秀软件应高内聚、低耦合。4、软件概要设计(1)概要设计的基本任务是：设计软件系统结构；数据结构及数据库设计；编写概要设-37-计文档；概要设计文档评审。(2)结构图（SC），是概要设计阶段的工具。其图形元素为：矩形表示一般模块。箭头表示模块间的调用关系。在结构图中还可以用带注释的箭头表示模块调用过程中来回传递的信息。用带实心圆的箭头表示传递的是控制信息。空心圆箭心表示传递的是数据。结构图的基本形式：基本形式、顺序形式、重复形式、选择形式。结构图有四种模块类型：传入模块、传出模块、变
27、换模块和协调模块。结构图的形态特征：包括深度、宽度、扇出、扇入。深度：表示控制的层数宽度：表示整体控制跨度扇入：调用一个给定模块的模块个数。扇出：一个模块直接调用的其他模块数。(3)面向数据流的设计方法：典型的数据流类型有两种：变换型和事务型。变换型系统结构图由输入、中心变换、输出三部分组成。事务型数据流的特点是：接受一项事务，根据事务处理的特点和性质，选择分派一个适当的处理单元，然后给出结果。5、软件详细设计(1)是为软件结构图中的每一个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节。(2)常见的过程设计工具有：图形工具：程序流程图（PDF），N-S，PAD（问
28、题分析图），HIPO表格工具：判定表语言工具：PDL（伪码）Point5：数据库设计与管理考点精讲1、数据库设计是数据应用的核心。数据库设计的两种方法：(1)面向数据：以信息需求为主，兼顾处理需求；(2)面向过程：以处理需求为主，兼顾信息需求。2、数据库的生命周期：需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段、编码阶段、测试阶段、运行阶段、进一步修改阶段。3、数据库设计包括：需求分析、概念设计、逻辑设计、物理设计。(1)需求分析：常用结构分析方法和面向对象的方法。结构化分析（简称SA）方法用自顶向下、逐层分解的方式分析系统。用数据流图表达数据和处理过程的关系。对数据库设计来讲，数据字
29、典是进行详细的数据收集和数据分析所获得的主要结果。数据字典是各类数据描述的集合，包括5个部分：数据项、数据结构、数据流（可以是数据项，也可以是数据结构）、数据存储、处理过程。(2)数据库概念设计的目的是分析数据间内在语义关联，并建立数据的抽象模型。设计的方法有两种：集中式模式设计法（适用于小型或并不复杂的单位或部门）；视图集成设计法。常见的方法有：E-R模型与视图集成。视图设计一般有三种设计次序：自顶向下、由底向上、由内向外。视图集成的实质是将所有的局部视图统一与合并成一个完整的数据模式，常见的几种局部设计的冲突：命名冲突、概念冲突、域冲突、约束冲突。(3)数据库的逻辑设计主要工作是将E-R图
30、转换成RDBMS中的关系模式。逻辑设计的另一个重要内容是关系视图的设计，又称为外模式设计。关系视图设计：关系视图的设计又称外模式设计。关系视图的主要作用：提供数据逻辑独立性：使应用程序不爱逻辑模式变化的影响。能适应用户对数据的不同需求；有一定数据保密功能。(4)数据库的物理设计主要目标是对数据内部物理结构做调整并选择合理的存取路径，以提高数据库访问速度有效利用存储空间。一般RDBMS中留给用户参与物理设计的内容大致有索引设计、集成簇设计和分区设计。4、数据库管理的内容：(1)数据库的建立；(2)数据库的调整；(3)数据库的重组；(4)数据库安全性与完整性控制；(5)数据库的故障恢复；(6)数据
31、库监控。Point6：软件测试考点精讲1、软件测试定义：使用人工或自动手段来运行或测定某个系统的过程，其目的在于检验它是否满足规定的需求或是弄清预期结果与实际结果之间的差别。2、软件测试的目的：软件测试是为了发现错误而执行程序的过程。3、软件测试的准则：所有测试都应追溯到需求；严格执行测试计划，排除测试的随意性；充分注意测试中的群集现象；程序员应避免检查自己的程序；穷举测试不可能。4、软件测试的方法和技术分类：从是否需要执行被测试软件的角度，分为静态测试和动态测试方法；按照功能划分，分为白盒测试和黑盒测试方法。5、静态测试包括代码检查、静态结构分析、代码质量度量。不实际运行软件，主要通过人工进行；动态测试是基本计算机的测试，主要包括白盒测试方法和黑盒测试方法。6、白盒测试：在程序内部进行，主要用于完成软件内部操作的验证。主要方法有逻辑覆盖、基本路径测试。黑盒测试：主要诊断功能不对或遗漏、界面错误、数据结构或外部数据率访问错误、性能错误、初始化和终止条件错，用于软
